and/or between computing devices (e.g. between the data server 122 and the client device 106), a network bus system including the network 102 or portions thereof, a processor mesh, a combination thereof, etc. In some implementations, the DBMS 220, its sub-components and various other software operating on the data server 122 (e.g., an operating system, etc.) may cooperate and communicate via a software communication mechanism implemented in association with the bus 206. The software communication mechanism can include and/or facilitate, for example, inter-process communication, local function or procedure calls, remote procedure calls, an object broker (e.g., CORBA), direct socket communication (e.g., TCP/IP sockets) among software modules, UDP broadcasts and receipts, HTTP connections, etc. Further, any or all of the communication could be secure (e.g., SSH, HTTPS, etc.).

The communication unit 208 may include one or more interface devices (I/F) for wired and/or wireless connectivity with the network 102. For instance, the communication unit 208 may include, but is not limited to, CAT-type interfaces; wireless transceivers for sending and receiving signals using radio transceivers (4G, 3G, 2G, etc.) for communication with the mobile network 102, and radio transceivers for Wi-Fi™ and close-proximity (e.g., Bluetooth®, NFC, etc.) connectivity, etc.; USB interfaces; various combinations thereof; etc. In some implementations, the communication unit 208 can link the processor 202 to the network 102, which may in turn be coupled to other processing systems. The communication unit 208 can provide other connections to the network 102 and to other entities of the system 100 using various standard network communication protocols.

Example Database Management System (DBMS) 220 Module

Referring now to FIG. 3, the DBMS 220 module is shown in more detail according to one embodiment. FIG. 3 is a block diagram of the DBMS 220 module included in a data server 122 according to one embodiment.

The DBMS 220 provides access to data stored by a database 120. For example, in one embodiment, the DBMS 220 provides an application 109 using a driver 228 access to data stored by a database 120 via the network 102. In one embodiment, the DBMS 220 receives a query requesting access to and/or manipulation of data, parses the query (e.g. to determine permissions, semantics, syntax, etc.), generates and selects a query plan for accessing and/or manipulating the data as requested, and executes the plan to access and/or manipulate the requested data.

As the number of databases, the size of databases and the number of queries made on a database increase, the efficiency of query processing and, therefore, the optimization of the query plan becomes increasingly important. The present disclosure provides a DBMS 220 for processing join queries using multiple indexes in the join operation(s), which may provide more efficient processing than current DBMS systems, for example, by reducing the number of rows read when executing the query.

In the illustrated embodiment, the DBMS 220 includes a multi-index disjunction optimization module 312 and a multi-index conjunction optimization module 314. However, it should be recognized that, according to some embodiments, one of the multi-index disjunction optimization module 312 and its features and functionality and the multi-index conjunction optimization module 314 and its features and functionality may be omitted from the DBMS 220. It should also be recognized that the modules 312 and 314, comprised in the DBMS 220 module may not be separate modules. For example, while 312 is described with regard to disjunctive operators and 314 is described with regard to conjunctive operators for clarity and convenience herein, the functionality need not be divided into the separate modules 312 and 314. It should further be recognized that the modules 312 and 314, comprised in the DBMS 220 module may not necessarily all reside on the same data server 122. In one embodiment, the modules 312, 314 and/or their functionality are distributed across multiple data servers 122.

The multi-index disjunction optimization module 312 includes code and routines for generating and selecting a query plan using multiple indexes for a join query that includes a disjunction operator. In one embodiment, the multi-index disjunction optimization module 312 is a set of instructions executable by the processor 202. In another embodiment, the multi-index disjunction optimization module 312 is stored in the memory 204 and is accessible and executable by the processor 202. In either embodiment, the multi-index disjunction optimization module 312 is adapted for cooperation and communication with the processor 202, other components of the data server 122 and other components of the DBMS 220 module.

The multi-index disjunction optimization module 312 includes code and routines for generating and selecting a query plan (e.g. a query tree) using multiple indexes for a join query that includes a disjunction operator. In one embodiment, the multi-index disjunction optimization module 312 determines a received query is a join query including a join operation on two tables. Examples of join operations include, but are not limited to an inner join, left outer join, right outer join, full outer join, or a cross join. For example, the multi-index disjunction optimization module 312 determines a received query includes an inner join on a first table (e.g. Tab1) and a second table (e.g. Tab2).

