Multiple dimensioned database architecture supporting operations on table groups

• US 8,204,885 B2
• Filed: 06/04/2011
• Issued: 06/19/2012
• Est. Priority Date: 01/07/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Akiban Technologies, Inc. (Apple Inc.)
• Inventors: Herrnstadt, Ori
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US13/153,406
• Publication Number:
  US 20120030246A1
• Time in Patent Office: 381 Days
• Field of Search: 707/713, 707/714, 707/766, 707/722, 707/737, 707/769, 707/809
• US Class Current: 707/737
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A database management system stores data form a plurality of logical tables as independent copies in different format. In one specific example the system organizes tables into table groups and de-normalizes the table in each table group. It also organizes data in a second format including vertical column containers that store all the data for one attribute, there being one column container for each table and each attribute within that table. The receipt of a query causes the system to develop a query plan that can interact with either or both of the container sets.

Claims

1. A non-transitory computer-readable storage medium storing a computer readable program of computer instructions, wherein the computer readable program, when executed on a data processing system, causes the data processing system to carry out operations to process a query against a database, the database storing information from a data dictionary that has been configured into one or more table groups, the operations comprising:

(a) identifying a set of one or more table groups associated with the query (i) constructing a first graph comprising a set of one or more nodes, and one or more links among the one or more nodes, wherein a node in the first graph is associated with a table in the data dictionary, wherein a link is associated with a directional edge corresponding to a link between a primary key and a foreign key in the data dictionary;

(ii) constructing a second graph comprising a set of one or more nodes, and one or more links among the one or more nodes, wherein a node in the second graph is associated with a table identified in the query, and wherein a link in the second graph is a join predicate in the query; and

(iii) comparing the first and second graphs to determine which tables and relationships are common to both the first and second graphs;

(b) for each table group, and until all table groups are evaluated;

(i) selecting a table group from the set of one or more table groups;

(ii) identifying one or more tables in the selected table group that are associated with the query; and

(iii) generating an intermediate resultset for the selected table group; and

(c) processing intermediate resultsets from the table groups to create a final result.

2. The non-transitory computer-readable storage medium as described in claim 1 wherein the generating step determines an optimal retrieval option for returning the intermediate resultset.

3. The non-transitory computer-readable storage medium as described in claim 2 wherein the optimal retrieval option identifies a join order for tables in the selected table group.

4. The non-transitory computer-readable storage medium as described in claim 2 wherein the optimal retrieval option identifies a best physical representation in the database for tables in the selected table group.

5. The non-transitory computer-readable storage medium as described in claim 1 wherein the comparing step identifies the tables within the table group that are associated with the query and that are already joined using the defining relationships in the data dictionary.

6. The non-transitory computer-readable storage medium as described in claim 5 wherein the comparing step also identifies at least first and second tables within the table group that are associated with the query but that are not joined using a defining relationship.

7. The non-transitory computer-readable storage medium as described in claim 6 wherein the method further includes processing the first and second tables independently.

8. The non-transitory computer-readable storage medium as described in claim 5 further including:

extracting attributes accessed in the query that belong to one of the overlapped tables in the selected table group and that are not primary keys; and

using the extracted attributes to produce the intermediate resultset for the selected table group.

9. The non-transitory computer-readable storage medium as described in claim 8 wherein a percentage of attributes extracted is based on a selectivity value indicating a percentage of data needed to be accessed from the database to generate the intermediate resultset for the selected table group.

10. The non-transitory computer-readable storage medium as described in claim 9 wherein a given selectivity value indicates that substantially all rows in the database associated with an attribute are involved.

11. The non-transitory computer-readable storage medium as described in claim 1 wherein the table group identified includes one root table and at least one other table related thereto, each table in the table group being characterized as having columns of attributes and rows of data.

12. The non-transitory computer-readable storage medium as described in claim 1 wherein the first graph includes a root node that is a node in the first graph to which no directional edges are directed after the one or more lookup edges are deleted.