Розширена оптимізація підзапитів в Oracle

  1. Розширена оптимізація підзапитів в Oracle
  2. зміст
  3. анотація
  4. 1. Введення
  5. 1.1. Перетворення запитів в Oracle
  6. 1.2. Усунення вкладеності підзапитів
  7. 1.3. віконні функції
  8. 1.3.1. Віконні функції для генерації звітів

2010 р

Розширена оптимізація підзапитів в Oracle

Срікант Белламконда, Рафі Ахмед, Анжела Амор, Мохамед Зейді

Переклад Леоніда Борчуков
Під ред. Сергія Кузнєцова

оригінал: Enhanced Subquery Optimizations in Oracle / Srikanth Bellamkonda, Rafi Ahmed, Andrew Witkowski, Angela Amor, Mohamed Zait, Chun-Chieh Lin // Proceedings of the 35th international conference on Very large data base 2009, pp. 1366 - 1377

зміст

1. Введення 1.1. Перетворення запитів в Oracle 1.2. Усунення вкладеності підзапитів 1.3. віконні функції 2. Зрощення підзапитів 2.1. Зрощування підзапитів однакового типу 2.2. Зрощування підзапитів різних типів 2.3. Зрощування та інші перетворення 2.4. Розширення можливостей виконання запитів 3. Виключення уявлень з угрупованням 3.1. виняток уявлень 4. Видалення підзапитів з використанням віконних функцій 4.1. Корельований поглинається підзапит 4.2. Некорреліровани поглинається підзапит 4.3. Поглинається підзапит в розділі HAVING 4.4. Підзапити, які повертають мультимножини 5. Масштабоване паралельне виконання 6. Антісоедіненіе з урахуванням наявності невизначених значень 6.1. Алгоритм антісоедіненія з урахуванням наявності невизначених значень 6.2. Стратегії виконання NAAJ 7. Дослідження продуктивності 7.1. зрощування підзапитів 7.2. Виняток уявлень з угрупованням 7.3. Видалення підзапитів з використанням віконних функцій 7.4. Масштабоване виконання віконних функцій 7.5. Антісоедіненіе з урахуванням наявності невизначених значень 8. Споріднені роботи 9. Висновок 10. Подяки 11. Список літератури

анотація

У статті описується розширена оптимізація підзапитів в реляційної СУБД Oracle. Розглядається кілька методів - зрощення підзапитів (subquery coalescing), видалення підзапитів з використанням віконних функцій (subquery removal using window functions) і усунення уявлень для запитів з угрупованням (group by view elimination). Ці методи розпізнають і усувають надмірність в структурах запиту і перетворять запити до потенційно більш оптимальним формам. У статті також обговорюються нові методи паралельного виконання, які мають універсальну застосовність і використовуються для поліпшення масштабованості запитів, підданих деяким з цих перетворень. Описується новий варіант антісоедіненія для оптимізації підзапитів з квантором загальності, стовпці яких можуть містити невизначене значення. Далі подаються результати перевірки продуктивності цих оптимізацій, які показують суттєве зменшення часу виконання.

1. Введення

Сучасні реляційні СУБД виконують складні SQL-запити, що включають вкладені підзапити з функціями агрегації, вистави за union / union all, distinct, group by і т.д. Такі запити стають все більш і більш важливими в системах підтримки прийняття рішень (Decision-Support System, DSS) і оперативної аналітичної обробки (On-Line Analytical Processing, OLAP). В якості методу оптимізації таких запитів прийнято використовувати перетворення запитів.

Підзапити - це потужний компонент мови SQL, що підвищує його рівень декларативності і виражальних можливостей. Стандарт SQL дозволяє використовувати вкладені запити в розділах SELECT, FROM, WHERE і HAVING. Підзапити широко використовуються в еталонних тестових наборах підтримки прийняття рішень TPC-H [4] і TPC-DS [15]. Майже половина з 22 запитів в тестовому наборі TPC-H містить підзапити. Майже всі підзапити є корельованими, і багато хто з них містять виклики агрегатних функцій. Тому ефективне виконання складних підзапитів є суттєво важливим для систем баз даних.

1.1. Перетворення запитів в Oracle