In one embodiment, the multi-index disjunction optimization module 312 determines that the join operation further includes two or more conditions. For example, the multi-index disjunction optimization module 312 determines the join query includes a first condition (e.g. Tab1.Col1=Tab2.Fld1) and a second condition (e.g. Tab1.Col2=Tab2.Fld2).

In one embodiment, the multi-index disjunction optimization module 312 determines that two conditions are based on two or more columns that are indexed. For example, the multi-index disjunction optimization module 312 determines that Fld1 and Fld2 are columns of table Tab2 which has indexes defined on them. In some embodiments, the multi-index disjunction optimization module 312 determines that a participating column of Table Tab2 does not have an index defined on it and dynamically indexes the participating column. While a typical index is created by a user and persist unless or until a user explicitly removes the index, a dynamic index is a temporary index created during execution of the query optimization module 302 and destroyed after execution of the query.

In one embodiment, the multi-index disjunction optimization module 312 determines that the two conditions are related by a disjunction operation. For example, the multi-index disjunction optimization module 312 determines that the first condition (e.g. Tab1.Col1=Tab2.Fld1) and a second condition (e.g. Tab1.Col2=Tab2.Fld2) are related by an “OR”.

The multi-index disjunction optimization module 312 generates a query tree by adding nodes including a first leaf node for an index scan on an index that is a basis for the first condition (e.g. used to evaluate a part of the first condition), a second leaf node for an index scan on an index that is the basis for the second condition (e.g. used to evaluate a part of the second condition), a third leaf node for a scan operation, an intermediary node associated with a Tuple Identifier (TID) Union operation using the aforementioned index scans, an intermediary node associated with an Multi Index Augmented Nested Loop (MIANL) join that evaluates the first and second conditions using the TID union. For example, the multi-index disjunction optimization module 312 generates a query tree by adding nodes including a first leaf node for an index scan on Tab2 using Fld1 of Tab2 as the index key, where Tab2.Fld1 is a basis for evaluating the first condition of Tab1.Col1=Tab2.Fld1, a second leaf node for an index scan on index scan on Tab2 using Fld2 of Tab2 as the index key, where Tab2.Fld2 is a basis for evaluating the second condition of Tab1.Col2=Tab2.Fld2, a third leaf node for a table scan operation of TAB1, an intermediary node associated with a Tuple Identifier (TID) Union operation (i.e. one kind of set operation) using the aforementioned index scans, an intermediary node associated with an Multi-Index Augmented Nested Loop (MIANL) join that evaluates the first and second conditions (i.e. Tab1.Col1=Tab2.Fld1, Tab1.Col2=Tab2.Fld2 in this example) using the TID union. In one embodiment, a TID Union is an operation that evaluates tuple (row) identifiers which are returned by aforementioned index scans and discards duplicates (i.e. rows having Tuple IDs that meet both the first and second conditions). To summarize and simplify, in one embodiment, for the example tables and indexes discussed in this paragraph, the multi-index disjunction optimization module 312 generates a query tree similar to the query tree 800 of FIG. 8.

In one embodiment, the multi-index disjunction optimization module 312 determines the query tree (e.g. query tree 800) is the plan with the lowest cost (e.g. vs query tree 600 and 800), and that query plan (e.g. 800) is selected for execution and is executed. The features, functionality, and benefits of the multi-index disjunction optimization module 312 are discussed in detail below with reference to FIG. 8 and the query tree 800 therein.

The multi-index conjunction optimization module 314 includes code and routines for generating and selecting a query plan using multiple indexes for a join query that includes a conjunction operator. In one embodiment, the multi-index conjunction optimization module 314 is a set of instructions executable by the processor 202. In another embodiment, the multi-index conjunction optimization module 314 is stored in the memory 204 and is accessible and executable by the processor 202. In either embodiment, the multi-index conjunction optimization module 314 is adapted for cooperation and communication with the processor 202, other components of the data server 122 and other components of the DBMS 220 module.

