Optimizing a query using a non-covering join index

• US 6,643,636 B1
• Filed: 06/05/2001
• Issued: 11/04/2003
• Est. Priority Date: 06/05/2001
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Au, Grace Kwan-On, Sinclair, Paul Laurence, Ghazal, Ahmad Said
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/874,804
• Time in Patent Office: 882 Days
• Field of Search: 707/2, 707/3, 707/4, 707/103.R, 707/8
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method, database system and computer program are disclosed for optimizing a SQL query, in which the SQL query includes a WHERE clause and a FROM clause. An evaluation is done to determine whether a non-covering join index partially but not completely covers the query. If it does, the join index is added to the FROM clause of the query without removing the partially covered base tables and the WHERE clause of the query is modified by: (1) mapping a query condition to the join index for its partially covered base tables; and (2) adding a join back condition from the join index to a base table from which the join index was formed.

Claims

1. A method for optimizing a SQL query, in which the SQL query includes a WHERE clause and a FROM clause, where the method includes

evaluating whether a non-covering join index partially but not completely covers the query, and if it does

adding the join index to the FROM clause of the query without removing the partially covered base tables;

modifying the WHERE clause of the query by;

(1) mapping a query condition to the join index for its partially covered base tables; and

(2) adding a join back condition from the join index to a base table from which the join index was formed.

2. The method of claim 1 further including

evaluating the cost of a plurality of different join paths to implement the query, the difference in at least some of the join paths being at least partially attributed to an order of the join back condition in the respective join paths; and

selecting the least costly of the plurality of different join paths.

3. The method of claim 1, in which the non-covering join index is recognized to have a unique column that can be used to join back to a base table of the join index efficiently, and adding the join back condition includes

adding a predicate to the WHERE clause which tests for equality between the unique column of the base table and the corresponding unique column included in the join index.

4. The method of claim 3 in which the unique column is a rowid column.

5. The method of claim 3 in which the unique column is a primary index column.

6. The method of claim 3 in which the unique column is a secondary index column.

7. The method of claim 1, in which (a) the FROM clause of the query specifies one or more tables, including one or more base tables, (b) the entire query references a entire-query set of columns from the one or more base tables of the join index, (c) the WHERE clause of the query references a whereclause set of columns from the one or more base tables of the join index, (d) the join index is defined by selecting columns from the one or more base tables, the method further includes

recognizing that the non-covering join index provides partial but not complete coverage by determining that the join index does not contain all of the entire-query set of columns;

and determining that the join index contains a subset of the where-clause set of column.

8. The method of claim 7 where recognizing that the non-covering join index provides partial but not complete coverage includes

determining that the join index includes a primary key for each of the one or more base tables from which the join index was formed that are not completely covered.

9. The method of claim 8 where the primary key included in the join index for at least one of the base tables is a rowid.

10. The method of claim 8 where the primary key included in the join index for at least one of the base tables is a unique primary index.

11. The method of claim 8 where the primary key included in the join index for at least one of the base tables is a unique secondary index.

12. A database system for accessing a database, the database system including

a massively parallel processing system including

one or more nodes;

a plurality of CPUs, each of the one or more nodes providing access to one or more CPUs;

a plurality of virtual processes each of the one or more CPUs providing access to one or more processes;

each process configured to manage data stored in one of a plurality of data-storage facilities;

an optimizer for optimizing a plan for executing a query, the query including a FROM clause and a WHERE clause, the optimizer including

a process for evaluating whether a non-covering join index partially but not completely covers the query, and if it does,

adding the join index to the FROM clause of the query without removing the partially covered base tables;

modifying the WHERE clause of the query by;

 

(1) mapping a query condition to the join index for its partially covered base tables; and

 

(2) adding a join back condition from the join index to a base table from which the join index was formed.

13. The database system of claim 12 where the optimizer further includes

