ACID Transaction performance with Pyrrho v7

Pyrrho uses optimistic algorithms and yet ensures true serialization for ACID transactions, even in conditions of high concurrency. According to many database textbooks, this should be unlikely or even impossible. Nevertheless, Pyrrho v7 achieves this goal, with the help of some novel programming techniques and approaches, with ACID performance much better than standard commercial databases.

In this blog post I want to provide a brief overview of the evidence for this achievement, and the techniques that enable it.

Pyrrho is of course a relational SQL database. First, we assume here that the goal of concurrency algorithms is to serialize concurrent ACID transactions. Pyrrho demonstrates actual serialization, not just serializability, since the database file is constructed as a serial file, where each committed transaction is appended separately to the file, enabling easy verification of the serialization at any later time. (A consequence of this approach is that the database contains a full history of every commit, and many professionals dislike their mistakes to be visible for all time.) The many ways of accessing the log file for verification purposes are described fully in the Pyrrho manual. The current state of the database is maintained in memory, and normal SQL access methods for the current data are enhanced by many system tables.

Moving on from the desirability or otherwise of a full serialized transaction log, what is meant here by conditions of high concurrency? There is a standard benchmark for online transaction processing maintained for many years by the Transaction Processing Council, and full details of this benchmark are available from https://tpc.org . The particular benchmark I refer to here is TPC-C, whose specification is available on this link. It was developed over twenty years ago, and models a telephone based ordering system where warehouses take orders from customers, organise delivery, process payments etc. Each warehouse has a clerk to operate the system, and there is a standard set of tasks that the clerks carry out.

There is one SQL database for the whole enterprise. Clerks are not superhuman, and it takes 23 seconds at least for a clerks to take the details of an order over the telephone (orders are for quantities of between 5 and 15 different products), somewhat less time for payments etc. It has always been an interesting test for DBMS comparisons because the benchmark design includes some important aspects that cause some difficulty for a DBMS. The standard mix of tasks results in 4% of transaction concurrency between different warehouses, and the performance target for a DBMS is the completion rate of new orders for the whole system. The 23 second requirement above means that for one warehouse this number is 16 new orders in 10 minutes, but standard DBMS report thousands of new orders per second when the number of warehouses becomes large.

I have modified this test by having multiple clerks per warehouse, in order to create a greater challenge for the DBMS. The testing software is written in C# and is available for numerous DBMS at https:/github.com/MalcolmCrowe/ShareableDataStructures . It is fair to say that this modification really shows up the weaknesses of all DBMS!  All DBMS tested with this modified benchmark show an eventual collapse in performance if there are 10 clerks or more for a single warehouse, as the DBMS is forced to abort transactions because of concurrency conflicts. The testing program records all commit requests made to the database (in the order they are sent to the DBMS).

But Pyrrho v7 can outperform them all, with performance on a single PC increasing up to 50 clerks for one warehouse. Try it yourself: the code is available at the above location. Full explanations and further details are forthcoming in DBKDA 2020, with previous bulletins in previous years of this conference. The screenshot below shows 50 clerks (see the full video), and 338 new orders in 10 minutes despite most commits failing. As mentioned above, the serialization of transactions is verified by the transaction log. The figures are explained in conference papers. (Another optimistic DBMS, StrongDBMS, is also documented, which last year performed well for 100 clerks, but it lacks many features of standard SQL.)

Lateral Derived Tables and Pyrrho v7

This post discusses a new feature in v7 of Pyrrho, namely a simple implementation of lateral derived tables, that does not require the LATERAL keyword. Lateral derived tables are specified in section 7.6 "Table Reference" of the SQL standard, but are well introduced in the MySQL 8.0 manual at https://dev.mysql.com/doc/refman/8.0/en/lateral-derived-tables.html .

That page gives an example problem where the concept is useful: "Given a table of people in a sales force (where each row describes a member of the sales force), and a table of all sales (where each row describes a sale: salesperson, customer, amount, date), determine the size and customer of the largest sale for each salesperson. "

Now a naive solution might look like this:

create table SalesPerson(pid int primary key)

create table Sales(sid int primary key, spid int, cust int, amount int)

select * from SalesPerson,  (select cust, amount from Sales where spid = pid  order by amount desc fetch first 1 rows only)

According to the MySQL manual page, this is not permitted because "A derived table cannot normally refer to (depend on) columns of preceding tables in the same FROM clause. " The page goes on to discuss a number of solutions which either are very complicated or require the LATERAL keyword.

Pyrrho v7 will automatically detect the need for a lateral derived table (or "lateral join") and will form the required join without using the LATERAL keyword. For example, the above naive solution is accepted and correctly computed by the current alpha build of Pyrrho at  https://github.com/MalcolmCrowe/ShareableDataStructures . The feature is not discussed in the Pyrrho manual, because no special syntax is required.

