Statistics and Sampling Concepts

Introduction

SingleStore automatically gathers statistics to give the optimizer the information it needs. The system that gathers statistics automatically is known as autostats. The term autostats is also used to describe statistics that are gathered automatically.

It’s almost always best to leave autostats enabled. But if for some reason you don’t want to use autostats, you can disable it. If you turn off autostats, you should use the ANALYZE command to gather statistics manually. Most users can rely on autostats and will never need to run the ANALYZE command.

The ANALYZE command also can be used to trigger plan re-optimization when data statistics change, whether or not autostats is enabled.

Autostat Types

SingleStore automatically collects and updates column statistics on columnstore tables, incrementally in the background. This greatly reduces the operational burden around maintaining these statistics with ANALYZE, ensures they are available without requiring user action, and keeps them up-to-date as table data changes with less performance impact.

Autostats provides automatic maintenance of column statistics. Statistics are collected and incrementally updated in the background as the table is modified with DML statements such as INSERT, UPDATE, DELETE, LOAD DATA, and TRUNCATE, as well as ALTER TABLE.

While statistics are updated automatically, to re-optimize query plans after statistics change, you must trigger plan invalidation by running ANALYZE.

Running ANALYZE also saves a copy of the table’s current automatic statistics. If you disable automatic statistics or they become out-of-date (see below), the query optimizer will use the last set of statistics saved by ANALYZE instead.

SingleStore uses three types of autostats:

+-----------------------+--------------+------+------+---------+-------+
| Field                 | Type         | Null | Key  | Default | Extra |
+-----------------------+--------------+------+------+---------+-------+
| DATABASE_NAME         | varchar(512) | NO   |      | NULL    |       |
| TABLE_NAME            | varchar(512) | NO   |      | NULL    |       |
| COLUMN_NAME           | varchar(512) | NO   |      | NULL    |       |
| ROW_COUNT             | bigint(21)   | YES  |      | NULL    |       |
| NULL_COUNT            | bigint(21)   | YES  |      | NULL    |       |
| CARDINALITY           | bigint(21)   | YES  |      | NULL    |       |
| AUTOSTATS_ENABLED     | tinyint(1)   | YES  |      | NULL    |       |
| AUTOSTATS_OUTDATED    | tinyint(1)   | YES  |      | NULL    |       |
| AUTOSTATS_ROW_COUNT   | bigint(21)   | YES  |      | NULL    |       |
| AUTOSTATS_NULL_COUNT  | bigint(21)   | YES  |      | NULL    |       |
| AUTOSTATS_CARDINALITY | bigint(21)   | YES  |      | NULL    |       |
| ADVANCED_HISTOGRAMS   | bigint(21)   | YES  |      | NULL    |       |
| LEGACY_HISTOGRAMS     | bigint(21)   | YES  |      | NULL    |       |
| RANGE_STATS           | bigint(21)   | YES  |      | NULL    |       |
| SAMPLE_SIZE           | bigint(21)   | YES  |      | NULL    |       |
| LAST_UPDATED          | datetime     | YES  |      | NULL    |       |
+-----------------------+--------------+------+------+---------+-------+

+-------------------------+---------------+------+------+---------+-------+
| Field                   | Type          | Null | Key  | Default | Extra |
+-------------------------+---------------+------+------+---------+-------+
| DATABASE_NAME           | varchar(512)  | NO   |      | NULL    |       |
| TABLE_NAME              | varchar(512)  | NO   |      | NULL    |       |
| COLUMN_NAME             | varchar(512)  | NO   |      | NULL    |       |
| TYPE                    | varchar(255)  | NO   |      | NULL    |       |
| VERSION                 | bigint(21)    | NO   |      | NULL    |       |
| BUCKET_COUNT            | bigint(21)    | NO   |      | NULL    |       |
| BUCKET_INDEX            | bigint(21)    | NO   |      | NULL    |       |
| RANGE_MIN               | varchar(8192) | YES  |      | NULL    |       |
| RANGE_MAX               | varchar(8192) | YES  |      | NULL    |       |
| UNIQUE_COUNT            | double        | YES  |      | NULL    |       |
| CARDINALITY             | double        | YES  |      | NULL    |       |
| UNIQUE_COUNT_CUMULATIVE | double        | YES  |      | NULL    |       |
| CARDINALITY_CUMULATIVE  | double        | YES  |      | NULL    |       |
+-------------------------+---------------+------+------+---------+-------+

SELECT DISTINCT DATABASE_NAME, TABLE_NAME, COLUMN_NAME
    FROM information_schema.ADVANCED_HISTOGRAMS;

Histograms vs Sampling

If histograms are unavailable, the optimizer will use a sample to compute estimates. For rowstore tables, it will use dynamic sampling (i.e. sample the table data by scanning part of the table) to compute estimates. For columnstore tables, it will use the stored columnstore sample.

Histograms are much faster to use than sampling during query optimization, since the optimizer merely needs to read the previously-collected histograms, which are relatively small objects, while sampling may require scanning a large amount of table data.

Whether histogram-based estimates or sampling-based estimates are more accurate depends on the table and query. For example, histograms are most effective on columns where the overall distribution of data is not changing quickly (even if the data itself is changing quickly). When the data distribution is changing, if autostats is disabled, it is important to periodically update histograms to reflect changes in data by re-running ANALYZE TABLE.

Conversely, histograms are least effective on columns where the data distribution is quickly and continuously changing. For example, a typical case where histograms are generally inaccurate and not recommended is on columns where the range of data is continuously growing, such as a timestamp or ID column where new, ever-increasing values are continuously being added. Histograms only reflect the range of data at the time the histograms were last updated, so new values outside that range are not reflected in the histograms. This leads to inaccurate estimates for queries that filter for this recent data. For these types of columns, leaving histograms disabled, which means sampling is used instead, typically leads to the best results.

