Multiple dimensioned database architecture

• US 8,150,850 B2
• Filed: 01/07/2008
• Issued: 04/03/2012
• Est. Priority Date: 01/07/2008
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Akiban Technologies, Inc. (Apple Inc.)
• Inventors: Herrnstadt, Ori
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US11/970,251
• Publication Number:
  US 20090193006A1
• Time in Patent Office: 1,548 Days
• Field of Search: 707/769, 707/954, 707/737, 707/741, 707/809, 707/600, 707/610
• 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 database management apparatus, comprising:

A) a first data store that stores, in a plurality of first memory units, a copy of the data of a logical database model according to a first physical layout, the logical database model comprising at least one table group, wherein each table group includes one root table and at least one other table distinct from the root table and related thereto, each table in the table group being characterized as having columns of attributes and rows of data, wherein each of the plurality of first memory units includes, as a first composite entity, all the data from at least one row of a root table and all related rows of data from the at least one other table related thereto such that rows from multiple distinct tables of the table group are inherently linked and stored in the first memory unit as the first composite entity, the first physical layout providing sequential access, as the first composite entity, to all the data in that root table row and the related data from the at least one other table in response to a query of a first type, the sequential access taking place without individual random accesses to the root table and the at least one other table related thereto, thereby eliminating a need to process a join operation each time such relationship is accessed, and

B) a second data store that stores, in a plurality of second memory units, a redundant copy of the data of the logical database model according to a second physical layout wherein each second memory unit includes all data from at least one of the attributes and all the corresponding values of that attribute, the second physical layout providing sequential access, as a set of columns, to the data in each attribute in response to a query of a second type; and

C) a data dictionary populated with information from the logical database model that identifies relationships among the tables in different ones of the table groups.

2. The database management apparatus as recited in claim 1 wherein each of the memory units in the first and second data store comprises contiguous memory locations.

3. The database management apparatus 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.

4. The database management apparatus as recited in claim 3 wherein the cluster row identification includes an identifier for the cluster and the corresponding table in the table group.

5. The database management apparatus as recited in claim 4 wherein each table includes a unique identifier for each row therein and each 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.

6. The database management apparatus as recited in claim 4 wherein each header additionally identifies the table in the logical database model associated with a cluster row.

7. The database management apparatus as recited in claim 4 wherein each header additionally includes an attribute identifier for identifying each attribute in a cluster row and whether the attribute is present in that cluster row.

8. The database management apparatus as recited in claim 4 wherein each header additionally includes a pointer to attribute values in the body of the cluster row.

9. The database management apparatus as recited in claim 4 wherein the information in each cluster row is stored in contiguous memory locations.

10. The database management apparatus as recited in claim 9 wherein the information in each cluster is stored in contiguous memory locations.

11. The database management apparatus as recited in claim 10 wherein the information in each container is stored in contiguous memory locations.

12. The database management apparatus as recited in claim 2 wherein second data store comprises a column container for each combination of a table and attribute, each column container comprising a header and column data.

13. The database management apparatus as recited in claim 12 wherein each header includes an identification of a logical table and one attribute therein.

14. The database management apparatus as recited in claim 13 wherein the container identification is a concatenation of a table name and the name of the attribute.

15. The database management apparatus as recited in claim 13 wherein each header additionally includes a column type value that identifies the structure of the data for that attribute.

16. The database management apparatus as recited in claim 15 wherein the column type value identifies a code table and the header additionally includes a code table field that identifies the values for each code.

17. The database management apparatus as recited in claim 13 wherein the column type value identifies a value having variable length, the header additionally including an attribute stride position vector having pointers to the locations of the column data.

18. The database management apparatus as recited in claim 13 wherein each header additionally includes a data type field that indicates a characteristic of the data values in the column container.

19. The database management apparatus as recited in claim 13 wherein each header additionally includes an attribute stride position vector that points to certain locations in the column data.

20. A method for generating a data structures for data contained in a logical database with tables in different relationships and a data dictionary, method comprising:

A) forming table groups from the tables in the logical database based on the data in the data dictionary including, for each table group, a root table and one or more tables related thereto, at least one table in the table group having a column structure that differs from the column structure of another table in the table group, the data dictionary populated with information from the logical database that identifies relationships among the tables in different ones of the table groups,

B) creating, for each table group, a data store unit for storing the data for the logical database in a first physical layout wherein each of a plurality of first memory units includes, as a composite entity, all the data from one row of the root table and relevant rows of data from the related tables such that rows from multiple distinct tables of the table group are stored in the first memory unit as the composite entity, the composite entity being adapted for sequential access without individual random accesses to the root table and the relevant rows of data from the related tables or any associated join operation, and

C) creating, for each table and attribute in the table group, another data store unit for storing a redundant copy of the data of the logical database in a plurality of second memory units in a second physical layout wherein each second memory unit includes all the data from an attribute in the database and all the corresponding values of that attribute.

21. 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, the data dictionary populated with information from the logical database that identifies relationships among the tables in different ones of the table groups, wherein each of the tables includes attributes in columns and data in rows, comprising:

storing a copy of the data in a plurality of first memory units according to a first physical layout wherein each first memory unit includes, as a composite entity, all the data from at least one row of a root table together with all related rows of data from the one or more other tables related thereto such that rows from multiple distinct tables of the table group are stored in the first memory unit as the composite entity, the composite entity being adapted for sequential access without individual random accesses to the root table and the relevant rows of data from the related tables or any associated join operation;

storing a redundant copy of the data in a plurality of second memory units according to a second physical layout wherein each second memory unit includes all the data from at least one of the attributes together with all the corresponding values of that attribute; and

responding to the query, for each table group, according to the following sub-steps;

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.

22. A computer program product comprising tangible machine-readable program instructions executable by a processor to perform a method of managing data grouped according to a logical database model, the logical database model associated with a data dictionary and comprising at least one table group, each table group including one root table and one or more other tables distinct from the root table and related thereto, each table in the table group having columns of attributes and rows of data, at least one table in the table group having a column structure that differs from the column structure of another table in the table group, the data dictionary populated with information from the logical database model that identifies relationships among the tables in different ones of the table groups, the method comprising:

storing a copy of the data in a plurality of first memory units according to a first physical layout wherein each first memory unit includes, as a composite entity, all the data from at least one row of a root table together with all related rows of data from the one or more other tables related thereto such that rows from multiple distinct tables of the table group are stored in the first memory unit as the composite entity; and

responsive to a query of a first type, sequentially accessing and providing, as the composite entity, all the data in a row of the root table together with all related data from the one or more other tables related thereto;

the sequential accessing and providing step taking place in response to the query without individual random accesses to the root table and the one or more other tables or any associated join operation;

storing a redundant copy of the data in a plurality of second memory units according to a second physical layout wherein each second memory unit includes all the data from at least one of the attributes together with all the corresponding values of that attribute; and

responsive to a query of a second type, sequentially accessing and providing, as a set of columns the data in each attribute.