Patent ID: 12197439

DETAILED DESCRIPTION

In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

General Overview

As discussed above, existing approaches have limitations for optimizing execution plans of certain complex database queries that are common in many data processing workloads. For example, database queries with disjunctive (“or”) subqueries and filter predicates in disjunction are generally not optimizable using existing approaches.

Accordingly, a new type of table join operation, outer semi join (OSJ), is provided. OSJ combines the semantics of both left outer-join (also referred to as left-join) and semi-join. The concept of an anti join marker (AJM) is also introduced, which specifies whether a matching row was found between joined tables for each result row in an OSJ operation or not found. The OSJ operation supports unnesting of a class of disjunctive ANY, ALL, EXISTS, and NOT EXISTS subqueries for execution plan optimization. For unnesting, OSJ avoids the need of using a distinct operator on the right table and also supports using inequality (e.g., >, >=, <, <=) in connecting or correlating conditions of subqueries, rather than being limited to equality only.

Example disjunctive subqueries that can be processed using OSJ include: (a) a subquery in disjunction with a filter predicate; (b) a first subquery in disjunction with a second subquery; (c) a first subquery in disjunction with a second subquery in disjunction with a filter predicate; (d) any number of disjunctive subqueries in disjunction with any number of filter predicates, and (e) disjunctive correlated predicates in one or more subqueries (as shown in external query942(Q8) ofFIG.9).

By supporting unnesting for database queries with subqueries and filter predicates in disjunction, an optimizer layer of a DBMS can provide highly optimized execution plans for a broader range of database queries supporting various data processing workloads. Accordingly, when the execution plans are later executed by the execution layer of the DBMS, the database queries can benefit from reduced execution time, optimized resource usage, smaller memory footprint, lower power consumption, and other performance benefits.

Network Arrangement Architecture

FIG.1is a block diagram that depicts an example network arrangement100for a database management system110, according to one or more embodiments. Network arrangement100includes a client device140and a database server computing device120communicatively coupled via a network150. Network150may be implemented with any type of medium and/or mechanism that facilitates the exchange of information between client device140and server device120. Example network arrangement200may include other devices, including client devices, server devices, storage devices, and display devices, according to one or more embodiments.

Client device140may be implemented by any type of computing device that is communicatively connected to network150. In network arrangement100, client device140is configured with a database client, which may be implemented in any number of ways, including as a stand-alone application running on client device140, or as a plugin to a browser running at client device140, etc. Client device140may submit one or more database queries, including external query142, to database management system110. As shown inFIG.1, external query142may include one or more disjunctive subqueries, or disjunctive subquery144A, disjunctive subquery144B, and disjunctive subquery144C. Client device140may be configured with other mechanisms, processes and functionalities, depending upon a particular implementation.

In network arrangement100, database server computing device120is configured with a database server instance122. Database server computing device120is implemented by any type of computing device that is capable of communicating with client device140over network150and also capable of running database server instance122.

Database server instance122on database server computing device120maintains access to and manages data in database132(i.e., on storage130). According to one or more embodiments, access to a given database comprises access to (a) a set of disk drives storing data for the database, and (b) data blocks stored thereon. Database132may reside in any type of storage130, including volatile and non-volatile storage, e.g., random access memory (RAM), one or more hard disks, main memory, etc.

Database server instance122includes optimizer layer128and execution layer129. Optimizer layer128may generate and optimize one or more execution plans, including execution plan124, to process external query142received from client device140. Execution layer129may execute execution plan124to process external query142using database132. The result rows from execution layer129may then be provided back to client device140.

Any of the functionality attributed to database server instance122or database management system110herein may be performed by any other entity, which may or may not be depicted in network arrangement100, according to one or more embodiments. Server device120may be configured with other mechanisms, processes and functionalities, depending upon a particular implementation.

In an embodiment, each of the processes and/or functionality described in connection with database server instance122, database management system110, and/or database132are performed automatically and may be implemented using one or more computer programs, other software elements, and/or digital logic in any of a general-purpose computer or a special-purpose computer, while performing data retrieval, transformation, and storage operations that involve interacting with and transforming the physical state of memory of the computer.

Example Table Join Operations

FIG.2Adepicts example database tables T1 and T2. Database tables T1 and T2 may be stored in database132. As shown inFIG.2A, table T1 includes data columns A1, B1, and C1, with five rows or records of data, and table T2 includes data columns A2, B2, and C2, with five rows or records of data. Tables T1 and T2 ofFIG.2Aare reproduced below:

TABLE T1A1B1C115327439114812562

TABLE T2A2B2C2132276241457769
Reproduction ofFIG.2A.

FIG.2Bdepicts example internal queries225A-225D shown in a structured query language (SQL) like syntax for use within an execution plan. Internal queries225A-225D may correspond to internal query125fromFIG.1. For illustrative purposes, the SQL-like syntax allows for explicit definition of table joins that may be reserved for internal DBMS use, such as semi-join, anti-join, and outer semi join (OSJ). Accordingly, the SQL-like syntax may not conform to a formal SQL definition such as ANSI SQL.

FIG.2Cdepicts result226A, result226B, result226C, and result226D from processing the respective internal queries225A-225D ofFIG.2Bwith tables T1 and T2 fromFIG.2A. The results226A-226D will be described in conjunction withFIG.2Bbelow.

