Объяснение индексов SQL, Pt. 1

При правильном использовании индекс базы данных SQL может быть настолько эффективным, что может показаться магией. Но следующая серия упражнений покажет, что в глубине логика большинства SQL-индексов — и их правильное использование — довольно проста.

В этой серии « Объяснение индексов SQL » мы рассмотрим мотивы использования индексов для доступа к данным и разработки индексов так, как это делается во всех современных СУБД. Затем мы рассмотрим алгоритмы, используемые для возврата данных для конкретных шаблонов запросов.

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

• Базовые знания SQL
• Базовые знания любого языка программирования

Основные темы, которые будут рассмотрены в разделе « Объяснение индексов SQL », следующие:

• Зачем нужны индексы базы данных SQL; визуализация планов выполнения с использованием индексов
• Дизайн индекса: какие индексы делают запрос быстрым и эффективным
• Как мы можем написать запрос для эффективного использования индексов
• Влияние использования индексов в SQL на эффективность чтения/записи
• Индексы покрытия
• Разделение, его влияние на чтение и запись и когда его использовать

Это не просто руководство по индексам SQL — это глубокое погружение в понимание базовой механики индексов.

Мы собираемся выяснить, как РСУБД использует индексы, выполняя упражнения и анализируя наши методы решения проблем. Наш учебный материал состоит из таблиц Google, доступных только для чтения. Чтобы выполнить упражнение, вы можете скопировать Google Sheet ( Файл → Создать копию ) или скопировать его содержимое в свой собственный Google Sheet.

В каждом упражнении мы покажем SQL-запрос, использующий синтаксис Oracle. Для дат мы будем использовать формат ISO 8601 YYYY-MM-DD .

Упражнение 1: Все бронирования клиента

Первая задача — пока не делайте этого — найти все строки из электронной таблицы Reservation для конкретного клиента системы бронирования отелей и скопировать их в свою собственную электронную таблицу, имитируя выполнение следующего запроса:

 SELECT * FROM Reservations WHERE ClientID = 12;

Но мы хотим следовать определенному методу.

Подход 1: без сортировки, без фильтрации

При первой попытке не используйте функции сортировки или фильтрации. Пожалуйста, зафиксируйте потраченное время. Полученный лист должен содержать 73 строки.

Этот псевдокод иллюстрирует алгоритм выполнения задачи без сортировки:

 For each row from Reservations If Reservations.ClientID = 12 then fetch Reservations.*

В этом случае нам пришлось проверить все 841 строку, чтобы вернуться, и скопировать 73 строки, удовлетворяющие условию.

Подход 2: только сортировка

Для второй попытки отсортируйте лист в соответствии со значением столбца ClientID . Не используйте фильтры. Запишите время и сравните его со временем выполнения задачи без сортировки данных.

После сортировки подход выглядит так:

 For each row from Reservations If ClientID = 12 then fetch Reservations.* Else if ClientID > 12 exit

На этот раз нам пришлось проверить «всего» 780 строк. Если бы мы могли каким-то образом перейти к первой строке, это заняло бы еще меньше времени.

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

Упражнение 2. Количество бронирований, начиная с определенной даты

Теперь задача — посчитать количество чекинов 16 августа 2020 года:

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16', 'YYYY-MM-DD')

Используйте таблицу из упражнения 1. Измерьте и сравните время, затраченное на выполнение задачи с сортировкой и без нее. Правильный счет 91.

Для подхода без сортировки алгоритм в основном такой же, как и в упражнении 1.

Подход к сортировке также аналогичен подходу из предыдущего упражнения. Мы просто разделим цикл на две части:

 -- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 16th of August 2020. Repeat Read next row Until DateFrom = '2020-08-16' -- Calculate the count While DateFrom = '2020-08-16' Increase the count Read the next row

Упражнение 3. Уголовное расследование

Инспектор полиции просит предоставить список гостей, прибывших в отель 13 и 14 августа 2020 года.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND HotelID = 3;

Подход 1: сортировка только по дате

Инспектор хочет список быстро. Мы уже знаем, что лучше отсортировать таблицу/таблицу по дате поступления. Если мы только что закончили упражнение 2, нам повезло, что таблица уже отсортирована. Итак, применяем подход, аналогичный подходу из упражнения 2.

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

 -- Assumption: Table reservation is sorted by DateFrom -- Find the first reservation from the 13th of August 2020. Repeat Read next row Until DateFrom >= '2020-08-13' -- Prepare the list While DateFrom < '2020-08-15' If HotelID = 3 then write down the ClientID Read the next row

