Оптимизатор запроса. Часть первая

23.12.19

Разработка - Запросы

Работа оптимизатора запроса является ключевой для обработки данных. Знание того, как оптимизатор выстраивает свою стратегию, отлично помогает при построении запросов.

Оптимизатор запросов. Часть первая. Статья из серии статей о СУБД.

ВСТУПЛЕНИЕ.

Данный цикл статей посвящен рассмотрению  устройства системы управления базами данных (СУБД). Хотя данное пособие не ставит целью ознакомить читателя с какой-то конкретной СУБД, опираться мы будем, в основном, на СУБД MS SQL. Для того, чтобы процесс обучения был понятен, я постараюсь вводить термины и определения постепенно, по мере углубления в материал.

Введение

Работа оптимизатора запроса является ключевой для обработки данных. Знание того, как оптимизатор выстраивает свою стратегию, отлично помогает при построении запросов.  

Для лучшего понимания статьи, необходимо понимать, что такое индексы (кластерные, некластерные), понимание языка манипулирования данными (DML  T-SQL).  Знать из чего состоит запрос, а именно: Условие; Соединения; Выражения в запросе; Вложенные запросы.

Что такое оптимизатор.

Когда выбираются данные из базы, движок СУБД пытается наилучшим (наиболее быстрым, менее затратным) образом использовать ресурсы. Эту работу выполняет оптимизатор запросов.  Задача оптимизатора – это рассмотрение наилучшей стратегии обработки данных. В качестве результата, оптимизатор выдает «План выполнения запроса». При выборе стратегии оптимизатор учитывает очень много факторов – это индексы, условия в запросе (подробно рассмотрим далее) и, так называемую, статистику или, как ее еще называют, статистические данные, содержащую такую информацию как диаграмма состояния таблиц.

Работа оптимизатора.

Работа оптимизатора состоит из нескольких этапов:

  1. Синтаксический разбор запроса. На этом этапе запрос проверяется правильность написания запроса. Если запрос написан правильно, то строится дерево, на основании текста запроса. Затем проверяется наличие объектов, к которым обращается запрос. После этого, строится окончательное дерево с идентификаторами объектов.
  2. Компиляция запроса. Дерево компилируется и передается на следующий этап.
  3. Оптимизация запроса. Оптимизатор анализирует входящее дерево. Ищет аргументы поиска и критерии соединения. Затем решает, какие индексы использовать, какой будет порядок соединения таблиц. И выбирает наилучшую стратегию.
  4. Исполнение запроса. Сохранение плана запроса и его исполнение

Этапы работы оптимизатора

  1. Анализ запроса
  2. Выбор индексов
  3. Выбор порядка выполнения операций соединения
  4. Выбор метода выполнения операций соединения

1. Анализ запроса. Это первый этап, на котором определяются:

  1. Аргументы поиска.
  2. Операторы OR (ИЛИ).
  3. Критерии соединения.

 

Запомните эту последовательность. Разбор происходит именно в такой последовательности. Наиболее значимым для нас, будет Аргумент поиска.

Что такое аргумент поиска? – Это та часть запроса, которая используется в условии и ограничивает конечную выборку данных. Аргументами поиска являются: условие отбора на равенство, операции больше/меньше, операции вхождения в множество. Основным назначением аргументов поиска является возможность использования индексов для ускорения выборки данных.

Например: Год рождения = 1980 - равенство

Годовой доход >= 1 000 000 рублей, - операции Больше равно

Год рождения = 1980 И Рост >= 175см – Логическое умножение и операции Больше равно

Место рождения В (Москва, Воронеж) – вхождение в множество

Что не входит в аргументы поиска? – Операции неравенства, операции отрицания и выражения в левой части условия.

Пример: Год рождения НЕ РАВНО 1980 - неравенство

Место рождения НЕ В (Москва, Нью-Йорк, Воронеж) – оператор отрицания