Internal query225A ofFIG.2Billustrates an example query using left outer join, wherein the left table or T1 drives the table join operation. All rows of table T1 are selected—those that do not match to T2 (the left side of the Venn diagram) and those that do match to T2 (the middle of the Venn diagram). Duplicate row matches are permitted, as indicated by the cross shading. For example, referring to the second and third rows in result226A ofFIG.2C, it is observed that T1.A1=T2.A2 is matched twice for the second and third rows of table T2. Internal query225A and result226A are reproduced below:

SELECT T1.a1, T1.b1, T2.c2FROM T1 LEFT OUTER JOIN T2 on T1. a1 = T2.a2;A1B1C215227627139NULL48756NULL
Reproduction of Portions ofFIGS.2B and2C.

Internal query225B ofFIG.2Billustrates an example query using semi-join, wherein the left table or T1 drives the table join operation. Only those rows of T1 are selected that match with any row of T2 (the middle of the Venn diagram). However, unlike an inner join, a semi-join only provides the first row that is matched, as indicated by the horizontal shading. For example, referring to result226B inFIG.2C, for the matching of T1.A1=T2.A2=2, it is observed that only the second row in T2 is matched to the second row in T1 to provide the second row in result226B. Any further potential matching rows, such as the third row in T2, are not matched, and therefore do not contribute any rows to the results. Accordingly, rows from T1 are not duplicated in the results of the semi-join operation. Internal query225B and result226B are reproduced below:

SELECT T1.a1, T1.b1FROM T1 semi join T2 on T1.a1 = T2.a2;A1B1152748
Reproduction of Portions ofFIGS.2B and2C.

Internal query225C ofFIG.2Billustrates an example query using anti-join, wherein the left table or T1 drives the table join operation. Only those rows of T1 are selected that do not match with any row of T2 (the left side of the Venn diagram). Rows from T1 are not duplicated in the results of an anti join operation. Internal query225C and result226C are reproduced below:

SELECT T1.a1, T1.b1FROM T1 anti join T2 on T1.a1 = T2.a2;A1B15639
Reproduction of Portions ofFIGS.2B and2C.

Internal query225D ofFIG.2Billustrates an example query using the new table join operation, or outer semi join (OSJ), wherein the left table or T1 drives the table join operation. As with left outer join, all rows of table T1 are selected—those that do not match to T2 (the left side of the Venn diagram) and those that do match to T2 (the middle of the Venn diagram). However, the rows that match to T2 are limited to the first matching row, as with semi-join. Accordingly, rows from T1 are not duplicated in the results of the outer-semi-join operation. Thus, it is observed that outer semi join combines the semantics of both left outer-join and semi-join. Internal query225D and result226D are reproduced below:

SELECT T1.a1, T1.b1, NVL2(T2.rowid, 0, 1) AJMFROM T1 OUTER SEMI JOIN T2 on T1.a1 = T2.a2;A1B1AJM150270391480561
Reproduction of Portions ofFIGS.2B and2C.

Further, database management system110may support the provision of an anti join marker (AJM) that defines, for each result row in an OSJ operation, whether the result row matches or not. For example,FIG.6provides one possible mapping of AJM values, wherein an AJM value of 0 indicates a matching row was found (center of the Venn diagram, or semi-join semantics), an AJM value of 1 indicates a matching row was not found (left of the Venn diagram, or anti join semantics), and an AJM value of 2 indicates that row evaluation was not performed. These AJM values may be assigned as part of a pre-filter operation, as described below under the heading “AUGMENTED ANTI JOIN MARKER”. This is only one example mapping; other values may be assigned. As shown in internal query225D, the expression “NVL2(T2.rowid, 0, 1) AJM” is another way to derive the AJM value: AJM is set to 0 when T2.rowid is not null (i.e. a valid matching row was found), and AJM is set to 1 when T2.rowid is null (i.e. matching row was not found).

Referring to result226D, it is observed that result226D is effectively the combination of result226B (semi-join) and result226C (anti-join), with the AJM field indicating whether the result was from semi-join (AJM=0) or anti join (AJM=1). Thus, an OSJ operation can also be described as a combination of semi-join and anti join semantics.

Example Query Unnesting: Single Disjunction

FIG.3Adepicts external query342(Q1) with disjunctive subquery344A. External query342may correspond to external query142, disjunctive subquery344A may correspond to disjunctive subquery144A, internal query325may correspond to internal query125, and execution plan324may correspond to execution plan124. External query342is reproduced below (note that tables “T_5K” and “G_4K” are assigned respective names “T1” and “T2”):

Query Q1.SELECT T1.hundred, T1.thousandFROM T_5K T1WHERE T1.unique3 > 19 and(T1.hundred IN(SELECT hundredFROM G_4K T2WHERE hundred > 5)OR T1.ten = 1 OR T1.ten = 2);

As shown in external query342, disjunctive subquery344A, or “IN (SELECT hundred FROM G_4K T2 WHERE hundred >5)” is in disjunction (“OR”) with the predicate “T1.ten IN (1, 2)”, or disjunctive filter predicates. By using outer semi join, disjunctive subquery344A can be unnested, as shown in the corresponding internal query325(Q2), reproduced below.

Query Q2.SELECT T1.hundred, T1.thousandFROM T_5K T1, G_4K T2WHERE T1.unique3 > 19 andT2.hundred > 5 andT1.hundred OSJ= T2.hundred and(T1.ten = 1 OR T1.ten = 2 ORT2.AJM = 0);

