Star/join query optimization

• US 5,960,428 A
• Filed: 08/28/1997
• Issued: 09/28/1999
• Est. Priority Date: 08/28/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lohman, Guy Maring, Pirahesh, Mir Hamid, Simmen, David Everett, Lindsay, Bruce Gilbert, Shekita, Eugene Jon, Urata, Monica Sachiye
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/919,739
• Time in Patent Office: 761 Days
• Field of Search: 707/2, 707/4, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Unwieldy star/join queries are performed more efficiently using a filtered fact table. Suitable queries include star/join queries with a large fact table joined with multiple subsidiary dimension tables, where indices exist over fact table join columns. The query is analyzed to prepare a query plan for the dimension table accesses. This plan is supplemented by adding nested loop join operations, where the inner table is a dimension table plan and the outer table is an index scan performed over a fact table index of the join column with the dimension table. The plan is also supplemented by filtering records resulting from the nested loop joins using a sequence of dynamic bit vectors, ultimately yielding a list of probable fact table records. The plan is further supplemented by fetching these records to construct a distilled fact which is used, instead of the large original table, to execute the query in considerably less time. If desired, the supplemented query plan and other competing approaches may studied to provide cost estimates, with the least costly approach being actually implemented.

Claims

1. A method for planning a database query, comprising:

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

forming a first query plan for access of each dimension table to identify resultant rows of each dimension table;

forming a second query plan for access of the fact table, comprising the steps of;

for the resultant rows of each dimension table, planning a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs; and

planning a fetch of all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

forming a final query plan comprising planning execution of the query using the distilled fact table.

2. The method of claim 1, further comprising:

predicting an execution cost required to perform the first, second, and final query plans.

3. The method of claim 2, further comprising:

determining whether the cost satisfies a predetermined criteria, and if so, carrying out the planned first, second, and final queries.

4. The method of claim 3, further comprising:

predicting an execution cost to perform one or more alternate query plans;

wherein the predetermined criteria comprises the cost of the first, second, and final query plans being less than each of the alternate query plans.

5. The method of claim 1, further comprising:

executing the first, second, and final query plans.

6. The method of claim 1, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

7. The method of claim 6, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if so excluding said dimension tables from the first and second query plans.

8. The method of claims 6, the analyzing step comprising:

analyzing the query to determine whether the join between any dimension table and the fact table reduces cardinality of the fact table, and if not, excluding said dimension tables from the first and second query plans.

9. The method of claim 1, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

10. The method of claim 1, the receiving further comprising:

identifying within the star/join query a snowflake join comprising a join of a first one of the dimension tables with another table that is neither the fact table nor one of the dimension tables; and

the forming of the first query plan including the snowflake join.

11. The method of claim 10, the forming of the first query plan only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

12. The method of claim 1, the first query plan being constructed to produce distinct join column values.

13. The method of claim 1, the first query plan suppressing columns of the dimension tables other than the join columns.

14. The method of claim 1, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of table.

15. The method of claim 1, the forming of the second query plan further comprising:

estimating a cardinality of each set of resultant RIDs of each dimension table join to the fact table index; and

the applying of stage comparative ridge filtering being performed in order from least to greatest number of the estimated cardinality.

16. A method for performing a database query, comprising:

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

performing access of each dimension table according to the star/join query to identify resultant rows of each dimension table; and

for the resultant rows of each dimension table, performing a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs;

fetching all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

executing the star/join query using the distilled fact table.

17. The method of claim 16, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

18. The method of claim 17, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if so, excluding said dimension tables from the performing access, performing the fact table index scan, applying, and fetching steps.

19. The method of claim 16, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

20. The method of claim 16, the receiving further comprising:

identifying within the star/join query a snowflake join comprising, a join of a first one of the dimension tables with another table that is neither the fact table nor one of the dimension tables; and

the performing access of each dimension table including performing each snowflake join.

21. The method of claim 20, the performing access of each dimension table only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

22. The method of claim 16, the access of each dimension table being executed so as to produce distinct join column values.

23. The method of claim 16, the access of each dimension table suppressing columns of the dimension tables other than the join columns.

