Query Execution Systems and Methods

• US 20110302151A1
• Filed: 02/22/2011
• Published: 12/08/2011
• Est. Priority Date: 06/04/2010
• Status: Active Grant

• Current Assignee: Yale University
• Original Assignee: Yale University
• Inventors: Abadi, Daniel, Bajda-Pawlikowski, Kamil
• Granted Patent: US 8,935,232 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

System, method, and computer program product for processing data are disclosed. The method includes receiving a query for processing of data, wherein the data is stored in a table in a plurality of tables, wherein the table is stored on at least one node within the database system, determining an attribute of the table and another table in the plurality of tables, partitioning one of the table and the another table in the plurality of tables using the determined attribute into a plurality of partitions, and performing a join of at least two partitions of the table and the another table using the determined attribute. The join is performed on a single node in the database system.

Claims

1. A method for processing data in a database system containing a plurality of nodes, the method comprising the steps of:

receiving a query for processing of data, wherein the data is stored in a table in a plurality of tables, wherein the table is stored on at least one node within the database system;

determining an attribute of the table and another table in the plurality of tables;

partitioning one of the table and the another table in the plurality of tables using the determined attribute into a plurality of partitions; and

performing a join of at least two partitions of the table and the another table using the determined attribute;

wherein the join is performed on a single node in the database system.

2. The method according to claim 1, wherein the table is smaller than another table.

3. The method according to claim 2, further comprising

determining a join attribute for each table partition of the stored data;

determining whether to re-partition at least one table of the stored data using the join attribute such that partitions of tables having the same join attribute are joined at a single node in the database system; and

using the join attribute, performing a join of tables at the single node.

4. The method according to claim 2, wherein the table is configured to be distributed to all nodes containing a partition of the another table, the table and the partition of the another table being partitioned on determined attribute.

5. The method according to claim 3, further comprising

selecting a column within a table to generate the column join attribute for the step performing of the join;

and

using the column join attribute, performing a join of tables at the single node in the database system.

6. The method according to claim 5, further comprising

initiating a first processing task;

using the initiated first processing task, performing the partitioning and joining steps.

7. The method according to claim 6, further comprising

initiating a second processing task;

using the initiated second processing task, performing said selecting and joining steps.

8. The method according to claim 7, wherein the first processing task and the second processing task are MapReduce processing tasks.

9. The method according to claim 2, wherein the smaller table is a dictionary table.

10. A system for processing data in a database system containing a plurality of nodes, comprising:

a receiving module configured to received a query for processing of data, wherein the data is stored in a table in a plurality of tables, wherein the table is stored on at least one node within the database system;

a partitioning module configured to partition one of the table and the another table in the plurality of tables using a determined attribute into a plurality of partitions, wherein the determined attribute is an attribute of the table and the another table; and

a join module configured to perform a join of at least two partitions of the table and the another table using the determined attribute;

wherein the join is performed on a single node in the database system.

11. The system according to claim 10, wherein the table is smaller than another table.

12. The system according to claim 11, wherein a join attribute is determined for each table partition of the stored data;

wherein the join module is configured to perform a join of tables at the single node using the determined join attribute after determining whether to re-partition at least one table of the stored data using the join attribute such that partitions of tables having the same join attribute are joined at a single node in the database system.

13. The system according to claim 11, wherein the table is configured to be distributed to all nodes containing a partition of the another table, the table and the partition of the another table being partitioned on determined attribute.

14. The system according to claim 12, further comprising

selecting module for selecting a column within a table to generate the column join attribute for the step performing of the join;

and

wherein using the column join attribute, the join module is configured to perform a join of tables at the single node in the database system.

15. The system according to claim 14, wherein the portioning and join are configured to be performed during a first processing task.

16. The system according to claim 15, wherein the selecting and join are configured to be performed during a second processing task.

17. The system according to claim 16, wherein the first processing task and the second processing task are MapReduce processing tasks.

18. The system according to claim 11, wherein the smaller table is a dictionary table.

19. A computer program product, tangibly embodied in a computer-readable medium, the computer program product being operable to cause a data processing system containing a database system having a plurality of nodes, to perform operations comprising:

receiving a query for processing of data, wherein the data is stored in a table in a plurality of tables, wherein the table is stored on at least one node within the database system;

determining an attribute of the table and another table in the plurality of tables;

partitioning one of the table and the another table in the plurality of tables using the determined attribute into a plurality of partitions; and

performing a join of at least two partitions of the table and the another table using the determined attribute;

wherein the join is performed on a single node in the database system.