Also, since histograms are one-dimensional, they cannot capture correlation between columns. Sampling can estimate predicates that feature a high degree of correlation between columns more accurately than histograms.

Finally, sampling may be inaccurate on predicates that are highly selective, or that have a high degree of skew between partitions. Histograms are typically more accurate on these predicates.

Plan Invalidation

When data statistics change, an old query plan optimized based on the old data statistics may no longer be the best for the new data statistics. It is often desirable to re-optimize the query plan after the data statistics change significantly, as a new plan may be significantly better than the old plan. Running ANALYZE triggers re-optimization of any plans based on statistics for that table that are significantly different than the current statistics, by invalidating each such plan and recompiling the corresponding query the next time it is run.

Plans can be invalidated manually by running the ANALYZE command. To automatically invalidate the plan as autostats update, set the enable_background_plan_invalidation variable to ON. By default, this variable is set to OFF to prevent unexpected recompilation of plans when data changes.

SingleStore uses changes in the table rowcount as a heuristic for significant changes in statistics: a plan is eligible for invalidation if there is a table rowcount differing by a factor of 2 between the statistics it was compiled with and the current statistics, i.e. if an old rowcount (from the statistics at the time the query was compiled) is less than 50% or greater than 200% of the current rowcount. When you run ANALYZE, all plans eligible for invalidation (i.e. those where the current statistics and compile-time statistics differ in any table rowcount by at least 2x) are invalidated, i.e. they will be reoptimized and recompiled the next time they are run.

In addition, if autostats on a table were outdated when the plan was compiled, the plan will be eligible for invalidation after autostats become up-to-date (i.e. after autostats become up-to-date and you run ANALYZE, the plan will be invalidated).

Also, running SHOW PLANCACHE will display any existing plans. If there are any plans you wish to invalidate, running DROP <plan_id> FROM PLANCACHE will invalidate that plan. If you run DROP ALL FROM PLANCACHE that will drop all valid plans. See DROP … FROM PLANCACHE for more details.

Correlation Statistics

Correlated columns mean the value of one column depends on the value of another column to some degree. This dependency typically arises from an inherent hierarchical relationship. For example, the values in a "zip code" column would be potentially 100% correlated with a "state" column.

Optimizing queries containing correlated columns can be challenging. Filters applied to multiple columns exhibit varied combinations based on the correlation levels between those respective columns. Correlation statistics allow the optimizer to improve the query plan of certain queries that filter on multiple columns that are related to each other.

Consider a scenario where 30% of a company's customers reside in California, resulting in a 30% selectivity when filtering by state = "CA." However, if the query additionally filters by zip code within California, the selectivity may drastically drop. In cases of uncorrelated columns, the optimizer combines these estimates through multiplication, resulting in a significantly lower overall selectivity which can lead to less efficient query plans. In queries where the filtered columns have a strong correlation, such as states and zip codes, the state filter becomes redundant. It is prudent to adopt the more selective filter's selectivity for a more accurate estimation and efficient execution plan, leading to better overall performance.

Optimizing the query plan can be achieved by using statistics that account for correlated column relationships and dependencies within a query predicate. Correlation coefficients can be added between columns to fine-tune how the optimizer combines the selectivity of single-column filters when using histogram estimation. At a high level, the optimizer must create an estimate of what portion of each base table will be read during query execution (the selectivity, measured between 0 and 1).

The optimizer defaults the correlation coefficient to 0.5 between any two columns. This feature allows the user to change the correlation coefficient for any set of two columns in a table.

Consider the tables and query:

CREATE TABLE inventory (
    id INT
    , model_year INT
    , make VARCHAR(10)
    , model VARCHAR(20)
    , SHARD KEY(id) 
    , SORT KEY(model));

CREATE TABLE sales (
    s_id INT PRIMARY KEY,
    i_id INT
    , sales_month FLOAT
    , monthly_sales FLOAT
    ,yearly_sales AS (monthly_sales * 12) PERSISTED FLOAT
    , SORT KEY(sales_month));

SELECT inventory.model_year, inventory.make, inventory.model, sales.sales_month, sales.montly_sales
    FROM inventory JOIN sales ON inventor.id = sales.i_id
    WHERE inventory.model = 'Honda' AND inventory.make = 'Accord'; 

In this case, the optimizer should disregard the inventory.model filter in estimations as it is functionally determined by inventory.make and use the correlation statistics functionality to correlate inventory.model and inventory.make with a coefficient of 1.

To set the correlation coefficient, run the following command. Refer to the ANALYZE page for more details:

ANALYZE TABLE inventory CORRELATE COLUMN inventory.model WITH COLUMN inventory.make USING COEFFICIENT 1.0;

To view the correlation coefficient set between two columns on a table, run the information_schema.correlated_column_statistics statement:

SELECT * FROM information_schema.correlated_column_statistics;

+---------------+------------+------------------------+-----------------------+-------------------|---------------------+
| DATABASE_NAME	| TABLE_NAME | CORRELATED_COLUMN_NAME | CORRELLEE_COLUMN_NAME |	CORRELATION_COEFF | CREATED_TIME        |
+---------------+------------+------------------------+-----------------------+-------------------+---------------------+
| test1         | inventory  | model                  | make                  | 1                 | 2023-12-07 22:02:31 |
+---------------+------------+------------------------+-----------------------+-------------------+---------------------+