Пошук уроків, статей та іншого контенту
Дослідіть Merge Join, сортування вхідних даних і переваги з’єднання впорядкованих наборів.
Merge Join — алгоритм з’єднання двох наборів даних, які впорядковані за ключем з’єднання.
Алгоритм працює за принципом злиття двох відсортованих послідовностей:
PostgreSQL читає поточний рядок з кожного джерела.
Порівнює значення ключів.
Якщо ключі однакові — формує рядки результату.
Якщо один ключ менший — переходить до наступного рядка у відповідному наборі.
Повторює процес, доки один із наборів не буде прочитано повністю.
Наприклад, для запиту:
SELECT *
FROM orders
JOIN customers ON customers.id = orders.customer_id;PostgreSQL може впорядкувати обидві таблиці за відповідними ключами:
orders.customer_id;
customers.id.
Після цього він послідовно проходить обидва набори, не порівнюючи кожен рядок з кожним.
Merge Join очікує, що його вхідні дані вже впорядковані за ключами з’єднання. Якщо це не так, PostgreSQL додає до плану вузли Sort.
Приклад спрощеного плану:
Merge Join
Merge Cond: (orders.customer_id = customers.id)
-> Sort
Sort Key: orders.customer_id
-> Seq Scan on orders
-> Sort
Sort Key: customers.id
-> Seq Scan on customersСпочатку кожна таблиця читається, потім сортується, а вже після цього виконується з’єднання.
Саме сортування може бути найдорожчою частиною такого плану. Якщо набір даних не поміщається в доступну пам’ять, PostgreSQL може виконувати сортування з використанням тимчасових файлів на диску.
EXPLAINНаведений приклад створює дві тимчасові таблиці, наповнює їх даними та примусово вимикає альтернативні алгоритми з’єднання. Це допомагає побачити саме Merge Join у плані.
BEGIN;
CREATE TEMP TABLE customers (
id integer,
name text
);
CREATE TEMP TABLE orders (
id integer,
customer_id integer,
amount numeric(10, 2)
);
INSERT INTO customers (id, name)
SELECT
id,
'Customer ' || id
FROM generate_series(1, 10000) AS id;
INSERT INTO orders (id, customer_id, amount)
SELECT
id,
((id - 1) % 10000) + 1,
round((random() * 1000)::numeric, 2)
FROM generate_series(1, 50000) AS id;
ANALYZE customers;
ANALYZE orders;
-- Вимикаємо інші алгоритми, щоб продемонструвати Merge Join.
SET enable_hashjoin = off;
SET enable_nestloop = off;
EXPLAIN (ANALYZE, BUFFERS)
SELECT
orders.id,
orders.amount,
customers.name
FROM orders
JOIN customers
ON customers.id = orders.customer_id;
ROLLBACK;У плані можна побачити структуру, подібну до такої:
Merge Join
Merge Cond: (orders.customer_id = customers.id)
-> Sort
Sort Key: orders.customer_id
-> Seq Scan on orders
-> Sort
Sort Key: customers.id
-> Seq Scan on customersТочні значення часу, кількості рядків і використаної пам’яті залежать від версії PostgreSQL та середовища виконання.
EXPLAIN (ANALYZE, BUFFERS) показує:
фактичний час виконання;
оцінену та фактичну кількість рядків;
кількість проходів вузлів;
використання буферів;
фактичні операції сортування.
Уявімо два впорядковані набори ключів:
Ліва сторона: 1, 2, 2, 5, 8
Права сторона: 2, 3, 5, 8, 8Алгоритм діє так:
Порівнює 1 і 2.
Оскільки 1 менше, переходить до наступного ключа ліворуч.
Порівнює 2 і 2 та створює відповідні комбінації рядків.
Переходить далі, пропускаючи ключі, які не можуть мати пару.
Для однакових значень враховує всі рядки з відповідної групи.
Якщо ключ повторюється в обох таблицях, результат міститиме всі комбінації рядків із цим ключем.
Наприклад, якщо зліва є три рядки з ключем 10, а справа — два, результат міститиме шість рядків для ключа 10.
Після сортування алгоритм проходить кожен вхідний набір послідовно. Це особливо корисно, коли потрібно з’єднати великі таблиці.
На відміну від наївного порівняння кожного рядка з кожним, Merge Join не виконує повний декартів пошук пар.
Додаткове сортування може бути непотрібним, якщо PostgreSQL отримує дані вже в потрібному порядку.
Наприклад, джерелом такого порядку може бути індекс, який дає змогу прочитати рядки за ключем з’єднання. У такому випадку план може не містити Sort для відповідної сторони.
Спрощений варіант плану:
Merge Join
Merge Cond: (orders.customer_id = customers.id)
-> Index Scan using orders_customer_id_idx on orders
-> Index Scan using customers_pkey on customersНаявність індексу сама по собі не гарантує використання Merge Join. Планувальник порівнює вартість різних планів і вибирає найдешевший.
Merge Join не обов’язково має зберігати всі рядки обох таблиць у пам’яті. Він переважно рухається вперед по відсортованих потоках.
Однак сортування перед з’єднанням може потребувати значного обсягу пам’яті або тимчасового дискового простору.
Оскільки вхідні дані впорядковані за ключем, Merge Join іноді може допомогти зберегти потрібний порядок для наступних операцій плану.
Це може зменшити потребу в окремому сортуванні, але залежить від конкретного запиту та структури плану.
Merge Join вигідний не в усіх ситуаціях. Якщо вхідні дані не впорядковані, PostgreSQL повинен спочатку відсортувати їх.
Вартість залежить від:
кількості рядків;
розміру рядків;
доступної пам’яті;
наявності придатних індексів;
вибірковості фільтрів;
того, чи можна прочитати дані в потрібному порядку.
Параметр work_mem визначає обсяг пам’яті, який може використовувати окрема операція сортування. Якщо пам’яті недостатньо, сортування може перейти до диска.
Перевірити це можна через EXPLAIN (ANALYZE):
Sort Method: quicksort Memory: 4200kBабо:
Sort Method: external merge Disk: 12000kBexternal merge означає, що PostgreSQL використовував тимчасові файли на диску.
Збільшення work_mem іноді пришвидшує сортування, але змінювати цей параметр потрібно обережно: у запиті може виконуватися кілька операцій сортування одночасно.
Планувальник розглядає Merge Join як один із можливих алгоритмів для з’єднання. Він може вибрати його, якщо:
обидві сторони вже впорядковані;
потрібний порядок можна отримати через індекси;
таблиці великі;
вартість сортування прийнятна;
з’єднання виконується за сумісним оператором порівняння, зазвичай =;
альтернативні плани є дорожчими.
Наявність звичайного INNER JOIN у SQL-запиті не означає, що буде використано Merge Join. SQL описує результат, а не спосіб його отримання.
Побачити фактичний алгоритм можна за допомогою:
EXPLAIN (ANALYZE)
SELECT
orders.id,
customers.name
FROM orders
JOIN customers
ON customers.id = orders.customer_id;Для аналізу реальної продуктивності важливо використовувати EXPLAIN (ANALYZE), оскільки лише EXPLAIN показує оцінений план, а не фактичний час виконання.
Hash Join зазвичай добре працює для з’єднання невпорядкованих наборів за рівністю:
ON left_table.key = right_table.keyВін будує хеш-таблицю для однієї сторони та шукає відповідності з іншої. Якщо дані вже впорядковані або потрібен порядок результату, Merge Join може бути вигіднішим.
Nested Loop може бути ефективним, коли одна сторона дуже мала, а для іншої є відповідний індекс.
Для двох великих наборів без зручного доступу Nested Loop часто виконує надто багато перевірок. У такому випадку Merge Join може бути кращим, особливо якщо дані можна швидко відсортувати або вже впорядкувати.
ORDER BY завжди потрібенMerge Join може використовувати внутрішнє сортування у плані, навіть якщо запит не містить ORDER BY.
ORDER BY визначає порядок фінального результату для користувача. Сортування, потрібне Merge Join, є внутрішньою деталлю виконання запиту.
Параметри на кшталт:
SET enable_hashjoin = off;
SET enable_nestloop = off;корисні для навчання та діагностики. Але зазвичай не варто залишати їх вимкненими в робочому середовищі. Планувальник має можливість вибрати інший алгоритм, якщо дані або параметри запиту зміняться.
SortПобачивши Merge Join, потрібно перевірити його дочірні вузли. Якщо перед ним виконуються два великі сортування, саме вони можуть бути основною причиною повільного запиту.
Merge Join не є автоматично швидшим або повільнішим за Hash Join. Потрібно оцінювати весь план:
обсяг даних;
оцінки та фактичні кількості рядків;
операції сортування;
використання індексів;
час виконання;
читання з диска.
Планувальник приймає рішення на основі статистики таблиць. Після значних змін у даних корисно оновити її:
ANALYZE customers;
ANALYZE orders;Неточні оцінки можуть призвести до вибору невигідного плану.
Merge Join з’єднує два набори, впорядковані за ключем з’єднання.
Алгоритм послідовно рухається по обох наборах і порівнює поточні ключі.
Якщо дані не впорядковані, PostgreSQL додає операції Sort.
Індекси можуть надати дані в потрібному порядку та зменшити потребу в сортуванні.
Merge Join особливо корисний для великих наборів і вже впорядкованих даних.
Вартість сортування може зменшити переваги цього алгоритму.
Фактичний план потрібно перевіряти через EXPLAIN (ANALYZE).
Вибір між Merge Join, Hash Join і Nested Loop робить планувальник на основі оціненої вартості.