Validating multiple execution plans for database queries

• US 20050149492A1
• Filed: 11/24/2004
• Published: 07/07/2005
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Galindo-Legaria, Cesar A., Waas, Florian
• Granted Patent: US 7,194,452 B2
• Time in Patent Office: Days
• 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-38. -38. (canceled)

39. A computer-executable medium having computer-executable instructions for validation by a programmed digital computer, the computer-executable instructions performing:

organizing a plurality of alternative execution plans for carrying out a database query into a plurality of groups each having at least one operator associated with at least one operator in another of the groups, where each of the execution plans is a tree of the operators and includes operators taken from different ones of the groups;

determining rank data for each operator related to a number of alternative operators in the other of the groups;

determining rank data for each group; and

producing a global rank for at least one of the alternative execution plans from the rank data.

40. The computer-executable medium of claim 39, where a respective global rank uniquely identifies one execution plan from all other alternative execution plans.

41. The computer-executable medium of claim 40, where the ranks of all alternative execution plans are dense.