При таком подходе нам пришлось прочитать 511 строк, чтобы составить список из 46 гостей. Если бы мы могли точно скользить вниз, нам фактически не нужно было бы выполнять 324 считывания из цикла повторения только для того, чтобы найти первое прибытие 13 августа. Однако нам все равно пришлось прочитать более 100 строк, чтобы проверить, прибыл ли гость в отель с HotelID , равным 3 .

Инспектор ждал все это время, но не был счастлив: вместо имен гостей и других важных данных мы предоставили только список бессмысленных удостоверений личности.

Мы вернемся к этому аспекту позже в этой серии. Давайте сначала найдем способ подготовить список быстрее.

Подход 2: сортировка по отелю, затем по дате

Чтобы отсортировать строки в соответствии с HotelID , а затем DateFrom , мы можем выбрать все столбцы, а затем использовать пункт меню Google Sheets Data → Sort range .

 -- Assumption: Sorted according to HotelID and DateFrom -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Find the first arrival at the hotel on 13th of August While HotelID = 3 and DateFrom < '2020-08-13' Read the next row -- Prepare the list While HotelID = 3 and DateFrom < '2020-08-15' Write down the ClientID Read the next row

Нам пришлось пропустить первые 338 прибытий, прежде чем найти первого в нашем отеле. После этого мы просмотрели 103 более ранних прибытия, чтобы найти первое 13 августа. Наконец, мы скопировали 46 последовательных значений ClientID . Нам помогло то, что на третьем шаге мы смогли скопировать блок последовательных идентификаторов. Жаль, что мы не могли каким-то образом перейти на первую строку из этого блока.

Подход 3: сортировка только по отелю

Теперь попробуйте выполнить то же упражнение, используя электронную таблицу, упорядоченную только по HotelID .

Алгоритм, применяемый к таблице, упорядоченной только по HotelID , менее эффективен, чем при сортировке по HotelID и DateFrom (именно в таком порядке):

 -- Assumption: Sorted according to HotelID -- Find the first reservation for the HotelID = 3. Repeat Read next row Until HotelID >= 3 -- Prepare the list While HotelID = 3 If DateFrom between '2020-08-13' and '2020-08-14' Write down the ClientID Read the next row

В этом случае мы должны прочитать все 166 прибытий в отель с HotelID 3 и для каждого проверить, принадлежит ли DateFrom запрошенному интервалу.

Подход 4: сортировка по дате, затем по отелю

Действительно ли имеет значение, сортируем ли мы сначала по HotelID , а затем DateFrom или наоборот? Давайте выясним: попробуйте отсортировать сначала по DateFrom , а затем по HotelID .

 -- Assumption: Sorted according to DateFrom and HotelID -- Find the first arrival on 13th of August While DateFrom < '2020-08-13' Read the next row --Find the first arrival at the Hotel While HotelID < 3 and DateFrom < '2020-08-15' Read the next row Repeat If HotelID = 3 Write down the ClientID Read the next row Until DateFrom > '2020-08-14' or (DateFrom = '2020-08-14' and HotelID > 3)

Мы нашли первую строку с соответствующей датой, затем читаем дальше, пока не найдем первое прибытие в отель. После этого для ряда строк выполнялись оба условия, правильная дата и правильный отель. Однако после заездов в гостиницу 3 у нас были заезды в гостиницы 4, 5 и так далее на ту же дату. После них нам пришлось снова читать строки на следующий день для отелей 1 и 2, пока мы не смогли прочитать последовательные прибытия в интересующий нас отель.

Как мы видим, все подходы имеют один последовательный блок данных в середине полного набора строк, представляющих частично совпадающие данные. Подходы 2 и 4 — единственные, в которых логика позволяет нам полностью остановить алгоритм до того, как мы достигнем конца частичных совпадений.

Подход 4 полностью соответствует данным в двух блоках, но подход 2 — единственный, в котором все целевые данные находятся в одном последовательном блоке.

Судя по цифрам, подход 2 в данном случае имеет больше преимуществ.

Объяснение индексов SQL: выводы и дальнейшие действия

Выполнение этих упражнений должно прояснить следующие моменты:

1. Чтение из правильно отсортированной таблицы происходит быстрее.
2. Если таблица еще не отсортирована, сортировка занимает больше времени, чем чтение из несортированной таблицы.
3. Поиск способа перехода к первой строке, соответствующей условию поиска в отсортированной таблице, сэкономит много операций чтения.
4. Было бы полезно заранее отсортировать стол.
5. Было бы полезно поддерживать отсортированные копии таблицы для наиболее частых запросов.

Теперь отсортированная копия таблицы звучит почти как индекс базы данных. Следующая статья в разделе « Объяснение индексов SQL » посвящена простейшей реализации индекса. Спасибо за прочтение!