EXECUTION COST REDUCTION OF SAMPLED QUERIES IN A DATABASE

• US 20070233648A1
• Filed: 03/30/2006
• Published: 10/04/2007
• Est. Priority Date: 03/30/2006
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: ZUZARTE, Paul
• Granted Patent: US 7,689,553 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method, system and computer program product for reducing the execution cost of sampled queries of tables in a database. A subset of entries comprising row identifiers or key values based on an input query of data in the tables of the database is generated. A sampling predicate to reduce the number of entries in the subset is generated. The sampling predicate is applied to the subset to reduce the number of entries in the subset. The data in the database corresponding to the reduced subset is retrieved from the database.

Claims

1. A method of establishing a sampled query of tables in a database, the method comprising the steps of:

a) generating a subset of entries based on a query for data from the tables, the entries representing elements of an index of a larger table from the tables of the query;

b) generating a sampling predicate to reduce the number of entries in the subset, the sampling predicate being obtained from the query;

c) applying the sampling predicate to the subset to reduce the number of entries in the subset; and

d) generating a search of the reduced subset based on the query.

2. The method of claim 1, wherein in step a) the entries of the subset are selected from the group consisting of row identifiers of the index and key values of the index of the larger table.

3. The method of claim 1, wherein step b) comprises:

generating the sampling predicate using Bernoulli sampling.

4. The method of claim 1, wherein step b) comprises:

generating the sampling predicate using a random generator function.

5. The method of claim 1, wherein step a) comprises:

determining those tables in the database having a referential integrity relationship, wherein the determined tables are used to generate the subset.

6. The method of claim 1, wherein step b) comprises:

generating the sampling predicate for selecting entries of the subset based on a sampling rate of the subset.

7. The method of claim 1, wherein step b) comprises:

generating the sampling predicate for selecting between about 5% and about 25% of the entries of the subset for the sampled query.

8. The method of claim 1, wherein step a) comprises:

generating the subset based on a bit-mapped star join of at least two dimension tables and indexes corresponding to the dimension key column of a fact table of the database.

9. The method of claim 1, wherein step a) comprises:

generating the subset based on a composite index of a fact table in the database used in a Cartesian star join of at least two dimension tables, the at least two dimension tables being joined to the fact table on the composite index containing the columns corresponding to the dimension keys.

10. The method of claim 1, wherein step a) comprises:

generating the subset based on an index of a large table of the database used in a general query with conditions.

11. The method of claim 1, wherein step a) comprises:

generating the subset based on a query with aggregation and grouping on a composite join key.

12. For a database management system (DBMS) operatively coupled to a data processing system, a computer program product comprising a computer readable medium containing computer executable code for performing a sampled query of tables in a database, the computer program product comprising:

a) code for generating a subset of entries based on a query for data from the tables, the entries representing elements of an index of a larger table from the tables of the query;

b) code for generating a sampling predicate to reduce the number of entries in the subset, the sampling predicate being obtained from the query;

c) code for applying the sampling predicate to the subset to reduce the number of entries in the subset; and

d) code for generating a search of the reduced subset based on the query.

13. The computer program product of claim 12, wherein code for generating the subset of entries the entries of the subset are selected from the group consisting of row identifiers of the index and key values of the index of the larger table.

14. The computer program product of claim 12, wherein code for generating the sampling predicate comprises:

code for generating the sampling predicate using Bernoulli sampling.

15. The computer program product of claim 12, wherein code for generating the sampling predicate comprises:

code for generating the sampling predicate using a random generator function.

16. The computer program product of claim 12, wherein code for generating the subset of entries comprises:

code for determining those tables in the database having a referential integrity relationship, wherein the determined tables are used to generate the subset.

17. The computer program product of claim 12, wherein code for generating the sampling predicate comprises:

code for generating the sampling predicate for selecting entries of the subset based on a sampling rate of the subset.

18. The computer program product of claim 12, wherein code for generating the sampling predicate comprises:

code for generating the sampling predicate for selecting between about 5% and about 25% of the entries in the subset for the sampled query.

19. The computer program product of claim 12, wherein code for generating the subset of entries comprises:

code for generating the subset based on a bit-mapped star join of at least a dimension table and a dimension key column of a fact table of the database.

20. The computer program product of claim 12, wherein code for generating the subset of entries comprises:

code for generating the subset based on a composite index of a fact table in the database used in a Cartesian star join of at least two dimension tables, the at least two dimension tables being joined to the fact table on the composite index containing the columns corresponding to the dimension keys.

21. The computer program product of claim 12, wherein code for generating the subset of entries comprises:

code for generating the subset based on an index of a large table of the database used in a general query with conditions.

22. The computer program product of claim 12, wherein code for generating the subset of entries comprises:

code for generating the subset based on a query with aggregation and grouping on a composite join key.

23. For a database management system (DBMS) operatively coupled to a data processing system, a system for performing a sampled query of tables in a database, the system comprising:

a subset generator component for generating a subset of entries based on a query for data from the tables, the entries representing elements of an index of a larger table from the tables of the query;

a predicate module for generating a sampling predicate to reduce the number of entries in the subset, the sampling predicate being obtained from the query; and

a sampling predicate applier component for applying the sampling predicate to the subset to reduce the number of entries in the subset.

24. The system of claim 23, wherein the entries of the subset are selected from the group consisting of row identifiers of the index and key values of the index of the larger table.

25. The system of claim 23, wherein the sampling predicate is selected from the group consisting of:

a form of Bernoulli sampling and a random generator function.

26. The system of claim 23, wherein those tables in the database having a referential integrity relationship are determined, wherein the determined tables are used to generate the subset.

27. The system of claim 23, wherein the predicate module generates the sampling predicate for selecting entries of the subset based on a sampling rate of the subset.

28. The system of claim 23, wherein the sampling predicate obtained selects between about 5% and about 25% of the row identifiers in the subset based on the query for data in the tables.

29. The system of claim 23, wherein the subset generator component comprises a bit-mapped star join generator for generating the subset based on a bit-mapped star join of at least a dimension table and a dimension key column of a fact table of the database.

30. The system of claim 23, wherein the subset generator component comprises a Cartesian star join generator for generating the subset based on a composite index of a fact table in the database used in a Cartesian star join of at least two dimension tables, the at least two dimension tables being joined to the fact table on the composite index containing the columns corresponding to the dimension keys.

31. The system of claim 23, wherein the subset generator component comprises a general query generator for generating the subset based on an index of a large table of the database used in a general query with conditions.

32. The system of claim 23, wherein the subset generator component comprises a query with aggregation generator for generating the subset based on a query with aggregation and grouping on a composite join key.

33. For a database management system (DBMS) operatively coupled to a data processing system having memory for storing a database, a method performing a sampled query of tables in a database, the method comprising the steps of:

a) receiving a query for data from the tables;

b) generating a subset of entries based on the query for data from the tables, the entries representing elements of an index of a larger table from the tables of the query;

c) generating a sampling predicate to reduce the number of entries in the subset, the sampling predicate being obtained from the query;

d) applying the sampling predicate to the subset to reduce the number of entries in the subset;

e) generating a search of the reduced subset based on the query; and

f) retrieving the data from the database based on the search generated.

34. The method of claim 33, wherein in step b) the entries of the subset are selected from the group consisting of row identifiers of the index and key values of the index of the larger table.

35. The method of claim 33, further including the added step of performing non-filtering look-up table joins after step d).

36. The method of claim 33, wherein step c) comprises:

generating the sampling predicate using Bernoulli sampling.

37. The method of claim 33, wherein step c) comprises:

generating the sampling predicate using a random generator function.

38. The method of claim 33, wherein step b) comprises:

determining those tables in the database having a referential integrity relationship, wherein the determined tables are used to generate the subset.

39. The method of claim 33, wherein step b) comprises:

generating the sampling predicate for selecting entries of the subset based on a sampling rate of the subset.

40. The method of claim 33, wherein step c) comprises:

generating the sampling predicate for selecting between about 5% and about 25% of the row identifiers in the subset for the sampled query.

41. The method of claim 33, wherein step b) comprises:

generating the subset based on a bit-mapped star join of at least a dimension table and a dimension key column of a fact table of the database.

42. The method of claim 33, wherein step b) comprises:

generating the subset based on a composite index of a fact table in the database used in a Cartesian star join of at least two dimension tables, the at least two dimension tables being joined to the fact table on the composite index containing the columns corresponding to the dimension keys.

43. The method of claim 33, wherein step b) comprises:

generating the subset based on an index of a large table of the database used in a general query with conditions.

44. The method of claim 33, wherein step b) comprises:

generating the subset based on a query with aggregation and grouping on a composite join key.