PostgreSQL Antipatterns: «Бесконечность — не предел!», или Немного о рекурсии

[gleb_l]

При разработке БД хорошо помнить правило — все, что делается часто и над большим количеством строк, должно делаться за логарифмическое время. Если вы можете обмануть природу за счёт частного случая (например, высокого отношения r/w, что позволяет хранить/индексировать корни тредов, как в посте, и/или использовать индексы) — вам повезло

[rinace]

По кейсу "Изменить структуру БД"
Интересно, кто-то проводил сравнения планов запросов и размеров таблиц, при количестве строк порядка 1000.

[Kilor]

При таком количестве записей в таблице при дефолтных настройках seq_page_cost/cpu_tuple_cost весьма велики шансы просто получать почти всегда Seq Scan.

[Xobotun]

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

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

[rinace]

Это к тому, а стоит ли менять структуру БД?
Будет ли запрос эффективнее рекурсивного?

[Kilor]

Если вопрос именно в эффективности на микросекундах — стоит, рекурсия сама по себе не супербыстрая:

WITH RECURSIVE T AS (
  SELECT 1 i
UNION ALL
  SELECT i + 1 FROM T WHERE i < 100
)
TABLE T;

SELECT generate_series(1, 100) i;

Результат одинаковый, а разница по времени в конкретном вырожденном случае до 10-15 раз.

[gleb_l]

Это действительно наивно. Скорость работы БД выражается не в микросекундах, а в количествах страниц/строк, которые нужно обработать для того, чтобы выполнить запрос. Движок БД — как огромный костер, который всегда горит. На него можно поставить 1000 чайников одновременно, и он вскпятит их все, скажем, за 10 минут. Можно ставить по очереди, по 10 минут на каждый. Но тогда вам потребуется 10000 минут, а большинство дров сгорит впустую.

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

В общем, даже 100 строк (особенно, если r/(r+w) достаточно высокое) и выборки частые, выиграют от использования индекса

[Kilor]

Кроме того, table scan — очень опасная операция в плане блокировок — так как будет либо залочена вся таблица, либо сразу большой диапазон. Другие треды будут в лучшем случае ждать, а в худшем — придет дедушка лок.

В PG это работает не совсем так.

[Kilor]

del