Большая часть времени планировщика запросов в СУБД тратится на поиск оптимального способа соединения таблиц. В PostgreSQL используется два алгоритма: алгоритм динамического программирования, также называемый DPsize, и генетический — GEQO. В других СУБД реализовано еще множество других алгоритмов. DPhyp — алгоритм соединения на основе гиперграфов — уже используется такими СУБД как MySQL и YDB. Я задался вопросом: можно ли реализовать его в PostgreSQL? Оказывается, можно. Так и зародилось расширение pg_dphyp для PostgreSQL, реализующее альтернативный алгоритм соединения таблиц. В статье я не описываю подробно сам алгоритм, привожу только концептуальное описание его идеи, а рассказываю вот о чем:-- Какие решения пришлось принять, чтобы добавить алгоритм DPhyp в существующую кодовую базу без изменения ядра; -- Как GPLv2 помог найти эффективный алгоритм обхода соседей; -- Как проиндексировали неиндексируемое гиперрёбра; -- Планирование какого запроса смогли ускорить в 600 раз; -- Какой изъян в работе существующего планировщика был найден.Но главный сюжетный поворот — в конце... Читать далее