Годовой доход * 10  >= 1 000 000 – выражение в левой части

Кстати, во многих случаях достаточно произвести небольшие манипуляции с запросом и результат может ускориться в разы. Вернувшись к нашему примеру, если мы переделаем условие: Годовой доход * 10  >= 1 000 000 на Годовой доход >= 100 000, то есть заменим выражение в левой части на простую выборку, то получим аргумент, который может использовать индекс. Так происходит потому, что выражения рассчитываются после выборки и потом на них накладывается условие. Тоже самое и с отрицанием: сначала необходимо выбрать данные и только потом, сравнивая с условием, откинуть ненужное. Поэтому там, где нет аргументов поиска, происходит сканирование таблицы (описано далее). Если же в условии стоит равенство, то его можно отобрать по индексу (если он установлен). Запомните это правило. Если есть возможность – используйте равенство.

Операторы OR - логически складывает условия и может, но не обязательно, создать еще одну выборку.

Критерии соединения – это, фактически, выбор порядка выполнения операций соединения и выбор метода выполнения операций соединения, которые и будут рассмотрены далее.                     

2.Выбор индексов. Это второй этап работы оптимизатора. На этом этапе оптимизатор ищет наличие индекса/ов, используя аргументы поиска, и решает - использовать индекс или нет. Выбор решения зависит от селективности выражения и статистических данных. Селективность – это отношение количества выбираемых строк, к общему количеству строк в таблице.

Для углубления в тему, давайте рассмотрим селективность выражения с индексированным столбцом, а затем «Статистические данные».

2.1.Селективность выражения с индексированным столбцом.

Когда оптимизатор строит план по выполнению запроса, он рассматривает возможность использования индексов. На его решение влияет не только то, есть индекс у поля/полей выборки, но также и целесообразность использования индекса. Если оптимизатор решил, что индекс лучше не использовать, то он просто сканирует страницы. Сканирование – это последовательное считывание страниц, в которых содержатся данные, и отбор нужных записей. В отличии от сканирования, доступ по индексу читает или записывает данные, используя индекс. Как правило, доступ по индексу работает быстрее, чем простое сканирование, разумеется, при условии хорошей селективности выражения. 

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

2.2.Статистические данные. Существуют статистические данные индекса и статистические данные столбца. Давайте рассмотрим их подробней.

2.2.1.Статистические данные индекса создаются при создании индекса. Помимо создания дерева индекса, система создает гистограмму. В этой гистограмме отображается количество точных совпадений строк для  каждого интервала, среднее количество строк с разными значениями в каждом интервале,  плотность значений и много еще различной информации. Эти данные позволяют искать наиболее оптимальное решение для оптимизатора.

 

2.2.2.Статистические данные столбца. Система может создавать статистику для столбца, точно также, как она создает статистику для индекса. Это бывает, когда столбец используется в условии WHERE (ГДЕ). Такая статистика может помочь при выборке по составному условию. Например, когда одно поле индексировано, а второе не имеет индекса, но имеет статистику. Тогда при выборке можно использовать помимо индекса еще и статистику поля.

По мере изменения данных столбца, статистические данные индекса устаревают. Устаревшие статистические данные могут в значительной мере отрицательно влиять на производительность запроса. Поэтому статистику необходимо обновлять. Неправильная статистика приводит к неправильным расчетам оптимизатора, а это влияет на выбор стратегии. Помните об этом.

3. Выбор порядка выполнения операций соединения. Некоторые считают, что порядок соединения таблиц будет таким же, как он описан в запросе. Если честно, то это никак не влияет на то, в каком порядке таблицы будут соединяться. Оптимизатор принимает решение на основе многих факторов. Это и количество строк в выборке каждой таблицы, и степень сложности выборки строк, и плотность данных в станицах  и т.д. Некоторые СУБД позволяют использовать подсказки для оптимизатора (hints), в которых можно приказать оптимизатору соединять таблицы в определенном порядке. Но это тема не для данной статьи.

