MULTIPLE DIMENISIONED DATABASE ARCHITECTURE

• US 20090193006A1
• Filed: 01/07/2008
• Published: 07/30/2009
• Est. Priority Date: 01/07/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Akiban Technologies, Inc. (Apple Inc.)
• Inventors: Herrnstadt, Ori
• Granted Patent: US 8,150,850 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. In a database management system including database storage means for storing the data of a logical database model comprising at least one table group wherein each table group includes one root table and at least one other table related thereto, each logical table being characterized as having columns of attributes and rows of data, said database storage means comprising:

A) first data store means for storing all the data in the database in a plurality of memory locations in a first dimension wherein each of the plurality memory locations includes all the data from one row of a root table and all the related data from the other tables in that table group relevant data that one root table row thereby to allow sequential access to all the data in that root table row and its related rows in the other related tables, and

B) second data store means for storing all the data in the database in a plurality of memory locations in a second dimension wherein each memory location includes all the data from one of the attributes in the database and all the corresponding values thereby to allow sequential access to the data in each attribute.

2. A system as recited in claim 1 each of the memory locations in said first and second data store means comprises contiguous memory locations.

3. A system as recited in claim 1 additionally comprising a data dictionary populated with information from the logical database model dictionary that identifies relationships among the tables in different ones of the table groups, said memory locations in said first data store means storing the data related to one row of the root table and other tables in the relationship whereby the data structure inherently links tables in accordance with the relationships thereby eliminating the need to process a join operation each time such relationship is accessed.

4. A system as recited in claim 1 wherein the data for each table group is stored in a container including clusters and cluster rows and wherein:

i) a cluster row comprises a header with a cluster row identification and a body for data for each row in the tables in the table group,

ii) a cluster comprises cluster rows for one row in the root table and corresponding rows in each related table in the table group, and

iii) a container comprises all the clusters for the table group.

5. A system as recited in claim 4 wherein said cluster row identification includes a identifiers for the cluster and the corresponding table in the table group.

6. A system as recited in claim 5 wherein each table includes a unique identifier for each row therein and each said cluster identifier comprises the value of the unique identifier for the root table and each cluster row identifier comprises the unique identifier for the row in the table.

7. A system as recited in claim 5 wherein each header additionally identifies the table in the logical database associated with a cluster row.

8. A system as recited in claim 5 wherein each header additionally includes an attribute identifier for identifying each attribute in a cluster row and whether in that cluster row the attribute is present.

9. A system as recited in claim 5 wherein each header additionally includes a pointer to attribute values in the body of said cluster row.

10. A system as recited in claim 5 wherein the information in each cluster row is stored in contiguous memory locations.

11. A system as recited in claim 10 wherein the information in each cluster is stored in contiguous memory locations.

12. A system as recited in claim 11 wherein the information in each container is stored in contiguous memory locations.

13. A system as recited in claim 2 wherein said second data store means comprises a column container for each combination of a table and attribute, each column container comprising a header and column data.

14. A system as recited in claim 13 wherein each header includes an identification of a logical table and one attribute therein.

15. A system as recited in claim 14 wherein the container identification is constituted by the concatenation of a table name and the name of the attribute.

16. A system as recited in claim 14 wherein each header additionally includes a column type value that identifies the structure of the data for that attribute.

17. A system as recited in claim 16 wherein said column type value identifies a code table and said header additionally includes a code table field that identifies the values for each code.

19. A system as recited in claim 14 wherein each header additionally includes a data type field that indicates the nature of the data values in the column container.

20. A system as recited in claim 14 wherein each header additionally includes an attribute stride position vector that points to certain locations in the column data.

18. A system as recited in claim each said column type value identifies a values have variable lengths, said header additionally an attribute stride position vector having pointers to the locations of the column data.

21. A method for generating a data structures for data contained in a logical database with tables in different relationships and a data dictionary, said method comprising the steps of:

A) forming table groups from the tables in the logical database based the data in the data dictionary including, for each table group, a root table and tables related thereto,

B) creating, for each table group, a data store unit for storing the data for the database in a first dimension wherein each of a plurality of memory locations includes all the data from one row of the root table and relevant data from the related tables thereby to allow sequential access to all the data in that root table row and related table row, and

C) creating, for each table and attribute in the table group, another data store unit for storing the database in a plurality of memory locations in a second dimension wherein each memory location includes all the data from an attribute in the database and all the corresponding values thereby to allow sequential access to the data in each attribute memory location.

22. A method for responding to a query to a logical database with root and related tables in different relationships and a data dictionary that identifies each table and a table group for that table in the database, wherein each of the tables includes attributes in columns and data in rows and the database is stored one data store unit in a first dimension wherein each of a plurality of memory locations includes all the data from one row of the root table and relevant data from the related tables and is stored in another data store unit in a plurality of memory locations in a second dimension wherein each memory location includes all the data from one of the attributes in the database and all the corresponding values, said response to the query including, for each table group, the steps of:

A) identifying table groups and the tables in the query,

B) parsing the query by comparing the tables in the table group as provided by the data dictionary to the identified query tables,

C) extracting a list of attributes in the query that are contained in tables that are common to the database and to the query,

D) identifying one of a plurality of processing options in response to the extracted list of attributes, and

E) processing the selected option to obtain the data in an intermediate resultset from the database that satisfies those portions of the query that related to the table group, and

F) combining the intermediate resultsets to obtain a final resultset that satisfies the query.