Как определяется количество шагов гистограммы в статистике

Как определяется количество шагов гистограммы в статистике в SQL Server?

Почему он ограничен 200 шагами, хотя мой ключевой столбец имеет более 200 различных значений? Есть ли решающий фактор?

демонстрация

Определение схемы

CREATE TABLE histogram_step
  (
     id   INT IDENTITY(1, 1),
     name VARCHAR(50),
     CONSTRAINT pk_histogram_step PRIMARY KEY (id)
  )

Вставка 100 записей в мою таблицу

INSERT INTO histogram_step
            (name)
SELECT TOP 100 name
FROM   sys.syscolumns

Обновление и проверка статистики

UPDATE STATISTICS histogram_step WITH fullscan

DBCC show_statistics('histogram_step', pk_histogram_step)

Шаги гистограммы:

+--------------+------------+---------+---------------------+----------------+
| RANGE_HI_KEY | RANGE_ROWS | EQ_ROWS | DISTINCT_RANGE_ROWS | AVG_RANGE_ROWS |
+--------------+------------+---------+---------------------+----------------+
|            1 |          0 |       1 |                   0 |              1 |
|            3 |          1 |       1 |                   1 |              1 |
|            5 |          1 |       1 |                   1 |              1 |
|            7 |          1 |       1 |                   1 |              1 |
|            9 |          1 |       1 |                   1 |              1 |
|           11 |          1 |       1 |                   1 |              1 |
|           13 |          1 |       1 |                   1 |              1 |
|           15 |          1 |       1 |                   1 |              1 |
|           17 |          1 |       1 |                   1 |              1 |
|           19 |          1 |       1 |                   1 |              1 |
|           21 |          1 |       1 |                   1 |              1 |
|           23 |          1 |       1 |                   1 |              1 |
|           25 |          1 |       1 |                   1 |              1 |
|           27 |          1 |       1 |                   1 |              1 |
|           29 |          1 |       1 |                   1 |              1 |
|           31 |          1 |       1 |                   1 |              1 |
|           33 |          1 |       1 |                   1 |              1 |
|           35 |          1 |       1 |                   1 |              1 |
|           37 |          1 |       1 |                   1 |              1 |
|           39 |          1 |       1 |                   1 |              1 |
|           41 |          1 |       1 |                   1 |              1 |
|           43 |          1 |       1 |                   1 |              1 |
|           45 |          1 |       1 |                   1 |              1 |
|           47 |          1 |       1 |                   1 |              1 |
|           49 |          1 |       1 |                   1 |              1 |
|           51 |          1 |       1 |                   1 |              1 |
|           53 |          1 |       1 |                   1 |              1 |
|           55 |          1 |       1 |                   1 |              1 |
|           57 |          1 |       1 |                   1 |              1 |
|           59 |          1 |       1 |                   1 |              1 |
|           61 |          1 |       1 |                   1 |              1 |
|           63 |          1 |       1 |                   1 |              1 |
|           65 |          1 |       1 |                   1 |              1 |
|           67 |          1 |       1 |                   1 |              1 |
|           69 |          1 |       1 |                   1 |              1 |
|           71 |          1 |       1 |                   1 |              1 |
|           73 |          1 |       1 |                   1 |              1 |
|           75 |          1 |       1 |                   1 |              1 |
|           77 |          1 |       1 |                   1 |              1 |
|           79 |          1 |       1 |                   1 |              1 |
|           81 |          1 |       1 |                   1 |              1 |
|           83 |          1 |       1 |                   1 |              1 |
|           85 |          1 |       1 |                   1 |              1 |
|           87 |          1 |       1 |                   1 |              1 |
|           89 |          1 |       1 |                   1 |              1 |
|           91 |          1 |       1 |                   1 |              1 |
|           93 |          1 |       1 |                   1 |              1 |
|           95 |          1 |       1 |                   1 |              1 |
|           97 |          1 |       1 |                   1 |              1 |
|           99 |          1 |       1 |                   1 |              1 |
|          100 |          0 |       1 |                   0 |              1 |
+--------------+------------+---------+---------------------+----------------+

