Порядок соединений в PostgreSQL: GEQO и pg_hint_plan

Запрос на 15 таблиц планируется полсекунды, а запрос из десяти таблиц выполняется в 6,4 раза дольше нужного, потому что планировщик не стал менять написанный порядок. Оба симптома растут из одного места: порядок соединений ищется в пространстве, которое растёт факториально, и PostgreSQL режет его тремя разными способами. Как читать готовые числа cost=, написано в статье про модель стоимости, как читать план — в статье про EXPLAIN ANALYZE BUFFERS. Здесь разберём сам перебор: где он точный, где случайный и где его можно переопределить руками.

Как ищется порядок

Для n таблиц существует n! порядков соединения, для 13 таблиц это 6 227 020 800. Планировщик не перебирает их по одному. Он строит лучшие пути для всех подмножеств таблиц по возрастанию размера (динамическое программирование): сначала для каждой таблицы, потом для каждой допустимой пары, потом для троек. Один уровень этой цепочки строит join_search_one_level: его комментарий называет её «one step of the dynamic-programming method» (joinrels.c).

Подмножеств у n таблиц 2^n, поэтому цена поиска примерно удваивается с каждой таблицей. Чтобы это не убило планирование, есть две отсечки. Первая: с geqo_threshold FROM-элементов (по умолчанию 12) включается генетический поиск. Выбор делается в одном месте:

		if (join_search_hook)
			return (*join_search_hook) (root, levels_needed, initial_rels);
		else if (enable_geqo && levels_needed >= geqo_threshold)
			return geqo(root, levels_needed, initial_rels);
		else
			return standard_join_search(root, levels_needed, initial_rels);

Вторая: явные JOIN склеиваются в один список для перебора только пока в нём не больше join_collapse_limit элементов (по умолчанию 8). Больше — порядок, записанный в запросе, остаётся:

		else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
				 join_collapse_limit)
		{
			/* OK to combine subproblems */
			joinlist = list_concat(leftjoinlist, rightjoinlist);
		}

Третья ручка, барьер: WITH ... AS MATERIALIZED вычисляется отдельно и в перебор снаружи не входит. Все три проверим на таблице fact с 14 справочниками.

Подготовка

docker run -d --name dba-join-order -e POSTGRES_PASSWORD=pg postgres:18
docker exec -i dba-join-order psql -U postgres -q <<'EOF'
CREATE TABLE fact AS
  SELECT g AS id, g%1000 AS d1, g%1000 AS d2, g%1000 AS d3, g%1000 AS d4, g%1000 AS d5,
         g%1000 AS d6, g%1000 AS d7, g%1000 AS d8, g%1000 AS d9, g%1000 AS d10,
         g%1000 AS d11, g%1000 AS d12, g%1000 AS d13, g%1000 AS d14
  FROM generate_series(1, 100000) g;
DO $$ BEGIN FOR i IN 1..14 LOOP
  EXECUTE format('CREATE TABLE dim%s AS SELECT g AS id, g::text AS name FROM generate_series(0,999) g', i);
  EXECUTE format('ALTER TABLE dim%s ADD PRIMARY KEY (id)', i);
END LOOP; END $$;
ANALYZE;
EOF

Запрос-звезду на N таблиц собирает небольшой скрипт; каждый справочник получает свой фильтр, чтобы порядок имел значение. Параметр rev пишет FROM в обратном порядке.

# star.sh N [rev]
N=$1; k=(0 50 1000 400 700 30 500 900 800 200 600 600 950 100 800)
t="fact f"; for i in $(seq 1 $((N-1))); do t="$t, dim$i"; done
[ "$2" = rev ] && { t=""; for i in $(seq $((N-1)) -1 1); do t="$t dim$i,"; done; t="$t fact f"; }
q="SELECT count(*) FROM $t WHERE true"
for i in $(seq 1 $((N-1))); do q="$q AND f.d$i = dim$i.id AND dim$i.id < ${k[$i]}"; done
echo "$q"

Все опыты идут на значениях по умолчанию: geqo_threshold = 12, join_collapse_limit = from_collapse_limit = 8, geqo_effort = 5, geqo_seed = 0.

Опыт 1: время планирования

Для 11–15 таблиц строим план с geqo = off (всегда полный перебор) и on (GEQO с 12 таблиц) и читаем строку Planning Time:

P(){ docker exec -i dba-join-order psql -U postgres -Atq "$@"; }
for n in 11 12 13 14 15; do q=$(bash star.sh $n); for g in off on; do
  echo -n "tables=$n geqo=$g  "
  P -c "SET geqo=$g; SET max_parallel_workers_per_gather=0; EXPLAIN (SUMMARY) $q" | grep "Planning Time"
done; done

tables=11 geqo=off  Planning Time: 16.752 ms
tables=11 geqo=on  Planning Time: 16.487 ms
tables=12 geqo=off  Planning Time: 36.835 ms
tables=12 geqo=on  Planning Time: 14.638 ms
tables=13 geqo=off  Planning Time: 79.684 ms
tables=13 geqo=on  Planning Time: 15.905 ms
tables=14 geqo=off  Planning Time: 204.351 ms
tables=14 geqo=on  Planning Time: 17.383 ms
tables=15 geqo=off  Planning Time: 542.014 ms
tables=15 geqo=on  Planning Time: 19.388 ms

DBA / 01

Полный перебор дорожает вдвое на таблицу, GEQO почти не растёт

Полный перебор на 15 таблицах стоит 542,0 мс против 19,4 мс у GEQO. На 11 таблицах пороги ещё не сработали, и обе настройки дают одно время.

Рост от 11 к 15 таблицам: 16,8 → 36,8 → 79,7 → 204,4 → 542,0 мс, то есть каждая таблица умножает время в 2,2–2,7 раза (542,0 / 204,4 = 2,65). Ниже порога geqo = on ничего не меняет (16,8 и 16,5 мс на 11 таблицах: разница — шум замера). С 12 таблиц GEQO планирует за 14,6–19,4 мс. Точность замера невысока: повторные прогоны давали разброс в 10–20 %, на порядок это не влияет.

Опыт 2: цена генетического поиска

GEQO не перебирает подмножества, а ведёт популяцию случайных порядков и скрещивает лучшие. Откуда берётся случайность, видно в коде: генератор инициализируется параметром geqo_seed.

/* initialize private number generator */
	geqo_set_seed(root, Geqo_seed);

Значит, при одном geqo_seed результат повторяется, а при другом нет. Строим план на 13 таблицах при полном переборе и при шести значениях seed и сравниваем стоимость плана:

q=$(bash star.sh 13)
echo -n "geqo=off      "; P -c "SET geqo=off; SET max_parallel_workers_per_gather=0; EXPLAIN $q" | head -1
for s in 0 0.1 0.3 0.5 0.7 0.9; do
  echo -n "geqo_seed=$s  "; P -c "SET geqo_seed=$s; SET max_parallel_workers_per_gather=0; EXPLAIN $q" | head -1
done

geqo=off      Aggregate  (cost=2475.28..2475.29 rows=1 width=8)
geqo_seed=0  Aggregate  (cost=2517.53..2517.54 rows=1 width=8)
geqo_seed=0.1  Aggregate  (cost=2486.47..2486.48 rows=1 width=8)
geqo_seed=0.3  Aggregate  (cost=2519.60..2519.61 rows=1 width=8)
geqo_seed=0.5  Aggregate  (cost=2487.40..2487.41 rows=1 width=8)
geqo_seed=0.7  Aggregate  (cost=2486.34..2486.35 rows=1 width=8)
geqo_seed=0.9  Aggregate  (cost=2491.19..2491.20 rows=1 width=8)