FIG.3Bdepicts internal query325(Q2), which corresponds to external query342(Q1) ofFIG.3Awith disjunctive subquery344A unnested using outer semi-join. The subquery is unnested by including the “G_4K T2” table in the FROM clause, including “T2.hundred>5” and “T1.hundred OSJ=T2.hundred” as additional conjunctions (“AND”) in the WHERE clause, wherein “OSJ=” indicates matching fields by equality using outer semi join, and adding “T2.AJM=0” as an additional disjunction (“OR”) in the “T1.ten IN (1, 2)” clause, or the disjunctive filter predicates. T2.AJM is matched to “0” since the associated statement is “T1.hundred IN”, indicating a semi-join rather than an anti-join.

FIG.3Cdepicts a simple execution plan324determined for internal query325(Q2) ofFIG.3B. Execution plan324, reproduced below, illustrates one possible execution plan for internal query325(Q2). In the example shown, the outer semi join (performed using a hash join method) is performed first at line 2 (Id=2), and then the disjunctive filter predicates are evaluated at line 1 (Id=1). Note that in this example, the hash join is performed for all rows, but in an optimized execution of outer semi-join, a pre-filter may be used to avoid row evaluation in outer semi-join when any of the disjunctive filter predicates are satisfied, as described further below under the heading “AUGMENTED ANTI JOIN MARKER”.

CostIdOperationNameRows(% CPU)0SELECT STATEMENT184527(12)* 1FILTER* 2HASH JOIN OUTERSEMI184527(12)* 3TABLE ACCESS FULLT_5K249024(9)* 4INDEX RANGE SCANG_4K_HUNDRED3672(0)Predicate Information (identified by operation id):1 - filter(“T2”.“AJM” = 0 OR “T1”.“TEN” = 1 OR “T1”.“TEN” = 2)2 - access(“T1”.“HUNDRED” = “T2”.“HUNDRED”)3 - filter(“T1”.“UNIQUE3” > 19)4 - access (“T2”.“HUNDRED” > 5)
Reproduction ofFIG.3C.
Example Query Unnesting: Multiple Disjunction

FIG.4Adepicts external query442(Q3) with disjunctive subquery444A and disjunctive subquery444B. External query442, reproduced below, may correspond to external query142, disjunctive subquery444A may correspond to disjunctive subquery444A, disjunctive subquery444B may correspond to disjunctive subquery444B, and internal query425may correspond to internal query125.

Query Q3.SELECT T1.x, T1.yFROM T1, T5WHERE T1.k = T5.k and T1.z > 19 and(NOT EXISTS (SELECT T2.pFROM T2WHERE T1.p = T2.p and T2.d > 5)OR T5.q > ANY (SELECT T3.qFROM T3WHERE T3.f = 7)OR T1.h = 1 OR T5.g = 99);

As shown in external query442(Q3), disjunctive subquery444A, or “NOT EXISTS (SELECT T2.p FROM T2 WHERE T1.p=T2.p and T2.d>5)” is in disjunction (“OR”) with disjunctive subquery444B, or “ANY (SELECT T3.q FROM T3 WHERE T3.f=7)”; both subqueries are further in disjunction with the disjunctive filter predicates, “T1.h=1 OR T5.g=99”. External query442(Q3) may be unnested into internal query425(Q4), reproduced below:

Query Q4.SELECT T1.x, T1.yFROM T1, T2, T3, T5WHERE T1.z > 19 and T1.k = T5.k andT1.p OSJ= T2.p and T2.d > 5 andT5.q OSJ> T3.q and T3.f = 7 and(T1.h = 1 OR T5.g = 99 OR T2.AJM = 1 OR T3.AJM = 0);

FIG.4Bdepicts internal query425(Q4), which corresponds to external query442(Q3) ofFIG.4Awith disjunctive subqueries444A and444B unnested using outer semi-join. Disjunctive subquery444A is unnested by including the “T2” table in the FROM clause, including “T1.p OSJ=T2.p and T2.d>5” as an additional conjunction (“AND”) in the WHERE clause, wherein “OSJ=” indicates matching fields by equality using outer semi join, and adding “T2.AJM=1” as an additional disjunction (“OR”) in the disjunctive filter predicates “T1.h=1 OR T5.g=99”. T2.AJM is equal to “1” since the associated statement is “NOT EXISTS”, indicating an anti-join rather than a semi-join.

Similarly, disjunctive subquery444B is unnested by including the “T3” table in the FROM clause, including “T5.q OSJ>T3.q and T3.f=7” as an additional conjunction (“AND”) in the WHERE clause, wherein “OSJ>” indicates greater than (rather than equal to) using outer semi join, and adding “T3.AJM=0” as an additional disjunction (“OR”) in the disjunctive filter predicates, “T1.h=1 OR T5.g=99” clause. T3.AJM is equal to “0” since the associated statement is “ANY”, indicating a semi-join rather than an anti-join.

In general, the unnesting of IN, ANY, and EXISTS subqueries result in semi-join (i.e., outer semi join with AJM equal to 0) and the unnesting of NOT IN, ALL, and NOT EXISTS subqueries result in anti join (i.e., outer semi join with AJM equal to 1).

Thus, as demonstrated above in conjunction withFIGS.3A-3BandFIGS.4A-4B, any number of disjunctive subqueries in a single database query can be unnested using outer semi-join.

Partial Join Order

FIG.5Adepicts an example external query542, reproduced below as Q5, with inner and left outer joins. For example, the joins “T1.z=T3.z (+)” and “T2.w=T3.w (+)” are left outer joins, while the join “T1.x=T2.x” is an inner join. When a table participates in an asymmetric join, such as left outer join, anti-join, semi-join, outer semi-join etc., the optimizer layer128may enforce a partial join order such that the outer-/semi-/anti-joined table(s) (e.g., T3) must succeed the table(s) (e.g., T1 and T2) it is joined to in the left-to-right join order.