24. The method of claim 16, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of the fact table.

25. The method of claim 16, the applying of staged comparative RID filtering employing a set of one or more dynamic bit vectors for each dimension table, the filtering being performed in order from smallest to largest of the dynamic bit vectors.

26. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for planning a database query, said method comprising:

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

forming a first query plan for access of each dimension table to identify resultant rows of each dimension table;

forming a second query plan for access of the fact table, comprising the steps of;

for the resultant rows of each dimension table, planning a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs; and

planning a fetch of all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

forming a final query plan comprising planning execution of the query using the distilled fact table.

27. The medium of claim 26, further comprising:

predicting an execution cost required to perform the first, second, and final query plans.

28. The medium of claim 27, further comprising:

determining whether the cost satisfies a predetermined criteria, and if so, carrying out the planned first, second, and final queries.

29. The medium of claim 28, further comprising:

predicting an execution cost to perform one or more alternate query plans;

wherein the predetermined criteria comprises the cost of the first, second, and final query plans being less than each of the alternate query plans.

30. The medium of claim 26, further comprising:

executing the first, second, and final query plans.

31. The medium of claim 26, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

32. The medium of claim 31, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if excluding said dimension tables from the first and second query plans.

33. The medium of claims 31, the analyzing step comprising:

analyzing the query to determine whether the join between any dimension table and the fact table reduces cardinality of the fact table, and if not, excluding said dimension tables from the first and second query plans.

34. The medium of claim 26, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

35. The medium of claim 26, the receiving further comprising:

identifying within the star/join query a snowflake join comprising a join of a first one of the dimension tables with another table that is neither the fact table nor one of the dimension tables; and

the forming of the first query plan including the snowflake join.

36. The medium of claim 35, the forming of the first query plan only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

37. The medium of claim 26, the first query plan being constructed to produce distinct join column values.

38. The medium of claim 26, the first query plan suppressing columns of the dimension tables other than the join columns.

39. The medium of claim 26, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of the fact table.

40. The medium of claim 26, the forming of the second query plan further comprising:

estimating a cardinality of each set of resultant RIDs of each dimension table join to the fact table index; and

the applying of stage comparative ridge filtering being performed in order from least to greatest number of the estimated cardinality.

41. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a database query, said method comprising:

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

performing access of each dimension table according to the star/join query to identify resultant rows of each dimension table; and

for the resultant rows of each dimension table, performing a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs;

fetching all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

executing the star/join query using the distilled fact table.

42. The medium of claim 41, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

43. The medium of claim 42, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if so excluding said dimension tables from the performing access, performing the fact table index scan, applying, and fetching steps.

44. The medium of claim 41, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

45. The medium of claim 41, the receiving further comprising:

identifying within the star/join query a snowflake join comprising a join of a first one of the dimension tables with another table that is neither the fact table nor one of the dimension tables; and

the performing access of each dimension table including performing each snowflake join.

46. The medium of claim 45, the performing access of each dimension table only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

47. The medium of claim 41, the access of each dimension table being executed so as to produce distinct join column values.

48. The medium of claim 41, the access of each dimension table suppressing columns of the dimension tables other than the join columns.

49. The medium of claim 41, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of the fact table.

50. The medium of claim 41, the applying of staged comparative RID filtering employing a set of one or more dynamic bit vectors for each dimension table, the filtering being performed in order from smallest to largest of the dynamic bit vectors.

51. A digital data processing apparatus, comprising:

a storage unit containing a program of machine-readable instructions; and

a processing unit coupled to the storage unit and being programmed to perform steps to evaluate a query by executing the machine-readable instructions, said steps comprising;

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

forming a first query plan for access of each dimension table to identify resultant rows of each dimension table;

forming a second query plan for access of the fact table, comprising the steps of;

for the resultant rows of each dimension table, planning a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs; and

planning a fetch of all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

forming a final query plan comprising planning execution of the query using the distilled fact table.

52. The apparatus of claim 51, further comprising:

predicting an execution cost required to perform the first, second, and final query plans.

53. The apparatus of claim 52, further comprising:

determining whether the cost satisfies a predetermined criteria, and if so, carrying out the planned first, second, and final queries.

54. The apparatus of claim 53, further comprising:

predicting an execution cost to perform one or more alternate query plans;

wherein the predetermined criteria comprises the cost of the first, second, and final query plans being less than each of the alternate query plans.

55. The apparatus of claim 51, further comprising:

executing the first, second, and final query plans.

56. The apparatus of claim 51, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

57. The apparatus of claim 56, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if so, excluding said dimension tables from the first and second query plans.

58. The apparatus of claims 56, the analyzing step comprising:

analyzing the query to determine whether the join between any dimension table and the fact table reduces cardinality of the fact table, and if not, excluding said dimension tables from the first and second query plans.

59. The apparatus of claim 51, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

60. The apparatus of claim 51, the receiving further comprising:

identifying within the star/join query a snowflake join comprising a join of a first one of the dimension tables with another table that is neither th. fact table nor one of the dimension tables; and

the forming of the first query plan including the snowflake join.

61. The apparatus of claim 60, the forming of the first query plan only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

62. The apparatus of claim 52, the first query plan being constructed to produce distinct join column values.

63. The apparatus of claim 52, the first query plan suppressing columns of the dimension tables other than the join columns.

64. The apparatus of claim 52, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of the fact table.

65. The apparatus of claim 51, the forming of the second query plan further comprising:

estimating a cardinality of each set of resultant RIDs of each dimension table join to the fact table index; and

the applying of stage comparative ridge filtering being performed in order from least to greatest number of the estimated cardinality.

66. A digital data processing apparatus, comprising:

a storage unit containing a program of machine-readable instructions; and

a processing unit coupled to the storage unit and being programed to perform a database a query by executing the machine-readable instructions, said steps comprising;

receiving a star/join query joining a fact table with multiple dimension tables, said fact table including a plurality of rows each row identified by a row identification code (RID);

performing access of each dimension table according to the star/join query to identify resultant rows of each dimension table; and

for the resultant rows of each dimension table, performing a fact table index scan over join columns of that dimension table to produce a set of resultant RIDs, said fact table having indices for join columns with each of the dimension tables;

applying staged comparative RID filtering to each dimension table'"'"'s set of resultant RIDs to produce a set of filtered RIDs;

fetching all fact table rows corresponding to the set of filtered RIDs to produce a distilled fact table; and

executing the star/join query using the distilled fact table.

67. The apparatus of claim 66, the receiving step comprising:

receiving a query; and

analyzing the query to determine whether the query comprises a star/join query joining a fact table with multiple dimension tables, and if not, aborting further operations.

68. The apparatus of claim 67, the analyzing step comprising:

analyzing the query to determine whether the fact table lacks indices for join columns with any of the dimension tables, and if so, excluding said dimension tables from the performing access, performing the fact table index scan, applying, and fetching steps.

69. The apparatus of claim 66, further comprising:

analyzing the query to determine whether the fact table includes indices for join columns with each of the dimension tables, and if not, supplementing the second query plan to include planning generation of said indices.

70. The apparatus of claim 66, the receiving further comprising:

identifying within the star/join query a snowflake join comprising a join of a first one of the dimension tables with another table that is neither the fact table nor one of the dimension tables; and

the performing access of each dimension table including performing each snowflake join.

71. The apparatus of claim 70, the performing access of each dimension table only including the snowflake join if the snowflake join reduces cardinality of the first dimension table.

72. The apparatus of claim 66, the access of each dimension table being executed so as to produce distinct join column values.

73. The apparatus of claim 66, the access of each dimension table suppressing columns of the dimension tables other than the join columns.

74. The apparatus of claim 66, the fact table index scan of each dimension table comprising a nested loop join operation performed upon an inner table and an outer table, the outer table comprising the plan for executing query of the dimension table, the inner table comprising an index over one or more join columns of the fact table.

75. The apparatus of claim 66, the applying of staged comparative RID filtering employing a set of one or more dynamic bit vectors for each dimension table, the filtering being performed in order from smallest to largest of the dynamic bit vectors.