Processing cross-table non-Boolean term conditions in database queries

• US 20060173833A1
• Filed: 01/28/2005
• Published: 08/03/2006
• Est. Priority Date: 01/28/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Purcell, Terence Patrick, Beavin, Thomas Abel
• Granted Patent: US 7,499,917 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Processing non-Boolean term conditions in database queries. A query that is a request for data in a database is received and includes at least one uneven non-Boolean term condition that spans multiple tables in the database. The non-Boolean term condition is split into separate portions, each of the portions providing a Boolean term that can be satisfied by accessing one table in the database. The separate portions are executed independently to find at least one data result in the database that satisfies the Boolean term of each separate portion, and the data result from each separate portion are combined into a final result that satisfies the query.

Claims

1. A method for searching for data in a database, the method comprising:

receiving a query that is a request for data in the database, the query including at least one uneven non-Boolean term condition that spans multiple tables in the database;

splitting the at least one non-Boolean term condition into separate portions, each of the separate portions providing a Boolean term that can be satisfied by accessing one table in the database;

executing the separate portions independently to find at least one data result in the database that satisfies the Boolean term of each separate portion; and

combining the data result from each separate portion into a final result that satisfies the query.

2. The method of claim 1 wherein the at least one uneven non-Boolean term condition includes an OR condition of the query, where each predicate of the OR condition is provided to a different one of the separate portions.

3. The method of claim 1 wherein the data results include rows in a table found from the execution of the separate portions, and wherein rows duplicated between the data results from the separate portions are removed from one of the data results.

4. The method of claim 1 further comprising rewriting the query before splitting the non-Boolean term condition into separate portions, such that the number of separate portions needed to be executed is reduced.

5. The method of claim 1 wherein the separate portions are separate tasks, each task being executed independently at runtime to find the data results for the Boolean term associated with that task, and wherein a duplication of table accesses is minimized.

6. The method of claim 5 wherein the non-Boolean term condition includes two predicates, each predicate referencing a different table, and wherein a bridge table is identified to allow the data results from each separate portion to be combined into a final result.

7. The method of claim 6 wherein the bridge table is another table that is not referenced by the at least one non-Boolean term condition.

8. The method of claim 6 wherein the bridge table is a duplicated one of the tables that is referenced by one of the separate tasks, the duplicated table being used in the separate task.

9. The method of claim 5 wherein record IDs of an index to the database are found as data results and are combined together, and further comprising accessing and joining rows of different tables in the database pointed to by the record IDs to provide the final results table.

10. The method of claim 5 wherein the query is rewritten in disjunctive normal form before splitting the at least one non-Boolean term condition into separate tasks.

11. The method of claim 1 wherein the separate portions are separate blocks of the query that are split by rewriting the query so that the separate blocks are on different sides of a UNION-type statement, such that the separate blocks are executed independently.

12. A computer readable medium including program instructions to be implemented by a computer, the program instructions for searching for data in a database, the program instructions implementing steps comprising:

receiving a query that is a request for data in the database, the query including at least one uneven non-Boolean term condition that spans multiple tables in the database;

splitting the at least one non-Boolean term condition into separate portions, each of the separate portions providing a Boolean term that can be satisfied by accessing one table in the database;

executing the separate portions independently to find at least one data result in the database that satisfies the Boolean term of each separate portion; and

combining the data result from each separate portion into a final result that satisfies the query.

13. The computer readable medium of claim 12 wherein the at least one uneven non-Boolean term condition includes an OR condition of the query, where each predicate of the OR condition is provided to a different one of the separate portions.

14. The computer readable medium of claim 12 wherein the data results include rows in a table found from the execution of the separate portions, and wherein rows duplicated between the data results from the separate portions are removed from one of the data results.

15. The computer readable medium of claim 12 further comprising rewriting the query before splitting the non-Boolean term conditions into separate portions, such that the number of separate portions needed to be executed is reduced.

16. The computer readable medium of claim 12 wherein the separate portions are separate tasks, each task being executed independently at runtime to find the data results for the Boolean term associated with that task, and wherein a duplication of table accesses is minimized.

17. The computer readable medium of claim 16 wherein the non-Boolean term condition includes two predicates, each predicate referencing a different table, and wherein a bridge table is identified to allow the data results from each separate portion to be combined into a final result.

18. The computer readable medium of claim 16 wherein record IDs of an index to the database are found as data results and are combined together, and further comprising accessing and joining rows of different tables in the database pointed to by the record IDs to provide the final results table.

19. The computer readable medium of claim 12 wherein the separate portions are separate blocks of the query that are split by rewriting the query so that the separate blocks are on different sides of a UNION-type statement, such that the separate blocks are executed independently.

20. A system for searching for data in a database, the system comprising:

a storage device for storing data in a database, the data being referenced within a plurality of tables; and

a processor coupled to the storage device, the processor operative to receive a query that is a request for data in the database, the query including at least one uneven non-Boolean term condition that spans multiple tables in the database, wherein the processor is operative to split the at least one non-Boolean term condition into separate portions, each of the separate portions providing a Boolean term that can be satisfied by accessing one table in the database, and wherein the processor is operative to process the query by executing the separate portions independently to find at least one data result in the database that satisfies the Boolean term of each separate portion, wherein the data results from each separate portion are combined into a final result that satisfies the query.

21. The method of claim 20 wherein the separate portions are separate tasks, each task being executed independently to find the data results for the Boolean term associated with that task, and wherein a duplication of table accesses is minimized.