Many-core algorithms for in-memory column store databases

1. A non-transitory computer program product storing instructions that, when executed by at least one programmable processor forming part of at least one computing system, cause the at least one programmable processor to perform operations comprising:

receiving a query request comprising a definition of a query of a database persisted in a column-based in-memory storage;

identifying a pattern in at least part of the query;

matching the identified pattern with a plurality of matching patterns among a set of pre-defined patterns, each of the pre-defined patterns having associated therewith at least one pre-compiled query execution sub-component of a plurality of pre-compiled query execution sub-components retained in a library, and wherein the matching includes selecting a selected matched pattern from among the plurality of matching patterns;

selecting, based on the matching of the identified patterns with the plurality of matching-patterns, an optimal sequence for processing a plurality of tables that must be joined to respond to the query that avoids intermediate results and allows for the query to be performed in a single pass of the database, wherein at least one matching pattern other than the selected matched pattern produces intermediate results and requires more than two passes of the database;

generating a plan for executing the query, the generating comprising incorporating the pre-compiled query execution sub-component associated with the selected matched pattern into the plan based on a pseudo code representation of the plan derived from the definition; and

executing the query using the generated plan; and

configuring the plan to include the optimal sequence for processing the plurality of tables;

wherein the pseudo code is pre-prepared, pre-compiled, and stored in a library.

2. A computer program product as in claim 1 , wherein the operations further comprise deriving the pseudo code representation of the plan from the definition.

3. A computer program product as in claim 1 , wherein the generating further comprises creating a single function to call the corresponding at least one pre-compiled query execution sub-component.

4. A computer program product as in claim 3 , wherein the single function defines a desired result and accesses a predefined parallelization plan from a set of two or more predefined parallelization plans based at least in part of the matching of the identified pattern.

5. A computer program product as in claim 1 , wherein the pre-compiled query execution sub-component comprises one or more pre-compiled SQL operations expressed in C++.

6. A computer program product as in claim 1 , wherein the matching uses a Boyer-Moore algorithm.

7. A computer program product as in claim 1 , wherein the database forms a computing environment comprising shared memory machines with multiple sockets each containing a multi-core processor with a plurality of cores that simultaneously execute threads and in which each socket can has its own locally attached main memory.

8. A system comprising:

a column-based database storing data in-memory;

at least one programmable processor; and

a machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one programmable processor to perform operations comprising:

receiving a query request comprising a definition of a query of the database;

identifying a pattern in at least part of the query;

matching the identified pattern with a plurality of matching patterns among a set of pre-defined patterns, each of the pre-defined patterns having associated therewith at least one pre-compiled query execution sub-component of a plurality of pre-compiled query execution sub-components retained in a library, and wherein the matching includes selecting a selected matched pattern from among the plurality of matching patterns;

selecting, based on the matching of the identified patterns with the plurality of matching-patterns, an optimal sequence for processing a plurality of tables that must be joined to respond to the query that avoids intermediate results and allows for the query to be performed in a single pass of the database, wherein at least one matching pattern other than the selected matched pattern produces intermediate results and requires more than two passes of the database;

generating a plan for executing the query, the generating comprising incorporating the pre-compiled query execution sub-component associated with the selected matched pattern into the plan based on a pseudo code representation of the plan derived from the definition; and

executing the query using the generated plan;

configuring the plan to include the optimal sequence for processing the plurality of tables;

wherein the pseudo code is pre-prepared, pre-compiled, and stored in a library.

9. A system as in claim 8 , wherein the operations further comprise deriving the pseudo code representation of the plan from the definition.

10. A system as in claim 8 , wherein the generating further comprises creating a single function to call the pre-compiled query execution sub-component and one or more other pre-compiled query execution sub-components to generate the plan.

11. A system as in claim 10 , wherein the single function defines a desired result and accesses a predefined parallelization plan from a set of two or more predefined parallelization plans based at least in part of the matching of the identified pattern.

12. A system as in claim 8 , wherein the pre-compiled query execution sub-component comprises one or more pre-compiled SQL operations expressed in C++.

13. A computer-implemented method comprising:

receiving a query request comprising a definition of a query of a database persisted in a column-based in-memory storage, the query comprising a plurality of subparts;

identifying, for each of at least two subparts of the query, a pattern from at least part of the query;

matching each identified pattern with a pattern among a set of pre-defined patterns, each of the pre-defined patterns having associated therewith at least one pre-compiled query execution sub-component of a plurality of pre-compiled query execution sub-components retained in a library, and wherein the matching includes selecting a selected matched pattern from among the plurality of matching patterns

selecting, based on the matching of the identified patterns with the plurality of matching-patterns, an optimal sequence for processing a plurality of tables that must be joined to respond to the query that avoids intermediate results and allows for the query to be performed in a single pass of the database, wherein at least one matching pattern other than the selected matched pattern produces intermediate results and requires more than two passes of the database;

generating a plan for executing the query, the generating comprising incorporating the pre-compiled query execution sub-component associated with the selected matched pattern into the plan based on a pseudo code representation of the plan derived from the definition; and

executing the query using the generated plan; and

configuring the plan to include the optimal sequence for processing the plurality of tables;

wherein the pseudo code is pre-prepared, pre-compiled, and stored in a library.

14. A computer-implemented method as in claim 13 , further comprising deriving the pseudo code representation of the plan from the definition.

15. A computer-implemented method as in claim 13 , wherein the generating further comprises creating a single function to call the corresponding at least one pre-compiled query execution sub-component.

16. A computer-implemented method as in claim 15 , wherein the single function defines a desired result and accesses a predefined parallelization plan from a set of two or more predefined parallelization plans based at least in part of the matching of each identified pattern.

17. A computer-implemented method as in claim 13 , wherein the pre-compiled query execution sub-component comprises one or more pre-compiled SQL operations expressed in C++.

18. A computer-implemented method as in claim 13 , wherein at least one of the receiving, the identifying, the matching, the generating, and the executing is performed by at least one programmable processor forming part of at least one computing system.