a process for evaluating the cost of a plurality of different join paths to implement the query, the difference in at least some of the join paths being at least partially attributed to an order of the join back condition in the respective join paths; and

a process for selecting the least costly of the plurality of different join paths.

14. The database system of claim 12, in which the non-covering join index is recognized to have a unique column that can be used to join back to a base table of the join index efficiently, and adding the join back condition includes

adding a predicate to the WHERE clause which tests for equality between the unique column of the base table and the corresponding unique column included in the join index.

15. The database system of claim 14 in which the unique column is a rowid column.

16. The database system of claim 14 in which the unique column is a primary index column.

17. The database system of claim 14 in which the unique column is a secondary index column.

18. The database system of claim 12, in which (a) the FROM clause of the query specifies one or more tables, including one or more base tables, (b) the entire query references a entire-query set of columns from the one or more base tables of the join index, (c) the WHERE clause of the query references a where-clause set of columns from the one or more base tables of the join index, (d) the join index is defined by selecting columns from the one or more base tables, the optimizer further includes

a process for recognizing that the non-covering join index provides partial but not complete coverage by

determining that the join index does not contain all of the entire-query set of columns;

determining that the join index contains a subset of the where-clause set of column.

19. The database system of claim 18 where the process for recognizing that the non-covering join index provides partial but not complete coverage includes

determining that the join index includes a primary key for each of the one or more base tables from which the join index was formed that are not completely covered.

20. The database system of claim 19 where the primary key included in the join index for at least one of the base tables is a rowid.

21. The database system of claim 19 where the primary key included in the join index for at least one of the base tables is a unique primary index.

22. The database system of claim 19 where the primary key included in the join index for at least one of the base tables is a unique secondary index.

23. A computer program, stored on a tangible storage medium, for use in optimizing a query including a FROM clause and a WHERE clause, the program including executable instructions that cause a computer to

evaluate whether a non-covering join index partially but not completely covers the query, and if it does

add the join index to the FROM clause of the query without removing the partially covered base tables;

modify the WHERE clause of the query by;

(1) mapping a query condition to the join index for its partially covered base tables; and

(2) adding a join back condition from the join index to a base table from which the join index was formed.

24. The computer program of claim 23 further including executable instructions that cause a computer to

evaluate the cost of a plurality of different join paths to implement the query, the difference in at least some of the join paths being at least partially attributed to an order of the join back condition in the respective join paths; and

select the least costly of the plurality of different join paths.

25. The computer program of claim 23, in which the non-covering join index is recognized to have a unique column that can be used to join back to a base table of the join index efficiently, and, when adding the join back condition, the computer

adds a predicate to the WHERE clause which tests for equality between the unique column of the base table and the corresponding unique column included in the join index.

26. The computer program of claim 25 in which the unique column is a rowid column.

27. The computer program of claim 25 in which the unique column is a primary index column.

28. The computer program of claim 25 in which the unique column is a secondary index column.

29. The computer program of claim 23, in which (a) the FROM clause of the query specifies one or more tables, including one or more base tables, (b) the entire query references a entire-query set of columns from the one or more base tables of the join index, (c) the WHERE clause of the query references a where-clause set of columns from the one or more base tables of the join index, (d) the join index is defined by selecting columns from the one or more base tables, the computer program further includes executable instructions that cause the computer to

recognize that the non-covering join index provides partial but not complete coverage by

determining that the join index does not contain all of the entire-query set of columns;

determining that the join index contains a subset of the where-clause set of column.

30. The computer program of claim 29 where, when recognizing that the non-covering join index provides partial but not complete coverage, the computer

determines that the join index includes a primary key for each of the one or more base tables from which the join index was formed that are not completely covered.

31. The computer program of claim 30 where the primary key included in the join index for at least one of the base tables is a rowid.

32. The computer program of claim 30 where the primary key included in the join index for at least one of the base tables is a unique primary index.

33. The computer program of claim 30 where the primary key included in the join index for at least one of the base tables is a unique secondary index.