The multi-index conjunction optimization module 314 includes code and routines for generating and selecting a query plan (e.g. a query tree) using multiple indexes for a join query that includes a conjunction operator. In one embodiment, the multi-index conjunction optimization module 314 determines a received query is a join query including a join operation on two tables. Examples of join operations include, but are not limited to an inner join, left outer join, right outer join, full outer join, or a cross join. For example, the multi-index conjunction optimization module 314 determines a received query includes an inner join on a first table (e.g. Tab1) and a second table (e.g. Tab2).

In one embodiment, the multi-index conjunction optimization module 314 determines that the join operation further includes two or more conditions. For example, the multi-index conjunction optimization module 314 determines the join query includes a first condition (e.g. Tab1.Col1=Tab2.Fld1) and a second condition (e.g. Tab1.Col2=Tab2.Fld2).

In one embodiment, multi-index conjunction optimization module 314 determines that two conditions are based on two or more columns that are indexed. For example, multi-index conjunction optimization module 314 determines that Fld1 and Fld 2 are columns of Tab2 which has indexes defined on them. In some embodiments, the multi-index conjunction optimization module 314 determines that a participating column of Table Tab2 does not have an index defined on it and dynamically indexes the participating column.

In one embodiment, the multi-index conjunction optimization module 314 determines that the two conditions are related by a conjunction operation. For example, the multi-index conjunction optimization module 314 determines that the first condition (e.g. Tab1.Col1=Tab2.Fld1) and a second condition (e.g. Tab1.Col2=Tab2.Fld2) are related by an “AND”.

The multi-index conjunction optimization module 314 generates a query tree by adding nodes including a first leaf node for an index scan on an index that is a basis for the first condition (e.g. used to evaluate a part of the first condition), a second leaf node for an index scan on an index that is the basis for the second condition (e.g. used to evaluate a part of the second condition), a third leaf node for a scan operation, an intermediary node associated with a Tuple Identifier (TID) Intersection operation using the aforementioned index scans, an intermediary node associated with an Multi-Index Augmented Nested Loop (MIANL) join that evaluates the first and second conditions using the TID Intersection. For example, the multi-index conjunction optimization module 314 generates a query tree by adding nodes including a first leaf node for an index scan on Tab2 using Fld1 of Tab2 as the index key, where Tab2.Fld1 is a basis for evaluating the first condition of Tab1.Col1=Tab2.Fld1, a second leaf node for an index scan on index scan on Tab2 using Fld2 of Tab2 as the index key, where Tab2.Fld2 is a basis for evaluating the second condition of Tab1.Col2=Tab2.Fld2, a third leaf node for a table scan operation of Tab1, an intermediary node associated with a Tuple Identifier (TID) Intersection operation using the aforementioned index scans, an intermediary node associated with an MIANL join that evaluates the first and second conditions (i.e. Tab1.Col1=Tab2.Fld1, Tab1.Col2=Tab2.Fld2 in this example) using the TID Intersection. In one embodiment, a TID Intersection is an operation that evaluates tuple (row) identifiers which are returned by aforementioned index scans and discards duplicates (i.e. rows having Tuple IDs that meet both the first and second conditions). To summarize and simplify, in one embodiment, for the example tables and indexes discussed in this paragraph, the multi-index conjunction optimization module 314 generates a query tree similar to the query tree 1000 of FIG. 10.

In one embodiment, the multi-index conjunction optimization module 314 determines the query tree is the plan with the lowest cost (e.g. vs query tree 900), and that query plan (e.g. 1000) is selected for execution and executed. The features, functionality, and benefits of the multi-index conjunction optimization module 314 are discussed in detail below with reference to FIG. 10 and the query tree 1000 therein.

Databases perform Joins when a query contains multiple tables. There are multiple types of join methods to process joins, but two of the widely used join methods are “Nested Loop” and “Augmented Nested Loop.” Since different databases refer to these join methods using different names, they are explained below with reference to the example scenarios of FIGS. 4 & 5.