4. Выбор метода выполнения операций соединения. Соединения таблиц может выполняться следующими методами:

4.1. Вложенный цикл (nested loops)

4.2. Соединение слиянием (merge connection)

4.3. Соединение хешированием (hash connection)

Вложенный цикл. Использование вложенного цикла основано на полном переборе строк таблиц. То есть, выбирая строку одной таблицы, перебираются все строки соединяемой таблицы. Можно заметить, что если таблицы не проиндексированы, то выборка будет очень накладной. Если в одной таблице N строк, а в соединяемой K строк, то результат прохода = N * K, то есть первая таблица будет сканирована один раз, а соединяемая столько раз, сколько строк в первой таблице. При полном переборе строки сначала сравниваются и, если они соответствуют условию соединения, попадают в результирующий набор

Соединение слиянием. Соединение слиянием подразумевает, что строки соединяемых таблиц предварительно физически упорядочены по полю соединения. Происходит сканирование двух таблиц и сопоставление строк по одинаковым значениям в полях соединения. Единственной проблемой при соединении слиянием может быть случаи, когда строки в таблицах не отсортированы. Иногда, при рассмотрении запроса, бывали случаи, когда простая сортировка полей соединения давала прирост производительности. (Правда, для этого нужно, все таки, глянуть на план выполнения запроса. А потом принимать решение). Соединение слиянием гораздо эффективнее вложенного цикла.

Соединение хешированием.  

Метод соединения хешированием обычно применяется при отсутствии индексов для столбцов соединения. В случае использования этого метода обе соединяемые таблицы рассматриваются как два потока ввода: компонуемый ввод и контрольный ввод. (В качестве компонуемого ввода обычно используется наименьшая таблица.) Процесс работает следующим образом:

1. Значение соединяемого столбца из строки компонуемого ввода сохраняется в определенном сегменте хеша в зависимости от числа, возвращаемого алгоритмом хеширования.

2. После обработки всех строк из компонуемого ввода начинается обработка строк из контрольного ввода.

3. Каждое значение соединяемого столбца строки из контрольного ввода обрабатывается с использованием того же самого алгоритма хеширования.

4. Соответствующие строки извлекаются из каждого сегмента хеша и затем используются для создания результирующего набора.

Это соединение используется для неиндексируемых столбцов. Поэтому, если вы видите в плане запроса данный вид соединения, то это может служить определенной подсказкой для создания индексов.

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

запрос СУБД оптимизатор SQL индекс соединения выборка

См. также

Инструментарий разработчика Роли и права Запросы СКД Программист Платформа 1С v8.3 Управляемые формы Запросы Система компоновки данных Конфигурации 1cv8 Платные (руб)

Набор инструментов программиста и специалиста 1С для всех конфигураций на управляемых формах. В состав входят инструменты: Консоль запросов, Консоль СКД, Консоль кода, Редактор объекта, Анализ прав доступа, Метаданные, Поиск ссылок, Сравнение объектов, Все функции, Подписки на события и др. Редактор запросов и кода с раскраской и контекстной подсказкой. Доработанный конструктор запросов тонкого клиента. Продукт хорошо оптимизирован и обладает самым широким функционалом среди всех инструментов, представленных на рынке.

10000 руб.

02.09.2020    139650    767    391    

800

Запросы СКД Программист Стажер Система компоновки данных Россия Бесплатно (free)

Часто при разработке отчетов в СКД возникает ситуация, когда не совсем понятно, почему отчет выводит не те данные, которые нужны, либо не выводит вовсе. Возникает потребность увидеть конечный запрос, который формирует СКД. Как это сделать, рассмотрим в этой статье.

15.05.2024    5062    implecs_team    6    

41

