Re: [HACKERS] Proposal: generic WAL compression - Mailing list pgsql-hackers

Hackers,

a few years ago generic WAL was proposed by Alexander Korotkov (https://www.postgresql.org/message-id/flat/CAPpHfdsXwZmojm6Dx%2BTJnpYk27kT4o7Ri6X_4OSWcByu1Rm%2BVA%40mail.gmail.com#CAPpHfdsXwZmojm6Dx+TJnpYk27kT4o7Ri6X_4OSWcByu1Rm+VA@mail.gmail.com). and was committed into PostgreSQL 9.6.
One of the generic WAL advantages is the common interface for safe interaction with WAL for modules and extensions. The interface allows module to register the page, then change it, and then generic WAL generates and writes into xlog the algorithm of changing the old version of page into the new one. In the case of crash and recovery this algorithm may be applied.

Bloom and RUM indexes use generic WAL. The issue is that the generic algorithm of turning the old page into the new one is not optimal in the sense of record size in xlog. Now the main idea of the approach is to find all positions in the page where new version is different from the original one and write these changes into xlog. It works well if the page was rewritten completely or if only a few bytes have been changed. Nevertheless, this approach produces too large WAL record in the case of inserting or deleting a few bytes into the page. In this case there are almost no position where the old version and the new one are equal, so the record size is near the page size, but actual amount of changes in the page is small. This is exactly what happens often in RUM indexes.

In order to overcome that issue, I would like to propose the patch, which provides possibility to use another approach of the WAL record construction. If another approach fails to make a short enough record, it rolls back to the original approach. The main idea of another approach is not to perform bytewise comparison of pages, but finding the minimal editing distance between two pages and the corresponding editing algorithm. In the general case, finding editing distance takes O(N^2) time and memory. But there is also an algorithm which requires only O(ND) time and O(D^2) memory, where D is the editing distance between two sequences. Also for given D algorithm may show that the minimal editing distance between two sequences is more than D in the same amount of time and memory.

The special case of this algorithm which does not consider replace operations is described in the paper (http://www.xmailserver.org/diff2.pdf). The version of this algorithm which consumes O(ND) time and O(N) memory is used in diff console command, but for our purposes we don't need to increase the constant for the time in order to decrease memory complexity. For RUM indexes we usually have small enough editing distance (less than 64), so D^2 is not too much to store.

The results of experiments:

+------------------------------+----------------+----------------+----------------+----------------+
|             Name             |  WAL_diff(MB)  |  WAL_orig(MB) |  Time_diff(s)  |  Time_orig(s)  |
+------------------------------+----------------+----------------+----------------+----------------+
| rum: make installcheck       | 38.9           | 82.5 | 4.37           | 4.16           |
+------------------------------+----------------+----------------+----------------+----------------+
| bloom: make installcheck     | 1.0            | 1.0 | 0.66           | 0.53           |
+------------------------------+----------------+----------------+----------------+----------------+
| test00.sql                 | 20.5           | 51.0 | 1.86           | 1.41           |
+------------------------------+----------------+----------------+----------------+----------------+
| test01.sql                   | 207.1      | 219.7   | 8.06 | 6.89           |
+------------------------------+----------------+----------------+----------------+----------------+

We can see that the patch provides a little slowdown, but compresses generic WAL efficiently for RUM index. Also I'm going to do a few more experiments on this patch with another data.

The patch was tested on Lubuntu 14.04, but should not contain any platform-specific items. The patch, the files and scripts for doing the experiments and performance tests are attached.

Oleg Ivanov
Postgres Professional
The Russian PostgreSQL Company


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers