Привет, Хабр! Меня зовут Андрей Саранчин, и я разработчик СУБД Tarantool в VK Tech. Вот уже полтора года мы строим MemCS — новый колоночный движок Tarantool для HTAP. И вот парадокс: даже с индексами иногда не уйти от сплошного прохода таблицы. Поделюсь, почему мы не смогли миновать Sequential Scan и как мы смягчили эту проблему с помощью Data Skipping.

Эта статья написана по мотивам доклада для Saint HighLoad++ и отражает одну из проблем, которую мы затрагивали в этом докладе.

Индексация данных

Перед тем как разбираться с Data Skipping, поговорим об индексации данных.

У нас есть таблица, в которой мы хотим найти набор строк по какому-то критерию. Есть всего два способа это сделать.

Сканирование всей таблицы. Просто переберем все строки и отложим те, которые нужны. Такой подход быстро работает на маленьких таблицах по очевидным причинам. Нет накладных расходов — нужна только табличка и ничего больше.

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

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

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

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

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

• Каждый индекс нужно обновлять, поэтому они заметно замедляют вставку. В результате если у нас много индексов, то нам может не хватить процессора.

• Индекс может оказаться бесполезным, если запросы читают большое количество данных.

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

Data Skipping

Для ускорения сканирования есть прием под названием Data Skipping — «пропуск данных». У него нет каноничного названия, но чаще всего его можно встретить именно под этим именем — так мы его и назовем. С таким приемом вы уже знакомы, если пользовались BRIN-индексом.

Рассмотрим все на примере. Есть табличка, которую мы разбили на три блока. В каждом блоке храним некоторые метаданные, например минимальное и максимальное значение колонки receiver в этом блоке.

Поступает запрос:

SELECT * WHERE receiver = 10;

Когда приходит запрос, мы сразу видим, что в третьем блоке минимальное значение 15 заведомо больше, чем искомое. Значит, нужных элементов там нет, и мы пропускаем этот блок при сканировании.

Data Skipping хранит метаданные для каждого блока, а не для каждой строки. Как правило, в блоках сотни или даже тысячи элементов. Такие индексы занимают гораздо меньше памяти, чем полноценный индекс, и чем больше размер блока, тем меньше расход памяти. Затрат на обновление таких индексов тоже меньше — как минимум потому, что хранилище этих метаданных меньше. Конечно, это зависит от устройства СУБД, но обычно такие хранилища метаданных гораздо проще хранилищ индексов.

Мы задумались о пользе такой штуки в Tarantool. Но перед тем как рассказать, к чему пришли, стоит познакомить вас с Tarantool и его колонками.

Устройство нового колоночного движка Tarantool

Tarantool — это in-memory СУБД, то есть все данные хранятся в оперативной памяти. Тем не менее она персистентная за счет использования Write-Ahead Log (WAL), то есть обработка транзакций происходит только в главном потоке.

Во избежание накладных расходов на многопоточную синхронизацию в Tarantool данными заведует (и, соответственно, обрабатывает запросы) строго один поток. Конечно, есть отдельные потоки для ввода-вывода и WAL, а также возможность создания иммутабельного read view и использования его из других потоков. Тем не менее все записи в индексы и таблицу происходят только в одном потоке.

Основным движком нашей СУБД считается MemTX. Это движок строчного хранения для OLTP-нагрузки. Наш новый движок MemCS (Memory Column Storage) — это колоночный движок, рассчитанный на HTAP-нагрузку. 

HTAP — это гибрид транзакций и аналитики. Здесь данные обновляются в реальном времени — это черта из мира OLTP. А еще здесь много аналитики, это из OLAP. Вследствие совмещения этих двух миров анализы проводятся на актуальных данных.

Есть два основных подхода к реализации HTAP-хранилищ:

1. Комбинация двух разнородных OLTP и OLAP движков

Каждый движок обрабатывает только присущие ему запросы, а между движками организован трансфер данных.

2. Гибрид (MemCS). Это магический движок, который обрабатывает сразу все запросы.

Мы решили пойти по второму пути, и получился MemCS.

