DYNAMIC FILTERS FOR RELATIONAL QUERY PROCESSING

• US 20080215556A1
• Filed: 03/01/2007
• Published: 09/04/2008
• Est. Priority Date: 03/01/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Surna, Aleksandras, Zabback, Peter, Gukal, Sreenivas
• Granted Patent: US 8,086,593 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• 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:

an operator tree associated with table(s) that are referenced by a query; and

a dynamic filter component(s) that is automatically generated during execution of the query by an analysis thereof, the dynamic filter component(s) to eliminate non-qualifying data for the operator tree.

2. The computer implemented system of claim 1, the dynamic filter component derived via predicates that are formed by analyzing the query.

3. The computer implemented system of claim 2, the operator tree with a join that interacts with a fact table and a dimension table.

4. The computer implemented system of claim 2 further comprising an evaluation component that evaluates performance order of the dynamic filter component.

5. The computer implemented system of claim 3, the fact table with rows disposable by the dynamic filter component.

6. The computer implemented system of claim 3, the join associated with a star join pattern, and the dynamic filter component derived from the dimension table.

7. The computer implemented system of claim 3, the join associated with a snow flake schema.

8. The computer implemented system of claim 3 further comprising a surrogate key.

9. The computer implemented system of claim 3 further comprising an optimizer that selects a join algorithm for the join.

10. A computer implemented method comprising the following computer executable acts:

determining predicates by examining a query; and

automatically generating a dynamic filter(s) from the predicates, the dynamic filter not explicitly defined by the query.

11. The computer implemented method of claim 10 further comprising eliminating non-qualifying rows from a table referenced by the query via the dynamic filter.

12. The computer implemented method of claim 10, the examining act further comprising assigning value boundaries.

13. The computer implemented method of claim 11 further comprising identifying qualifying fact table rows.

14. The computer implemented method of claim 13 further comprising processing qualifying rows in the operator tree.

15. The computer implemented method of claim 10 further comprising determining the dynamic filter during a build phase of a hash join.

16. The computer implemented method of claim 15 further comprising probing the dynamic filter before a row of the table is employed in the hash join.

17. The computer implemented method of claim 16 further comprising evaluating an order of implementing dynamic filters.

18. The computer implemented method of claim 17 further comprising re-ordering the dynamic filters.

19. The computer implemented method of claim 18 further comprising monitoring number of eliminated rows.

20. A computer implemented system comprising:

processing means for processing joins associated with table(s) that are referenced by a query; and

means for eliminating non qualifying data for the operating means.