Query Q5.SELECT *FROM T1, T2, T3WHERE T1.x = T2.x and T1.z = T3.z (+) and T2.w = T3.w (+);

For external query542(Q5), enforcing the partial join order means that T3 (the left outer joined table) comes after T1 and T2 in the join order. Thus, as shown in join order560A ofFIG.5B, the first joins include tables T1 and T2, and the second join includes table T3. Thus, the valid left-to-right join orders are 1/2 (T1, T2, T3) and 2/2 (T2, T1, T3). Optimizer layer128may select a specific join order option based on efficiency (e.g., by choosing the join order option with the lowest projected cost). Join order560A is reproduced below:Tables in the first join (Option 1): {T1, T2}Tables in the second join (Option 1): {T1, T2, T3}Join order option 1/2: (T1, T2, T3)Join order option 2/2: (T2, T1, T3)
Reproduction ofFIG.5B.

For outer semi join, in enforcing join order there is an additional requirement that in valid join orders all tables referenced in disjunctive filter predicates must precede all the outer-semi-joined tables. This allows the evaluation of disjunctive filter predicates before any outer semi-join takes place.

For internal query325(Q2), there is only a single outer semi join with T2 (“T1.hundred OSJ=T2.hundred”). Since outer semi join shares the semantics of left outer join, it is considered an asymmetric join. Thus, as shown in join order560B ofFIG.5C, there is only one possible join order option 1/1 (T1, T2). Join order560B is reproduced below:Tables in the first join (Option 1): {T1, T2}Join order option 1/1: (T1, T2)
Reproduction ofFIG.5C.

For internal query425(Q4), there are two outer semi joins with T2 and T3 (“T1.p OSJ=T2.p” and “T5.q OSJ>T3.q”), and a single inner join with T1 and T5 (“T1.k=T5.k”). For the two outer semi joins, tables T2 and T3 become part of the disjunctive filter predicates (T2.AJM=1 OR T3.AJM=0), which are ordered to join after the other tables. Thus, as shown in join order560C ofFIG.5D, there are four possible join order options: 1/4 (T1, T5, T2, T3), 2/4 (T5, T1, T2, T3), 3/4 (T1, T5, T3, T2), and 4/4 (T5, T1, T3, T2). Optimizer layer128may select a specific join order option based on efficiency. Join order560C (i.e., T1, T5, T2, T3) is reproduced below:Tables in the first join (Option 1): {T1, T5}Tables in the second join (Option 1): {T1, T5, T2}Tables in the third join (Option 1): {T1, T5, T2, T3}Join order option 1/4: (T1, T5, T2, T3)Join order option 2/4: (T5, T1, T2, T3)Join order option 3/4: (T1, T5, T3, T2)Join order option 4/4: (T5, T1, T3, T2)
Reproduction ofFIG.5D.
Augmented Anti Join Marker

FIG.6depicts an example determination of anti-join marker (AJM)670for the outer semi joined table T2 in execution plan324(for Q2) ofFIG.3C. As shown inFIG.6, AJM670may be determined by proceeding through three steps for each T1 row in the OSJ operation. First, if any of the disjunctive filter predicates (“T1.ten=1 OR T1.ten=2”) are satisfied, then T2.AJM is set to 2 and the evaluation of the current row is completed. This step may be integrated as part of a pre-filter, enabling join evaluation to be skipped if any disjunctive filter predicate is satisfied. Second, if some T2 row satisfies the OSJ join condition of “T1.hundred=T2.hundred”, then T2.AJM is set to 0. Third or otherwise, T2.AJM is set to 1. AJM670for Q2 is reproduced below:1. Set T2.AJM to 2 for rows where (T1.ten=1 OR T1.ten=2) is satisfied2. Set T2.AJM to 0 for rows wheresome T2 row satisfies T1.hundred=T2.hundred3. Set T2.AJM to 1 otherwise
AJM Value Definitions:0: Matching row is found/Anti-join marker is 01: Matching row is not found/Anti-join marker is set to 12: Disjunctive filter predicates evaluate to true
Reproduction ofFIG.6.

As discussed above, an AJM value of 0 corresponds to “true” and indicates that a matching row was found in the join (and thus the result row has the semantics of semi-join). An AJM value of 1 corresponds to “false” and indicates that no matching row was found in the join (and thus the result row has the semantics of anti-join). An AJM value of 2 indicates that no join evaluation occurred, since disjunctive filter predicates evaluate to true. Execution layer129may automatically provide the “AJM” value when processing an OSJ operation in execution plan124.

Example Execution Strategy

FIG.7Adepicts execution plan724using join order option 3/4 (T1, T5, T3, T2) in join order560C ofFIG.5Dfor Query4. Lines 5-8 of execution plan724implement join order option 3/4. Thus, an inner hash join of T1 and T5 happens first at line 4. To perform the hash join, all the rows from the left side (T1), or build side, are retrieved. Note that post join filter (T1.h=1 OR T5.g=99 OR T2.AJM=1 OR T3.AJM=0) is associated with the outer semi-join(s) as they are part of the disjunction. The resulting rows from the inner hash join form the left side of the first OSJ with T3 (line 3). Execution plan724for Q4 is reproduced below:

0SELECT STATEMENT1FILTER<− filter T2.AJM=1 orT3.AJM=0 or T1.h=1 orT5.g=992OSJ<− (B)3OSJ<− (A)4HASH JOIN<− join on T1.k = T5.k5TABLE ACCESS FULL T1<− filter T1.z > 196TABLE ACCESS FULL T57TABLE ACCESS FULL T3<− filter T3.f = 78TABLE ACCESS FULL T2<− filter T2.d > 5
Reproduction ofFIG.7A.

While a hash join is used here, other join types may be used as well, such as sort merge join and nested loop join.

A pre-filter allows bypassing of join evaluation for rows that satisfy disjunctive filter predicates for outer semi-join. A row that satisfies the disjunctive filter predicates (T1.h OR T5.g) is bypassed and does not participate in the first outer semi-join with T3. The rows that do not satisfy the disjunctive filter predicates become the left side of the first outer semi-join. The resulting rows of the first outer semi-join form the left side of the second outer semi-join. A row that satisfies the disjunctive filter predicates (T1.h OR T5.g OR T3,AJM=0) is bypassed and does not participate in the second outer semi-join with T5. The rows that do not satisfy these disjunctive filter predicates become the left side of the second outer semi-join.

Since the amount of work that is performed for an OSJ can be determined based on the projected selectivity of the disjunctive filter predicates, optimizer layer128can use the projected selectivity to refine an estimated cost of performing the OSJ to reflect the actual work performed after accounting for the row evaluation bypasses. Similarly, the estimated or actual cardinality of data columns, or the estimated or actual number of distinct values for each data column, can also be used to refine the estimated cost of performing the OSJ, as columns with lower cardinality tend to result in fewer result rows since only the first matching row in a right-side table is provided in an OSJ operation.

As shown in the determination of anti join marker (AJM)770inFIG.7B, the first OSJ with T3 first checks whether “T1.h=1 OR T5.g=99” is satisfied, and if so, sets T3.AJM to 2 (null). Next, the first OSJ checks whether some T3 row satisfies “T5.q>T3.q”, and if so, sets T3.AJM to 0 (true). Otherwise, the first OSJ sets T3.AJM to 1 (false). The resulting rows from the first OSJ then form the left side of the second OSJ with T2 (line 2). AJM770is reproduced below:A. T3.AJM1. Set T3.AJM to 2 for rows where (T1.h=1 OR T5.g=99) is satisfied2. Set T3.AJM to 0 for rows wheresome T3 row satisfies T5.q>T3.q3. Set T3.AJM to 1 otherwiseB. T2.AJM1. Set T2.AJM to 2 for rows where(T1.h=1 OR T5.g=99 or T3.AJM=0) is satisfied2. Set T2.AJM to 0 for rows wheresome T2 row satisfies T1.p=T2.p3. Set T2.AJM to 1 otherwise
Reproduction ofFIG.7B.

As shown in the determination of anti join marker (AJM)770inFIG.7B, the second OSJ with T2 first checks whether “T1.h=1 OR T5.g=99 OR T3.AJM=0” is satisfied, and if so, sets T2.AJM to 2. Next, the second OSJ checks whether some T2 row satisfies “T1.q=T2.q”, and if so, sets T2.AJM to 0. Otherwise, the second OSJ sets T2.AJM to 1.

The resulting rows from the second OSJ are then processed through the post-join filter predicates (line 1), or “T2.AJM=1 OR T3.AJM=0 OR T1.h=1 OR T5.g=99”. If the disjunctive filter predicates are not satisfied, the result row is not returned. Otherwise, the result row is returned to answer the original database query (line 0).

Existing Disjunctive Subquery Unnesting Techniques

FIG.8depicts an external query842(Q6) using a first class of disjunctive subqueries and an unnested version using existing techniques without OSJ as internal query825. External query842may correspond to external query142, and internal query825may correspond to internal query125. The first class of disjunctive subqueries includes multiple IN, EXISTS, or ANY subqueries that appear in a disjunction in the outer query block's WHERE clause, and requires the outer query block's columns in the connecting or correlating conditions of the subqueries to be the same. For example, referring to external query842, it is observed that the same outer block column, “T2.x”, appears in the connecting condition and correlating conditions of the IN and EXISTS subqueries, respectively. External query842(Q6) is reproduced below:

Query Q6.SELECT T1.xFROM T1, T2WHERE T1.y = T2.y and(T2.x IN (SELECT T3.aFROM T3WHERE T3.a = T2.x)OREXISTS (SELECT 1FROM T4, T5WHERE T4.k = T5.k andT4.m > 1 and T4.b = T2.x));

A proposed unnesting of external query842(Q6) is shown as internal query825A (Q7), which includes a UNION ALL view and a semi-join (“S=”). This approach may introduce significant processing overhead when compared to unnesting using OSJ, which does not require the generation of a UNION ALL view. Internal query825A is reproduced below:

Query Q7.SELECT T1.xFROM T1, T2,(SELECT T3.a as ZFROM T3UNION ALLSELECT T4.b AS ZFROM T4, T5WHERE T4.k = T5.k and T4.m > 1) VWHERE T1.y = T2.y and T2.x S= V.Z;

A proposed unnesting of external query842(Q6) using OSJ is shown as internal query825B (Q7o). Q7o is more efficient than Q7. Note that an inline view V has been introduced in Q7o to represent the second subquery, as it contains multiple tables. Internal query825B is reproduced below:

Query Q7o.SELECT T1.xFROM T1, T2, T3, (SELECT T4.bFROM T4, T5WHERE T4.k = T5.k and T4.m > 1) VWHERE T1.y = T2.y and T2.x OSJ= T3.a and T2.x OSJ= V.b(T3.AJM = 0 OR V.AJM = 0);

