Эвристика: OR в SQL — это дорого / Хабр

Один запрос выполняется 100 мс, другой — меньше 1 мс. Оба делают одно и то же, но второй написан на странном, почти алхимическом SQL. В чём подвох? Этот перевод — расследование того, почему условие OR так дорого обходится вашей базе данных, и практическое руководство по тому, как проектировать схемы, чтобы избежать этой ловушки производительности.

Планировать запросы очень непросто. Как правило, они включают несколько условий фильтрации, связанных AND. Но зачастую разработчикам приходится использовать и условие OR:

select count(*)
from application
where submitter_id = :user_id
or reviewer_id = :user_id;

Такой запрос работает медленно. Для миллиона заявок и тысячи пользователей при равномерном распределении в обоих столбцах выполнение занимает более 100 мс при непрогретом кэше (исходный код примеров).

Если переписать запрос с одними AND:

SELECT (
   SELECT COUNT(*)
   FROM application a
   WHERE a.reviewer_id = :user_id
) + (
   SELECT COUNT(*)
   FROM application a
   WHERE a.submitter_id = :user_id
) - (
   SELECT COUNT(*)
   FROM application a
   WHERE a.submitter_id = :user_id
     AND a.reviewer_id = :user_id
);

то он выполнится меньше чем за 1 мс — в 100 с лишним раз быстрее! (Возможно, этот случай уже оптимизирован в PostgreSQL 18 благодаря патчу, но автор ещё не проверял).

Прим. ред.

В PostgreSQL 18 ничего не изменилось. Патч Александра Короткова и Андрея Лепихова, на который ссылается автор, оптимизирует другую ситуацию, когда в запросе есть несколько условий OR для одного и того же столбца

Удивительно, ведь у нас есть индексы по обоим фильтруемым столбцам.

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

Планирование запр��сов на интуитивном уровне

Представим таблицу с двумя столбцами и отдельным индексом по каждому из них:

CREATE TABLE example_table (
 text_column VARCHAR(2) NOT NULL,
 num_column  INT8       NOT NULL
);

По временнóй сложности поиск по одному столбцу схож с поиском при помощи BTreeMap<String, ExampleTable> или BTreeMap<i64, ExampleTable>.

Если же использовать составной индекс, например (text_column, num_column), поиск будет схож с BTreeMap<String, BTreeMap<i64, ExampleTable>>. Таким образом, запросы с AND (то есть поиск сначала по первому, а затем по второму столбцу), естественно, ложатся на составные индексы.

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

Найти строки, где text_column = 'ES' AND num_column = 1, можно двумя способами:

найти все строки с 'ES', а затем отфильтровать их по num_column;
найти все строки с 1, а затем отфильтровать по text_column.

Здесь возникают две проблемы:

Если в строках с 1 много значений 'ES' (или наоборот) и мы выберем не тот план, то прочитаем с диска гораздо больше данных, чем нужно. Помните: индексы хранятся на диске блоками (страницами), а ввод-вывод обычно является узким местом.
CPU и память тоже важны! Загрузка в память больших объёмов данных и их обработка могут дорого стоить, особенно при соединении с другими таблицами.

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

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

Например, если значений 1 очень много, а 'ES' — мало, статистика покажет, что 1 входит в список наиболее частых значений своего столбца (низкая селективность), а 'ES' — нет (высокая селективность). Остаётся создать индекс по более селективному столбцу.

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

Почему OR — это дорого

С условием OR всё сложнее. В запросе с условием text_column = 'ES' OR num_column = 1 можно:

применить каждый фильтр отдельно, а затем объединить результаты, как делает union distinct;
пройтись по всей таблице последовательно (sequential scan), фильтруя строки в памяти.

Статистика всё равно может помочь. Если 'ES' и 1 — редкие значения, можно выполнить индексный поиск и прочесть только подходящие строки — это лучше, чем сканировать всю таблицу. Выполнив такой поиск дважды для каждого фильтра и объединив результаты с помощью побитового OR (bitwise OR), мы избегаем последовательного сканирования. Но и такой вариант обходится дорого, как показал наш первый пример.

