Header RSS-подписка на обновления сайта eMail-подписка на обновления сайта

Density, Selectivity, Cardinality или о чем «думает» оптимизатор. Часть 3/6.

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

1
2
3
4
5
6
7
statistics_name             column_name stats_column_id
_WA_Sys_00000003_0EA330E9   C           1
_WA_Sys_00000002_0EA330E9   B           1
_WA_Sys_00000001_0EA330E9   A           1
B_C_A                       B           1
B_C_A                       C           2
B_C_A                       A           3

Тут главное разобраться в том как движок обрабатывает запрос на создание статистики для сочетания колонок (вспомните, кстати, что запрос такой может поступить движку двумя путями: явно, командой CREATE STATISTICS, и косвенно, в момент создания многоколоночного индекса).

Казалось бы, задали мы движку просчитать статистику по колонкам B, C, A. Ну соедини ты значения из указанных колонок в указанном порядке и проанализируй уникальность полученных сочетаний по всем строкам таблицы, да и успокойся на этом! Но нет, вместо одного сочетания и, следовательно, одной статистики для него, движок создает целых три, а именно:

  • берется самая левая колонка (в нашем случае B) и производится анализ только для нее. Результатом этого анализа становится статистика которую мы видим в последнем резалт-сете в строке 5. Строго говоря, она полностью дублирует статистику из строки 3, т.к. обе были просчитаны индивидуально для колонки B. Полученная статистика заносится (добавляется, в нашем случае) к списку уже имеющихся статистик под именем набора B_C_A, и с порядковым номером 1 (см. строку 5, колонку stats_column_id);
  • к левой колонке добавляется вторая слева и производится анализ только для этого сочетания (в нашем случае B и С). Полученная статистика также добавляется к списку уже имеющихся статистик под тем же именем набора, но с порядковым номером 2 (см. строку 6 того же резалт-сета);
  • к сочетанию двух самых левых колонок прибавляется третья слева и мы, наконец-то, получаем статистику B-C-A. С ней поступают полностью аналогично и, как легко догадаться, порядковый номер она получает 3.

А как же сочетания B-A, C-A-B, C-A, и прочие возможные перестановки спросите вы? А очень просто — нет их и не будет. По крайней мере пока мы не озаботимся создать их одним из двух известных вам способов. Кстати, отметьте себе, что определение «левости» колонки в паре последних абзацах базируется не на положении колонки в самой таблице, это-то как-раз не важно. А важно насколько слева указана та или иная колонка в параметрах команд CREATE STATISTICS / CREATE INDEX. Итого, важный промежуточный итог:

При создании многоколоночной статистики сервер всегда будет работать с т.н. «лево-ориентированными поднаборами». Такие наборы перебирают все возможные сочетания колонок, но только для самых левых из них. То есть: самая левая колонка персонально; самая левая + вторая слева; левая + вторая + третья слева; и т.д. Прочие возможные комбинации не учитываются и статистика для них не создается.

Теперь картина прояснилась? А раз так, мы можем вернуться к нашей таблице TT и только что созданной по ее данным статистике B_C_A, и посмотреть отчет по последней:

1
DBCC SHOW_STATISTICS ('TT', B_C_A) WITH DENSITY_VECTOR

Резалт-сет будет примерно таким:

All density Average Length  Columns
0.1428571   4               B
0.08333334  6               B, C
0.07142857  10              B, C, A

Проанализируем его справа-налево.

  • колонка Columns. Ранее я упоминал, что для одноколоночной статистики эта информация практически бесполезна. И обещал, что в статистике многоколоночной будет интересней. И, как видите, не обманул. Нас не может не интересовать к какому именно сочетанию колонок относится та или иная плотность;
  • колонка Average Length. Здесь, по идее, должны быть длинны (мне более понятен термин «ширина») значений колонок в байтах, проверим? B у нас int, а значит ожидаем 4. C у нас char(2), а значит всегда имеет ширину 2 байта. А сочетание этой и предыдущей колонки будет 2+4=6. Для последнего сочетания буду краток: 4+2+4=10 — сходится?
  • и конечно же, самое главное, колонка All density. Для колонки B она измеряет степень уникальности значений только этой колонки. Уникальных значений теперь стало 7 и D(B)=1/7=0.142857. Для сочетания B, C измеряется, соответственно, уникальность сочетания значений двух колонок, коих (проверьте!) ровно 12. Тогда D(B,C)=1/12=0.08333333... . И, наконец, у нас нет такой строки где бы совпали значения во всех трех столбцах, отсюда: D(B,C,A)=1/14=0.07142857.

Красиво, скажете вы — а толку? А толку очень много! Вновь в отдельно вкладке редактора напечатайте наш «много-группировочный» запрос:

1
2
SELECT COUNT(*) FROM TT
GROUP BY B,C,A

