Multi-dimensional selectivity estimation method using compressed histogram information

• US 6,311,181 B1
• Filed: 03/19/1999
• Issued: 10/30/2001
• Est. Priority Date: 03/05/1999
• Status: Expired due to Fees

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Lee, Ju-Hong, Chung, Chin-Wan, Kim, Deok-Hwan
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): NGUYEN, TAM V
• Application Number:
  US09/273,131
• Time in Patent Office: 956 Days
• Field of Search: 707/2, 707/5, 348/403.1, 375/240.18, 382/248
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Disclosed is a multi-dimensional selectivity estimation method using compressed histogram information which the database query optimizer in a database management system uses to find the most efficient execution plan among all possible plans. The method includes the several steps to generate a large number of small-sized multi-dimensional histogram buckets, sampling DCT coefficients which have high values with high probability, compressing information from the multi-dimensional histogram buckets using a multi-dimensional discrete cosine transform(DCT) and storing compressed information, and estimating the query selectivity by using compressed and stored histogram information as the statistics.

Claims

1. A multi-dimensional selectivity estimation method using compressed histogram information to obtain the statistics approximating data distribution of a database for the estimation of database query selectivity, said method comprising the steps of:

dividing the data distribution to generate a large number of small-sized multi-dimensional histogram buckets;

compressing the histogram information from the multi-dimensional histogram buckets using a multi-dimensional discrete cosine transform(DCT) and storing the compressed information; and

estimating the query selectivity by using the compressed and stored histogram information as the statistics.

2. The method of claim 1, wherein said histogram compressing step by using said multi-dimensional DCT uses, upon a geometrical zonal sampling in which DCT coefficients having large values among DCT coefficients are selected to reduce the amount of stored information, after the DCT, a triangular sampling method which selects the DCT coefficients, such that the sum of position indices is less than or equal to a given sampling bound value.

3. The method of claim 1, wherein said histogram compressing step by using said multi-dimensional DCT uses, upon a geometrical zonal sampling in which DCT coefficients having large values among DCT coefficients are selected to reduce the amount of stored information, after the DCT, a reciprocal sampling method which selects the DCT coefficients, such that the multiplication of position indices to which ‘

1’

is added is less than or equal to a given sampling bound value.

4. The method of claim 1, wherein said histogram compressing step by using said multi-dimensional DCT uses, upon a geometrical zonal sampling in which DCT coefficients having large values among DCT coefficients are selected to reduce the amount of stored information, after the DCT, a spherical sampling method which selects the DCT coefficients, such that the sum of the square of position indices is less than or equal to a given sampling bound value.

5. The method of claim 1, wherein upon application of said DCT, if data are newly inserted, the DCT coefficients of the inserted data are computed and added to existing DCT coefficients, and if data are deleted, the DCT coefficients of the deleted data are computed and subtracted from the existing DCT coefficients, to thereby reflect dynamic data updates to the statistics for estimating the query selectivity immediately in the environment where the data are frequently inserted or deleted.

6. The method of claim 1, wherein in said estimating step, assuming that q_k is a k-dimensional range query, the range of the query q_k is a_i≦

x_i≦

b_i for 1≦

i≦

k, the data space is normalized as (0,1)ⁿ, and the x_i coordinate is divided into N_i partitions, the selectivity of a query q_k is expressed as follows;

$\begin{array}{cc}\mathrm{Selectivity}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>a<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{query}& \left(13\right)\\ \begin{array}{c}{q}_k=\text{\hspace{1em}<br><br>}<br><br>{\int <br><br>}_{a_k}^{b_k}<br><br>\mathrm{\dots <br><br>}<br><br>{\int <br><br>}_{a_2}^{b_2}<br><br>{\int <br><br>}_{a_1}^{b_1}<br><br>f<br><br>\left(x_1,x_2,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},x_k\right)<br><br><br><br>x_1<br><br><br><br>x_2<br><br>\mathrm{\dots <br><br>}<br><br><br><br>x_k\\ \approx <br><br>\text{\hspace{1em}<br><br>}<br><br>\sqrt{\frac{2}{N_1}}<br><br>\mathrm{\dots <br><br>}<br><br>\sqrt{\frac{2}{N_k}}<br><br>\underset{g<br><br>\left(u_1,\mathrm{\dots <br><br>},u_k\right)\in <br><br>Z}{\sum <br><br>}<br><br>k_{u_1}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>k_{u_k}<br><br>g<br><br>\left(u_1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>u_k\right)\\ \text{\hspace{1em}<br><br>}<br><br>{\int <br><br>}_{a_1}^{b_1}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(u_1<br><br>\mathrm{\pi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_1\right)<br><br><br><br>x<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\int <br><br>}_{a_k}^{b_k}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\left(u_k<br><br>\mathrm{\pi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_k\right)<br><br><br><br>x_k.\end{array}& \text{\hspace{1em}<br><br>}\end{array}$