Referring now to FIG. 4, FIG. 4 illustrates an example Augmented Nested Loop query scenario, also referred to as Query Scenario 1 herein, according to one embodiment. As indicated at 402, there are two tables-Tab1 and Tab2. Tab1 has three columns-Col1, Col2, and Col3. Col1, Col2, and Col3 columns that all have an integer data type. Tab2 has three columns-Fld1, Fld2, and Fld3. Fld1, Fld2, and Fld3 columns that all have an integer data type. As indicated at 404, Tab1 does not have an index, while Tab2 has multiple indexes-created on Fld1, an index created on Fld2 and a composite index created on (Fld2, Fld3). As indicated at 406, a join query—an inner join in the example shown—is received. As mentioned above, a join is used when a query includes or involves more than one table. In the illustrated Query Scenario 1, the query received, as indicated at 406, includes Tab1 and Tab2 in order to obtain the result of where Col1 of Tab1 and Fld1 of Tab2 are the same (i.e. Tab1.Col1=Tab2.Fld1). Since Fld1 of Tab2 has an index, this index may be used to evaluate the join condition, this join method is referred to as an “Augmented Nested Loop” (ANL).

Referring now to FIG. 5, FIG. 5 illustrates an example Nested Loop query scenario, also referred to as Query Scenario 2 herein, according to one embodiment. As indicated at 502, there are two tables-Tab1 and Tab2. Tab1 has three columns—Col1, Col2, and Col3. Col1, Col2, and Col3 columns that all have an integer data type. Tab2 has three columns—Fld1, Fld2, and Fld3. Fld1, Fld2, and Fld3 columns that all have an integer data type. As indicated at 504, Tab1 does not have an index, while Tab2 has multiple indexes—created on Fld1, an index created on Fld2 and a composite index created on (Fld2, Fld3). As indicated at 506, a join query—an inner join in the example shown—is received. As mentioned above, a join is used when a query includes or involves more than one table. In the illustrated Query Scenario 2, the query received, as indicated at 506, includes Tab1 and Tab2 in order to obtain the result of where Col3 of Tab1 and Fld3 of Tab2 are the same (i.e. Tab1.Col3=Tab2.Fld3). Since neither Col3 of Tab1 nor Fld3 of Tab2 has an index, hence no index is used to evaluate the join condition. This join method is referred to as “Nested Loop” (NL).

The NL is computationally more costly compared to an ANL, because a NL uses the Cartesian product of two tables before evaluating the join condition, whereas an ANL uses an index to evaluate the join condition. Additionally, an index scan is generally faster and less computationally costly than a table scan. Therefore, the query plan 408 using the Augmented Nested Loop, as depicted in block diagram 400 of FIG. 4, would execute more quickly than the query plan 508 using the Nested Loop, as depicted in block diagram 500 of FIG. 5, if everything else remained equal (e.g. number of rows returned in the result) due to the use of ANL vs NL (422 vs 524 & 522) and usage of the index scan instead of using table scan (426 vs 528). A Multi-Index Augmented Loop differs from an Augmented Nested Loop in that it utilizes multiple indices and one or more SET operations.

Join conditions, depending on the query, may include a logical disjunction operator (e.g. OR), a logical conjunction operator (e.g. AND), or a combination thereof. Existing systems evaluate a logical disjunction (OR) operator using two methods discussed with reference to FIGS. 6 &7. For clarity and convenience, examples of two, existing methods of handling a join operation including a disjunction operator are described, with reference to FIGS. 6 and 7, and compared to the operation of the multi-index disjunction optimization module 312, with reference to FIG. 8, disclosed herein.

Existing systems evaluate a logical conjunction (AND) operator using a method discussed with reference to FIG. 9. For clarity and convenience, an example of an existing method of handling a join operation including a conjunction operator is described, with reference to FIG. 9, and compared to the operation of the multi-index conjunction optimization module 314, with reference to FIG. 10, disclosed herein. Additionally, the handling of a complex join operation (i.e., includes multiple conjunctions, multiple disjunctions or a mixture of one or more conjunctions and one or more disjunctions) is described with reference to FIG. 11.

Example and Discussion of Disjunction Use Cases

As previously mentioned, there may be many query scenarios where a logical disjunction operator (e.g. OR) is used in a join condition that involves columns which have indexes on them. To better understand the operation and benefits of the multi-index disjunction optimization module 312, it may be useful to discuss existing methods for processing a join condition with a disjunction operator. Referring now to FIG. 6, an example query scenario 3 is described. In example query scenario 3, the following query 606 is received:

QUERY 606: SELECT Tab1.Col1, Tab2.Fld2

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col1 = Tab2.Fld1

OR Tab1.Col2= Tab2.Fld2;

For the purpose of discussion, let us assume that the query returns 100 rows. Existing systems may create the query plan 600, which uses a Nested Loop join 624. In a Nested Loop join method, indexes are not used for evaluation of join conditions. Therefore, for each left side row, existing systems read all rows from right side to see if any of the condition is satisfied. Therefore, when a disjunction operator (OR) is involved in the join condition, a query plan using a Nested Loop join is created and executed, which is a costly operation.

More specifically, while there are indexes on Tab2.Fld1 and Tab2.Fld2 columns, existing optimizers cannot use these to evaluate the join condition. Hence, Nested Loop (NL) join method will be used which does table scan on Tab2 to read all rows of Tab2 for each row of Tab1 and evaluate the join condition. Now, assume that table Tab1 has 1000 rows and Tab2 has 100,000 rows, then, for each left side row, 100,000 rows of right-side table will be read. Since, there are 1,000 rows in left-side table, this would result in 100,000,000 rows on which the specified join condition will be applied before returning the result of 100 rows.

Some existing systems have attempted to improve on the processing of queries including a join and a disjunction operator (e.g. query 606). Referring now to FIG. 7, query scenario 4 is described. In query scenario 4, query 706 (identical to query 606 of the previous scenario) is received. However, the existing query optimizer, realizing there are indexes available on columns involved in the disjunction condition, uses a Union operation. The Union operation splits query 706 into two logical queries, 708a and 708b, and performs union of the same. Each logical query 708a and 708b may use the available index. Since, columns, Tab2.Fld1 and Tab2.Fld2 have indexes defined on them, so the original query 706 can be re-written as query 708 below.

QUERY 708: SELECT Tab1.Col1, Tab2.Fld2, Tab2.ROWID

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col1 = Tab2.Fld1

UNION

SELECT Col1, Fld2, Tab2.ROWID

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col2 = Tab2.Fld2;

Although, the method of FIG. 7 is better than the Nested Loop method of FIG. 6 in that it makes use of Indexes, it still has the following de-merits. First, it performs two join operations. Second, since it does two join operations, it must read left-side table of the join operation twice. See Table Scans of Tab1 at 728 and 732 in of the query tree 700. Third, when there are other join conditions apart from the disjunction condition (not shown in this example), then this approach reads the same rows of right-side table redundantly to evaluate the extra condition. We can visualize the specified condition as (Tab1.Col1=Tab2.Fld1 OR Tab1.Col2=Tab2.Fld2) AND (Tab1.Col3=Tab2.Fld3). Where the extra condition is Tab1.Col3=Tab2.Fld3.

Referring now to FIG. 8, the multi-index disjunction optimization module 312 provides a join strategy that uses multiple indexes to evaluate a given join condition with a disjunction operator. With the introduction of the multi-index disjunction optimization module 312 and the join method, described further by way of example with reference to FIG. 8, a query optimizer (not shown) of the DBMS 220 has an option to pick and execute a join method which utilizes more than one index, which was not previously feasible.

Consider query scenario 5, in which query 806 is received (identical to queries 606 and 706).

QUERY 806: SELECT Col1, Fld2

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col1 = Tab2.Fld1

OR Tab1.Col2 = Tab2.Fld2;

In the schema defined at 802 and 804 of query scenario 5 (also in 602 and 604 of query scenario 3 and 702 and 704 of query scenario 4), there are two different indexes on Tab2.Fld1 and Tab2.Fld2 columns. Now, since, there are two different indexes on columns, Tab2.Fld1 and Tab2.Fld2, multi-index disjunction optimization module 312 creates a TID-UNION operator on right side of the join operator. The TID-UNION operator contains two children, one doing an index scan for column Tab2.Fld1 to evaluate first part of the condition, Tab1.Col1=Tab2.Fld1, and another doing an index scan on column, Tab2.Fld2 to evaluate second part of the join condition, Tab1.Col2=Tab2.Fld2. Now, both these index scans return Tuple ID (Row ID) of the rows which matches corresponding conditions. The TID-UNION operator does UNION of these Tuple IDs to remove duplicate Tuple IDs or Tuple IDs which are common in both results of underlying index scans. FIG. 8 illustrates an example embodiment of a query tree 800 generated by the multi-index disjunction optimization module 312 as described above.