FIG.9depicts an external query942(Q8) using a second class of disjunctive subqueries and an unnested version using existing techniques without OSJ as internal query925. External query942may correspond to external query142, and internal query925may correspond to internal query125. In the second class of disjunctive subqueries, IN, EXISTS, or ANY subqueries contain disjunctive correlation predicates in their WHERE clause. For example, referring to external query942, it is observed that the EXISTS subquery correlates “T1.hundred” in disjunction. External query942is reproduced below:

Query Q8.SELECT T1.tenFROM G_4K T1WHERE EXISTS (SELECT 1FROM H_4K T2, T_5K T3WHERE T2.thousand = T3.thousand andT2.ten > 7 AND(T2.hundred = T1.hundred ORT3.ten = T1.hundred));

A proposed unnesting of external query942is shown as internal query925A (Q9), which includes a UNION ALL view and a semi-join (“S=”). Since each branch of the UNION ALL requires a duplication of the subquery tables (“H_4K T2, T_5K T3”) and the join operations (“T2.thousand=T3.thousand”), this approach may introduce significant processing overhead when compared to unnesting using OSJ, which does not require the generation of a UNION ALL view. Internal query925A (Q9) is reproduced below:

Query Q9.SELECT T1.tenFROM G_4K T1,(SELECT T2.hundred ZFROM H_4K T2, T_5K T3WHERE T2.thousand = T3.thousand AND T2.ten > 7UNION ALLSELECT T3.ten ZFROM H_4K T2, T_5K T3WHERE T2.thousand = T3.thousand AND T2.ten > 7) VWHERE T1.hundred S= V.Z;

A proposed unnesting of external query Q8 using OSJ is shown as internal query925B (Q10), which is more efficient than Q9. Internal query925B is reproduced below:

Query Q10.SELECT T1.tenFROM G_4K T1,(SELECT T2.hundred ZFROM H_4K T2, T_5K T3WHERE T2.thousand = T3.thousand AND T2.ten > 7) V1,(SELECT T3.ten ZFROM H_4K T2, T_5K T3WHERE T2.thousand = T3.thousand AND T2.ten > 7) V2WHERE T1.hundred OSJ= V1.Z and T1.hundred OSJ= V2.Z and(V1.AJM = 0 OR V2.AJM = 0);
Example Process for Using Outer Semi-Join

FIG.10is a flow diagram that depicts an example process1000that database management system110may perform to use outer semi-join operations to optimize execution plans of database queries.

Referring toFIG.1, in block1010, database management system110receives external query142for database132comprising a plurality of tables, wherein external query142includes one or more disjunctive subqueries such as disjunctive subquery144A,144B, and144C. For example, a user of client device140may operate a database client to provide a SQL query as external query142, which is then transmitted to database management system110via network150, and then delegated to a specific database server instance, such as database server instance122. For the purposes of illustration, external query142may correspond to external query342(Q1).

In block1012, optimizer layer128determines execution plan124for external query142, wherein the execution plan includes an outer semi-join (OSJ) operation to unnest the one or more disjunctive subqueries, wherein the OSJ operation includes matching criteria between a left-side table and a right-side table in the plurality of tables, and wherein the OSJ operation processes every row from the left-side table and returns, for each said every row from the left-side table that satisfies the matching criteria in at least one row of the right-side table, a first matching row from the at least one row of the right-side table. For example, as discussed above in conjunction with internal query225D ofFIG.2B, the outer semi join combines the semantics of left-outer join (processing every row from the left-side table) and semi-join (returning corresponding first matching rows from the right-side table). As described above, the OSJ operation can unnest disjunctive subqueries. For example, referring to external query342, disjunctive subquery344A is the one or more disjunctive subqueries, and internal query325includes an OSJ operation that includes matching criteria (T1.hundred=T2.hundred) between a left-side table T1 and a right-side table T2 to unnest disjunctive subquery344A. Execution plan324, which may correspond to execution plan124, reflects the OSJ operation in line 2.

In block1014, execution layer129executes execution plan124to generate one or more output rows, wherein executing the execution plan comprises executing the OSJ operation to generate one or more intermediate rows and associated anti-join markers (AJMs) that indicate whether each of the one or more intermediate rows were bypassed for join evaluation or did not find a match in the right-side table. For example, referring toFIG.6, steps are illustrated in AJM670to determine the AJMs for each row of T1 processed in the OSJ operation. As discussed previously, the first step of AJM670may be used as part of a pre-filter to skip evaluation of rows that already satisfy one of the disjunctive filter predicates.

In block1016, execution layer129provides the one or more output rows from block1014back to client device140to respond to the original external query142. Client device140may then display the output rows in an interactive text or graphical terminal display, or use the output rows for further processing in an interactive application program, a client/server or peer-to-peer service, an automated script or data processing job, or any other use case.

Database Overview

Embodiments of the present invention are used in the context of database management systems (DBMSs). Therefore, a description of an example DBMS is provided.

Generally, a server, such as a database server, is a combination of integrated software components and an allocation of computational resources, such as memory, a node, and processes on the node for executing the integrated software components, where the combination of the software and computational resources are dedicated to providing a particular type of function on behalf of clients of the server. A database server governs and facilitates access to a particular database, processing requests by clients to access the database.

A database comprises data and metadata that is stored on a persistent memory mechanism, such as a set of hard disks. Such data and metadata may be stored in a database logically, for example, according to relational and/or object-relational database constructs.

