Method and apparatus for performing a depth-first join in a database
View Patent ↗In a database, inner joins are performed in a depth-first manner. Depth-first joins differ from breadth-first joins in that rows are examined a page at a time during execution from every table that is participating in the query. Thus, the depth-first join is a constant-space operation with respect to the size of the data set, with the storage required approximately equal to the sum of the sizes of a page from each table.
1. An apparatus for executing a database query that comprises an inner join and returns rows with fields F, subject to a set of restrictions R, said apparatus comprising:
means for instantiating exactly one Query Execution Node (QEN) associated with each table participating in said query;
means for connecting, with a computer, the QENs to each other in a chain;
for each QEN in said chain,
means for requesting rows from the previous QEN in said chain, if present;
means for performing a single-table query against the associated table using said requested rows, if present; and
means for passing the resulting rows from said single-table query to the next QEN in said chain; and
means for outputting, with said computer, a solution to said query that comprises the rows that are returned by the last QEN in said chain;
wherein a single-table query against a table t comprises three arguments I, R q , and F p , where:
I is a set of input rows comprising said requested rows, if present;
R q is the set of restrictions within R that operate on the fields indicated by F I ∪F t , where F I and F t are the sets of field names from I and t, respectively; and
F p is a set of field names from F I ∪F t indicating the columns onto which results should be projected to yield said resulting rows;
wherein in response to a request for said requested rows, the i th QEN in said chain performs a single-table query against the associated table t i with arguments I, R q and F p equal to I i−1 , R i , and F i respectively, where
R I is the set of restrictions containing all restrictions that can be applied using only fields from t I , and
F I is the set of fields that either exist in F or in one of the remaining unused restrictions in R; and
wherein in response to a request for a said requested rows, the ith QEN in said chain performs a single-table query against the associated table t i with arguments I, R q , and F p equal to I i−1 , R i , and F i , respectively, where
I i−1 is said requested rows received from said previous QEN in said chain,
R i is the set of restrictions that have not been associated with a previous QEN in said chain and can be applied using only fields from table t i and F i−1 , and
F i is the set of fields that either exist in F or in one of the remaining unused restrictions in R.
2. The apparatus of claim 1 , said single-table query additionally comprising two arguments c and S, where:
c is a Boolean value indicating whether duplicate rows should be culled from said single-table query results; and
S is an optional sequence of field names specifying the relative significance of the fields indicated by F p in determining a lexicographical ordering of results of said single-table query.
3. The apparatus of claim 1 , further comprising:
paging parameters for specifying which portion of a single-table query result to retrieve, including a marker indicating a beginning of a page and a page size indicating a number of rows to return.
4. The apparatus of claim 1 further comprising:
means for constructing said QEN chain based upon a definition of each QEN's inputs and outputs and an association of every restriction supplied by said query.
5. The apparatus of claim 4 , said means for constructing said QEN chain operating upon a sequence of said participating tables, said means for constructing said QEN chain proceeding iteratively from a first table of said participating tables to a last table of said participating tables.
6. The apparatus of claim 5 , wherein upon completion of said QEN chain, all restrictions supplied by said inner join are associated with a QEN.
7. The apparatus of claim 1 , further comprising:
means for culling duplicates across single-table queries.
8. The apparatus of claim 7 , wherein said means for culling manipulates a sort order of rows to make duplicates appear adjacent to each other in a sequence of all rows across all pages, wherein identical rows are collapsed onto one.
9. The apparatus of claim 8 , said means for culling defining a set of unperturbed fields, wherein all duplicates of a row are within an unperturbed group of rows, potentially returned by separate single-table queries, with unperturbed field values equaling those of said row, wherein a QEN collects all rows within said unperturbed group, sorts them, and removes duplicates.
10. The apparatus of claim 9 , wherein said means for culling examines all rows in said unperturbed group before any row within said unperturbed group can be passed to a next QEN in said QEN chain.
11. The apparatus of claim 10 , further comprising:
means for explicitly setting a QEN's position in its output stream to allow a QEN to seek backwards and output rows that it has already returned.
12. A computer-implemented method for executing a database query that comprises an inner join and returns rows with fields F, subject to a set of restrictions R, said computer-implemented method comprising the steps of:
instantiating exactly one Query Execution Node (QEN) associated with each table participating in said query;
connecting, with a computer, the QENs to each other in a chain;
for each QEN in said chain,
requesting rows from the previous QEN in said chain, if present;
performing a single-table query against the associated table using said requested rows, if present; and
passing the resulting rows from said single-table query to the next QEN in said chain; and
outputting, with said computer, a solution to said query that comprises the rows that are returned by the last QEN in said chain;
wherein a single-table query against a table t comprises three arguments I, R q , and F p , where:
I is a set of input rows comprising said requested rows, if present;
R q is the set of restrictions within R that operate on the fields indicated by F I ∪F t ,where F I and F t are the sets of field names from I and t, respectively; and
F p is a set of field names from F I ∪F t indicating the columns onto which results should be projected to yield said resulting rows;
wherein in response to a request for said requested rows, the i th QEN in said chain performs a single-table query against the associated table t i with arguments I, R q and F p equal to I i−1 , R i , and F i respectively, where
R I is the set of restrictions containing all restrictions that can be applied using only fields from t I , and
F I is the set of fields that either exist in F or in one of the remaining unused restrictions in R; and
wherein in response to a request for a said requested rows, the ith QEN in said chain performs a single-table query against the associated table t i with arguments I, R q , and F p equal to I i−1 , R i , and F i , respectively, where
I i−1 is said requested rows received from said previous QEN in said chain,
R i is the set of restrictions that have not been associated with a previous QEN in said chain and can be applied using only fields from table t i , and F i−1 , and
F i is the set of fields that either exist in F or in one of the remaining unused restrictions in R.
13. The method of claim 12 , said single-table query additionally comprising two arguments c and S, where:
c is a boolean value that indicates whether duplicate rows should be culled from said single-table query result; and
S is an optional sequence of field names specifying the relative significance of the fields indicated by F p in determining a lexicographical ordering of results of said single-table query.
14. The method of claim 12 , further comprising the step of:
providing paging parameters for specifying which portion of a single-table query result to retrieve, including a marker indicating a beginning of a page and a page size indicating a number of rows to return.
15. The method of claim 12 , further comprising the step of:
constructing said QEN chain based upon a definition of each QEN's inputs and outputs and an association of every restriction supplied by said query.
16. The method of claim 15 , said constructing step comprising the step of:
operating upon a sequence of said participating tables, said constructing step proceeding iteratively from a first table of said participating tables to a last table of said participating tables.
17. The method of claim 16 , wherein upon completion of said QEN chain, all restrictions supplied by said query are associated with a QEN.
18. The method of claim 12 , further comprising the step of:
culling duplicates across single-table queries.
19. The method of claim 18 , wherein said culling step further comprises the step of:
manipulating a sort order of rows to make duplicates appear adjacent to each other in a sequence of all rows across all pages, wherein identical rows are collapsed onto one.
20. The method of claim 19 , said culling step further comprises the step of:
defining a set of unperturbed fields, wherein all duplicates of a row are within an unperturbed group of rows, potentially returned by separate single-table queries, with unperturbed field values equaling those of said row, wherein a QEN collects all rows within said unperturbed group, sorts them, and removes duplicates.
21. The method of claim 20 , wherein said culling step further comprises the step of:
examining all rows in said unperturbed group before any row within said unperturbed group can be passed to a next QEN in said QEN chain.
22. The method of claim 21 , further comprising the step of:
explicitly setting a QEN's position in its output stream to allow a QEN to seek backwards and output rows that it has already returned.