Assume that, Tab1 and Tab2 contains rows as mentioned below:

- Tab1 (Col1, Col2, Col3)
  - TAB1-TID1: (10, 20, 30)
  - TAB1-TID2: (100, 20, 30)
- Tab2 (Fld1, Fld2, Fld3)
  - TAB2-TID1: (10, 40, 30)
  - TAB2-TID2: (10, 20, 30)
  - TAB2-TID3: (50, 60, 70)
- TAB2-TID4: (50, 20, 30)

The join condition, Tab1.Col1=Tab2.Fld1 OR Tab1.Col2=Tab2.Fld2, should output the below rows.

- RESULT-ROW1: (10,20,30, 10,40,30)
- RESULT-ROW2: (10,20,30, 10,20,30)
- RESULT-ROW3: (10,20,30, 50,20,30)
- RESULT-ROW4: (100,20,30, 10,20,30)
- RESULT-ROW5: (100,20,30, 50,20,30)

The above output is obtained using the multi-index disjunction optimization module 312 and the query tree 800 as follows. For TAB1-TID1 row of Tab1, when index scan on Tab2.Fld1 takes place, it will results in two rows of Tab2 which are TAB2-TID1 and TAB2-TID2. Similarly, when index scan on Tab2.Fld2, happens for TAB1-TID1, it results in two rows, which are TAB2-TID2 and TAB2-TID4. So, for TAB1-TID1, the Tuple IDs which are produced by index scan of Tab2.Fld1 will be (TAB2-TID1, TAB2-TID2). The Tuple IDs which are produced by index scan of Tab2.Fld2 will be (TAB2-TID2, TAB2-TID4).

Next, TID-UNION operator executes performing a UNION operation on these two results to arrive at below result set for TAB1-TID1 row of Tab1.

(TAB2-TID1, TAB2-TID2, TAB2-TID4)

The index scan on Tab2Fld1 will result in no rows and index scan on Tab2.Fld2 will result in 2 rows (i.e. TAB2-TID2 and TAB2-TID4). So, the result set for the second row TAB1-TID2 of Tab 1 would be union of “Empty set” with (TAB2-TID2, TAB2-TID4) which is (TAB2-TID2, TAB2-TID4).

When the results for the two rows of Tab1 are combined, then the result set would be equal to expected result. That is,

Output:

- RESULT-ROW1: (10,20,30, 10,40,30)
- RESULT-ROW2: (10,20,30, 10,20,30)
- RESULT-ROW3: (10,20,30, 50,20,30)
- RESULT-ROW4: (100,20,30, 10,20,30)
- RESULT-ROW5: (100,20,30, 50,20,30)

As discussed above, if we assume that table Tab1 has 1,000 rows and Tab2 has 100,000 rows, then, when query tree 600 of FIG. 6 is executed, for each left side row, 100,000 rows of right-side table will be read. Since, there are 1,000 rows in left-side table, this would result in 100,000,000 rows on which the specified join condition is applied before returning the result of 100 rows. By contrast, if we again assume that table Tab1 has 1000 rows and Tab2 has 100,000 rows, then, when query tree 700 of FIG. 7 is executed, the number of physical reads drops from 100,000,000 to approximately 200,800. However, if we again assume that table Tab1 has 1000 rows and Tab2 has 100,000 rows, then, when query tree 800 of FIG. 8 is executed, the number of physical reads drops from to approximately 100,400, thereby improving the operation of one or more of the database and hardware associated therewith, and decreasing the time needed to provide a result.

Example and Discussion of Conjunction Use Case

