Застосування машинного навчання для збільшення продуктивності PostgreSQL

image

Машинне навчання займається пошуком прихованих закономірностей в даних. Зростаючий зростання інтересу до цієї теми в ІТ-співтоваристві пов'язаний з винятковими результатами, одержуваними завдяки йому. Розпізнавання мови і відсканованих документів, пошукові машини — все це створено з використанням машинного навчання. У цій статті я розповім про поточному проекті нашої компанії: як застосувати методи машинного навчання для збільшення продуктивності СУБД.
У першій частині цієї статті розуміється існуючий механізм планувальника PostgreSQL, у другій частині розповідається про можливості його поліпшення з застосуванням машинного навчання.



Що таке план виконання SQL-запиту?
Нагадаємо, що SQL — декларативний мову. Це означає, що користувач вказує тільки те, які операції повинні бути виконані з даними. За вибір способу виконання цих операцій відповідає СУБД. Наприклад, запит
SELECT name FROM users WHERE age > 25;

можна виконати двома способами: прочитати всі записи з таблиці users і перевірити кожну з них на виконання умови age > 25 або використовувати індекс поля age. У другому випадку ми не переглядаємо зайві записи, зате витрачаємо більше часу на обробку одного запису з-за операцій з індексами.



Розглянемо більш складний запит
SELECT messages.text FROM users, messages users WHERE.id = messages.sender_id;

Цей JOIN можна виконати вже трьома способами:
  • Вкладений цикл (NestedLoopJoin) переглядає всі можливі пари записів із двох таблиць і перевіряє для кожної пари виконання умови.
  • Злиття (MergeJoin) відсортує обидві таблиці по полям id і sender_id відповідно, а потім використовує метод двох покажчиків для пошуку всіх пар записів, що задовольняють умові. Цей метод аналогічний методу сортування злиттям (MergeSort).
  • Хешування (HashJoin) будує хеш-таблицю по полю найменшою таблиці (у нашому випадку це поле users.id). Хеш-таблиця дозволяє для кожного запису з messages швидко знайти запис, в якій users.id = messages.sender_id.


Якщо ж у запиті потрібно виконати більш однієї операції Join, то можна також виконувати їх в різному порядку, наприклад, у запиті
SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2
WHERE u1.id = m.sender_id AND u2.id = m.reciever_id;



Дерево виконання запиту називається планом виконання запиту.

Подивитися той план, який вибирає СУБД для конкретного запиту, можна, використовуючи команду
explain
:
EXPLAIN SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2
WHERE u1.id = m.sender_id AND u2.id = m.reciever_id;


Для того, щоб виконати запит і подивитися вибраний для нього план, можна використовувати команду
explain analyse
:
EXPLAIN ANALYSE SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2 
WHERE u1.id = m.sender_id AND u2.id = m.reciever_id;


Час виконання різних планів одного і того ж запиту може відрізнятися на багато порядків. Тому правильний вибір плану виконання запиту чинить серйозний вплив на продуктивність СУБД. Розберемося докладніше, як відбувається вибір плану в PostgreSQL зараз.

СУБД шукає оптимальний план виконання запиту?
Можна розділити процес пошуку оптимального плану на дві частини.

По-перше, потрібно вміти оцінювати вартість будь-якого плану — кількість ресурсів, необхідних для його виконання. У разі, коли на сервері не виконуються інші завдання і запити, оцінюваний час виконання запиту прямо пропорційно кількості витрачених на нього ресурсів. Тому можна вважати, що вартість плану — це його час виконання в деяких умовних одиницях.

По-друге, необхідно вибрати план з мінімальною оцінкою вартості. Легко показати, що число планів зростає експоненціально зі збільшенням складності запиту, тому не можна просто перебрати всі плани, оцінити вартість кожного і вибрати найдешевший. Для пошуку оптимального плану використовуються більш складні алгоритми дискретної оптимізації: динамічне програмування підмножини для простих запитів і генетичний алгоритм для складних.



У нашому проекті ми зосередилися на першій задачі: по даним планом треба передбачити його вартість. Як це можна зробити, не запускаючи план на виконання?
справдіPostgreSQL для плану предсказываются дві вартості: вартість запуску (start-up cost) і загальна вартість (total cost). Вартість запуску показує, скільки ресурсів план витратить до того, як видасть перший запис, а загальна вартість — скільки ресурсів потрібно плану для виконання. Однак це не принципово для цієї статті. Надалі під вартістю виконання будемо розуміти загальну вартість.


Ця задача також розділяється на дві підзадачі. Спочатку для кожної вершини плану (plan node) прогнозується, скільки кортежів буде відібрано в ній. Потім на основі цієї інформації оцінюється вартість виконання кожної вершини, і, відповідно, всього плану.



