ProHoster > Blog > Administration > Balancing Reads and Writes in a Database

Balancing Reads and Writes in a Database

Balancing Reads and Writes in a Database
In the previous article I described the concept and implementation of a database built on functions rather than tables and fields like in relational databases. It presented numerous examples demonstrating the advantages of this approach over the classical model. Many found them insufficiently convincing.

In this article, I will show how such a concept allows for quick and convenient balancing of reads and writes in a database without any change to the underlying logic. A similar functionality has been attempted in modern commercial DBMSs (notably, Oracle and Microsoft SQL Server). By the end of the article, I will show that their results were, to put it mildly, not very effective.

Description

As before, for better understanding, I will start the description with examples. Suppose we need to implement logic that returns a list of departments with the number of employees in each and their total salary.

In a functional database, this would look as follows:

CLASS Department 'Department';
name 'Designation' = DATA STRING[100] (Department);

CLASS Employee 'Employee';
department 'Department' = DATA Department (Employee);
salary 'Salary' = DATA NUMERIC[10,2] (Employee);

countEmployees 'Number of Employees' (Department d) = 
    GROUP SUM 1 IF department(Employee e) = d;
salarySum 'Total Salary' (Department d) = 
    GROUP SUM salary(Employee e) IF department(e) = d;

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

The complexity of executing this query in any DBMS will be equivalent to O(number of employees), as the calculation requires scanning the entire employee table and then grouping them by department. There will also be a slight addition (assuming there are significantly more employees than departments) depending on the chosen plan. O(log number of employees) or O(number of departments) for grouping and so on.

It's clear that the overhead for execution may vary across different DBMSs, but the complexity will remain unchanged.

In the proposed implementation, the functional DBMS will generate a single subquery that computes the required values by department and then performs a JOIN with the departments table to retrieve the name. However, for each function upon declaration, there is an option to specify a special marker MATERIALIZED. The system will automatically create a corresponding field for each such function. When the function value changes, the field value will also change within the same transaction. When accessing this function, it will refer directly to the precomputed field.

Specifically, if MATERIALIZED is set for the functions countEmployees and salarySum, two fields will be added to the department list table, which will store the number of employees and their total salary. Any changes to employees, their salaries, or department affiliations will automatically update these field values. The aforementioned query will then directly reference these fields and will execute in O(number of departments).

What are the restrictions? Only one: such a function must have a finite number of input values for which its value is defined. Otherwise, it would not be possible to construct a table storing all its values, as there cannot be a table with an infinite number of rows.

Example:

employeesCount 'Number of employees with a salary > N' (Department d, NUMERIC[10,2] N) = 
    GROUP SUM salary(Employee e) IF department(e) = d AND salary(e) > N;

This function is defined for an infinite number of values of the number N (for instance, any negative value would apply). Therefore, MATERIALIZED cannot be applied to it. Thus, this is a logical, not a technical restriction (i.e., it is not because we were unable to implement it). In other respects — no restrictions. Groupings, sorting, AND and OR, PARTITION, recursion, etc., can be used.

For example, in task 2.2 of the previous article, MATERIALIZED can be applied to both functions:

bought '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 '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;

The system will automatically create one table with the key types Customer, Product and INTEGER, it will add two fields to it and will update the field values upon any changes. Further calls to these functions won't prompt recalculation but will read values from the corresponding fields.

With this mechanism, one can, for instance, eliminate recursion (CTE) in queries. In particular, consider groups that form a tree through a child/parent relationship (where each group has a link to its parent):

parent = DATA Group (Group);

In a functional database, recursion logic can be defined as follows:

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;

Since the function isParent is marked as MATERIALIZED, a table will be created for it with two keys (groups), where the field isParent will be true only if the first key is a descendant of the second. The number of records in this table will be equal to the number of groups multiplied by the average depth of the tree. If, for example, it is necessary to count the number of descendants of a specific group, you can call this function:

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

There will be no CTE in the SQL query. Instead, there will be a simple GROUP BY.

Using this mechanism, it's also easy to denormalize the database if needed:

CLASS Order 'Order';
date 'Date' = DATA DATE (Order);

CLASS OrderDetail 'Order line';
order 'Order' = DATA Order (OrderDetail);
date 'Date' (OrderDetail d) = date(order(d)) MATERIALIZED INDEXED;

When calling the function date for the order line, it will read from the orders table the field for which there is an index. When the order date changes, the system will automatically recalculate the denormalized date in the line.

Benefits

Why is this entire mechanism necessary? In traditional DBMS, without rewriting queries, developers or DBAs can only modify indexes, determine statistics, and hint the query planner on how to execute them (and HINTs are only in commercial DBMS). No matter how hard they try, they won't be able to execute the first query in this article for O (number of departments) without changing queries and adding triggers. In the proposed scheme, at the development stage, one doesn't have to worry about the data storage structure and which aggregations to use. All of this can be adjusted on the fly directly during operation.

