Skew-based Costing for Database Queries

• US 20100114870A1
• Filed: 10/30/2008
• Published: 05/06/2010
• 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: Wall, Robert l., Kosuru, Ranajynar, Varshneya, Renu, Al-Omari, Awny K.
• Granted Patent: US 8,190,598 B2
• Time in Patent Office: Days
• 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 skew so data load while executing the query is evenly distributed across multiple processors; and

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

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, 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.

5. ) 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.

6. ) 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.

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

8. ) 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;

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.

9. ) The tangible computer readable storage medium of claim 8 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.

10. ) The tangible computer readable storage medium of claim 8 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.

11. ) The tangible computer readable storage medium of claim 8 further comprising, compensating query plan costs for situations where an inherent value of skew is significant by determining skew-based cardinality of a busiest operator instance.

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

13. ) The tangible computer readable storage medium of claim 8 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.

14. ) The tangible computer readable storage medium of claim 8 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.

15. ) The tangible computer readable storage medium of claim 8 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.

16. ) A computer system, comprising:

a database; and

a processor to;

determine skew to predict costs for query plans for a query of the database;

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.

17. ) The computer system of claim 16, wherein the processor further determines a cardinality of a processor with a busiest operator.

18. ) The computer system of claim 16, wherein the processor further accounts for both the skew and a ratio of a number of distinct values to a total number of parallel processors (D/P) to provide accurate query plan costing.

19. ) The computer system of claim 16, 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.

20. ) The computer system of claim 16, 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.