There may be many query scenarios where a logical conjunction operator (AND) is used in a join condition that involves columns which have indexes on them. To better understand the operation and benefits of the multi-index conjunction optimization module 314, it may be useful to discuss existing methods for processing a join condition with a conjunction operator. Referring now to FIG. 9, an example query scenario 6 is described. In example query scenario 6, the following query 906 is received:

QUERY 906: SELECT Tab1.Col1, Tab2.Fld2

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col1 = Tab2.Fld1

AND Tab1.Col2 = Tab2.Fld2;

For the purposes of discussion, assume the above query produces 10 rows. Though, there are two separate indexes on columns, Tab2.Fld1 and Tab2.Fld2, existing systems use only one of the indexes. Assume that, index on Tab2.Fld2 is selected, then the other part of the condition, i.e., Tab1.col1=Tab2.Fld1, is evaluated after the join processing. See query tree 900 of FIG. 9.

If we assume that tables Tab1 and Tab2 have 10,000 rows each, and assume that, irrespective of which index is selected among indexes on columns, Tab2.Fld1 or Tab2.Fld2, on an average they result in 100 rows from right-side table for each left side row, then the ANL join 924 produces 1,000,000 rows. Second condition will be applied 922 on these 1,000,000 rows to produce the result of 10 rows at 920. Therefore, such an approach reads 1,000,000 rows though the result consists of just 10 rows.

Historically, query optimizers are limited to selecting a single index for use in evaluation of a join condition. However, the multi-index conjunction optimization module 314 is able to use multiple indexes to evaluate the join condition in a more efficient manner.

Referring now to FIG. 10, query 1006 is received (which is identical to query 906 of FIG. 9).

QUERY 1006: SELECT Tab1.Col1, Tab2.Fld2

FROM Tab1 INNER JOIN Tab2 ON Tab1.Col1 = Tab2.Fld1

AND Tab1.Col2 = Tab2.Fld2;

Note that there are two different indexes available on columns Tab2.Fld1 and Tab2.Fld2, multi-index conjunction optimization module 314 uses “Multi-Index Augmented Nested Loop” join method which creates a TID-INTERSECTION 1026 operator on the right side of the join operator 1022 in the query tree 1000. In the query tree 1000, the TID-INTERSECTION 1026 operator contains two children, one 1028 doing an index scan for column Tab2.Fld1 to evaluate part of the join condition, Tab1.Col1=Tab2.Fld1, and another 1030 doing an index scan on column, Tab2.Fld2 to evaluate second part of the join condition, Tab1.Col2-Tab2.Fld2. Both these index scans 1028 & 1030 return Tuple IDs (RowID) of the rows which matches corresponding conditions. TID-INTERSECTION operator does INTERSECTION of these Tuple IDs to make sure that tuples which match both the conditions are obtained. Rows with these Tuple IDs are then read for the further processing.

This means the join method only reads 100 rows which satisfy complete join condition, contrast to existing methods which reads a greater number of rows. For example, as discussed above, if we assume that tables Tab1 and tab 2 each have 10,000 rows, then, when query tree 900 of FIG. 9 is executed, for each left side row, 100 rows of right-side table will be read. Since, there are 10,000 rows in left-side table, this would result in 1,000,000 rows on which the specified join condition is applied before returning the result of 10 rows. By contrast, if we again assume that tables Tab1 and tab 2 each have 10,000 rows, then, when query tree 1000 of FIG. 10 is executed, the number of physical reads drops from 1,000,000 to approximately 100 rows which satisfy the join condition, thereby improving the operation of one or more of the database and hardware associated therewith, and decreasing the time needed to provide a result.

Example and Discussion of Complex Join Condition Use Case

In the preceding portions of the description, for clarity and convenience, the query optimization module 302 and its subcomponents 312 & 314 have been discussed with regard to simple join conditions including a single disjunction or single conjunction operation. However, it should be recognized that Multi-Index Augmented Nested Loop method discussed above with reference to FIGS. 1-3, 8 and 10 is not limited to such simple join queries. Rather, it should be recognized that the systems and methods herein may be used for complex” queries having multiple disjunctions or multiple conjunctions or combination of both. For clarity and convenience, please consider Query scenario 8 (1102) and FIG. 11, which includes:

QUERY 1106: SELECT Col1, Fld2