MemCS

Выведем факторы, которые сформировали MemCS:

1. Большое количество аналитических запросов (OLAP). Много аналитики из мира OLAP, поэтому храним данные в колонках. На запросах мы читаем только те колонки, которые нужны. Как следствие, получаем ��окальность данных при чтении, и запрос ускоряется.

2. Большая доля INSERT-/UPDATE-/DELETE-запросов (OLTP). Нам хотелось бы удалять данные из середины каждой колонки физически. Есть подход, который называется Tombstone, когда мы не удаляем данные, а просто помечаем, что они удалены, но они все еще занимают память. Такой подход нам не подходит, потому что может быть много удалений, вплоть до десятков тысяч в секунду, и тогда Tombstones просто забьют нам всю память.

3. B+*-дерево — основная структура данных в Tarantool. На основании этих факторов получился MemCS. Это набор колонок и каждая отдельная колонка — это B+*-дерево по неявному ключу.

Изначально у нас было B-дерево — самобалансирующееся дерево поиска.

У B-дерева есть один недостаток. Если хотим сделать упорядоченное сканирование, то приходится обойти все дерево и прыгать по листьям, точнее по блокам, туда-сюда.

Мы находим точку старта, сканируем первый лист. Видим, что следующий элемент находится на уровень выше, поднимаемся туда. Потом спускаемся в другой лист, сканируем его. То есть нам приходится все время прыгать по дереву вверх-вниз.

Модификация B+-дерево решает эту проблему. Так мы храним все элементы только в листьях, которые провязаны в двусвязный список.

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

Как вы могли заметить, тут довольно много незанятого места из-за того, что минимальный размер блока в B-дереве — B/2 элементов.

Модификация B+*-дерево поднимает эту границу выше, до 2/3 B, тем самым храня данные немного более компактно.

Это B+*-дерево — всем привычное дерево, которое умеет делать поиск по ключу и вставку элементов в произвольное место.

Но нам нужен немного другой интерфейс, аналог STD-вектора, который делает поиск по индексу и вставку по индексу в произвольное место. Поэтому мы применили следующую модификацию, которая называется «дерево по неявному ключу».

Теперь во внутренних узлах мы храним мощности поддеревьев, а поиск работает так:

Мы хотим найти 12-й элемент, отсчет с нуля. Заводим счетчик. Смотрим на левое поддерево, понимаем, что его мощность — 6, то есть там 6 элементов, поэтому мы можем его пропустить, и нам остается пропустить еще 6 элементов.

Мы пропускаем это поддерево, смотрим на второе, понимаем, что его пропустить мы не можем, потому что мы проскочим наш элемент.

Поэтому мы его не пропускаем. Спускаемся в это поддерево и запускаем процедуру рекурсивно.

Пропустили первое поддерево:

Второе смотрим, не пропускаем.

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

Таким образом, наш движок MemCS — это набор таких B+*-деревьев по неявному ключу. Также выделенный набор колонок является первичным ключом. Все колонки упорядочены по первичному ключу.

На самом деле есть довольно много интересных модификаций, которые мы применили. Можно посмотреть доклад моего коллеги про деревья на Database Internals — там много интересных деталей.

Покажу наглядно, как все это работает. Вот наши колонки:

Я дорисовал узлы, чтобы вы помнили, что это на самом деле деревья. Обратите внимание, что колонка primary отсортирована, это наш первичный ключ. Я добавлю виртуальные офсеты — просто порядковые номера элементов в колонке. Напомню, что они в явном виде не хранятся. Мы их вычисляем с помощью мощностей поддеревьев — та самая модификация по неявному ключу.

Если мы хотим найти, например, строчку с первичным ключом 7, то делаем бинарный поиск в первичной колонке. Так как это модификация по неявному ключу, мы заодно вычислили ее порядковый номер.

По этому порядковому номеру, то есть офсету, мы сделали lookup в других колонках и получили строку целиком.

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

Таким образом, мы получили быстрое сканирование колонок. Скорость достигает 1 миллиарда элементов в секунду на ядро на одну колонку.

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

