Балансировка записи и чтения в базе данных

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

В этой статье я покажу, каким образом такая концепция позволяет быстро и удобно балансировать запись и чтение в базу данных без какого-либо изменения логики работы. Похожий функционал попытались реализовать в современных коммерческих СУБД (в частности, 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;

Система сама создаст одну таблицу с ключами типов Customer, Product и 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;

При обращении к функции date для строки заказа будет идти чтение из таблицы со строками заказов поля, по которому есть индекс. При изменении даты заказа система будет сама автоматически пересчитывать денормализованую дату в строке.

Преимущества

Для чего весь этот механизм нужен? В классических СУБД, без переписывания запросов, разработчик или DBA могут лишь изменять индексы, определять статистику и подсказывать планировщику запросов, как их выполнять (причем HINT'ы есть только в коммерческих СУБД). Как бы они не старались, они не смогут первый запрос в статье выполнить за О (кол-во отделов) без изменения запросов и дописывания триггеров. В предложенной же схеме, на этапе разработки можно не задумываться о структуре хранения данных и о том, какие агрегации использовать. Это все можно спокойно менять на лету уже непосредственно в эксплуатации.

На практике это выглядит следующим образом. Некоторые люди разрабатывают непосредственно логику на основе поставленной задачи. Они не разбираются ни в алгоритмах и их сложности, ни в планах выполнения, ни в типах join’ов, ни в любой другой технической составляющей. Эти люди — скорее бизнес-аналитики, чем разработчики. Затем, все это идет в тестирование или эксплуатацию. Включается логирование длительных запросов. Когда обнаруживается долгий запрос, то уже другими людьми (более техническими — по сути DBA) принимается решение о включении MATERIALIZED на некоторой промежуточной функции. Тем самым немного замедляется запись (так как требуется обновление дополнительного поля в транзакции). Однако, значительно ускоряется не только этот запрос, но и все другие, которые используют эту функцию. При этом принятие решения о том, какую именно функцию материализовать принимается относительно несложно. Два основных параметра: кол-во возможных входных значений (именно столько записей будет в соответствующей таблице), и насколько часто она используется в других функциях.

Аналоги

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

Во-первых, можно включить материализацию только, если у вас уже был создан обычный VIEW. Иначе придется переписывать остальные запросы на обращение к вновь созданному представлению, чтобы использовать эту материализацию. Или оставить все как есть, но будет как минимум неэффективно, если есть определенные уже преподсчитанные данные, но многие запросы их не всегда используют, а высчитывают заново.

Во-вторых, у них есть огромное количество ограничений:

Oracle

5.3.8.4 General Restrictions on Fast Refresh

The defining query of the materialized view is restricted as follows:

• The materialized view must not contain references to non-repeating expressions like SYSDATE and ROWNUM.
• The materialized view must not contain references to RAW or LONG RAW data types.
• It cannot contain a SELECT list subquery.
• It cannot contain analytic functions (for example, RANK) in the SELECT clause.
• It cannot reference a table on which an XMLIndex index is defined.
• It cannot contain a MODEL clause.
• It cannot contain a HAVING clause with a subquery.
• It cannot contain nested queries that have ANY, ALL, or NOT EXISTS.
• It cannot contain a [START WITH …] CONNECT BY clause.
• It cannot contain multiple detail tables at different sites.
• ON COMMIT materialized views cannot have remote detail tables.
• Nested materialized views must have a join or aggregate.
• Materialized join views and 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.
• You cannot create a fast refreshable materialized view from multiple tables with simple joins that include an object type column in the SELECT statement.

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

• The defining query uses an outer join that behaves like an inner join. If the defining query contains such a join, consider rewriting the defining query to contain an inner join.
• The SELECT list of the materialized view contains expressions on columns from 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 and ON DEMAND materialized views, however the following restrictions apply:

• All tables in the materialized view must have materialized view logs, and the materialized view logs must:
  
  • Contain all columns from the table referenced in the materialized view.
  • Specify with ROWID and INCLUDING NEW VALUES.
  • Specify the SEQUENCE clause if the table is expected to have a mix of inserts/direct-loads, deletes, and updates.
  
  
• Only SUM, COUNT, AVG, STDDEV, VARIANCE, MIN and MAX are supported for fast refresh.
• COUNT(*) must be specified.
• Aggregate functions must occur only as the outermost part of the expression. That is, aggregates such as AVG(AVG(x)) or AVG(x)+ AVG(x) are not allowed.
• For each aggregate such as AVG(expr), the corresponding COUNT(expr) must be present. Oracle recommends that SUM(expr) be specified.
• If VARIANCE(expr) or STDDEV(expr) is specified, COUNT(expr) and SUM(expr) must be specified. Oracle recommends that SUM(expr *expr) be specified.
• The SELECT column in the defining query cannot be a complex expression with columns from multiple base tables. A possible workaround to this is to use a nested materialized view.
• The SELECT list must contain all GROUP BY columns.
• The materialized view is not based on one or more remote tables.
• If you use a CHAR data type in the filter columns of a materialized view log, the character sets of the master site and the materialized view must be the same.
• If the materialized view has one of the following, then fast refresh is supported only on conventional DML inserts and direct loads.
  
  • Materialized views with MIN or MAX aggregates
  • Materialized views which have SUM(expr) but no COUNT(expr)
  • Materialized views without COUNT(*)
  
  Such a materialized view is called an insert-only 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 clause.
  The max/min fast refresh after delete or mixed DML does not have the same behavior as the insert-only case. It deletes and recomputes the max/min values for the affected groups. You need to be aware of its performance impact.
• Materialized views with named views or subqueries in the FROM clause can be fast refreshed provided the views can be completely merged. For information on which views will merge, see Oracle Database SQL Language Reference.
• If there are no outer joins, you may have arbitrary selections and joins in the WHERE clause.
• Materialized aggregate views with outer joins are fast refreshable after conventional DML and direct loads, provided only the outer table has been modified. Also, unique constraints must exist on the join columns of the inner join table. If there are outer joins, all the joins must be connected by ANDs and must use the equality (=) operator.
• For materialized views with CUBE, ROLLUP, grouping sets, or concatenation of them, the following restrictions apply:
  
  • The SELECT list should contain grouping distinguisher that can either be a GROUPING_ID function on all GROUP BY expressions or GROUPING functions one for each GROUP BY expression. For example, if the GROUP BY clause of the materialized view is "GROUP BY CUBE(a, b)", then the SELECT list should contain either "GROUPING_ID(a, b)" or "GROUPING(a) AND GROUPING(b)" for the materialized view to be fast refreshable.
  • 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 Restrictions on Fast Refresh on Materialized Views with 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 operator at the top level.
  
  The UNION ALL operator cannot be embedded inside a subquery, with one exception: The UNION ALL can be in a subquery in the FROM clause provided 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
   FROM customers c WHERE c.cust_last_name = '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 the requirements of a fast refreshable materialized view with aggregates or a fast refreshable materialized view with joins.
  
  The appropriate materialized view logs must be created on the tables as required for the corresponding type of fast refreshable materialized view.
  Note that the Oracle Database also allows the special case of a single table materialized view with joins only provided the ROWID column has been included in the SELECT list and in the materialized view log. This is shown in the defining query of the view view_with_unionall.
• The 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, the 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 markers.
• Some features such as outer joins, insert-only aggregate materialized view queries and remote tables are not supported for materialized views with UNION ALL. Note, however, that materialized views used in replication, which do not contain joins or aggregates, can be fast refreshed when UNION ALL or remote tables are used.
• The compatibility initialization parameter must be set to 9.2.0 or higher to create a fast refreshable materialized view with UNION ALL.

Не хочу обидеть поклонников Oracle, но судя по их списку ограничений, создается впечатление, что этот механизм писали не в общем случае, используя какую-то модель, а тысячи индусов, где каждому дали писать свою ветку, и каждый из них что смог, то и сделал. Использование этого механизма для реальной логики — это как хождение по минному полю. В любой момент можно получить мину, попав на одно из не очевидных ограничений. Как это работает — тоже отдельный вопрос, но он находится вне рамок данной статьи.

Microsoft SQL Server

Additional Requirements

In addition to the SET options and deterministic function requirements, the following requirements must be met:

• The user that executes CREATE INDEX must be the owner of the view.
• 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, schema.tablename in the view definition.
• User-defined functions referenced in the view must be created by using the WITH SCHEMABINDING option.
• Any user-defined functions referenced in the view must be referenced by two-part names, <schema>.<function>.
• The data access property of a user-defined function must be NO SQL, and external access property must be NO.
• Common language runtime (CLR) functions can appear in the select list of the view, but cannot be part of the definition of the clustered index key. CLR functions cannot appear in the WHERE clause of the view or the ON clause of a JOIN operation in the view.
• CLR functions and methods of CLR user-defined types used in the view definition must have the properties set as shown in the following table.
  

  Property	Note
  DETERMINISTIC = TRUE	Must be declared explicitly as an attribute of the Microsoft .NET Framework method.
  PRECISE = TRUE	Must be declared explicitly as an attribute of the .NET Framework method.
  DATA ACCESS = NO SQL	Determined by setting DataAccess attribute to DataAccessKind.None and SystemDataAccess attribute to SystemDataAccessKind.None.
  EXTERNAL ACCESS = NO	This property defaults to NO for CLR routines.

• The view must be created by using the WITH SCHEMABINDING option.
• The view must reference only base tables that are in the same database as the view. The view cannot reference other views.
• The SELECT statement in the view definition must not contain the following Transact-SQL elements:
  

  COUNT	ROWSET functions (OPENDATASOURCE, OPENQUERY, OPENROWSET, AND OPENXML)	OUTER joins (LEFT, RIGHT, or FULL)
  Derived table (defined by specifying a SELECT statement in the FROM clause)	Self-joins	Specifying columns by using SELECT * or SELECT <table_name>.*
  DISTINCT	STDEV, STDEVP, VAR, VARP, or AVG	Common table expression (CTE)
  float1, text, ntext, image, XML, or filestream columns	Subquery	OVER clause, which includes ranking or aggregate window functions
  Full-text predicates (CONTAINS, FREETEXT)	SUM function that references a nullable expression	ORDER BY
  CLR user-defined aggregate function	TOP	CUBE, ROLLUP, or GROUPING SETS operators
  MIN, MAX	UNION, EXCEPT, or INTERSECT operators	TABLESAMPLE
  Table variables	OUTER APPLY or CROSS APPLY	PIVOT, UNPIVOT
  Sparse column sets	Inline (TVF) or multi-statement table-valued functions (MSTVF)	OFFSET
  CHECKSUM_AGG

  
  ¹ The indexed view can contain float columns; however, such columns cannot be included in the clustered index key.
• If GROUP BY is present, the VIEW definition must contain COUNT_BIG(*) and must not contain HAVING. These GROUP BY restrictions are applicable only to the indexed view definition. A query can use an indexed view in its execution plan even if it does not satisfy these GROUP BY restrictions.
• If the view definition contains a GROUP BY clause, the key of the unique clustered index can reference only the columns specified in the GROUP BY clause.

Здесь видно, что индусов не привлекали, так как они решили делать по схеме “сделаем мало, но хорошо”. То есть у них мин на поле побольше, но их расположение прозрачнее. Больше всего огорчает вот это ограничение:

The view must reference only base tables that are in the same database as the view. The view cannot reference other views.

В нашей терминологии это означает, что функция не может обращаться к другой материализованной функции. Это рубит всю идеологию на корню.
Также вот это ограничение (и дальше по тексту) очень сильно уменьшает варианты использования:

The SELECT statement in the view definition must not contain the following Transact-SQL elements:

COUNT	ROWSET functions (OPENDATASOURCE, OPENQUERY, OPENROWSET, AND OPENXML)	OUTER joins (LEFT, RIGHT, or FULL)
Derived table (defined by specifying a SELECT statement in the FROM clause)	Self-joins	Specifying columns by using SELECT * or SELECT <table_name>.*
DISTINCT	STDEV, STDEVP, VAR, VARP, or AVG	Common table expression (CTE)
float1, text, ntext, image, XML, or filestream columns	Subquery	OVER clause, which includes ranking or aggregate window functions
Full-text predicates (CONTAINS, FREETEXT)	SUM function that references a nullable expression	ORDER BY
CLR user-defined aggregate function	TOP	CUBE, ROLLUP, or GROUPING SETS operators
MIN, MAX	UNION, EXCEPT, or INTERSECT operators	TABLESAMPLE
Table variables	OUTER APPLY or CROSS APPLY	PIVOT, UNPIVOT
Sparse column sets	Inline (TVF) or multi-statement table-valued functions (MSTVF)	OFFSET
CHECKSUM_AGG

Запрещены OUTER JOINS, UNION, ORDER BY и прочие. Возможно проще было указать, что можно использовать, чем то, что нельзя. Список вероятно был бы гораздо меньше.

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

Реализация

Как это работает? В качестве «виртуальной машины» используется PostgreSQL. Внутри есть сложный алгоритм, который занимается построением запросов. Вот исходный код. И там не просто большой набор эвристик с кучей if’ов. Так что, если есть пару месяцев на изучение, то можете попробовать разобраться в архитектуре.

Работает ли это эффективно? Достаточно эффективно. К сожалению, доказать это тяжело. Могу лишь сказать, что если рассмотреть тысячи запросов, которые есть в больших приложениях, то в среднем они эффективнее, чем у хорошего разработчика. Отличный SQL-программист может написать любой запрос эффективнее, но на тысяче запросов у него просто не будет ни мотивации, ни времени это делать. Единственное, что я могу сейчас привести как доказательство эффективности — это то, что на базе платформы, построенной на этой СУБД работают несколько проектов ERP-системы, в которых есть тысячи различных MATERIALIZED функций, с тысячей пользователей и террабайтными базами с сотнями миллионов записей, работающих на обычном двух-процессорном сервере. Впрочем, любой желающий может проверить/опровергнуть эффективность, скачав платформу и PostgreSQL, включив логирование SQL-запросов и попробовав изменять там логику и данные.

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