Кроме того, подход с побитовым OR нестабилен. Если к запросу добавляется ещё одно условие (например, дополнительный AND или сортировка по третьему столбцу), то без составных индексов (включающих этот третий столбец) придётся снова делать полный перебор.

Попробуем переписать запрос как union: (x or y) and z = (x and z) or (y and z).

Пересечения и объединения соответствуют операциям AND и OR, а также сложению и умножению. Все эти операции обладают свойствами дистрибутивности, ассоциативности и коммутативности.

Операция AND (пересечение) уменьшает объём данных, а OR (объединение) увеличивает его, а с ним и стоимость операции. Эта идея лежит в основе алгоритмов соединений с оптимальной сложностью в худшем случае (Worst-case optimal join algorithms).

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

Практические советы

В проектировании схем встречаются две типичные проблемы:

Таблица содержит несколько столбцов одинакового типа с одинаковыми ограничениями — обычно внешними ключами, ссылающимися на одну и ту же таблицу.
Представление типов-сумм (type sum) в виде отдельных таблиц.

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

Просто добавьте ещё одну таблицу

Вернёмся к первому примеру:

CREATE TABLE application (
 application_id INT8 NOT NULL,
 submitter_id   INT8 NOT NULL,
 reviewer_id    INT8 NOT NULL
);

Чтобы найти все заявки, связанные с конкретным пользователем, можно создать вспомогательную таблицу, связанную отношением «один ко многим»:

create table application_user (
 user_id int8 not null,
 application_id int8 not null,
 user_type enum ('submitter', 'reviewer') not null
);

Можно переписать запрос так, чтобы сначала использовался индекс по user_id, а затем — по application_id:

select *
from application a
join application_user au using (application_id)
where au.user_id = :user_id

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

Наследование и пагинация по ключу (keyset pagination)

Предположим, у нас есть две таблицы с общим набором столбцов:

create table post (
 user_id int8 not null,
 title text not null,
 body text not null
);
create table comment (
 user_id int8 not null,
 body text not null,
 parent_id int8 not null
);

Здесь лучший способ найти всё, что написал пользователь, — это написать запрос с union.

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

create table writing (
 writing_id int8 not null,
 user_id int8 not null,
 body text not null
);
create table post (
 writing_id int8 not null,
 title text not null,
 foreign key writing_id references writing
);
create table comment (
 writing_id int8 not null,
 parent_id int8 not null,
 foreign key writing_id references writing
);

Можно обойтись и без этого: чтобы получить все совпадения, достаточно использовать union:

select *
from (
   select p.post_id, null comment_id, p.title, p.body, null parent_id
   from post p
   where p.user_id = :user_id
   and p.post_id > :post_id_start
   order by p.post_id
   limit :page_size
   union
   select null post_id, c.comment_id, null, c.body, c.parent_id
   from comment c
   where c.user_id = :user_id
   and c.comment_id > :comment_id_start
   order by c.comment_id
   limit :page_size
) keyset
order by keyset.post_id, keyset.comment_id
limit :page_size

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

Вывод

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

По каким условиям выбираются отдельные строки или множества строк?
Преобладают чтения или записи?
- Возможен ли одновременный доступ к одним и тем же таблицам?
- ....

Если вы не используете OR, то и беспокоиться не о чем. Но кто знает, ведь всё может измениться...

Вопросы для размышления:

Как обычным инвертированным индексам удаётся эффективно обрабатывать условия OR и отрицания?
Есть ли материалы, глубоко разбирающие планирование запросов в PostgreSQL в контексте OR? Особенно при соединениях, а не только при фильтрации по одному столбцу в одной таблице.
Публиковались ли научные исследования по запросам с операцией OR?
Есть ли у расширения таблиц официальное название? В статье Джейми Брандона Against SQL упоминается, что это общеизвестный приём, но я не встречал прямого обсуждения этого подхода в контексте проектирования схем или производительности.
Были ли случаи, когда составной индекс на таблице помог ускорить запросы с операцией OR к этой таблице?

Эвристика: OR в SQL — это дорого