Спецификация стенда, на котором все это происходит: AMD Ryzen 9 9950X (5.2GHz), 128 GB DDR5 RAM (4.8 GHz)

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

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

Вторичные индексы в MemCS

Расскажу, как мы их сделали.

Ниже — наше хранилище. Я вернул виртуальные офсеты. Напомню, что они в явном виде не хранятся. Мы их вычисляем с помощью мощностей поддеревьев. Рядом сделал вторичный индекс по колонке age.

По сути, я просто скопировал колонку age и колонку primary, но в другом порядке — в порядке возрастания значений age. Теперь, если хочу найти все записи с age, равным 18, я делаю отображение из age в первичный ключ, а потом по первичному ключу делаю по старой процедуре look-up в основном хранилище.

Но что, если мы считываем большое количество данных, как часто бывает при аналитике? Тогда приходится делать много трансляций из age в primary, и довольно много look-up в основном хранилище.

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

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

Таким образом, первая вариация вторичного индекса, «key-value вторичный индекс», плохо работает на большой аналитике. Вторая вариация, покрывающий вторичный индекс, работает хорошо, но требует слишком много ресурсов. Из-за этого наши индексы довольно негибкие, и мы оказались в ситуации, в которой нам часто приходится сканировать таблицу целиком, если запрос сделан не по первичному ключу. Для ускорения сканирования есть как раз Data Skipping. Поэтому мы решили реализовать его в Tarantool в нашем колоночном движке.

Data Skipping индекс в MemCS

Data Skipping — это прием, который использовал блоки данных, запоминал для них метаданные и пропускал целиком блоки при сканировании. Но проблема в том, что у нас в Tarantool нет как таковых блоков данных и физических страниц, потому что у нас база in-memory: обычно мы используем указатели прямо на данные, а в случае с MemCS вообще храним все значения прямо в дереве. Возникает вопрос: где же хранить эти метаданные?

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

Вот наша табличка, куда я опять добавил виртуальные офсеты (выделены белым), которые, как мы помним, в явном виде не хранятся:

Первичная колонка — это B-дерево. В нашем примере это B-дерево с тремя листьями.

На схеме слева самый первый лист первичной колонки. Справа я отрисовал значение других колонок, но в таком же layout.

Теперь добавим в первичную колонку наши метаданные.

Тут, например, есть minmax по колонке age для строк, покрытых первым листом, то есть для всех строк с офсетами от 1 до 3. Аналогично есть minmax, то есть минимумы и максимумы по другим колонкам.

Это здорово, но давайте посмотрим на первичную колонку в разрезе, что там происходит:

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

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

Но что происходит в случае балансировки дерева? Приезжает элемент (8):

Мы видим, что в листе, куда он приехал, места больше нет, и дерево просто выкидывает оттуда 7 в первый лист:

Строчка с первичным ключом 7 могла быть актуальным минимумом или максимумом в одной из колонок. Так как она исчезла из этого блока, то быстро узнать новые минимумы или максимумы нельзя. Единственный способ это сделать — по-честному просканировать все колонки с офсетами, покрытыми вторым листом дерева, и пересчитать minmax'ы заново. Это происходит потому, что дерево оперирует отдельными элементами и перемещает элементы по одному при удобном случае. Теперь нам нужно просканировать блок, чтобы пересчитать метаданные заново.

Виртуальные блоки

У метаданных есть ряд особенностей.

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

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

Физический размер не зависит от логического. Минимум и максимум по двум числам — это два числа. Минимум и максимум по 100 числам — все еще два числа.

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

У нас было хранилище, где мы хранили метаданные прямо в первичной колонке.

Стало то же самое =)

Мы просто отделили метаданные и называем это виртуальными блоками. В них есть:

• Первичный ключ (Primary Key) — первичный ключ первой строки в блоке.

• Размер (Size) — количество строк в блоке.

• Разумеется, виновники торжества — метаданные по другим колонкам (age, x, y) — minmax в блоке.

Приходит новая строка:

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

