Method for efficient query execution using dynamic queries in database environments

• US 7,281,000 B2
• Filed: 04/23/2004
• Issued: 10/09/2007
• Est. Priority Date: 04/20/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kapoor, Rahul, Ellis, Nigel R., Sundaresan, Prakash
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US10/830,584
• Publication Number:
  US 20040215638A1
• Time in Patent Office: 1,264 Days
• Field of Search: 707 1- 4
• US Class Current: 1/1
• 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 implemented by a computing device providing query execution plans for distributed database environments having partitioned views comprising the steps of:

analyzing offered queries to determine if the offered queries comprise predicate expressions or sub-queries;

providing dynamic start-up filters for inclusion in the query execution plans for the distributed database environments having the partitioned views,

removing redundant partitions from the query execution plans by applying the dynamic start-up filters, wherein the dynamic start-up filters are chosen based on the predicate expressions found in the offered queries;

classifying the offered queries according to whether the offered queries comprise the predicate expressions and the sub-queries;

generating start-up expressions for the offered queries having the predicate expressions;

generating start-up conjunctions such that an array of conjunction expressions is created for each predicate expression of the predicate expressions found in the offered queries and;

storing the generated start-up conjunctions in a memory.

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

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

4. The method recited in claim 3 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.

5. A computer-implemented system providing enhanced query execution plans for distributed database environments having partitioned views comprising:

a processor;

a dynamic execution plan system, the dynamic execution plan system analyzing offered queries and processing the offered queries to determine if the offered queries comprises predicate expressions or sub-queries;

a dynamic start-up filter generation system cooperating with the dynamic execution plan system to produce query execution plans having dynamic start-up filters for the distributed database environments having the partitioned views, to generate start-up conjunctions such that an array of conjunction expressions is created for each predicate expression of the predicate expressions found in the offered queries, and to store the generated start-up conjunctions in a memory, wherein the dynamic start-up filters are chosen based on at least one predicate expression in the offered queries; and

the dynamic start-up filter generation system further comprises a plurality of functions and operations to identify appropriate the dynamic start-up filters for the offered queries, the dynamic start-up filters comprising functions and operations to remove redundant steps from the query execution plans.

6. A method implemented by a computing device providing enhanced query execution plans comprising:

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

applying the dynamic start-up filters on the offered queries;

classifying the offered queries according to whether the offered queries comprise predicate expressions and sub-queries;

generating start-up expressions for the offered queries having the predicate expressions;

generating start-up conjunctions such that an array of conjunction expressions is created for each predicate expression of the predicate expressions found in the offered queries; and

storing the generated start-up conjunctions in a memory.