Не выполняя его снова вызовите предполагаемый план выполнения и посмотрите на планируемое число строк у того же шага Stream Aggregate. Что видите? Снова «13 с точкой»?? Что ж такое! Неужели мы ошиблись и оптимизатор не принимает во внимание «плотность слиянием»? Хотя, если подумать... Ведь оптимизатор, на самом деле, не генерирует новый план при нашем его обновлении в студии, он берет уже готовый из кэша планов!

На SQL-курсах, форумах и даже в E-письмах меня часто спрашивают: кэш планов (plan cache) и процедурный кэш (procedure cache) — одно и то же? Или в сервере есть 2 отдельных кэша? Ответ на этот вопрос простой: не только эти 2 термина, но и примыкающий к ним кэш процедурных планов (procedure plan cache) обозначают ровно одно и то же — место в оперативной памяти SQL Server куда складируются готовые (а «готовые»=«скомпилированные ранее») планы исполнения. Корни такого рассогласования терминов кроются в том, что раньше (да и теперь немногое изменилось в этом смысле) авторы для объяснения механизма работы кэша брали для примера какую-нибудь хранимую процедуру и начинали свой рассказ о фазах ее исполнения. И получалось, что готовый план процедуры (procedure) сохранялся у них в процедурном же кэше. А на самом деле, из всех трех наименований наиболее адекватен первый, кэш планов (plan cache). Он именно подчеркивает, что в этом кэше сохраняются далеко не только планы процедур (хотя и их тоже, конечно). А еще планы запросов (query), пакетов (batch), триггеров (trigger) и т.д. В современной литературе по SQL вы равновероятно можете встретить любой из 3-х терминов.

Продолжаем. А если он берет планы из кэша, то, наверно, и характеристики этого плана (одним из которых является предполагаемое число строк) он берет оттуда же? Так давайте заставим его именно перегенерировать план, для чего достаточно старый план удалить из кэша:

1
DBCC FREEPROCCACHE

И снова вызовите предполагаемый план. И уж на этот раз:

Step_Stream_Aggregate_multiCol

...А не какие-то «13 с точкой».

Все ли я правильно понял о плотности?

Будем на это надеяться. Но просто что бы проверить себя ответьте на пару-другую вопросов и соотнесите свои ответы с правильными.

1. Какое минимальное и максимальное значение может принять параметр плотности для данной колонки?

Смотреть ответ
0 и, соответственно, 1. Ровно 0 достижим только в теории, для этого нужно что бы таблица содержала бесконечное число уникальных значений в столбце. На практике плотность может быть очень близка к 0, но все же больше него. 1 без проблем достигается на практике, достаточно вставлять в колонку одно и тоже значение во все строки.

2. В общем случае плотность вычисляется как 1/(число различающихся значений в колонке). Если интересующая нас колонка является первичным ключом таблицы — как можно оптимизировать эту формулу сделав ее проще для вычислений?

Смотреть ответ
1/(число строк в таблице). Для подобной колонки (число различающихся значений в ней)=(число строк в таблице).

3. Есть запрос вида SELECT * FROM [имя_таблицы] WHERE FName='Ivan'. В таблице Tab1 плотность для колонки FName D(FName)=0.000087, для таблицы же Tab2 D(FName)=0.0945. В каком из двух случаев указанный запрос вернет (предположительно) большее количество строк?

Смотреть ответ
Во втором, для таблицы Tab2. Чем выше плотность — тем «плотнее» (в буквальном смысле) идут друг к другу строки, тем больше их будет в итоговом резалт-сете.

4. В таблице из 4-х колонок A,B,C,D статистика (и, соответственно, плотность) для сочетания D-C-B-A уже создана и запомнена. Есть ли основания отдельного расчета плотности для сочетания C-B-A?

Смотреть ответ
Да, есть. C-B-A не является лево-ориентированным поднабором набора исходного, D-C-B-A. Нужны отдельные статистика / плотность.

5. Исходные условия те же, что и в вопросе 4. Есть ли основания отдельного расчета плотности для сочетания D-C-B?

Смотреть ответ
Нет, отдельный расчет не требуется. D-C-B является лево-ориентированным поднабором набора исходного, а значит данные по нему уже сохранены.

Selectivity


366bef3a

Мы довольно подробно, с примерами и иллюстрациями, рассмотрели важнейшую концепцию — плотность данных в колонке. Честно говоря, автор ожидал что по объему это будет раз в 5 меньше, но что уж теперь... не зачеркивать же. :lol: Впрочем жалеть не о чем, тема столь важна, что потребуй она еще несколько экранов текста автор приступил бы к их написанию без всяких колебаний. Однако теперь мы с чистой совестью и чувством отданного долга можем двигаться вперед. К нам, на наш «разделочный столик», попадает вторая концепция — Selectivity. Или, по-русски говоря, избирательность или даже селективность, как вам ближе. Какая из двух концепций важнее — большой вопрос. Ну да суть не в правильной расстановке конкурентов на пьедестале, а в понимании принципов их работы и смысла значений в них содержащихся. Уж тем более, что Density и Selectivity и не конкуренты-то ни разу, а скорей коллеги. Они оба работают как «ассистенты» оптимизатора запросов, дабы последний мог выполнять свою работу максимально качественно.