FROM Tab1 INNER JOIN Tab2 ON

(Tab1.Col1 = Tab2.Fld2 AND Tab1.Col2 = Tab2.Fld3)

OR

(Tab1.Col2 = Tab2.Fld1 AND Tab1.Col3 = Tab2.Fld2);

Note that, above join condition has combination of a disjunction and two conjunctions. FIG. 11 shows a query tree 1100 generated by the query optimizer 302 and the subcomponents thereof 312 and 314. The multi-index disjunction optimization module 312 and the multi-index conjunction optimization module 314 cooperate to generate the query tree 1100. The nodes and relative positions in the query tree 1100 are determined based on the join operation and junction (e.g. conjunction or disjunction) operations therein. In the illustrated embodiment of FIG. 11, the multi-index conjunction optimization module 314 adds a node for an index scan of Tab2 using Fld1 as the index key 1132 and a node for an index scan of Tab2 using Fld2 as the index key 1134 based on the conditions Tab1.Col2=Tab2.Fld1 and Tab1.Col3=Tab2.Fld2, respectively. The multi-index conjunction optimization module 314 adds a node 1130 for the set operation (TID-Intersection, as shown, because Tab1.Col2=Tab2.Fld1 and Tab1.Col3=Tab2.Fld2 are related by an “AND” in Query 1106). The multi-index disjunction optimization module 312 adds a node 1126 for the set operation (TID-Union, as shown, because of the “OR” in Query 1106), where the TID-Intersection node 1130 and Index scan node 1128 of Tab2 using Fld2 and Fld3 as index keys are child nodes of the TID-Union node 1126. The query optimization node 302 adds a Multi-Index Augmented Nested Loop node 1122 to the query tree 1100, where the TID-Union node 1126 and the Table scan node 1124 are child nodes of the Multi-Index Augmented Nested Loop join node 1122. The query optimization node 302 adds a node 1120 to the query tree 1100 for providing the results of the query.

Example and Discussion of Dynamic Index Use Cases

Referring now to FIG. 12, a query scenario is described in which an index was not created on a participating column (i.e. Fld2 of Tab2) in the query 1206. However, the multi-index disjunction optimization module 312 dynamically indexes 1230 Fld 2 of Tab2 and thereafter operates similar to query scenario 5 of FIG. 8.

While creation of the dynamic index does come at a computational price, in most practical applications that tables involved exceed the threshold at which the cost of creating the dynamic index, or indices, is less than the cost of having a Nested Loop and reverting to tables scanning.

It should be recognized that creation of a dynamic index is not limited to disjunctive use cases. While query scenario 9 of FIG. 12 is disjunctive, it was merely selected for illustration purposes. A dynamic index may be created and used in conjunctive, or mixed/complex use cases; however, for clarity and simplicity, only the disjunctive use case is illustrated and discussed in detail herein with reference to FIG. 12.

It should be recognized that, while the examples discussed herein focus on queries that include two or three conditions, the Multi-Index Augmented Nested Loop method discussed herein may accommodate any number of conditions and is not limited to a maximum of 2 or 3 conditions. For example, based on the description herein it should be recognized how the Multi-Index Augmented Nested Loop method discussed herein would handle a query such as:

SELECT Col1, Fld2

FROM Tab1 INNER JOIN Tab2 ON

(Tab1.Col1 = Tab2.Fld1 OR Tab1.Col2 = Tab2.Fld2 OR

Tab1.Col3 = Tab2.Fld3);

Or the query:

SELECT Col1, Fld2

FROM Tab1 INNER JOIN Tab2 ON

(Tab1.Col1 = Tab2.Fld1 AND Tab1.Col2 = Tab2.Fld2 AND

Tab1.Col3 = Tab2.Fld3);

Or the query:

SELECT Col1, Fld2

FROM Tab1 INNER JOIN Tab2 ON

(Tab1.Col1 = Tab2.Fld2 OR Tab1.Col2 = Tab2.Fld2)

AND

(Tab1.Col3 = Tab2.Fld3 OR Tab1.Col4 = Tab2.Fld4)

OR

(Tab1.Col4 = Tab2.Fld4 AND Tab1.Col5 = Tab2.Fld5);