Полный перебор нашёл 2475,28; GEQO в зависимости от seed дал от 2486,34 до 2519,60, то есть от 0,4 % до 1,8 % хуже. На звезде с равномерными справочниками хороших порядков много, поэтому разрыв маленький. Но порядок можно сдвинуть и без seed: тот же запрос с FROM, записанным в обратном порядке, при geqo_seed = 0:

geqo_seed=0 again  Aggregate  (cost=2517.53..2517.54 rows=1 width=8)
reversed FROM, geqo_seed=0  Aggregate  (cost=2485.04..2485.05 rows=1 width=8)
reversed FROM, geqo=off  Aggregate  (cost=2475.58..2475.59 rows=1 width=8)

Повтор с тем же seed дал те же 2517,53, а перестановка таблиц в FROM сменила результат GEQO на 2485,04. Практический вывод: запрос с 12 и более элементами FROM может получить другой план от безобидной перестановки таблиц в тексте запроса, и это не «нестабильная статистика», а свойство алгоритма. Полный перебор тоже зависит от порядка при равных стоимостях (2475,28 и 2475,58), но разброс там в сотых долях процента.

Опыт 3: join_collapse_limit и явные JOIN

Теперь запрос из девяти справочников с явными JOIN, где единственный селективный фильтр (dim9.id < 3, 3 строки из 1 000) стоит у последней таблицы. Пишем JOIN в этом порядке и меняем лимит:

cat > gen3.sh <<'EOF'
q="SELECT count(*) FROM fact f"
for i in 1 2 3 4 5 6 7 8 9; do q="$q JOIN dim$i ON f.d$i = dim$i.id"; done
echo "$q WHERE dim1.id < 900 AND dim2.id < 900 AND dim3.id < 900 AND dim4.id < 900 AND dim5.id < 900 AND dim6.id < 900 AND dim7.id < 900 AND dim8.id < 900 AND dim9.id < 3"
EOF
q=$(bash gen3.sh)
for l in 1 8 10; do echo "join_collapse_limit=$l"
  P -c "SET join_collapse_limit=$l; SET max_parallel_workers_per_gather=0; EXPLAIN (ANALYZE, SUMMARY) $q" | grep -E "^Aggregate|Planning Time|Execution Time"
done

join_collapse_limit=1
Aggregate  (cost=4029.53..4029.54 rows=1 width=8) (actual time=80.704..80.710 rows=1.00 loops=1)
Planning Time: 1.299 ms
Execution Time: 80.960 ms
join_collapse_limit=8
Aggregate  (cost=3926.56..3926.57 rows=1 width=8) (actual time=71.736..71.742 rows=1.00 loops=1)
Planning Time: 2.012 ms
Execution Time: 71.871 ms
join_collapse_limit=10
Aggregate  (cost=2727.83..2727.84 rows=1 width=8) (actual time=11.159..11.164 rows=1.00 loops=1)
Planning Time: 7.276 ms
Execution Time: 11.301 ms

При значении по умолчанию 8 десять таблиц не помещаются в один список: запрос выполняется 71,9 мс, почти как при полном запрете перестановок (лимит 1 — 81,0 мс). При 10 планировщик видит все таблицы сразу, и выполнение занимает 11,3 мс, в 6,4 раза быстрее, а планирование стоит на 5 мс больше (7,3 против 2,0 мс). Позицию селективного соединения показывает номер строки плана: чем он больше, тем глубже узел и тем раньше он выполняется.

for l in 8 10; do echo "join_collapse_limit=$l"
  P -c "SET join_collapse_limit=$l; SET max_parallel_workers_per_gather=0; EXPLAIN (COSTS off) $q" | grep -n -E "Hash Cond: \(f.d(1|9) "
done

join_collapse_limit=8
4:              Hash Cond: (f.d9 = dim9.id)
18:                                                        Hash Cond: (f.d1 = dim1.id)
join_collapse_limit=10
14:                                                  Hash Cond: (f.d1 = dim1.id)
16:                                                        Hash Cond: (f.d9 = dim9.id)

