Dynamic filters for relational query processing

• US 8,086,593 B2
• Filed: 03/01/2007
• Issued: 12/27/2011
• Est. Priority Date: 03/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Surna, Aleksandras, Gukal, Sreenivas, Zabback, Peter
• Primary Examiner(s): Lu, Kuen
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US11/680,708
• Publication Number:
  US 20080215556A1
• Time in Patent Office: 1,762 Days
• Field of Search: 707/4, 707687-704, 707604-606, 707/736, 707/75, 707/713, 707/E17.017
• US Class Current: 707/713
• CPC Class Codes: G06F 16/245 Query processing

Abstract

Systems and methods that eliminate non-qualifying data for queries against data warehouses and improve execution time, via a dynamic filter component(s). In general, such dynamic filter components are derived from data during processing of the query and without being explicitly defined by the users within a query forwarded to the data warehouse. Moreover, an evaluation component can monitor efficiency of filter components (e.g., number of rows that can be eliminated), and dynamically change and/or update the evaluation order of such filters.

Claims

1. A computer implemented system comprising:

a processor; and

a memory component communicatively coupled to the processor, the memory component having stored therein computer-executable instructions configured to implement the system including;

an operator tree including at least one join configured to interact with a first table and a second table referenced by a query, wherein the operator tree is configured to receive first data from the first table via a first segment of the operator tree, and wherein the operator tree is configured to receive second data from the second table via a second segment of the operator tree;

a dynamic filter component configured to;

automatically generate a plurality of dynamic filters independent of an explicit external input, wherein the dynamic filter component is configured to generate the plurality of dynamic filters during execution of the query while the first data from the first table is received via the first segment of the operator tree, and wherein the dynamic filter component is configured to derive the plurality of dynamic filters via predicates that are formed through an analysis of the query; and

apply the plurality of dynamic filters at an initial position of the second segment of the operator tree according to an order based on a corresponding selectivity of each dynamic filter to eliminate a set of non-qualifying data from the second data prior to performing the at least one join, and wherein the dynamic filter component is configured to calculate the corresponding selectivity by dividing a number of rows passing through a corresponding dynamic filter by a number of rows being processed; and

an evaluation component configured to evaluate a performance order of the dynamic filter component, wherein the evaluation component is further configured to reorder the plurality of dynamic filters according to a corresponding quotient value, and wherein the corresponding quotient value is the number of rows passing through the corresponding dynamic filter divided by the number of rows being processed.

2. The computer implemented system of claim 1, wherein the second table being a fact table and the first table being a dimension table.

3. The computer implemented system of claim 2, wherein the fact table includes rows that are disposable by the dynamic filter component.

4. The computer implemented system of claim 2, wherein the join is associated with a star join pattern, and the dynamic filter component is configured to derive the plurality of dynamic filters from the dimension table.

5. The computer implemented system of claim 2, wherein the join is associated with a snow flake schema.

6. The computer implemented system of claim 2, wherein the dynamic filter component is configured to generate a surrogate key as a function of the first table, and wherein the dynamic filter component is configured to apply the surrogate key to the second table.

7. The computer implemented system of claim 2, further comprising an optimizer configured to select a join algorithm for the join.

8. A computer implemented method comprising the following computer executable steps:

employing a processor to execute computer executable instructions stored on a computer readable storage medium to implement the following steps;

determining predicates by examining a query, the query executed according to an operator tree including at least one join configured to interact with a first table having a first set of data and a second table having a second set of data, wherein the operator tree is configured to receive the first set of data via a first segment of the operator tree, and wherein the operator tree is configured to receive the second set of data via a second segment of the operator tree;

automatically generating a plurality of dynamic filters from the predicates independent of an explicit external input, wherein the plurality of dynamic filters are generated during execution of the query while the first set of data is received via the first segment of the operator tree;

applying the plurality of dynamic filters at an initial position on the second segment of the operator tree according to an order based on a corresponding selectivity of each dynamic filter, wherein the dynamic filter facilitates eliminating a set of non-qualifying data from the second set of data prior to performing the at least one join, and wherein the corresponding selectivity is calculated by dividing a number of rows passing through a corresponding dynamic filter by a number of rows being processed; and

evaluating a performance of the order, wherein the plurality of dynamic filters are reordered according to a corresponding quotient value, and wherein the corresponding quotient value is the number of rows passing through the corresponding dynamic filter divided by the number of rows being processed.

9. The computer implemented method of claim 8, further comprising eliminating the set of non-qualifying data from a fact table referenced by the query, wherein the second table is the fact table.

10. The computer implemented method of claim 8, the determining step further comprising assigning value boundaries.

11. The computer implemented method of claim 9, further comprising identifying a set of qualifying rows from the fact table referenced by the query.

12. The computer implemented method of claim 11, further comprising processing the set of qualifying rows.

13. The computer implemented method of claim 8, further comprising generating the plurality of dynamic filters during a build phase of a hash join corresponding to the first table and the second table.

14. The computer implemented method of claim 13, further comprising probing the second table with the dynamic filter before a row of the second table is employed in the hash join.

15. The computer implemented method of claim 8, further comprising ascertaining a number of eliminated rows.

16. A non-transitory computer readable storage medium comprising:

a memory component configured to store computer-readable instructions, the computer-readable instructions including instructions for performing the following acts;

processing an operator tree including a plurality of joins associated with a first table and a second table referenced by a query, wherein the operator tree is configured to receive first data from the first table via a first segment of the operator tree, and wherein the operator tree is configured to receive second data from the second table via a second segment of the operator tree;

generating a plurality of filters independent of an explicit external input, wherein the plurality of filters are generated during execution of the query while the first data from the first table is received via the first segment of the operator tree, and wherein the plurality of dynamic filters are derived via predicates that are formed through an analysis of the query;

eliminating a set of non qualifying data from the second table before performing any of the plurality of joins, the non qualifying data eliminated by applying the plurality of filters at an initial position on the second segment of the operator tree according to an order based on a corresponding selectivity of each filter to eliminate the set of non qualifying data as the second data from the second table is initially received via the second segment of the operator tree, wherein the corresponding selectivity is calculated by dividing a number of rows passing through a corresponding dynamic filter by a number of rows being processed; and

evaluating a performance of the order, wherein the plurality of dynamic filters are reordered according to a corresponding quotient value, and wherein the corresponding quotient value is the number of rows passing through the corresponding dynamic filter divided by the number of rows being processed.