Подорож запиту Select через нутрощі Постгреса

До конференції PG Day'16 Russia залишилися лічені дні, розклад можна подивитися на нашому сайті. Ми працюємо в поті чола, але тим не менш встигаємо готувати для вас переклади самих цікавих матеріалів про PostgreSQL. Сьогодні представляємо вашій увазі переклад статті Pat Shaughnessy про поведінку запиту Select.

Готуючись влітку до цієї презентації, я вирішив вивчити деякі частини вихідного коду PostgreSQL на C. Я запустив дуже простий запит select і спостерігав, що Постгрес з ним робить, з допомогою LLDB, відладчика C. Як Постгрес зрозумів мій запит? Як він знайшов дані, які я шукав?



Цей пост — неформальний журнал моєї подорожі через нутрощі PostgreSQL. Я опишу пройдений мною шлях і те, що я бачив у процесі. Я використовую серію простих концептуальних діаграм, щоб пояснити, як Постгрес виконав мій запит. У разі, якщо ви розумієте C, я залишу вам декілька орієнтирів і покажчиків, які ви можете пошукати, якщо раптом вирішите покопатися в нутрощах Постгреса.

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

У пошуках Капітана Немо
Ось приклад запиту з першої половини моєї презентації. Ми будемо слідувати за Постгресом, поки він шукає Капітана Немо:



Знайти одне єдине ім'я в текстовому стовпці має бути досить просто, чи не так? Ми будемо міцно триматися за цей запит select, досліджуючи нутрощі Постгреса, як глибоководні нирці тримаються за мотузку, щоб знайти шлях назад на поверхню.

Картина в цілому
Що Постгрес робить з цієї SQL рядком? Він розуміє, що ми маємо на увазі? Як він дізнається, які дані ми шукаємо?

Постгрес обробляє кожну SQL команду, яку ми відправляємо йому, в чотири кроки.


Спочатку PostgreSQL виробляє синтаксичний аналіз («парсинг») нашого запиту SQL і конвертує його в ряд збережених в пам'яті структур даних мови C дерево синтаксичного аналізу (parse tree). Далі Постгрес аналізує переписує наш запит, оптимізуючи і спрощуючи його з допомогою серії складних алгоритмів. Після цього він генерує план для пошуку наших даних. Немов людина з обсесивно-компульсивним розладом, що не вийде з будинку, поки його портфель не буде ретельно упакований, Постгрес не запустить наш запит, поки у нього не буде плану. Нарешті, Postgres виконує наш запит. В цій презентації я коротко торкнуся перших трьох кроків, після чого зосереджуся на останньому: виконанні запиту.

Функція C всередині Постгреса, яка виконує цей чотириступінчастий процес, називається exec_simple_query. Ви можете знайти посилання на неї нижче разом з трасуванням LLDB, яка показує деталі того, коли саме і як Постгрес викликає exec_simple_query.



image
exec_simple_queryview on postgresql.org

image
image



Синтаксичний аналіз
Як Постгрес розуміє SQL рядок, яку ми йому відправили? Як він знаходить сенс в ключових словах і виразах SQL нашого запиту select? Через процес під назвою синтаксичний аналіз (парсинг). Постгрес конвертує нашу SQL рядок у внутрішню структуру даних, яку він розуміє — дерево синтаксичного аналізу.

Виявляється, Постгрес використовує ту ж технологію парсинга, що і Ruby, а саме — генератор синтаксичного аналізатора під назвою Bison. Bison працює під час процесу складання постгреса і генерує код парсера на підставі ряду граматичних правил. Згенерований код програми — це те, що працює всередині Постгреса, коли ми відправляємо йому SQL команди. Кожне граматичне правило викликається, коли згенерований парсер знаходить відповідний патерн або синтаксис в рядку SQL і вставляє нову структуру пам'яті C в дерево синтаксичного аналізу.

Сьогодні я не буду витрачати час на детальне пояснення того, як працює алгоритм парсингу. Якщо вам цікаві подібні теми, то раджу почитати мою книгу Ruby Under a Microscope. В першому розділі я детально розглядаю приклад алгоритму синтаксичного аналізу LALR, використовуваного Bison і Ruby. Постгрес парсити SQL запит абсолютно таким же чином.

Використовуючи LLDB і активувавши деякий логирующий код C, я спостерігав, як парсер Постгреса створив наступне дерево синтаксичного аналізу для нашого запиту з пошуку Капітана Немо:


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

Якщо ви хочете дізнатися більше про те, як Постгрес парсити SQL запити, пройдіть за порядком виконання від exec_simple_query через іншу функцію C під назвою pg_parse_query.



image
pg_parse_queryview on postgresql.org






Як ви бачите, у вихідному коді Постгреса багато корисних і докладних коментарів, які не тільки пояснюють, що відбувається, але і вказують на важливі проектні рішення.