У Oracle виконується безліч перетворень запитів - усунення вкладеності підзапитів (subquery unnesting), злиття уявлень з угрупованням і видаленням дублікатів (group-by and distinct view merging), виключення загальних подвираженій (common sub-expression elimination), проштовхування предикатів з'єднань (join predicate pushdown ), факторизація з'єднань (join factorization), перетворення теоретико-множинних операцій перетину і віднімання в (анти) з'єднання (conversion of set operators intersect and minus into (anti) join), розкриття OR (OR expansion), перетворення типу "зірка" ( star transformation), розміщення операцій груп іровкі і видалення дублікатів (group-by and distinct placement) і т.д. Перетворення запитів можуть бути засновані на евристиках або оцінці вартості. При застосуванні перетворень, заснованих на оцінці вартості, для генерації оптимального плану комбінуються логічні перетворення і фізична оптимізація.

У Oracle 10g з'явилися загальна інфраструктура (framework) [8] перетворень запитів на основі оцінки вартості і кілька стратегій пошуку в просторі станів. При виконанні перетворень, заснованих на оцінці вартості, запит копіюється, перетворюється, і з використанням існуючого вартісного фізичного оптимізатора обчислюється його вартість. Цей процес повторюється кілька разів із застосуванням нових наборів перетворень; і врешті-решт вибирається одне або декілька перетворень, які застосовуються до вихідного запиту, якщо це призводить до оптимальної вартості. Інфраструктура перетворень на основі оцінки вартості забезпечує механізм для дослідження простору станів, утвореного при застосуванні одного або декількох перетворень, що дозволяє Oracle ефективним чином вибирати оптимальне перетворення. Інфраструктура перетворень на основі оцінки вартості дозволяє справлятися зі складнощами, що виникають при наявності в запиті користувача кількох блоків запиту і взаємної залежності перетворень. Наявність загальної інфраструктури перетворень на основі оцінки вартості дозволяє розширювати великий репертуар методів перетворення запитів Oracle новими перетвореннями. У цій статті представлені нові методи перетворення - зрощення підзапитів (subquery coalescing), видалення підзапитів (subquery removal) і усунення фільтруючого з'єднання (filtering join elimination).

1.2. Усунення вкладеності підзапитів

Усунення вкладеності підзапитів [1], [2], [8], [9] - це важливе перетворення запитів, підтримуване в багатьох системах баз даних. Якщо вкладеність корельованого підзапиту не зникає, він обчислюється кілька разів з використанням семантики покортежной ітерації (tuple iteration semantics). Це схоже на з'єднання методом вкладених циклів, і, отже, при цьому не можуть бути враховуватися ефективні шляхи доступу, методи з'єднань і порядки з'єднань.

У Oracle усувається вкладеність підзапитів майже всіх типів. Є дві широкі категорії методів усунення вкладеності - методи першої категорії породжують похідні таблиці (inline views, вбудовані уявлення), а методи другої категорії зливають підзапит з тілом містить його запиту. У Oracle методи першої категорії застосовується на основі оцінок вартості, а методи другої категорії - евристичним способом.

Усунення вкладеності нескалярних підзапитів часто призводить до напів-або антісоедіненіям. У Oracle для виконання напів-або анти з'єднання можуть використовуватися індексний пошук, хешування і сортування зі злиттям. Виконавчий механізм Oracle кешує результати напів- і анти з'єднань для кортежів лівої таблиці, так що можна уникнути декількох обчислень результатів підзапиту, якщо в шпальтах з'єднання лівої таблиці є велика кількість дублікатів. У Oracle усувається вкладеність підзапитів, що входять в квантифікувати (з квантором існування або загальності) порівняння з операцією порівняння, відмінною від рівності (наприклад,> ANY, <ALL і т.д.) c використанням з'єднання методом сортування зі злиттям з предикату порівняння при відсутності відповідних індексів.

Вкладеність підзапитів, є операндами операцій порівняння з квантором загальності (наприклад, <> ALL), за допомогою стовпців, в яких допускаються невизначені значення, не може бути усунена з використанням звичайного антісоедіненія. Для усунення вкладеності таких підзапитів в Oracle використовується варіант антісоедіненія, званий антісоедіненіем з урахуванням наявності невизначених значень (null-aware antijoin).

1.3. віконні функції

