Details
-
Task
-
Status: Open (View Workflow)
-
Major
-
Resolution: Unresolved
-
None
Description
Histograms with equal-width bins are easy to construct using samples. For this it's enough
to look through the given sample set and for each value from it to figure out what bin this value can be placed in. Each bin requires only one counter.
Let f be a column of a table with N rows and n be the number of samples by which the equal-width histogram of k bins for this column is constructed. Let after looking through all sample
rows the counters created for the histogram bins contain numbers c[1],..,c[k]. Then
m[i]= c[i]/n * 100 is the percentage of the rows whose values of f are expected to be in the interval
(max(f)-min(f))/k *(i-1), max(f)-min(f))/k *i-1).
|
It means that if the sample rows have been chosen randomly the expected number of rows with the values of f from this interval can be approximated by the number m[i]*/100 * N.
To collect such statistics it is suggested to use the following variant of the ANALYZE TABLE command:
ANALYZE FAST TABLE tbl [ WITH n ROWS ] [SAMPLING p PERCENTS ]
|
PERSISTENT FOR COLUMNS (col1 [IN RANGE r] [WITH k INTERVALS],...)
|
Here:
- 'WITH n ROWS' provides an estimate for the number of rows in the table in the case when this estimate cannot be obtained from statistical data.
- 'SAMPLING p PERCENTS' provides the percentage of sample rows to collect statistics.
If this is omitted the number is taken from the system variable samples_ratio. - 'IN RANGE r' sets the range of equal-width bins of the histogram built for the column col1. If this is omitted then and min and max values for the column can be read from statistical data
then the histogram is built for the range [min(col1), max(col1)]. Otherwise the range [MIN_type(col1), MAX_type(col1) is considered]. The values beyond the given range, if any, are also is taken into account in two additional bins. - WITH k INTERVALS says how many bins are included in the histogram. If it is omitted this value is taken from the system variable histogram_size.
Attachments
Activity
Project Update
All changes are on the MariaDB 10.3 fork on my GitHub page:
https://github.com/teodorniculescu/server
Commit hash:
8cb57d3b3f7e2fea02e3851e8f67a94845d549ff
What is new:
- created a new function 'collect_fast_statistics_for_table' which creates Equal-Width Histograms (sql/sql_statistics.cc);
- the function is called by the 'ANALYZE FAST' query;
- the Equal-Width Histogram is stored in the same data structure as the equal-height histogram (uchar* values);
- the Equal-Width Histogram is constructed using a full table scan;
- works with both Single and Double precision (as shown in the test case mysql-test/t/analyze_fast.test);
Follow-up:
- change the function in order to samples values;
- add a lot of values (~10.000) to the test case in order to show that it works as intended;
- toggle sampling according to the number of entries in the table (if there are too few entries, there is no need for sampling);
Any advice, criticism or questions will be greatly appreciated!
Notes from discussion with Igor
- How will the code compute the estimated number of distinct values from the sample? (there's a formula for that. are we using it?)
- What is the overhead of doing a full table scan as opposed to doing sampling (need to experiment)?
- Using a secondary index to drive sampling as opposed to using a primary: this is beneficial because the secondary index is smaller.
- PG's approach is not "sample X% of the table". They sample ~30K rows regardless of table size (there's a paper that says sufficient sample size is ~log(table_rows)).
- mysql.column_stats.histogram. Do we keep it VARCHAR(255) or change to a bigger datatype?
Project Update
All changes can be seen on my github page:
https://github.com/teodorniculescu/server
What I have done so far:
ANALYZE FAST TABLE table [ WITH n ROWS ] [ SAMPLING p PERCENT ] [ LASTS s SECONDS ]
PERSISTENT FOR COLUMNS (column_1 [IN RANGE r] [WITH k INTERVALS],...)
Follow-up: