Пошук уроків, статей та іншого контенту
Розберіть побудову хеш-таблиці, вимоги до пам’яті та сценарії застосування Hash Join.
Hash Join — алгоритм з’єднання таблиць, який використовує хеш-таблицю для пошуку відповідних рядків.
Він особливо ефективний для з’єднань за умовою рівності:
table_a.key = table_b.keyНа відміну від Nested Loop, Hash Join не порівнює кожен рядок однієї таблиці з кожним рядком іншої. Спочатку PostgreSQL будує структуру для швидкого пошуку, а потім використовує її під час з’єднання.
Hash Join зазвичай складається з двох етапів:
Build phase — побудова хеш-таблиці.
Probe phase — пошук збігів у хеш-таблиці.
Розглянемо запит:
SELECT *
FROM orders
JOIN customers ON customers.id = orders.customer_id;У спрощеному вигляді PostgreSQL виконує такі кроки:
Читає рядки внутрішньої частини з’єднання — у цьому випадку зазвичай customers.
Обчислює хеш для значення customers.id.
Додає рядок у відповідний кошик хеш-таблиці.
Читає рядки зовнішньої частини — зазвичай orders.
Обчислює хеш для orders.customer_id.
Переходить до відповідного кошика.
Перевіряє точну рівність значень і повертає знайдені збіги.
Хеш-функція перетворює значення ключа на числове значення. Рядки з однаковим ключем потрапляють до одного кошика. Різні ключі іноді також можуть потрапити до одного кошика — це називається колізією. Тому після пошуку в кошику PostgreSQL додатково перевіряє саму умову з’єднання.
Хешування не замінює перевірку рівності. Воно лише швидко визначає, де шукати потенційні збіги.
На етапі побудови PostgreSQL читає одну сторону з’єднання та створює хеш-таблицю.
Виконуваний план часто має таку структуру:
Hash Join
Hash Cond: (orders.customer_id = customers.id)
-> Seq Scan on orders
-> Hash
-> Seq Scan on customersВузол Hash означає, що результати дочірнього вузла будуть завантажені в хеш-таблицю.
Після побудови хеш-таблиці PostgreSQL читає іншу сторону з’єднання. Для кожного рядка він:
обчислює хеш ключа;
знаходить відповідний кошик;
перевіряє умову JOIN;
повертає відповідні рядки.
У прикладі з orders і customers PostgreSQL може побудувати хеш-таблицю для customers, а потім перевірити кожен рядок orders.
Важливо: PostgreSQL не просто обирає таблицю, яка записана першою в FROM. Планувальник оцінює обсяг даних і вартість операцій та може змінити порядок виконання.
Створімо дві таблиці та наповнимо їх даними:
CREATE TEMP TABLE customers (
id integer PRIMARY KEY,
name text NOT NULL
);
CREATE TEMP TABLE orders (
id integer PRIMARY KEY,
customer_id integer NOT NULL,
amount numeric(10, 2) NOT NULL
);
INSERT INTO customers (id, name)
SELECT
id,
'Customer ' || id
FROM generate_series(1, 1000) AS id;
INSERT INTO orders (id, customer_id, amount)
SELECT
id,
((id - 1) % 1000) + 1,
(id % 500) + 10.00
FROM generate_series(1, 100000) AS id;
ANALYZE customers;
ANALYZE orders;Тепер виконаємо з’єднання та подивимося план:
SET enable_nestloop = off;
SET enable_mergejoin = off;
EXPLAIN (ANALYZE, BUFFERS)
SELECT
o.id,
o.amount,
c.name
FROM orders AS o
JOIN customers AS c
ON c.id = o.customer_id;Один із можливих планів матиме приблизно такий вигляд:
Hash Join
Hash Cond: (o.customer_id = c.id)
-> Seq Scan on orders o
-> Hash
Buckets: 1024 Batches: 1 Memory Usage: ...
-> Seq Scan on customers cКонкретні значення кількості рядків, часу та використаної пам’яті залежать від версії PostgreSQL і середовища виконання.
У цьому плані:
Hash Join — основний вузол з’єднання;
Hash Cond — умова, за якою обчислюються хеші;
Seq Scan on customers — читання таблиці, на основі якої будується хеш-таблиця;
Hash — створення хеш-таблиці;
Seq Scan on orders — читання рядків для пошуку збігів;
Buckets — кількість кошиків хеш-таблиці;
Batches — кількість пакетів обробки;
Memory Usage — пам’ять, використана хеш-вузлом.
Після експерименту параметри можна повернути до початкових значень:
RESET enable_nestloop;
RESET enable_mergejoin;Вимкнення інших алгоритмів у прикладі потрібне лише для демонстрації. У реальному застосунку не слід вимикати enable_nestloop або enable_mergejoin без чіткої причини.
Для двох наборів даних із приблизно N і M рядками побудова та пошук зазвичай мають складність, близьку до:
O(N + M)Це вигідно, коли:
з’єднання виконується за рівністю;
обидві таблиці містять багато рядків;
немає відповідного індексу або індекс не дає переваги;
послідовне читання таблиць дешевше за багато випадкових звернень;
одна зі сторін з’єднання достатньо мала, щоб ефективно розміститися в пам’яті.
На практиці вартість залежить не лише від кількості рядків. PostgreSQL також враховує:
оцінений розмір рядків;
селективність умов;
наявність індексів;
вартість послідовного та випадкового читання;
доступну пам’ять;
статистику таблиць.
Хеш-таблиця зберігає не тільки значення ключів. Для кожного рядка потрібні також:
службова інформація;
посилання на рядок;
структура кошиків;
місце для обробки колізій;
іноді додаткові копії або внутрішні структури.
Тому обсяг пам’яті більший за просту суму розмірів колонок ключа.
Основним параметром для операцій сортування та хешування є work_mem. Він задає базовий обсяг пам’яті, доступний для однієї операції виконання запиту, а не для всього запиту загалом.
Перевірити поточні значення можна так:
SHOW work_mem;
SHOW hash_mem_multiplier;У сучасних версіях PostgreSQL для хеш-операцій також використовується параметр hash_mem_multiplier. Орієнтовний ліміт пам’яті для хеш-операції визначається як:
work_mem × hash_mem_multiplierЦе не означає, що весь сервер має лише такий ліміт. Один запит може містити кілька операцій, а паралельне виконання може створювати додаткові екземпляри робочих структур.
Через це необережне глобальне збільшення work_mem може призвести до значного споживання пам’яті.
Якщо хеш-таблиця не поміщається в доступну пам’ять, PostgreSQL може розділити обробку на кілька пакетів — batches.
У плані це видно, наприклад, так:
Hash
Buckets: 16384 Batches: 8 Memory Usage: ...Принцип роботи:
PostgreSQL розподіляє рядки за пакетами на основі хешу.
Частину даних залишає в пам’яті.
Інші частини тимчасово записує у файли.
Обробляє пакети по черзі.
Для кожного пакета виконує пошук відповідностей.
Якщо:
Batches: 1це означає, що хеш-таблиця обробляється одним пакетом і зазвичай повністю поміщається в доступну пам’ять.
Кілька пакетів не є помилкою. Це механізм роботи з великими наборами даних. Однак запис і читання тимчасових даних збільшує вартість виконання.
Перевірити використання тимчасових файлів можна через:
EXPLAIN (ANALYZE, BUFFERS)
SELECT
o.id,
c.name
FROM orders AS o
JOIN customers AS c
ON c.id = o.customer_id;У результаті можуть бути показані блоки, пов’язані з тимчасовими файлами, наприклад temp read або temp written.
Збільшення work_mem іноді зменшує кількість пакетів, але це не універсальне рішення. Спочатку потрібно перевірити план і переконатися, що саме Hash Join створює проблему.
PostgreSQL обирає Hash Join на основі оцінок. Для цього планувальнику потрібна актуальна статистика про таблиці:
приблизну кількість рядків;
розподіл значень;
частоту повторень;
селективність умов.
Статистика оновлюється командою ANALYZE або автоматично через autovacuum та autoanalyze.
Якщо статистика застаріла, PostgreSQL може:
неправильно оцінити кількість рядків;
вибрати невдалу сторону для побудови хеш-таблиці;
недооцінити потрібну пам’ять;
отримати значно більше пакетів під час виконання;
вибрати Hash Join там, де кращим був би інший алгоритм.
Тому після значних змін у таблиці корисно оновити статистику:
ANALYZE orders;
ANALYZE customers;Порівнювати потрібно значення:
rows=...і:
actual rows=...у виводі EXPLAIN (ANALYZE).
Велика різниця між оціненими та фактичними рядками може пояснювати несподіваний план.
Hash Join добре підходить для таких сценаріїв:
з’єднання великих таблиць за колонками з однаковими значеннями;
відсутність корисних індексів для з’єднання;
обробка значної частини рядків обох таблиць;
аналітичні запити з послідовним читанням;
ситуація, коли одна сторона з’єднання помітно менша за іншу.
Типовий приклад:
SELECT
p.category_id,
COUNT(*) AS product_count
FROM products AS p
JOIN categories AS c
ON c.id = p.category_id
GROUP BY p.category_id;Якщо потрібно обробити велику кількість товарів і категорій, Hash Join може бути дешевшим за багаторазовий пошук через Nested Loop.
Hash Join не є найкращим алгоритмом у всіх ситуаціях.
Класичний Hash Join призначений для умов на кшталт:
a.id = b.idУмови діапазону не підходять для такого алгоритму:
a.created_at < b.created_atабо:
a.amount BETWEEN b.min_amount AND b.max_amountДля таких умов PostgreSQL може обрати інший план.
Якщо сторона, яку потрібно завантажити в хеш-таблицю, дуже велика, операція може:
споживати багато пам’яті;
використовувати багато пакетів;
створювати тимчасові файли;
виконуватися повільніше через дисковий ввід-вивід.
Якщо планувальник очікує маленьку таблицю, але фактично вона велика, Hash Join може виявитися дорожчим, ніж передбачалося під час планування.
Якщо запит повертає дуже мало рядків, а для доступу є ефективний індекс, Nested Loop з індексним скануванням може бути швидшим.
PostgreSQL має кілька алгоритмів з’єднання.
Hash Join:
використовує хеш-таблицю;
добре працює для рівності;
часто читає великі частини таблиць;
залежить від доступної пам’яті.
Nested Loop:
для кожного рядка зовнішньої таблиці шукає рядки у внутрішній;
добре працює, коли зовнішній набір малий;
особливо ефективний із відповідним індексом.
Merge Join:
обробляє два впорядковані набори;
підходить для з’єднання за рівністю;
може вимагати сортування, якщо дані вже не впорядковані.
Вибір алгоритму залежить від конкретних даних, статистики та умов запиту. Не слід визначати найкращий алгоритм лише за назвою таблиці або типом індексу.
Hash Join може бути вигідним для великих рівних з’єднань, але для малого результату або хорошого індексу Nested Loop може бути кращим.
Buckets і BatchesBuckets — внутрішні кошики хеш-таблиці.
Batches — частини даних, на які розділено операцію через обмеження пам’яті.
Велика кількість Buckets сама по собі не означає проблему. Значення Batches, більше за одиницю, вказує на пакетну обробку.
work_mem без аналізуЗбільшення work_mem для всього сервера може створити дефіцит пам’яті, оскільки ліміт застосовується до окремих операцій, а не до всього сеансу чи сервера.
Спочатку потрібно перевірити:
план виконання;
кількість пакетів;
тимчасовий ввід-вивід;
точність оцінок рядків;
наявність зайвих даних у вибірці.
Застаріла статистика може бути причиною невдалого плану. Перед висновками про алгоритм з’єднання варто перевірити, коли востаннє виконувалася команда ANALYZE.
Параметри enable_nestloop і enable_mergejoin корисні для експериментів, але не повинні бути постійним способом оптимізації конкретного запиту. Дані змінюються, тому оптимальний план також може змінитися.
Hash Join складається з етапів Build і Probe.
На етапі Build PostgreSQL створює хеш-таблицю для однієї сторони з’єднання.
На етапі Probe рядки іншої сторони шукаються через хеші.
Hash Join найкраще підходить для з’єднань за умовою рівності.
Хеш-таблиця потребує пам’яті, яку контролюють work_mem і hash_mem_multiplier.
Якщо пам’яті недостатньо, PostgreSQL використовує кілька Batches і тимчасові файли.
Для аналізу потрібно використовувати EXPLAIN (ANALYZE, BUFFERS).
Вибір Hash Join залежить від оцінок планувальника, статистики, розміру даних та альтернативних алгоритмів.