In practice, it looks like this. Some people develop logic directly based on the given task. They do not understand algorithms and their complexity, execution plans, types of joins, or any other technical components. These individuals are more business analysts than developers. Then, all of this goes into testing or production. Long query logging is enabled. When a long query is detected, a decision is made by other individuals (who are more technical—essentially DBAs) to enable MATERIALIZED on some intermediate function. This slightly slows down the write operation (as it requires updating an additional field in the transaction). However, it significantly speeds up not only this query but also all other queries that use this function. The decision on which specific function to materialize is relatively straightforward. Two main parameters: the number of possible input values (that is how many records will be in the corresponding table) and how often it is used in other functions.

Analogues

Modern commercial DBMS have similar mechanisms: MATERIALIZED VIEW with FAST REFRESH (Oracle) and INDEXED VIEW (Microsoft SQL Server). In PostgreSQL, MATERIALIZED VIEW cannot be updated in a transaction, only on demand (with very strict limitations), so we won't consider it. However, they have several issues that significantly limit their use.

First of all, you can only enable materialization if you already have a regular VIEW created. Otherwise, you would need to rewrite other queries to refer to the newly created view to utilize this materialization. Or you can leave everything as is, but it will at least be inefficient if there are certain pre-calculated data that many queries do not always use and recalculate.

Secondly, there are a huge number of restrictions:

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:

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 can be fast refreshable after conventional DML and direct loads, as long as only the outer table has been modified. Additionally, 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 combinations thereof, the following restrictions apply:
    • The SELECT The list should contain a 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 instance, 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 It should not result in any duplicate groupings. For example, «GROUP BY a, ROLLUP(a, b)» is not fast refreshable because it yields duplicate groupings «(a), (a, b), AND (a)«.

5.3.8.7 Restrictions on Fast Refresh for Materialized Views with UNION ALL

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

  • The defining query must have the UNION ALL operator at the top level.

    The UNION ALL The 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 structured as 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 meet the standards 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 necessary for the respective type of fast refreshable materialized view.
    The Oracle Database also permits the special case of a single table materialized view with joins only, provided the ROWID column has been included in the SELECT list and within the materialized view log. This is displayed in the defining query of the view. view_with_unionall.

  • The SELECT The list of each query must contain a UNION ALL marker, and the UNION ALL column must carry a distinct constant numeric or string value in each UNION ALL branch. Moreover, the marker column must appear in the same ordinal position in the SELECT list of each query block. Refer to «UNION ALL Marker and Query Rewrite» for further information regarding UNION ALL markers.
  • Certain features, such as outer joins, insert-only aggregate materialized view queries, and remote tables, are not supported for materialized views with UNION ALL. However, note that materialized views used in replication, which do not include joins or aggregates, can be fast refreshed when UNION ALL or remote tables are utilized.
  • The compatibility initialization parameter must be set to 9.2.0 or higher to establish a fast refreshable materialized view with UNION ALL.

I don't want to offend Oracle fans, but judging by their list of restrictions, it feels like this mechanism was written not as a general case using some model, but rather by thousands of developers, each writing their own thread based on what they could manage. Using this mechanism for real logic is like walking through a minefield. At any moment, you could hit a mine by stumbling upon one of the non-obvious restrictions. How it works is also a separate question, but that's beyond the scope of this article.

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 the 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

    .*

    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

    1 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.

    • It is clear that Indians were not attracted here, as they decided to follow the approach of 'let’s do less but better'. That is, they have more mines on the field, but their arrangement is clearer. The most disappointing thing is this limitation:

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

    In our terminology, this means that a function cannot call another materialized function. This cuts the entire ideology at its root.
    Also, this limitation (and further in the text) greatly reduces the options for use:

    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

    .*

    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, and others are prohibited. It might have been simpler to specify what can be used rather than what cannot. The list would likely be much shorter.

    In summary: a huge set of restrictions in each (I note commercial) DBMS vs no restrictions (except for one logical, not technical) in LGPL technology. However, it should be noted that implementing this mechanism in relational logic is somewhat more complicated than in the described functional logic.

    Implementation

    How does it work? PostgreSQL is used as the 'virtual machine'. Inside, there is a complex algorithm responsible for building queries. Here source code. And it involves not just a large set of heuristics with a bunch of ifs. So if you have a couple of months to study, you can try to figure out the architecture.

    Does this work effectively? Quite effectively. Unfortunately, it is hard to prove it. I can only say that if you consider thousands of queries in large applications, on average they are more efficient than those by a good developer. An excellent SQL programmer can write any query more efficiently, but over a thousand queries, they simply won't have the motivation or time to do it. The only evidence I can provide for effectiveness right now is that several projects are based on a platform built on this DBMS ERP systems, which have thousands of various MATERIALIZED functions, with thousands of users and terabyte databases containing hundreds of millions of records, all running on a standard dual processor server. However, anyone can verify/disprove effectiveness by downloading the platform and PostgreSQL, enabling SQL query logging and trying to modify the logic and data there.

    In the following articles, I will also discuss how to impose restrictions on functions, work with session changes, and much more.

    Source: habr.com

    Buy reliable website hosting with DDoS protection, VPS VDS servers 🔥 Buy reliable website hosting with DDoS protection, VPS VDS servers | ProHoster