Балансування запису та читання в базі даних

У попередній статті я описав концепцію та реалізацію бази даних, побудовану на основі функцій, а не таблиць та полів як у реляційних базах даних. У ній було наведено безліч прикладів, які б переваги такого підходу перед класичним. Багато хто вважав їх недостатньо переконливими.

У цій статті я покажу, яким чином така концепція дозволяє швидко та зручно балансувати запис та читання до бази даних без будь-якої зміни логіки роботи. Схожий функціонал спробували реалізувати у сучасних комерційних СУБД (зокрема, Oracle та Microsoft SQL Server). Наприкінці статті я покажу, що вийшло їм, м'яко кажучи, не дуже.

Опис

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

У функціональній базі даних це буде виглядати так:

CLASS Department ‘Отдел’;
name ‘Наименование’ = DATA STRING[100] (Department);

CLASS Employee 'Співробітник';
department 'Відділ' = DATA Department (Employee);
salary 'Зарплата' = DATA NUMERIC[10,2] (Employee);

countEmployees 'У співробітників' (Department d) = 
    GROUP SUM 1 IF department(Employee e) = d;
salarySum 'Сумарна зарплата' (Department d) = 
    GROUP SUM salary(Employee e) IF department(e) = d;

SELECT name(Department d), countEmployees(d), salarySum(d);

Складність виконання цього запиту до будь-якої СУБД буде еквівалентна O(кількість співробітників)Так як для цього обчислення потрібно просканувати всю таблицю співробітників, а потім згрупувати їх по відділу. Також буде деяка невелика (вважаємо, що співробітників набагато більше ніж відділів) добавка в залежності від обраного плану O(log кол-ва співробітників) або O(кількість відділів) на угруповання та інше.

Зрозуміло, що витрати на виконання можуть бути різними в різних СУБД, але складність не зміниться ніяк.

У запропонованій реалізації функціональна СУБД сформує один підзапит, який обчислить потрібні значення з відділу, а потім зробить JOIN з таблицею відділів для отримання імені. Однак, для кожної функції при оголошенні є можливість задати спеціальний маркер MATERIALIZED. Система автоматично створить відповідне поле під кожну таку функцію. При зміні значення функції в тій же транзакції змінюватиметься значення поля. При зверненні до цієї функції йтиме звернення вже до підрахованого поля.

Зокрема, якщо поставити MATERIALIZED для функцій countEmployees и salarySum, то таблиці зі списком відділів додадуться два поля, у яких зберігається кількість співробітників та його сумарна зарплата. При будь-якій зміні працівників, їх зарплат або приналежності до відділів система автоматично змінюватиме значення цих полів. Наведений вище запит буде звертатися безпосередньо до цих полів і буде виконаний за O(кількість відділів).

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

Приклад:

employeesCount ‘Количество сотрудников с зарплатой > N’ (Department d, NUMERIC[10,2] N) = 
    GROUP SUM salary(Employee e) IF department(e) = d AND salary(e) > N;


Ця функція визначена для нескінченної кількості значень N (наприклад, підходить будь-яке негативне значення). Тому на неї не можна поставити MATERIALIZED. Таким чином це логічне, а не технічне обмеження (тобто не тому, що ми не змогли це реалізувати). В іншому – жодних обмежень. Можна використовувати групування, сортування, AND та OR, PARTITION, рекурсії і т.д.

Наприклад, у задачі 2.2 попередньої статті можна поставити MATERIALIZED на обидві функції:

bought 'Купил' (Customer c, Product p, INTEGER y) = 
    GROUP SUM sum(Detail d) IF 
        customer(order(d)) = c AND 
        product(d) = p AND 
        extractYear(date(order(d))) = y MATERIALIZED;
rating 'Рейтинг' (Customer c, Product p, INTEGER y) = 
    PARTITION SUM 1 ORDER DESC bought(c, p, y), p BY c, y MATERIALIZED;
SELECT contactName(Customer c), name(Product p) WHERE rating(c, p, 1997) < 3;


Система сама створить одну таблицю із ключами типів Клієнт, Продукт и INTEGER, додасть до неї два поля і оновлюватиме значення полів за будь-яких змін. При подальших зверненнях до цих функцій не відбуватиметься їх розрахунок, а зчитуватимуться значення з відповідних полів.

За допомогою цього механізму можна, наприклад, позбавлятися від рекурсій (CTE) у запитах. Зокрема, розглянемо групи, які утворюють дерево за допомогою відношення child/parent (кожна група має посилання на свого батька):

parent = DATA Group (Group);


