Method and computer program product for implementing subquery join6134546Abstract A method and computer program product are provided for processing subquery join composites using hash join in a computer system. A hash table is built for a first table to be joined with a second table. A cursor is built for the second table. For each tuple in the second table, the hash table for the first table is probed. If a match is found, then any non-equal join predicate is evaluated. A unique fanout join is processed to return an error if a tuple or row from the second table joins to more than one row in the first table where the result of the basic predicate subquery can only be one row. A distinct fanout join is processed when the tuple or row from the second table joins to a row in the first table, the row is returned, advancing to a next tuple in the second table without checking for any more matches on the first table. Claims What is claimed is: Description FIELD OF THE INVENTION
______________________________________
SELECT TI.EMPNAME, T2.DEPTNAME
FROM EMPLOYEE T1, DEPARTMENT T2
WHERE T1.DEPTNUM=T2.DEPTNUM
AND T1.SALARY>50000 AND T2.DEPTNAME LIKE
`ENG%`
______________________________________
This query is rewritten into new queries as follows where the record selection is applied to the appropriate query which reduces the hash table size.
______________________________________
Q1: SELECT T1.EMPNAME, HASH.sub.-- FUNCTION(T1.DEPTNUM)
FROM EMPOYEE T1
WHERE T1.SALARY>50000
Q2: SELECT T2.DEPTNAME, HASH.sub.-- FUNCTION(T2.DEPTNUM)
FROM DEPARTMENT T2
Where T2.DEPTNAME LIKE `ENG%`
______________________________________
The query is rewritten into the QDT form. The query optimizer 208 is then recursively called in order to optimize each new query individually. This frees the query optimizer 208 from restrictions imposed on join queries and allows for better optimization of each single-file query. The cursors are created for each query. For the primary table, the result rows can be read from the cursor. For the secondary table, a hash table is built and returned when a read is done from its cursor. In accordance with features of the preferred embodiment, the current hash join implementation is extended to support the new joins needed for subquery join composites. To support subquery join composites, the hash join has been modified to support a unique fanout join and a distinct fanout join on the inner join. Typically, hash join out performs nested loop for large sequential files. Hash algorithms can also take advantage of large memories to reduce the amount of I/O required. Also for multi-processor systems, hash algorithms can be easily parallelized. The query optimizer 208 attempts to transform subqueries into joins whenever possible. Query optimizer 208 makes this choice again using the cost-based optimizer; however in almost every case the subquery join implementation has better performance characteristics than the subquery implementation. FIG. 3 illustrates the hash table structure generally designated 300. Hash table structure 300 includes a header 302 pointing to a root page 304 including multiple pointers 306 to buckets 308 for hash values 1-n. Buckets 308 store multiple hash entries 310 and a pointer 312 to a next bucket for respective hash values 1-n. Hash join is the method commonly used for inner equi-joins. The records for each file are hashed to the same hash point using the same hashing function on the join attributes A of R and B of S as hash keys. A single pass through each file hashes the records to the hash file buckets 308. This phase is called the build phase. Each bucket 308 is then examined for records from R and S with matching join attribute values to produce the result of the join operation, called the join phase. There are only certain types of subqueries which can be transformed into joins by the DB2/400 query optimizer 208. These transformations are not described except where specifically applicable to the hash join implementation. The join pairs for the join composite are the correlated predicates. For all subqueries except the basic predicate subquery, the subquery predicate is also a join pair. For a basic predicated subquery, the subquery predicate must be evaluated after the join is complete. Referring to FIG. 4, and TABLE 1 below, exemplary steps performed starting at a block 400 and pseudo code for the hash join algorithm are shown. FIG. 4 illustrates the current inner join hash join algorithm (assuming R.times.S). As indicated at a block 402, a cursor is built for R, Then the hash table is built for S as indicated at a block 404. Then as indicated at block 406, 408, and 410, for each R-tuple in relation R, hash join attribute of R-tuple to S hash-table entry and that hash table entry is probed. While there is a match identified at decision block 412, then the R-tuple and S-tuple is copied to the result buffer. Note, that the entire hash table can always be built and is not restricted to the amount of main memory 104 available on the system. However, performance will be much better if the hash table fits in main memory 104. The hash tables not fitting in main memory results in excess paging as the hash tables are paged into main memory. Another feature of the hash algorithm is that a bit map is returned for the secondary that indicates if there is entry stored at the hash point. This bit map can then be used with other pieces of the query and indicates an interest only in records which have a hash value where the bit is ON. This limits the amount of data that is returned above the MI 202. This hash bit map can also be used in subsequent hash table builds and may reduce the hash table size. FIGS. 5A and 5B illustrate methods for processing a nested loop join and an equivalent hash join supporting a unique fanout join of the preferred embodiment. Pseudo code for the unique fanout join of the preferred embodiment is provided in TABLE 3 below. In the unique fanout join variation, an error is returned if a row from the primary table joins to more than one row in the secondary. This type of join is used to support correlated basic predicate subquery join composites, where the result of the basic predicate subquery can only be one row. In this type of join, the basic predicate evaluation must be done after the determination of a match. This is due to the error checking required for more than one row returned. For a nested loop join, any non-join selection in the subquery must be performed prior to doing the join, this is done by building a select/omit (or sparse) index that has the subquery selection applied to it. FIG. 5A illustrates the algorithm for the nested loop join. An appropriate sparse index is build or located on S as indicated at a block 502. For each R-tuple identified at decision block 504, the index is probed on S as indicated at a block 506. If there is a match identified at decision block 508, then the index is probed on S as indicated at a block 510. If there is a match identified at decision block 512, then an error is returned. If the basic-predicate evaluates true at decision block 516, then the R-tuple is copied to the result buffer as indicated at a block 518. FIG. 5B illustrates an equivalent hash join unique fanout join algorithm. The hash join algorithm of FIG. 4 has been modified to add support for non-equal join predicates since the current hash join only supports equal join predicates and all join predicates must be evaluated prior to evaluating the basic predicate. Also support is provided to issue an error if results are placed in an intermediate table and then a query runs over that table. In FIG. 5B, the algorithm for hash join starts with building the hash table on S applying the selection on S before building the hash table as indicated at a block 530. Then for each R-tuple, the hash table on S is probed as indicated at blocks 532 and 534. If there is a match identified at decision block 536, then any non-equal join predicates are evaluated as indicated at a block 538. If there is a still a match identified at decision block 540, then the hash table on S is probed at block 542. If there is a match identified at decision block 544 then any non-equal join predicates are evaluated at block 546. If there is a match identified at decision block 548, then an error is returned at block 550. If the basic-predicate evaluates true at decision block 554, then the R-tuple is copied to the result buffer as indicated at a block 556. FIGS. 6A and 6B illustrate methods for processing a nested loop join and an equivalent hash join supporting a distinct fanout join. Pseudo code for the distinct fanout join of the preferred embodiment is provided in TABLE 2 below. In the distinct fanout join, if the row from the primary table joins to a row from the secondary, then the row is returned and the join advances to the next row of the primary table without checking if there are any more matches on the secondary. The distinct fanout join is used to support correlated EXISTS, uncorrelated and correlated IN, and quantified uncorrelated and correlated ANY subquery join composites. Since this join type has no error checking the subquery predicate can be evaluated as part of the join. Referring to FIG. 6A, the nested loop algorithm for the distinct fanout join is shown. For each R-tuple identified at decision block 602, the index on S is probed as indicated at a block 604. If there is a match identified at decision block 606, then the R-tuple is copied to the result buffer. This ends the process as indicated at a block 610. Referring to FIG. 6B, an equivalent hash join supporting the distinct fanout join is shown. The hash join implementation for the distinct fanout join supports non-equal join predicates during the evaluation. Since this support was needed for the unique fanout join, support for non-equal join predicates during the evaluation is incorporated into the distinct fanout join algorithm to provide better performance by eliminating the need for a query over an intermediate result to process the non-equal join criteria. In 6B, the equivalent hash join algorithm for distinct fanout join begins with building the hash table on S as indicated at a block 620. For each R-tuple identified at decision block 622, the hash table on S is probed as indicated at a block 624. If there is a match identified at decision block 626, then any non-equal join predicates are evaluated as indicated at a block 628. If there is still a match identified at decision block 630, then the R-tuple is copied to result buffer as indicated at a block 632. Note that the probe and non-equal join evaluation continues until a match is found or no more probes are possible on S. FIGS. 7A, 7B, and 7C illustrate the hash join incorporating both the unique and distinct fanout join. As indicated at a block 702, a hash table is built on S. For each R-tuple the hash table is probed as indicated at decision blocks 704 and 706 and at block 708. If there is match identified at block 710, then any non-equal join predicates are evaluated at block 712. If still a match identified at block 714, then following entry point F in FIG. 7B, if a unique join is required then the hash table is probed again as indicated at blocks 718 and 720. If another match is identified at decision block 724, then any non-equal join predicates are evaluated at block 726. If still a match identified at decision block 728, then an error is sent and the sequential steps end as indicated at a block 732. Else when a match is not identified at decision block 728, then the basic-predicate predicate is evaluated at block 734. If still a match then the R-tuple is copied to the result buffer as indicated at block 738. If distinct or unique fanout join is identified at decision block 742, then the S-hash table bucket is set to end as indicated at a block 744. Processing continues at block 706 in FIG. 7A as indicated at a block 746. FIGS. 8A and 8B illustrate a hash join supporting multiple file join or where three or more files can be joined at one time. The distinct and unique fanout join support is incorporated into the hash join supporting multiple file join. The hash join supporting multiple file join supports when to spin the dial and when to advance to a next dial. As indicated at a block 800, an n-file join is assumed. The hash table is built on S.sub.2 S.sub.n. For each S.sub.1 =tuple, do i=2 to n and while not at end of S.sub.i hash table chain, the hash table on S.sub.i is probed as indicated at blocks 806, 808, 810 and 812. If there is match identified at decision block 814, then any non-equal join predicates are evaluated. If there is not a match identified at decision block 818, then the record is put into the buffer as indicated at a block 820. If there is still a match identified at decision block 818 following entry point J in FIG. 8B, then if unique join is required, the hash table is probed again as indicated at blocks 822 and 824. If another match is identified at decision block 828, then any non-equal join predicates are evaluated as indicated at a block 830. If there is still a match identified at decision block 832, then an error is sent as indicated at a block 834. If not, the record is copied to the buffer at block 836. Else if another match is not identified at block 828, the basic-predicate predicate is evaluated as indicated at a block 840 and the record is copied if the basic predicate evaluates true. In FIG. 8C, if a match is not identified at decision block 842, then the sequential steps return to block 810 in FIG. 8A as indicated at block 844. If there is still a match identified at block 842, then it is determined if n=i as indicated at decision block 846. If not, then the sequential steps return to block 808 in FIG. 8A as indicated at a block 848. Otherwise, the R-tuple is copied to the result buffer as indicated at a block 850. If distinct or unique fanout join is identified at decision block 852, then the Si-hash table bucket is set to the end as indicated at a block 854. Otherwise, the sequential steps return to block 810 in FIG. 8A as indicated at a block 856. For example, the hash join algorithm of the preferred embodiment allows a subquery join composite to be composed and evaluated for a query that is of the following form:
______________________________________
SELECT T1.NAME,T2.DEPTNAME
FROM T1.EMPLOYEE, T2.DEPARTMENT
WHERE T1.DEPTNUM=T2.DEPTNUM
AND T1.PROJNO IN (SELECT PROJNO
FROM PROJECTS P
WHERE T1.PROJNO
=P.PROJNO
AND PRIORITY=`HIGH`)
AND T2.DEPTLOC = (SELECT LOC
FROM LOCATIONS L
WHERE T1.ADDRESS
=L. ADDRESS)
______________________________________
In the above exemplary subquery join composite, the EMPLOYEE and DEPARTMENT table will be joined using the standard hash join algorithm allowing for a full fanout. PROJECTS will then be joined using the distinct fanout join, and LOCATIONS will be joined using the unique fanout join. FIGS. 9A, 9B, 10 and 11 illustrate performance measurements run on AS/400 9406-S20 running V4R2M0 OS/400. This system is a 4-way multiprocessor with 4 G of main memory and 63 G of DASD. The queries were run in the interactive job pool which was allocated 300 M of main memory. The tables used were from the TPCD 1 GB benchmark and the system catalog tables. The queries were run twice and the measurements taken on a the second run, this allowed for as much of the tables as possible to be loaded in to memory. Since this is a multi-processor system, the queries were run once in single processor mode and a second time where the query optimizer could take advantage of all 4 processors using the Symmetric Multiprocessor (SMP) option of DB2/400. Referring to FIG, 9A, there is shown a chart illustrating table sizes for the performance measurements. For the UNIQUE fanout join 4 queries were run as follows:
______________________________________
Q1: SELECT COUNT(*)FROM TPCDIGB.CUSTOMER
WHERE C.sub.-- CUSTKEY IN
(SELECT O.sub.-- CUSTKEY FROM TPCDIGB.ORDERS)
Q2: SELECT N.N.sub.-- NATIONKEY,N.sub.-- NAME,COUNT(*)
FROM TPCDIGB.CUSTOMER C, TPCDIGB.NATION N
WHERE C.sub.-- CUSTKEY IN
(SELECT O.sub.-- CUSTKEY FROM
TPCDIGB.ORDERS)
AND C.C.sub.-- NATIONKEY=N.sub.-- NATIONKEY
GROUP BY N.N.sub.-- NATIONKEY,N.sub.-- NAME
ORDER BY N.sub.-- NAME
Q3: SELECT COUNT(*)FORM TPCDIGB.CUSTOMER A
WHERE C.sub.-- CUSTKEY IN
(SELECT O.sub.-- CUSTKEY FORM TPCDIGB.ORDERS
WHERE O.sub.-- TOTALPRICE<100000)
Q4: SELECT N.N.sub.-- NATIONKEY,N.sub.-- NAME,COUNT(*)
FROM TPCDIGB.CUSTOMER C, TPCDIGB.NATION N
WHERE C.sub.-- CUSTKEY IN
(SELECT O.sub.-- CUSTKEY FROM
TPCDIGB.ORDERS O,
TPCDIGB.LINEITEM L
WHERE O.sub.-- TOTALPRICE<100000 AND
O.O.sub.-- ORDERKEY=L.L.sub.-- ORDERKEY
AND L.L.sub.-- SUPPKEY=9986)
AND C.C.sub.-- NATIONKEY=N.sub.-- NATIONKEY
GROUP BY N.N.sub.-- NATIONKEY,N.sub.-- NAME
ORDER BY N.sub.-- NAME
______________________________________
Referring to FIG. 9B, performance results are shown. For Q1 and Q2, nested loop join is a better implementation choice. The nested loop join method used an existing index on ORDERS. For hash join since there is no additional selection, there are approximately 23 entries in the hash bucket (64K hash points) and there are 100,000 unique values in ORDERS. The time to search the hash chains is more than the time to probe using the index. This same behavior has been seen with current inner hash joins. The hash join implementation was able to apply the subquery selection as to the split query. It was also able to take advantage of hash bit map processing to reduce the number of rows returned for the outer query. For Q4, in the nested loop implementation, the optimizer 208 builds index for orders, it uses existing indexes on customer, nation, and line item. In the hash join case, the query optimizer 208 decides to do nested loop on customer and nation, and hash join for orders and line item. As expected for all four queries, building the hash tables in parallel improves the response (or wall clock) time. Referring to FIG. 10, an example for performance measurements for the unique fanout join is shown. In FIG. 10, SYSINDEXES is a view defined as a 3-way join. Three queries were run as follows.
__________________________________________________________________________
Q5:
SELECT INDEX.sub.-- NAME FROM QSYS2.SYSINDEXES A
WHERE INDEX.sub.-- OWNER < >
(SELECT TABLE.sub.-- OWNER FROM QSYSS2.SYSTABLES B
WHERE A.TABLE.sub.-- NAME=B.TABLE.sub.-- NAME AND
A.TABLE.sub.-- SCHEMA=B.TABLE.sub.-- SCHEMA)
Q6:
SELECT A.COLUMN.sub.-- NAME FROM QSYS2.SYSCOLUMNS A
WHERE A.COLUMN.sub.-- NAME=
(SELECT B.TABLE.sub.-- NAME FROM QSYS2.SYSTABLES B
WHERE A.TABLE.sub.-- NAME=B.TABLE.sub.-- NAME AND
A.TABLE.sub.-- SCHEMA=B.TABLE.sub.-- SCHEMA)
Q7:
SELECT A.COLUMN.sub.-- NAME FROM QSYS2.SYSCOLUMNS A
WHERE A.COLUMN.sub.-- NAME=
(SELECT B.TABLE.sub.-- NAME FROM QSYS2.SYSTABLES B
WHERE A.TABLE.sub.-- NAME=B.TABLE.sub.-- NAME AND
A.TABLE.sub.-- SCHEMA=B.TABLE.sub.-- SCHEMA
AND B.TABLE.sub.-- SCHEMA LIKE `TPCDIGB`)
__________________________________________________________________________
Referring to FIG. 11, performance results are shown. For Q5, in the hash join implementation, SYSINDEXES was implemented using nested loop and then was hash joined to SYSTABLES. Q7 performed better than Q6 for hash join because it was able to use the hash bit map processing to reduce the hash table size and to limit the number of rows returned for SYSCOLUMNS. SMP was not used for these queries because the table sizes were too small. The optimizer 208 decided that the SMP start-up costs was greater than the benefit of running in parallel. Referring to FIGS. 12A and 12B, a detailed example of subquery join composites follows using tables T1 and T2 containing the data. First consider an example for distinct fanout join given an IN subquery as follows. SELECT T1.C1 FROM T1 WHERE T1.C2 IN (SELECT T2.C3 FROM T2) Subquery join composite is: SELECT T1.C1 FROM T1 DISTINCT INNER JOIN T2 ON T1.C1=T2.C3 1. Read the first record from T1 (1,A). 2. The hash table on T2 is probed resulting in a match since there is an `A` in T2.C3. 3. The results are mapped to the output buffer, returning C1 in this case. 4. In a normal inner join, processing would probe the hash table on T2.C3 and determine that there is another match. In this case, since it is a distinct join, we are not interested in additional matches since the IN subquery selection predicated for row (1,A) of T1 has already been satisfied. 5. Read the next record for T1 (2,B). 6. The hash table on T2 is probed, resulting in no matches. The record is not returned to the user. 7. Read the next record for T2 (3,C). 8. The hash table on T2 is probed resulting a match since there is a `C` in T2.C3 9. The results are mapped to the output buffer. 10. Attempt to read the next record from T1, resulting in end-of-file. 11. Return the records to the user. Next consider an example for unique fanout join given a basic predicate subquery as follows.
______________________________________
SELECT T1.C1 FROM T1
WHERE T1.C1 = (SELECT 1
FROM T2
WHERE T1.C2=T2.C3
AND T2. .C3>`A`)
______________________________________
Subquery join composite is: SELECT T1.C1 FROM T1 UNIQUE INNER JOIN T2 ON T1.C1=T2.C2 and T2.C3>`A` WHERE T1.C1=1 1. Read the first record from T1 (1,A). 2. The hash table on T2 is probed resulting in no matches, since C3=`A` was eliminated by the selection. 3. Read the next record from T1 (2,B). 4. The hash table on T2 is probed resulting in no matches. 5. Read the next record from T1 (3,C). 6. The hash table on T2 is probed resulting in a match. The hash table is probed again, looking for another match; however there is no match. 7. The results are mapped to the output buffer. 8. Attempt to read the next record from T1, result in end-of-file. 9. Return the record to the user Consider an error case for unique fanout join given a basic predicate subquery as follows.
______________________________________
SELECT T1.C1 FROM T1
WHERE T1.C1 =(SELECT 1
FROM T2
WHERE T1.C2=T2.C2)
______________________________________
Subquery join composite is: SELECT T1.C1 FROM T1 UNIQUE INNER JOIN T2 ON T1.C1=T2.C2 WHERE T1.C1=1 1. Read the first record from T1 (1,A). 2. The hash table on T2 is probed resulting in a match since there is an `A` in T2.C3. 3. Since there was a match, the hash table is again probed and another match is found, resulting in an error, since the basic predicate subquery can only return 1 result. Referring now to FIG. 13, an article of manufacture or a computer program product 1300 of the invention is illustrated. The computer program product 1300 includes a recording medium 1302, such as, a floppy disk, a high capacity read only memory in the form of an optically read compact disk or CD-ROM, a tape, a transmission type media such as a digital or analog communications link, or a similar computer program product. Recording medium 1302 stores program means 1304, 1306, 1308, 1310 on the medium 1302 for carrying out the subquery join composite methods using hash join of the preferred embodiment in the system 100 of FIGS. 1 and 2. A sequence of program instructions or a logical assembly of one or more interrelated modules defined by the recorded program means 1304, 1306, 1308, 1310, direct the computer system 100 for implementing subquery join composite methods using hash join of the preferred embodiment.
TABLE 1
______________________________________
Hash join algorithm:
______________________________________
Assume tables R and S are being joined, where S is
the primary dial.
Build a hash table for R
Read a record from S
DO UNTIL no more records in S
Probe hash table of R using join field from record of
S
IF match found then
DO UNTIL no more matches found
build output buffer to return to user
probe next hash point in R looking for
additional matches
END do until
ENDIF
Read next record from S
END do until
IF non-egual join predicates
Evaluate non-egual join predicates as selection
prior to returning records to user and
removing any records that do not meet the
selection criteria.
ENDIF
______________________________________
While the present invention has been described with reference to the details of the embodiments of the invention shown in the drawing, these details are not intended to limit the scope of the invention as claimed in the appended claims.
|
Same subclass Same class Consider this |
||||||||||