У стандарті SQL 2003 [11] SQL розширюється віконними функціями 1 , Які не тільки забезпечують прості і витончені виразні засоби для формулювання аналітичних запитів, але також можуть сприяти ефективній оптимізації та виконання запитів, дозволяючи уникнути численних самосоедіненій (self-join) і наявності декількох блоків запиту. Віконні функції широко використовуються в ряді аналітичних додатків. У Oracle віконні функції підтримуються починаючи з версії Oracle 8i. Синтаксис віконних функцій виглядає наступним чином:

Window_Function ([arguments]) OVER ([PARTITION BY pk1 [, pk2, ...]] [ORDER BY ok1 [, ok2, ...] [WINDOW clause]])

Віконні функції обчислюються всередині розділів (partition), що визначаються ключами pk1, pk2 і т.д. розділу PARTITION BY (PBY), над даними, упорядкованими всередині кожного розділу по значеннями ключів ok1, ok2 і т.д. розділу ORDER BY (OBY). У розділі WINDOW визначається вікно (window) (початкова та кінцева точки) для кожного рядка. Як віконних функцій можуть використовуватися агрегатні функції SQL (SUM, MIN, COUNT і т.д.), функції ранжирування (RANK, ROW_NUMBER і т.д.) або довідкові функції (LAG, LEAD, FIRST_VALUE і т.д.). Деталі синтаксису і семантики віконних функцій описані в стандарті ANSI SQL [10] [11].

Віконні функції в блоці запиту обчислюються після розділів WHERE, GROUP BY і HAVING. Oracle обчислює віконну функцію, сортуючи дані по ключам розділів PBY і OBY і виконуючи, якщо це потрібно, проходи по відсортованим даними. Ми називаємо такий спосіб виконання методом сортування вікна (window sort). Очевидно, що, якщо віконна функція не містить ключів PBY і OBY, сортування не потрібно. В цьому випадку Oracle буферизирует дані, необхідні для обчислення віконної функції, і такий спосіб виконання називається методом буферизації вікна (window buffer).

Оціночний оптимізатор Oracle усуває сортування при віконних обчисленнях, якщо вибирається план, що виробляє дані в порядку ключів PBY і OBY. У цьому випадку виконання провадиться на основі буферизації вікна, коли Oracle просто буферизирует дані і виробляє кілька проходів по ним для обчислення віконної функції. Однак якщо дані надходять впорядкованими, то для обчислення віконних функцій типу RANK, ROW_NUMBER, кумулятивних (cumulative) (наростаючих) віконних агрегатів можна уникнути і буферизації. Зберігаючи деяку інформацію про контекст (значення віконної функції і ключів PBY), можна обчислити ці функції при обробці вхідних даних.

1.3.1. Віконні функції для генерації звітів

Оптимізація підзапитів, представлена в цій статті, використовується для класу віконних функцій, які називаються віконними функціями для генерації звітів (Reporting Window Functions). Це такі віконні функції, які, в силу своєї специфікації, повертають для кожного рядка агреговане значення всіх рядків відповідного розділу (як він визначається ключами PBY). Якщо віконна функція не містить розділів OBY і WINDOW, або якщо вікно для кожного рядка включає в себе всі рядки розділу, до якого вона належить, то ця функція є віконної функцією для генерації звітів. У цій статті ми іноді називаємо ці функції агрегатами для генерації звітів (reporting aggregate).

Віконні функції для генерації звітів корисні в порівняльному аналізі, де вони забезпечують можливість порівняти значення рядка на деякому рівні деталізації зі значенням на більш загальному рівні деталізації. Наприклад, щоб обчислити для деякого тікера (коду акції) відношення щоденного обсягу біржових торгів до загального обсягу, для кожного рядка (на рівні одного дня) потрібно отримати сукупну суму за всі дні. Віконна функція, яка видає сукупну суму для всіх рядків, і її підсумкові дані виглядали б приблизно таким чином:

Q1

SELECT tiker, day, volume, SUM (volume) OVER (PARTITION BY ticker) AS "Reporting SUM" FROM stocks;

Таблиця 1. Приклад віконної функції для генерації звітів SUM

Приклад віконної функції для генерації звітів SUM

Якщо в агрегаті для генерації звітів відсутні ключі PBY, то видається їм значення є загальним підсумком по всіх рядках, так як є тільки один неявний розділ. Ми називаємо такі агрегати для генерації звітів функціями загального підсумку (grand-total, GT). Наші перетворення запитів в деяких випадках вставляють в запит GT-функції.

1 У документації Oracle згадуються в розділі 'analytic functions'

зміст вперед