Method and system for sample size determination for database optimizers6732085Abstract A system and method for determining an adequate sample size for statistics collection is disclosed. A mechanism for automatically determining an adequate sample size for both statistics and histograms is provided. The sample size determination is accomplished via an iterative approach where the process starts with a small sample, and for each attribute which may need more data, the sample size is increased while restricting the information collected to only those attributes that require the larger sample. Claims What is claimed is: Description COPYRIGHT NOTICE
ifauto sample size
do a quick row count estimate of the object
initialize all of the statistics bits for the columns
while there are still unresolved statistics
generate the from clause for the query
execute the basic query
work on all of the desired histograms
evaluate the basic statistics
if some statistics are not ready (need larger sample size)
construct a new select list using the current statistics
bits
The following table defines variables used in the illustrative pseudocode.
TABLE 1
Term Definition
P Sampling fraction (between 0.0 and 1.0)
N Number of rows in the table
Avg Average column length statistic
min/max Minimum/maximum column value statistic
Nv Number of null column values statistic
Ndv Number of distinct values statistic
S Number of rows seen in the sample
Snnv Number of non-null column values seen in the
sample
Sndv Number of distinct values seen in the sample
mnb Maximum number of buckets allowed in the
histogram
The following is pseudocode for the top level routine for gathering statistics and for determining whether a histogram should be collected:
estimate n -- use block sample count(*) on user's table
initialize_gather_bits( )
while (some statistics still need to be (re)collected)
generate_from_clause( ) -- includes possible materialization of
new table
execute_basic( )
execute_hist( )
evaluate_basic( )
This top level pseudocode executes the main functions that comprise the statistics gathering processes according to one embodiment of the invention. The initialize_gather_bits( ) function is a procedure which takes in the array of columns for which statistics need to be collected and sets bits representing which statistics are needed. These bits are later individually cleared after gathering statistics and evaluating their probable accuracy. The function is called initially so that the select list can be generated from it for all objects. It is later called again to reset the bits for each new object (e.g., table/partition/subpartition). The process takes in the list of columns (including statistics bits) and creates a select list to be used to gather basic statistics (not including histograms). In an embodiment, the process ensures that the select list does not contain more functions than the server can handle at once, e.g., only 256 distinct aggregates. If it cannot fit them all in one statement, the caller is informed of which columns are included. The generate_from_clause( ) function has the responsibility of generating the FROM clause for the basic query and all the histogram queries. In one embodiment, each histogram uses a separate query, and therefore employs a separate scan of the data. If many scans are required and involve sampling the underlying table, it may be beneficial to materialize the sample once and then pass over that multiple times. If that is the case, this procedure in one embodiment will generate a temporary table and populate it with a sample. The execute_basic( ) function handles the basic statistics query to parse, execute, and fetch information from the database objects. In an embodiment, the query is generated earlier in the process and the column array provides sufficient information to infer the select list. The evaluate_basic( ) procedure looks at the fetched basic statistics and tries to scale them up. This procedure clears the bits for all statistics that are acceptably scaled, and suggests a larger sampling percentage if some statistics need to be recollected. The execute_hist( ) procedure is the driver for collecting and evaluating the histogram statistics. This function looks over all columns that are marked as possibly needing histograms. It then collects a frequency histogram, a height histogram, or both, depending upon the expected number of distinct values and the requested number of buckets. The following comprises pseudocode for an embodiment of the initialize_gather_bits( ) function, in which the following statistics are collected: nv, ndv, min, max, and avg.
for each column the user requested
mark a bit to indicate need to collect the following statistics:
nv, ndv, min, max, avg
if there is a need to collect a histogram (see results of FIG. 4)
mark a bit indicating this
The following comprises pseudocode for an embodiment of the generate_from_clause( ) function, which establishes the initial sampling fraction p for the statistics gathering process:
if first time, set p to 5500 / n -- try for 5500 rows
otherwise, p is passed in to this function
if((p <= 0) or (p >= 0.15)) set p to 1.0 -- don't sample
if p < 1.0 and there are multiple passes (due to histograms)
materialize the sample in another table and use that table instead
In the illustrative embodiment, the process attempts to collect 5500 rows. To accomplish this, it is useful to know in advance the number of rows in the table. Based upon the number of rows, the sampling fraction p is established as shown in the pseudocode. If the number of rows is not known, then estimate this value. Certain thresholds can be established for the sampling fraction, beyond which the sampling fraction is set to 1. Under certain circumstances, it may make sense to create another table to hold the sampled data from the column. For example, if multiple passes are needed, e.g., because histograms are to be collected, then the samples are materialized into a table to prevent repeated accesses to the larger base table. The execute_basic( ) function builds up one or more queries to retrieve sampled data and calculates the desired statistics (excluding histograms in an embodiment). The one or more queries are then executed to retrieve the results for evaluation, as set forth below. In an embodiment, the one or more queries samples rows from the table based upon the sampling fraction p that was previously established. The evaluate_basic( ) function determines whether the number of rows sampled according to the sampling fraction p can be adequately scaled upward for the entire table. The following comprises pseudocode for an embodiment of the evaluate_basic( ) function:
if (p < 1.0)
if (s < 2500) -- too small a sample
bump up p accordingly
n = s / p
for each column
clear all non-histogram bits that indicate which statistics to
collect if nv bit was set
nv = n - snnv / p
if (avg, min, or max bit was set) and (snnv < 919)
bump up p accordingly
set avg, min, and max bits again for next pass
if ndv bit was set
try to scale it up *
if cannot scale upward
bump up p accordingly
set ndv again for next pass
else -- this was not an estimate
set all requested statistics
The pseudocode first checks that at least 2500 rows were sampled based upon the current sampling fraction (p). If not, then the sampling fraction is adjusted upward and the table is re-sampled. If a sufficient number of rows has been collected, then the number of rows (n) is estimated based upon the following: n=s/p, where s represents the number of rows that have been collected. For the average length, minimum, and maximum column value statistics (avg, min, max), the pseudocode checks that at least 919 non-null column values (snnv) are detected in the sample. If so, then these values are considered adequate for the entire table. If not, then the sampling fraction p is increased for the next pass through the table. For the number of distinct values statistic (ndv), the pseudocode attempts to scale this statistic up for the entire table. If the statistic based upon the sampled rows cannot be scaled upward, then the sampling fraction is increased for the next pass through the table. The following comprises pseudocode for scaling ndv and density (defined below) statistics according to an embodiment of the invention:
sdiv := sndv / snnv
if((snnv < 100) or
((snnv >= 100) and (snnv < 500) and (sdiv > 0.3299)) or
((snnv >= 500) and (snnv < 1000) and (sdiv > 0.4977)) or
((snnv >= 1000) and (snnv < 2000) and (sdiv > 0.5817)) or
((snnv >= 2000) and (snnv < 5000) and (sdiv > 0.6634)) or
((snnv >= 5000) and (snnv < 10000) and (sdiv > 0.7584)) or
((snnv >= 10000) and (snnv < 1000000) and (sdiv > 0.8169))
or
((snnv >= 1000000) and (sdiv > 0.9784)))
cannot reliable use kkesdv to scale the value
else
can use kkesdv scaling reliably
nnv := snnv / p
if((sndv = snnv) and
((snnv >= 29472) or
((nnv < 10000) and (snnv >= 708)) or
((nnv < 40000) and (snnv >= 1813)) or
((nnv < 160000) and (snnv >= 4596)) or
((nnv < 640000) and (snnv >= 11664)))) then
can use linear scaling reliably -- ndv := sndv * 1/p
else
cannot reliably use linear scaling to scale the value
The following comprises pseudocode for an embodiment of the kkesdr scaling function:
x1 := sndv
x2 := nnv
stay_loop := true
while (stay_loop and (x1 <= x2)
x := floor ( (x2 + x1)/2)
y2 := x * (1-power(1-(1/x), snnv))
if(sndv < y2)
x2 := x-1
elseif (sndv > y2)
x1 := x + 1
else
stay_loop := false
ndv := x
The execute_hist( ) function determines whether a histogram should be collected. The following comprises pseudocode for an embodiment of the execute_hist( ) function:
for each column with the histogram bit set
if((p < 1.0) and (snnv < 2500))
not enough data -- bump up p for next pass accordingiy
else
if # buckets specified via an integer or repeat
set mnb to that value
else
set mnb to min(75,(max(200, snnv/26)))
estimate the ndv based on prior information if available
if(estimated ndv < (mnb * 0.75)) -- probably a frequency
histogram execute_frequency( )
if still need to collect histogram
execute_height( )
As before, the pseudocode checks whether 2500 rows have been collected during the sampling process. If not, then the sampling fraction (p) is increased for the next pass through the table. The maximum number of buckets (mnb) is set as shown in the pseudocode. The number of distinct values (ndv) is estimated, possibly based upon a previous pass through the table and the prior execution of the evaluate_basic( ) function. If it is desired to collect a histogram and the estimated ndv value is below a given threshold (mnb*0.75), then a frequency histogram is generated in an embodiment. A frequency histogram is often appropriate for a column having a small number of distinct values. In a frequency histogram, the endpoints of multiple buckets have the same endpoint value (because the same value entry is in multiple buckets). For this reason, buckets having the same endpoint values often do not need an explicitly expressed endpoint. This provides one or more "bucket gaps" in the histogram that allows comparatively cheap storage and compressed representation of such frequency histograms. If this type of data distribution is identified, then the process preferably creates a frequency histogram using the execute_frequency( ) function. If it is desired to collect a histogram and the ndv value is greater than an established threshold, then the procedure generates a height-balanced histogram using the execute_height( ) function in an embodiment of the invention. The following comprises pseudocode for an embodiment of the execute_frequency( ) function:
build up frequency query and execute it
if (ndv <= mnb) -- have a good frequency histogram
clear histogram collection bit
The following pseudocode can be used to build up a frequency query according to an embodiment of the invention:
select c, count(*)
from t sample (s)
where c is not null
group by c
order by c;
This query collects column values from a table and performs a count of the values. The following comprises pseudocode for an embodiment of the execute_height( ) function:
build up a height-balanced query and execute it
check for non-uniformity
if non-uniformity exists
try to scale the multiplicative inverse of the density
if it can be successfully scaled -- histogram is ready
clear histogram collection bit
else
clear histogram collection bit -- no histogram needed
In this pseudocode, the column values are checked for non-uniformity. If the column values are uniform, then no histogram is collected. Otherwise, the pseudocode attempts to scale the multiplicative inverse of the density using the previously described process for scaling ndv. In prior evaluations, the number of repetitions was considered uniform over the values; but once histograms are introduced, the popular values can be removed to remove influence upon non-popular values in the histogram. According to an embodiment, a popular value is a value that corresponds to more than one endpoint in a height-balanced histogram. All values that are not popular are considered non-popular. Density is the expected number of repeated occurrences of a non-popular value. In one embodiment, density can be calculated as the sum of the square of the repetition counts for non-popular values divided by the product of the number of rows in the table and the number of non-popular values in the table. The following comprises pseudocode for building up a height-balanced query according to one embodiment of the invention:
select maxbkt, min(value) minval, max(value) maxval,
sum(rep) sumrep, sum(repsq) sumrepsq, max(rep) maxrep, count(*)
bktndv from (
select value, max(bkt) maxbkt,
count(value) rep, count(value)* count(value) repsq
from (
select c as value, ntile(mnb) over (order by c) bkt
from t sample(s)
where c is not null
)
group by value;
)
group by maxbkt
order by maxbkt;
Here, the inner select statement calls an ntile( ) function, which creates a height-balanced histogram and places data sample values into appropriate buckets in the histogram. In an embodiment, such a function creates an uncompressed histogram and returns a number representing the bucket that a value falls into. The repetition counts (and square of repetition counts) are selected in the middle statement. The outer loop performs a count and checks the values and buckets for the result set. The max and min values for the buckets are reviewed to obtain the histogram endpoints. Density, which is related to the selectivity of non-popular values in the data sample, is calculated in this procedure using the function results from the outer loop. This is computed in an embodiment by looking at the number of repetitions of a non-popular value. The result of this query is that one row is obtained per bucket, with missing buckets coming from the more popular values. Each row will have the minimum and maximum value for that bucket, along with the number of rows in that bucket, the sum of the repetition counts and square of the repetition counts for rows in that bucket, and the number of repetitions for the most popular value in that bucket. All missing buckets have been folded into the nearest bucket that is larger. For example, consider if the process ends up with the following:
maxbkt minval maxval sumrep sumrepsq maxrep
1 1 2 2 2 1
4 3 4 9 65 8
5 5 5 3 9 3
6 6 8 4 6 2
8 9 10 6 20 4
This would mean that the number 3 is popular because it is the largest value in the missing buckets 2 and 3. Notice that the number 9 is not a popular value because it is only the largest value of a single bucket, bucket 7, and thus would only appear once as a histogram endpoint. To calculate density, the influence of the popular value, 3, would be removed. Since the value 3 appears 8 times, the number 8 is subtracted from the sumrep sum and 64 (square of 8) from the sumrepsq sum. This enables the computation at a density which is based upon the number of rows in the table, the number of non-popular values in the column, and the sum of the square of the repetition counts of non-popular values. The following pseudocode provides an illustrative embodiment of the invention for histogram determination that was generally described with respect to FIG. 4.
for each column, c, for which a histogram is considered
if the user has specified size
create and save a histogram with number of buckets = requested
size
else if the user has specified size repeat
if c already has a histogram with b buckets
create and save a histogram with b buckets
else if the user has specified size skewonly
create a histogram
if the created histogram exhibits equality or range skew
save it in the dictionary
else if the user has specified size auto
check the dictionary for column usage information
if c has been in a predicate involving an equality, range, or like
create a histogram
if c appeared in an equality (including equijoin) predicate
if the histogram exhibits non-uniformity in value
repetition save it in the dictionary
if c appeared in a like or range predicate (not involving
join)
if the histogram exhibits non-uniformity in range
save it in the dictionary
any prior histogram on c will be removed
The first portion of the pseudocode relates to specific instructions from a user to create a histogram, which results in the creation of the desired histogram. The specific histogram is created without a determination as to whether it is actually needed. Alternatively, the invention can be adapted to automatically check whether a histogram specifically called for by a user should actually be collected and/or saved. The second portion of the pseudocode relates to automated determination of histogram collection. In this illustrative embodiment, the following items of information are utilized for histogram determination: 1) the subset of columns for which the user wants to gather statistics; 2) the columns which already have histograms created for them; 3) column usage information; and 4) the distribution of data, e.g., as seen in a data sample. Because data distribution information is involved, this process may be advantageously used in conjunction with the process of FIG. 2 for automated sample size determination. In the illustrative embodiment, column usage information is considered in conjunction with data distribution information for that column to determine whether a histogram should be collected and stored. Column usage information includes, for example, the type of predicates that is executed against the column. The data skew of the column is evaluated against the type of predicate for that column to determine whether a histogram is needed. When parsing a statement for the first time in an embodiment, the cost-based optimizer looks at the statistics on all of the objects (tables, columns, etc.) involved in the statement. For each column in the where clause, it will estimate the selectivity of the predicate involving that column. At this point, the system will make an entry in the data structure for the column indicating what type of predicate it was involved in. In an embodiment, column usage information is collected every time a user hard-parses a statement, in which a bit is marked in memory for the column usage information. Whenever information is flushed to disk, these bits indicate whether to increment the appropriate dictionary columns. For example, if a query containing a column with a range predicate was hard parsed since the last flush, the system will increment the range_predicate counter for that column when the next flush procedure takes place, as well as updating the timestamp. One reason for using counters on disk is to provide a better feel for the importance of the predicate. Counters can also be used in memory, but may result in expensive overhead. In the illustrative pseudocode, a histogram is created if the column is involved in equality, range, or like predicates. In an embodiment, the histogram is created based on a sampled portion of the column, and is preferably created using a small sample of the entire population that is sufficient to both determine the need for histograms and produce histograms which are representative of the entire population. The number of buckets in the histogram could be based on the sample size. The range max and min is selected based upon the data samples. Values in the data samples are placed into the selected buckets. The process then counts the number of equi-height endpoints that fall within the equi-width buckets. The buckets are reviewed to determine if any buckets are overly large or small. If so, then it is likely that the column does not have uniform data distribution, thereby indicating range skew. In addition, the act of creating a histogram also provides an estimate for the number of distinct values, providing an extra benefit even if the histogram is later discarded. If an equality or equijoin predicate is involved, then the histogram is saved only if the histogram exhibits non-uniformity in value repetition. For purposes of this example, a column will be considered to have non-uniform value repetition if any value is popular, e.g., repeats as an endpoint in the histogram. If a like or range predicate is involved, then the histogram is saved only if the histogram exhibits non-uniformity in range. In one embodiment, a column is considered to have non-uniformity in range if it passes the following test:
given that the created histogram had b equi-height buckets
divide the range (max-min) into b equi-width buckets
sum = 0
for each equiwidth bucket
count the number of equi-height endpoints that fall in the bucket
sum += (count * count)
if(sum / b)>1.7
this column is considered to be non-uniform in range
For a uniform column, the equi-height endpoints would coincide with the equi-width endpoints, and the sum would simply be b. SYSTEM ARCHITECTURE OVERVIEW Referring to FIG. 5, in an embodiment, a computer system 520 includes a host computer 522 connected to a plurality of individual user stations 524. In an embodiment, the user stations 524 each comprise suitable data terminals, for example, but not limited to, e.g., personal computers, portable laptop computers, or personal data assistants ("PDAs"), which can store and independently run one or more applications, i.e., programs. For purposes of illustration, some of the user stations 524 are connected to the host computer 522 via a local area network ("LAN") 526. Other user stations 524 are remotely connected to the host computer 522 via a public telephone switched network ("PSTN") 528 and/or a wireless network 530. In an embodiment, the host computer 522 operates in conjunction with a data storage system 531, wherein the data storage system 531 contains a database 532 that is readily accessible by the host computer 522. Note that a multiple tier architecture can be employed to connect user stations 524 to a database 532, utilizing for example, a middle application tier (not shown). In alternative embodiments, the database 532 may be resident on the host computer, stored, e.g., in the host computer's ROM, PROM, EPROM, or any other memory chip, and/or its hard disk. In yet alternative embodiments, the database 532 may be read by the host computer 522 from one or more floppy disks, flexible disks, magnetic tapes, any other magnetic medium, CD-ROMs, any other optical medium, punchcards, papertape, or any other physical medium with patterns of holes, or any other medium from which a computer can read. In an alternative embodiment, the host computer 522 can access two or more databases 532, stored in a variety of mediums, as previously discussed. Referring to FIG. 6, in an embodiment, each user station 524 and the host computer 522, each referred to generally as a processing unit, embodies a general architecture 605. A processing unit includes a bus 606 or other communication mechanism for communicating instructions, messages and data, collectively, information, and one or more processors 607 coupled with the bus 606 for processing information. A processing unit also includes a main memory 608, such as a random access memory (RAM) or other dynamic storage device, coupled to the bus 606 for storing dynamic data and instructions to be executed by the processor(s) 607. The main memory 608 also may be used for storing temporary data, i.e., variables, or other intermediate information during execution of instructions by the processor(s) 607. A processing unit may further include a read only memory (ROM) 609 or other static storage device coupled to the bus 606 for storing static data and instructions for the processor(s) 607. A storage device 610, such as a magnetic disk or optical disk, may also be provided and coupled to the bus 606 for storing data and instructions for the processor(s) 607. A processing unit may be coupled via the bus 606 to a display device 611, such as, but not limited to, a cathode ray tube (CRT), for displaying information to a user. An input device 612, including alphanumeric and other columns, is coupled to the bus 606 for communicating information and command selections to the processor(s) 607. Another type of user input device may include a cursor control 613, such as, but not limited to, a mouse, a trackball, a fingerpad, or cursor direction columns, for communicating direction information and command selections to the processor(s) 607 and for controlling cursor movement on the display 611. According to one embodiment of the invention, the individual processing units perform specific operations by their respective processor(s) 607 executing one or more sequences of one or more instructions contained in the main memory 608. Such instructions may be read into the main memory 608 from another computer-usable medium, such as the ROM 609 or the storage device 610. Execution of the sequences of instructions contained in the main memory 608 causes the processor(s) 607 to perform the processes described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and/or software. The term "computer-usable medium," as used herein, refers to any medium that provides information or is usable by the processor(s) 607. Such a medium may take many forms, including, but not limited to, non-volatile, volatile and transmission media. Non-volatile media, i.e., media that can retain information in the absence of power, includes the ROM 609. Volatile media, i.e., media that can not retain information in the absence of power, includes the main memory 608. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise the bus 606. Transmission media can also take the form of carrier waves; i.e., electromagnetic waves that can be modulated, as in frequency, amplitude or phase, to transmit information signals. Additionally, transmission media can take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications. Common forms of computer-usable media include, for example: a floppy disk, flexible disk, hard disk, magnetic tape, any other magnetic medium, CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, RAM, ROM, PROM (i.e., programmable read only memory), EPROM (i.e., erasable programmable read only memory), including FLASH-EPROM, any other memory chip or cartridge, carrier waves, or any other medium from which a processor 607 can retrieve information. Various forms of computer-usable media may be involved in providing one or more sequences of one or more instructions to the processor(s) 607 for execution. The instructions received by the main memory 608 may optionally be stored on the storage device 610, either before or after their execution by the processor(s) 607. Each processing unit may also include a communication interface 614 coupled to the bus 606. The communication interface 614 provides two-way communication between the respective user stations 624 and the host computer 622. The communication interface 614 of a respective processing unit transmits and receives electrical, electromagnetic or optical signals that include data streams representing various types of information, including instructions, messages and data. A communication link 615 links a respective user station 624 and a host computer 622. The communication link 615 may be a LAN 526, in which case the communication interface 614 may be a LAN card. Alternatively, the communication link 615 may be a PSTN 528, in which case the communication interface 614 may be an integrated services digital network (ISDN) card or a modem. Also, as a further alternative, the communication link 615 may be a wireless network 530. A processing unit may transmit and receive messages, data, and instructions, including program, i.e., application, code, through its respective communication link 615 and communication interface 614. Received program code may be executed by the respective processor(s) 607 as it is received, and/or stored in the storage device 610, or other associated non-volatile media, for later execution. In this manner, a processing unit may receive messages, data and/or program code in the form of a carrier wave.
|
Same subclass Same class Consider this |
||||||||||