Приходит нагрузка, и с течением времени их layout’ы совсем разъезжаются. В этом и была цель: сделать независимые балансировки. Храним мы эти виртуальные блоки в B+-дереве с кастомной балансировкой.

Эти виртуальные блоки являются листьями.

Кастомная балансировка заключается в том, что:

• Мы оперируем целыми блоками на уровне листьев, поэтому мы не перемещаем элементы по отдельности.

• Допустимые размеры листа — [0.5 B, 1.5 B].

• При нарушении границ размера довольно простая стратегия: при необходимости мы делаем merge с соседом; если блок слишком большой, то делаем сплит в несколько блоков.

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

Давайте вернемся ненадолго к нашему обычному B+-дереву.

Мы вставляем новый элемент в конец:

Снова появляется лист. Все здорово, но такое дерево некорректно, потому что минимальный размер блока B/2 пополам. Чтобы добить последний лист до минимального размера, нам приходится копировать элемент 11 в этот лист.

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

Та же ситуация и с виртуальными блоками. На картинке размер второго блока уже максимальный. 

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

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

Оптимизация довольно простая и заключается в том, что мы не будем делать этот сплит, а просто снимем ограничения на размер последнего листа снизу.

Давайте прогоним этот кейс еще раз. Приходит новая строка, под нее появился новый блок.

Он, конечно, очень маленький, но не беда, потому что размер последнего блока снизу не ограничен.

Все, вставка завершена, сплит не нужен.

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

Графики деградации записей в конец и случайное место:

Эксперимент измеряет замедление записей после создания data-skipping индекса. В эксперименте мы храним минимум и максимум для каждой колонки. Размер блока — 8192 элемента. На сотне колонок мы получаем:

• замедление 14% при записях в конец;

• замедление 22% при записях в случайное место.

Также по графикам видно, что деградация с ростом числа колонок падает. При этом замечу, что в эксперименте мы храним minmax на все колонки сразу.

Спецификация стенда, на котором все это происходит: AMD Ryzen 9 9950X (5.2GHz), 128 GB DDR5 RAM (4.8 GHz)

Мы научились хранить метаданные. Поэтому возникает вопрос: а что там вообще можно хранить? Рассмотрим это дальше.

Существующие подходы к Data Skipping

Небольшой дисклеймер. Пусть существует наша табличка:

В каждом блоке есть значение receiver, равное 42. Если приходит запрос, который читает это значение, никакой Data Skipping не поможет, потому что мы в любом случае обязаны вычитать все блоки. Так что такой подход - не панацея. Для менее безнадежных случаев есть разные техники. Самая простая и тривиальная — это minmax.

Minmax

Мы храним минимум и максимум по блоку. Расход памяти на один блок два элемента: 2 * sizeof(element). Приходит запрос:

SELECT * WHERE value BETWEEN 13 AND 20;

Мы видим, что максимальное значение в первом и втором блоках меньше искомого, поэтому просто пропускаем их на сканировании.

Конечно, здорово, что наши данные уже упорядочены. К сожалению, в реальном мире это далеко не всегда так.

Давайте добавим всего пару выбросов:

SELECT * WHERE value BETWEEN 13 AND 20;

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

Поэтому есть следующая итерация этого подхода, которая называется minmax multi.

Minmax multi

SELECT * WHERE value BETWEEN 13 AND 20;

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

• Расход памяти: 2 * sizeof(element) * minmax_cnt на блок.

• В каждом блоке свое независимое разбиение на интервалы.

• Цель разбиения — минимизация суммарной длины интервалов.

Почему такая цель разбиения? Чем меньше суммарная длина интервалов, тем больше вероятность ткнуть пальцем и попасть мимо этих интервалов — разумеется, в условиях равномерного распределения.

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

Set

Мы храним множество всех значений в блоке. Максимальный размер set регулируется, и при превышении лимита он отключается для блока. Например, мы готовы выделить место в каждом блоке на 3 элемента. Если там 5 уникальных элементов, то метаданные просто не будут храниться, потому что там не хватает памяти. Data Skipping на них не будет работать. Поэтому основное применение — это, как ни удивительно, значения маленькой мощности, когда у нас есть мало различных значений.