Ми провели невелике дослідження, щоб встановити, яка з двох підзадач в PostgreSQL вирішується гірше.
Кожна точка на малюнках нижче відповідає одній вершині плану. Для кожної вершини були передбачені кількість відібрані в неї кортежів і вартість її виконання, а потім виміряні реальна кількість відібраних кортежів і час виконання. На правій картинці відображені тільки ті вершини, для яких кількість кортежів передбачене правильно, тому по ній можна судити про якість оцінки вартості.
Залежність дійсної кількості кортежів від передбаченого Залежність часу роботи плану від вартості,
якщо кількість кортежів передбачене правильно
На першому малюнку видно, що результат вирішення першої підзадачі відрізняється від істинного на кілька порядків. На другому малюнку видно, що при правильному вирішенні першої підзадачі модель PostgreSQL досить адекватно оцінює вартість виконання того чи іншого плану, оскільки видно сильна кореляція з часом виконання. В результаті було встановлено, що від неточних рішень обох підзадач страждає продуктивність СУБД, але від невірно встановленого кількості кортежів у кожній вершині вона страждає більше.

Розглянемо використовується в PostgreSQL рішення першої підзадачі.

СУБД оцінює кількість кортежів у вершинах?
Для початку спробуємо передбачити кількість кортежів, що відбираються простим запитом
SELECT name FROM users WHERE age < 25;


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