Запросы Программист Стажер Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Часто поступают задачи по произвольному распределению общих сумм. После распределения иногда пропадают копейки. Суть решения добавить АвтоНомерЗаписи() в ВТ распределения, и далее используя функции МАКСИМУМ или МИНИМУМ можем положить разницу копеек в первую или последнюю строку знаменателя распределения.

11.04.2024    2901    andrey_sag    10    

32

Запросы СКД Программист Стажер Платформа 1С v8.3 Запросы Система компоновки данных 1С:ERP Управление предприятием 2 Бесплатно (free)

В типовых конфигурациях разработчики компании 1С иногда используют в отчетах, построенных на СКД, такую конструкцию, как "ГДЕ ЛОЖЬ". Такая конструкция говорит о том, что данные в запросе не будут получены совсем. Для чего же нужен тогда запрос?

13.02.2024    6702    KawaNoNeko    23    

26

Запросы СКД Программист Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Абонемент ($m)

Есть список полей в виде текста, или запрос - закидываем в набор СКД.

1 стартмани

31.01.2024    2544    2    Yashazz    0    

33

Инструментарий разработчика Запросы Программист Стажер Платформа 1С v8.3 Управляемые формы Конфигурации 1cv8 Бесплатно (free)

Пишем на человеческом языке, что нам надо, и получаем текст запроса на языке 1С. Используются большие языковые модели (LLM GPT) от OpenAI или Яндекс на выбор.

15.01.2024    8255    83    mkalimulin    32    

60

Инструментарий разработчика Запросы Программист Стажер Платформа 1С v8.3 Бесплатно (free)

Одной из интересных задач, стоящих в процессе разработки, была поддержка механизма представлений в ЗУП. Но не просто возможность исполнения запросов с ними. Основная проблема была в том, чтобы с ними было удобно работать, а именно: создавать, модифицировать и отлаживать. Кратко о том, что в итоге получилось...

14.12.2023    2246    vandalsvq    7    

29

Инструментарий разработчика Запросы Программист Платформа 1С v8.3 Управляемые формы Запросы Россия Абонемент ($m)

Работа с запросом и СКД, Полная поддержка пакетных запросов, временных таблиц. Главное скорость отладки запроса и данных, а красота вторична.

1 стартмани

07.12.2023    3737    52    DrZombi    54    

21
Комментарии
Подписаться на ответы Инфостарт бот Сортировка: Древо развёрнутое
Свернуть все
1. bugagashenka 204 24.12.19 08:11 Сейчас в теме
Вот как то и статья, вроде, нужная, а как то написана сухо, что ли. Тысячу раз мусолена тема оптимизатора. Про SARG и соединения еще больше, тем более, что их всего то три.
Никаких примеров, а особоважные примеры не вида SELECT T.Fld1 From dbo.MegaTab T, а что то более экзотическое ,сложное и на пальцах показать, почему оптимизатор выбрал такой план и как такие вещи разгребать. А так статья и джунам не подойдет, ибо не доросли еще до такой магии, и синьорам не подойдет, ибо они и так это все уже знают. А интересующиеся миды и так уже читали, вникали, разбираются.
Извините за критику, я за качество статей, а не за количество.
Alexx48; BomjBandit; wowik; mult1c; Tsuzik; GoR1313; +6 Ответить
2. darkdan77 343 24.12.19 09:48 Сейчас в теме
Александру Буганову. Полностью согласен с вами. На самом деле выставлял две части, но вторую заставили переработать (это я сейчас оправдываюсь). Там, как раз примеры. После доработки, выставлю. Насчет сильно большой экзотики не обещаю, потому, что хочется простого объяснения. Хотя... надо подумать. Если вам будет нетрудно прочесть еще раз, буду рад. И еще больше рад буду критике. У вас она конкретна.
P.S. Если есть интерес создать что-то вроде группы единомышленников, пишите. Можно вместе поработать над статьями
user774630; +1 Ответить
3. strek_ivan 80 25.12.19 10:14 Сейчас в теме
Полезная статья, материал изложен ёмко и без лишней воды.
Данис, в продолжение хотелось бы видеть примеры запросов с планом запроса и вариантами оптимизации.
Дмитрий74Чел; +1 Ответить
4. darkdan77 343 25.12.19 11:15 Сейчас в теме
(3) strek_ivan .

