CARDINALITY ESTIMATION IN DATABASE SYSTEMS USING SAMPLE VIEWS

• US 20080306903A1
• Filed: 06/08/2007
• Published: 12/11/2008
• Est. Priority Date: 06/08/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-Ake, Zhou, Jingren, Zabback, Peter Alfred, Lehner, Wolfgang Martin Josef
• Application Number:
  US11/760,203
• Publication Number:
  US 20080306903A1
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A system and method that facilitates and effectuates estimating the result of performing a data analysis operation on a set of data. Employing an approximation of the data analysis operation on a statistically valid random sample view of the data allows for a statistically accurate estimate of the result to be obtained. Sequential sampling in the view enables the approximated operation to evaluate accuracy conditions at intervals during the scan of the sample view and obtain the estimated result without having to scan the entire sample view. Feedback regarding the accuracy of the estimated result can be captured when the data analysis operation is performed against the set of data. Process control techniques can be employed with the feedback to maintain the statistical validity of the sample view.

Claims

1. A system for estimating the results of a data analysis operation, comprising:

an sample view component that creates one or more sample views representing data on which the data analysis operation is intended to be performed, the one or more sample views contains a random sample of the data; and

an estimation component that performs an approximation of the data analysis operation on the one or more sample views to produce an estimated result of performing the data analysis operation on the data.

2. The system of claim 1, wherein the data analysis operation is a query or a subexpression of a query.

3. The system of claim 2, wherein the approximation of the data analysis operation is a probe query.

4. The system of claim 3, wherein the estimated result is a cardinality estimate.

5. The system of claim 4, further comprising an optimization component that employs the cardinality estimate to produce an optimized execution plan for the query.

6. The system of claim 5, further comprising a feedback component that produces feedback with the error between actual cardinality and the cardinality estimate each time the query is executed.

7. The system of claim 6, further comprising a sample quality control component that employs the feedback to determine when a sample view should be recreated.

8. The system of claim 7, wherein the sample quality control component triggers the sample view component to recreate the sample view when the error exceeds a threshold.

9. The system of claim 3, wherein a probe query employs sequential sampling against at least one sample view.

10. The system of claim 9, wherein a random identifier is assigned to each row of the at least one sample view, the at least one sample view is sorted by the random identifier.

11. The system of claim 10, wherein the probe query scans the at least one sample view until a stopping condition is met, the stopping condition is evaluated at each change in the random identifier, upon meeting the stopping condition the estimated result is output.

12. A method for estimating the results of a data analysis operation, comprising:

creating one or more sample views representing data on which the data analysis operation is intended to be performed, the one or more sample views contains a random sample of the data; and

performing an approximation of the data analysis operation on the one or more sample views to produce an estimated result of performing the data analysis operation on the data.

13. The method of claim 12, wherein the estimated result is a cardinality estimate of a query or a subexpression of a query.

14. The method of claim 13, further comprising employing the cardinality estimate to produce an optimized execution plan for the query.

15. The method of claim 14, further comprising producing feedback with the error between actual cardinality and the cardinality estimate each time the query is executed.

16. The method of claim 15, further comprising employing the feedback to recreate a sample view when the error exceeds a threshold.

17. The system of claim 12, further assigning a random identifier to each row of a sample view and sorting the sample view by the random identifier.

18. The method of claim 17, performing the approximation of the data analysis operation on the sample view until a stopping condition is met, wherein the stopping condition is evaluated at each change in the random identifier, and outputting the estimated result upon meeting the stopping condition.

19. A system for estimating the results of a data analysis operation, comprising:

means for creating one or more sample views representing data on which the data analysis operation is intended to be performed, the one or more sample views contains a random sample of the data; and

means for performing an approximation of the data analysis operation on the one or more sample views to produce an estimated result of performing the data analysis operation on the data.

20. The system of claim 19, further comprising:

means for producing feedback with the error between actual result and the estimated result each time the data analysis operation is executed on the data; and

means for employing the feedback to recreate a sample view when the error exceeds a threshold.