Как мы видим, в гистограмме 53 шага.

Снова вставив несколько тысяч записей

INSERT INTO histogram_step
            (name)
SELECT TOP 10000 b.name
FROM   sys.syscolumns a
       CROSS JOIN sys.syscolumns b

Обновление и проверка статистики

UPDATE STATISTICS histogram_step WITH fullscan

DBCC show_statistics('histogram_step', pk_histogram_step)

Теперь шаги гистограммы уменьшены до 4 шагов

+--------------+------------+---------+---------------------+----------------+
| RANGE_HI_KEY | RANGE_ROWS | EQ_ROWS | DISTINCT_RANGE_ROWS | AVG_RANGE_ROWS |
+--------------+------------+---------+---------------------+----------------+
|            1 |          0 |       1 |                   0 |              1 |
|        10088 |      10086 |       1 |               10086 |              1 |
|        10099 |         10 |       1 |                  10 |              1 |
|        10100 |          0 |       1 |                   0 |              1 |
+--------------+------------+---------+---------------------+----------------+

Снова вставив несколько тысяч записей

INSERT INTO histogram_step
            (name)
SELECT TOP 100000 b.name
FROM   sys.syscolumns a
       CROSS JOIN sys.syscolumns b

Обновление и проверка статистики

UPDATE STATISTICS histogram_step WITH fullscan

DBCC show_statistics('histogram_step', pk_histogram_step) 

Теперь шаги гистограммы сокращены до 3 шагов

+--------------+------------+---------+---------------------+----------------+
| RANGE_HI_KEY | RANGE_ROWS | EQ_ROWS | DISTINCT_RANGE_ROWS | AVG_RANGE_ROWS |
+--------------+------------+---------+---------------------+----------------+
|            1 |          0 |       1 |                   0 |              1 |
|       110099 |     110097 |       1 |              110097 |              1 |
|       110100 |          0 |       1 |                   0 |              1 |
+--------------+------------+---------+---------------------+----------------+

Может кто-нибудь сказать мне, как решаются эти шаги?

Я собираюсь ограничить этот пост обсуждением статистики по одному столбцу, потому что она уже будет довольно продолжительной, и вас интересует, как SQL Server объединяет данные в шаги гистограммы. Для многостолбцовой статистики гистограмма создается только в верхнем столбце.

Когда SQL Server определяет необходимость обновления статистики, он запускает скрытый запрос, который считывает либо все данные таблицы, либо образец данных таблицы. Вы можете просматривать эти запросы с расширенными событиями. В StatManSQL Server вызывается функция , связанная с созданием гистограмм. Для простых объектов статистики существует как минимум два разных типа StatManзапросов (существуют разные запросы для быстрого обновления статистики, и я подозреваю, что функция инкрементной статистики в многораздельных таблицах также использует другой запрос).

Первый просто берет все данные из таблицы без какой-либо фильтрации. Вы можете увидеть это, когда таблица очень мала или вы собираете статистику с FULLSCANопцией:

CREATE TABLE X_SHOW_ME_STATMAN (N INT);
CREATE STATISTICS X_STAT_X_SHOW_ME_STATMAN ON X_SHOW_ME_STATMAN (N);

-- after gathering stats with 1 row in table
SELECT StatMan([SC0]) FROM
(
    SELECT TOP 100 PERCENT [N] AS [SC0] 
    FROM [dbo].[X_SHOW_ME_STATMAN] WITH (READUNCOMMITTED)
    ORDER BY [SC0] 
) AS _MS_UPDSTATS_TBL 
OPTION (MAXDOP 16);

SQL Server выбирает автоматический размер выборки на основе размера таблицы (я думаю, что это и количество строк и страниц в таблице). Если таблица слишком большая, то автоматический размер выборки падает ниже 100%. Вот что я получил для той же таблицы с 1М строк:

-- after gathering stats with 1 M rows in table
SELECT StatMan([SC0], [SB0000]) FROM 
(
    SELECT TOP 100 PERCENT [SC0], step_direction([SC0]) over (order by NULL) AS [SB0000] 
    FROM 
    (
        SELECT [N] AS [SC0] 
        FROM [dbo].[X_SHOW_ME_STATMAN] TABLESAMPLE SYSTEM (6.666667e+001 PERCENT) WITH (READUNCOMMITTED) 
    ) AS _MS_UPDSTATS_TBL_HELPER 
    ORDER BY [SC0], [SB0000] 
) AS _MS_UPDSTATS_TBL
OPTION (MAXDOP 1);

TABLESAMPLEэто документально , но Statman и step_direction нет. здесь SQL Server выбирает около 66,6% данных из таблицы для создания гистограммы. Это означает, что вы можете получить различное количество шагов гистограммы при обновлении статистики (без FULLSCAN) для одних и тех же данных. Я никогда не наблюдал это на практике, но я не понимаю, почему это было бы невозможно.

Давайте проведем несколько тестов на простых данных, чтобы увидеть, как статистика меняется со временем. Ниже приведен тестовый код, который я написал для вставки последовательных целых чисел в таблицу, сбора статистики после каждой вставки и сохранения информации о статистике в таблицу результатов. Начнем с того, что вставляем по 1 строке за раз до 10000. Тестовый стенд:

DECLARE
@stats_id INT,
@table_object_id INT,
@rows_per_loop INT = 1,
@num_of_loops INT = 10000,
@loop_num INT;

BEGIN
    SET NOCOUNT ON;

    TRUNCATE TABLE X_STATS_RESULTS;

    SET @table_object_id = OBJECT_ID ('X_SEQ_NUM');
    SELECT @stats_id = stats_id FROM sys.stats
    WHERE OBJECT_ID = @table_object_id
    AND name = 'X_STATS_SEQ_INT_FULL';

    SET @loop_num = 0;
    WHILE @loop_num < @num_of_loops
    BEGIN
        SET @loop_num = @loop_num + 1;

        INSERT INTO X_SEQ_NUM WITH (TABLOCK)
        SELECT @rows_per_loop * (@loop_num - 1) + N FROM dbo.GetNums(@rows_per_loop);

        UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN; -- can comment out FULLSCAN as needed

        INSERT INTO X_STATS_RESULTS WITH (TABLOCK)
        SELECT 'X_STATS_SEQ_INT_FULL', @rows_per_loop * @loop_num, rows_sampled, steps 
        FROM sys.dm_db_stats_properties(@table_object_id, @stats_id);
        END;
END;

Для этих данных число шагов гистограммы быстро увеличивается до 200 (сначала оно достигает максимального числа шагов с 397 строками), остается на уровне 199 или 200 до 1485 строк в таблице, затем медленно уменьшается до тех пор, пока гистограмма имеет только 3 или 4 шаги. Вот график всех данных:

Вот как выглядит гистограмма для строк по 10 тыс.

RANGE_HI_KEY    RANGE_ROWS  EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
1               0           1       0                   1
9999            9997        1       9997                1
10000           0           1       0                   1

Проблема в том, что гистограмма имеет только 3 шага? Похоже, информация сохраняется с нашей точки зрения. Обратите внимание, что, поскольку тип данных является INTEGER, мы можем выяснить, сколько строк в таблице для каждого целого числа от 1 до 10000. Как правило, SQL Server может это выяснить, хотя в некоторых случаях это не совсем получается. , Посмотрите этот пост SE для примера этого.

Как вы думаете, что произойдет, если мы удалим одну строку из таблицы и обновим статистику? В идеале мы получили бы еще один шаг гистограммы, чтобы показать, что отсутствующее целое число больше не находится в таблице.

