Защо е необходима инструменталната поддръжка на пагинацията на ключовете

Здравейте! Аз съм бекенд разработчик, пиша микросервизи на Java + Spring. Работя в един от екипите за разработка на вътрешни продукти в компания Тинькофф.

В нашия екип често се поставя въпросът за оптимизация на заявките в СУБД. Винаги искаме малко повече бързина, но не винаги можем да се справим с добре проектирани индекси — понякога трябва да търсим обходни решения. По време на едно от тези скитания из мрежата в търсене на разумни оптимизации при работа с БД открих безкрайно полезния блог на Маркус Винанд,, автора на книгата SQL Performance Explained. Това е онзи рядък вид блог, в който можете да четете всичките статии от начало до край.

Искам да преведа за вас една малка статия на Маркус. Можете да я наречете в известен смисъл манифест, който се опитва да привлече внимание към стар, но все още актуален проблем с производителността на операцията offset по стандарта SQL.

На някои места ще добавям обяснения и забележки от автора. Всички такива места ще обозначавам като «прим.» за по-голяма яснота.

Кратко въведение

Мисля, че много хора знаят колко проблемна и бавна оказва се работата с постранични селекти чрез offset. А знаете ли, че тя може да бъде сравнително просто заменена с по-производителна конструкция?

И така, ключовото слово offset указва на базата да пропусне първите n записа в заявката. Въпреки това, базата все още трябва да прочете тези първи n записа от диска, и то в зададения ред (прим.: да приложи сортиране, ако е зададено), и едва след това ще бъде възможно да върне записите, започвайки от n+1 и нататък. Най-интересното е, че проблемът не е в конкретната реализация в СУБД, а в първоначалното определение по стандарта:

…the rows are first sorted according to the and then limited by dropping the number of rows specified in the from the beginning…
-SQL:2016, Part 2, 4.15.3 Derived tables (прим.: сега най-използваният стандарт)

Ключовият пункт тук е, че offset приема единствен параметър — броя записите, които трябва да пропуснете, и всичко. Следвайки такова определение, СУБД може само да извлече всички записи, а след това да отхвърли ненужните. Очевидно е, че такова определение на offset води до ненужна работа. А тук дори не е важно дали е SQL или NoSQL.

Още малко болка

Проблемите с offset не свършват тук, и ето защо. Ако между четенето на две страници данни от диска друга операция вмъкне нова запис, какво ще стане в този случай?

Когато се използва offset за пропускане на записи от предишни страници, в ситуация на добавяне на нова запись между операциите на четене на различни страници, много вероятно е да получите дубликати (пример: това е възможно, когато четем страница по страница с конструкцията order by, тогава нова запис може да попадне в средата на нашето резултатно издание).

Илюстрацията ясно показва такава ситуация. Базата данни чете първите 10 записа, след което се вмъква нова запись, която изместват всички прочетени записи с 1. След това базата взима нова страница с 10 следващи записа и започва не от 11-та, както би трябвало, а от 10-та, дублирайки този запис. Има и други аномалии, свързани с използването на това изражение, но това е най-разпространената.

Както вече установихме, това не е проблем на конкретна СУБД или техните реализации. Проблемът е в определението на пагинацията по стандарт SQL. Казваме на СУБД коя страница трябва да изтегли или колко записи да пропусне. Базата просто не може да оптимизира такъв запит, тъй като за това имаме прекалено малко информация.

Струва си също така да уточним, че това не е проблем на конкретна ключова дума, а по-скоро на семантиката на запитването. Има още няколко идентични по проблематика синтаксиса:

• Ключовата дума offset, както беше споменато по-рано.
• Конструкцията от две ключови думи limit [offset] (въпреки че самият limit не е толкова лош).
• Филтриране по долни граници, изградени на номериране на редове (например, row_number(), rownum и т.н.).

Всички тези изрази просто казват колко реда трябва да пропуснете, без никаква допълнителна информация или контекст.

По-нататък в тази статия ключовата дума offset се използва като обобщение на всички тези варианти.

Живот без OFFSET