I'd welcome comments on this feature, and a reference in the SQL standard for the rule that MySQL gives. Write to me at malcolm.crowe@uws.ac.uk .

Further progress with v7 alpha

(for latest post see: 2 January 2021)
on https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha

An important goal in v7 of Pyrrho is to compile SQL code once only, on definition by the user or on load on a database cold-start. Another is to use shareable immutable data structures in the server wherever possible, in the manner described in the above GitHub repository. By the end of 2019, Database, Query and Transaction had these properties. The current version extends this philosophy to RowSet and Cursor objects, and the current version passes a set of tests including stored procedures, triggers, constraints, cascade operations, and structured types.

The documentation in the repository includes full details of how this is done. The Pyrrho manual from previous versions applies almost unchanged to v7, and this version will reach beta stage when all examples in the Pyrrho manual have been implemented for v7. The next stage in this process will be to implement role-based security.

I look forward to demonstrating the performance of the current version at DBKDA 2020. Comments to malcolm.crowe@uws.ac.uk, including PyrrhoDB in the subject line.

Progress with Pyrrho v7 alpha, contd

Today's version (28 March 2020) on https://GitHub.com/MalcolmCrowe/ShareableDataStructures/tree/master/PyrrhoV7alpha
shows check constraints, cascades and triggers working.
V7 documentation is provided with the source code.

There is a new section in the SourceIntro.pdf document about multi-threading, uids, and dynamic memory layout. This has been substantially improved since the December 2019 version to prepare
for the next stage of implementation, which includes Persistent Stored Modules.

The main technical changes are to make more of Pyrrho's data structures immutable and shareable: now including RowSets and Cursors which are now TypedValues.

I hope to have a new full v7 version for the pyrrhodb.com website in the near future. The following is taken from the SourceIntro document in the alpha distribution, under the heading Stored Persistent Modules. 

This heading includes Trigger and sored Procedure definitions, which are parsed once only by the server[1]. Both use the SQL stored persistent modules language as described in the SQL standard, including the handling of conditions (exceptions). When such modules are invoked, they run in the definer’s role as specified by the SQL standard.

Following the design outlined in this document, although the transaction log contains only the source form of trigger and stored procedure code, while the in-memory database contains a compiled version. From version 7 parsing is done once only, and following parsing everything is referred to by uid, not by using string identifiers. As their name implies, uids are unique in the database, but they are private to the implementation, and are subject to change is later versions of the DBMS. The transaction log contains only the source code of these modules, and the format is forward and backward compatible.

There are differences in operation of the different versions, however. Up to version 6.3 of the DBMS (file format 5.1) the source code contained database object positions instead of the definer’s name for database objects. This approach is supported in version 7 of the DBMS for database files created with previous versions. Databases created with version 7 or later (file format >5.1) will contain the source code exactly as given by the definer. This is generally supported by previous versions of the DBMS, but objects will display differently in the Log$ system tables.

The in-memory data structures resulting from parsing include SqlValues, Queries, and Executables. Persistent modules exist in one of three forms, as follows:

• Source code that has been deserialised from the database file on Load() is compiled into data structures that use uids based on lexical positions of source identifiers in the database file. If the server is restarted after committing the definition, the corresponding compiled code will be of this form.
• For source code that has been defined by client interaction, and committed to the database, the compiled version will use uids allocated sequentially from within the range of file positions where the commit has occurred, until the server is restarted.
• For source code that has not yet been committed, the compiled version will use temporary uids above 5×2⁶⁰ allocated according to the lexical position in the client input. This version is recursively converted to the above version on Commit.

Unless you are debugging the server, you should notice no difference between these versions. The uids that differ are not generally visible, and the in-memory compiled code structures are otherwise identical.

CheckConstraints are simpler as they consist merely of an SqlValueExpr that is tested to validate a given value.

---

[1] Up to version 6.3 of the DBMS source code was parsed on each use.

Progress with Pyrrho v7 alpha

The alpha code for PyrrhoDB v7 on GitHub was updated on 20 November 2019, which probably continues to demonstrate the concurrency with the Tpcc benchmark reported previously in this blog.
The alpha version comes with a test application called PyrrhoTest, which will be extended in time to verify all sample code from pyrrhodb.com. The GitHub site contains updated documentation: the Pyrrho manual and an introduction to the source code.
Pyrrho v7 aims to be compatible with databases developed with previous versions, and, apart from using optimistic concurrency throughout, complies closely with the ISO SQL standard.
The current state of the v7 alpha implementation includes default values, generated columns, not-null and integrity constraints, alter and drop, and restrict/cascade behaviour for drop, update and delete in addition to joins and subqueries. Alters are role-dependent, laying the groundwork for a full implementation of role-based object renaming and the SQL security model.
The next phases of implementation will include check constraints and triggers.

