Hybrid technique for joining tables
First Claim
1. A machine-executed method for joining first and second tables of a relational database system, the system including an index on a join column of the second table, the method comprising the relational database system-performed steps of:
- (a) comparing the rows of the first table with a local predicate;
(b) retrieving rows of the first table which satisfy the local predicate and entering the rows into a sort table;
(c) ordering the rows of the sort table by join column values;
(d) retrieving, from the index, identifiers of rows of the second table having join column values satisfying a join predicate and entering the identifiers in a row index (RID) list;
(e) retrieving, from the second table, rows matching the identifiers of step (d); and
(f) combining the rows of the sort table with the rows retrieved in step (e) to produce composite rows and entering the composite rows in an intermediate result table.
1 Assignment
0 Petitions
Accused Products
Abstract
Results of a relational data base management system are joined in a process requiring, first, existence of an index on the join columns of the inner table, and, second, ordering on the join column of the first table. First, the index on the inner table'"'"'s join column is scanned for rows of the inner table having join column values matching such values of rows in the outer table. This is done in a single pass through the outer table. Next, a temporary work table containing the identifiers of inner table rows having join column values matching those of the outer table is produced by concatenating the row identifiers to their matching outer table rows. Following this, the temporary work table is ordered by the identifiers. Last, the identifier list of inner table rows is used to retrieve the corresponding rows of the inner table. All predicates local to the inner table are applied to the retrieved rows, and those satisfying these local predicates are combined with their matching outer table rows and returned to the user.
131 Citations
5 Claims
-
1. A machine-executed method for joining first and second tables of a relational database system, the system including an index on a join column of the second table, the method comprising the relational database system-performed steps of:
-
(a) comparing the rows of the first table with a local predicate; (b) retrieving rows of the first table which satisfy the local predicate and entering the rows into a sort table; (c) ordering the rows of the sort table by join column values; (d) retrieving, from the index, identifiers of rows of the second table having join column values satisfying a join predicate and entering the identifiers in a row index (RID) list; (e) retrieving, from the second table, rows matching the identifiers of step (d); and (f) combining the rows of the sort table with the rows retrieved in step (e) to produce composite rows and entering the composite rows in an intermediate result table. - View Dependent Claims (2, 3, 4)
-
-
5. A machine-executable method for joining first and second tables in a relational database system, the system providing a prefetch facility and including an index on a join column of the second table, comprising the relational database system-performed steps of:
-
(a) retrieving rows of the first table which satisfy a first local predicate and placing the rows into a sort table in an order determined by join column values; (b) identifying rows in the second table having join column values matching join column values of the rows of the sort table of step (a); (c) obtaining from the index row identifiers of the second table rows identified in step (b), each row identifier including a value which identifies a respective row of the second table; (d) combining the identifiers obtained in step (c) with sort table rows to form intermediate rows and placing the intermediate rows in an intermediate result table, wherein each intermediate row includes a row identifier of a row of the second table, a join column value matching the corresponding join column value of the second table row identified by the row identifier and the corresponding join column value of a row of the sort table, and a value corresponding to the first local predicate; (e) if the row identifiers are not in order, ordering the intermediate rows by row identifier values; (f) retrieving from the second table rows matching the row identifiers of step (e) in the prefetch facility; (g) combining second table rows retrieved in step (f) and satisfying a second local predicate with intermediate rows to form result rows, each result row including a join column value of a second table row and a join column value of an intermediate row including the row identifier of the second table row; and (h) placing the result rows in a result table.
-
Specification