DELETE FROM X_SEQ_NUM
WHERE X_NUM  = 1000;

UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN;

DBCC SHOW_STATISTICS ('X_SEQ_NUM', 'X_STATS_SEQ_INT_FULL'); -- still 3 steps

DELETE FROM X_SEQ_NUM
WHERE X_NUM  IN (2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000);

UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN;

DBCC SHOW_STATISTICS ('X_SEQ_NUM', 'X_STATS_SEQ_INT_FULL'); -- still 3 steps

Это немного разочаровывает. Если бы мы строили гистограмму вручную, мы добавили бы шаг для каждого пропущенного значения. SQL Server использует алгоритм общего назначения, поэтому для некоторых наборов данных мы можем придумать более подходящую гистограмму, чем код, который он использует. Конечно, практическая разница между получением 0 или 1 строки из таблицы очень мала. Я получаю те же результаты при тестировании с 20000 строками, у каждого из которых целое число имеет 2 строки в таблице. Гистограмма не набирает шаги, когда я удаляю данные.

RANGE_HI_KEY    RANGE_ROWS  EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
1               0           2       0                   1
9999            19994       2       9997                2
10000           0           2       0                   1

Если я тестирую 1 миллион строк, а каждое целое число имеет 100 строк в таблице, я получаю немного лучшие результаты, но я все равно могу построить лучшую гистограмму вручную.

truncate table X_SEQ_NUM;

BEGIN TRANSACTION;
INSERT INTO X_SEQ_NUM WITH (TABLOCK)
SELECT N FROM dbo.GetNums(10000);
GO 100
COMMIT TRANSACTION;

UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN;

DBCC SHOW_STATISTICS ('X_SEQ_NUM', 'X_STATS_SEQ_INT_FULL'); -- 4 steps

DELETE FROM X_SEQ_NUM
WHERE X_NUM  = 1000;

UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN;

DBCC SHOW_STATISTICS ('X_SEQ_NUM', 'X_STATS_SEQ_INT_FULL'); -- now 5 steps with a RANGE_HI_KEY of 998 (?)

DELETE FROM X_SEQ_NUM
WHERE X_NUM  IN (2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000);

UPDATE STATISTICS X_SEQ_NUM X_STATS_SEQ_INT_FULL WITH FULLSCAN;

DBCC SHOW_STATISTICS ('X_SEQ_NUM', 'X_STATS_SEQ_INT_FULL'); -- still 5 steps

Конечная гистограмма:

RANGE_HI_KEY    RANGE_ROWS  EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
1               0           100     0                   1
998             99600       100     996                 100
3983            298100      100     2981                100
9999            600900      100     6009                100
10000           0           100     0                   1

Продолжим тестирование с последовательными целыми числами, но с большим количеством строк в таблице. Обратите внимание, что для таблиц, которые слишком малы, ручное указание размера выборки не окажет никакого влияния, поэтому я буду добавлять 100 строк в каждую вставку и собирать статистику каждый раз до 1 миллиона строк. Я вижу такой же шаблон, как и раньше, за исключением того, что когда я доберусь до 637300 строк в таблице, я больше не буду производить выборку 100% строк в таблице с частотой дискретизации по умолчанию. Когда я набираю строки, количество шагов гистограммы увеличивается. Возможно, это связано с тем, что в SQL Server появляется больше пробелов в данных по мере увеличения числа несэмплированных строк в таблице. Я не пробиваю 200 шагов даже на 1 М строк, но если бы я продолжал добавлять строки, я ожидал, что доберусь до них и в конце концов начну возвращаться вниз.

Ось X - это количество строк в таблице. По мере увеличения количества строк выборка меняется немного и не превышает 650 тыс.

Теперь давайте проведем несколько простых тестов с данными VARCHAR.

CREATE TABLE X_SEQ_STR (X_STR VARCHAR(5));
CREATE STATISTICS X_SEQ_STR ON X_SEQ_STR(X_STR);