У функціональній базі даних логіку рекурсій можна задати так:

level (Group child, Group parent) = RECURSION 1l IF child IS Group AND parent == child
                                                             STEP 2l IF parent == parent($parent);
isParent (Group child, Group parent) = TRUE IF level(child, parent) MATERIALIZED;


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

childrenCount (Group g) = GROUP SUM 1 IF isParent(Group child, g);


Жодного CTE у SQL запиті при цьому не буде. Натомість буде простий GROUP BY.

За допомогою цього механізму можна також легко робити денормалізацію бази даних за необхідності:

CLASS Order 'Заказ';
date 'Дата' = DATA DATE (Order);

CLASS OrderDetail 'Рядок замовлення';
order 'Замовлення' = DATA Order (OrderDetail);
date 'Дата' (OrderDetail d) = date(order(d)) MATERIALIZED INDEXED;

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

Переваги

Навіщо весь цей механізм потрібен? У класичних СУБД, без переписування запитів, розробник чи DBA можуть лише змінювати індекси, визначати статистику та підказувати планувальнику запитів, як їх виконувати (причому HINT'и є лише у комерційних СУБД). Як би вони не намагалися, вони не зможуть перший запит у статті виконати за Про (кількість відділів) без зміни запитів та дописування тригерів. У запропонованій схемі, на етапі розробки можна не замислюватися про структуру зберігання даних і про те, які агрегації використовувати. Це все можна спокійно змінювати на льоту безпосередньо в експлуатації.

Насправді це виглядає так. Деякі люди розробляють безпосередньо логіку на основі поставленого завдання. Вони не розуміються ні на алгоритмах та їх складності, ні на планах виконання, ні на типах join'ів, ні на будь-якій іншій технічній складовій. Ці люди — скоріше бізнес-аналітики, ніж розробники. Потім все це йде в тестування або експлуатацію. Включається логування тривалих запитів. Коли виявляється довгий запит, то вже іншими людьми (технічнішими — по суті DBA) приймається рішення про включення MATERIALIZED на деяку проміжну функцію. Тим самим трохи сповільнюється запис (оскільки потрібно оновлення додаткового поля в транзакції). Проте, значно прискорюється як цей запит, а й інші, які використовують цю функцію. При цьому ухвалення рішення про те, яку саме функцію матеріалізувати, приймається відносно нескладно. Два основних параметри: кількість можливих вхідних значень (саме стільки записів буде у відповідній таблиці), і наскільки часто вона використовується в інших функціях.

аналоги

У сучасних комерційних СУБД є схожі механізми: MATERIALIZED VIEW із FAST REFRESH (Oracle) та INDEXED VIEW (Microsoft SQL Server). У PostgreSQL MATERIALIZED VIEW не вміє оновлюватися в транзакції, а лише за запитом (та ще з дуже жорсткими обмеженнями), тому його не розглядаємо. Але вони мають кілька проблем, що значно обмежує їх використання.

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

По-друге, вони мають величезну кількість обмежень:

оракул

5.3.8.4 General Restrictions on Fast Refresh

Definition quest of materialized view is restricted as follows:

• Materialized view must not contain references to non-repeating expressions like SYSDATE та ROWNUM.
• Materialized view must not contain references to RAW or LONG RAW типи даних.
• It cannot contain a SELECT List subquery.
• Він не має жодних аналітичних функцій (для прикладу, RANK) У SELECT пункт.
• It cannot reference a table on which an XMLIndex index is defined.
• It cannot contain a MODEL пункт.
• It cannot contain a HAVING clause with a subquery.
• Це може бути необмежену помилку, що має ANY, ALLабо NOT EXISTS.
• It cannot contain a [START WITH …] CONNECT BY пункт.
• Це може бути необхідний багаторазових деталей таблиць в різних вузлах.
• ON COMMIT materialized views cannot have remote detail tables.
• Необхідні матеріальні погляди повинні мати join or aggregate.
• Materialized join views і materialized aggregate views with a GROUP BY clause cannot select from an index-organized table.

5.3.8.5 Restrictions on Fast Refresh on Materialized Views with Joins Only

Defining queries for materialized views with joins only and no aggregates have the following restrictions on fast refresh:

• All restrictions from «General Restrictions on Fast Refresh".
• They cannot have GROUP BY clauses or aggregates.
• Rowids of all the tables in the FROM list must appear in the SELECT list of the query.
• Materialized view logs must exist with rowids for all the base tables in the FROM list of the query.
• Ви можете creat fast refreshable materialized view from multiple tables with simple joins that include an object type column in the SELECT Заява

Also, the refresh method you choose will not be optimally efficient if:

• Definition query uses outer join that behaves як inner join. Якщо ви знайдете запитання про те, щоб знайти його, з'ясувати, що потрібно визначити, що потрібно, щоб виконати ін'єр join.
• Команда SELECT List of materialized view contains expressions on columns of multiple tables.

5.3.8.6 Restrictions on Fast Refresh on Materialized Views with Aggregates

Defining queries for materialized views with aggregates or joins have the following restrictions on fast refresh:

• All restrictions from «General Restrictions on Fast Refresh".

Fast refresh is supported for both ON COMMIT та ON DEMAND матеріалізованих views, however the following restrictions apply:

• Всі таблиці в матеріалах view must мають materialized view logs, і materialized view logs must:
  • Розташовані всі columnи з table referenced in materialized view.
  • Specify with ROWID та INCLUDING NEW VALUES.
  • Вкажіть SEQUENCE Clase if the table is expected to have mix of inserts/direct-loads, deletes, and updates.

• Only SUM, COUNT, AVG, STDDEV, VARIANCE, MIN та MAX є supported для fast refresh.
• COUNT(*) необхідно вказати.
• Aggregate функцій повинен occur only as outermost part of the expression. That is, aggregates such as AVG(AVG(x)) or AVG(x)+ AVG(x) не допускаються.
• For each aggregate such as AVG(expr), відповідний COUNT(expr) must be present. Oracle recommends that SUM(expr) бути уточненим.
• If VARIANCE(expr) or STDDEV(expr) вказано, COUNT(expr) та SUM(expr) must be specified. Oracle recommends that SUM(expr *expr) бути уточненим.
• Команда SELECT column in the defining query cannot be complex expression with columns from multiple base tables. Як можлива роботаназивається до цього, використовує необхідний матеріальний вигляд.
• Команда SELECT list must contain all GROUP BY стовпчики.
• Materialized view не базується на одному або більше remote tables.
• Якщо ви використовуєте a CHAR Data type in the filter columns materialized view log, character sets of master site and materialized view must be the same.
• Якщо матеріалізований перегляд має один з наступних, то швидкий рефриз є підтриманий тільки на конвенційних DML inserts і direct loads.
  • Materialized views with MIN or MAX агрегати
  • Materialized views which have SUM(expr) але не COUNT(expr)
  • Materialized views without COUNT(*)

  Такий materialized view називається insert-тільки materialized view.

• A materialized view with MAX or MIN is fast refreshable after delete or mixed DML statements if it does not have a WHERE пункт.
  Max/min fast refresh after delete or mixed DML не може мати самий behavior як insert-only case. Це delets and recomputes max/min values ​​for affected groups. Ви потребуєте, щоб його продуктивність impact.
• Materialized views with named views or subqueries in the FROM clause can be fast refreshed подробиці перегляду can be completely merged. Для інформації на яких переглядах will merge, see Довідник з мови SQL Oracle Database.
• Якщо ви не маєте жодних joins, ви можете мати arbitrary selections and joins in the WHERE пункт.
• Матеріальні агрегативні перегляди з двома joins є швидким freshable після конвенційних DML і прямих loads, передбачені тільки в одному table tables, щоб бути зміненим. Also, unique constraints must exist on join columns of inner join table. If there є outer joins, all the joins must be connected by ANDs and must use the equality (=) оператор.
• Для матеріалів views with CUBE, ROLLUP, grouping sets, або concatenation them, following restrictions apply:
  • Команда SELECT list should contain grouping distinguisherher that can either be a GROUPING_ID function on all GROUP BY вирази або GROUPING functions one for each GROUP BY вираз. Для прикладу, якщо GROUP BY clause of the materialized view is «GROUP BY CUBE(a, b)«, then the SELECT list should contain either «GROUPING_ID(a, b)» або «GROUPING(a) AND GROUPING(b)» для матеріалізованого перегляду для того, щоб бути швидко рефризованим.
  • GROUP BY should not result in any duplicate groupings. For example, «GROUP BY a, ROLLUP(a, b)» is not fast refreshable because it results in duplicate groupings «(a), (a, b), AND (a)".

5.3.8.7 Відповіді на швидкі обмеження на матеріалізованих переглядах з UNION ALL

Materialized views with the UNION ALL set operator support the REFRESH FAST option if the following conditions are satisfied:

• The defining query must have the UNION ALL оператор на верхньому рівні.

  Команда UNION ALL функціонер не може бути зроблений всередині суб'єкта, з одним виключенням: UNION ALL can be in a subquery in the FROM clause налаштований the defining query is of the form SELECT * FROM (view or subquery with UNION ALL) as in the following example:

  CREATE VIEW view_with_unionall AS (SELECT c.rowid crid, c.cust_id, 2 umarker FROM customers c WHERE c.cust_last_name = 'Smith' UNION ALL SELECT c.rowid crid, c.cust_id, 3 umarker FROMcus 'Jones'); CREATE MATERIALIZED VIEW unionall_inside_view_mv REFRESH FAST ON DEMAND AS SELECT * FROM view_with_unionall;
  

  Note that the view view_with_unionall satisfies the requirements for fast refresh.

• Each query block in the UNION ALL Query must satisfy requirements of fast refreshable materialized view with aggregates or fast refreshable materialized view with joins.

  Придатний матеріалізований view logs повинен бути створений на tables as required for corresponding type of fast refreshable materialized view.
  Зверніть увагу на те, що Oracle Database також дозволить особливу інформацію про один table матеріалізований перегляд з готівкою тільки передбачений ROWID column has been included in the SELECT List і в матеріалізованих view log. Це зображено в визначеному режимі перегляду view_with_unionall.

• Команда SELECT List of each query must include a UNION ALL marker, and the UNION ALL column must have a distinct constant numeric or string value in each UNION ALL branch. Further, marker column must appear in the same ordinal position in the SELECT List of each query block. See «UNION ALL Marker and Query Rewrite» for more information regarding UNION ALL маркери.
• Деякі особливості так само, як інші joins, insert-only aggregate materialized view queries and remote tables are no supported for materialized views with UNION ALL. Note, however, що матеріалізованих views used in replication, which do not contain joins or aggregates, can be fast refreshed when UNION ALL або remote tables are used.
• Порівнянність ініціалізації параметр повинен бути набір до 9.2.0 або висока до створення fast refreshable materialized view with UNION ALL.

Не хочу образити шанувальників Oracle, але, судячи з їхнього списку обмежень, складається враження, що цей механізм писали не в загальному випадку, використовуючи якусь модель, а тисячі індусів, де кожному дали писати свою гілку, і кожен з них що зміг, то і зробив. Використання цього механізму для реальної логіки - це як ходіння мінним полем. Будь-якої миті можна отримати міну, потрапивши на одне з не очевидних обмежень. Як це працює — теж окреме питання, але воно знаходиться поза рамками цієї статті.

Microsoft SQL Server

Додаткові вимоги

В додатку до параметрів SET і визначальних функцій потреб, following requirements must be met:

• The user that executes CREATE INDEX повинні бути власником перегляду.
• When you create the index, the IGNORE_DUP_KEY option must be set to OFF (the default setting).
• Tables must be referenced by two-part names, схема.ім'я таблиці в view definition.
• User-defined functions referenced in the view must be created by using the WITH SCHEMABINDING варіант.
• Будь-які user-defined functions referenced in view must be referenced by two-part names, ..
• The data access property of a user-defined function must be NO SQL, and external access property must be NO.
• Загальна лінгвістична функція (CLR) функції можуть з'явитися в розділі select list, але не можуть бути визначені в clustered index key. CLR функцій може не з'ясувати в WHERE clause of view або ON clause of JOIN operation in the view.
• CLR функцій і методів CLR user-defined typs, які використовувалися в view definition, повинні мати properties set as shown in the following table.

  властивість
  Примітка:

  DETERMINISTIC = TRUE
  Must be declared explicitly as attribute of the Microsoft .NET Framework метод.

  PRECISE = TRUE
  Must be declared explicitly as attribute of .NET Framework метод.

  DATA ACCESS = NO SQL
  Визначено, щоб встановити DataAccess atribut to DataAccessKind.None і SystemDataAccess atribut to SystemDataAccessKind.None.

  EXTERNAL ACCESS = NO
  Це особливість defaults до NO for CLR routines.

• The view must be created by using the WITH SCHEMABINDING варіант.
• View must reference only base tables що є в той же самий 데이터베이스 як view. View cannot reference інших views.
• SELECT statement in the view definition не має на увазі following Transact-SQL elements:

  COUNT
  ROWSET функцій (OPENDATASOURCE, OPENQUERY, OPENROWSETІ OPENXML)
  OUTER joins (LEFT, RIGHTабо FULL)

  Derived table (defined by specifying a SELECT заяву в FROM пункт)
  Self-joins
  Specifying columns by using SELECT * or SELECT <table_name>.*

  DISTINCT
STDEV, STDEVP, VAR, VARPабо AVG
  Common table expression (CTE)

  плавати1, текст, ntext, зображення, XMLабо потік файлів стовпців
  Підзапит
  OVER clause, які включають ranking or aggregate window functions

  Full-text predicates (CONTAINS, FREETEXT)
  SUM function that references a nullable expression
  ORDER BY

  CLR user-defined aggregate функція
  TOP
CUBE, ROLLUPабо GROUPING SETS Оператори

  MIN, MAX
UNION, EXCEPTабо INTERSECT Оператори
  TABLESAMPLE

  Змінні таблиці
  OUTER APPLY or CROSS APPLY
PIVOT, UNPIVOT

  Sparse column sets
  Inline (TVF) або multi-statement table-valued functions (MSTVF)
  OFFSET

  CHECKSUM_AGG

  1 indexed view can contain плавати columns; However, such columns неможна включатися в clustered index key.

• If GROUP BY is present, the VIEW definition must contain COUNT_BIG(*) and must not contain HAVING. Ці GROUP BY Відповіді є придатними лише до indexed view definition. Яким чином можна використовувати indexed view in its execution plan even if it does not satisfy these GROUP BY обмеження
• If the view definition contains a GROUP BY clause, key of unique clustered index can reference only the columns specified in the GROUP BY пункт.

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

View must reference only base tables що є в той же самий 데이터베이스 як view. View cannot reference інших views.

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

SELECT statement in the view definition не має на увазі following Transact-SQL elements:

COUNT
ROWSET функцій (OPENDATASOURCE, OPENQUERY, OPENROWSETІ OPENXML)
OUTER joins (LEFT, RIGHTабо FULL)

Derived table (defined by specifying a SELECT заяву в FROM пункт)
Self-joins
Specifying columns by using SELECT * or SELECT <table_name>.*

DISTINCT
STDEV, STDEVP, VAR, VARPабо AVG
Common table expression (CTE)

плавати1, текст, ntext, зображення, XMLабо потік файлів стовпців
Підзапит
OVER clause, які включають ranking or aggregate window functions

Full-text predicates (CONTAINS, FREETEXT)
SUM function that references a nullable expression
ORDER BY

CLR user-defined aggregate функція
TOP
CUBE, ROLLUPабо GROUPING SETS Оператори

MIN, MAX
UNION, EXCEPTабо INTERSECT Оператори
TABLESAMPLE

Змінні таблиці
OUTER APPLY or CROSS APPLY
PIVOT, UNPIVOT

Sparse column sets
Inline (TVF) або multi-statement table-valued functions (MSTVF)
OFFSET

CHECKSUM_AGG

Заборонені OUTER JOINS, UNION, ORDER BY та інші. Можливо, простіше було вказати, що можна використовувати, ніж те, що не можна. Список ймовірно був би набагато меншим.

Підсумовуючи: величезний набір обмежень у кожному (зауважу комерційної) СУБД vs ніяких (крім одного логічного, а чи не технічного) в LGPL технології. Проте слід зазначити, що реалізувати цей механізм у реляційній логіці дещо складніше, ніж описаної функціональної.

Реалізація

Як це працює? Як «віртуальна машина» використовується PostgreSQL. Усередині є складний алгоритм, який займається розбудовою запитів. Ось вихідний код. І там не просто великий набір евристик із купою if'ів. Так що якщо є кілька місяців на вивчення, то можете спробувати розібратися в архітектурі.

Чи працює це ефективно? Досить ефективно. На жаль, довести це важко. Можу лише сказати, що якщо розглянути тисячі запитів, які є у великих додатках, то в середньому вони ефективніші, ніж гарний розробник. Відмінний SQL-програміст може написати будь-який запит ефективніше, але на тисячі запитів він просто не матиме ні мотивації, ні часу це робити. Єдине, що я можу зараз навести як доказ ефективності — те, що на базі платформи, побудованої на цій СУБД, працюють кілька проектів. ERP-системи, в яких є тисячі різних MATERIALIZED функцій, з тисячі користувачів і террабайтних баз з сотнями мільйонів записів, що працюють на звичайному дво-процесорному сервері. Втім, будь-який бажаючий може перевірити/спростувати ефективність, завантаживши платформу та PostgreSQL, увімкнувши логування SQL-запитів і спробувавши змінювати там логіку та дані.

У наступних статтях я також розповім про те, як можна вішати обмеження на функції, роботу з сесіями змін та багато іншого.

Джерело: habr.com