Operations over nested relationships using operators

• US 9,064,000 B1
• Filed: 07/19/2012
• Issued: 06/23/2015
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: FoundationDB, LLC (Apple Inc.)
• Inventors: Herrnstadt, Ori, Orenstein, Jack A.
• Primary Examiner(s): Liao, Jason
• Assistant Examiner(s): Mitiku, Berhanu
• Application Number:
  US13/553,187
• Time in Patent Office: 1,069 Days
• Field of Search: 707/604, 707/713, 707/714, 707/719, 707/737, 707/741, 707/759, 707/770, 707/798, 707/803, 707/748, 707/752, 707/769, 707/809, 707/999.005, 707/999.102, 707/999.103, 707/E17.056, 707/E17.009, 707/E17.037, 707/E17.127, 707/999.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

A set of operators on group-structured data enable creation of efficient execution plans. These operators are of two (2) distinct types. They operate similarly. For each row that matches an input row type, an hkey is obtained. The hkey uniquely identifies a table row within a table group. The hkey is transformed into a modified hkey associated with an output row type. Starting with a row of interest associated with the modified hkey, a table group is probed to identify one or more additional rows. As the additional rows are identified, they are written into an output stream.

Claims

1. A computer program product in a non-transitory computer readable medium, the computer program product comprising machine-readable program instructions executed by a processor to perform a method of storage and retrieval with respect to a set of data stored in tables organized by table groups, wherein a table group comprises all the data from at least one row of a root table together with all related rows of data from one or more other tables related thereto such that rows from multiple distinct tables of the table group are associated as a composite entity, wherein, within the table group, there are one or more root-to-leaf paths that each include, along the root-to-leaf path, the root table, and one or more descendant tables, wherein one of the descendant tables is a leaf table, the method comprising:

in response to receipt of a query, constructing a plan of execution composed of one or more operators, wherein at least one of the operators identifies a table or index to be used as an input row type;

carrying out the plan of execution by;

for each row that matches the input row type, obtain an hkey;

transforming the hkey into a modified hkey associated with an output row type pointing to a different table or index;

starting with a row of interest associated with the modified hkey, probing a table group to read one or more additional rows; and

as each of the one or more additional rows are read, writing into an output stream the one or more additional rows, the output stream being a response to the query.

2. The computer program product as described in claim 1 wherein the row that matches the input row type is one of:

a table index row, a group index row, and a table row.

3. The computer program product as described in claim 1 wherein the modified hkey is created by shortening the hkey into a shortened hkey that points to the row of interest.

4. The computer program product as described in claim 3 further including appending a table identifier to the shortened hkey.

5. The computer program product as described in claim 3 wherein probing the table group returns one or more additional rows that have given output row types matching the output row type associated with the modified hkey.

6. The computer program product as described in claim 4 wherein probing the table group returns one or more additional rows that are descendants of the row that matches the input row type.

7. The computer program product as described in claim 1 wherein the hkey uniquely identifies a table row within the table group.

8. The computer program product as described in claim 1 wherein the query is a non-procedural specification of data to be retrieved.

9. The computer program product as described in claim 1 wherein at least one row of a root table together with all related rows of data from one or more descendant tables related thereto are stored together physically.

10. A method of retrieving data stored in tables organized by table groups, wherein a table group comprises all the data from at least one row of a root table together with all related rows of data from one or more other tables related thereto such that rows from multiple distinct tables of the table group are associated as a composite entity, wherein, within the table group, there are one or more root-to-leaf paths that each include, along the root-to-leaf path, the root table, and one or more descendant tables, wherein one of the descendant tables is a leaf table, the method comprising:

in response to a database query, the database query being a non-procedural specification of data to be retrieved, generating an execution plan composed of one or more operators, wherein at least one of the operators identifies a table or index to be used as an input row type;

carrying out the execution plan by the following sub-steps, using a hardware element;

for each row that matches the input row type, obtaining an hkey;

transforming the hkey into a modified hkey associated with an output row type pointing to a different table or index;

starting with a row of interest associated with the modified hkey, probing a table group to read one or more additional rows; and

as each of the one or more additional rows are read, writing into an output stream the one or more additional rows, the output stream being a response to the query.

11. The method as described in claim 10 wherein the row that matches the input row type is one of:

a table index row, a group index row, and a table row.

12. The method as described in claim 10 wherein the modified hkey is created by shortening the hkey into a shortened hkey that points to the row of interest.

13. The method as described in claim 12 further including appending a table identifier to the shortened hkey.

14. The method as described in claim 12 wherein probing the table group returns one or more additional rows that have given output row types matching the output row type associated with the modified hkey.

15. The method as described in claim 13 wherein probing the table group returns one or more additional rows that are descendants of the row that matches the input row type.

16. The method as described in claim 10 wherein the hkey uniquely identifies a table row within the table group.

17. Apparatus, comprising:

a relational database in which data is stored in tables organized into table groups, wherein a table group comprises all the data from at least one row of a root table together with all related rows of data from one or more other tables related thereto such that rows from multiple distinct tables of the table group are associated as a composite entity, wherein, within the table group, there are one or more root-to-leaf paths that each include, along the root-to-leaf path, the root table, and one or more descendant tables, wherein one of the descendant tables is a leaf table;

computer memory storing program code that is responsive to a database query to generate an execution plan composed of one or more operators, wherein at least one of the operators identifies a table or index to be used as an input row type;

computer memory storing program code to carry out the execution plan by the following sub-steps;

for each row that matches the input row type, obtaining an hkey;

transforming the hkey into a modified hkey associated with an output row type pointing to a different table or index;

starting with a row of interest associated with the modified hkey, probing a table group to read one or more additional rows; and

as the one or more additional rows are read, writing into an output stream the one or more additional rows, the output stream being a response to the query.

18. The apparatus as described in claim 17 wherein the row that matches the input row type is one of:

a table index row, a group index row, and a table row.

19. The apparatus as described in claim 17 wherein probing the table group returns one or more additional rows that have given output row types matching the output row type associated with the modified hkey.

20. The apparatus as described in claim 17 wherein probing the table group returns one or more additional rows that are descendants of the row that matches the input row type.