Data Skipping в новом движке Tarantool: когда полное сканирование таблицы неизбежно

Здравствуйте, читатели Хабра! Андрей Саранчин, разработчик СУБД Tarantool в VK Tech, представляет обзор работы над MemCS — новым колоночным движком Tarantool для HTAP, над которым команда трудится уже полтора года. В процессе разработки обнаружилась интересная проблема: даже при наличии индексов иногда невозможно избежать полного сканирования таблицы. В этой статье, вдохновлённой докладом для Saint HighLoad++, будет рассказано, почему полное сканирование таблицы (Sequential Scan) иногда неизбежно и как можно уменьшить его влияние с помощью Data Skipping. **Индексация данных** Чтобы понять принцип работы Data Skipping, необходимо разобраться в методах индексации данных. Существует таблица, в которой нужно найти определённые строки по заданному критерию. Есть два способа это сделать: 1. **Сканирование всей таблицы.** Этот метод заключается в переборе всех строк и выборе нужных. Он эффективен для небольших таблиц из-за отсутствия дополнительных затрат. 2. **Использование индекса.** Индекс организует данные определённым образом, например, упорядочивает их с помощью дерева поиска или разделяет на классы эквивалентности через хеш-таблицу. Однако индексы требуют значительного объёма памяти и должны обновляться при каждой записи в таблицу. Несмотря на это, они позволяют быстро находить нужные данные без перебора всех строк. В системах управления базами данных (СУБД) часто поступают разнообразные запросы. Например, в одной таблице могут быть запросы на поиск по идентификатору, возрасту, времени, имени или флагу. Для ускорения каждого типа запросов может потребоваться отдельный индекс. Однако даже при наличии индекса он не всегда ускоряет поиск записей, особенно при чтении большого количества строк. В некоторых случаях сканирование всей таблицы может быть более эффективным. При использовании индексов для ускорения чтения данных можно столкнуться с несколькими проблемами: * Каждый индекс занимает много памяти, и при большом количестве индексов может потребоваться значительный объём памяти. * Индексы нужно обновлять при каждой записи, что может замедлить вставку данных. * Индекс может оказаться бесполезным, если запросы читают большое количество данных. В таких случаях приходится сканировать таблицу целиком.