Здесь я вставляю 200 чисел (в виде строк) вместе с NULL.

INSERT INTO X_SEQ_STR
SELECT N FROM dbo.GetNums(200)
UNION ALL
SELECT NULL;

UPDATE STATISTICS X_SEQ_STR X_SEQ_STR ;

DBCC SHOW_STATISTICS ('X_SEQ_STR', 'X_SEQ_STR'); -- 111 steps, RANGE_ROWS is 0 or 1 for all steps

Обратите внимание, что NULL всегда получает свой собственный шаг гистограммы, когда он находится в таблице. SQL Server мог дать мне ровно 201 шаг, чтобы сохранить всю информацию, но он этого не сделал. Технически информация теряется, потому что «1111» сортирует, например, между «1» и «2».

Теперь давайте попробуем вставить разные символы вместо целых чисел:

truncate table X_SEQ_STR;

INSERT INTO X_SEQ_STR
SELECT CHAR(10 + N) FROM dbo.GetNums(200)
UNION ALL
SELECT NULL;

UPDATE STATISTICS X_SEQ_STR X_SEQ_STR ;

DBCC SHOW_STATISTICS ('X_SEQ_STR', 'X_SEQ_STR'); -- 95 steps, RANGE_ROWS is 0 or 1 or 2

Никаких реальных отличий от последнего теста.

Теперь давайте попробуем вставить символы, но поместим разные номера каждого символа в таблицу. Например, CHAR(11)имеет 1 строку, CHAR(12)имеет 2 строки и т. Д.

truncate table X_SEQ_STR;

DECLARE
@loop_num INT;

BEGIN
    SET NOCOUNT ON;

    SET @loop_num = 0;
    WHILE @loop_num < 200
    BEGIN
        SET @loop_num = @loop_num + 1;

        INSERT INTO X_SEQ_STR WITH (TABLOCK)
        SELECT CHAR(10 + @loop_num) FROM dbo.GetNums(@loop_num);
    END;
END;

UPDATE STATISTICS X_SEQ_STR X_SEQ_STR ;

DBCC SHOW_STATISTICS ('X_SEQ_STR', 'X_SEQ_STR'); -- 148 steps, most with RANGE_ROWS of 0

Как и раньше, я до сих пор не получаю ровно 200 шагов гистограммы. Тем не менее, многие из шагов имеют RANGE_ROWS0.

Для финального теста я собираюсь вставить случайную строку из 5 символов в каждом цикле и собирать статистику каждый раз. Вот код случайной строки:

char((rand()*25 + 65))+char((rand()*25 + 65))+char((rand()*25 + 65))+char((rand()*25 + 65))+char((rand()*25 + 65))

Вот график строк в таблице против шагов гистограммы:

Обратите внимание, что количество шагов не опускается ниже 100, как только оно начинает подниматься и опускаться. Я откуда-то слышал (но не могу найти его прямо сейчас), что алгоритм построения гистограммы SQL Server объединяет шаги гистограммы, поскольку для них не хватает места. Таким образом, вы можете получить резкие изменения в количестве шагов, просто добавив немного данных. Вот один пример данных, которые мне показались интересными:

ROWS_IN_TABLE   ROWS_SAMPLED    STEPS
36661           36661           133
36662           36662           143
36663           36663           143
36664           36664           141
36665           36665           138

Даже когда выборка с помощью FULLSCANдобавления одной строки может увеличить количество шагов на 10, сохранить его постоянным, затем уменьшить его на 2, а затем уменьшить на 3.

Что мы можем подвести итог всего этого? Я не могу доказать ничего из этого, но эти наблюдения, похоже, верны:

• SQL Server использует алгоритм общего использования для создания гистограмм. Для некоторых распределений данных может быть возможно создать более полное представление данных вручную.
• Если в таблице есть данные NULL, и запрос статистики находит их, тогда данные NULL всегда получают свой шаг гистограммы.
• Минимальное значение, найденное в таблице, получает свой шаг гистограммы с RANGE_ROWS= 0.
• Максимальное значение, найденное в таблице, будет последним RANGE_HI_KEYв таблице.
• Поскольку SQL Server выбирает больше данных, ему может потребоваться объединить существующие шаги, чтобы освободить место для новых данных, которые он находит. Если вы посмотрите на достаточное количество гистограмм, вы можете увидеть повторение общих значений для DISTINCT_RANGE_ROWSили RANGE_ROWS. Например, 255 появляется здесь несколько раз для RANGE_ROWSи DISTINCT_RANGE_ROWSдля финального теста.
• Для простых распределений данных вы можете увидеть, как SQL Server объединяет последовательные данные в один шаг гистограммы, который не вызывает потери информации. Однако при добавлении пробелов в данные гистограмма может не корректироваться так, как вы надеетесь.

Когда все это проблема? Это проблема, когда запрос работает плохо из-за гистограммы, которая не может представить распределение данных таким образом, чтобы оптимизатор запросов мог принять правильные решения. Я думаю, что существует тенденция думать, что иметь больше шагов гистограммы всегда лучше, и возникает ужас, когда SQL Server генерирует гистограмму на миллионах строк или более, но не использует точно 200 или 201 шагов гистограммы. Тем не менее, я видел много проблем со статистикой, даже когда гистограмма имеет 200 или 201 шагов. Мы не имеем никакого контроля над тем, сколько шагов гистограммы генерирует SQL Server для объекта статистики, поэтому я не стал бы беспокоиться об этом. Тем не менее, есть некоторые шаги, которые вы можете предпринять, если у вас возникают неэффективные запросы, вызванные проблемами статистики. Я дам чрезвычайно краткий обзор.

Сбор статистики в полном объеме может помочь в некоторых случаях. Для очень больших таблиц автоматический размер выборки может составлять менее 1% строк в таблице. Иногда это может привести к плохим планам в зависимости от разрушения данных в столбце. Документация Microsoft для CREATE STATISTICS и UPDATE STATISTICS гласит:

SAMPLE полезен в особых случаях, когда план запроса, основанный на выборке по умолчанию, не является оптимальным. В большинстве случаев указывать SAMPLE необязательно, поскольку оптимизатор запросов уже использует выборку и по умолчанию определяет статистически значимый размер выборки, что требуется для создания высококачественных планов запросов.

Для большинства рабочих нагрузок полное сканирование не требуется, и выборка по умолчанию является адекватной. Однако для определенных рабочих нагрузок, чувствительных к широко варьирующемуся распределению данных, может потребоваться увеличение размера выборки или даже полное сканирование.

В некоторых случаях может помочь создание отфильтрованной статистики. У вас может быть столбец с искаженными данными и множеством различных значений. Если в данных есть определенные значения, которые обычно фильтруются, вы можете создать статистическую гистограмму только для этих общих значений. Оптимизатор запросов может использовать статистику, определенную для меньшего диапазона данных, вместо статистики, определенной для всех значений столбца. Вам по-прежнему не гарантировано получить 200 шагов в гистограмме, но если вы создадите отфильтрованную статистику только по одному значению, вы гистограммой сделаете шаг по этому значению.

Использование секционированного представления - один из способов эффективно получить более 200 шагов для таблицы. Предположим, что вы можете легко разделить большую таблицу на одну таблицу в год. Вы создаете UNION ALLпредставление, которое объединяет все годовые таблицы. У каждой таблицы будет своя гистограмма. Обратите внимание, что новая инкрементная статистика, представленная в SQL Server 2014, позволяет только обновлять статистику, чтобы быть более эффективной. Оптимизатор запросов не будет использовать статистику, созданную для каждого раздела.

Здесь можно выполнить еще много тестов, поэтому я советую вам поэкспериментировать. Я провел это тестирование на SQL Server 2014 Express, так что на самом деле ничто не останавливает вас.