Users interact with a database server of a DBMS by submitting to the database server commands that cause the database server to perform operations on data stored in a database. A user may be one or more applications running on a client computer that interact with a database server. Multiple users may also be referred to herein collectively as a user.

A database command may be in the form of a database statement. For the database server to process the database statements, the database statements must conform to a database language supported by the database server. One non-limiting example of a database language that is supported by many database servers is SQL, including proprietary forms of SQL supported by such database servers as Oracle, (e.g. Oracle Database 11g). SQL data definition language (“DDL”) instructions are issued to a database server to create or configure database objects, such as tables, views, or complex types. Data manipulation language (“DML”) instructions are issued to a DBMS to manage data stored within a database structure. For instance, SELECT, INSERT, UPDATE, and DELETE are common examples of DML instructions found in some SQL implementations. SQL/XML is a common extension of SQL used when manipulating XML data in an object-relational database.

Generally, data is stored in a database in one or more data containers, each container contains records, and the data within each record is organized into one or more fields. In relational database systems, the data containers are typically referred to as tables, the records are referred to as rows, and the fields are referred to as columns. In object-oriented databases, the data containers are typically referred to as object classes, the records are referred to as objects, and the fields are referred to as attributes. Other database architectures may use other terminology. Systems that implement the present invention are not limited to any particular type of data container or database architecture. However, for the purpose of explanation, the examples and the terminology used herein shall be that typically associated with relational or object-relational databases. Thus, the terms “table”, “row” and “column” shall be used herein to refer respectively to the data container, record, and field.

Query Optimization and Execution Plans

Query optimization generates one or more different candidate execution plans for a query, which are evaluated by the query optimizer to determine which execution plan should be used to compute the query.

Execution plans may be represented by a graph of interlinked nodes, each representing an plan operator or row sources. The hierarchy of the graphs (i.e., directed tree) represents the order in which the execution plan operators are performed and how data flows between each of the execution plan operators.

An operator, as the term is used herein, comprises one or more routines or functions that are configured for performing operations on input rows or tuples to generate an output set of rows or tuples. The operations may use interim data structures. Output set of rows or tuples may be used as input rows or tuples for a parent operator.

An operator may be executed by one or more computer processes or threads. Referring to an operator as performing an operation means that a process or thread executing functions or routines of an operator are performing the operation.

A row source performs operations on input rows and generates output rows, which may serve as input to another row source. The output rows may be new rows, and or a version of the input rows that have been transformed by the row source.

A match operator of a path pattern expression performs operations on a set of input matching vertices and generates a set of output matching vertices, which may serve as input to another match operator in the path pattern expression. The match operator performs logic over multiple vertex/edges to generate the set of output matching vertices for a specific hop of a target pattern corresponding to the path pattern expression.

An execution plan operator generates a set of rows (which may be referred to as a table) as output and execution plan operations include, for example, a table scan, an index scan, sort-merge join, nested-loop join, filter, and importantly, a full outer join.

A query optimizer may optimize a query by transforming the query. In general, transforming a query involves rewriting a query into another semantically equivalent query that should produce the same result and that can potentially be executed more efficiently, i.e. one for which a potentially more efficient and less costly execution plan can be generated. Examples of query transformation include view merging, subquery unnesting, predicate move-around and pushdown, common subexpression elimination, outer-to-inner join conversion, materialized view rewrite, and star transformation.

Hardware Overview

According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques.

For example,FIG.11is a block diagram that illustrates a computer system1100upon which an embodiment of the invention may be implemented. Computer system1100includes a bus1102or other communication mechanism for communicating information, and a hardware processor1104coupled with bus1102for processing information. Hardware processor1104may be, for example, a general purpose microprocessor.

Computer system1100also includes a main memory1106, such as a random access memory (RAM) or other dynamic storage device, coupled to bus1102for storing information and instructions to be executed by processor1104. Main memory1106also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor1104. Such instructions, when stored in non-transitory storage media accessible to processor1104, render computer system1100into a special-purpose machine that is customized to perform the operations specified in the instructions.

Computer system1100further includes a read only memory (ROM)1108or other static storage device coupled to bus1102for storing static information and instructions for processor1104. A storage device1110, such as a magnetic disk, optical disk, or solid-state drive is provided and coupled to bus1102for storing information and instructions.

Computer system1100may be coupled via bus1102to a display1112, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device1114, including alphanumeric and other keys, is coupled to bus1102for communicating information and command selections to processor1104. Another type of user input device is cursor control1116, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor1104and for controlling cursor movement on display1112. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane.

Computer system1100may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system1100to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system1100in response to processor1104executing one or more sequences of one or more instructions contained in main memory1106. Such instructions may be read into main memory1106from another storage medium, such as storage device1110. Execution of the sequences of instructions contained in main memory1106causes processor1104to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical disks, magnetic disks, or solid-state drives, such as storage device1110. Volatile media includes dynamic memory, such as main memory1106. Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid-state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge.

Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus1102. Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor1104for execution. For example, the instructions may initially be carried on a magnetic disk or solid-state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system1100can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus1102. Bus1102carries the data to main memory1106, from which processor1104retrieves and executes the instructions. The instructions received by main memory1106may optionally be stored on storage device1110either before or after execution by processor1104.

Computer system1100also includes a communication interface1118coupled to bus1102. Communication interface1118provides a two-way data communication coupling to a network link1120that is connected to a local network1122. For example, communication interface1118may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface1118may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface1118sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information.

