Query optimization with zone map selectivity modeling

Patent metadata

Field	Value
Publication number	US-10031942-B2
Application number	US-201514836109-A
Country	US
Kind code	B2
Filing date	Aug 26, 2015
Priority date	Dec 5, 2014
Publication date	Jul 24, 2018
Grant date	Jul 24, 2018

Abstract

According to one embodiment of the present invention, a system for processes a query for accessing data within one or more database objects stores an element of a database object among a plurality of different storage regions. Each storage region is associated with first and second range values indicating a value range for element values within that storage region. The system examines the first and second range values for the storage regions of each database object element and determines an effectiveness value representing a degree of overlap between the storage regions of that database object element. The system determines a selectivity model for the storage regions for each database object utilizing the effectiveness value, determines a query plan based on the selectivity model, and executes the query plan. Embodiments of the present invention further include a method and computer program product for processing a query in substantially the same manners.

First claim

What is claimed is:

1. A computer-implemented method of processing a query for accessing data within one or more database objects, wherein a database object element is stored among a plurality of different storage regions with each storage region being associated with a first range value and a second range value indicating a value range for element values within that storage region, the computer-implemented method comprising:
determining a zone map effectiveness value representing a degree of overlap between the storage regions of each database object element by examining the first range value and the second range value for the storage regions of that database object element, the determining the zone map effectiveness value for each respective database object element by:
sorting the first range values and the second range values for storage regions of the respective database object element, the first range values being minimum values for respective storage regions and the second range values being maximum values for the respective storage regions,
for each respective sorted value of the first range values and the second range values, determining a respective rolling count, the rolling count being incremented for each minimum value encountered and being decremented for each maximum value encountered,
adding each of the respective rolling counts to produce an accumulated sum, and
producing the zone map effectiveness value based on the accumulated sum and a number of respective storage regions for the respective database object element;

determining a zone map selectivity model for the storage regions for each database object element of the query utilizing the zone map effectiveness value of the each database object element of the query and a total quantity of the storage regions for the each database object element to model zone map selectivity and multiplying the zone map effectiveness value of each individual respective database object element of the each database object element of the query by the total quantity of the corresponding storage regions for the each individual respective database object element to produce an estimate of a quantity of storage regions to be read when performing a second query regarding the each individual respective database object;
determining an order for executing a plurality of query plans for the query based on the determined zone map selectivity model for the each database object element of the query, the determined order for executing the plurality of query plans having a lowest expected cost among all possible orders for executing the plurality of query plans; and
executing the plurality of query plans in the determined order to access data from the database object elements for the query.

2. The computer-implemented method of claim 1 , wherein the zone map effectiveness value for each database object element is in a value range between zero and one.

3. The computer-implemented method of claim 1 , wherein each database object includes a database table, and the database object element includes a database table column.

4. The computer-implemented method of claim 3 , wherein the query includes a restriction on plural database table columns and determining the zone map selectivity model further comprises:
combining the zone map effectiveness values for the database table columns of the restriction with column correlation statistics to determine an amount of input/output operations for the plural column restriction on the plural database table columns.

5. The computer-implemented method of claim 1 , wherein the determined order for executing the plurality of query plans indicates at least one of a scan order and a join order for the database objects based on the zone map selectivity model of the corresponding database object elements.

6. The computer-implemented method of claim 5 , wherein the query plan indicates a join order that effectively utilizes the storage regions of the database objects, and determining the zone map selectivity model further comprises:
utilizing join conditions with the first range value and the second range value for the storage regions of each of the corresponding database object elements to determine the zone map selectivity model for those corresponding database object elements.

7. The computer-implemented method of claim 1 , further comprising:
sampling a portion of the data from the one or more database objects to evaluate query plan costs in response to the zone map selectivity model indicating that an expected cost of performing the query exceeds a predetermined threshold.

Assignees

• IBM

Inventors

• Dickie Garth A
• Wolf Jay B

Classifications

• G06F16/24545

  Selectivity estimation or determination · CPC title

• G06F16/90335

  Query processing · CPC title

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/9017

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F17/30979

  Physics · mapped topic