Порядок полей в составном индексе

Постановка задачи

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

Допустим, у нас есть социальная сеть и нам нужно реализовать выбор постов по определенному типу

Структура базы

В таблице activities

• recipient_id - пользователь которому пост попал в фид
• owner_id - автор поста
• trackable_id - идентификатор поста
• trackable_type - указывает тип поста (на какую таблицу ссылается идентификатор) и может принимать значения (posts videos photos)

Запрос на фильтрацию будет выглядеть так

SELECT * FROM activities WHERE recipient_id = :current_user_id AND trackable_type = :type

Тут явно видно, что нам нужен составной ключ по полям receipient_id и trackable_type

add_index :activities, [:recepient_id, :trackable_type]
#Но, возможен и другой вариант
add_index :activities, [:trackable_type, :recepient_id]

Что такое индекс и как он работает

Чтобы понять, важен ли порядок ключей в составном индексе, нужно понимать как работает индекс и почему вообще добавление индекса делает выборку быстрее.

Допустим, у нас нет никаких индексов. Есть просто таблица в базе данных с миллионом записей. Они хранятся на жестком диске и движку базе данных придется пройти все записи и проверить соответствие строки условию. Например, нам нужно выбрать все видео для пользователя с идентификатором 577

SELECT * FROM activities WHERE recipient_id = 577 AND trackable_type = ‘videos’

Движку базы данных придется считать с жесткого диска 1_000_000 записей и проверить каждую на соответствие условию. Т.е он проверит запись, хранящуюся на диске по адресу 122, потом 123 и т.д.. Причем по порядку.

Но, мы могли бы отдельно хранить пару значений {HDD ячейка, Recipient ID}, причем хранить не подряд а используя какую нибудь структуру данных, заточенную под быстрый поиск. Это и есть индекс базы данных. Поиск по таким данным будет очень быстрым, особенное если индекс загружен в оперативную память. Найдя элемент в индексе, мы уже знаем ячейку памяти в которой на жестком диске хранится полная запись.

B-Tree как самый популярный тип индекса

Деревья представляют собой структуры данных, в которых реализованы операции над динамическими множествами. При этом в них оптимизированы такие операции как поиск, добавление, удаление. Давайте рассмотрим самый простой вариант - бинарное дерево. (Бинарное не значит B, то есть бинарное дерево и B - дерево не одно и то же)

Пусть у нас есть следующий набор идентификаторов - [8, 13, 5, 0, 7]. И мы строим из них дерево по простому правилу - если дерево пустое, входящий элемент становится корнем, если не пустой - смотрим а больше ли входящий элемент чем корень, если да - идем вправо, если нет - влево. Т.е заполнение дерева будет следующим

Но, Бинарное дерево является не сбалансированным деревом. Т.е возможна ситуации, когда поиск по нему будет такой же медленный как и при переборе всех элементов. Такая ситуация возможна когда на вход поступает уже отсортированный массив. В таком случае дерево будет иметь линейную структуру(ветвиться вправо) и выигрыша при поиске не будет.

Но, есть и сбалансированные деревья, например «красно-черное дерево», «AVL-дерево», «Декартово дерево», «Б -Дерево»

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

Как выглядит B - Дерево

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

При построении дерева используется параметр t, который называется минимальной степенью. Каждый узел, кроме корневого, должен иметь, как минимум t – 1, и не более 2t – 1 ключей. Обозначается n[x] – количество ключей в узле x. Допустим у нас t = 3 и нам нужно построить дерево для наших индексов из примера про чтение подряд [12, 577, 23, 577, 577, 2] - рисунок 1

И нам нужно добавить еще 5ть элементов 577. Они все уйдут в правое дерево. И, чем больше мы будем добавлять элементов со значением 577, тем сильнее будет дерево ветвится справа.

Так какой же правильный порядок для составного индекса

Составной индекс это такое же B Дерево по склеенному значению полей, Т.е если мы строим индекс по [:recipient_id, :trackable_type], то это будет набор значений [12videos, 577posts, 23posts, 577videos, 577photos, 2photos] Если будем строить по [:trackable_type, :recipient_id], то это будет набор значений [videos12, posts577, posts23, videos577, photos577, photos2]

Нам нужен индекс с максимальной селективностью. Т.е. Допустим что у нас 1_000_000 распределены равномерно. И у каждого пользователя по 1000 записей каждого вида.Тогда:

Тогда при 1 варианте нам нужно будет сначала найти узлы начинающиеся на 577 (их всего 3000 в индексе) и потом перебрать все с типом videos.

При 2ом варианте нам нужно будет найти узел начинающийся на videos (их в индексе 300_000) и потом среди них искать 1000 записей по значению 577.

Выводы

1. При использовании составного индекса важен его порядок и первым должно идти поле с самой высокой селективностью, т.е. то поле, уникальных значений которого в базе больше.
2. Так же нужно помнить что индексы базы независимы друг от друга, и если у вас есть составной индекс [:recipient_id, :trackable_id] - это не значит, что не нужны отдельные индексы на :recipient_id и на :trackable_id. Если запрос начал выполнятся медленно, не гадаем почему так,  а смотрим EXPLAIN