Я, как раз, перерабатываю две статьи по оптимизации и статьи по индексам. Будут примеры (MS SQL). Постараюсь вычистить заумное, потом выставлю. Не думал, что это столько отнимает времени. Могу разослать оповещение, как будет готово (напишите, если нужно, просто так беспокоить не стану). Спасибо за комментарий
5. strek_ivan 80 25.12.19 16:27 Сейчас в теме
(4) darkdan77,

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

Слишком заумных моментов в вашей статье я не заметил, но примеры нужны обязательно, чтобы у читателя хоть что-то закрепилось в голове! Было бы удобно, если примеры запросов (вместе с тестовыми данными) были размещены в отдельной демо-базе (при желании читатель сможет приобрести её за Стартмани).

Да, я с удовольствием прочту продолжение по теме "оптимизации запроса" даже в черновом варианте. Если у самого будет время, готов оказать поддержку.

Я дважды пытался сдать на Эксперта, и даже немного стыдно, что до сих не получил сертификат. Увы, разочаровываться некогда, т. к. вопросы производительности всегда стояли остро - ведь плохим запросом можно испортить ожидание пользователей и пошатнуть свою репутацию как специалиста.

Давайте писать запросы со знанием дела!
6. darkdan77 343 26.12.19 06:36 Сейчас в теме
(5) Как доделаю, оповещу обязательно. Правда, до Нового 2020 года могу не успеть.

Всех с Наступающим Новым годом!!! Всем здоровья, удачи, богатства и славы!!!
7. darkdan77 343 30.12.19 13:22 Сейчас в теме
(5) Черновой вариант есть. Пишите адреса е-майл, кому выслать.
8. Cyberhawk 135 20.01.20 17:45 Сейчас в теме
строки соединяемых таблиц предварительно физически упорядочены по полю соединения
А что означает "физически"? И как этого добиться?
9. darkdan77 343 21.01.20 07:05 Сейчас в теме
(8) Физическое упорядочивание - это когда записи, следуют друг за другом последовательно. Не все поля можно физически упорядочить. Представьте, что у вас есть поле "Код" типа число. Тогда вы можете упорядочить это поле от 1 до количества записей. Добиться такого упорядочивания можно путем создания кластерного индекса.

P.S. Если быть честным, то физического упорядочивания, с точки зрения физики, - нет. Когда мы работаем с каким-либо программным обеспечением, то уровень, на котором мы работаем, называется логическим, а все что ниже, ближе к железу и до чего нам не дотянуться без спец. средств, то мы называем физическим уровнем.
10. Cyberhawk 135 21.01.20 08:44 Сейчас в теме
(9) Где должны быть отсортированы строки соединяемых таблиц? В реальных таблицах (таблицах БД) изначально? Или в соединяемых таблицах (если, например, это соединение временных таблиц, в которые выбраны записи из реальных)? Или достаточно, чтобы строки в принципе могли быть упорядочены (т.е. просто подходящее поле соединения чтоб было), но делать самостоятельно это не нужно?
11. darkdan77 343 21.01.20 10:31 Сейчас в теме
(10) Существуют два пути получения отсортированных входных потоков соединения слиянием: мы можем явно отсортировать входной поток (используя оператор сортировки) или возможно чтение строк из индекса. Как правило, план запроса, использующий для сортировки индекс, будет обходиться дешевле, чем план запроса с явной сортировкой. При использовании индекса (кластерного) данные УЖЕ будут упорядочены (таблицы БД, тут ничего не надо сортировать). В случае, когда вы сортируете (сами добавляете в выборку сортировку) - это ЯВНАЯ сортировка. Еще одно: соединение слиянием требует, как минимум, одного предиката и наличия отсортированных данных по ключу соединения. К примеру, соединяем Табл1.Поле1 и Табл2.Поле1. В обоих таблицах Поле1 должно быть отсортировано (упорядочено). Запускаются два потока, которые считывают значения из Поля1 обеих таблиц и сравниваются между собой. Если значения равны, то записываем в таблицу выборки, если не равны, то удаляем меньшее значение (в выборку не попадает) и сдвигаем на одну строчку таблицу, в которой удалили запись (вернее не удалили, а пропустили/не добавили в таблицу выборки).