Network link1120typically provides data communication through one or more networks to other data devices. For example, network link1120may provide a connection through local network1122to a host computer1124or to data equipment operated by an Internet Service Provider (ISP)1126. ISP1126in turn provides data communication services through the worldwide packet data communication network now commonly referred to as the “Internet”1128. Local network1122and Internet1128both use electrical, electromagnetic, or optical signals that carry digital data streams. The signals through the various networks and the signals on network link1120and through communication interface1118, which carry the digital data to and from computer system1100, are example forms of transmission media.

Computer system1100can send messages and receive data, including program code, through the network(s), network link1120and communication interface1118. In the Internet example, a server1130might transmit a requested code for an application program through Internet1128, ISP1126, local network1122and communication interface1118.

The received code may be executed by processor1104as it is received, and/or stored in storage device1110, or other non-volatile storage for later execution.

A computer system process comprises an allotment of hardware processor time, and an allotment of memory (physical and/or virtual), the allotment of memory being for storing instructions executed by the hardware processor, for storing data generated by the hardware processor executing the instructions, and/or for storing the hardware processor state (e.g. content of registers) between allotments of the hardware processor time when the computer system process is not running. Computer system processes run under the control of an operating system, and may run under the control of other programs being executed on the computer system.

In the foregoing specification, embodiments of the invention have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the invention, and what is intended by the applicants to be the scope of the invention, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.

Software Overview

FIG.12is a block diagram of a basic software system1200that may be employed for controlling the operation of computing device1100. Software system1200and its components, including their connections, relationships, and functions, is meant to be exemplary only, and not meant to limit implementations of the example embodiment(s). Other software systems suitable for implementing the example embodiment(s) may have different components, including components with different connections, relationships, and functions.

Software system1200is provided for directing the operation of computing device1100. Software system1200, which may be stored in system memory (RAM)1106and on fixed storage (e.g., hard disk or flash memory)1110, includes a kernel or operating system (OS)1210.

The OS1210manages low-level aspects of computer operation, including managing execution of processes, memory allocation, file input and output (I/O), and device I/O. One or more application programs, represented as1202A,1202B,1202C . . .1202N, may be “loaded” (e.g., transferred from fixed storage1110into memory1106) for execution by the system1200. The applications or other software intended for use on device1100may also be stored as a set of downloadable computer-executable instructions, for example, for downloading and installation from an Internet location (e.g., a Web server, an app store, or other online service).

Software system1200includes a graphical user interface (GUI)1215, for receiving user commands and data in a graphical (e.g., “point-and-click” or “touch gesture”) fashion. These inputs, in turn, may be acted upon by the system1200in accordance with instructions from operating system1210and/or application(s)1202. The GUI1215also serves to display the results of operation from the OS1210and application(s)1202, whereupon the user may supply additional inputs or terminate the session (e.g., log off).

OS1210can execute directly on the bare hardware1220(e.g., processor(s)1104) of device1100. Alternatively, a hypervisor or virtual machine monitor (VMM)1230may be interposed between the bare hardware1220and the OS1210. In this configuration, VMM1230acts as a software “cushion” or virtualization layer between the OS1210and the bare hardware1220of the device1100.

VMM1230instantiates and runs one or more virtual machine instances (“guest machines”). Each guest machine comprises a “guest” operating system, such as OS1210, and one or more applications, such as application(s)1202, designed to execute on the guest operating system. The VMM1230presents the guest operating systems with a virtual operating platform and manages the execution of the guest operating systems.

In some instances, the VMM1230may allow a guest operating system to run as if it is running on the bare hardware1220of device1100directly. In these instances, the same version of the guest operating system configured to execute on the bare hardware1220directly may also execute on VMM1230without modification or reconfiguration. In other words, VMM1230may provide full hardware and CPU virtualization to a guest operating system in some instances.

In other instances, a guest operating system may be specially designed or configured to execute on VMM1230for efficiency. In these instances, the guest operating system is “aware” that it executes on a virtual machine monitor. In other words, VMM1230may provide para-virtualization to a guest operating system in some instances.

The above-described basic computer hardware and software is presented for purpose of illustrating the basic underlying computer components that may be employed for implementing the example embodiment(s). The example embodiment(s), however, are not necessarily limited to any particular computing environment or computing device configuration. Instead, the example embodiment(s) may be implemented in any type of system architecture or processing environment that one skilled in the art, in light of this disclosure, would understand as capable of supporting the features and functions of the example embodiment(s) presented herein.

EXTENSIONS AND ALTERNATIVES

Although some of the figures described in the foregoing specification include flow diagrams with steps that are shown in an order, the steps may be performed in any order, and are not limited to the order shown in those flowcharts. Additionally, some steps may be optional, may be performed multiple times, and/or may be performed by different components. All steps, operations and functions of a flow diagram that are described herein are intended to indicate operations that are performed using programming in a special-purpose computer or general-purpose computer, in various embodiments. In other words, each flow diagram in this disclosure, in combination with the related text herein, is a guide, plan or specification of all or part of an algorithm for programming a computer to execute the functions that are described. The level of skill in the field associated with this disclosure is known to be high, and therefore the flow diagrams and related text in this disclosure have been prepared to convey information at a level of sufficiency and detail that is normally expected in the field when skilled persons communicate among themselves with respect to programs, algorithms and their implementation.

In the foregoing specification, the example embodiment(s) of the present invention have been described with reference to numerous specific details. However, the details may vary from implementation to implementation according to the requirements of the particular implement at hand. The example embodiment(s) are, accordingly, to be regarded in an illustrative rather than a restrictive sense.