Итак, вопрос номер один: почему нельзя было изобрести Density и на этом успокоиться? Чего этим теоретикам баз данных спокойно не живется? А вот почему. Допустим у нас на фирме есть БД, в ней таблица клиентов по имени, конечно же, Customers. В этой таблице есть много колонок, однако мы сосредоточимся на колонке City. Статистика по этой колонке давно просчитана и мы знаем что D(City)=0.0085. Какой из этого делаем вывод мы и оптимизатор вместе с нами? А такой, что запрос вида

1
2
3
DECLARE @p1 varchar(25)
SET @p1='...'
SELECT * FROM Customers WHERE City=@p1

будет возвращать нам в районе 0.0085*[число_строк_в_таблице_Customers] записей. Кстати, почему именно столько — помните? Правильно, потому что это все тот же AVG_DBL(City), то бишь среднее число дубликатов на каждое отдельное значение колонки. Итого, если у нас 1000 зарегистрированных клиентов то запрос выше будет нам возвращать в районе 0.0085*1000=8.5 записей для каждого отдельного значения параметра @p1. Однако, я не зря дважды подчеркнул слова «в районе», потому как даже здравый смысл подсказывает что @p1='Москва' и @p1='Простоквашино' будут двумя ну ОЧЕНЬ разными «районами». Если наша фирма искусственно не ограничивает географию своего бизнеса, число клиентов (а так же записей) будет для указанных значений различаться хорошо если в разы, но скорее на порядки. Вот как это может быть в цифрах:

  • из Москвы — 883 клиента
  • из «Простоквашино-1» - 1 клиент
  • из «Простоквашино-2» - 1 клиент
  • ...
  • из «Простоквашино-117» - 1 клиент

Итого у нас 883+117=1000 клиентов. А разных населенных пунктов? 1 Москва + 117 «Простоквашиных» = 118 разных населенных пунктов. Плотность колонки? D(City)=1/118=0.0085. Вот и приплыли. По плотности — 8.5 записей при любом значении @p1 (из имеющихся в таблице, разумеется), по факту — или одна запись или уж сразу 883!

Теперь чувствуете «засаду»? Плотность элементарно считается, очень легка для понимания, обслуживает сразу всю колонку таблицы (на довольно широкую таблицу из 20 колонок нужно всего-навсего 20 цифр типа decimal, что очень скромно), но отчаянно «фейлит» (от слова fail) при наступлении, как это изящно выражаются наши англоговорящие коллеги, data skew, то бишь «перекоса данных в рамках одной колонки». Цифровой пример такого перекоса был приведен только что. Ситуация усугубляется еще и тем, что в любой реальной БД, любая колонка (кроме уникальных по их определению, конечно) склонна скорее иметь подобный «перекос», вопрос лишь в его степени.

Задумаемся теперь над корнями этого «провала». Собственно, думать особо и не придется, «наши недостатки лишь продолжение наших достоинств». Так и тут: компактна, удобна, но... Но не всегда возможно (более правильно — почти никогда) вычислить одну плотность которая отражала бы любое распределение данных: от полностью равномерного до крайне несбалансированного. А как исправить ситуацию? Очевидно — разбить всю колонку на диапазоны данных и работать уже с ними, оценивая каждый диапазон персонально. Итак, встречаем — Selectivity.

В целом можно сказать, что Selectivity, как и Density, является мерилом (не-)уникальности значений колонки, только работает на ином уровне гранулированности. Иногда их даже настолько путают что пишут формулу Density = 1/Selectivity, что в корне не верно, но продолжает тиражироваться в форумах, статьях и даже книгах. Правильная же формула для селективности (S) будет такой:

S=[число строк удовлетворяющих предикату]/[всего строк в таблице]

Что такое предикат? Это любое условие просчитываемое в True или False и оказывающее влияние на включение или, соответственно, не включение данной строки таблицы в выходной резалт-сет. Допустим часть WHERE City=@p1 из скрипта чуть выше — самый простой и понятный предикат. Поэтому промежуточный вывод какой? Для запросов без предикатов селективность не играет роли и расчет ее лишен смысла. Кстати — ровно тоже можно сказать и о плотности. Еще проще — если нужно вернуть все строки таблицы, нужно их просто все возвращать и не морочиться (ни вам, ни оптимизатору) ни с какой «sql-алгеброй». Другое дело что большинство реальных запросов предикат в том или другом виде все-таки имеют... Поэтому я продолжу изложение, а вы — чтение данной увлекательной статьи. :)

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

Теперь снова немного посчитаем. Беря пример выше — какова селективность колонки City при значении предиката 'Москва'? Очевидно, S(City,'Москва')=883/1000=0.883. А ее же при предикате 'Простоквашино-117'? Еще более очевидно: S(City,'Простоквашино-117')=1/1000=0.001. Какой отсюда можно сделать очередной промежуточный, но от этого не менее важный вывод?