Следующая итерация set — это bloom filter.

Bloom filter

Размер bloom filter регулируется, и от него зависит эффективность. Обычно bloom filter занимает довольно много места. Например, рекомендуемый размер для блока из 8 тысяч элементов при False Positive Rate 10% — это порядка 5 Кб, что довольно много.

В bloom filter используется хеширование и эффективность непрозрачная. То есть если пользователь задает Data Skipping с помощью minmax или set, то он как-то может посмотреть на данные и предсказать, как Data Skipping будет себя вести. Если он использует bloom filter, то ничего предсказать не может, потому что там хешируются и агрегируются эти биты и все от него сокрыто.

Также ванильный bloom filter умеет реализовывать только точечные запросы, то есть запросы на равенство. Есть разные расширения bloom filter, которые умеют в range-запросы, но эти расширения не очень популярны.

Bit set

Следующая ступень развития bloom filter

Давайте не хранить хеши, а используем сразу битовое представление значений, агрегируем их с помощью побитового ИЛИ.

Приходит запрос:

SELECT * WHERE value = 3;

Мы превращаем значение в битовую маску:

SELECT * WHERE value = 0b11;

И выбираем только те блоки, где все биты проставлены. 

• Размер очевиден — sizeof(element).

• Прозрачно устроен.

• Для оценки эффективности нужно думать про битовую математику.

• Совместим не со всеми типами, а только с теми, которые умеют в биты.

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

Data Skipping и логические предикаты 

Даем пользователю задать свой предикат. Например, он задал Predicate: value < 3.

На каждом блоке ставим флажок в зависимости от того, выполняется предикат хотя бы на одном элементе в этом блоке или нет. Когда приходит запрос, например SELECT * WHERE value = 1, мы понимаем, что 1 меньше 3, поэтому мы можем задействовать наш предикат и скипаем второй и третий блоки.

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

Попробуем развить еще немного. Есть довольно интересная особенность: можно задать предикат сразу по двум разным колонкам.

Посмотрим сценарий, когда есть два предиката: age < 18 и country = RUS.

Приходит запрос SELECT * WHERE age < 18 AND country = RUS, то есть запрос, который использует сразу оба бита.

По факту у нас есть только одна строка, которая удовлетворяет сразу двум предикатам.

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

Чтобы решить конкретно эту проблему из примера, мы можем скомбинировать фильтры, то есть завести предикат SELECT * WHERE age < 18 AND country = RUS.

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

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

Мы можем с помощью предикатов разбить пространство на произвольную сетку.

Например, я разбил пространство колонки age на 3 бакета: age < 18, от 18 до 25, от 26 до 40. Приходит запрос SELECT * WHERE age = 22, мы понимаем, в какой бакет он падает, и отбираем только те блоки, где у этого бакета проставлен флажок.

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

• Легко найти узкое место, то есть мы видим, что у нас всего три блока и во всех трех блоках проставлен true напротив бакета age < 18.

• Можем задавать эти предикаты вручную, а поэтому можем сами их контролировать и оптимизировать — конечно, если это позволяют наши данные.

В данном случае я просто разбиваю бакет age < 18 на 2 бакета (age < 17, age = 17).

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

Такой подход достаточно прозрачный и гибкий, но он требует контроля и его сложнее применить. Тот же minmax или bloom filter будет сам организовывать метаданные у каждого блока - в случае же с предикатами это нужно делать самому.

Выводы

• Используйте ло��ические предикаты, чтобы делать прозрачный Data Skipping.

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

• И конечно, думайте о балансировке, когда храните агрегаты рядом с данными в B-дереве. 

Скрытый текст

Если вам близки такие инженерные вызовы и хочется глубже погрузиться в архитектуру современных СУБД, приходите на HighLoad++. Там мы подробно обсуждаем реальные практики оптимизации под высокие нагрузки. Живое общение, вопросы из зала и обмен опытом ― то, что не заменит ни одна статья.