Why Pyrrho performs so well in the TPC-C benchmark tests

I have been asked how it can be that commercial DBMS, and also PostgreSQL, show up so badly in the TPC-C benchmark tests that I have published on GitHub.

To begin with, the TPC-C benchmark normally has 1 clerk per warehouse, so that the conflict rate is around 4%. In my tests I deliberatiely increase the concurrency challenge by using multiple clerks for a single warehouse. When the number of clerks goes above 10, most New Order tasks will fail with a write-write conflict on NEXT_O_ID as this is set per district and there are only 10 districts. Worse, the single row in the WAREHOUSE table contains an amount W_YTD which is updated by the payment task, and fields from this row are read by all the NewOrder tasks and others so that a great many more tasks are aborted because of read/write conflicts. In all of the products tested, apart from Pyrrho and StrongDBMS, read/write conflicts are detected at the row level or wider.

Both Pyrrho and StrongDBMS see no conflict between the payment and NewOrder task because Payment is the only task that accesses W_YTD, and one of the available tests in the ReadConstraint for detecting read/write conflicts is a set of fields in a specific single row of a table.

There are actually three levels of read/write conflict detection in these DBMS. The following comment in the source code at ReadConstraint.cs dates from about 2005:

    /// ReadConstraints record all of the objects that have been accessed in the current transaction
    /// so that this transaction will conflict with a transaction that changes any of them.
    /// However, for records in a table, we allow specific non-conflicting updates, as follows:
    /// (a) (CheckUpdate) If unique selection of specific records cannot be guaranteed, then
    /// we should report conflict if any column read is updated by another transaction.
    /// (b) (CheckSpecific) If we are sure the transaction has seen a small number of records of tb,
    /// selected by specific values of the primary or other unique key, then
    /// we can limit the conflict check to updates of the selected records (if any),
    /// or to updates of the key TableColumns.
    /// (c) (BlockUpdate) as (a) but it is known that case (b) cannot apply.

If the isolation level is reduced to repeatable-read or read-committed, most of the competing products achieve performance comparable with Pyrrho and StrongDBMS.

I remain very satisfied with the results of these tests since they show that Pyrrho and StrongDBMS achieve such high scores on concurrency tests despite, or even because of, using immutable data structures and optimistic concurrency.

TPCC benchmark with Pyrrho v7

At present, successive updates to PyrrhoDB v7 alpha are on GitHub . As of today, this location contains the 14 September 2019 version, and a version of TpccPyrrho. The TPC-C benchmark test is for OLTP for a warehouse, where the clerk works through a task sequence including new orders, with realistic time delays. In 10 minutes the clerk handles 16 new orders along with other tasks.

In order to demonstrate exceptional handling of concurrency, this version of the benchmark uses multiple clerks per warehouse. This introduces high levels of concurrency and many transactions should fail. With StrongDBMS I demonstrated performance superior to commercial databases, and now can do the same with the alpha version of PyrrhoDB. The GitHub repository includes versions of the benchmark for several popular DBMS so this claim can be verified by anyone interested.

The results for Pyrrho v7 alpha are as follows:


                Recreate DB: 1:02

                Fill stock: 2:02

                Fill districts: 6:15

                Cold start with initial warehouse: 1:30



F:\PyrrhoDB7\Pyrrho>tpccpyrrho

fid 1 loaded at 15/09/2019 12:04:32

Started at 15/09/2019 12:04:40 with 1 clerks

fid 2 loaded at 15/09/2019 12:04:40

At 15/09/2019 12:14:40 Commits 16, Conflicts 0 0

Last fid=2



F:\PyrrhoDB7\Pyrrho>tpccpyrrho

fid 1 loaded at 15/09/2019 12:17:56

Started at 15/09/2019 12:18:03 with 10 clerks

fid 11 loaded at 15/09/2019 12:18:03

At 15/09/2019 12:28:03 Commits 145, Conflicts 0 95

Last fid=11



F:\PyrrhoDB7\Pyrrho>tpccpyrrho

fid 1 loaded at 15/09/2019 12:32:41

Started at 15/09/2019 12:33:33 with 100 clerks

fid 101 loaded at 15/09/2019 12:35:01

At 15/09/2019 12:43:33 Commits 313, Conflicts 0 2920

Last fid=101



F:\PyrrhoDB7\Pyrrho>



During the benchmark test for 100 clerks my desktop machine reported the CPU utilisation was around 40% and the memory utilisation 50%.


PyrrhoDB v7 should reach beta version by December and include all of the usual database features as in previous versions of the DBMS.