Використовуючи гістограму, ми легко можемо відновити частку тих користувачів, які молодші за 25 років. Для кожної вершини плану частка всіх відібраних кортежів по відношенню до всіх оброблених кортежів називається вибірковість (selectivity). У наведеному прикладі вибірковість SeqScan буде дорівнює приблизно 0.3. Для отримання кількості кортежів, що відбираються вершиною, достатньо помножити вибірковість вершини на кількість оброблюваних кортежів (у разі SeqScan'а це буде кількість записів у таблиці).

Розглянемо більш складний запит
SELECT name FROM users WHERE age < 25 AND city = 'Moscow';


У цьому випадку з допомогою гістограм за віком і містах ми зможемо отримати тільки маргінальні вибірковості, тобто частку користувачів молодше 25 років і частку москвичів серед користувачів. У моделі PostgreSQL всі умови (крім пар умов виду
5 < a AND a < 7
, які автоматично перетворюються у умова
5 < a < 7
), вважаються незалежними. Математики називають дві умови A і B незалежними, якщо ймовірність того, що виконуються обидві умови одночасно, дорівнює добутку їх ймовірностей: P(A і B) = P(A)P(B). Проте в прикладному сенсі можна розуміти незалежність двох величин як те, що від значення однієї величини не залежить розподіл на іншу величину.

У чому ж проблема?


У деяких випадках припущення про незалежність умов не виконується. У таких випадках модель PostgreSQL працює не дуже добре. Є два способи боротися з цією проблемою.

Перший спосіб полягає в побудові багатовимірних гістограм. Проблема цього способу полягає в тому, що зі збільшенням розмірності багатовимірна гістограма вимагає експоненціально зростає кількість ресурсів для збереження тієї ж точності. Тому доводиться обмежуватися гістограмами маленької розмірності (2-8 вимірювань). Звідси випливає друга проблема цього методу: потрібно якимось чином зрозуміти, для яких пар (або трійок, або четвірок...) стовпців має сенс будувати багатовимірні гістограми, а для яких необов'язково.
Щоб вирішити цю проблему, потрібно або добрий адміністратор, який буде вивчати плани ресурсномістких запитів, визначати кореляції між стовпцями і вручну вказувати, які гістограми потрібно добудувати, або програмне засіб, який за допомогою статистичних тестів спробує знайти залежні один від одного стовпці. Однак не для всіх залежних стовпців має сенс будувати гістограми, тому програмне засіб також має аналізувати спільну зустрічальність стовпців в запитах. Зараз існують патчі, дозволяють використовувати в PostgreSQL багатовимірні гістограми, але в них адміністратору потрібно вручну задавати, для яких стовпців ці багатовимірні гістограми повинні бути побудовані.

Використовуємо машинне навчання для оцінки вибірковості
Однак ця стаття присвячена альтернативним підходом. Альтернативний підхід — це застосування машинного навчання для знаходження спільної вибірковості кількох умов. Як вже говорилося вище, машинне навчання займається пошуком закономірностей в даних. Дані — це набір об'єктів. У нашому випадку об'єктом є сукупність умов в одній вершині плану. За цими умовами та їх маргінальним выборочностям нам потрібно передбачити спільну вибірковість.

Спостережуваними ознаками вершини плану будуть маргінальні вибірковості всіх її умов. Будемо вважати еквівалентними між собою всі умови, які відрізняються тільки в константах. Можна розглядати це допущення як типовий прийом машинного навчання — hashing trick — застосований для зменшення розмірності простору. Однак за цим стоїть більш потужна мотивація: ми припускаємо, що вся необхідна для передбачення інформація про константах умови міститься у його маргінальної вибірковості. Можна показати це строго для простих умов виду a < const: тут вибірковості умови ми можемо відновити значення константи, тобто втрати інформації не відбувається.

Отримана задача машинного навчання буде виглядати так, як показано на малюнку.


Ми повинні передбачити самий лівий стовпець за відомих значень у всіх інших стовпцях. Таке завдання, в якому потрібно передбачити деяке дійсне число, в машинному навчанні називається завданням регресії. Метод, вирішальний її, що називається, відповідно, регрессором.

Перейдемо до логарифмам у всіх стовпцях. Зауважимо, що, якщо тепер використовувати лінійну регресію, то в якості окремого випадку ми отримаємо поточну модель PostgreSQL.

Лінійна регресія:


У випадку, коли всі параметри дорівнюють 1, отримуємо стандартну модель вибірковості PostgreSQL:


Стандартний метод гребеневої регресії пропонує шукати параметри з допомогою мінімізації наступного функціоналу:


Для тестування різних підходів ми використовували бенчмарк TPC-H

В якості простих регрессоров були використані наступні методи:
  • Гребневая лінійна регресія + стохастичний градієнтний спуск. Цей метод хороший тим, що дозволяє використовувати динамічне навчання (online learning), тому не вимагає зберігати ніяких спостережуваних об'єктів.
  • Безліч гребеневих лінійних регресій + стохастичний градієнтний спуск. Тут передбачається, що для кожного набору умов створюється окремий гребневий лінійний регрессор. Цей метод, як і минулий, хороший тим, що дозволяє використовувати динамічне навчання, тому не вимагає зберігати ніяких спостережуваних об'єктів, однак працює кілька точніше попереднього, оскільки містить істотно більше параметрів.
  • Безліч гребеневих лінійних регресій + аналітичне рішення методом Гаусса. Цей метод вимагає зберігати всі спостережувані об'єкти, але при цьому, на відміну від двох попередніх, набагато швидше настроюється під дані.
    Проте в цьому ж і його мінус: він веде себе досить нестабільно.
Пояснимо природу нестабільності, що виникає при аналітичному рішенні. Відповіді нашого регрессора є вхідними значеннями для оптимізатора, який шукає оптимальний план. Спостережувані нами об'єкти (виконуються плани), є вихідними значеннями оптимізатора. Тому спостережувані нами об'єкти залежать від відповідей регрессора. Такі системи зі зворотним зв'язком набагато складніше для вивчення, ніж системи, в яких регрессор не впливає на навколишнє середовище. Саме в цих термінах аналітичне рішення методом Гаусса є нестабільним — воно швидко навчається, але пропонує більш ризиковані рішення, тому в цілому система працює гірше.



Після детального вивчення лінійної моделі ми виявили, що вона недостатньо повно описує дані. Тому найкращі результати з випробуваних нами методів показав kNN.
  • kNN. Істотний мінус цього методу полягає в необхідності збереження у пам'яті всіх об'єктів з подальшою організацією швидкого пошуку по ним. Істотно поліпшити цю ситуацію можна, використовуючи алгоритм відбору об'єктів. Ідея наївного алгоритму відбору об'єктів: якщо передбачення на об'єкті досить хороше, то запам'ятовувати цей об'єкт не потрібно.


Також цей метод є більш стабільним, ніж лінійна регресія: для збіжності на бенчмарку TPC-H потрібно всього 2 циклу навчання, наведених на малюнку вище.

До чого призводить використання машинного навчання
Наведемо отримані результати для алгоритму kNN.

До машинного навчання Після машинного навчання


Можна бачити, що запропонований підхід справді прискорює час роботи СУБД. На одному з типів запитів бенчмарку прискорення становить 30-45%, на іншому — в 2-4 рази.

Які є шляхи розвитку?
Є ще багато напрямків для подальшого поліпшення наявного прототипу.

  1. Проблема пошуку планів. Поточний алгоритм гарантує, що в тих планах, до яких сходиться алгоритм, передбачення вибірковості будуть правильними. Однак це не гарантує глобальної оптимальності обраних планів. Пошук глобально оптимальних планів або хоча б кращого локального оптимуму — це окрема задача.
  2. Режим переривань для припинення виконання невдалого плану. У стандартній моделі PostgreSQL нам не має сенс переривати виконання плану, оскільки у нас є лише один найкращий план, і він не змінюється. Із запровадженням машинного навчання ми можемо перервати виконання плану, в якому були допущені серйозні помилки в прогнозі вибірковості, врахувати отриману інформацію і вибрати новий кращий план для виконання. У більшості випадків новий план буде істотно відрізнятися від попереднього.
  3. Режими старіння інформації. У процесі роботи СУБД змінюються дані і типові запити. Тому дані, які були отримані в минулому, можуть бути вже неактуальні. Зараз в нашій компанії ведеться робота над хорошою системою визначення актуальності інформації, і, відповідно, «забування» застарілої інформації.


Що це було?
У цій статті ми:
  • розібрали механізм роботи планувальника PostgreSQL;
  • відзначили проблеми в поточному алгоритмі оцінки вибірковості;
  • показали, як можна використовувати методи машинного навчання для оцінки вибірковості;
  • експериментально встановили, що використання машинного навчання веде до поліпшення роботи планувальника і, відповідно, прискорення роботи СУБД.


Спасибі за увагу!

image

Література


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.