При лимите 8 dim9 присоединяется после dim1 и ещё шести неселективных справочников (строка 4 против 18), и все они успевают пропустить через себя 100 000 строк fact. При 10 dim9 (строка 16) присоединяется к fact раньше dim1 (строка 14), и дальше идут только строки с тремя значениями d9.

Опыт 4: CTE как барьер

То же соединение, но восемь неселективных справочников вынесены в WITH ... MATERIALIZED, а селективный остаётся снаружи. Лимиты подняты до 12, чтобы они не мешали:

w=""; wh="true"; for i in 1 2 3 4 5 6 7 8; do w="$w JOIN dim$i ON f.d$i=dim$i.id"; wh="$wh AND dim$i.id<900"; done
for m in MATERIALIZED "NOT MATERIALIZED"; do echo "$m"
  P -c "SET join_collapse_limit=12; SET from_collapse_limit=12; SET max_parallel_workers_per_gather=0; EXPLAIN (ANALYZE, SUMMARY) WITH m AS $m (SELECT f.* FROM fact f $w WHERE $wh) SELECT count(*) FROM m JOIN dim9 ON m.d9=dim9.id WHERE dim9.id<3" | grep -E "^Aggregate|CTE Scan|Planning Time|Execution Time"
done

MATERIALIZED
Aggregate  (cost=4890.47..4890.48 rows=1 width=8) (actual time=121.629..121.639 rows=1.00 loops=1)
        ->  CTE Scan on m  (cost=0.00..860.94 rows=43047 width=4) (actual time=1.009..115.514 rows=90000.00 loops=1)
Planning Time: 3.895 ms
Execution Time: 122.795 ms
NOT MATERIALIZED
Aggregate  (cost=2727.83..2727.84 rows=1 width=8) (actual time=13.230..13.236 rows=1.00 loops=1)
Planning Time: 12.035 ms
Execution Time: 13.450 ms

Материализованный CTE сначала собирает 90 000 строк, и только потом на них накладывается фильтр по dim9: 122,8 мс. Без материализации планировщик встраивает CTE в запрос, берёт тот же план, что и в опыте 3 при лимите 10 (стоимость 2727,83), и укладывается в 13,5 мс. Оптимизатор не видит через барьер условий снаружи, поэтому MATERIALIZED нужен только там, где результат действительно должен быть вычислен один раз.

Опыт 5: подсказки pg_hint_plan

Когда планировщик ошибается, а статистику и лимиты править нельзя, порядок можно зафиксировать подсказкой. В образе postgres:18 расширения нет, его ставят из репозитория PGDG, который в образе подключён:

docker exec dba-join-order sh -c 'apt-get update -qq && apt-get install -y -qq postgresql-18-pg-hint-plan'
docker exec dba-join-order dpkg -l | grep hint

ii  postgresql-18-pg-hint-plan   1.8.1-1.pgdg13+1                     amd64        support for optimizer hints in PostgreSQL

Подсказка Leading(t1 t2 t3 ...) задаёт порядок соединений. Расширение подключается в сессии командой LOAD 'pg_hint_plan', подсказка пишется комментарием /*+ ... */ перед запросом. Запрос из опыта 3 при лимите 8 и 10, с плохим (dim9 последним) и хорошим (dim9 первым) порядком:

for l in 8 10; do for h in "Leading(dim1 f dim2 dim3 dim4 dim5 dim6 dim7 dim8 dim9)" "Leading(dim9 f dim1 dim2 dim3 dim4 dim5 dim6 dim7 dim8)"; do
  echo "limit=$l  $h"
  P -c "LOAD 'pg_hint_plan'; SET join_collapse_limit=$l; SET max_parallel_workers_per_gather=0; EXPLAIN (ANALYZE, SUMMARY) /*+ $h */ $q" | grep -E "^Aggregate|Execution Time"
done; done