Вся робота псу під хвіст
Дерево синтаксичного аналізу вище швидше за все здалося знайомим — це майже в точності те ж абстрактне синтаксичне дерево (AST), за створенням якого в ActiveRecord ми спостерігали раніше. Згадайте першу частину презентації: ActiveRecord згенерував наш запит select про Капітана Немо, коли ми виконали ось цей запит на Ruby:


Ми бачили, що ActiveRecord створив внутрішнє подання AST, коли ми викликали такі методи, як where і first. Пізніше (дивіться другий пост) ми спостерігали за тим, як gem Arel конвертував AST в наш приклад запиту select з допомогою алгоритму, заснованого на паттерне visitor.

Якщо подумати, дуже іронічно, що перше, що Постгрес робить з вашим SQL запитом — конвертує його з рядка назад у AST. Процес парсингу в Постгресе скасовує все, що ActiveRecord робив до цього, вся важка робота, яку виконав gem Arel, пройшла даром! Єдиною причиною для створення SQL рядки було звернення до Постгресу по мережі. Але як тільки Постгрес отримав запит, він переконвертировал його назад в AST, що є набагато більш зручним і корисним способом подання запитів.

Дізнавшись це, ви можете запитати: а чи немає кращого способу? Немає іншого способу концептуально пояснити Постгресу, які дані нам потрібні без написання SQL-запиту? Без вивчення складного мови SQL або додаткових накладних витрат за використання ActiveRecord і Arel? Здається жахливою тратою часу йти таким довгим шляхом, створюючи SQL рядок з AST тільки для того, щоб знову перетворити її назад у AST. Може, варто використовувати замість цього NoSQL рішення?

Звичайно, AST, використовуваний Постгресом, сильно відрізняється від AST, використовуваного ActiveRecord. У ActiveRecord AST складається з об'єктів Ruby, а в Постгресе — з серії збережених в пам'яті структур мови C. Ідея одна, але реалізація дуже різна.

Аналіз і перезапис
Як тільки Постгрес згенерував дерево синтаксичного аналізу, він конвертує його в інше дерево, використовуючи інший набір вузлів. Воно відоме як дерево запиту. Повернувшись до функції C exec_simple_query, ви можете побачити, що далі викликається інша функція C — pg_analyze_and_rewrite.



image
pg_analyze_and_rewriteview on postgresql.org






Якщо не вдаватися в подробиці, процес аналізу і перезапису застосовує ряд складних алгоритмів і евристик у спробі оптимізувати і спростити ваш SQL-запит. Якщо ви виконали складний запит select з вкладеними запитами та безліччю inner і outer join, то простір для оптимізації величезний. Цілком можливо, що у Постгреса вийде зменшити кількість вкладених запитів або об'єднань, щоб зробити більш простий запит, який буде виконуватися швидше.

Для нашого простого запиту select pg_analyze_and_rewrite створив ось таке дерево запиту:


Не буду прикидатися, що розумію детально алгоритми, які стоять за pg_analyze_and_rewrite. Я просто зауважив, що для нашого прикладу дерево запиту дуже схоже на дерево синтаксичного аналізу. Це означає, що запит select був настільки простим, що Постгрес не зміг зробити його ще простіше.

План
Останнє, що Посгрес робить перш, ніж розпочати виконувати наш запит, — створює план. Цей процес включає в себе створення третього дерева вузлів, які представляють собою список інструкцій для Постгреса. Ось дерево плану для нашого запиту select:



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

Функція C, яка починає процес планування запиту, називається pg_plan_queries.



image
pg_plan_queriesview on postgresql.org






Зверніть увагу на значення startup_cost і total_cost в кожному вузлі. Постгрес використовує ці значення, щоб оцінити, скільки часу буде потрібно на виконання плану. Вам не потрібно використовувати відладчик C, щоб побачити план виконання вашого запиту. Просто додайте в початок запиту команду SQL EXPLAIN. Ось так:


Це відмінний спосіб зрозуміти, що Постгрес внутрішньо проробляє з одним з ваших запитів і чому він може бути повільним або неефективним, незважаючи на складні алгоритми планування в pg_plan_queries.

Виконання вузла плану Limit
До цього моменту Постгрес піддав вашу SQL рядок синтаксичному аналізу і конвертував її назад у AST. Потім він її оптимізував і переписав, ймовірно, спростивши. Після цього Постгрес написав план, яким буде слідувати, щоб знайти і повернути дані, які ви шукаєте. І нарешті, настав час Постгресу виконати ваш запит! Як він це зробить? Дотримуючись плану, звичайно ж!

Давайте почнемо з верху дерева плану і будемо рухатися вниз. Якщо пропустити кореневий вузол, то перший працівник, якого Постгрес використовує для нашого запиту про Капітана Немо, називається Limit. Вузол Limit, як ви могли здогадатися, виконує команду SQL LIMIT, яка обмежує результат певною кількістю записів. Також цей вузол плану виконує команду OFFSET, яка ініціює вікно з набором результатів, починаючи з вказаного рядка.



