Пошук уроків, статей та іншого контенту
Навчіться читати Nested Loop і визначати випадки, коли він ефективний або повільний.
Nested Loop Join — алгоритм з’єднання двох наборів рядків:
PostgreSQL бере один рядок із зовнішнього набору.
Для цього рядка шукає відповідні рядки у внутрішньому наборі.
Повторює операцію для всіх рядків зовнішнього набору.
У спрощеному вигляді алгоритм можна представити так:
для кожного рядка outer:
знайти відповідні рядки inner
додати їх до результатуНаприклад, для запиту:
SELECT o.id, o.total
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
WHERE c.email = 'anna@example.com';PostgreSQL може спочатку знайти одного клієнта, а потім виконати пошук його замовлень. Якщо для orders.customer_id є індекс, такий план може бути дуже ефективним.
Приклад плану може виглядати так:
Nested Loop (cost=0.56..12.84 rows=3 width=16)
-> Index Scan using customers_email_idx on customers c
Index Cond: (email = 'anna@example.com'::text)
-> Index Scan using orders_customer_id_idx on orders o
Index Cond: (customer_id = c.id)У цьому плані:
customers — зовнішній набір рядків;
orders — внутрішній набір;
спочатку PostgreSQL знаходить клієнта за email;
для кожного знайденого клієнта шукає замовлення за customer_id;
умова customer_id = c.id залежить від поточного рядка зовнішнього набору.
Важлива ознака Nested Loop — внутрішній вузол виконується багато разів, по одному разу для кожного рядка зовнішнього вузла.
Для аналізу фактичного виконання використовуйте:
EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, o.total
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id
WHERE c.email = 'anna@example.com';Результат може мати такий вигляд:
Nested Loop (cost=0.56..12.84 rows=3 width=16)
(actual time=0.035..0.051 rows=3 loops=1)
Buffers: shared hit=8
-> Index Scan using customers_email_idx on customers c
(cost=0.28..4.30 rows=1 width=8)
(actual time=0.018..0.020 rows=1 loops=1)
Index Cond: (email = 'anna@example.com'::text)
-> Index Scan using orders_customer_id_idx on orders o
(cost=0.28..8.50 rows=3 width=16)
(actual time=0.012..0.018 rows=3 loops=1)
Index Cond: (customer_id = c.id)
Buffers: shared hit=5Основні поля:
cost — оцінка планувальника, а не час у мілісекундах;
actual time — фактичний час виконання вузла;
rows — кількість рядків;
loops — кількість виконань вузла;
Buffers — інформація про читання сторінок із буферного кешу або диска.
loopsЯкщо внутрішній вузол має:
actual time=0.010..0.020 rows=4 loops=1000це означає, що вузол запускався 1000 разів. Значення часу в EXPLAIN зазвичай показується для одного виконання вузла, тому загальний вплив можна приблизно оцінити так:
кількість виконань × час одного виконанняУ цьому прикладі внутрішній пошук повертає приблизно 4 рядки за кожен із 1000 запусків. Саме тому навіть невелика вартість одного пошуку може стати значною в сумі.
Наступний приклад створює тимчасові таблиці, додає дані та показує запит, для якого Nested Loop є природним вибором.
CREATE TEMP TABLE customers (
id integer PRIMARY KEY,
email text NOT NULL
);
CREATE TEMP TABLE orders (
id integer PRIMARY KEY,
customer_id integer NOT NULL,
total numeric(10, 2) NOT NULL
);
INSERT INTO customers (id, email)
SELECT
value,
'customer' || value || '@example.com'
FROM generate_series(1, 1000) AS value;
INSERT INTO orders (id, customer_id, total)
SELECT
value,
((value - 1) % 1000) + 1,
(value % 200) + 10.00
FROM generate_series(1, 10000) AS value;
CREATE INDEX orders_customer_id_idx
ON orders (customer_id);
ANALYZE customers;
ANALYZE orders;
EXPLAIN (ANALYZE, BUFFERS)
SELECT
c.email,
o.id AS order_id,
o.total
FROM customers AS c
JOIN orders AS o
ON o.customer_id = c.id
WHERE c.id <= 3;Умова c.id <= 3 повертає лише кілька рядків із customers. Для кожного з них PostgreSQL може швидко використати індекс orders_customer_id_idx.
Типова структура плану:
Nested Loop
-> Index Scan using customers_pkey on customers c
Index Cond: (id <= 3)
-> Bitmap Heap Scan on orders o
Recheck Cond: (customer_id = c.id)
-> Bitmap Index Scan on orders_customer_id_idx
Index Cond: (customer_id = c.id)Конкретний план може відрізнятися залежно від версії PostgreSQL, статистики та обсягу даних. Важливим є не точний текст плану, а його структура: невеликий зовнішній набір і пошук у внутрішньому наборі за індексом.
Nested Loop зазвичай добре працює за таких умов.
Якщо зовнішній вузол повертає кілька рядків, внутрішній пошук виконується мало разів.
Наприклад:
SELECT o.id, o.total
FROM customers AS c
JOIN orders AS o ON o.customer_id = c.id
WHERE c.id = 42;Якщо знайдено одного клієнта, PostgreSQL виконує пошук замовлень лише для одного значення customer_id.
Для умови:
ON o.customer_id = c.idкорисним буде індекс:
CREATE INDEX orders_customer_id_idx
ON orders (customer_id);Тоді кожна ітерація може виконувати індексний пошук, а не повне сканування таблиці.
Навіть якщо зовнішній набір не зовсім малий, Nested Loop може бути ефективним, якщо кожна ітерація знаходить один або кілька рядків.
Nested Loop може почати повертати перші рядки до завершення повного з’єднання. Це корисно, наприклад, коли запит має:
LIMIT 20Але це не гарантує швидкого виконання в кожному випадку: PostgreSQL усе одно має виконати необхідні вузли для отримання потрібного результату.
Якщо зовнішній вузол повертає сотні тисяч або мільйони рядків, внутрішній вузол запускається стільки ж разів.
Наприклад:
SELECT o.id, c.email
FROM orders AS o
JOIN customers AS c ON c.id = o.customer_id;Якщо зовнішнім вузлом є вся таблиця orders, пошук клієнта може виконуватися для кожного замовлення. Навіть індексний пошук може стати дорогим через велику кількість повторень.
Невдалий варіант може виглядати так:
Nested Loop
-> Seq Scan on customers
-> Seq Scan on orders
Filter: (customer_id = customers.id)Якщо внутрішня таблиця сканується повністю для кожного рядка зовнішньої таблиці, складність наближається до:
кількість рядків outer × кількість рядків innerДля великих таблиць це може бути дуже повільно.
Індекс не завжди робить Nested Loop ефективним. Якщо кожне значення ключа відповідає великій частині внутрішньої таблиці, PostgreSQL змушений обробити багато рядків на кожній ітерації.
У такій ситуації послідовне читання таблиць і алгоритм Hash Join можуть бути кращими.
Для Nested Loop важливо оцінювати не лише час одного пошуку, а кількість його повторень.
У спрощеному вигляді вартість можна уявити так:
вартість зовнішнього вузла +
кількість рядків outer × вартість внутрішнього вузлаНаприклад:
зовнішній вузол повертає 10 рядків;
один індексний пошук у внутрішній таблиці займає мало часу;
внутрішній вузол запускається 10 разів.
Це часто швидко.
Інший випадок:
зовнішній вузол повертає 1 000 000 рядків;
внутрішній індексний пошук займає лише 0,05 мс;
пошук повторюється 1 000 000 разів.
Сумарна вартість уже може бути значною.
Index Cond і FilterУ плані Nested Loop корисно звертати увагу на умови внутрішнього вузла.
Ефективніший варіант:
Index Scan using orders_customer_id_idx on orders o
Index Cond: (customer_id = c.id)Умова використовується самим індексом. PostgreSQL одразу шукає потрібний діапазон значень.
Менш ефективний варіант:
Index Scan using orders_status_idx on orders o
Index Cond: (status = 'paid')
Filter: (customer_id = c.id)Тут індекс обмежує рядки лише за status, а умова customer_id = c.id перевіряється після отримання рядків. Якщо замовлень зі статусом paid багато, кожна ітерація може обробляти зайві дані.
Для частого запиту можна розглянути складений індекс:
CREATE INDEX orders_customer_status_idx
ON orders (customer_id, status);Після цього PostgreSQL може ефективніше застосовувати обидві умови. Потрібність такого індексу слід перевіряти за реальним планом і запитами, а не створювати індекси автоматично.
Порівнюйте значення rows і actual rows.
Наприклад:
Nested Loop (cost=... rows=10 ...)
(actual time=... rows=50000 loops=1)Планувальник очікував 10 рядків, але фактично отримав 50 000. Така помилка може призвести до невдалого вибору Nested Loop.
Перевіряйте:
чи виконано ANALYZE;
чи актуальна статистика таблиць;
чи немає дуже нерівномірного розподілу значень;
чи відповідають умови запиту даним у таблицях.
Оновити статистику можна так:
ANALYZE customers;
ANALYZE orders;Якщо оцінки сильно відрізняються від фактичних, спочатку потрібно зрозуміти причину, а не просто вимикати Nested Loop.
PostgreSQL може використовувати різні алгоритми з’єднання:
Nested Loop — повторює пошук у внутрішньому наборі;
Hash Join — будує хеш-структуру для одного набору та шукає відповідності;
Merge Join — з’єднує впорядковані набори.
Для великих наборів даних Hash Join або Merge Join часто ефективніші, ніж Nested Loop. Для маленького зовнішнього набору та точкового індексного пошуку Nested Loop часто має перевагу.
Не слід оцінювати алгоритм лише за його назвою. Важливі:
кількість рядків на кожному етапі;
кількість loops;
наявність індексів;
фактичний час;
використання буферів;
відповідність оцінок реальним даним.
Дотримуйтеся послідовності:
Запустіть запит із EXPLAIN (ANALYZE, BUFFERS).
Знайдіть вузол Nested Loop.
Перевірте, скільки рядків повертає зовнішній вузол.
Перевірте loops внутрішнього вузла.
Подивіться, чи використовує внутрішній вузол індекс.
Перевірте, чи збігаються оцінки rows із actual rows.
Оцініть, скільки зайвих рядків відкидається через Filter.
Перевірте, чи актуальна статистика таблиць.
Приклад запиту для аналізу:
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT
c.id,
count(o.id) AS order_count
FROM customers AS c
JOIN orders AS o
ON o.customer_id = c.id
WHERE c.id <= 100
GROUP BY c.id;Якщо зовнішній набір має 100 рядків, а внутрішній вузол запускається 100 разів — це очікувана поведінка Nested Loop. Питання полягає в тому, наскільки швидким є кожен із цих 100 пошуків.
Для діагностики можна тимчасово вимкнути алгоритм у поточній сесії:
SET enable_nestloop = off;
EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, c.email
FROM orders AS o
JOIN customers AS c
ON c.id = o.customer_id;
RESET enable_nestloop;Це допомагає порівняти альтернативний план. Але вимикати Nested Loop як постійне рішення зазвичай не варто. Планувальник може правильно використовувати його для інших запитів.
Краще виправити причину проблеми:
додати відповідний індекс;
оновити статистику;
уточнити умови запиту;
перевірити помилкові оцінки кількості рядків;
зменшити зовнішній набір, якщо це відповідає вимогам запиту.
Nested Loop не є помилкою. Він часто є найкращим вибором для невеликого зовнішнього набору та індексного пошуку.
costcost — внутрішня оцінка планувальника. Для діагностики фактичної проблеми використовуйте EXPLAIN ANALYZE і порівнюйте реальний час.
loopsЧас одного виконання внутрішнього вузла може бути малим, але велика кількість loops робить сумарну вартість високою.
Індекс має відповідати умовам пошуку. Якщо внутрішній вузол усе одно читає багато рядків і відкидає їх через Filter, індекс може не вирішити проблему.
Для Nested Loop особливо важливо, щоб внутрішній вузол міг швидко шукати рядки за значенням із зовнішнього вузла.
SET enable_nestloop = off — інструмент для порівняння планів, а не універсальне виправлення продуктивності.
Nested Loop Join обробляє зовнішні рядки по одному та шукає відповідності у внутрішньому наборі.
Кількість запусків внутрішнього вузла показує поле loops.
Nested Loop ефективний для невеликого зовнішнього набору та швидкого індексного пошуку у внутрішній таблиці.
Великий зовнішній набір або повне сканування внутрішньої таблиці на кожній ітерації можуть зробити його повільним.
Аналізуйте actual rows, loops, Index Cond, Filter і Buffers.
Сильно неточні оцінки кількості рядків можуть призвести до невдалого плану.
Перед зміною налаштувань PostgreSQL перевірте індекси, статистику та фактичну структуру плану.