System and method for join-partitioning for local computability of query over shared-nothing clusters

• US 8,156,107 B2
• Filed: 02/02/2007
• Issued: 04/10/2012
• Est. Priority Date: 02/02/2007
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Bawa, Mayank, Argyros, Anastasios, Candea, George
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): BIBBEE, JARED M
• Application Number:
  US11/670,936
• Publication Number:
  US 20080189239A1
• Time in Patent Office: 1,894 Days
• Field of Search: 707/2, 707/3, 707/713, 707/971, 707/972, 707/966
• US Class Current: 707/713
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/971 Federated
• CPC Class Codes: Y10S 707/972 Partitioning

Abstract

The present invention addresses the problem of partitioning database relations across a plurality of hosts in a shared-nothing cluster while minimizing communication costs. A new partitioning approach for database relations—join-partitioning—is introduced that focuses on relations and their dependencies to a priori partition the plurality of relations to the plurality of hosts such that each host can locally compute a large class of queries over its partitioned data in isolation at query time, independent of other hosts in the cluster. Such an approach thus overcomes the primary bottleneck, i.e., the network, in deploying database systems over shared-nothing clusters by allowing them to seamlessly scale linearly to tens of thousands of hosts and manage tens or hundreds of terabytes of data.

Claims

1. A system to support data partitioning for local computability of queries, comprising:

a shared-nothing cluster including a plurality of hosts sharing no hard disk drive and/or computer memory among the hosts;

a partitioning module operable to actively partition each of a plurality of relations of a dataset as the dataset is being provided by an external user of the system into a plurality of sub-relations and to store the sub-relations on the plurality of hosts, the partitioning module performing join partitioning while preserving one or more foreign key references locally on each of the hosts, the partitioning module being constrained to provide partitions which have data that allow for local computability of queries, and the sub-relations constrained to always output correct answers in response to a query, and the partitioning module being operable to keep a plurality of partitions of the sub-relations balanced across the plurality of hosts via one or more of;

(i) keeping track of the foreign keys for each of the plurality of sub-relations that are placed on each of the plurality of partitions using a bit-map per referenced relation;

(ii) keeping a score on the number of tuples of the sub-relations that have been placed in each of the plurality of partitions along with a count of the number of distinct dimension keys per relation in each of the plurality of partitions;

(iii) looking up the bit-maps to determine if there are one or more candidate partitions which have all the dimension keys that occur in a tuple;

(iv) inserting the tuple into the partition with the least score of the bit-maps if there are one or more candidate partitions or into the one with the least count if there is no candidate partition; and

(v) updating the bit-maps to reflect the placement of the dimension keys in that partition as are the score and count; and

a query executing module operable to;

receive a query and identify at query time whether the query to the dataset is computable over the plurality of sub-relations locally on each of the plurality of hosts independent of the rest of the plurality of hosts, and in which a given received query is ad hoc and unpredictable, the query executing module being operable to identify local computability of the query at query time by;

(i) constructing a characterization graph of the query whose vertices correspond to relation variables in the query for each of the plurality of databases; and

(ii) determining if there exists a vertex in the characterization graph such that every other vertex in the characteristic graph is reachable from it by following directed edges;

execute the query over the plurality of partitioned sub-relations stored on the plurality of hosts without moving data among the hosts or causing network bottlenecks; and

generate an exact result for each query by merging local query output from the plurality of hosts.

2. The system according to claim 1, wherein:

each of the plurality of hosts is one of;

a server computer, a mainframe computer, a workstation, a laptop or desktop PC, a PDA, a Tablet PC, a Pocket PC, a cell phone, an electronic messaging device, a Java-enabled device, and a FPGA-based device.

3. The system according to claim 1, wherein:

the partitioning module is operable to model the plurality of relations via a snowflake schema; and

the snowflake schema comprises a plurality of relations maintaining one or more of the following information;

a plurality of recurring events, a plurality of participants in the plurality of recurring events, summary of measures of the plurality of recurring events, and time of the plurality of recurring events.

4. The system according to claim 1, wherein:

the partitioning module is operable to model the plurality of relations via a snowflake schema; and

the snowflake schema is a combination of one or more of;

one or more singleton relations, star schema, snowflaked-dimension schema, and one or more summary relations.

5. The system according to claim 3, wherein:

the partitioning module is operable to dynamically determine one or more partition candidates for each of the plurality of relations based on the snowflake schema.

6. The system according to claim 1, wherein:

the query class is an equi-join SELECT-PROJECT-JOIN (SPJ) query.