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

В первом уроке « Объяснение индексов SQL » мы научились использовать сортировку для ускорения поиска данных. Хотя выполнение нашего запроса после сортировки строк выполняется быстрее, сортировка включает в себя чтение каждой строки по крайней мере один раз и ее перемещение. Это делает метод более медленным и менее эффективным, чем просто последовательное чтение всей таблицы.

Кажется, логический вывод состоит в том, что мы должны поддерживать отсортированные копии — которые мы будем официально называть индексами SQL с префиксом IX_ — данной таблицы. Алгоритмы поиска из первой статьи тогда были бы применимы, и нам не нужно было бы сортировать таблицу перед началом.

Индекс как отсортированная копия таблицы

Давайте посмотрим на буквальную реализацию этой идеи, опять же, используя Google Sheets. Наша таблица Reservation становится набором из пяти листов, содержащих одни и те же данные. Каждый лист сортируется по разным наборам столбцов.

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

1. Как более эффективно извлекать данные при использовании отдельных индексов, а не отсортированных первичных таблиц
2. Как поддерживать порядок в каждом индексе и таблице при изменении данных

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

Предварительное упражнение: отмена бронирования

Чтобы получить представление о производительности индекса SQL с использованием стратегии отсортированных таблиц, ваша задача — удалить бронирование для Клиента 12 от 22 августа 2020 года в Отеле 4. Имейте в виду, что вам нужно удалить строку из всех копий таблице и поддерживать правильную сортировку.

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

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

Индексы SQL с использованием адресов строк

Эта электронная таблица содержит индексы, в которых используется другой подход. Строки индекса по-прежнему сортируются по определенным критериям, но вся остальная информация не хранится в строке индекса. Вместо этого мы сохраняем только «адрес строки», адрес строки в листе Reservations, представляющий саму таблицу, в столбце H.

Все реализации РСУБД используют возможность уровня операционной системы для быстрого поиска блока на диске с использованием физического адреса. Адреса строк обычно состоят из адреса блока и позиции строки в блоке.

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

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

Как и в первой статье, вы собираетесь смоделировать выполнение следующего SQL-запроса:

 SELECT * FROM Reservations WHERE ClientID = 12;

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

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

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

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Здесь выражение « Get first row from » реализовано в виде цикла, похожего на те, что были в предыдущей статье:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

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

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

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

Мы вернемся к этой части позже и представим эффективное решение. А пока давайте сосредоточимся на части после того, как вы найдете первую строку, соответствующую нашим критериям.

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

Задача состоит в том, чтобы подсчитать количество чекинов 16 августа 2020 года, используя новый дизайн индекса.

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

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

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

Алгоритм в основном такой же, как и при использовании отсортированных таблиц. Однако строка индекса намного короче строки таблицы, поэтому нашей СУБД придется считывать с диска меньше блоков данных.

Упражнение 3: Уголовное расследование (список гостей с учетом отеля и диапазона дат)

Подготовим список гостей, прибывших в отель 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;

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

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Можем ли мы разработать еще более эффективный индекс?

Мы обращаемся к таблице из-за значения ClientID , единственной информации, которая нам нужна для списка гостей, о которых мы сообщаем. Если мы включим это значение в индекс SQL, нам вообще не нужно будет обращаться к таблице. Попробуйте подготовить список, читающий только из такого индекса, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Когда индекс содержит всю необходимую информацию для выполнения запроса, мы говорим, что индекс охватывает запрос.

Упражнение 4: список имен гостей вместо идентификаторов

Список гостевых удостоверений был бы бесполезен для полицейского, расследующего преступление. Нам нужно указать имена:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Чтобы предоставить список, помимо данных из таблицы Reservations , нам также нужна таблица Clients , содержащая информацию о гостях, которую можно найти в этой таблице Google.

Это упражнение похоже на предыдущее, как и подход.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

Выражение Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID может быть реализовано сканированием таблицы или с использованием нашего индекса. Если мы используем сканирование таблицы, для каждого ClientID из цикла While нам пришлось бы читать в среднем половину строк из таблицы Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

Реализация индекса, которую мы рассматривали до сих пор, — назовем ее «плоской» реализацией индекса — не слишком полезна. Нам нужно было бы прочитать такое же количество строк (хотя и меньших строк) из индекса, а затем перейти к строке в Clients с помощью RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Примечание. Здесь PK относится к «первичному ключу», термину, который мы рассмотрим позже в этой серии.

Есть ли способ сделать это, не читая так много строк? Да, именно для этого и нужны индексы B-tree.

Индексы сбалансированного дерева (B-дерева)

Разделим строки из Clients_PK_Flat на блоки из четырех строк и создадим список, содержащий значение последнего ClientID из блока и адрес начала блока (столбец IndexRowAddress ). Результирующую структуру данных индекса базы данных можно найти на листе Clients_PK_2Levels. Попробуйте, как новая структура поможет вам найти клиента с ClientID 28. Алгоритм должен выглядеть так:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Вы, наверное, догадались, что мы можем добавить еще один уровень. Уровень 1 состоит из четырех строк, как вы можете видеть на вкладке IX_Clients_PK. Чтобы найти имя гостя с ClientID 28, вам нужно прочитать три блока (узла) данных — по одному на уровень — из структуры первичного ключа и, наконец, перейти к строке «Клиенты» с адресом 42.

Структура этого SQL-индекса называется сбалансированным деревом. Дерево сбалансировано, когда путь от корневого узла к каждому конечному узлу имеет одинаковую длину, так называемую глубину B-дерева. В нашем случае глубина равна трем.

С этого момента мы будем считать, что каждый индекс имеет структуру B-дерева, даже несмотря на то, что наши электронные таблицы содержат только элементы конечного уровня. Наиболее важные факты, которые нужно знать о B-дереве:

• Структура индекса B-дерева является наиболее часто используемым индексом во всех основных СУБД на рынке.
• Все уровни сбалансированного дерева упорядочены по значениям ключевых столбцов.
• Данные считываются с диска блоками.
• Один узел B-дерева содержит один или несколько блоков.
• Наиболее важным фактором, влияющим на производительность запросов, является количество блоков, считанных с диска.
• Количество элементов на каждом новом уровне B-дерева, начиная с корневого и заканчивая конечным уровнем, увеличивается экспоненциально.

Упражнение 5: Уголовное расследование, часть II

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

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Подход 1

Если мы используем индекс IX_DateFrom_HotelID_ClientID , то для каждой строки из диапазона дат нам пришлось бы обращаться к таблице Hotels и проверять, находится ли гостиница в городе A. Если это так, нам также нужно было бы обращаться к таблице Clients, чтобы прочитать имя клиента.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Подход 2

Использование IX_HotelID_DateFrom_ClientID дает нам более эффективный план выполнения.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Из таблицы Hotels находим все отели города A. Зная ID этих отелей, мы можем прочитать последующие элементы из индекса IX_HotelID_DateFrom_ClientID . Таким образом, после нахождения первой строки листового уровня B-дерева для каждого отеля и даты, мы не читаем бронирования из отелей за пределами города A.

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

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

Индексный запрос в SQL: детали решают все

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

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

В заключительной части « Объяснение индексов SQL » мы также узнаем о секционировании таблиц и индексов, правильных и неправильных мотивах их использования и их влиянии на производительность запросов и обслуживание базы данных.