При першому виклику вузла Limit Постгрес обчислює, якими повинні бути значення limit і offset, оскільки вони можуть бути прив'язані до результату деякого динамічного розрахунку. У нашому прикладі offset дорівнює 0, а limit — 1.

Далі вузол плану Limit багаторазово викликає субплан — в нашому випадку це Sort — поки він не досягне значення offset:


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

Нарешті, коли Постгрес продовжить викликати вузол Limit, він стане передавати значення даних з субплана по одному:


Оскільки в нашому прикладі limit дорівнює 1, Limit відразу поверне NULL, показуючи вищестоящому планом, що доступних даних більше немає.

Постгрес виконує вузол Limit за допомогою коду з файлу під назвою nodeLimit.з



image
ExecLimitview on postgresql.org






Ви можете побачити, що вихідний код Постгреса використовує такі слова, як tuple (набір значень, по одному з кожного стовпця) і subplan. У цьому прикладі субплан — це вузол Sort, який розташований в плані під Limit.

Виконання вузла плану Sort
Звідки беруться значення даних, які відфільтровує Limit? З сайту Sort, розташованого під Limit в дереві плану. Sort завантажує значення даних з свого субплана і повертає їх викликає сайту Limit. Ось що Sort робить, коли вузол Limit викликає його в перший раз, щоб отримати перше значення даних:


Як бачите, Sort функціонує зовсім не так, як Limit. Він відразу завантажує всі доступні дані з субплана в буфер перш, ніж що-небудь повертати. Потім він сортує буфер за допомогою алгоритму Quicksort і, нарешті, повертає перше отсортированное значення.

Для другого і наступних викликів Sort просто повертає додаткові значення з відсортованого буфера, і йому більше не потрібно знову викликати субплан:



Вузол плану Sort виконується функцією C під назвою ExecSort:



image
ExecSortview on postgresql.org






Виконання вузла плану SeqScan
Звідки ExecSort бере значення? Зі свого сублана — сайту SeqScan, розташованого в самому низу дерева плану. SeqScan розшифровується як послідовне сканування (sequential scan), що передбачає перегляд всіх значень в таблиці і повернення значень, які відповідають заданому фільтру. Щоб зрозуміти, як сканування працює з нашим фільтром, давайте представимо таблицю користувачів, заповнену вигаданими іменами, і спробуємо знайти в ній Капітана Немо.



Постгрес починає з першого запису в таблиці (яка у вихідному коді Постгреса називається relation) і запускає булеві вирази з дерева плану. Простіше кажучи, Постгрес задає питання: «Це Капітан Немо?» Оскільки Laurianne Goodwin — це не Капітан Немо, Постгрес переходить до наступного запису.



Ні, Candace — це теж не Капітан Немо. Постгрес продовжує:



… і в кінці кінців знаходить Капітана Немо!



Постгрес виконує вузол SeqScan, використовуючи функцію C під назвою ExecSeqScan.



image
ExecSeqScanview on postgresql.org






Що ми робимо не так?
Ось ми й дійшли до кінця! Ми рушили за простим запитом select по всьому шляху через нутрощі Постгреса і побачили, як він піддався синтаксичному аналізу, був переписаний, спланований і, нарешті, виконаний. Після виконання багатьох тисяч рядків коду на C Постгрес знайшов дані, які ми шукали! Тепер все, що йому залишилося зробити — це повернути рядок Капітана Немо назад в наше додаток Rails, і ActiveRecord зможе створити об'єкт Ruby. Нарешті-то ми можемо повернутися на поверхню нашої програми.

Але Постгрес не зупиняється! Замість того, щоб просто повернути дані, він продовжує сканувати таблицю користувачів, хоча ми вже знайшли Капітана Немо:



Що ж відбувається? Чому Постгрес витрачає свій час, продовжуючи шукати, незважаючи на те, що вже знайшов необхідні дані?

Відповідь лежить в дереві плану, у вузлі Sort. Згадайте, що для сортування всіх користувачів ExecSort спочатку завантажує всі значення в буфер, багаторазово викликаючи субплан, поки значення не закінчаться. Це означає, що ExecSeqScan буде продовжувати сканувати до кінця таблиці, поки не збере всіх відповідних користувачів. Якщо б наша таблиця містила тисячі або навіть мільйони записів (уявіть, що ми працюємо в Facebook або Twitter), ExecSeqScan довелося б повторювати цикл для всіх записів користувачів і виконувати порівняння для кожної з них. Очевидно, що це повільно і неефективно, і ми будемо все змінюється по мірі того, як в таблицю будуть додаватися нові записи користувачів.

Якщо у нас є всього один запис про Капітана Немо, ExecSort «відсортує» тільки цю відповідну запис, а ExecLimit пропустить її через свій фільтр offset/limit… але лише після того, як ExecSeqScan пройдеться по всіх імен.

наступного разу
Як же вирішити цю проблему? Що робити, якщо для виконання наших SQL запитів з таблиці користувачів потрібно все більше і більше часу? Відповідь проста: ми створюємо індекс.

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

0 коментарів

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