А сега си представете какъв би бил нашият свят без всички тези проблеми. Оказва се, че животът без offset не е толкова сложен: можем да избираме само онези редове, които все още не сме виждали (пример: тоест тези, които не са били на предишната страница), с помощта на условие в where.

В този случай основаваме на факта, че селектите се изпълняват върху подредена множества (старият добър order by). Тъй като имаме подредена множество, можем да използваме доста прост филтър, за да извличаме само тези данни, които са след последната запис от предишната страница:

    SELECT ...
    FROM ...
    WHERE ...
    AND id < ?last_seen_id
    ORDER BY id DESC
    FETCH FIRST 10 ROWS ONLY

Ето го и целият принцип на този подход. Разбира се, при сортиране по много колони всичко става по-интересно, но идеята остава същата. Важно е да се отбележи, че тази конструкция е приложима на много NoSQL-решения.

Този подход се нарича seek method или keyset pagination. Той решава проблема с плаващия резултат (прим.: ситуацията с записите между четенията на страниците, описана по-рано) и, разбира се, каквото всички обичаме, работи по-бързо и по-стабилно от класическия offset. Стабилността се състои в това, че времето за обработка на запитването не се увеличава пропорционално на номера на запрашваната таблица (прим.: ако искате да научите повече за работата на различните подходи към пагинацията, можете да прегледате презентацията на автора. Там можете да намерите сравнителни бенчмарки по различни методи).

Един от слайдовете разказва за това, че пагинацията по ключове, разбира се, не е всевиждаща — тя има своите ограничения. Най-същественото е, че тя няма възможност да чете произволни страници (прим.: несеквенционално). Въпреки това, в епохата на безкрайното скролване (прим.: на фронтенда) това не е толкова голям проблем. Указването на номера на страницата за кликване — в крайна сметка е лошо решение при разработката на потребителски интерфейс (прим.: мнението на автора на статията).

А какво с инструментите?

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

Ситуацията е усложнена от това, че описаният метод изисква последователна поддръжка в използваните технологии — от СУБД до изпълнението на AJAX-запитвания в браузера при безкрайно скролване. Вместо да посочвате само номера на страницата, сега ще трябва да посочите набор от ключове за всички страници наведнъж.

Въпреки това, броят на фреймворковете, които поддържат пагинация на ключове, постепенно нараства. Ето какво имаме в момента:

• jOOQ за Java;
• order_query за Ruby;
• chunkator и Django Infinite Scroll Pagination за Django;
• SQL Alchemy sqlakeyset за Python;
• blaze-persistence — criteria API за реализации на JPA;
• DBIx::Class::Wrapper за Perl;
• Massive.js, мапер для Node.js Keyset Documentation.

(Бележка: някои линкове бяха премахнати, тъй като по време на превода някои библиотеки не бяха актуализирани от 2017—2018 г. Ако ви интересува, можете да погледнете оригинала.)

Точно в този момент имам нужда от вашата помощ. Ако разработвате или поддържате фреймуърк, който по някакъв начин използва пагинация, моля, призовавам ви да направите нативна поддръжка за пагинация на ключове. Ако имате въпроси или ви е нужна помощ, ще се радвам да помогна (форум, Twitter, форма за запитвания) (бележка: от моят опит с Маркус мога да кажа, че той наистина е ентусиазиран относно разпространението на тази тема).

Ако използвате готови решения, които смятате, че заслужават поддръжка за пагинация по ключове, — създайте заявка или дори предложете готово решение, ако е възможно. Можете също да включите тази статия в линка.

Заключение

Причината, поради която такъв прост и полезен подход като пагинацията по ключове е слабо разпространен, не е в това, че е сложно технически или изисква големи усилия. Главната причина е, че много хора са свикнали да виждат и работят с offset — такова отношение е продиктувано от самия стандарт.

Като следствие, малко хора обмислят смяната на подхода към пагинация, а заради това и инструменталната поддръжка от страна на фреймворкове и библиотеки не се развива активно. Затова, ако ви е близка идеята и целта на безофсетната пагинация, — помогнете да я разпространим!

Източник: https://use-the-index-luke.com/no-offset
Автор: Markus Winand

Източник: habr.com