limit=8  Leading(dim1 f dim2 dim3 dim4 dim5 dim6 dim7 dim8 dim9)
Aggregate  (cost=4029.53..4029.54 rows=1 width=8) (actual time=73.987..73.999 rows=1.00 loops=1)
Execution Time: 74.165 ms
limit=8  Leading(dim9 f dim1 dim2 dim3 dim4 dim5 dim6 dim7 dim8)
Aggregate  (cost=3926.56..3926.57 rows=1 width=8) (actual time=68.101..68.109 rows=1.00 loops=1)
Execution Time: 68.245 ms
limit=10  Leading(dim1 f dim2 dim3 dim4 dim5 dim6 dim7 dim8 dim9)
Aggregate  (cost=4029.53..4029.54 rows=1 width=8) (actual time=77.348..77.355 rows=1.00 loops=1)
Execution Time: 77.511 ms
limit=10  Leading(dim9 f dim1 dim2 dim3 dim4 dim5 dim6 dim7 dim8)
Aggregate  (cost=2727.83..2727.84 rows=1 width=8) (actual time=9.598..9.605 rows=1.00 loops=1)
Execution Time: 9.762 ms

Подсказка работает как рычаг, но не обходит границы, заданные лимитом. Плохой порядок она навязывает при обоих лимитах (стоимость 4029,53, как при join_collapse_limit = 1). Хороший порядок при лимите 10 даёт 2727,83 и 9,8 мс, а при лимите 8 тот же Leading оставляет стоимость 3926,56 и 68,2 мс, то есть ровно то, что планировщик выбрал и без подсказки. Синтаксис и формы Leading — в документации подсказок.

Что из этого следует

Мерь Planning Time у запросов с 8+ таблицами. План за 0,5 с на 15 таблицах (опыт 1) невидим на графиках выполнения. Сравнивай Planning Time с Execution Time в одном EXPLAIN (ANALYZE, SUMMARY).
12 элементов FROM — граница между детерминированным и зависящим от seed планом. Если запрос на 12+ таблиц внезапно сменил план без изменения данных, проверь, не сработал ли GEQO: поднять geqo_threshold выше числа таблиц и сравнить стоимость. Цена в планировании: 36,8 мс вместо 14,6 мс на 12 таблицах и 542,0 вместо 19,4 мс на 15 (опыт 1).
Если ORM или вьюха строит запрос из 9–12 явных JOIN, подними join_collapse_limit для роли или сессии, а не для всей базы. Опыт 3: 11,3 мс против 71,9 мс. Значение, равное geqo_threshold или больше, может пустить запрос в GEQO, как предупреждает документация.
WITH ... AS MATERIALIZED — барьер, и его надо ставить осознанно. На восьми соединениях он замедлил запрос с 13,5 до 122,8 мс, потому что селективный фильтр снаружи не дошёл до fact (опыт 4).
Подсказки — крайняя мера и зависят от лимитов. pg_hint_plan не лечит причину (плохую оценку строк, см. модель стоимости) и не обходит join_collapse_limit: подсказка с хорошим порядком при лимите 8 не изменила план. Сначала ANALYZE и расширенная статистика, потом лимиты, потом подсказки.

Чек-лист

Для самых длинных запросов сравни Planning Time и Execution Time через EXPLAIN (ANALYZE, SUMMARY).
Посчитай элементы FROM: при 12 и больше проверь план с SET geqo = off; если стоимость заметно ниже, оставь запросу SET LOCAL geqo_threshold или перепиши его.
Для запросов с явными JOIN проверь SHOW join_collapse_limit и число таблиц; при превышении подними лимит в сессии и сравни время выполнения.
Не материализуй CTE без причины и не оставляй старый MATERIALIZED после обновления статистики.
Убери контейнер вместе с данными: docker rm -f -v dba-join-order.

Порядок соединений в PostgreSQL: GEQO, join_collapse_limit, CTE и pg_hint_plan