Answering top-K selection queries in a relational engine

• US 20060212429A1
• Filed: 03/17/2005
• Published: 09/21/2006
• Est. Priority Date: 03/17/2005
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Hui, Bruno, Nicolas
• Application Number:
  US11/082,645
• Publication Number:
  US 20060212429A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

The subject invention leverages threshold-based strategies applied to relational data to facilitate in determining an optimal execution plan for top-k selection queries. These strategies utilize a given query and relational data metadata to identify possible execution plans. This allows alternatives to scanning techniques to be considered in order to further enhance the overall efficiency of the optimal execution plan. A query optimizer can prune, for example, the alternative execution plans during enumeration of the plan space and/or during cost evaluations of the possible alternative execution plans. A cost model for the query optimizer can utilize a cost function based on an approximation of the number of iterations required to complete a threshold-based strategy.

Claims

1. A system that facilitates query processing, comprising:

a receiving component that receives a top-k query for a relational data; and

a query optimization component that determines an optimal execution plan for providing a top-k set of ordered tuples for the query via consideration, at least in part, of a threshold-based process that employs metadata associated with the relational data.

2. The system of claim 1, the threshold-based process employs an adaptation of a Threshold Algorithm (TA) strategy to identify alternative execution plans.

3. The system of claim 2, the query optimization component determines the optimal execution plan via selection of a lowest cost execution plan from the alternative execution plans.

4. The system of claim 1, the metadata comprising at least one index structure associated with the relational data.

5. The system of claim 1, the query optimization component identifies a set of possible execution plans given the query and the relational data metadata.

6. The system of claim 5, the query optimization component employs a pruning process to prune the set of possible execution plans to facilitate in determining the optimal execution plan.

7. The system of claim 6, the pruning process utilizes a number of iterations and a cost per iteration to determine if a possible execution plan exceeds a cost threshold and eliminates possible execution plans that employ similar index structures as the exceeding execution plan.

8. The system of claim 1 further comprising:

a cost model component that evaluates a cost of at least one execution plan determined via a threshold-based process.

9. A relational database management system that employs the system of claim 1.

10. A method of facilitating a top-k selection for relational data queries, comprising:

receiving a top-k query for relational data;

employing a threshold-based process to identify possible execution plans for a search space of the relational data;

the identification based, at least in part, on the query and metadata associated with the relational data;

pruning the possible execution plans to facilitate in determining an optimal alternative execution plan;

estimating a cost for each execution plan; and

selecting a minimal cost execution plan as the optimal alternative execution plan.

11. The method of claim 10, the possible execution plans comprising execution plans that utilize a zero or one index with a leading column c_i for each attribute c_i in a scoring function.

12. The method of claim 10, pruning the possible execution plans comprising:

determining if an execution plan exceeds a cost threshold utilizing a number of iterations and a cost per iteration; and

eliminating possible execution plans that employ similar index structures as the execution plan that exceeds the cost threshold.

13. The method of claim 10 further comprising:

estimating the execution plan cost by employing a process that determines cost based on, at least in part;

$\begin{array}{cc}\mathrm{Cost}=D·<br><br>T_C\left(\underset{\underset{\underset{\mathrm{strategy}}{c_i<br><br>\mathrm{usesindex}}}{1\le <br><br>i\le <br><br>m,}}{\sum <br><br>}<br><br>T_{S_i}+\underset{\underset{\underset{\mathrm{coveringindex}}{c_i<br><br>\mathrm{usesnon}}}{1\le <br><br>i\le <br><br>m,}}{\sum <br><br>}<br><br>T_L\right);<br><br>& \left(\mathrm{Eq}.\text{\hspace{1em}<br><br>}<br><br>1\right)\end{array}$

where the execution plan requires D iterations to finish, T_C represents the cost of maintaining a priority queue and calculating scores and threshold values, T_Si is the cost of a sorted access utilizing an index for attribute c_i, and T_L is a cost of a primary index lookup.

14. The method of claim 13, estimating the execution plan cost further comprising:

obtaining an approximate score of a top-k tuple;

determining a minimum value that results in a threshold value less than the approximate score of the top-k tuple; and

evaluating a cost function utilizing the minimum value as an approximation of the number of iterations D.

15. The method of claim 14 further comprising:

utilizing a small sample for the top-k score; and

employing unidimensional histograms for facilitating in the determination of the number of iterations.

16. The method of claim 15 further comprising:

obtaining top-k scores that are expected to rank in a data set at positions

$\frac{N+1}{S+1},\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},\frac{k·<br><br>\left(N+1\right)}{S+1}$

 

utilizing a precomputed small sample, where N is a number of tuples in a data set table and S is a sample size;

determining an expected number of iterations for each score utilizing single-column histograms; and

deriving an optimal curve that approximates a number of iterations function and evaluating it in k to facilitate in obtaining D.

17. A query optimizer for a relational database employing the method of claim 10 to facilitate in selecting an optimal query execution plan.

18. A scan-based query optimizer employing the method of claim 10 to augment sequential scan-based processes.

19. A system that facilitates query processing, comprising:

means for receiving a top-k query for a relational database; and

means for determining an optimal execution plan for providing a top-k set of ordered tuples for the query via consideration of a threshold-based process that employs metadata associated with the relational database.

20. The system of claim 19 further comprising:

means for comparing costs of execution plans determined via the threshold-based process and/or a sequential scan-based process.