P.S. Я действительно написал эту статью, мягко сказать, сжато. Сейчас готовится вторая часть. Там заглянем глубже в оптимизатор. Если этот ответ не слишком развернут, напишите. Я постараюсь ответить более развернуто. Или что еще лучше, разложу такие действия по статьям
12. Cyberhawk 135 21.01.20 10:51 Сейчас в теме
(11)
Если этот ответ не слишком развернут
Из написанного так и осталось неясным назначение слова "физически" в статье. Складывается ощущение, что если его убрать, то смысл никак не меняется, а значит оно просто лишнее.
13. darkdan77 343 21.01.20 13:10 Сейчас в теме
(12) В данном случае, физически - это таблицы и индексы БД и их проекция в оперативной памяти. Упорядочивание по полю кластерного индекса - это первый случай. Второй случай - это упорядочивание в оперативной памяти, когда сделана выборка таблицы. ОБА этих случая, опять же повторюсь, для нашего уровня работы, называются физическими. То есть, считается, что уровень СУБД (прослойка кода между нами и операционной системой), для нас - физический. Без этого упоминания, получается, что у нас есть возможность регулировать порядок записей в таблице как нам хочется, а это не так.
15. Cyberhawk 135 21.01.20 13:17 Сейчас в теме
(13)
у нас есть возможность регулировать порядок записей в таблице как нам хочется, а это не так
Почему не так? Что мне мешает отсортировать оба входа перед соединением?
16. darkdan77 343 21.01.20 14:12 Сейчас в теме
(15) Регулировкой порядком записей занимается движок СУБД. Мы можем дать команду на упорядочивание, но само упорядочивание мы не делаем.
17. Cyberhawk 135 21.01.20 14:43 Сейчас в теме
(16) А какой еще бывает вариант упорядочивания, помимо "физического"?
18. darkdan77 343 21.01.20 15:12 Сейчас в теме
(17) Бывает еще логический. Когда мы получаем выборку и делаем с ней то, что нам нужно
19. Cyberhawk 135 21.01.20 15:23 Сейчас в теме
(18) Упорядочивание входов (двух таблиц) перед их соединением - это физическое или логическое упорядочивание?
20. darkdan77 343 21.01.20 16:13 Сейчас в теме
21. Cyberhawk 135 21.01.20 16:24 Сейчас в теме
(20) А мы можем сделать какое-то еще (кроме физического) упорядочивание входов (двух таблиц) перед их соединением?
22. darkdan77 343 21.01.20 16:43 Сейчас в теме
(21) Можно сгруппировать. Можно проиндексировать саму выборку.

P.S. Только это не значит, что надо бросаться в омут с головой. Иногда это улучшает выборку, но не всегда. Представьте, что вы читаете книгу, в которой есть ссылки на другой источник. Если вам надо прочитать несколько глав и сделать несколько переходов к другому источнику, то это - одна ситуация. Здесь можно использовать оглавление (индекс), И упорядочить не помешает. А если вам надо прочитать всю книгу? Стоит ли обращаться к оглавлению? То есть, взяли оглавление, нашли первую главу, перешли к ней, прочитали, потом опять к оглавлению, нашли вторую главу и т.д.
Оставьте свое сообщение