Skew-based costing for database queries

• US 8,190,598 B2
• Filed: 10/30/2008
• Issued: 05/29/2012
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kosuru, Ramakumar, Varshneya, Renu, Al-Omari, Awny K, Wall, Robert L.
• Primary Examiner(s): Xue, Belinda
• Application Number:
  US12/261,058
• Publication Number:
  US 20100114870A1
• Time in Patent Office: 1,307 Days
• Field of Search: None
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

One embodiment is a method that determines skew to predict costs for query plans for a database query. The method selects a query plan that accounts for the skew to evenly distribute processing load among multiple processors and then executes the query with the selected query plan.

Claims

1. A method, comprising:

considering skew to generate costs for query plans for executing a query in a database;

selecting a query plan to eliminate the skew so data load while executing the query is evenly distributed across multiple processors;

executing the query with the query plan with the multiple processors in a parallel processing system; and

traversing histogram intervals for partitioning columns of input data and identifying an interval with a most frequent value to consider the skew to generate the costs for the query plans.

2. The method of claim 1 further comprising, estimating a number of participating records in the database having a busiest parallel processing stream to penalize a query plan cost to account for imbalances in workload apportionment across the multiple processors.

3. The method of claim 1 further comprising, identifying a cardinality of a busiest operator instance to provide an indicator of cost for executing the query plans.

4. The method of claim 1 further comprising, determining skew-based cardinality of a busiest operator instance that depends on a number of partitions for a column of the database.

5. The method of claim 1 further comprising, using a regression model to determine cardinality of a busiest operator instance based on a maximum expected cardinality resulting from random variation alone to account for instances of statistical variation in a number of unique values assigned to each processor of the multiple processors.

6. The method of claim 1 further comprising, computing a cardinality of a busiest operator instance for input into a cost model of an optimizer.

7. A tangible computer readable storage medium having instructions for causing a computer to execute a method, comprising:

estimating skew to predict costs for query plans for a query in a database, wherein estimating the skew comprises traversing histogram intervals for partitioning columns of input data and identifying an interval with a most frequent value;

selecting a query plan that reduces the skew to uniformly distribute processing load among multiple processors; and

executing the query with the query plan with the multiple processors in a parallel processing architecture.

8. The tangible computer readable storage medium of claim 7 further comprising, determining a processor with a busiest operator that will dominate a proportion of the processing load allocated to the multiple processors to improve accuracy of evaluating the query plans.

9. The tangible computer readable storage medium of claim 7 further comprising, determining a cardinality of records expected to be processed by an operator instance and using the cardinality to estimate operator-costs for the query plans.

10. The tangible computer readable storage medium of claim 7 further comprising, using a Monte Carlo method to determine a predictive model that supports parallel processing.

11. The tangible computer readable storage medium of claim 7 further comprising, determining a ratio of a number of distinct values to a total number of parallel processors (D/P) to provide accurate query plan costing.

12. The tangible computer readable storage medium of claim 7 further comprising, using a query optimizer to detect in advance of query compilation degrees of potential work imbalances across the multiple processors that accrue from data value skew.

13. The tangible computer readable storage medium of claim 7 further comprising, determining a cardinality of a processor with a busiest operator to penalize the costs for the query plans to account for imbalance in workload apportionment across the multiple processors.

14. A computer system, comprising:

a database; and

a processor to;

determine skew to predict costs for query plans for a query of the database, wherein determining the skew comprises traversing histogram intervals for partitioning columns of input data and identifying an interval with a most frequent value;

select a query plan that accounts for the skew to evenly distribute processing load among multiple processors; and

execute the query with the query plan with the multiple processors.

15. The computer system of claim 14, wherein the processor further determines a cardinality of a processor with a busiest operator.

16. The computer system of claim 14, wherein the processor further uses histograms to compute derivative metrics for a query optimizer to assist in establishing an accurate query plan cost based on an expected cardinality of a busiest operator instance.

17. The computer system of claim 14, wherein the processor further estimates a number of participating records in the database having a busiest parallel processing stream to penalize a query plan cost to account for imbalances in workload apportionment across the multiple processors.