Method for efficient query execution using dynamic queries in database environments

• US 20040215638A1
• Filed: 04/23/2004
• Published: 10/28/2004
• Est. Priority Date: 04/20/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kapoor, Rahul, Ellis, Nigel R., Sundaresan, Prakash
• Granted Patent: US 7,281,000 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2471 Distributed queries
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and method allowing for optimization of query execution in database environments is provided. In an illustrative implementation, a database having distributed partitioned views is provided such that queries may initiate at any of the participating data stores. In operation, an offered query is analyzed to determine if it has predicate expression and/or sub-queries. Using this information the expressions and/or sub-queries are analyzed and processed to determine if appropriate start-up filters are available for the offered query. The start-up filters are applied to the query such that during compile and/or run time, redundant partitions in the distributed partitioned database environment are eliminated during query execution.

Claims

1. A method providing query execution plans for distributed database environments having distributed partitioned views comprising the steps of:

analyzing offered queries to determine if said offered queries comprise predicate expressions and/or sub-queries; and

providing dynamic start-up filters for inclusion in query execution plans, said startup filters, when applied, removing redundant partitions from query plan execution, wherein the dynamic start-up filters are chosen based on the predicate expressions found in the offered queries.

2. The method as recited in claim 1 further comprising the step of classifying said offered queries according to whether said offered queries comprise predicate expressions and sub-queries.

3. The method recited in claim 2 further comprising the steps of executing a function to generate start-up expressions for said offered queries having said predicate expressions.

4. The method recited in claim 3 further comprising the step of executing a function to generate start-up conjunctions such that an array of conjunction expressions rgTemp is created for each of said predicate expressions found in said offered queries.

19. A computer readable storage medium comprising computer-executable instructions for instructing a computer to perform the acts recited in claim 1.

20. The method recited in claim 2 further comprising the steps of executing a function to generate start-up expressions for said offered queries having said sub-queries.

21. The method recited in claim 20 further comprising the step of executing a function to generate query start-up conjuncts, said query start-up conjuncts generation function producing an array of conjunction expressions rgTemp1.

5-18. -18. (Cancelled)

22-23. -23. (Cancelled)

24. A system providing enhanced query execution plans for distributed database environments having distributed partitioned views comprising:

a dynamic execution plan system, the dynamic execution plan system processing queries comprising at least one predicate expression; and

a dynamic start-up filter generation system cooperating with said dynamic execution plan system to produce execution plans having start-up filters, wherein the start-up filters are chosen based on the at least one predicate expression.

25. The system recited in claim 24, wherein said dynamic execution plan system generates execution plans for offered queries, said execution plans providing steps to process said offered queries.

26. The system recited in claim 25, wherein said dynamic start-up filter generation system comprises a plurality of functions and operations to identify appropriate start-up filters for said offered queries, said start-up filters comprising functions and operations to remove redundant steps from said execution plans.

27. A method providing enhanced query execution plans comprising:

providing start-up filters, said start-up filters being processed at run and/or compile time to remove redundant processing steps from said execution plans based on data provided in offered queries, wherein the queries comprise at least one predicate expression and wherein the start-up filters provided are provided based on the at least one predicate expression; and

applying said start-up filters on said offered queries.

28. The method recited in claim 27 further comprising the step of:

analyzing said offered queries for predicate expressions and/or sub-queries.

29. The method recited in claim 28 further comprising the step of providing different start-up filters for said offered queries having predicate expressions than for said offered queries having sub-queries.