Validating multiple execution plans for database queries

• US 7,010,524 B2
• Filed: 02/24/2004
• Issued: 03/07/2006
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US10/785,328
• Publication Number:
  US 20040167891A1
• Time in Patent Office: 742 Days
• Field of Search: 707 2- 7, 707/10, 707100-102, 707/104.1, 707/201, 709/104, 709/201, 709/203, 709/206, 709/213
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/959 Network
• 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/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

Validation of large numbers of alternative execution plans for a database query, either an exhaustive enumeration of the complete space of alternatives, or else an unbiased random sample, is performed by efficiently constructing execution trees from a data structure having groups alternative operators that are ranked in a directory. Each global rank of a plan identifies that plan uniquely among all the alternative plans. The operators are unranked from the directory according to a specification that characterizes the desired plans.

Claims

1. A system for validating multiple alternative execution plans for a single database query, comprising:

a search engine responsive to the query for constructing a data structure containing a plurality of groups each including a number of alternative operators, at least some of the operators having pointers to one or more different ones of the groups;

a ranking module for ranking the operators in the groups and for unranking them so as to construct a plurality of different execution plans for the query, wherein each execution plan is assigned a unique global rank, based on operator rank data, that identifies one respective execution plan from all other possible execution plans; and

a validation module for validating the execution plans from the ranking module.

2. The system of claim 1 where the data structure is a table.

3. The system of claim 1 further including a specification for specifying a number of different plans to be constructed.

4. The system of claim 1 further including a directory containing locations of the groups and operators within the data structure containing the groups.

5. The system of claim 4 where the directory includes rank data for each group representing a number of alternative plans associated with that group.