Forem: Sergey Solovev

Create and debug PostgreSQL extension using VS Code

Sergey Solovev — Sat, 18 Oct 2025 15:27:17 +0000

In this tutorial we will create PostgreSQL extension ban_sus_query. It will check that DML queries contain predicates, otherwise will just throw an error.

Next, in order not to mislead up, I will use term contrib for PostgreSQL extension, and for extension for PostgreSQL Hacker Helper VS Code extension.

This tutorial is created not only for newbies in PostgreSQL development, but also as a tutorial for VS Code extension PostgreSQL Hacker Helper. Documentation for it you can find here.

Preparation

First things first, you must setup development environment. This involves 2 things.

PostgreSQL setup

To create extension you must build PostgreSQL. Even if you will not run any query and just trust me - you will not be able to build an extension, because compilation depends on several files which are created only during source code compilation.

Do not worry about it. On documentation site there are 2 related pages:

PostgreSQL setup - introduction to PostgreSQL build system
Development scripts - various development scripts for PostgreSQL building, developing and debugging.

Pages contain not only examples, but also tips.

VS Code setup

VS Code - is the IDE we are using, so we should setup it properly for convenient development.

VS Code setup page contains lists of necessary extensions and configuration files.

Also, it has a very handy tasks.json file which is bundled with lots of predefined tasks for various use cases of PostgreSQL development. They use scripts from previous section and thus you can use them to turn VS Code in a PostgreSQL IDE. i.e. you can have PostgreSQL up and running from the ground using 2 tasks: Bootstrap and Run DB!

Creating initial files

PostgreSQL has infrastructure for contrib building and installation. In short, contribs have a template architecture - most parts are common for all.

So, for faster contrib creation we will use command: PGHH: Bootstrap extension.

It will prompt us to bootstrap some files - choose only C sources.

After that we will have our contrib files created:

Initial code

Query execution pipeline has 3 stages:

Parse/Semantic analysis - query string parsing and resolving tables
Plan - query optimization and creating execution plan
Execution - actual query execution

Our logic will be added to the 2 stage, because we must check real execution plan, not Query.
This is because after multiple transformations query can be changed in multiple ways - predicates can be deleted or added, therefore we may get a completely different query than in the original query string.

To implement that we will create hook on planner - planner_hook. Inside we will invoke actual planner and check it's output for the existence of predicates.

Starter code is the following:

#include "postgres.h"

#include "fmgr.h"
#include "optimizer/planner.h"

#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

static planner_hook_type prev_planner_hook;

void _PG_init(void);
void _PG_fini(void);

static bool
is_sus_query(Plan *plan)
{
    /* ... */
    return false;
}

static PlannedStmt *
ban_sus_query_planner_hook(Query *parse,
                           const char *query_string,
                           int cursorOptions,
                           ParamListInfo boundParams)
{
    PlannedStmt *stmt;

    if (prev_planner_hook)
        stmt = prev_planner_hook(parse, query_string, cursorOptions, boundParams);
    else
        stmt = standard_planner(parse, query_string, cursorOptions, boundParams);

    if (is_sus_query(stmt->planTree))
        ereport(ERROR,
                (errmsg("DML query does not contain predicates")));

    return stmt;
}
void
_PG_init(void)
{
    prev_planner_hook = planner_hook;
    planner_hook = ban_sus_query_planner_hook;
}

void
_PG_fini(void)
{
    planner_hook = prev_planner_hook;
}

Now we are ready to add "business-logic", but before let's understand how such suspicious queries look like.

Examine queries

Suspicious query - is a DELETE/UPDATE query that does not contain predicates.

One of the benefits that we are checking already planned statements is that all predicates are already optimized in a sense that boolean rules are applied.

Query plan - is a tree of Plan nodes. Each Plan contains lefttree/righttree - left and right children and qual - list of predicates to apply at this node. But we must check only UPDATE/DELETE nodes, not each node, - nodes for them is ModifyTable.

Thus our goal is:

traverse query tree, find ModifyTable and check that it's qual is not empty

But, before run sample queries to look what their queries looks like (inside) and which predicates they have.

For tests we will use this setup:

-- Schema
CREATE TABLE tbl(x int);

-- Test queries
DELETE FROM tbl;
DELETE FROM tbl WHERE x = 0;

UPDATE tbl SET x = 1;
UPDATE tbl SET x = 1 WHERE x = 0;

To do this we will use our contrib - install it using make install, add to shared_preload_libraries='ban_sus_query' and put a breakpoint to return in ban_sus_query_planner_hook function.

PostgreSQL has multiprocess architecture, so you must specify PID of process (backend) to which you want to attach. You can do this in 2 ways:

Request PID of backend directly using SELECT pg_backend_pid(); query. It will return PID of backend.
Search for required backend by typing postgres in quick input (when using ${command:pickProcess}).

But in any way, you must setup launch.json file. In documentation for the extension I have included sample configuration file (link), that you can use in most projects.

After debugger have attached and you run first DELETE query without predicate, we will see the following:

PlannedStmt contains top-level ModifyTable with empty qual list
Inner SeqScan also contains empty qual list

Now run DELETE query with predicate:

PlannedStmt still contains empty qual list
Inner SeqScan now contains qual with single element - equality predicate

This is no surprise, because our ModifyTable does not apply any filtering - it just takes tuples from children (note, that by convention single-child nodes store them in lefttree), so it's qual is empty, but filtering is applied to SeqScan - we must check this.

As you can mention, extension shows all Node variables with actual types, without showing generic Plan entry.
Also extension is able to show you elements of container types (List * in this example).
More than that, it renders Expr nodes (expressions) as it was in a query, so you do not have to manually check each field, trying to figure out what expression it is.

In vanilla PostgreSQL you would have to evaluate 2 expressions: (first) get NodeTag and (second) cast variable to obtained NodeTag.
In this example, to show stmt->planTree all you need to do is expand the tree node in variables explorer, but manually (without extension), you need to evaluate (i.e. in watch) 2 expressions/steps:

((Node *)planTree)->type get T_ModifyTable - tag of ModifyTable node, and then

(ModifyTable *)planTree - show variable with real type.

Such manipulations take roughly 5 second, but, as this time accumulates, totally it can take up to 1 hour in a day - just to show variable's contents!

But there is not such support for Expr variables - you will not see their representation.
For this you have to dump variable to log using pprint function, which is not very convenient when you developing in IDE.

Now we are ready to write some code.

`is_sus_query` implementation

I repeat, our goal is to traverse query tree, find ModifyTable and check that it's qual is not empty, but now we can refine it:

Search for ModifyTable in Plan tree and check that it's children have non-empty qual list

As tree traversal is a recursive function, we will use 2 recursive functions:

is_sus_query - main function that traverses plan tree to find ModifyTable node, and when it finds one invokes...
contains_predicates - function that checks that this Plan node contains any predicate in a query

Let's start with is_sus_query. All we have to do here is to check that Plan is a ModifyTable and if so, then check that it's children contain predicates.

Node type checking is a frequent operation, so extension ships with some snippets - one of them is a isaif, which expands to if(IsA()) check:

When we have determined, that it is a DML operation check that it is DELETE or UPDATE, because ModifyTable is used for other operations, i.e. INSERT. This is not hard - just check operation member.

static bool
is_sus_query(Plan *plan)
{
    /* ... */
    ModifyTable *modify = (ModifyTable *)plan;
    switch (modify->operation)
    {
        case CMD_UPDATE:
        case CMD_DELETE:
            /* Check predicates */
            break;
        default:
            break;
    }
    /* ... */
}

And now check these operations contain predicates using contains_predicates function (will be defined further).

Also, do not forget to handle recursion: call is_sus_query for children and handle end case (NULL).

The result function looks like this:

static bool
is_sus_query(Plan *plan)
{
    /* Recursion end */
    if (plan == NULL)
        return false;

    if (IsA(plan, ModifyTable))
    {
        ModifyTable *modify = (ModifyTable *)plan;
        switch (modify->operation)
        {
            case CMD_UPDATE:
            case CMD_DELETE:
                return !contains_predicates(modify->plan.lefttree);
            default:
                break;
        }
    }

    /* Handle recursion */
    return is_sus_query(plan->lefttree) || is_sus_query(plan->righttree);
}

`contains_predicates` implementation

Now perform actual checking of the predicates existence using contains_predicates. Inside this function we must check that given Plan contains predicates.

But situation is complicated by the fact that only base Plan is given and we do not know actual query. For example this query:

DELETE FROM t1 using t2 where t1.x = t2.x;

Will contain JOIN in lefttree of ModifyTable:

Thus we have to clarify what does contains_predicates must check. In order not to complicate things a lot, we will just find first node with any predicate.

static bool
contains_predicates(Plan *plan)
{
    if (plan == NULL)
        return false;

    if (plan->qual != NIL)
        return true;

    return contains_predicates(plan->lefttree) || contains_predicates(plan->righttree);
}

Testing

First things first - test on example queries we defined above:

postgres=# delete from tbl;
ERROR:  DML query does not contain predicates
postgres=# delete from t1 where x = 0;
DELETE 0

postgres=# update tbl set x = 0;
ERROR:  DML query does not contain predicates
postgres=# update tbl set x = 0 where x = 0;
UPDATE 0

It's working as expected.

Also, as we injected our contrib as the last step, we can handle more complicated cases, like:

postgres=# delete from t1 where true;
ERROR:  DML query does not contain predicates

Further improvements

This is just the beginning of the contrib, because there are lot's of corner cases that are not handled.

For example, if we change true to false in last query, then we still will get an ERROR.
That is because the database has realized that subquery will not return anything, so replaced with "dummy" Plan - Result node with FALSE one-time check, so nothing will be returned:

Conclusion

So far we have seen how you can quickly create new contrib using single command that will create all necessary files.

To write some templated code, we used isaif snippet to quickly add check for Node type.

Also, we have traversed query plan tree and saw it's nodes, without requirement to obtain NodeTag and cast to given type, which incredibly boosts productivity.

And like the icing on the cake we saw expression representations of predicates. For our purposes this is not a very big deal, because query contained only 1 predicate, but in large queries with dozens of different predicates it's just a lifesaver.

But actually, this is the small part of the extension's features. As stated before, it knows about PostgreSQL variables semantics and actively uses it. For example, display elements of hash-tables, render some builtin scalar types in more convenient way (i.e. XLogRecPtr shown in FILE/OFFSET form, not integer), bitmask support, etc...

Tip & tricks

As you may have noticed, the extension greatly facilitates development and debugging process. But extension is just an extension, an automation tool - there are lots of other aspects that can be optimized. You can refer to documentation site where you can find useful information with tips and tricks for development:

And, of course, main links:

The PostgreSQL Hacker Helper extension is one year old

Sergey Solovev — Thu, 14 Aug 2025 12:09:02 +0000

PostgreSQL Hacker Helper is a VS Code extension for developing PostgreSQL source code. A couple of days ago (August 9th), one year has passed since the release of version 1.0.0.

Initially, it was a utility for dynamically calculating expressions and casting variables, but after a while I realized that not everything is so simple. The main catch is that there are types (if you can say so) that require special treatment.

The most striking example is a List, a dynamic array. What's so special about it? Firstly, there is only one data structure, but inside it it stores (either-or) a pointer/int/TransactionID/Oid. Secondly, its implementation depends on the version. Previously, it was implemented as a linked list, but today it is an array.

Another interesting example is Value. Today, this structure does not exist, as it has been split into separate String, Integer, Float, Boolean, and BitString (src/include/nodes/value.h). This also violates the initially beautiful picture, as you have to add (complex) logic - the name of the structure does not correspond to the type of the stored node.

I've added a lot of features this year:

Expression rendering (variables representing expressions are displayed by the expression they represent)
Displaying the contents of hash tables
Pointers to relations from variables of the Relids type
Formatting a source code using pgindent
Bootstrapping new extensions (creating template extension files)
Dump node representation to a log or a separate text file (via pprint/nodeToString)

If we talk about non-functional features:

Greater extensibility due to the configuration file
Support for multiple debugger extensions
Testing (integraion) and CI pipeline for this

What I remember most was the addition of CodeLLDB debugger support. I've been doing this for 5 days from morning to night. At the same time, I added testing.

The most difficult part of all this is supporting older versions of PostgreSQL. For the extension to work, I rely on dynamic evaluation of functions in the debugger, but various major releases may break binary compatibility and some functions may be removed. I can't remember how many times I spent hours looking for workarounds to implement some functionality.

Looking at all this, I realize that now it can be called an entire IDE for PostgreSQL. Although it seems that everything that could have been written has already been done, I am constantly finding new opportunities for its development.

Links for those interested: GitHub repo, VS Code marketplace.

pg_dphyp: teach PostgreSQL to JOIN tables in a different way

Sergey Solovev — Mon, 28 Jul 2025 09:15:11 +0000

Greetings!

I work in Tantor Labs as a database developer and naturally I am fond of databases. Once during reading the red book I have decided to study planner deeply. Main part of relational database planner is join ordering and I came across DPhyp algorithm that is used in most modern (and not so much) databases. I wonder - is there is anything in PostgreSQL? Surprisingly, nothing. Well, if something does not exist, you need to create it yourself.

This article is not about DPhyp per se, but about what I had to deal with in the process of writing the corresponding extension for PostgreSQL. But first thing first, a little theory.

If you want to go straight to the extension, here is the link to the repository.

Join ordering algorithms

The query planner in databases is perhaps the most complex and important component of the system, especially if we are talking about terabytes (especially petabytes) of data. It doesn't matter how fast the hardware is: if the planner made a mistake and started using sequential scan instead of the index scan, that's it, please come back for the result in a week. In this complex component, you can single out the core: JOIN ordering. Choosing the right table JOIN order has the greatest impact on the cost of the entire query. For example, a query like this...

SELECT *
FROM t1 
JOIN t2 ON t1.x = t2.x
JOIN t3 ON t2.x = t3.x
JOIN t4 ON t3.x = t4.x;

...has 14 possible combinations of table JOIN orderings. In general, this is the number of possible representations of a binary tree of n nodes, where nodes are tables, Catalan number - $C_{n - 1}$ . But do not forget, that order of tables also important, so for each shape of JOIN tree we must consider all table reorderings. Thus, number of possible JOIN orderings for query with n tables is $C_{n - 1}n!$ . This number is growing very fast. For example, for 6 tables it will be 30240, and for 7 - 665280! Needless to say, from a certain point on, this number becomes so huge that it becomes almost practically impossible to find the optimal plan by simply iterating through all the combinations? The way we are going to search suitable ordering determines architecture of the planner: top-down vs bottom-up.

In the top-down approach (also called goal-oriented) we start from the root and recursively descending down the query tree. The advantage here is that we have the full context in our hands and can use it. The most illustrative example are correlated subqueries: top-down planner can use current context to transform such nested subquery into simple JOIN - this can dramatically improve performance. An example is the cascades planner (roughly speaking, this is the framework), which is used in Microsoft SQL Server: it can easily move the nodes of the query graph under GROUP-BY, which another approach (bottom-up) cannot do without additional help (the architecture assumes a static set of relationships for connection).

Bottom-up is the opposite approach. Here all JOINS are planned first and only then sorting/grouping (+ other operators) operators are added. This approach is used in many databases, including PostgreSQL. Its advantage is scalability, as it allows you to schedule a huge number of JOINS. For example, in the article Adaptive Optimization of Very Large Join Queries presents an approach that allows query planning with several thousand tables by combining different algorithms. The example in the article is SAP, which, due to the constant use of views within other views, can create a query using thousands of regular tables.

There are lots of bottom-up algorithms, so consider the ones that PostgreSQL uses.

DPsize

During the dawn of RDBMS, no one fully understood how everything should work, and everyone did their best. Then the first dynamic programming algorithm appeared to find the order of connections. Today, everyone (at least in the articles) calls it DPsize.

Let's remember what an relation is. Relational algebra is built on working with relations. Relation can be understood as a simple data source with its own schema (attributes). The simplest example of a relation is a table, but another important example is a JOIN, because in fact it meets the requirements (it gives tuples and have attributes). Next, I will use the term "relation", but where it is important to emphasize the difference, I will say "table".

The idea of DPsize is simple: to create a JOIN of i tables, you need to JOIN other relations, which in the sum of the number of tables will give i. For example, for 4 we need to connect 1 + 3 or 2 + 2 tables. Actually, this is dynamic programming - the answer of the current step depends on the answer of the previous ones, but the base is a relation of size 1 - ordinary table. The algorithm performs well on an OLTP load when there are few tables, and provides almost optimal query plans, but problems begin when there are too many tables.

As you can see, the time/space complexity of this algorithm is exponential, since at each subsequent step it is required to process even more pairs of relationships. Different databases deal with this in different ways, and PostgreSQL has started using a different algorithm.

GEQO

GEQO (Genetic Query Optimizer) is a genetic algorithm for finding the optimal query plan. If you try to run a query in PostgreSQL, first for 12 tables, and then for 13, you will be surprised, because the time spent has decreased from a few seconds to almost ten milliseconds. Why? Because GEQO has entered the game (geqo_threshold setting is 12 by default). The fact is that this is a randomized algorithm, its core idea can be described as follows: first, we build at least some query plan, and then we carry out several iterations (this is determined by the configuration), in each of which we randomly change some nodes, and in the next iteration there is a plan with the best cost. Hence the name "genetic" due to the fact that the strongest (in our case, the cheapest) pass into the next generation (iteration).

DPhyp

Let's move on to the main topic — the DPhyp algorithm. DPhyp is a dynamic programming algorithm for JOIN ordering. Its main idea is that the query itself contains guidance on how tables should be joined. So why not use it? The main problem is in the query representation itself. I mentioned earlier that a query can be represented as a graph, but is it possible to do this for the purposes of iterating over JOINS? To understand the difficulty, let's look at an example from the paper:

SELECT *
FROM R1, R2, R3, R4, R5, R6
WHERE R1.x = R2.x AND R2.x = R3.x AND R4.x = R5.x AND R5.x = R6.x AND
      R1.x + R2.x + R3.x = R4.x + R5.x + R6.x

Yes, we see that there are several explicitly connected tables — for them we can create edges in our graph (for example, R1 - R2), but what about the last predicate, which actually connects multiple tables? This problem is solved by DPhyp, a dynamic programming algorithm (DP) based on hypergraphs (hyp — hypergraph). You should not be afraid, I assume that you are familiar with an ordinary graph — a set of nodes connected by edges, but a hypergraph is a set of hypernodes connected by hyperedges:

hypernode — is a set of regular nodes;
hyperedge — is an edge, connecting 2 hypernodes.

In example query we have next hyperedges:

{R1} - {R2}
{R2} - {R3}
{R4} - {R5}
{R5} - {R6}
{R1, R2, R3} - {R4, R5, R6}

If there is only one relation in a hypernode, then it is called a simple hypernode. Similarly, if a hyperedge connects two simple hypernodes, then it is a simple hyperedge. Thus, the first four of the list above are simple hyperedges.

To create a plan for a set of i nodes, we need to handle not all possible pairs that give i in total, but all pairs of hypernodes that give the same set. This is a pair of two disjoint sets: a connected subgraph (csg, subgraph) and a connected complement (cmp, complement). These abbreviations will often appear in the post.

To make everything work optimally, we need to introduce a small restriction — the order of the nodes. There should be an order above the nodes (i.e. tables), roughly speaking, they should be numbered (numbering is used most often) so that we can compare and sort them later. To understand why, let's look at the core of the algorithm — neighborhood.

During the operation of the algorithm, we use neighbors to move from one hypernode to another. The article provides a mathematical definition, but the easiest way is to say that the neighbors of a hypernode are other reachable nodes. It is also required that this set be minimal, otherwise we will process the same hypernodes several times. This is where the order is needed — when we bypass the edges to find neighbors, we add only the representative of the hypernode, its minimal element, to the set. Next, you just need to check that the other edges do not contain nodes that have already been added.

The last important detail of the algorithm is the excluded set. In DPsize, as an optimization, we start iterating over complementary pairs not from 0, but from the next index, or otherwise we will try to connect ourselves to ourselves, and process some pairs twice. The idea is about the same here, we keep track of nodes that are not worth considering (excluded) and check this almost everywhere, even when finding neighbors. Due to this, we can avoid considering the same set twice.

The main logic of the algorithm in the article is represented by five functions, and the core of the algorithm can be briefly described as follows: we need to find a csg-cmp pair that combines the entire query, so using neighbor search, csg and cmp will increase alternately/recursively. The only question is where to start. The answer here is this — we start iterating over all nodes starting from the end, and add to excluded set all nodes that are smaller than the current one. As a result, we start with a simple hypernode that no one has considered, and then recursively expand it and find the cmp for it using neighbors.

Actually, it's not difficult to understand the functions now:

Solve — algorithm's entry point. Iterate over all simple hypernodes from end and invoke EmitCsg and EnumerateCsgRecursive;
EmitCsg — accepts fixed csg, for which we find corresponding cmp, and then invoke EmitCsgCmp and/or EnumerateCmpRecursive;
EmitCsgRecursive — accepts csg, which is expanded using it's neighborhood, then invoke EmitCsg and/or EnumerateCsgRecursive;
EnumerateCmpRecursive — accepts fixed csg with cmp, which is expanded using cmp's neighborhood, then invoke EmitCsgCmp and/or EnumerateCmpRecursive;
EmitCsgCmp — creates query plan for given fixed csg/cmp pair.

The main idea is clear. And as an example, the article also has a step-by-step illustration of how the algorithm works for the query from the example:

Iteration performed backwards, so start from R6 (the highest index), but it does not have any neighbors, because all other nodes are in excluded set.
Move on to R5.
Find neighbor R6 and create cmp {R6}.
Expand csg itself to {R5, R6}.
Move on to R4.
Find neighbor R5 and create cmp {R5}.
Expand cmp to {R5, R6} (R6 is a neighbor of R5).
Move back to 6 step and expand csg to {R4, R5} (earlier cmp is expanded).
Find neighbor R6 for csg {R4, R5} and create corresponding cmp {R6}.
Expand csg {R4, R5} to {R4, R5, R6}.
Move on to R3 ({R1, R2} are excluded), but it does not have any neighbors:
- All hypernodes, we have direct edge with (R1 and R2), are excluded (have lower index);
- Representative of left hyperedge of complex hyperedge (min({R1, R2, R3}) = R1) also in excluded set, so this hyperedge is not considered.
Move on to R2.
Find neighbor R3 and create cmp {R3}.
Expand csg to {R2, R3}.
Move on to R1.
Find neighbor R2 and create cmp {R2}.
Expand cmp to {R2, R3} (R3 is a neighbor of R2).
Expand csg to {R1, R2} (R2 is a neighbor of R1).
Find neighbor R3 and create cmp {R3}.
Expand csg to{R1, R2, R3} (R3 is a neighbor of R2).
Find neighbor R4 and create cmp {R4} (use representative R4 of complex hyperedge {R1, R2, R3} - {R4, R5, R6}).
Expand cmp to {R4, R5} (R5 is a neighbor of R4).
Expadn cmp to {R4, R5, R6} once again (R6 is a neighbor of R5).
Move back to step 20 and expand csg using {R4}.
Then add {R5}.
Finally add {R6}.

The algorithm is quite good and intuitive. Can I add it to PostgreSQL? Yes, and it has always been possible! For such case, there is a join_search_hook — a hook that allows you to replace vanilla JOIN search algorithm.

pg_dphyp extension

The idea to create this extension came to me by chance: I was studying different JOIN algorithms and came across it. An Internet search didn't turn up anything like this for PostgreSQL, and I realized that I had to do it myself. Who immediately wants to see what happened, here is the link to the repository. In the context of the core of the algorithm, I did not bring anything new, on the contrary, I copied more from others. Before starting to implement my own, I looked at the implementations in several databases, in particular, YDB, MySQL and DuckDB. If someone wants to learn DPhyp by code, I recommend looking at code YDB — Clean and clear, very easy to read. But I didn't start with YDB myself, but with MySQL, and now its implementation has been significantly changed and optimized, it won't be possible to figure it out right away, only based on the comments and with the initial understanding of DPhyp itself.

In the implementation, I tried to be closer to the paper and make the minimum number of changes. For example, the names of functions and some variables are the same as in the paper. But although there are practically no changes in the core of the algorithm, they exist at the operational decision-making level, and the first of them concerns the representation of sets.

Set representation

Sets are the workhorse of the algorithm, underlying all of its effectiveness. Different DBMS do this in different ways, for example:

DuckDB uses numbers directly and store them in an array;
YDB - std::bitset<> from C++ standard library;
MySQL - 8-byte number as bitset.

Anyone who works with PostgreSQL knows that there is its own implementation of the set — Bitmapset. It is used everywhere and most common use case is to store relation IDs. It would seem that you should just take it and use, but the problem is that there are a lot of operations on sets, and Bitmapset creates a new copy every time it changes, that is, these are unnecessary memory allocations. In PostgreSQL, this problem often does not occur, because after creating the Bitmapset it rarely changes, but not in my case, and this is critical.

In first implementation, I have solved the problem by implementing two approaches at once — I have created two files, where in one I used bitmapword (an 8-byte number/bitset, as in MySQL), and in the other I have used Bitmapset for complex queries (with more than 64 tables). But this happened at the very beginning of development, when I still did not really understand the subtleties of the algorithm. So after a while I dropped updating the file with the "Bitmapset" (I decided to add changes later), and finally completely deleted it.

Now I use the representation of a set using a number, and this does not cause many problems. The basic operations with a set are performed with simple bitwise operations: |, & and ~. But there are a couple more operations that are important for the algorithm itself, for example, iterating over the elements of the set in the process of calculating neighbors. There are many such operations, so I put them in a separate header file.

Another interesting operation is iteration over all subsets, this is necessary to expand csg/cmp. Since a set is a number, the operation is performed with a number. In MySQL and YDB, this was solved using the bit trick (init - state) & state, which, when applied continuously, behaves like an increment, but only the bits of the set change. This implementation is currently in use. For example, for the set 01010010 we get the following subsets:

00000010    001
00010000    010
00010010    011
01000000    100
01000010    101
01010000    110
01010010    111

On the left side - number as set in binary representation, and on the right side - it's bitmask. As we iterate by incrementing, so we can say, that bitmask in number representation is the same as iteration number. Next, we will use such property often.

DP-table

DPhyp is a dynamic programming algorithm, and it has its own table for tracking execution status. If you look at the algorithm from the paper, you can see that this table is used only for storing ready-made query plans. In PostgreSQL, the RelOptInfo structure is used to store list of query plans (Path structures) for fixed set of relations, and it is already stored in the hash table. It seems that you don't have to think about creating your own hash-table, but no. The problem lies in PostgreSQL itself, or rather, its FULL JOIN processing.

For this type of JOIN, only the equality predicate is currently supported, and in the code, when such a predicate occurs, all relations in the left and right parts fall into separate lists that are planned independently. For example, for query SELECT * FROM t1 FULL JOIN (SELECT t2.x x FROM t2 JOIN t3 ON t2.x = t3.x) s ON t1.x = s.x we have to run 2 JOIN algorithms: {t2, t3} and {t1, {t2, t3}}.

This is the reason why internal tables use their own indexes (that is, DPhyp node indexes do not necessarily correspond to relationship indexes). Therefore, even if we temporarily turn bitmapword into Bitmapset, which will require additional memory allocation, I will not be able to do this if the relation indexes exceed 64 (the maximum value for an eight-byte number).

Hash table in PostgreSQL (HTAB structure) has one specificity - it store element and it's key in same structure (key must be first member of element's structure). But builtin hash table for storing RelOptInfos hash Bitmapset key and pg_dphyp uses bitmapword (the reason discussed above). So extension creates and maintains it's own hash table.

Hypergraph creation

Another important task is the building of the hypergraph itself. The problem is that unlike YDB or MySQL, we don't run the show and obey the rules of the database.

There doesn't seem to be a problem, I can go through all the predicates used in the query and create edges from them. Actually, this is how it is implemented now. But the devil is in the details.

Such hyperedge information stored in 3 separate places:

PlannerInfo->join_info_list — list of non-INNER non-INNER JOIN predicates.
RelOptInfo->joinclauses — list of JOIN predicates (require more than 1 relation).
PlannerInfo->eq_classes — list of equivalence classes.

The first is the simplest. This list contains restrictions that are imposed by various non-INNER (i.e. LEFT/RIGHT/FULL, etc.) JOINS. It has 2 pairs of parts: syntactic constraints and the minimum ones (the only needed for the calculation). Hyperedges are created a hyper-edge for both pairs just in case.

The second one has difficulties in terms of the expression itself — expression may not be binary, or it may be, but the same relation can be mentioned on both sides. For such moments, I added my own concept — cross join set (cjs). It's just a set of relations that need to connect with each other (clique). For each relation in CJS, I create simple edge (each with each one). This solves the problem that some predicates may be missing. In example WHERE sample_func(t1.x, t2.x t3.x) have CJS of {t1, t2, t3} - this is not binary predicate and we create {t1} - {t2}, {t2} - {t3} and {t1} - {t3} hyperedges.

Lastly, the third - equivalence classes. The equivalence class is a PostgreSQL mechanism by which it determines that some expressions are equal to each other. This is not only used in predicates (to deduce equivalences). For example, expressions in ORDER BY or GROUP BY are represented by an equivalence class (possibly degenerate, with a single element). But now it's not about that, but about how it shoots. Such equivalence classes appear when there are equality expressions in the query, and even one is enough to create an equivalence class. As you might guess, they are also used for JOINS. When I encounter an equivalence class with multiple relations, I have to create hyper edges for each pair. Therefore, such queries with only equality under the hood turn into a clique (as you can mention - logic is same as for CJS).

For example, consider this query:

SELECT * FROM t1 
         JOIN t2 ON t1.x = t2.x AND t1.y > t2.y
         JOIN t3 ON t1.x + t2.x = t3.x
    LEFT JOIN t4 ON t4.x = t3.x;

It contains:

equivalence classes: {t1.x, t2.x} and {t1.x + t2.x, t3.x};
JOIN predicate: t1.y > t2.y;
special (LEFT) JOIN predicate: t4.x = t3.x.

We will create the following hyperedges:

{t1} - {t2}
{t3} - {t1, t2}
{t3} - {t4}

Disconnected subgraphs

Another problem arises from the above. What happens if we get a disconnected graph (a forest)? In this case, the algorithm will not be able to create result plan. More precisely, it will create a plan for each connected component in the forest, but it will no longer be able to do so for the entire query. Moreover, this problem may appear not only because of the CROSS JOIN or ,, but also because of the external parameters of the subqueries. I'll give you an example:

SELECT * FROM t1
WHERE t1.x IN 
    (SELECT t2.x FROM t2, t3 WHERE t2.x = t1.x AND t3.x = t1.x);

I discovered this when I ran \d (to display all tables) in psql, and it turned out that there was an example query.

In the subquery, t1.x is a parameter, but we have a forest in the output graph, because there is no relation ID for t1 in the subquery. On one hand, in practice disconnected graphs are quite rare to waste resources to detect such a thing, moreover, we can waste extra time (just double the planning time without any payload). Therefore, I left it up to the users to decide what to do.

There is setting pg_dphyp.cj_strategy, which accepts 3 values:

no – if we failed to build result plan, then invoke DPsize/GEQO with initial values;
pass – if we failed to build result plan, then collect plans for all connected components and pass them to DPsize/GEQO;
detect – find all connected components during initialization and create dummy hyperedges for them.

You can think that no is superfluous, but it is not because the plans created for these subgraphs may not be optimal due to the fact that there may be implicit connections between disconnected subgraphs that could help create an optimal plan. Therefore, the final plan may also be suboptimal.

The question remains: how to find disconnected graphs? The answer is simple - Union-Set algorithm. For performance, an optimized version is used: ranking and leader updating.

Hypergraph representation

One more task is storing the hypergraph. The graph can be stored as a list of edges, or it can be an adjacency table. But for a hypergraph, only the first option remains, since it is practically impossible to build an adjacency table for hypergraph (hyperedge connects hypernodes which can have more than 1 node on both sides).

Well, we've decided to use list of hyperedges, but is it possible to apply any optimizations? Yes, we can. For almost all implementations (for example, YDB and MySQL) there is an optimization for simple hyperedges. Let me remind you once again that a simple hyperedge has set of a single element on both sides. This optimization uses this fact to store all nodes for which we have simple hyperedge in single set. Next, during work we need to do a single operation (i.e. subset or overlaps) to check multiple edges at once. Such a set is often called a "simple neighborhood", I think it's clear why. This optimization is also used in extension, but I went a little further, and I store this simple neighborhood for each hypernode (in the HyperNode structure). This simplifies the work a bit, since you don't need to spend time on additional iteration across nodes, and it takes up only 8 bytes of space.

But this is still not the end. Earlier, I said that for the same expression in the query text, multiple instances of RestrictInfo (representation of the expression in the source code) can be created, but with a different set of indexes of the required relations. At the same time, I said that I couldn't process these additional relation IDs, so I could end up with a lot of duplicates of expressions. This can lead to lots of wasted work. I solved this using sorting: all hyperedges stored in sorted array. So adding new hyperedge is adding new element to sorted array - binary search can quickly find duplicates and prevent such bloating.

Query plan building

If you have read original paper then you known that DPhyp is not only about JOIN ordering, but it also gives some tips for effective query plan creation. This is an important point, since some JOIN operators are not commutative (for example, LEFT JOIN), and such JOINs impose restrictions. But that's not all. Let me remind you that DPsize (builtin planner) has high cohesion with the code base — so much so that it is impossible to create a plan for the i tables without finding the optimal plan for the underlying ones.

According to DPhyp query plan built in EmitCsgCmp. Initially, that's what I did:

Take 2 RelOptInfo (csg/cmp, left/right) and invoke make_join_rel with them.
Call generate_useful_gather_paths to create gather paths (parallel).
Call set_cheapest to find the best plan.

But if you look inside, you will see that the generate_useful_gather_paths and set_cheapest functions go through all the paths created so far, that is, as the program runs, the time spent on its execution will only increase. Moreover, set_cheapest function will update cheapest paths found, so these paths can be used to create new RelOptInfos - that is the problem, because in such approach we can use not cheapest plan, but first created.

Due to these facts, I switched to a DPsize-like approach. Keep a list of candidate hypernode pairs that can create target for each hypernode. At the end recursively build target RelOptInfos using this list and finally invoke generate_useful_gather_paths/set_cheapest.

Yes, there is a chance that there will be a pair inside that will not be able to create a query plan, and I will waste time, but the overhead of the initial approach (with a constant call to set_cheapest) is still greater, and the probability that some pair of hyper nodes will not create a useful JOIN is extremely low due tofor the very idea of DPhyp.

Optimal neighborhood calculation

Finally, we've come to the most interesting part - how we're going to traverse the neighbors. We can highlight three functions in the algorithm that are engaged in creation of csg/cmp pairs, and in them we need to calculate neighbors as many as four times: EmitCsg, EnumerateCsgRec and EnumerateCmpRec. Everything starts to look more intimidating when you realize that the algorithm involves iterating over all possible subsets of neighbors (power set without the empty set) is $2^i - 1$ combinations.

Yes, we have added simple neighborhood optimization, but still we need to process all the nodes in the subsets. Totally, we get $∑k=1nkCnk\sum_{k = 1}^{n}kC_{n}^{k}$ nodes that need to be processed for all subsets.

The number of different combinations of subsets of $k$ elements is $C_{n}^{k}$ , but for each subset of size $k$ , each of its elements must be processed, and there are $k$ of them. In other words, the number of elements in all subsets of size $k$ is $kC_{n}^{k}$ .

First, let's look at the definition of neighborhood:

E\darr'(S, X) = {v|(u, v) \in E, u \subseteq S, v \cap S = \emptyset, v \cap X = \emptyset } \newline E\darr(S, X) = minimal\ set: \forall_{v\in E\darr'(S,X)} \exists v' \in E\darr(S,X): v' \subseteq v \newline \mathcal{N}(X, X) = \cup_{v \in E\darr(S, X)} min(v)

The set $E↓′E\darr'$ is created — (interesting) hyperedges belonging to the current hypernode and pointing beyond it.
This set is minimized to eliminate subsumed hypernodes (so there are no overlaps and potential duplicates).
Only representatives (the smallest elements) are selected from remaining hypernodes.

The second step (finding the minimum set) is a complex computational task, so many databases use optimization: as nodes are traversed representatives added into the neighbors only if this hypernode does not intersect with already computed neighborhood. This approach is used by MySQL and YDB.

Does it make sense to optimize this fragment? There are quite a lot of comments in the MySQL code that describe certain decisions made (most often based on micro benchmarks). One of the such comments is written for the neighborhood computation function FindNeighborhood:

...
This function accounts for roughly 20–70% of the total DPhyp running time, depending on the shape of the graph (~40% average across the microbenchmarks)
...

That is, almost all the time the algorithm is running is occupied by the logic of calculating neighbors, and therefore, yes, there is a point in optimizing it.

MySQL approach

The idea implemented in MySQL is based on the property of subsets that we get when iterating incrementally. You can notice that in the next step we often get a superset of the previous step, and very often (in most cases - every next step) the first bit is constantly switched from 0 to 1. And if we switch it from 0 to 1, then we get a subset! For example, 0011101 is subset of 0011100.

There is an immediate desire to simply take the previous neighbors and add this first element, but the question arises — is this correct? Yes, that's correct. If we look again at the definition of neighbors from the article, we will not see any restrictions on the order of node traversal, which means that we can take one set and enlarge it with some new element.

To make the idea clearer, let's look at an example of iterating over a subset of 4 nodes. Here is an example from a comment:

With an asterisk, I indicated the places where we will have to fully calculate the neighbors, that is, you must clear the cache, but after that — on the next subset — it will be enough for us to process only one node (the first one). If everything is done honestly (without optimizations), then for an initial set of size 4, - 32 nodes will have to be processed, and using this heuristic, only 20.

It was also pointed out in the comment that there are optimal subset traversal orders that will give even greater gains. For a set of four elements, it will be like this (in the comment in the code, probably a little bit — after 0111 comes 1110, which does not allow optimal calculation of neighbors, so here is my corrected version).

The idea is simple: we iteratively shift the rightmost (first) bit to the left until it hits the left side of sequence of ones, and when this left side is over (all 1), we start a new digit — we update the cache at the beginning of a new digit or when this bit hits a sequence of ones.

Here we only need 15 iterations (nodes to process). In practice, even such a heuristic with tracking the last bit gives a significant increase, requiring almost 2 times fewer iterations.

Is the optimal order known for a larger set? Yes, but only for five elements (I won't give example of it here, you can see it in the same comment).

If someone thought, "just take a shortcut and that's it," then alas. Do not forget that right now you are just looking at a bitmask of included/excluded elements from the set. In reality, the elements in the bitmask are sparse, for example, iterating over the set of three elements 00101001 will look like this (on the left is a subset, on the right is this mask/iteration number):

00000001   001
00001000   010
00001001   011
00100000   100
00100001   101
00101000   110
00101001   111

Limitations of caching scheme

The neighbor caching scheme only works when the set of excluded nodes is fixed. This requirement is satisfied by the last cycles in the Enumerate* functions, when the excluded set is fixed during all iterations (in the definition from the article, these functions recursively call themselves, but with a fixed set of excluded nodes X∪N(S,X)X\cup\mathcal{N}(S,X)X∪N(S,X) ).

But even this is enough to increase performance, since the other two places of traversing subsets are:

EnumerateCmpRecursive, but it only invokes EmitCsgCmp which does not require to compute neighborhood;
EnumerateCsgRecursive, but it invokes EmitCsg, which require new excluded set (it is not fixed, depends on iteration).

To understand why neighbors cannot be cached if the set of excluded nodes is changing, let's look at a specific example. Call EnumerateCsgRecursive with a hypernode S=000110S = 000110S=000110 and excluded set X=000111X = 000111X=000111 . It has many neighbors, whose subsets we will iterate over, N=1110000\mathcal{N} = 1110000N=1110000 (that is, note that 000100000010000001000 is free for now and does not belong to anyone):

We want to efficiently compute neighbors, and for this purpose we cache them. The question is: what should I cache? The immutable part is SSS , to which a subset of neighbors is added. We decide to cache it, but then this situation arises: for some node there is a hyperedge, the right side of which is 100100010010001001000 (remember that previous free 000100000010000001000 is used).

S =  000110
X =  000111
N = 1110000  <-- current neighborhood
R = 1001000  <-- neighbor candidate

How can this hyperedge be processed correctly? We have two possible outcomes (depending on whether we have added this right part to excluded set or not):

all neighbors were not added to the set of excluded nodes. Then the node 000100000010000001000 is added to the neighbors for EmitCsg, which will be passed everywhere. But this means that for iterations in which 100000010000001000000 is involved, the logic of computing neighbors in EmitCsg will be violated, since this element will be in the excluded set, and accordingly the edge should not be taken into account;
all neighbors were added to the set of excluded nodes. Then we get the other side — in iterations where the 100000010000001000000 element is not involved, some node will be missing.

If you look at the MySQL code, you can see that they still use caching, but why? The fact is that they compute the neighbors for a subset, and then add the excluded nodes and the original neighbors to the resulting neighbors. Excluded ones are added according to the logic of Enumerate* functions, since excluded sets are passed to them as input, which contain all previously found sets, although only a small subset could be passed by a recursive call. For example, during operation, EnumerateCsgRecursive recursively called itself several times, and each time the set of neighbors consisted of two elements, but recursive calls passed only one, although the accumulated excluded nodes are the union of all found neighbors. That is, the set of excluded nodes that have been passed to us can contain all the nodes that will be valid neighbors in EmitCsg (since it resets the current excluded ones and starts using its own).

Example: after several recursive calls, EnumerateCsgRecursive has S=1010001011S = 1010001011S=1010001011 , X=1111111111X = 1111111111X=1111111111 , but when invoking EmitCsg, the excluded set will be reset to X=0000000011X = 0000000011X=0000000011 (for example, because the smallest node is 2). Then adding X§=0101110100X\S = 0101110100X§=0101110100 will simply mean that, just in case, we want to process those nodes that were neighbors of previous calls, but did not get into the current CSG set.

The original neighbors are added according to the same logic, but in order not to violate the correctness of the algorithm: all nodes that are in the resulting subgraph are removed from the resulting set. The developers initially know that the neighbors obtained in this way may not contain all the neighbors, so they generally add everything that may be true, even if this leads to excessive calculations. Here is a part of this code with comments describing the reasons in more detail (lowest_node_idx is the index of the node with which the current iteration in solve is running):

// EnumerateComplementsTo() resets the forbidden set, since nodes that
// were forbidden under this subgraph may very well be part of the
// complement. However, this also means that the neighborhood we just
// computed may be incomplete; it just looks at recently-added nodes,
// but there are older nodes that may have neighbors that we added to
// the forbidden set (X) instead of the subgraph itself (S). However,
// this is also the only time we add to the forbidden set, so we know
// exactly which nodes they are! Thus, simply add our forbidden set
// to the neighborhood for purposes of computing the complement.
//
// This behavior is tested in the SmallStar unit test.
new_neighborhood |= forbidden & ~TablesBetween(0, lowest_node_idx);

// This node's neighborhood is also part of the new neighborhood
// it's just not added to the forbidden set yet, so we missed it in
// the previous calculation).
new_neighborhood |= neighborhood;

To implement their singleton cache, they use the class NeighborhoodCache and they transitively pass it almost everywhere. Its logic is simple: before starting the neighbor search, we find the delta of the sets, but in fact we check that the last bit is set, and at the end we save the calculated neighbors — but only if the first bit (taboo bit) is not set - just because this will not contribute to any further neighborhood sets anymore (this is last bit can be set).

As soon as I understood the idea, I rewrote the code to myself almost word for word, only rename taboo to forbidden. The code lived in this form for quite a one week, but then I realized — GPLv2! The MySQL code is distributed under the GPLv2 license, and considering that I rewrote almost everything word for word (at that time, probably not even fully understanding the idea itself), I violated this license: the extension uses MIT - they are incompatible! Then I faced the question — should I throw out this good optimization and make the code slow, or leave it, but change the license to GPLv2? As a result, I chose the first one, and this was the beginning of an exciting several-week thinking on how to optimize this combinatorics.

Suffix cache

My task is to optimize the algorithm, but in such a way that it is not a MySQL tracing paper. The idea itself is clear: why to compute the entire set if you can simply extend it with this delta. We somehow need to find either a template or something that will help us detect such a subset.

But what if you look at it from the other side? Literally from the other side. Indeed, our subset iteration method has a good property: the upper part (MSB) changes much less frequently than the lower part (LSB). So why don't we use this property? We will just cache something that rarely changes!

But what is "rarely changing" in essence? In the first idea, I took the closing ones for this constant — the sequence of the last (leftmost) ones (with a fixed digit) in the number can only increase during increment, that is, it is enough only to count the neighbors for this sequence, and then add the changing one. We can separate the base (immutable) part with a simple bitmask, and we know its size (calculated).

If we recall the optimal iteration sequence proposed by MySQL, then we can see that this strategy is ideally suited for such a sequence.

How do we track the change in this base part? It's easy, because this is binary arithmetic: we just keep track of how many iterations until the next new 1, and then divide by 2 and wait calculated number of iterations. When a new digit begins, we simply reset the counter and repeat. The algorithm is as follows:

Initialization:
1. nb_cache = 0 — cached neighborhood.
2. nb_cache_subset = 0 — bitmask of cached neighborhood above.
3. next_update = 0 — number of iterations until next cache update.
4. prev_update = 0 — saved next_update value.
For each iteration (starting from 1):
1. If next_update == 0 (new digit added to base part):
  1. Calculate neighborhood using the first element (add to cached neighborhood).
  2. next_update = prev_update / 2 — next new 1 will be right after half the number of previous iteration number (binary arithmetic).
  3. prev_update = next_update — reset value.
  4. nb_cache = *currently computed neighborhood*.
  5. nb_cache_subset = *current subset*.
2. If there is only single element in subset (of iteration number is a power of 2):
  1. Calculate neighborhood using the only element.
  2. next_update = 2^*digit number - 2* — number of iterations before new digit is added to base part.
  3. prev_update = next_update.
  4. nb_cache = *currently computed neighborhood*.
  5. nb_cache_subset = *current subset*.
3. Otherwise:
  1. Remove nb_cache_subset from current subset (so find that delta).
  2. Calculate current neighborhood as nb_cache + neighborhood of delta.

1-layered cache

Is this a good idea? Yes, but only a starting point for further reasoning, but in practice, this caching scheme will give an increase only at the end, when almost everything is filled with ones (since I have not found a way to iterate over optimal subsets, it means iterating incrementally).

Let's go back to the beginning. We discussed that rarely changing parts need to be cached. For this part, we took the sequence of closing ones. It rarely changes, but note that this part is variable, that is, you need to track its size. Now we will make base part fixed, that is, we will cache a certain suffix of the set.

Which will give a greater increase — caching of closing ones or MSB suffix? Let's count on the same set of 4 elements. For the caching scheme of the leading 1 we have the following computation scheme (the second column shows the number of processed nodes, and an asterisk marks the cache update locations):

In total, 22 elements need to be processed — two more than the taboo-bit scheme.

With the MSB suffix caching scheme, you first need to answer the question — what is its size? If we take a little, we will perform computations of variable part a lot, on the contrary, if we take too much, we will calculate this MSB often. Basically, you can calculate everything, because it's the same binary math. But for clarity, let's take the MSB equal to 2:

There are already 20 elements here — the same number as in the MySQL approach, but less than the closing ones approach.

Here, every time I updated the cache - computed the neighbors completely. You might have noticed that when calculating the cached part for the neighbors, we could use the same optimization with the last bit — add this last element to the cached neighbors. This optimization will allow us to achieve only 16 iterations, which is much more efficient.
Back then I missed this moment, but it was for the best — you will soon find out why.

The scheme with caching of the fixed part of the MSB proved to be better, and besides, it is configurable (the parameter is the size of the cached part). As a result, we choose a caching scheme with MSB suffix. Next, I will call this immutable part (which we use as the starting value for calculating neighbors) - base. The algorithm for working with it is quite simple: every $2^{len(64 - MSB)}$ iterations we save this basic part to the cache, and then just use it as a starting point when calculating neighbors.

2-layered cache

Wait, we're working with sets, and any set can be created from the previous one by adding single element! For example, the set 011010 can be constructed from any 001010, 010010 or 011000. But it also means that you can create the current set by simply adding the outermost element from the beginning. The same initial example with the taboo bit is a special case when we added the first element.

Let's draw a graph of 4 element set and see how we can create the current set from the previous one:

0000 <+  <+  <+
   ^  |   |   |
0001  |   |   |
      |   |   |
0010 -+   |   |
   ^      |   |
0011      |   |
          |   |
0100 <+  -+   |
   ^  |       |
0101  |       |
      |       |
0110 -+       |
   ^          |
0111          |
              |
1000 <+  <+  -+
   ^  |   |
1001  |   |
      |   |
1010 -+   |
   ^      |
1011      |
          |
1100 <+  -+
   ^  |
1101  |
      |
1110 -+
   ^
1111

Do you see this pattern? We take the elements in the cell under the index less than ours by some power of two and use it as a base to create the current set by adding the current outermost element. What is this power of two? You can see from the same diagram that the number of current leading zeros (or it can be represented as number of first element), that is, the set of neighbors that can be used to create the current one, is located $2^{zeros}$ steps back, where $zeros$ is the number of current leading zeros of the iteration number.

This is a dynamic programming table! To calculate the current set, we use the result of the previous calculation. Wait! Doesn't this mean that to calculate the neighbors for each of the $2^i$ subset, we will need to process exactly $2^i$ nodes? Yes, it means! Thus, our entire set can be divided into 2 parts: the base part, where we have cached the rarely changing upper part, and the table part, which is calculated using our dynamic programming table. There is no question about the size of each part — the table part takes what is left: $64 - l e n (MSB)$ (or vice versa). As a result, we have the following algorithm:

If iteration number (number representation of subset bit mask) is divided by $2^{table size}$ , then compute neighborhood - this is new base part begins.
Otherwise:
1. Take lower part of iteration number (i.e. using bit mask)
2. Calculate number of zeros in subset and get delta: $delta = 2^{zeros}$
3. Take parent neighborhood (starting point for computation): $t ab l e [i t er a t i o n - d e lt a]$
4. Compute neighborhood using first element
5. Save computed neighborhood to table

A practical question arises: how much memory to allocate for table? An 8-byte number is used to store the set (bitmapword == uint64), so the size of each set is fixed. This means that in my case it takes $8* 2^i = 2^{i+3}$ bytes to store a table with $i$ elements. Now we can make rough estimates.

Table size	Memory consumption	Total	Optimized	Saved
2	32 b	4	3	1
3	64 b	12	7	5
4	128 b	32	15	17
5	256 b	80	31	49
6	512 b	192	63	129
7	1 Kb	448	127	321
8	2 Kb	1024	255	769
9	4 Kb	2304	511	1793
10	8 Kb	5120	1023	4097
11	16 Kb	11264	2047	9217
12	32 Kb	24576	4095	20481

Legend:

Table size — size of suffix we are caching.
Memory consumption — amount of memory required to allocate table ( $2^{table\ size + 3}$ ).
Total — total number of all elements across all subsets ( $sizek\sum_{k = 1}^{table\ size}k C_{table\ size}^{k}$ ).
Optimized — number of elements we have to process in table version, the same as number of iterations but without first (empty) set ( $2^{table\ size} - 1$ ).
Saved — difference between "Total" and "Optimized".

Which table size to use can be calculated dynamically or simply choose the optimal value for your load heuristically (constant set in configuration). To make it easier to think further, I will choose a table size of 10 elements.

I was wondering — what kind of gain does an increase in the table give? For example, how many iterations can we save if we use tbl + 1 instead of a table with tbl elements. To begin with, here is the formula for the total number of iterations. Let's imagine that the number of our neighbors (i.e., the size of the set) is max (for current implementation it is 64, but this is generalization), and the size of the table is tbl. Then, the number of iterations required to process all subsets of neighbors is:

\sum^{k = 0}{max - tbl}C{max - tbl}^{k}(2^{tbl} - 1 + k)

That is, for each new base there are $k$ iterations to calculate its neighbors, and then another $2^{tbl}$ iterations for table. We do this for each subset ( $∑max−tblk\sum^{k}_{max - tbl}$ ). Now we can calculate the difference between the number of iterations for the current table and the one increased by 1.

\sum_{k}^{max - tbl}C_{max - tbl}^{k}(2^{tbl} - 1 + k) - \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl + 1} - 1 + k) = \newline \sum_{k}^{max - tbl - 1}C_{max - tbl}^{k}(2^{tbl} - 1 + k) - \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl + 1} - 1 + k) + C_{max - tbl}^{max - tbl}(2^{tbl} - 1 + max - tbl) = \newline \sum_{k}^{max - tbl - 1}(C_{max - tbl - 1}^{k} + C_{max - tbl - 1}^{k - 1})(2^{tbl} - 1 + k) - \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl + 1} - 1 + k) + 2^{tbl} - 1 + max - tbl = \newline \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl} - 1 + k) + \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2^{tbl} - 1 + k) - \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl + 1} - 1 + k) + 2^{tbl} - 1 + max - tbl = \newline \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}(2^{tbl} - 1 + k - 2^{tbl + 1} + 1 - k) + \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2^{tbl} - 1 + k) + 2^{tbl} - 1 + max - tbl = \newline -2^{tbl}\sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k} + \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2 ^{tbl} - 1 + k) + 2^{tbl} - 1 + max - tbl = \newline 2^{tbl}(\sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1} - \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k}) + \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2^{tbl} - 1 + k) + 2^{tbl} + max - tbl

If we expand the sums under the brackets in the first term, we get a sum of the following type: $C^0 - C^1 + C^1 - C^2 + C^2 - ...$ . It is easy to see that the terms destroy each other, and we get $C^0 - C^{max - tbl - 1} = 0$ — the first term is zero. Then the final expression is:

\sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2^{tbl} - 1 + k) + 2^{tbl} - 1 + max - tbl = \newline \sum_{k}^{max - tbl - 1}C_{max - tbl - 1}^{k - 1}(2^{tbl} - 1 + k) = \newline \sum_{k}^{max - tbl}C_{max - tbl - 1}^{k}(2^{tbl} + k)

Considering that $ma x > t b l$ (the formula assumes that we increase $t b l$ by 1, that is, this is the previous value, and it makes no sense to increase the size of the table beyond the size of the set), we see that this expression is non-negative, since each term of this sum is non-negative.

3-layered cache

So, we came up with the idea of storing a table of cached neighborhood. It's not bad, but it's sad that there are only fixed number of nodes in the cache. For complex queries, we will have to recalculate the base. Yes, we can make the table size configurable, but in any case, from some point on, the table size may become impractically large, i.e., starting with 15 elements, a 256 Kb table will be required. In the worst case, after several similar recursive calls (for example, the same EnumerateCsgRecursive), the memory allocated only for tables may amount to more than a megabyte. Is there any other way to optimize? Yes.

Let's go back to the beginning. The whole idea of caching in MySQL was based on calculating the neighbors by the first node of the current set, but when the moment came to save the neighbors for further calculations, they did not save the neighbors if this first taboo bit was set. Why? But because this is the final station! Neighbors created in such set will no longer be used by anyone when iterating incrementally. It doesn't take long to go after the proof — look at the previous scheme and you'll see that the neighbors calculated in odd iterations are not used by anyone. That is, we can safely avoid saving neighbors of odd iterations. How much does this optimization save us? Exactly half: half of the sets are even, and the other half are odd. The code, of course, will have to be slightly modified, it is necessary to take into account the indexing of the new scheme: to get the previous index, you need to take not $2^{zeros}$ , but $2^{zeros - 1}$ elements back.

Wait, but if we cut off the first bits, there will be another part with a similar pattern. What if you optimize it that way too, and how many times can you repeat it that way? I won't waste much time on these thoughts, but I'll say right away that I was able to apply a similar prefix compression for four elements, while only needing two additional variables to calculate the current neighbors. Thus, we come to a 3-layered caching scheme: base, table, hot (initially I called them well-done, medium and rare). The third part, hot, can be called a compressed prefix.

The algorithm now depends even more on the iteration number: depending on its value, we work with the base, table, or hot part.

First, let's look at the order of processing the hot part. It consists of 4 elements, and the main thing is that the pattern repeats itself:

0   0000 <+  <+  <+    quad leader
       ^  |   |   |
1   0001  |   |   |
          |   |   |
2   0010 -+   |   |
       ^      |   |
3   0011      |   |
              |   |
4   0100 <+  -+   |
       ^  |       |
5   0101  |       |
          |       |
6   0110 -+       |
       ^          |
7   0111          |
                  |
8   1000 <+  <+  -+    quad leader
       ^  |   |
9   1001  |   |
          |   |
10  1010 -+   |
       ^      |
11  1011      |
              |
12  1100 <+  -+
       ^  |
13  1101  |
          |
14  1110 -+
       ^
15  1111

We divide all these 16 elements (total number of possible subsets for 4 elements) in half into 2 parts, each of which has its own leader, called the quad leader. In fact, these are the cached neighbors for a set in which only the last bit is set. We calculate it 2 times: at iterations 0 and 8. Next, we also use optimization for odd iterations — for them, we specifically save the neighbors of even iterations at each iteration and simply use the ready-made value at the next (already odd) iteration (we don't need to save anything for odd ones).

As a result, we are left with iterations: 2, 4, 6, 10, 12, 14. Here we can note that for 2, 6, 10, 14, we just need to take the neighbors of the previous even iteration — we save it for odd iterations anyway. But 4 and 12 require special processing: we need to take the quad leader as a starting point, but we also save it (the second required variable). As a result, we store only two calculated values of the neighbors: the previous even iteration and the quad leader.

Moving on to the table part. The changes primarily affected the calculation of the table index. Now, for the parent neighborhood, you need to subtract 4 (the size of the hot part) from the number of leading zeros: $2^{zeros - 4}$ . It is worth noting that when a new table part begins, a new hot part also begins, so each time after calculating the neighbors and saving this value to the table, we should clear the state of the hot part - assign a new quad-leader with the current neighbor value.

There are almost no changes with the base part. First, as can be understood from the previous steps, when starting a new base part, we need to reset the state of the table part (the calculation of the table begins anew), as well as the hot part (set the quad leader to the current calculated value of the neighbors). But that's not all: why don't we use the same trick with odd iterations? And it's true: if the first bit of the current iteration number of the base part is 1, then we can simply recompute the neighbors, just as we did before.

The last question is: how to decide which action to perform? Use the subset prefix here. It is easy to see that:

every $2^{table size}$ iterations, the base part should be updated (which in terms of binary numbers means that the first $i$ bits are 0);
every $2^4 = 16$ iterations, new entries should be made in the table;
every $8$ iterations, the quad leader should be updated in the hot part.

The algorithm has become much more complicated, but that is done for the sake of optimization. Now for the same set size, not $2^{i}$ bytes are required, but only $2^{i - 4}$ . For example, instead of 8Kb, only 0.5Kb is now required whereas still all 10 elements are cached.

And when this idea settled in my head and I started writing code with all my might, it suddenly dawned on me...

Perfect cache

I looked at the graph again, wrote it for five elements, and noticed something that was in plain sight all the time, but I didn't notice. Here is this diagram, on the right of which is the number of accesses to the elements (I did not write for odd ones):

00000 <+  <+  <+  <+    5
    ^  |   |   |   |  
00001  |   |   |   |
       |   |   |   |
00010 -+   |   |   |    1
    ^      |   |   |
00011      |   |   |
           |   |   |
00100 <+  -+   |   |    2
    ^  |       |   |
00101  |       |   |
       |       |   |
00110 -+       |   |    1
    ^          |   |
00111          |   |
               |   |
01000 <+  <+  -+   |    3
    ^  |   |       |
01001  |   |       |
       |   |       |
01010 -+   |       |    1
    ^      |       |
01011      |       |
           |       |
01100 <+  -+       |    2
    ^  |           |
01101  |           |
       |           |
01110 -+           |    1
    ^              |
11111              |
                   |
10000 <+  <+  <+  -+    4  
    ^  |   |   |
10001  |   |   |
       |   |   |
10010 -+   |   |        1
    ^      |   |
10011      |   |
           |   |
10100 <+  -+   |        2
    ^  |       |
10101  |       |
       |       |
10110 -+       |        1
    ^          |
10111          |
               |
11000 <+  <+  -+        3
    ^  |   |
11001  |   |
       |   |
11010 -+   |            1
    ^      |
11011      |
           |
11100 <+  -+            2
    ^  |
11101  |
       |
11110 -+                1
    ^
11111

Do you see the pattern? If not yet, here's a hint — the relationship between the prefix of the iteration number and the number of hits. The number of accesses to the element is equal to the number of zeros at the beginning, and after this number of accesses, the value will not be used at all. Instead, it will be a new one, but the iteration number will have the same number of zeros at the beginning. That is, we don't need to store these values, and since our iteration is only forward (incremental), we can safely delete old elements. With this approach, the maximum size of the table is equal to the size max size of nodes. Since I represent a set as a number, I don't even need to think about it — I allocate a 64-sized array on the stack (64 * 8 = 512 bytes).

But how to use it correctly? Let's remember how we compute the neighbors: we take the parent neighborhood and calculate current one with the first element. And here's the second observation: the parent set is ours, but without the last bit, for example, for 01110 the parent will be 01100. And which cell the parent neighborhood for 01100 is stored? That's right — under the index 2, because it has 2 zeros at the beginning. The corner case is when we move to a new digit, then after deleting a bit we get an empty set, but for an empty set (nodes) we return an empty set (neighborhood), because it cannot have neighbors.

And now the algorithm itself:

Create DP-table, (dynamic) array.
Start next iteration.
Remove the first bit (element) from the iteration number and count the number of zeros.
Take the element with this index from the DP table.
Calculate the neighborhood based on the cached one, and for delta — the first element of the current subset.
Save computed neighborhood to DP-table with index of current number of zeros.

Is this correct? Yes. Here is a evidence to the contrary. The proof itself comes from the property of the subset—increment algorithm.

Algorithm:

Given current iteration iter.
Remove last bit and get number iter_parent.
Calculate number of zeros and get parent neighborhood from table nb_parent.

It is stated that nb_parent is the neighborhood of the set iter_parent. Let's assume that it is not, that is, the neighbors of iter_parent_2 are stored in that cell, which is not equal to iter_parent. Then this number can be either more or less than expected, but:

iter_parent_2 definitely can not be greater than iter_parent, since this means that it would be greater than the original iter (since the differences are in the MSB part), but we iterate in a strictly increasing way, which means that we have not yet encountered this number, and its value is not in the table.
it can't be a smaller number either, because that would mean that we missed the iter_parent: both numbers have the same number of leading zeros (according to our assumption), and since iter_parent comes after iter_parent_2 (since it is larger in numerical representation), we should have overwritten the value under the corresponding index (overwrite the neighbors of iter_parent_2), but we did not do this and thus violated the algorithm.

The only remaining option is that the neighborhood of the iter_parent is stored under this index. Given that the neighbors are defined for an empty set, we can also say that we can't get garbage either:

if the current set consists of single element, it means that we have moved to a new higher order digit, which we have not been in before. By removing this element, we get an empty set, but the neighbors are defined for it, and for this new index, which has not been seen before, the neighbors will be preserved, and then the value will be determined;
otherwise, the number of leading zeros will not exceed the number of the highest digit (otherwise we started a new digit and this is case 1), and we should have already written the neighbors for them in the table, that is, it is determined.

So we proved that this caching scheme is correct. Here is the code itself that calculates it all.:

typedef struct SubsetIteratorState
{
    /* Current subset */
    bitmapword subset;
    /* State variables for subset iteration */
    bitmapword state;
    bitmapword init;
    /* Current iteration number */
    bitmapword iteration;
    /* Neighborhood cache */
    bitmapword cached_neighborhood[64];
} SubsetIteratorState;

/* Get parent neighborhood */
static inline bitmapword
get_parent_neighborhood(DPHypContext *context, SubsetIteratorState *iter_state)
{
    int zero_count;
    bitmapword last_bit_removed;

    /* Remove first bit/element */
    last_bit_removed = bmw_difference(iter_state->iteration, bmw_lowest_bit(iter_state->iteration));
    if (last_bit_removed == 0)
    {
        /* There are no neighbors */
        return 0;
    }

    zero_count = bmw_rightmost_one_pos(last_bit_removed);
    return iter_state->cached_neighborhood[zero_count];
}

/* Calculate neighborhood for current iteration */
static bitmapword
get_neighbors_iter(DPHypContext *context, bitmapword subgroup,
                   bitmapword excluded, SubsetIteratorState *iter_state)
{
    int i;
    int idx;
    int zero_count;
    bitmapword neighbors;
    EdgeArray *complex_edges;

    excluded |= subgroup;

    iter_state->iteration++;

    idx = bmw_rightmost_one_pos(iter_state->subset);

    /* Computation basis - parent neighborhood */
    neighbors = get_parent_neighborhood(context, iter_state);

    /* Add simple neighborhood */
    neighbors |= bmw_difference(context->simple_edges[idx], excluded);

    /* Process complex edges */
    complex_edges = &context->complex_edges[idx];
    i = get_start_index(complex_edges, neighbors | excluded);
    for (; i < complex_edges->size; i++)
    {
        HyperEdge edge = complex_edges->edges[i];
        if ( bmw_is_subset(edge.left, subgroup) &&
            !bmw_overlap(edge.right, neighbors | excluded))
        {
            neighbors |= bmw_lowest_bit(edge.right);
        }
    }

    neighbors = bmw_difference(neighbors, excluded);

    /* Save current neighborhood to table */
    zero_count = bmw_rightmost_one_pos(iter_state->iteration);
    iter_state->cached_neighborhood[zero_count] = neighbors;

    return neighbors;
}

The scheme can also be slightly optimized - do not save neighborhood for odd iterations, but this is micro-optimization.

Is it possible to add more optimizations? Yes. An example of this is already in the code above — indexing.

Not exactly perfect cache

Yes, this caching strategy is good, but not perfect. Remember the MySQL caching approach — they use it even in the first EnumerateCsgRec cycle, when excluded set varies. MySQL overcomes this using heuristic — it caches excluded nodes, and then add all previously prohibited ones which could be neighbors.

Here is an example when this is not the case. There are 3 calls to EnumerateCsgRec (S is a subgraph, X is a set of excluded nodes, N is the neighbors that are currently being iterated over, i.e. N(S, X) has been calculated):

1. S = 00000001, X = 00000001, N = 00001110
2. S = 00001001, X = 00001111, N = 01110000
3. S = 01001001, X = 01111111, N = 10000000

The first two iterations yielded neighbors of three adjacent elements, and now we are in the third call: subgraph = 1001001, excluded = 1111111, neighbors = 10000000. In the first (and only cycle), we found that 11001001 has a plan, so we need to find neighbors for this set. Following the logic of MySQL, the neighbors for it are 10110110, since you need to add all the previous neighbors.

Where could there be a problem here? Look at the second call: where did the neighbors 1110000 come from? We got them from 0000100, but it was not in our **final* subgraph*, which means that one of the hyperedges could contain 01000000, which should be excluded (contained in the final subgraph).

It is not difficult to guess that after this, the number of nodes (and therefore possible csg/cmp pairs) that should be considered will increase, which means that the number of "junk" solutions that either will not give a useful answer or will be considered several times will also increase. There is certainly a connection between them, since the past neighbors are obtained from current nodes.

It is difficult to say whether it is bad or good for MySQL. But for PostgreSQL, at least at this stage of the extension's life, we can say that it is bad. The reason is the choice of the plan creation function — make_join_rel. Calling this function is very expensive and takes up almost all the time (i.e. if you built flame-graph for planner). If we use the MySQL approach in this part, then as a result, quite a lot of unnecessary CSG/CMP pairs will be created, for which we will have to create a plan. Most likely, we will waste time and resources on this, because even if there are no predicates between the relations, we can create a CROSS JOIN. In short, in the current cost model, it is much more profitable to spend an extra call to the neighbor finding function (get_neighbors) than to create a plan (make_join_rel). But that's not all.

Note the fundamental difference in the caching approach. In the MySQL approach, they can quite rightly use their cache and use it if necessary, since you just need to check the subset. Maybe it's not as optimal, but it works even in the case of conditional execution. But the "perfect" cache is another matter, it requires us to constantly maintain it, that is, we are required to compute the neighbors at each iteration to maintain DP-table intact so that further calculations give the correct result.

It's hard to say which is better.:

In some scenarios, it makes sense to use an "perfect" cache (and adapt caching from MySQL):
- we already have a plan in place for most of the subsets;
- no further recursive calls are expected (and there will be no combinatorial explosion)
In other scenarios, there are no such plans at all, so there is no need to compute neighbors, you can only conditionally calculate them.

Even so, taking the first approach, we should evaluate the consequences, since adding a few more nodes to the neighborhood will increase further costs for other iterations. This can almost completely negate the gains you're making right now: don't forget that each additional node increases the number of subset iterations by 2 times, and this additional node will also add new nodes to future neighbors! From the example above, we added two nodes to the neighbors, which means that there will be four times as many iterations, and for each one we will need to find more neighbors, call other functions, and so on. And how many such "indirect" neighbors will accumulate for an even greater number of recursive calls is hard to imagine.

Hyperedge indexing

Earlier I have mentioned that complex hyperedges are sorted, to get rid of duplicates. But there is another benefit. If we look at some parts of DPhyp, and specifically at the places where we need to traverse hyperedges — computing neighborhood and determining the connection (edges) between two hypernodes — we can see a similar pattern: there are moving parts, and there are permanent ones:

when searching for neighbors, the set of excluded nodes remains unchanged (or only increases).
when determining the connection between hypernodes, both hypernodes in hyperedge are fixed.

Let's try to use this knowledge somehow, and first we'll learn how to account for excluded nodes. Analysis of DPhyp makes it clear that the set of excluded nodes has the same structure: leading ones, and then sparse elements, for example, 010110011111 — it has 5 leading ones.

It's no coincidence, the algorithm works this way: we should not look at nodes that have not yet been processed, so each time we go through the edges, we check that no part intersects with these excluded ones (such constant part is determined in solve). The set of excluded nodes during iteration can only increase, but not decrease, which means that we can know in advance which nodes will definitely not satisfy the condition, that is, they will intersect with these leading zeros.

What we can do is take all the hyperedges and sort them depending on the right hypernode, and use the number of leading zeros as comparator. Then, during iteration, we calculate the length of the sequence of leading ones in the set (hypernode we are checking) of excluded ones and set the loop start index so that the first element of the right hypernode of the first hyperedge exactly exceeds the last element of the sequence of ones.

I'll show you an example. We have several hyperedges sorted by the number of leading zeros. I wrote indexes on the right for convenience (the left part of the hyperedge is not important, only the right one, so xxxxx is a placeholder):

[
    xxxxx - 00101    0
    xxxxx - 00111    1
    xxxxx - 00100    2
    xxxxx - 00100    3
    xxxxx - 01100    4
    xxxxx - 10100    5
    xxxxx - 11100    6
    xxxxx - 01000    7
]

Now it's easy to figure out which index we should start iterating from, depending on how many excluded nodes we have in front of us:

`excluded`	start index
`00100`	0
`00001`	2
`11101`	2
`10011`	2
`00111`	7
`01111`	8

A few points:

We can only be sure of the size of the leading ones - the rest is a black box for us. For example, because of this, in the third example, we start the iteration from 2, although it is clear that the rest is completely excluded.
To generalize the code when there are no suitable hyperedges, we can return the length of the array (a large number).

To understand the benefits of this optimization, remember that all edges in the graph are bidirectional, that is, for each hyperedge we create two pairs with swapped left and right sides. It may turn out that a very large number of tables refer to the same node (for example, this is a table of facts, and we have 100+ dimensions), and this table itself has the largest index, that is, excluded will include almost all tables. In this case, we will have to unsuccessfully go through all the complex edges, knowing that this will not give any result.

Well, how are we going to get the start index? The first thing that comes to mind when someone says "sorted" is binary search - just perform binary search using given hypernode (it's set) as key. But don't rush it. Let's recall that our space of "keys" (the number of leading zeros/ones) is discrete. It starts from zero and can only increment (in my case, there is a limit of 64). And what fits the description of such a structure? Array! This array will store hyperedge at index i, if it's right hypernode constans at least i leading zeros.

What about the gaps? In the example, 00111 is followed by 00100, without any 00010. We fill in these gaps with the previous value (index), that is, if for a certain length of i I do not know which index we should start the iteration from, then we need to take the previous index - index that was used for i - 1. We will take the index 0 as the base, that is, if there is no such sequence of excluded nodes, then its value will be 0, since in this case we must iterate over all hyperedges.

The cost of using such an index is only equal to calculating the number of leading units in the set of excluded nodes. But this can be optimized with a simple bit trick — we add 1 and get a sequence of 0 of the same length, but ending in 1, and then calculate the position of this "1". You can get this value using a special instruction, for example, POPCNT (it is used in PostgreSQL). So, time complexity for this index is O(1).

For the edges from the example, we can build such an index (the index of the array of edges on the right):

The size of this index depends only on the maximum number of leading 0 edges in the entire array. For example, you can see that I could create an array of only four elements, and then always return 8 (as the size of the array).

Of course, there is a problem with sparse sets, i.e. when right hypernode is {1, 1000}. Such arrays waste too much memory. We can fix this by using sparse arrays, but I don't think that this is a very big problem for now.

We have learned how to quickly cut off unnecessary edges when searching for neighbors. But we also use edges to determine the connectivity of two hypernodes. Is it possible to use this index here? Yes, we can. Two hypernodes are connected when there is a hyperedge, the left part of which is a subset of the left hypernode, and the right part is the subset of right one. The hypernodes for which we must find connectivity do not change during iterations, just like the excluded set. And now it should be noted that the right part of the hyperedge will definitely not be a subset if there are elements in this part whose index is less than the smallest in the hypernode on the right. Example: the right side of the hyperedge is 001010 and never be a subset of the hypernode 001100, since there is an element with index 2 in the edge. That is, the semantics here are practically the same as in the case of an excluded set — we must exclude all edges that have elements smaller than the smallest element of the right hypernode.

The calculation of the starting index is in the get_start_index function. For convenience, it accepts not a ready-made node index (minimal) as input, but a set of excluded nodes. This function is also used to determine the connectivity of two hypernodes: you just need to subtract "1" from the set representing the right hypernode before passing the argument, then the sequence of "0" will become a sequence of "1" back, which is the same thing according to the semantics.

static int
get_start_index(EdgeArray *edges, bitmapword excluded)
{
    int index;
    int lowest_bit;

    lowest_bit = bmw_rightmost_one_pos(excluded + 1);

    if (edges->start_idx_size <= lowest_bit)
        return edges->size;

    index = (int)edges->start_idx[lowest_bit];
    return index;
}

Query complexity

So, PostgreSQL uses 2 algorithms: DPsize and GEQO, and the latter is used if the table query has more than the value of the geqo_threshold parameter. But why exactly the number of tables? The fact is that the complexity of DPsize is determined by the number of tables — we will certainly consider all possible combinations. But with DPhyp, everything is different, its complexity depends on the shape of query graph. The original paper compares the performance of algorithms on some types of queries (chain, cliques, etc...), but they do not provide a direct answer on how to determine the complexity of a query (or maybe I overlooked it). This answer is given in another paper — "Adaptive Optimization of Large Join Queries".

The authors of this paper propose a meta-algorithm that, by combining several different JOIN algorithms, allows you to build query plans for several thousand tables. For simple queries, the authors suggest using DPhyp, but what is a simple query? For example, if there are 100 tables in a query, this does not mean that DPhyp cannot handle it. If the query graph is a simple chain, for example (all predicates are in the form Ti.x OP T(i + 1).x) then it's not difficult to find a plan for it, but if it's a clique (each joins with each other), then even 15 tables is too much. For DPhyp, complexity should be determined not in the number of tables, but in the complexity of the query graph — the number of connected subgraphs. A value of 10000 connected subgraphs is the limit of query efficiency, which corresponds to about 14 tables in clique.

The same article not only suggests an idea, but also a function for calculating the number of connected subgraphs - countCC. When I looked at her, I realized: it fits perfectly fits the caching scheme described above. Without further interruptions, the ready code:

static uint64
count_cc_recursive(DPHypContext *context, bitmapword subgraph, bitmapword excluded,
                   uint64 count, uint64 max, bitmapword base_neighborhood)
{
    SubsetIteratorState subset_iter;
    subset_iterator_init(&subset_iter, base_neighborhood);
    while (subset_iterator_next(&subset_iter))
    {
        bitmapword set;
        bitmapword excluded_ext;
        bitmapword neighborhood;

        count++;
        if (count > max)
            break;

        excluded_ext = excluded | base_neighborhood;
        set = subgraph | subset_iter.subset;
        neighborhood = get_neighbors_iter(context, set, excluded_ext, &subset_iter);
        count = count_cc_recursive(context, set, excluded_ext, count, max, neighborhood);
    }

    return count;
}

static uint64
count_cc(DPHypContext *context, uint64 max)
{
    int64 count = 0;
    int rels_count;

    rels_count = list_length(context->initial_rels);
    for (size_t i = 0; i < rels_count; i++)
    {
        bitmapword excluded;
        bitmapword neighborhood;

        count++;
        if (count > max)
            break;

        excluded = bmw_make_b_v(i);
        neighborhood = get_neighbors_base(context, i, excluded);
        count = count_cc_recursive(context, bmw_make_singleton(i), excluded,
                                   count, max, neighborhood);
    }

    return count;
}

I have kept the names of the functions the same as in the article, but adapted the signature to support efficient iteration across neighbors.

Bonus: The number of connected subgraphs is the size of the resulting DP table. Now this value is used for its preliminary hash-table allocation.

Testing

Let's check everything first on some simple query.:

EXPLAIN ANALYZE
SELECT * 
FROM t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13, t14
WHERE 
    t1.x + t2.x + t3.x + t4.x + t5.x + t6.x + t7.x > t8.x + t9.x + t10.x + t11.x + t12.x + t13.x + t14.x;

These are 14 tables connected by a single hyperline: {t1, t2, t3, t4, t5, t6, t7} - {t8, t9, t10, t11, t12, t13, t14}. Each table is a single—column table with three values (so that the query does not run for a long time). For DPsize, the result is as follows:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56) (actual time=1.672..1330.944 rows=2083371 loops=1)
   Join Filter: (((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) + t7.x) > ((((((t8.x + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   Rows Removed by Join Filter: 2699598
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.057..0.612 rows=2187 loops=1)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.042..0.128 rows=81 loops=1)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.029..0.061 rows=9 loops=1)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4) (actual time=0.018..0.028 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.003..0.008 rows=3 loops=3)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.005 rows=9 loops=9)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.025 rows=9 loops=1)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.010 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.004 rows=3 loops=3)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.006 rows=3 loops=1)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.001..0.002 rows=27 loops=81)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.014..0.037 rows=27 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.008..0.022 rows=9 loops=1)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.008 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.004 rows=3 loops=3)
                                 ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.007 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=9)
                           ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28) (actual time=0.000..0.078 rows=2187 loops=2187)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.039..0.405 rows=2187 loops=1)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.021..0.043 rows=81 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.010..0.014 rows=9 loops=1)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.002..0.002 rows=3 loops=3)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.002 rows=9 loops=9)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.009..0.013 rows=9 loops=1)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.001 rows=27 loops=81)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.016..0.026 rows=27 loops=1)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.010..0.014 rows=9 loops=1)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4) (actual time=0.005..0.006 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                       ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=9)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.005 rows=3 loops=1)
 Planning Time: 3069.835 ms
 Execution Time: 1371.090 ms
(44 rows)

It took 3 seconds for planner, although it took less than 1.5 seconds to complete. What will DPhyp give us?:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56) (actual time=1.612..1325.670 rows=2083371 loops=1)
   Join Filter: (((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) + t7.x) > ((((((t8.x + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   Rows Removed by Join Filter: 2699598
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.039..0.551 rows=2187 loops=1)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.029..0.131 rows=81 loops=1)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.021..0.051 rows=9 loops=1)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4) (actual time=0.015..0.023 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.006 rows=3 loops=3)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.006 rows=9 loops=9)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.034 rows=9 loops=1)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.012 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.005 rows=3 loops=3)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.009 rows=3 loops=1)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.002 rows=27 loops=81)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.009..0.032 rows=27 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.020 rows=9 loops=1)
                           ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.008 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.003 rows=3 loops=3)
                                 ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.006 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.000..0.001 rows=3 loops=9)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.003 rows=3 loops=1)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28) (actual time=0.000..0.078 rows=2187 loops=2187)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28) (actual time=0.025..0.397 rows=2187 loops=1)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16) (actual time=0.013..0.037 rows=81 loops=1)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.012 rows=9 loops=1)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.005 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.002 rows=3 loops=3)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8) (actual time=0.001..0.002 rows=9 loops=9)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.006..0.009 rows=9 loops=1)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=3)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4) (actual time=0.002..0.003 rows=3 loops=1)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12) (actual time=0.000..0.001 rows=27 loops=81)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12) (actual time=0.011..0.021 rows=27 loops=1)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8) (actual time=0.007..0.011 rows=9 loops=1)
                                 ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4) (actual time=0.004..0.004 rows=3 loops=1)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.001..0.001 rows=3 loops=3)
                                       ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.003 rows=3 loops=1)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4) (actual time=0.000..0.001 rows=3 loops=9)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4) (actual time=0.003..0.004 rows=3 loops=1)
 Planning Time: 4.706 ms
 Execution Time: 1365.543 ms
(44 rows)

4 milliseconds! At the same time, the plans are identical — an increase in productivity of almost 600 times!

But this is just a small query, let's take something more serious - JOB (Join Order Benchmark) presented in "How Good Are Query Optimizers, Really?". It was used to compare planners of several databases, including PostgreSQL. The benchmark can be found in this repository.

In the paper, authors compared planner estimations, not planning time, so simple queries were used — these are INNER equi-JOINS (i.e., the JOIN conditions are only equality). A wide variety of loads should be used to evaluate real performance, including all kinds of complex outer joins, but for now this is good enough.

How the testing was performed:

the time was measured using a simple extension that measured the execution time of join_search_hook.
after feeding the database, the final size is slightly more than 8GB (IMDB dataset).

There were 113 queries in total, but actually there are 33 queries - all the others are variations with different constants. For the tests, each query was run 10 times and the average execution time was calculated, and then, in order not to "make noise", the results of the same query classes (with different constants) were grouped and the average value was calculated.

Finally we got the following table:

Query class	Time, DPsize	Time, DPhyp	Cost, DPsize	Cost, DPhyp
1	0.00	0.00	20063.63..20063.64	20047.21..20047.22
2	0.00	0.00	3917.21..3917.22	3865.78..3865.79
3	0.00	0.00	16893.51..16893.52	16893.07..16893.08
4	0.00	0.00	16537.03..16537.04	16532.75..16532.76
5	0.00	0.00	55136.70..55136.71	55110.84..55110.85
6	0.00	0.00	9136.23..9136.24	8601.80..8601.81
7	1.30	2.00	26596.24..26596.25	25281.84..25281.85
8	0.25	0.85	237500.71..237500.73	215342.88..215342.89
9	1.75	1.95	121709.02..121709.03	118041.88..118041.89
10	0.23	0.30	218646.80..218646.81	216146.76..216146.77
11	1.25	2.03	4264.53..4264.54	4263.81..4263.82
12	1.47	2.27	18062.07..18062.08	17923.86..17923.87
13	3.28	3.73	19880.57..19880.58	19561.58..19561.60
14	1.20	1.30	6675.30..6675.31	6675.12..6675.13
15	4.70	6.03	140612.22..140612.23	105280.24..105280.26
16	2.03	2.30	4373.61..4373.62	3928.40..3928.41
17	0.72	1.10	4526.53..4526.54	4073.57..4073.58
18	0.50	1.03	36882.96..36882.97	33151.67..33151.68
19	8.35	9.23	141225.66..141225.67	131527.60..131527.61
20	4.60	6.23	12982.67..12982.68	12976.69..12976.70
21	4.57	5.90	3833.12..3833.13	3833.12..3833.13
22	17.55	21.00	7532.63..7532.64	7532.28..7532.29
23	16.07	20.53	43981.68..43981.69	42108.50..42108.51
24	47.90	56.35	6665.46..6665.47	6580.84..6580.85
25	3.73	5.30	8502.14..8502.15	8495.15..8495.16
26	29.83	41.83	9324.37..9324.38	9237.43..9237.44
27	42.40	69.67	1053.48..1053.49	1290.69..1290.70
28	137.20	208.17	7534.70..7534.71	7534.67..7534.68
29	949.77	936.80	4013.73..4013.74	4013.73..4013.74
30	38.67	61.60	9323.59..9323.60	9323.59..9323.60
31	20.83	34.00	9584.13..9584.14	9575.61..9575.62
32	0.00	0.00	3880.96..3880.97	3838.37..3838.38
33	165.90	216.83	3029.91..3029.92	2995.14..2995.15

When I ran through the table a bit, I couldn't believe. Let's look at it as a bar plot.

DPhyp overwhelmingly creates a plan better than DPsize. Yes, the time to complete it is a little bit longer, but the plan is better, which means that we win in the long run!

However, something is clearly wrong here. At least, we only managed the join order of the relations, but we didn't create the plans ourselves - it's up to PostgreSQL. So does vanilla planner misbehave? Let's look at the output manually and see what happened. We will examine 6f query. That's what DPsize gives us:

                                                                        QUERY PLAN                                           
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=15215.38..15215.39 rows=1 width=96)
   ->  Nested Loop  (cost=8.10..15175.34 rows=5339 width=48)
         ->  Nested Loop  (cost=7.67..12744.50 rows=5339 width=37)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19)
               Index Cond: (id = ci.person_id)
(19 rows)

And that's for DPhyp:

                                                                        QUERY PLAN                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=13720.08..13720.09 rows=1 width=96)
   ->  Nested Loop  (cost=8.10..13704.27 rows=2108 width=48)
         ->  Nested Loop  (cost=7.67..12744.50 rows=2108 width=37)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19)
               Index Cond: (id = ci.person_id)
(19 rows)

The plan is cheaper by almost 2000 units! That is, the expansion really gives you a better plan... Stop! the plans are identical, but the costs are different? The differences occur in the third node, the Nested Loop with ci.movie_id = t.id predicate: DPsize evaluates it to 5339 rows, and DPhyp evaluates it to 2108. How could this even happen? We need to find this out.

The starting point will be query tracing to discover which subplans are used to create this NL. We will have to do this manually using debugger, because there are no special settings for this (there is a macro OPTIMIZER_DEBUG, but it will output ready-made relations, but we have to follow order of which relations used to create final, so it is not suitable).

For DPsize, the order will be as follows:

{1, 2, 3} {5}
{1, 3, 5} {2}
{2, 3, 5} {1}
{1, 5} {2, 3}

For DPhyp — like this:

{1} {2, 3, 5}
{1, 5} {2, 3}
{1, 3, 5} {2}
{1, 2, 3} {5}

Numbers are IDs of relations:

1 - cast_info ci
2 - keyword k
3 - movie_keyword mk
5 - title t

Despite the difference in order, the same pairs are processed, meaning we don't lose anything. But why the different cost then? Let's look at the other side — what are these numbers 2108 and 5339 in the query plans, where do they come from? If you look in the code, this is the rows field in the Path structure. How is this member initialized? In the code, we will see that the rows of the Path structure is initialized by the rows field of RelOptInfo, and this is done in all types of plan nodes (examples are all JOIN nodes):

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L3375 */
void
final_cost_nestloop(PlannerInfo *root, NestPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L3873 */
void
final_cost_mergejoin(PlannerInfo *root, MergePath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

/* https://github.com/postgres/postgres/blob/144ad723a4484927266a316d1c9550d56745ff67/src/backend/optimizer/path/costsize.c#L4305 */
void
final_cost_hashjoin(PlannerInfo *root, HashPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
{
    /* ... */
    if (path->jpath.path.param_info)
        path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
    else
        path->jpath.path.rows = path->jpath.path.parent->rows;
    /* ... */
}

Okay, then where does rows come from in RelOptInfo? If we search through the code, then for JOIN we will find the only place of its initialization — set_joinrel_size_estimates. It is called in two places: build_join_rel to create a new JOIN RelOptInfo and build_child_join_rel — the same thing, but for inherited tables (i.e. partitions fall here). In our case, there are no partitions, so build_join_rel is used. So where does it estimate the number of rows? The answer is that when creating the structure for the first time set_joinrel_size_estimates is called, which sets this field, evaluating by the current pair of the connected relations. In other words, the estimate of the returned number of rows occurs once, and then we use this estimate in all cases. It sounds quite logical, since predicates are also fixed for each set of relations, so the number of rows returned by this set of relations should not depend on the physical implementation of the operators.

But then why does the estimate vary so much? To do this, we will do the tracking again, but this time we will track all the invocations and all the estimates that we make. Let's build a tree, the nodes of which will be sets of relations, and the child nodes will be those from which the parent is created. Since only the JOIN INNER is used in the query, the formula for calculating the number of tuples will be as follows: nrows = outer_rows * inner_rows * jselect:

nrows — total number of tuples;
outer_rows — number of tuples in outer (left) part;
inner_rows — number of tuples in inner (right) part;
jselec — predicates selectivity.

For DPsize, the call stack will be as follows (predicate selectivity is written under sets, edges contain the number of tuples at the output):

                     {1, 2, 3, 5}
                        3.95e-7
                    /           \
                9813           1375372
                 /                   \
            {1, 2, 3}                {5}
             7.45e-6  
            /      \ 
     164574168      8
        /            \
    {1, 3}           {2}
     1e-6
    /     \
36245584  4523930 
  /          \
{1}          {3}

The specified selectivity is trimmed in order not to take up much space, since the numbers are long, but even without this, it can be seen that 9813 * 1375372 * 3.95 e-7 = 5332. If you add the dropped digits, it will be typed to the expected number — 5339.

Now let's see what happened in DPhyp:

                 {1, 2, 3, 5}
                    3.95e-7
                  /         \   
             36245584        147
               /               \
            {1}             {2, 3, 5}
                              7.45e-6
                            /        \
                           8       2461152
                          /             \
                        {2}           {3, 5}
                                      3.95e-7
                                     /      \
                                 4523930  1375372
                                   /          \
                                 {3}          {5}

36245584 * 147 * 3.95 e-7 = 2104, with ceiling gives us 2108.

So, we found the original problem — a incorrect initial estimations. Is it really bad? In our case, yes, because if we run the query, we will get the following results:

                                                                             QUERY PLAN                                             
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=13720.08..13720.09 rows=1 width=96) (actual time=8753.807..8753.810 rows=1 loops=1)
   ->  Nested Loop  (cost=8.10..13704.27 rows=2108 width=48) (actual time=0.637..8530.663 rows=785477 loops=1)
         ->  Nested Loop  (cost=7.67..12744.50 rows=2108 width=37) (actual time=0.623..2643.045 rows=785477 loops=1)
               Join Filter: (ci.movie_id = t.id)
               ->  Nested Loop  (cost=7.23..12483.46 rows=147 width=41) (actual time=0.610..405.496 rows=14165 loops=1)
                     ->  Nested Loop  (cost=6.80..12351.21 rows=270 width=20) (actual time=0.597..140.721 rows=35548 loops=1)
                           ->  Seq Scan on keyword k  (cost=0.00..3691.40 rows=8 width=20) (actual time=0.143..37.305 rows=8 loops=1)
                                 Filter: (keyword = ANY ('{superhero,sequel,second-part,marvel-comics,based-on-comic,tv-special,fight,violence}'::text[]))
                                 Rows Removed by Filter: 134162
                           ->  Bitmap Heap Scan on movie_keyword mk  (cost=6.80..1079.43 rows=305 width=8) (actual time=0.993..12.278 rows=4444 loops=8)
                                 Recheck Cond: (k.id = keyword_id)
                                 Heap Blocks: exact=23488
                                 ->  Bitmap Index Scan on keyword_id_movie_keyword  (cost=0.00..6.72 rows=305 width=0) (actual time=0.501..0.501 rows=4444 loops=8)
                                       Index Cond: (keyword_id = k.id)
                     ->  Index Scan using title_pkey on title t  (cost=0.43..0.49 rows=1 width=21) (actual time=0.007..0.007 rows=0 loops=35548)
                           Index Cond: (id = mk.movie_id)
                           Filter: (production_year > 2000)
                           Rows Removed by Filter: 1
               ->  Index Scan using movie_id_cast_info on cast_info ci  (cost=0.44..1.33 rows=36 width=8) (actual time=0.008..0.148 rows=55 loops=14165)
                     Index Cond: (movie_id = mk.movie_id)
         ->  Index Scan using name_pkey on name n  (cost=0.43..0.46 rows=1 width=19) (actual time=0.007..0.007 rows=1 loops=785477)
               Index Cond: (id = ci.person_id)
 Planning Time: 1.419 ms
 Execution Time: 8753.873 ms
(24 rows)

In reality, that node gave 785477 tuples, and the error is (multiplicity):

DPhyp: 370;
DPsize: 150.

We made a mistake in estimating the number of tuples by more than two times, and for the worse — underestimation. But that's not all. Remember the first example, a query with a single hyperedge. It is planned very quickly, but if we change something a little bit, for example, move t7.x to the right side of the binary predicate, we will get such a plan:

-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215344.72 rows=1594323 width=56)
   Join Filter: ((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) > (((((((t7.x + t8.x) + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   ->  Nested Loop  (cost=0.00..93.00 rows=6561 width=32)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                     ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4)
         ->  Materialize  (cost=0.00..5.80 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4)
   ->  Materialize  (cost=0.00..19.94 rows=729 width=24)
         ->  Nested Loop  (cost=0.00..16.29 rows=729 width=24)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4)
 Planning Time: 9.477 ms
(42 rows)

Yes, it's a little slower — 9ms instead of 4ms, but it's still fast. Yes, it's fast, but it's not about speed anymore. See what DPsize gives you:

                                                                  QUERY PLAN                                   
-----------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..215311.78 rows=1594323 width=56)
   Join Filter: ((((((t1.x + t2.x) + t3.x) + t4.x) + t5.x) + t6.x) > (((((((t7.x + t8.x) + t9.x) + t10.x) + t11.x) + t12.x) + t13.x) + t14.x))
   ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28)
         ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
               ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                     ->  Seq Scan on t4  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t5  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)
         ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
               ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t1  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t2  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                           ->  Seq Scan on t3  (cost=0.00..1.03 rows=3 width=4)
   ->  Materialize  (cost=0.00..47.29 rows=2187 width=28)
         ->  Nested Loop  (cost=0.00..36.36 rows=2187 width=28)
               ->  Nested Loop  (cost=0.00..5.39 rows=81 width=16)
                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t11  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t12  (cost=0.00..1.03 rows=3 width=4)
                     ->  Materialize  (cost=0.00..2.23 rows=9 width=8)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t13  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t14  (cost=0.00..1.03 rows=3 width=4)
               ->  Materialize  (cost=0.00..3.69 rows=27 width=12)
                     ->  Nested Loop  (cost=0.00..3.56 rows=27 width=12)
                           ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                                 ->  Seq Scan on t8  (cost=0.00..1.03 rows=3 width=4)
                                 ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                       ->  Seq Scan on t9  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t10  (cost=0.00..1.03 rows=3 width=4)
 Planning Time: 3337.097 ms
(42 rows)

The planning time is indeed much longer, but take a closer look at the query plan. The first thing to notice is that the cost is lower. Take a look at why:

                     ->  Nested Loop  (cost=0.00..2.18 rows=9 width=8)
                           ->  Seq Scan on t6  (cost=0.00..1.03 rows=3 width=4)
                           ->  Materialize  (cost=0.00..1.04 rows=3 width=4)
                                 ->  Seq Scan on t7  (cost=0.00..1.03 rows=3 width=4)

Yes, DPsize was able to find an implicit connection between the relations, even if they were on different sides of the operands. DPhyp will not do this, since these are different sides of an edge, and according to its logic it is forbidden to do this — you cannot connect separate nodes of different hypernodes if they are on different sides of a hyperedge. From this we can conclude that DPhyp is a very good, but heuristic. Unfortunately, these are not all the problems.

3 different sources are used to create hyperedgegs, but they do not cover all the possible cases. The problem lies in the joinclauses. During operation, PostgreSQL creates all possible variants of an expression with a different set of necessary relations of the left and right sides. This allows you to consider different options for the location of the expression in the tree. The problem is that the relation IDs used there may refer not to tables, but to indexes of JOIN nodes (RangeTblEntry of type RTE_JOIN). And they are there for a reason - to "tell" the planner which relations can be used and how to reorder them. To understand, let's look at such a query (taken from the regression tests of PostgreSQL itself):

select t1.* from
  text_tbl t1
  left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)
  on (t1.f1 = b1.d1)
  left join int4_tbl i4
  on (i8.q2 = i4.f1);

The problematic predicate here is i8.q2 = i4.f1 — it stores 3 copies with a different set of relations of the left and right sides:

{3} - {8}
{3, 6} - {8}
{3, 6, 7} - {8}

3 and 8 are indexes corresponding to tables i8 and i4, respectively. But what are these 6 and 7? These are the indexes of JOINS:

-- 6
(select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)

-- 7
text_tbl t1
  left join (select *, '***'::text as d1 from int8_tbl i8b1) b1
    left join int8_tbl i8
      left join (select *, null::int as d2 from int8_tbl i8b2) b2
      on (i8.q1 = b2.q1)
    on (b2.d2 = b1.q2)
  on (t1.f1 = b1.d1)

This reflects the limitations: i8.q2 = i4.f1 does not apply to i8 itself, but to the result of the LEFT JOIN.

OK, but then why is the execution time longer? If we are not considering additional cases (discussed above), then this time should be shorter. Here's the thing.

If we take a look at the code of the vanilla planner, we can see that it is quite smart. Function join_search_one_level is responsible for processing single level of DPsize:

join_search_one_level

/* src/backend/optimizer/path/joinrels.c */
void
join_search_one_level(PlannerInfo *root, int level)
{
    List      **joinrels = root->join_rel_level;
    ListCell   *r;
    int         k;

    root->join_cur_level = level;

    /*
     * Make ZIG-ZAG plan - join table with previous level.
     */
    foreach(r, joinrels[level - 1])
    {
        RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

        if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
            has_join_restriction(root, old_rel))
        {
            int         first_rel;

            if (level == 2)
                first_rel = foreach_current_index(r) + 1;
            else
                first_rel = 0;

            make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel);
        }
        else
        {
            make_rels_by_clauseless_joins(root,
                                          old_rel,
                                          joinrels[1]);
        }
    }

    /*
     * Creation of "bushy" plans - main DPsize logic, where all possible
     * pairs of relations with several tables on both sides are considered.
     */
    for (k = 2;; k++)
    {
        int         other_level = level - k;

        foreach(r, joinrels[k])
        {
            RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
            int         first_rel;
            ListCell   *r2;

            if (k == other_level)
                first_rel = foreach_current_index(r) + 1;
            else
                first_rel = 0;

            for_each_from(r2, joinrels[other_level], first_rel)
            {
                RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);

                /* Build plan only if it makes sense */
                if (!bms_overlap(old_rel->relids, new_rel->relids))
                {
                    if (have_relevant_joinclause(root, old_rel, new_rel) ||
                        have_join_order_restriction(root, old_rel, new_rel))
                    {
                        (void) make_join_rel(root, old_rel, new_rel);
                    }
                }
            }
        }
    }

    /*
     * Build CROSS JOIN if we failed to build anything at current level
     */
    if (joinrels[level] == NIL)
    {
        foreach(r, joinrels[level - 1])
        {
            RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

            make_rels_by_clauseless_joins(root,
                                          old_rel,
                                          joinrels[1]);
        }
    }
}

Logic is the following:

First, we create left-deep/right-deep plans — we create the current level by joining 1 table to the previous level (even if there is no predicate, that is, we create a CROSS JOIN).
Then we run the main DPsize logic with consideration of all possible pairs, that create target set.
In the end, if we couldn't find anything, then we create the CROSS JOIN nodes.

The main optimization is in step 2 — we do not create extra CROSS JOINS if they are not needed. This is, in fact, an imitation of the behavior of DPhyp, since its idea is to connect relationships only if there is a connection between them:

/* Left/right parts do not intersect */
if (!bms_overlap(old_rel->relids, new_rel->relids))
{
    /* Have edge between nodes */
    if (have_relevant_joinclause(root, old_rel, new_rel) ||
        have_join_order_restriction(root, old_rel, new_rel))
    {
        (void) make_join_rel(root, old_rel, new_rel);
    }
}

We spend the remaining microseconds on operational:

Hypergraph building.
Neighbors traversing.
Hash-table maintenance.

All these extra cycles accumulate and result in an even longer execution.

Conclusions

The extension, of course, is still not ready due to performance reasons. The existing infrastructure is highly coherent with existing code base of PostgreSQL, so to implement some functionality, you have to look for hacks, or it will work ineffectively.

The question arises: is it all necessary? R&D. As I said at the beginning, the planner is an important part of the DBMS, so researches in this area may at some point turn into a significant gain (the keyword is "may"). Unfortunately, the payback on this particular investment is negative for now — in practice, this algorithm creates plans that are neither better nor faster.

Let's summarize the disadvantages:

Some possible optimizations are lost: hyperedges are created from predicates that currently cannot be completely transformed into hyperedges due to RangeTable indexes that do NOT refer to relations (main problem is for OUTER JOINS)
Disconnected subgraphs require special processing: the user must tell the extension how to act (the cj_strategy setting).
Estimations suffer due to the suboptimal order of relation pairs: the order of the processed relation pairs is important for JOINS, but now it does not correspond to what the built-in planner does.
It takes quite a long time to complete: the built-in make_join_rel is currently being used, but it takes the lion's share of the time.

There is also good news: everything is fixable. The limitations are dictated by the implementation alone, that is, they are not fundamental limitations. No one forbids us to write our own make_join_rel optimized for DPhyp. As a last resort, we can patch the core and add what we're missing. Moreover, we found at least one query that we were able to speed up hundreds of times, and this can open up a whole field of applicability, which means that the work has not been done in vain.

Links:

Extension pg_dphyp
Dynamic Programming Strikes Back — DPhyp
Adaptive Optimization of Very Large Join Queries — planning of large queries (1000+ tables)

How to handle files?

Sergey Solovev — Sat, 03 May 2025 15:21:10 +0000

Greetings!

Fault tolerance is a very important aspect of every non-startup application.
It can be described as a definition:

Fault tolerance is the ability of a system to maintain proper operation despite failures or faults in one or more of its components.

But this gives only slight overview - fault tolerance concerns many areas especially when we are talking about software engineering:

Network failures (i.e. connection halt due to power outage on intermediate router)
Dependent service unavailability (i.e. another microservice)
Hardware bugs (i.e. Pentium FDIV bug)
Storage layer corruptions (i.e. bit rot)

As a database developer I'm interested in latter - in the end all data stored in disks.

But you should know that not only disks can lead to such faults. There are other pieces that can misbehave or it's developer's mistake that he/she didn't work with these parts correctly.

I'm going to explain how this 'file write stack' (named in opposite to 'network stack') works.
Of course, main concern will be about fault tolerance.

Application

Everything starts in application's code. Usually, there is separate interface to work with files.

Each PL (programming language) has own interface. Some examples:

fwrite - C
std::fstream.write - C++
FileStream.Write - C#
FileOutputStream.Write - Java
open().write - Python
os.WriteFile - go

These all means given by PL itself: read, write, etc...
Their main advantage - platform independence: runtime (i.e. C#) or compiler (i.e. C) implements this.
But this have drawbacks. Buffering in this case - all calls to this virtual "write" function store going to be written data in special buffer to later write it all at once (make syscall to write).

Due to documentation, each of all PL above support buffering:

What about C# - class FileStream uses another class FileStreamStrategy - it handles all requests (Strategy pattern).
For example, when we are instantiating FileStream through File.Open() - BufferedFileStrategy wraps OSFileStreamStrategy.
It adds buffering layer above syscalls.

Generaly, buffering in user space is a good feature - usually it improves performance.
But programmer should be aware of additional buffers. There are 2 types of buffering I can identify:

Manual (go, Java) - create buffered file object manually
Transparent (C, C++) - buffer maintained automatically

In first case we know, that buffer should be flushed at end of write session, but in second case can you can easily shoot in your foot:

File opened in memory, but no callbacks for flushing registered or just forgot to add such code
Application closed abnormally (i.e. got SIGKILL)

All such cases ends up with all data in in-memory buffer get lost.

So, there are 2 solutions:

Always flush data after write session. The easiest case for simple application is by adding single write function that accepts batch of write buffers and calls flush function at the end.
Disable buffering at all and make writes directly.

From performance view - first case is the most attractive.

Performance comparison

I have made a small benchmark - sequential write of 64Mb data into a file.
Test matrix: old laptop with HDD and new laptop with SSD NVMe M.2.

	Direct write, s	Buffered write, s
Old	894.7	109.6
New	8.932	1.198

The result is obvious: buffered IO faster by at least 8 times.
Source code of benchmark here.

Operating system

Programming language gives good platform abstraction - programmer does not need to think about (at least, not very often) on which operating system application works.
But eventually, PL interface will be mapped to some syscalls.
These syscalls are OS dependent, but in common we have 4 main functions:

Operation	*nix	Windows
Open/Create	`open`/`creat`	`CreateFile`
Read	`pread`/`read`	`ReadFile`
Write	`pwrite`/`write`	`WriteFile`
Close	`close`	`CloseFile`

*nix means Unix-like OS: Linux, FreeBSD, OSX.
Semantics of some operations can differ, but now it is not very important - common interface/behaviour pattern the same.

There is buffering also at OS layer. It is called page buffer.
And it's even easier to shoot yourself in the foot with it.

Operations with file are perform in pages (huge sequential block of data, usually 4Kb) even if only single byte was requested.

When we read page is stored in buffer. Then we send write request that is not written to device immeately. Instead, it just marked as "dirty" and scheduled to be flushed at near future.
All such pages (clean and dirty) make up a page cache.

How it can harm us? Follow these steps:

User sends request to update info about himself. For example, it can be his password
We open file with users information - retrieve required page
Page is updated with new password (of course it will be password hash for security reasons)
Application make "write" request to OS (everything is ok)
We tell user that everything is updated

What could go wrong? Power outage!

User replaced his old password with new one in his password manager (old cryptographic password)
"dirty" page with new password (step 3) was lost because of power failure and old password still the same (on disk)

Congratulations - user lost access to his account.

Page cache is very helpfull, especially when there are many operations on same page.
But when we should make a "durable" write (that is it must be saved to disk permanently, not being just updated in memory) we must ensure data is flushed to disk.

Even here there are 2 solutions:

Special syscall to flush data to disk
Bypass page cache and always write to disk

Special syscall to flush data

This solution uses separate syscall that ensures that all our write requests were completed.

Linux

In Linux we can use:

fdatasync(fd) - checks, that data in memory and on disk are synchronized, that is performs flushing of pending ("dirty") pages.
fsync(fd) - the same as fdatasync(fd), but also updates file metadata (i.e. last access time). Usually, you don't need this and should prefer fdatasync for performance.
sync_file_range(fd, range) - checks that specific range of file is flushed to disk (according to man this is very dangerous function, so I added it here just for familiarization)
sync() - it flushes all pages to disk, but for all files, not some specified

As said earlier, fdatasync synchronizes only contents, without metadata like fsync, so it is faster.
etcd comments this out and makes explicit separation between them:

// Fsync is a wrapper around file.Sync(). Special handling is needed on darwin platform.
func Fsync(f *os.File) error {
 return f.Sync()
}

// Fdatasync is similar to fsync(), but does not flush modified metadata
// unless that metadata is needed in order to allow a subsequent data retrieval
// to be correctly handled.
func Fdatasync(f *os.File) error {
 return syscall.Fdatasync(int(f.Fd()))
}

Windows

For Windows there are functions:

_commit - flushes data from file to disk
FlushFileBuffers(fd) - causes write all buffered data to a file (I'm not a Windows developer, so do not known difference with previous one)
NtFlushBuffersFileEx(fd, params) - causes page cache flush, but it is more low-level function (marked with NTSYSCALLAPI)

P.S. NtFlushBuffersFileEx used in Postgres as a writer for crossplatform fdatasync, and for fsync it uses _commit.

// https://github.com/postgres/postgres/blob/9acae56ce0b0812f3e940cf1f87e73e8d5784e78/src/include/port/win32_port.h#L85
/* Windows doesn't have fsync() as such, use _commit() */
#define fsync(fd) _commit(fd)

// https://github.com/postgres/postgres/blob/874d817baa160ca7e68bee6ccc9fc1848c56e750/src/port/win32fdatasync.c#L23
int
fdatasync(int fd)
{
    // ...
 status = pg_NtFlushBuffersFileEx(handle,
          FLUSH_FLAGS_FILE_DATA_SYNC_ONLY,
          NULL,
          0,
          &iosb);
    // ...
}

macOS

It is also worth mentioning macOS. Althrough it is POSIX-complient, but one call to fsync is not enough - fcntl(F_FULLSYNC) call requred.
This is outlined even in documentation.

For applications that require tighter guarantees about the integrity of their data, Mac OS X provides the F_FULLFSYNC fcntl.

Again, this is handled in etcd:

// Fsync on HFS/OSX flushes the data on to the physical drive but the drive
// may not write it to the persistent media for quite sometime and it may be
// written in out-of-order sequence. Using F_FULLFSYNC ensures that the
// physical drive's buffer will also get flushed to the media.
func Fsync(f *os.File) error {
 _, err := unix.FcntlInt(f.Fd(), unix.F_FULLFSYNC, 0)
 return err
}

// Fdatasync on darwin platform invokes fcntl(F_FULLFSYNC) for actual persistence
// on physical drive media.
func Fdatasync(f *os.File) error {
 return Fsync(f)
}

Bypass OS page cache

The second solution require us to pass special flag during file opening.

Linux

Linux require passing 2 flags O_SYNC | O_DIRECT to open:

O_SYNC - every write flushed immediately to disk. Also, there is O_DSYNC - replace fsync with fdatasync
O_DIRECT - write bypasses page cache (equivalent to disabling it at all for this file)

Using O_SYNC/O_DSYNC is equivalent to calling fsync/fdatasync right after we call write/pwrite.

Also, using fcntl you can change O_DIRECT flag, but no O_SYNC.
This is specified in documentation for fcntl:

... It is not possible to change the O_DSYNC and O_SYNC flags; see BUGS, below.

Windows

In Windows we have similar flags:

FILE_FLAG_NO_BUFFERING - disables OS page buffering
FILE_FLAG_WRITE_THROUGH - all writes flushed to disk, without buffering

Documentation gives description of behaviour when both are specified:

If FILE_FLAG_WRITE_THROUGH and FILE_FLAG_NO_BUFFERING are both specified, so that system caching is not in effect, then the data is immediately flushed to disk without going through the Windows system cache. The operating system also requests a write-through of the hard disk's local hardware cache to persistent media.

And this blog article introduces comparison matrix:

		NO_BUFFERING
		Clear	Set
WRITE_THROUGH	Clear	Writes go into cache Lazily written to disk No hardware flush	Writes bypass cache Immediately written to disk No hardware flush
WRITE_THROUGH	Set	Writes go into cache Immediately written to disk Hardware flush	Writes bypass cache Immediately written to disk Hardware flush

Postgres uses this mapping between Windows/Linux flags:

Windows	Unix
FILE_FLAG_NO_BUFFERING	O_DIRECT
FILE_FLAG_WRITE_THROUGH	O_DSYNC

// https://github.com/postgres/postgres/blob/30e144287a72529c9cd9fd6b07fe96eb8a1e270e/src/port/open.c#L65
HANDLE
pgwin32_open_handle(const char *fileName, int fileFlags, bool backup_semantics)
{
    // ...
 while ((h = CreateFile(fileName,
                           // ...
         ((fileFlags & O_DIRECT) ? FILE_FLAG_NO_BUFFERING : 0) |
         ((fileFlags & O_DSYNC) ? FILE_FLAG_WRITE_THROUGH : 0),
         NULL)) == INVALID_HANDLE_VALUE)
    // ...
}

Directory sync

Linux

But that's not all. Unix way - everythin is file, even directory. Directory is a file, but read/write operations are different:

read - iterate directory entries
write - create/delete entry

Read is not very interesting for us, but write is - when we create or delete file (moving file is both operations) performed to must ensure these operations are flushed - fsync(directory_fd) is called.
This is documented as well:

Calling fsync() does not necessarily ensure that the entry in the directory containing the file has also reached disk.
For that an explicit fsync() on a file descriptor for the directory is also needed.

Windows

As for Windows - we can not do it:

Directory is not openable - we get EACCESS when try to do this
FlushFileBuffers works only with files or whole volume (all files in volume), but for the latter elevated privileges required.

Again, Postgres use *nix style - it call fsync for directories, but for Windows it has additional check:

/*
 * fsync_fname_ext -- Try to fsync a file or directory
 *
 * If ignore_perm is true, ignore errors upon trying to open unreadable
 * files. Logs other errors at a caller-specified level.
 *
 * Returns 0 if the operation succeeded, -1 otherwise.
 */
int
fsync_fname_ext(const char *fname, bool isdir, bool ignore_perm, int elevel)
{
 returncode = pg_fsync(fd);

 /*
  * Some OSes don't allow us to fsync directories at all, so we can ignore
  * those errors. Anything else needs to be logged.
  */
 if (returncode != 0 && !(isdir && (errno == EBADF || errno == EINVAL)))
 {
  // ...
  return -1;
 }

 return 0;
}

fsync errors

Even though write returned success status code, it does not mean that write was successful - recall that we use buffering, so we just updated in-memory page.

When we call fsync it can return error. It was shown in the code above.
But what we should do when we get error code from fsync?

Generally - halt immediately. If developing for specific OS - it depends. Why? Main reason, is that we no longer can be sure about consistency:

File system can be broken
File can have a hole (invalid write)
"Dirty" pages can be just marked "clean" and no longer flushed.

Latter may cause differences in file (contents) view from in-memory and disk perspectives, but we will not notice that.

Marking pages as "clean" is a part of Linux implementation - it assumes, that file system correctly completes write operation.

Postgres hackers make a brief overview of different operating system behaviour on fsync error:

Darwin/macOS - invalidate buffers
OpenBSD - invalidate buffers
NetBSD - invalidate buffers
FreeBSD - remain "dirty"
Linux (after 4.16) - marked "clean"
Windows - unknown

So, if we are developing crossplatform application - the state of buffers after we get fsync error is undefined.
But when developing for specific OS - it is defined.

fsyncgate

We can not talk about fsync errors without touching fsyncgate.

fsyncgate - is a name of a bug found in Postgres that caused data loss. More infor can be found here.
Briefly, initially developers thought fsync semntics is following:

If fsync() completed successfully, then all writes since last successful fsync() were flushed to disk.

In another words - try to call fsync until it returns a successful status code.
But as we observed earlier it is a misconception. In reality, if fsync returned error code, than all "dirty" pages will be just forgotten.
Therefore, more correct to state:

If fsync() completed successfully, then all writes since last ~~successful~~ fsync() were flushed to disk.

This was noticed in 2018 year and answer was discussed in mailing list.

That bug was fixed in 12 version (with backpatching) in this commit using next code (increase error level):

// https://github.com/postgres/postgres/blob/30e144287a72529c9cd9fd6b07fe96eb8a1e270e/src/backend/storage/file/fd.c#L3936
int
data_sync_elevel(int elevel)
{
    return data_sync_retry ? elevel : PANIC;
}

// Любая функция, например эта - https://github.com/postgres/postgres/blob/30e144287a72529c9cd9fd6b07fe96eb8a1e270e/src/backend/access/heap/rewriteheap.c#L1132
void sample_function() 
{
    // Любой вызов fsync в логике 
    if (pg_fsync(fd) != 0)
    // ereport(ERROR,
       ereport(data_sync_elevel(ERROR),
                (errcode_for_file_access(),
                 errmsg("could not fsync file \"%s\": %m", path)));
}

Page cache in databases

Disk operations - is one of the most important part of each database. So many of them implement their own page cache manager (subsystem) and does not rely on OS.

This adds some improvements:

More effective IO operations scheduling (durable write should occur after COMMIT)
More effective (potentially) page eviction algorithms
Size of page and whole cache can be adjusted

Here some examples of several databases:

DBMS	Implementation	Page eviction algorithm
Postgres	bufmgr.h, bufmgr.c	clock-sweep
SQL Server	sources N/A	LRU-2 (LRU-K)
Oracle	sources N/A	LRU, Temperature-based
MySQL (InnoDB)	buf0buf.h, buf0buf.cc	LRU

As I said, own page cache/manager can optimize database workflow and smart page eviction algorithm is not only place to optimize:

Oracle and SQL Server use flash disks as temporal page cache storage instead of flushing them to main disk (settings DB_FLASH_CACHE_FILE for Oracle and BPE (buffer pool extension) for SQL Server)
Postgres have pg_prewarm extension to "warm" page cache

I searched Linux kernel source code and found fsync implementation here

File system

Usually, we say "write to disk", but actually it is final destination. There is another layer that should be passed - file system.

Nowadays all data stored in filesystems. As for me, I do not know any system that access block devices using either LBA or CHS - you just write at some offset in a file.
So, before data is written to disk it must be processed by file system.

Today there are huge amount of different file systems, so I primarly focus on small part:

ext family
btrfs
xfs
ntfs

Choose them, as most popular in my opinion

File systems can be characterized by multiple aspects (i.e. max file name length), but now we are interested in those, who related to fault tolerance.

File system integrity

From programming perspective, file system - is a global, shared object. Everyone has access to and can to modify it.
Taking global lock during write operations seems a bad idea, so there are a couple of mechanisms different file systems use:

Journaling (ext family, ntfs, xfs) - file system maintains a log of operations and always able to replay it in case of error
COW, Copy on write (btrfs, zfs) - blocks of data are not modified, but instead they create new block with modifed data
Log-structured - file system itself is a log of operations

Not all file system support such mechanisms, i.e. ext2 is not journaling fs and all modifications applied directly.

That seems to be an answer - just choose FS with jounaling/COW and here you go. But no.

Research Model-Based Failure Analysis of Journaling File Systems reveals, that even journaled file systems can end up being inconsistent.
3 file systems (ext3, reiserfs, jfs) were examined when block writing error occurred. Result is presented in table:

As you can mention - every file system can leave content of block (Data Block) in inconsistent state (DC, Data Corruption).
Conclusion: do not rely heavily on file system journaling.

I also found research for NTFS (163 p.) - even with metadata redundancy file system can be corrupted and become unrecoverable.

What about COW and log structured?

In this research (26 p.) btrfs was tested on SSD and after some power outages file system has become unusable and unrecoverable.
On the other hand, journaled ext4 survived 1406.

As for log-structured - I couldn't find any research about them.

Magic number

We can outline 2 main components in file, that we should update - file size and data blocks.
What we should update first?

If file size, then in case of failure garbage can be found in file - file size can be larger, but data in new block contains some garbage.

It can be compared to garbage that stored in initialized variables on stack or in just allocated memory (i.e. using malloc in C)

From file system perspective - there is no inconsistency. But there may be in case of application - garbage in data.

We can protect ourselves by using special markers in file - after we read some chunk of data first check that marker.
Usually, it is some predefined constant.

This approach is used by:

Postgres - add "magic number" in header of WAL page

Postgres code

/*
* Each page of XLOG file has a header like this:
*/
#define XLOG_PAGE_MAGIC 0xD114 /* can be used as WAL version indicator */

typedef struct XLogPageHeaderData
{
    uint16  xlp_magic;  /* magic value for correctness checks */
    // ...
} XLogPageHeaderData;

Kafka - "magic number" used as a version

Kafka magic number

public class FileLogInputStream implements LogInputStream<FileLogInputStream.FileChannelRecordBatch> {
    @Override
    public FileChannelRecordBatch nextBatch() throws IOException {
        // ...

        byte magic = logHeaderBuffer.get(MAGIC_OFFSET);
        final FileChannelRecordBatch batch;

        if (magic < RecordBatch.MAGIC_VALUE_V2)
            batch = new LegacyFileChannelRecordBatch(offset, magic, fileRecords, position, size);
        else
            batch = new DefaultFileChannelRecordBatch(offset, magic, fileRecords, position, size);
        return batch;
    }
}

SQLite - use ASCII constant string "SQLite format 3" for main database file or random bytes for journal

SQLite magic numbers

// Header for undo journal

/*
** Journal files begin with the following magic string.  The data
** was obtained from /dev/random.  It is used only as a sanity check.
*/
static const unsigned char aJournalMagic[] = {
0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7,
};

static int readJournalHdr(
Pager *pPager,               /* Pager object */
int isHot,
i64 journalSize,             /* Size of the open journal file in bytes */
u32 *pNRec,                  /* OUT: Value read from the nRec field */
u32 *pDbSize                 /* OUT: Value of original database size field */
){
int rc;                      /* Return code */
unsigned char aMagic[8];     /* A buffer to hold the magic header */
i64 iHdrOff;                 /* Offset of journal header being read */

/* Read in the first 8 bytes of the journal header. If they do not match
** the  magic string found at the start of each journal header, return
** SQLITE_DONE. If an IO error occurs, return an error code. Otherwise,
** proceed.
*/
if( isHot || iHdrOff!=pPager->journalHdr ){
    rc = sqlite3OsRead(pPager->jfd, aMagic, sizeof(aMagic), iHdrOff);
    if( rc ){
    return rc;
    }
    if( memcmp(aMagic, aJournalMagic, sizeof(aMagic))!=0 ){
    return SQLITE_DONE;
    }
}

// ...
}

// Header of main database file

#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
#  define SQLITE_FILE_HEADER "SQLite format 3"
#endif

/*
** The header string that appears at the beginning of every
** SQLite database.
*/
static const char zMagicHeader[] = SQLITE_FILE_HEADER;

static int lockBtree(BtShared *pBt){
// ...
if( nPage>0 ){
    /* EVIDENCE-OF: R-43737-39999 Every valid SQLite database file begins
    ** with the following 16 bytes (in hex): 53 51 4c 69 74 65 20 66 6f 72 6d
    ** 61 74 20 33 00. */
    if( memcmp(page1, zMagicHeader, 16)!=0 ){
    goto page1_init_failed;
    }

// ...

page1_init_failed:
pBt->pPage1 = 0;
return rc;
}

Additionally, there are some predefined headers for different file formats. For example, BOM, JPEG or PNG.

Checksum

But this is just a constant, that does not depend on stored data - it is used to definetely say "this is a garbage".

What go wrong? For example, we send write request and it failed in the middle of operation. Then checksum in file header will be valid, but contents of file are not.
One can think that we should move magic number to the end of such chunk, but who said that data starts to be written from begin to end and not from end to begin?

Even so, what happens if data in the middle of page will be corrupted?
Magic number will not detect this, so we need some small digest of our chunk.
We will use it to compare our stored data with those that we have read to ensure integrity.

This small digest called checksum. This is just small fixed-sized byte array computed using some hash functions over all contents of file.
Checksum can be stored both at the begginning and at the end of chunk.
If you have such choice, I recommend store it in the end - data locality: page (OS) with high probability will be already in cache (same for cpu cache, L1/2/3).

Checksum is widely used:

Postgres - uses CRC32C for WAL records:

Postgres WAL CRC

typedef struct XLogRecord
{
    // ...
    pg_crc32c xl_crc;   /* CRC for this record */
} XLogRecord;

etcd - uses CRC for WAL records

etcd sliding crc

type Record struct {
Crc                  uint32   `protobuf:"varint,2,opt,name=crc" json:"crc"`
}

KurrentDB (formerly EventStore) - uses MD5

EventStore MD5

public class ChunkFooter {
    // ...
    public readonly byte[] MD5Hash;
    // ...
}

File System consistency model

Before going ahead, we should talk about consistency model.

In programming languages there is such a thing as "memory model".
In short, our program can be described in terms of store/load operations (assign value to a variable/read variable's value) and memory model describes which operations can be reordered (more accurately, which reoderings are prohibited).
Such reordering can give some performance improvements, but when we are moving to multi-threaded/concurrent execution these reorderings can spoil everything.
Given example:

void function() {
    // 1
    a = 123;
    b = 244;

    // 2
    int c = a;
    b = 555; 
}

Questions:

In 1 case - are we allowed to write b and only then a, so perform store/store reordering
In 2 case, are we allowed to write b and only then read from a, so perform store/load reodering.

The memory order answers these questions. For PLs and hardware there is documentation with memory model explanation:

Let's leave programming languages for later. The main thing is that we can define such rules for the file system as well.

This is called persistency semantics (name from this paper).

Study "All File Systems Are Not Created Equal" identified these "basic" operations:

File chunk overwrite
Append data to file
Rename
Directory operations

After conducting the experiment, this table was compiled:

Also note, that table shows only found bugs - if bug is not found, it does not mean that is does not exist.

For simplicity, I will continue use term "journaled" for file systems that have some kind of buffer, in which all operations stored before being applied - COW, log-structured, journaled and so on.

Atomicity

Single logical operation may consists of multiple physical operations. For example, append to a file (write to end) consists of:

Update size of file
Add new data block

Atomicity in that case means transactional atomicity, like in databases - if we fail to perform even single operation, we must be able rollback state to the initial (with same metadata).

We can draw the following conclusions:

No file system can atomically append some data blocks to file (except single block)
Overwrite of 1 disk sector is atomic
Non-journaled file system almost always do not provide atomicity of operations
Directory operations almost always atomic, except non-journaled file systems

What happens in case of failure during non-atomic operation?
The worst case - file system will be corrupted and you will have to run fsck (and pray to God it will be fixed).
As for files:

There will be garbage in file (in case of apppend) - just allocated new block and updated length
Part on block will be overwritten - overwrite operation failed in the middle

The same study also presented comparison matrix of behaviour in case of failure during some common file operation patterns.

Legend:

PA (Prefix Append) - safe append of new data bloc{ks
ARVR (Atomic Replace Via Rename) - rename file to update large amount of data
ACVR (Atomic Create Via Rename) - create new file with initialized contents by renaming file

As you can see each file system is not perfect and can become inconsistent in case of interruption during operation.

Important ARVR/ACVR assumption made

Study covered behaviour for ACVR/ARVR and showed that even these operation can be non-atomic.
But, then there was a note - there is no fsync call in those experments.
Take a look at tests specification:

# Atomic Replace Via Rename (ARVR)
initial:
  g <- creat("file", 0600)
  write(g, old)
main:
  f <- creat("file.tmp", 0600)
  write(f, new)
  rename("file.tmp", "file")
exists?:
  content("file") 6= old ^ content("file") 6= new

# Atomic create via rename (ACVR)
main:
  f <- creat("file.tmp", 0600)
  write(f, data)
  rename("file.tmp", "file")
exists?:
  content("file") 6= ∅ ^ content("file") 6= data

You can see, that there is no fsync call between write and rename. What is happening:

New file is created
Data is written to file
File is renamed
File system decides to first rename file (operation reordering)
!Failure!

After application reboot we observe that file is empty, because only rename operation performed on empty file.

To fix this, we should add fsync call before rename.

But, file system developers known about this pattern and add some hacks (to flush data to disk before rename):

ext4 - mount option auto_da_alloc
btrfs - mount option flushoncommit (description took from here, but wiki is archieved, so I do not known whether it is true anymore)
xfs - according to mailing list, the sync-after-rename behaviour was suggested and rejected for xfs

And the last question - is rename itself atomic?
Of course, we can write data to temporary file, fsync it, but what the point if everything breaks during rename call?
Documentation says the following:

If newpath already exists, it will be atomically replaced, so that there is no point at which another process attempting to access newpath will find it missing.

So, rename is "atomic" only from multi-*process*ing point of view, but not fault-tolerance.
Then, we find:

If newpath exists but the operation fails for some reason, rename() guarantees to leave an instance of newpath in place.

That means, that in case of errors, contents in newpath stay the same.
But still, no information about fault-tolerance.

In GNU C documentation I have found the following behaviour description:

If there is a system crash during the operation, it is possible for both names to still exist; but newname will always be intact if it exists at all.

Finally - target file (which is replaced) does not changes in case of failure.

So, conlusion: rename is atomic, but you should call fsync before to guarantee, that new data actually present on disk and file is not empty/half-full.

Reorderings

As for operations reordering, we can make such conclusion: if file system is journaled, then order of operations in most cases is preserved.
But that's not true for ext2, ext3-writeback, ext4-writeback, reiserfs-writeback so operations can be reordered.

Also, do not forget about directory operations - they are handled in the same way as regular file operations.
That means, that if we are writing to a file and then rename, actual operations can be rename empty file and start appending data blocks.

All file systems can do this, so always call fsync!

Write barrier

In memory model there is a definition of "write barrier" - machanism, that prohibit reordering of store/load operations.
As you can notice, file systems also have such machanism - it is fsync.

We can give such semantics:

All write operations happens before fsync (for same file)

We can say nothing about reordering of write operations before fsync, but definetely say - not after fsync.

Actually, fsync is not real barrier, just we can use such semantics for it.
But similar discussion has been raised - there was suggestion to add fbarrier syscall, but Linus rejected this idea, considering that it will add unnecessary complexity.

Other file systems

Previous studyings were oriented primarly on widely-used *nix file systems, but of course there are many others.

NTFS

NTFS - is a "standard" file system on Windows. I didn't find any research about it's fault tolerance.

The only I can do is draw conclusions based on file system properties:

Only metadata is journaled - there may be garbage in files after operations
Metadata is duplicated - in case of some hardware fault, you always have a "second chance" to recover it
Have it's own transactional API (TxF), but developers should not use it

APFS

APFS (Apple File System) - file system for Apple, which should replace HFS+.

According to papers and blogs (everything that I could find):

Uses Copy on write (not journaling) - main reason because it fits well for SSD
Have Atomic Safe-Save technique to guarantee atomic rename
Uses checksums for metadata only, but not user data

I have highlighted last point specifically, because I didn't understand the article I relied on.
It states:

apfs doesn’t checksum data because “[apfs] engineers contend that Apple devices basically don’t return bogus data”

But, if you go to the referenced article, you will see:

APFS checksums its own metadata but not user data

The misunderstanding is caused by the fact that in referenced article there was comparison with ZFS (which have checksum for user data), but in first - there is no mention about this.

Appliction `fsync` error handling

In previous section we were talking about fsync and it's errors. We saw how OS handles fsync errors (in my optinion, fsync should be special function in interface of a file system driver, so OS also should handle such error), but how real applications respond to errors?

Here we will use paper "Can Applications Recover from fsync Failures?". The title is selfdescriptive - this paper shows how different software and file systems behaves when encounters an error returned by fsync.

First table shows behaviour of file system:

ext4 data - means journaled mode

This table says:

fsync errors arise only during writing of data blocks or journal. But for metadata errors behaviour differs: xfs and btrfs will be remounted in read-only mode, and ext4 just log it (to OS) and continue to work
When error occurres during data block writing, metadata will not rollback. So size can be increased, but content of file will contain garbage.
After file system recover in runtime (error occurred and file system driver has been unloaded and loaded), state in memory can left unmodifed. In example, there is btrfs - after recovery, metadata can be changed, but file descriptor is old and points to a position in file outside of it.

All file systems mark pages "clean" but that because tests were run on Linux

The next table shows behaviour of applications in case of fsync error arising:

Legend:

OV (old value) - return old value, instead of new
FF (false failure) - return user error, but actually it's ok
KC/VC (ke/value corruption) - data was corrupted (tests were run on key-value storage)
KNF (key not found) - return user that all ok, but new value not saved (get lost)

We can make such conclusions:

If an fsync error occurres not immediately, then error amount increases
COW file systems better handle fsync errors, compared to regular journaled
Many applications in case of fsync error just halt and rollback to previous state (- and | in table)

Storage

And the last layer - persistent storage. We will talk about HDD and SSD.

They have different storage technologies under the hood, but now we are focused on their parameters:

Time to failure
ECC (error correction codes)
Access controller

Beyond HDD and SSD

There are other storage devices beside HDD and SSD. For example:

Tape drives
CD/DVD/Blu-ray disks
PCM, FRAM, MRAM

We will not talk about them in the rest part, but mention here.

Tape drives seems ideal option for backup storage. Compared to HDD, tape drives has more longevity and capacity/cost fraction. But they are not suitable for modern workloads with lots of random access.

CD/DVD/Blu-ray disks also not forgotten. According to this research sales of optical disks only increasing.
Again, optical disks are not well suited for extensive workloads.

Also, there are some technologies like PCM (Phase-Change Memory), FRAM (Ferroelectric RAM) and MRAM (Magnetoresistive RAM). I couldn't find enough information on them, so I won't say anything so as not to misinform.

Time to failure

Every piece of equipment wears out. In case of processing hardware (CPU or GPU) will break down, we just replace it and that's all.

But, if our persistence will break down, we might loose data. Blackbaze released a report for 2023 year with disk failure statistics. We can draw such conclusions:

AFR (Annualized Failure Rate) depends on many factors. For example, vendor and disk size, but average across the board is about 65 months (5.5 years)
Compared to 2022 year AFR increased

As for SSD, they have report for 2022. According to it, AFR for SSD - 0.92% (lower than HDD). But take into account, that SSD was took into operations only in 2018 year, so statistics can be not accurate.

Now, something about the impact of physical world on HDD/SSD operations:

HDD has more moving parts, so it is more susceptible to physical damage. There is a bright example - "Shouting in the Datacenter". This video shows that even such small action is enough to affect HDD - response time increases. Digging deeper, this study analyzed the effect of noise on HDD operations - HDD was forced to work in noise (ADoS - Acoustice Denial of Service). As a result, positioning errors rate increases and sometimes there are disk failures occurred.
SSD, on the other hand, does not have moving parts, but it heavily relies on elictricity. It is very sensible to sudden power outage! This research have tested behaviour of SSD for such power outage. And suddenly, such sudden power outage can lead to: data integrity violation, data loss or even trun SSD into a brick.

ECC

Often, HDD and SSD has builtin support for ECC - Error Correction Codes.

HDD supports Advanced Format layout. It allows to store ECC for whole sector. But, this requires additional support from OS (nowadays almost everyone support this). Also note, that file systems can know about Advanced Format and can adjust to it, but this is out of article's scope.
SSD also has such support, but only for NAND storage technology and NOR (for microcontrollers). But this is supported at storage level, not OS.

But ECC is much smaller than stored data, so sometimes it will not be able to fix all errors. In this study compared HDD and SSD lifecycles (using their own tests). Next plots show how many Uncorrectable Errors (UE) occurred until disk failure - errors, that ECC can not handle.

Conclusions:

Amount of UE in SSD depends on lifetime of disk, whereas HDD depends on head flying hours.
Amount of errors on HDD increases dramatically 2 days before failure.
Amount of UE on SSD is higher, than on HDD.

Principal conclusion: modern hardware (with modern OS) have ECC, but we should not rely on it heavily.

P.S. point 1 - is another reason to consider data locality (the longer HDD's lifetime, the less disk head moves)

Access controller

Last component - is a disk access controller. It is stored in disk itself and handles all requests to disk. Important detail here - is a disk cache.

Recall fsync - it must make sure all changes were flush to disk. But if you look more closely to it's man, you will see:

The fsync() implementations in older kernels and lesser used filesystems do not know how to flush disk caches. In these cases disk caches need to be disabled using hdparm(8) or sdparm(8) to guarantee safe operation.

In old kernel versions (for Linux it's less than 2.2) fsync did not know how to correctly flush disk cache, just as some filesystems. According to blog article "Ensuring data reaches disk" there is barrier mount option for ext3/4, btfs and xfs filesystems that enables barriers (disk cache flushing).

I have researched some Linux kernel code and figured out, that only "readonly" filesystems do not have fsync implementation (i.e. efs and isofs do not register custom fsync).
Also, there is a generic fsync implementation (i.e. for non-journaled file systems)

HFS fsync implementation

// https://github.com/torvalds/linux/blob/a4145ce1e7bc247fd6f2846e8699473448717b37/block/bdev.c#L203
/*
 * Write out and wait upon all the dirty data associated with a block
 * device via its mapping.  Does not take the superblock lock.
 */
int sync_blockdev(struct block_device *bdev)
{
 if (!bdev)
  return 0;
 return filemap_write_and_wait(bdev->bd_inode->i_mapping);
}
EXPORT_SYMBOL(sync_blockdev);

// https://github.com/torvalds/linux/blob/a4145ce1e7bc247fd6f2846e8699473448717b37/mm/filemap.c#L779
/**
 * file_write_and_wait_range - write out & wait on a file range
 * @file: file pointing to address_space with pages
 * @lstart: offset in bytes where the range starts
 * @lend: offset in bytes where the range ends (inclusive)
 *
 * Write out and wait upon file offsets lstart->lend, inclusive.
 *
 * Note that @lend is inclusive (describes the last byte to be written) so
 * that this function can be used to write to the very end-of-file (end = -1).
 *
 * After writing out and waiting on the data, we check and advance the
 * f_wb_err cursor to the latest value, and return any errors detected there.
 *
 * Return: %0 on success, negative error code otherwise.
 */
int file_write_and_wait_range(struct file *file, loff_t lstart, loff_t lend)
{
 int err = 0, err2;
 struct address_space *mapping = file->f_mapping;

 if (lend < lstart)
  return 0;

 if (mapping_needs_writeback(mapping)) {
  err = __filemap_fdatawrite_range(mapping, lstart, lend,
       WB_SYNC_ALL);
  /* See comment of filemap_write_and_wait() */
  if (err != -EIO)
   __filemap_fdatawait_range(mapping, lstart, lend);
 }
 err2 = file_check_and_advance_wb_err(file);
 if (!err)
  err = err2;
 return err;
}
EXPORT_SYMBOL(file_write_and_wait_range);

// https://github.com/torvalds/linux/blob/a4145ce1e7bc247fd6f2846e8699473448717b37/fs/hfs/inode.c#L661
static int hfs_file_fsync(struct file *filp, loff_t start, loff_t end,
     int datasync)
{
    // ...
 file_write_and_wait_range(filp, start, end);
 // ... 
 sync_blockdev(sb->s_bdev);
 // ... 
 return ret;
}

Again, access controller is not bad thing. For example, it allows SSD to live longer by smart utilizing blocks as they have limited number or P/E cycles (roughly speaking, access controller plays more crucial part in SSD than HDD).

Persistence properties

At the end, let's talk about persistence properties provided by HDD and SSD: atomicity and PowerSafe OverWrite.

Atomicity

IO is very slow, compared to other operations. Here reference to "Latency Numbers every programmer should know" (extended version by year) - even for 2020 year HDD spends 2ms just for seek.
As we can not eliminate disk seeks (from HDD) or increase memory cells (for SSD) the only thing we can do is to add some optimizations. Main optimization is to batch operations by blocks. So, even when you request to read/write single byte actually you will read/write whole block.

Today, we have 2 block sizes: 512 bytes and 4Kb. But for HDD name of such unit is "sector" and for SSD are "page" and "block" for read and write accordingly.
Reading can not corrupt data, but write can, so we will focus primarly on write operations, so use "unit for write".

There is already an answer to such question on StackOverflow:

a sector write sent by the kernel is likely atomic

But under conditions:

Access controller has a spare battery (if power outage occurres during operations)
SCSI disk vendor gives guarantees for write atomicity
(for NVMe) special atomic write function is called

That sounds quite logical, so I'll believe it.

PowerSafe OverWrite

PowerSafe OverWrite (PSOW) - is a term, used by SQLite developers to describe behaviour of file systems and disk in case of sudden power outage.
The meaning is as follows:

When an application writes a range of bytes in a file, no bytes outside of that range will change, even if the write occurs just before a crash or power failure.

Practically, it means that there is a spare battery in disk that will be used to safe write remaining data. If there is no such thing, then when we write single unit of write (either or both):

One part of write range will contain new data and another old
Part of same sector that not in write range will contain garbage

Atomicity and PSOW are not the same

At first glance, one can think atomicity and PowerSafe OverWrite are same, but that's not true.

For example let's imagine such situation - we want to overwrite part of file and during write operation power outage occurred. Depending on different combinations of properties, we can get different consequences.

To be specific, we have 3 sectors/unit of write which all contains 0 (old data) and we want to write range of 1.

              А         Б         В
Sectors: |000000000|000000000|000000000|        
Write:        |------------------|

Then, we have situations:

Atomic + PSOW: each sector contains either new data or old data.

   | A:  | 000011111 | 000000000 | 000000000 |
   | --- |

   | B:  | 000000000 | 111111111 | 000000000 |
   | --- |

   | C:  | 000000000 | 000000000 | 111100000 |
   | --- |

!Atomic + PSOW: the sector that was overwritten during power outage will contain garbage

   | A:  | 000011010 | 000000000 | 000000000 |
   | --- |

   | B:  | 000000000 | 110011010 | 000000000 |
   | --- |

   | C:  | 000000000 | 000000000 | 001000000 |
   | --- |

NOTE: data outside the sector is not affected/corrupted/changed

Atomic + !PSOW: thanks to atomicity data in the sector we write will be written successfully, but PSOW can not guarantee that other sectors will be fine. So consinder such result:

   | A:  | 000011111 | 001011100 | 000000000 |
   | --- |

   | B:  | 000000000 | 111111111 | 001000000 |
   | --- |

   | C:  | 000001010 | 111000110 | 111100000 |
   | --- |

How can this happen? For example, battery is enough to write that single page but only for it - when we finish writing that page, disk head will randomly walk, affecting stored data with remaining magnetic energy.

!Atomic + !PSOW: it gets more interesting when we can not guarantee anything. Example of such behaviour is given by SQLite developers: OS reads whole sector, modify some bytes, write that page (Read-Modify-Write) and during write there is a power outage. Data was partially written and ECC is not updated, so when after restart disk controller figures out incorrect sector and clears that page.

   | A:  | 111111111 | 000000000 | 000000000 |
   | --- |

   | B:  | 000000000 | 111111111 | 000000000 |
   | --- |

   | C:  | 000000000 | 000000000 | 111111111 |
   | --- |

Repository hashcorp/raft-wal have README with collected assumptions of different applications about persistence guarantees:

Application	Atomicity	PowerSafe OverWrite
SQLite	-	+ (from 3.7.9)
Hashicorp	-	+
Etcd/wal	+	+
LMDB	+	-
BoltDB	+	+

You can think that's all, but we did not cover one important layer, that many modern programming langauges have - runtime.

Runtime

At the very beginning we went from PL to OS directly, but some languages have some managed layer - runtime:

Runtime itself - Nodejs, .NET, JVM
Interpreter - Python, Ruby

In case of C/C++ we can make syscall directly (just invoke fsync), but other langauges may have some abstraction layer. Now, we will talk about invoking fsync as it is necessary to ensure data is persisted.

For java it is very simple - function force(true). According to documentation:

Forces any updates to this channel's file to be written to the storage device that contains it.

So, we will not directly call fsync - we are programming in abstractions that runtime provides to us. So, the same is applied to .NET - class FileStream has overloaded method Flush(bool flushToDisk). When passing true all data must be flushed to disk:

Use this overload when you want to ensure that all buffered data in intermediate file buffers is written to disk. When you call the Flush method, the operating system I/O buffer is also flushed.

Again note - there is no word about fsync as it is platform-dependent implementation detail. But, I'm not used to blindly rely on words, so let's take a look at .NET source code - we file such piece of code (call chain):

FileStream.Flush call chain

public class FileStream
{
    private readonly FileStreamStrategy _strategy;

    // https://github.com/dotnet/runtime/blob/da781b3aab1bc30793812bced4a6b64d2df31a9f/src/libraries/System.Private.CoreLib/src/System/IO/FileStream.cs#L389
    public virtual void Flush(bool flushToDisk)
    {
        if (_strategy.IsClosed)
        {
            ThrowHelper.ThrowObjectDisposedException_FileClosed();
        }

        _strategy.Flush(flushToDisk);
    }
}

internal abstract class OSFileStreamStrategy : FileStreamStrategy
{
    // https://github.com/dotnet/runtime/blob/da781b3aab1bc30793812bced4a6b64d2df31a9f/src/libraries/System.Private.CoreLib/src/System/IO/Strategies/OSFileStreamStrategy.cs#L137
    internal sealed override void Flush(bool flushToDisk)
    {
        if (flushToDisk && CanWrite)
        {
            FileStreamHelpers.FlushToDisk(_fileHandle);
        }
    }
}

internal static partial class FileStreamHelpers
{
    // https://github.com/dotnet/runtime/blob/da781b3aab1bc30793812bced4a6b64d2df31a9f/src/libraries/System.Private.CoreLib/src/System/IO/Strategies/FileStreamHelpers.Unix.cs#L40
    internal static void FlushToDisk(SafeFileHandle handle)
    {
        if (Interop.Sys.FSync(handle) < 0)
        {
            Interop.ErrorInfo errorInfo = Interop.Sys.GetLastErrorInfo();
            switch (errorInfo.Error)
            {
                case Interop.Error.EROFS:
                case Interop.Error.EINVAL:
                case Interop.Error.ENOTSUP:
                    // Ignore failures for special files that don't support synchronization.
                    // In such cases there's nothing to flush.
                    break;
                default:
                    throw Interop.GetExceptionForIoErrno(errorInfo, handle.Path);
            }
        }
    }
}

internal static partial class Interop
{
    internal static partial class Sys
    {
        // https://github.com/dotnet/runtime/blob/da781b3aab1bc30793812bced4a6b64d2df31a9f/src/libraries/Common/src/Interop/Unix/System.Native/Interop.FSync.cs#L11
        [LibraryImport(Libraries.SystemNative, EntryPoint = "SystemNative_FSync", SetLastError = true)]
        internal static partial int FSync(SafeFileHandle fd);
    }
}

// https://github.com/dotnet/runtime/blob/da781b3aab1bc30793812bced4a6b64d2df31a9f/src/native/libs/System.Native/pal_io.c#L736
int32_t SystemNative_FSync(intptr_t fd)
{
    int fileDescriptor = ToFileDescriptor(fd);

    int32_t result;
    while ((result =
#if defined(TARGET_OSX) && HAVE_F_FULLFSYNC
    fcntl(fileDescriptor, F_FULLFSYNC)
#else
    fsync(fileDescriptor)
#endif
    < 0) && errno == EINTR);
    return result;
}

So, when we are passing true, then there is fsync must occur. But let's look what happens in reality. I have written such code for this and trace it with strace:

using var file = new FileStream("sample.txt", FileMode.OpenOrCreate);
file.Write("hello, world"u8);
file.Flush(true);

Here is part of strace output:

openat(AT_FDCWD, "/path/sample.txt", O_RDWR|O_CREAT|O_CLOEXEC, 0666) = 19
lseek(19, 0, SEEK_CUR)                  = 0
pwrite64(19, "hello, world", 12, 0)     = 12
fsync(19)                               = 0
flock(19, LOCK_UN)                      = 0
close(19)                               = 0

Steps:

openat - open file and file descriptor is 19
lseek - position file at the very beginning
pwrite64 - our data is written
fsync(19) - fsync call happened
close(19) - file is closed

That's all fine - fsync is called. But I used .NET 8.0.1 for that, next I wanted to test behaviour on another version - 7.0.11. Source code is the same but output is different:

openat(AT_FDCWD, "/path/sample.txt", O_RDWR|O_CREAT|O_CLOEXEC, 0666) = 19
lseek(19, 0, SEEK_CUR)                  = 0
pwrite64(19, "hello, world", 12, 0)     = 12
flock(19, LOCK_UN)                      = 0
close(19)                               = 0

There is no fsync! Moreover, if we call Flush(true) again it will appear and all subsequent calls will invoke fsync (add second Flush(true)):

openat(AT_FDCWD, "/path/sample.txt", O_RDWR|O_CREAT|O_CLOEXEC, 0666) = 19
lseek(19, 0, SEEK_CUR)                  = 0
pwrite64(19, "hello, world", 12, 0)     = 12
fsync(19)                               = 0
flock(19, LOCK_UN)                      = 0
close(19)                               = 0

So, I have concluded that first Flush(true) is ignored (for some reason, idk), but subsequent are not.

Also, I must note that developer often is limited to abstractions and programming model provided by runtime. Take .NET as an example again.
Remember that directories are also files and we must call fsync after operations. In .NET we can not open directories (Windows legacy):

Directory class does not have Open method (or some Sync)
If we call FileStream with directory path (even when specifying readonly mode), then we get UnauthorizedAccessException.

I have found a rough workaround - call open function using P/Invoke, get directory file descriptor and wrap it with SafeFileHandle. In this case, there is no excpetion and we can use fsync.

var directory = Directory.CreateDirectory("sample-directory");
const int directoryFlags = 65536; // O_DIRECTORY | O_RDONLY
var handle = Open(directory.FullName, directoryFlags); 
using var stream = new FileStream(new SafeFileHandle(handle, true), FileAccess.ReadWrite);
stream.Flush(true);

[DllImport("libc", EntryPoint = "open")]
static extern nint Open(string path, int flags);

Here is strace output:

openat(AT_FDCWD, "/path/sample-directory", O_RDONLY|O_DIRECTORY) = 19
lseek(19, 0, SEEK_CUR)                  = 0
lseek(19, 0, SEEK_CUR)                  = 0
fsync(19)                               = 0
close(19)                               = 0

Key takeways

To sum up, we can see that IO stack has multiple details that we must take into account to ensure data integrity. Each layer has own semantics and characteristics.
Neglecting them means neglecting our data: data corruption, data loss, garbage occurrence and other unpleasant events.

Here a small diagram briefly summarizing all above:

File operations patterns

After considering possible problems, that can arise during operations with files, let's consider opposite - how to fight with these problems.

As a developers we create huge systems with lots of connected subsystems. The most illustrative example is a database (persistent, not in-memory).
So most of example implementation will be given in DBMSs source code.

Create new file

Let's kick off from the very beginning - creating a new file.

If we want a new empty file then we should just call fsync on parent directory after we have created it:

creat("/dir/data") - create new file
fsync("/dir") - sync directory's contents

Initially, file is empty, but what if file must have initial data, i.e. header with metadata. As we have seen, just fsync is not enough because if operation is interrupted then file either will not exist or will be half-full (which is not acceptable).

We already have seen such pattern - Atomic Create Via Rename. Again, the title is selfdescriptive - to create initialized file we need to swap it (rename) with another initialized file.
Algorithm is the following:

creat("/dir/data.tmp") - create temporary file
write("/dir/data.tmp", new_data) - write required data to it
fsync("/dir/data.tmp") - flush contents of temporary file to disk
fsync("/dir") - flush updates to parent directory
rename("/dir/data.tmp", "/dir/data") - rename (replace) temporary file with target one
fsync("/dir") - flush rename to parent directory

Pratical example: creation of new log segment (file with operations being performed on data) in etcd:

Creation of new log segment file in etcd

// cut closes current file written and creates a new one ready to append.
// cut first creates a temp wal file and writes necessary headers into it.
// Then cut atomically rename temp wal file to a wal file.
func (w *WAL) cut() error {
 // Название для нового файла сегмента
 fpath := filepath.Join(w.dir, walName(w.seq()+1, w.enti+1))

    // 1. Create temporary file
 newTail, err := w.fp.Open()
 if err != nil {
  return err
 }

    // 2. Write data to temporary file
 // update writer and save the previous crc
 w.locks = append(w.locks, newTail)
 prevCrc := w.encoder.crc.Sum32()
 w.encoder, err = newFileEncoder(w.tail().File, prevCrc)
 if err != nil {
  return err
 }
 if err = w.saveCrc(prevCrc); err != nil {
  return err
 }
 if err = w.encoder.encode(&walpb.Record{Type: MetadataType, Data: w.metadata}); err != nil {
  return err
 }
 if err = w.saveState(&w.state); err != nil {
  return err
 }

 // atomically move temp wal file to wal file

    // 3-4. Flush file data to disk
 if err = w.sync(); err != nil {
  return err
 }

    // 5. Rename temporary file to target
 if err = os.Rename(newTail.Name(), fpath); err != nil {
  return err
 }

 // 6. Flush "rename" of parent directory to disk
 if err = fileutil.Fsync(w.dirFile); err != nil {
  return err
 }

 // reopen newTail with its new path so calls to Name() match the wal filename format
 newTail.Close()
 if newTail, err = fileutil.LockFile(fpath, os.O_WRONLY, fileutil.PrivateFileMode); err != nil {
  return err
 }

 w.locks[len(w.locks)-1] = newTail
 prevCrc = w.encoder.crc.Sum32()
 w.encoder, err = newFileEncoder(w.tail().File, prevCrc)
 if err != nil {
  return err
 }

 return nil
}

I have commented steps of our defined algorithm with numbers. As you can see, steps performed in same sequence.

Also, target file is reopened in the end. This is done to correctly display target filename, not temporary (does not affect correctness).

File modification

File is created and now we must make some modifications - write new data to it or update (overwrite) existing. Here we have 2 options:

Change of a small file

If our file is small enough, then we can apply sibling of previous pattern - Atomic Replace Via Rename (btrfs call this overwrite-by-rename). Algorithm is almost the same:

creat("/dir/data.tmp") - create temporary file
write("/dir/data.tmp", new_data) - write new data to it
fsync("/dir/data.tmp") - flush data to disk
fsync("/dir") - update parent directory contents (new file creation)
rename("/dir/data.tmp", "/dir/data") - rename (replace) old file with a new one
fsync("/dir") - update parent directory contents (file rename)

Earlier I said that some file systems can detect this pattern and perform fsync themselves. But as a developers we target on multiple systems and do not rely on specific tehnologies - specific file system features in this case.

Pratical example: LevelDB flush memtable to disk.

LevelDB flush memtable to disk

LevelDB stores data in memory using special MemTable. When it becomes too big it is flushed to disk - this is called "Compaction"

// https://github.com/google/leveldb/blob/068d5ee1a3ac40dabd00d211d5013af44be55bea/db/db_impl.cc#L549
void DBImpl::CompactMemTable() {
  // ...

  // Replace immutable memtable with the generated Table
  if (s.ok()) {
    edit.SetPrevLogNumber(0);
    edit.SetLogNumber(logfile_number_);  // Earlier logs no longer needed
    s = versions_->LogAndApply(&edit, &mutex_); // Versionset->LogAndApply
  }

  // ...
}

// https://github.com/google/leveldb/blob/068d5ee1a3ac40dabd00d211d5013af44be55bea/db/version_set.cc#L777
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
  // 1. Create new state - apply patches to current state (in-memory for now)
  Version* v = new Version(this);
  {
    Builder builder(this, current_);
    builder.Apply(edit);
    builder.SaveTo(v);
  }
  Finalize(v);

  // Initialize new descriptor log file if necessary by creating
  // a temporary file that contains a snapshot of the current version.
  std::string new_manifest_file;
  Status s;
  if (descriptor_log_ == nullptr) { 
    // 2. Create temporary file
    new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
    s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
    if (s.ok()) {
      // 3. Write data (new snapshot) to temporary file
      descriptor_log_ = new log::Writer(descriptor_file_);
      s = WriteSnapshot(descriptor_log_);
    }
  }

  {
    if (s.ok()) {
      // 4. Flush data to disk
      s = descriptor_file_->Sync();
    }

    // If we just created a new descriptor file, install it by writing a
    // new CURRENT file that points to it.
    if (s.ok() && !new_manifest_file.empty()) {
      // 5. Rename temporary file to target
      s = SetCurrentFile(env_, dbname_, manifest_file_number_);
    }

    mu->Lock();
  }
  return s;
}

// https://github.com/google/leveldb/blob/068d5ee1a3ac40dabd00d211d5013af44be55bea/util/env_posix.cc#L334
class PosixWritableFile: public WritableFile {
public:
  Status Sync() override {
    Status status = SyncDirIfManifest();

    status = FlushBuffer();
    return SyncFd(fd_, filename_);
  }
private:
  static Status SyncFd(int fd, const std::string& fd_path) {
#if HAVE_FULLFSYNC
    // On macOS and iOS, fsync() doesn't guarantee durability past power
    // failures. fcntl(F_FULLFSYNC) is required for that purpose. Some
    // filesystems don't support fcntl(F_FULLFSYNC), and require a fallback to
    // fsync().
    if (::fcntl(fd, F_FULLFSYNC) == 0) {
      return Status::OK();
    }
#endif  // HAVE_FULLFSYNC

#if HAVE_FDATASYNC
    bool sync_success = ::fdatasync(fd) == 0;
#else
    bool sync_success = ::fsync(fd) == 0;
#endif  // HAVE_FDATASYNC

    if (sync_success) {
      return Status::OK();
    }
    return PosixError(fd_path, errno);
  }
}

// https://github.com/google/leveldb/blob/068d5ee1a3ac40dabd00d211d5013af44be55bea/db/filename.cc#L123
Status SetCurrentFile(Env* env, const std::string& dbname,
                      uint64_t descriptor_number) {
  // ...
  if (s.ok()) {
    // Rename temporary file to target
    s = env->RenameFile(tmp, CurrentFileName(dbname));
  }
  return s;
}

Steps performed the same. Also, if you saw the code, you could mention usage of macOS specific - it requires usage of fcntl instead of fsync.

UNDO log

This example is given for a small file, but what if file is large or free disk space is low?

So far we saw many atomic operations + fsync and now we will use them to create atomic file overwrite. But what does mean "atomically" here? Actually, we can go in both directions: undo operation (rollback operation) and reapply new operation (redo operation). Thus, we come to the 2 main conceptions:

UNDO log - contains information about how to rollback to previous state if operation fails
REDO log - contains information about what operation we wanted to perform in order to redo it if some failure occurred

First, we describe UNDO log and REDO log come after.

Undo log contains information to rollback operations. In case of file rewrite it can store original data that we are overwriting. So, after restart (there is a failure occurred) we check for some incomplete operation in that log and undo them.

Example for undo/redo log is borrowed from "Files Are Hard".

Our example is following: we want to write new data (new_data) starting from 10 byte (start) with length of 15 bytes (length), so undo log will contain bytes from 10 to 25 of original data (old_data).
Algorithm is the following:

creat("/dir/undo.log") - create undo log
write("/dir/undo.log", "[check_sum, start, length, old_data]") - store original data, that we want to overwrite:
- start - start position
- length - length of byte range
- old_data - actual data in that range
- check_sum - chech-sum, computed for the data
fsync("/dir/undo.log") - persist undo log on disk
fsync("/dir") - sync parent directory contents (undo log creation)
write("/dir/data", new_data) - overwrite original file
fsync("/dir/data") - flush file updates to disk
unlink("/dir/undo.log") - remove undo log
fsync("/dir") - sync parent directory contents (undo log deletion)

What is taken into account in this example:

Fault can occur even right after UNDO log creation or data can be corrupted during reboot - so store checksum of that stored data
Always call fsync even for undo log - without this undo log can disappear after we have modified main data file
Call fsync even after deletion of undo log - otherwise we would think that operation was not completed at time of halt and perform rollback

Actually, you do not need to constantly create and remove undo log - you can just create it once and use special markers to detect that operation is completed successfully.
But you still need to call fsync when performing changes in that file.

At this time you have probably already figured out how to rollback:

Check undo-log existence (or there are some operations "in-progress")
Check correctness of records (checksums)
Find all undo operations (start byte, length, data)
Write that original data
Remove undo-log (mark operations "aborted")
Flush changes to disk

Even if there is another fault during rollback we always can retry because our algorithm is idempotent (additionally, you should consider atomicity and PSOW).

SQLite developers use undo log and developed 2 optimizations (as new file creation is a costly operation):

Truncate file after operation is complete: PRAGMA journal_mode=TRUNCATE
Set file header to all 0 - PRAGMA journal_mode=PERSIST

Practical example: undo log in SQLite

SQLite undo log

This algorithm is described in documentation - Atomic Commit In SQLite

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/btree.c#L4388
int sqlite3BtreeCommit(Btree *p){
  int rc;
  // First phase - create log and update data in database file
  rc = sqlite3BtreeCommitPhaseOne(p, 0);
  if( rc==SQLITE_OK ){
    // Second phase - remove/trancate/nullify log
    rc = sqlite3BtreeCommitPhaseTwo(p, 0);
  }
  return rc;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/btree.c#L4267
int sqlite3BtreeCommitPhaseOne(Btree *p, const char *zSuperJrnl){
  int rc = SQLITE_OK;
  if( p->inTrans==TRANS_WRITE ){
    rc = sqlite3PagerCommitPhaseOne(pBt->pPager, zSuperJrnl, 0);
  }
  return rc;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/pager.c#L6437
int sqlite3PagerCommitPhaseOne(
  Pager *pPager,                  /* Pager object */
  const char *zSuper,            /* If not NULL, the super-journal name */
  int noSync                      /* True to omit the xSync on the db file */
){
  int rc = SQLITE_OK;             /* Return code */

  if( 0==pagerFlushOnCommit(pPager, 1) ){
    // ...
  }else{
    if( pagerUseWal(pPager) ){
      // ...
    }else{
      // 1. Save original data to log
      rc = pager_incr_changecounter(pPager, 0);
      // 2. Sync data to disk (call fsync)
      rc = syncJournal(pPager, 0);
      if( rc!=SQLITE_OK ) goto commit_phase_one_exit;

      // 3. Write updated data to main database file
      pList = sqlite3PcacheDirtyList(pPager->pPCache);
      if( /* ... */ ){
        rc = pager_write_pagelist(pPager, pList);
      }
      if( rc!=SQLITE_OK ) goto commit_phase_one_exit;

      // 4. Flush main database file to disk
      if( /* ... */ ){
        rc = sqlite3PagerSync(pPager, zSuper);
      }
    }
  }

commit_phase_one_exit:
  return rc;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/pager.c#L4259
static int syncJournal(Pager *pPager, int newHdr){
  int rc;                         /* Return code */

  if( /* ... */ ){
    if( /* ... */ ){
      if( /* ... */ ){
        // Write total amount of pages equal to 0 (just in case)
        if( rc==SQLITE_OK && 0==memcmp(aMagic, aJournalMagic, 8) ){
          static const u8 zerobyte = 0;
          rc = sqlite3OsWrite(pPager->jfd, &zerobyte, 1, iNextHdrOffset);
        }

        if( /* ... */ ){
          // Flush written data
          rc = sqlite3OsSync(pPager->jfd, pPager->syncFlags);
          if( rc!=SQLITE_OK ) return rc;
        }

        // Write header with metadata
        rc = sqlite3OsWrite(
            pPager->jfd, zHeader, sizeof(zHeader), pPager->journalHdr
        );
        if( rc!=SQLITE_OK ) return rc;
      }
      if( /* ... */ ){
        // Flush data to disk again
        rc = sqlite3OsSync(pPager->jfd, pPager->syncFlags|
          (pPager->syncFlags==SQLITE_SYNC_FULL?SQLITE_SYNC_DATAONLY:0)
        );
        if( rc!=SQLITE_OK ) return rc;
      }
    }else{
      pPager->journalHdr = pPager->journalOff;
    }
  }

  return SQLITE_OK;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/pager.c#L6372
int sqlite3PagerSync(Pager *pPager, const char *zSuper){
  int rc = SQLITE_OK;
  if( /* ... */ ){
    // fsync
    rc = sqlite3OsSync(pPager->fd, pPager->syncFlags);
  }
  return rc;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/btree.c#L4356
int sqlite3BtreeCommitPhaseTwo(Btree *p, int bCleanup){
  if( p->inTrans==TRANS_WRITE ){
    int rc;
    rc = sqlite3PagerCommitPhaseTwo(p->pBt->pPager);
    if( rc!=SQLITE_OK && bCleanup==0 ){
      sqlite3BtreeLeave(p);
      return rc;
    }
  }

  return SQLITE_OK;
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/pager.c#L6674
int sqlite3PagerCommitPhaseTwo(Pager *pPager){
  int rc = SQLITE_OK;                  /* Return code */
  rc = pager_end_transaction(pPager, pPager->setSuper, 1);
  return pager_error(pPager, rc);
}

// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/pager.c#L2033
static int pager_end_transaction(Pager *pPager, int hasSuper, int bCommit){
  int rc = SQLITE_OK;
  int rc2 = SQLITE_OK;     

  if( isOpen(pPager->jfd) ){
    if( sqlite3JournalIsInMemory(pPager->jfd) ){
      // ...
    }else if( pPager->journalMode==PAGER_JOURNALMODE_TRUNCATE ){
      // PRAGMA journal_mode=TRUNCATE
      // Truncate file to 0
      if( pPager->journalOff==0 ){
        rc = SQLITE_OK;
      }else{
        rc = sqlite3OsTruncate(pPager->jfd, 0);
        if( rc==SQLITE_OK && pPager->fullSync ){
          rc = sqlite3OsSync(pPager->jfd, pPager->syncFlags);
        }
      }
      pPager->journalOff = 0;
    }else if( pPager->journalMode==PAGER_JOURNALMODE_PERSIST){
      // PRAGMA journal_mode=PERSIST
      // Nullify header
      rc = zeroJournalHdr(pPager, hasSuper||pPager->tempFile);
      pPager->journalOff = 0;
    }else{
      // PRAGMA journal_mode=DELETE
      // Remove undo log file
      int bDelete = !pPager->tempFile;
      sqlite3OsClose(pPager->jfd);
      if( bDelete ){
        rc = sqlite3OsDelete(pPager->pVfs, pPager->zJournal, pPager->extraSync);
      }
    }
  }
  // ...
  return (rc==SQLITE_OK?rc2:rc);
}

// sqlite3OsDelete implementation for *nix
// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/os_unix.c#L6533
static int unixDelete(
  sqlite3_vfs *NotUsed,     /* VFS containing this as the xDelete method */
  const char *zPath,        /* Name of file to be deleted */
  int dirSync               /* If true, fsync() directory after deleting file */
){
  int rc = SQLITE_OK;

  // Remove file itself
  if( osUnlink(zPath)==(-1) ){
    rc = unixLogError(SQLITE_IOERR_DELETE, "unlink", zPath);
    return rc;
  }

  // Sync directory contents
  if( (dirSync & 1)!=0 ){
    int fd;
    rc = osOpenDirectory(zPath, &fd);
    if( rc==SQLITE_OK ){
      // "Improved fsync"
      if( full_fsync(fd,0,0) ){
        rc = unixLogError(SQLITE_IOERR_DIR_FSYNC, "fsync", zPath);
      }
    }else{
      rc = SQLITE_OK;
    }
  }
  return rc;
}

// "Improved fsync" - is just fsync that counts in specifics of some OS
// https://github.com/sqlite/sqlite/blob/5007833f5f82d33c95f44c65fc46221de1c5950f/src/os_unix.c#L3638
static int full_fsync(int fd, int fullSync, int dataOnly){
  int rc;

  /* If we compiled with the SQLITE_NO_SYNC flag, then syncing is a
  ** no-op.  But go ahead and call fstat() to validate the file
  ** descriptor as we need a method to provoke a failure during
  ** coverage testing.
  */
#ifdef SQLITE_NO_SYNC
  {
    struct stat buf;
    rc = osFstat(fd, &buf);
  }
#elif HAVE_FULLFSYNC
  if( fullSync ){
    rc = osFcntl(fd, F_FULLFSYNC, 0);
  }else{
    rc = 1;
  }
  /* If the FULLFSYNC failed, fall back to attempting an fsync().
  ** It shouldn't be possible for fullfsync to fail on the local
  ** file system (on OSX), so failure indicates that FULLFSYNC
  ** isn't supported for this file system. So, attempt an fsync
  ** and (for now) ignore the overhead of a superfluous fcntl call.
  ** It'd be better to detect fullfsync support once and avoid
  ** the fcntl call every time sync is called.
  */
  if( rc ) rc = fsync(fd);

#elif defined(__APPLE__)
  /* fdatasync() on HFS+ doesn't yet flush the file size if it changed correctly
  ** so currently we default to the macro that redefines fdatasync to fsync
  */
  rc = fsync(fd);
#else
  rc = fdatasync(fd);
#if OS_VXWORKS
  if( rc==-1 && errno==ENOTSUP ){
    rc = fsync(fd);
  }
#endif /* OS_VXWORKS */
#endif /* ifdef SQLITE_NO_SYNC elif HAVE_FULLFSYNC */

  if( OS_VXWORKS && rc!= -1 ){
    rc = 0;
  }
  return rc;
}

REDO log

REDO log works similarly. The main difference is that we write to log new data instead of old.

creat("/dir/redo.log") - create new REDO log
write("/dir/redo.log", "[check_sum, start, length, new_data]") - write new data to log:
- start - starting position of data
- length - length of new data
- new_data - new data being written
- check_sum - checksum for new data
fsync("/dir/redo.log") - flush new redo log file changes to disk
fsync("/dir") - sync parent directory contents (create redo-log)
write("/dir/data", new_data) - write new data to main file
fsync("/dir/data") - flush changes of main file to disk
unlink("/dir/redo.log") - remove redo-log (mark completed)
fsync("/dir") - sync parent directory contents (remove redo-log)

Main advantage of REDO log, that is widely used by multiple dbms, is that we can return response to user right after we made record to redo-log (step 4).
We can be sure changes will be applied - later (flush to file in background) or during recovery.

As in the UNDO log here we can apply some optimizations. Again, main optimization is to persist this file instead of constant creation/deletions. When we perform commit we just mark record as applied (or can just create new special record that previous record is applied ~ "commit record").

REDO log has alternative name - WAL, Write Ahead Log.

Practical example: WAL in Postgres.

WAL in Postgres

As I said, WAL is widely used in databases. It is used in Oracle, MySQL, Postgres, SQLite, SQL Server.

This example is splited into 2 parts:

COMMIT - save data to WAL
Dirty page flushing to disk

Here we can see advantage that I have highlighted earlier - it's enough to make record in WAL to return response to user and continue processing other requests. Dirty page will be flushed to table file later, during checkpoint.

// 1. "COMMIT;"

// https://github.com/postgres/postgres/blob/cc6e64afda530576d83e331365d36c758495a7cd/src/backend/access/transam/xact.c#L2158
static void
CommitTransaction(void)
{   
    // ...
 RecordTransactionCommit();
    // ...
}

// https://github.com/postgres/postgres/blob/97d85be365443eb4bf84373a7468624762382059/src/backend/access/transam/xact.c#L1284
static TransactionId
RecordTransactionCommit(void)
{
    // ...
    XactLogCommitRecord(GetCurrentTransactionStopTimestamp(),
                        nchildren, children, nrels, rels,
                        ndroppedstats, droppedstats,
                        nmsgs, invalMessages,
                        RelcacheInitFileInval,
                        MyXactFlags,
                        InvalidTransactionId, NULL /* plain commit */ );
    // ...
}

// https://github.com/postgres/postgres/blob/eeefd4280f6e5167d70efabb89586b7d38922d95/src/backend/access/transam/xact.c#L5736
XLogRecPtr
XactLogCommitRecord(TimestampTz commit_time,
     int nsubxacts, TransactionId *subxacts,
     int nrels, RelFileLocator *rels,
     int ndroppedstats, xl_xact_stats_item *droppedstats,
     int nmsgs, SharedInvalidationMessage *msgs,
     bool relcacheInval,
     int xactflags, TransactionId twophase_xid,
     const char *twophase_gid)
{
    // ...
 return XLogInsert(RM_XACT_ID, info);
}

XLogRecPtr
XLogInsertRecord(XLogRecData *rdata,
     XLogRecPtr fpw_lsn,
     uint8 flags,
     int num_fpi,
     bool topxid_included)
{
    // ...
    XLogFlush(EndPos);
    // ...
}

// https://github.com/postgres/postgres/blob/dbfc44716596073b99e093a04e29e774a518f520/src/backend/access/transam/xlog.c#L2728
void
XLogFlush(XLogRecPtr record)
{
 // ...
 XLogWrite(WriteRqst, insertTLI, false);
    // ...
}

// https://github.com/postgres/postgres/blob/dbfc44716596073b99e093a04e29e774a518f520/src/backend/access/transam/xlog.c#L2273
static void
XLogWrite(XLogwrtRqst WriteRqst, TimeLineID tli, bool flexible)
{
 while (/* Have data to write */)
 {
        // 1. Create new WAL segment file or open existing
     if (/* Размер сегмента превышен */)
  {
   openLogFile = XLogFileInit(openLogSegNo, tli);
  }
  if (openLogFile < 0)
  {
   openLogFile = XLogFileOpen(openLogSegNo, tli);
  }

        // 2. Write data to WAL
        do
        {
            written = pg_pwrite(openLogFile, from, nleft, startoffset);
        } while (/* Have data to write */);

        // 3. Flush WAL to disk
        if (finishing_seg)
        {
            issue_xlog_fsync(openLogFile, openLogSegNo, tli);
        }
    }
}

// https://github.com/postgres/postgres/blob/dbfc44716596073b99e093a04e29e774a518f520/src/backend/access/transam/xlog.c#L8516
void
issue_xlog_fsync(int fd, XLogSegNo segno, TimeLineID tli)
{
    // fsync behaviour can be adjusted by GUC (configuration)
 switch (wal_sync_method)
 {
  case WAL_SYNC_METHOD_FSYNC:
      pg_fsync_no_writethrough(fd);
   break;
  case WAL_SYNC_METHOD_FSYNC_WRITETHROUGH:
      pg_fsync_writethrough(fd);
   break;
  case WAL_SYNC_METHOD_FDATASYNC:
      pg_fdatasync(fd);    
   break;
  // ...
 }
}

// 2. Flush "dirty" pages to disk, table file itself

// https://github.com/postgres/postgres/blob/97d85be365443eb4bf84373a7468624762382059/src/backend/storage/buffer/bufmgr.c#L3437
static void
FlushBuffer(BufferDesc *buf, SMgrRelation reln, IOObject io_object,
   IOContext io_context)
{
    // 3. Flush change to WAL
 if (buf_state & BM_PERMANENT)
  XLogFlush(recptr);

    // Flush changes to table file
    smgrwrite(reln,
     BufTagGetForkNum(&buf->tag),
     buf->tag.blockNum,
     bufToWrite,
     false);
}

// https://github.com/postgres/postgres/blob/eeefd4280f6e5167d70efabb89586b7d38922d95/src/include/storage/smgr.h#L121
static inline void
smgrwrite(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum,
    const void *buffer, bool skipFsync)
{
 smgrwritev(reln, forknum, blocknum, &buffer, 1, skipFsync);
}

// https://github.com/postgres/postgres/blob/eeefd4280f6e5167d70efabb89586b7d38922d95/src/backend/storage/smgr/smgr.c#L631
void
smgrwritev(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum,
     const void **buffers, BlockNumber nblocks, bool skipFsync)
{
 smgrsw[reln->smgr_which].smgr_writev(reln, forknum, blocknum,
           buffers, nblocks, skipFsync);
}

// https://github.com/postgres/postgres/blob/eeefd4280f6e5167d70efabb89586b7d38922d95/src/backend/storage/smgr/md.c#L928
void
mdwritev(SMgrRelation reln, ForkNumber forknum, BlockNumber blocknum,
   const void **buffers, BlockNumber nblocks, bool skipFsync)
{
    // 5. Write data to table file
 while (/* Have more data blocks */)
 {
        FileWriteV(v->mdfd_vfd, iov, iovcnt, seekpos,
                   WAIT_EVENT_DATA_FILE_WRITE);
 }

    // 6. Flush data to disk
    register_dirty_segment(reln, forknum, v);
}


// https://github.com/postgres/postgres/blob/6b41ef03306f50602f68593d562cd73d5e39a9b9/src/backend/storage/file/fd.c#L2192
ssize_t
FileWriteV(File file, const struct iovec *iov, int iovcnt, off_t offset,
     uint32 wait_event_info)
{
    // Perform write directly
 returnCode = pg_pwritev(vfdP->fd, iov, iovcnt, offset); 
}

// https://github.com/postgres/postgres/blob/eeefd4280f6e5167d70efabb89586b7d38922d95/src/backend/storage/smgr/md.c#L1353
static void
register_dirty_segment(SMgrRelation reln, ForkNumber forknum, MdfdVec *seg)
{
 if (/* Failed to ask checkpointer to perform fsync */)
 {
        // Perform fsync directly
  FileSync(seg->mdfd_vfd, WAIT_EVENT_DATA_FILE_SYNC);
 }
}

// https://github.com/postgres/postgres/blob/c20d90a41ca869f9c6dd4058ad1c7f5c9ee9d912/src/backend/storage/file/fd.c#L2297
int
FileSync(File file, uint32 wait_event_info)
{
 pg_fsync(VfdCache[file].fd);
}

Segmented log + Snapshot

Since we are talking about WAL, it's worth talking about pair of segmented log and snapshot. Segmented log - is a pattern of representing single "logical" log as multiple "physical" segments.

The benefit we get with this approach is significant. Earlier we have only one big file. Huge systems with highload might have this file have size of thousands TB. You might think that this is OK because we huge amount of storage, but remember that file is stored in file system that might have limit for file size.
Even if we use zfs or xfs (with file size limit of 8 exbibytes) there are engineering problems - maintaince.

But, if we split this big file into several small/medium sized files we get not only ability to grow WAL indefinitely, but also comfortable engineering experience - old WAL segments can be stored in some other place (and possible compressed).

The segmented log itself is a good tool for transactional processing (ability to rollback), but if our server works some months, then this log can become too large and starup time will become impractical (several hours). And here comes "Snapshot" - serialized application state to which WAL records applied up to certain record.

There is illustration from Raft paper that better describes relationship between these 2 components:

As a result, we have 2 "files" representing application state:

Snapshot - file with serialized state after applying some WAL records, and
Segmented log/WAL - multiple files representing single logical sequence of commands that must be applied to state to bring it up to date

Actual state = Snapshot + WAL records.

Finally, main magic - now we can work with both files atomically:

To create or update snapshot - use ACVR/ARVR
When some command comes from user - add to WAL/Segmented log (and return response)
New WAL segments created - ACVR

Also, when using Snapshot we actual do not need old WAL segments, because they are already applied in snapshot. If we were using not segmented log, but a monolog (came up with the name myself), then freeing up a disk space will be problematic: atomic operation will require ARVR, but for large file it will consume to much resources. As for segmented log - we can just remove some log segments (or send to another storage/archive).

Some examples:

Postgres: WAL represented as multiple segments
Apache Kafka: each partition consists of several segments
etcd: data stored in snapshot and segmented WAL
log-cabin: data stored in snapshot and segmented WAL

Actually, we can think of table files in Postgres in terms of Snapshot.
But in Raft snapshot is immutable and Postgres performs changes on such "snapshot" directly.

Such approach for the organization of data storage has advantages:

Fault-tolerant update of application state: fault-tolerant WAL write and snapshot updates
Increase data update speed: response right after WAL saved record + data locality and sequential access when writing to WAL
Replication is more effective: streaming replication of state (just send WAL records sequentially) and/or send immutable snapshot
Application startup speed increases: we need to deserialize application state and apply some records from WAL (instead of applying all records for all time, without snapshot)

Conclusion

In this blog-post we went through the main layers that write request passes. But some topics are not covered:

Network file systems
More deep description of storage devices
Architecture and implementation of different file systems
Comparison of file systems
Ephemeral file systems (i.e. OverlayFS used in Docker)
Cross-platform
Bugs in implementation of each layer
Behaviours in emulators/virtual machines

Hope this article was useful. Bye!

PostgreSQL planner development and debugging

Sergey Solovev — Thu, 06 Feb 2025 15:52:46 +0000

This is translation of my report "Debugging PostgreSQL planner" from PGBootCamp 2024 conference.
You can find repository with source code and another staff here.

In this post we will look at how the PostgreSQL planner works, but on code level (functions and data structures) and how to hack on it's planner.

Go over the main functions used by the planner, main pipeline
Get acquainted with the type system: Node and it's children
How query is represented in code and different data structures that represent it's parts

After some theory we will implement and add a little feature into the planner.

Setting up

Work will be done in folder link a gave earlier (it's cwd)

If you want to reproduce some parts of this post, then you need to setup repository.

All you need to do is to run init.sh. This script:

Downloads PostgreSQL 16.4
Applies patch
Copies development scripts
If VS Code is installed:
1. Copies configuration files to .vscode folder
2. Installs required extensions

For source code downloading you also need to have wget or curl and tar to unzip.
If they are missing install them manually or download archive manually using this link and store it in same directory as init.sh script.

For building and debugging PostgreSQL you also need to have these libraries/executables installed:

libreadline
bison
flex
make
gcc
gdb (or another debugger)
CPAN (for PERL)

You can install them in such way:

# Debian based
sudo apt update
sudo apt install build-essential gdb bison flex libreadline-dev git

# RPM based
sudo yum update
sudo yum install gcc gdb bison flex make readline-devel perl-CPAN git

So, whole setup pipeline is this:

# Clone repository and go to directory with meetup files
git clone https://github.com/TantorLabs/meetups
cd "meetups/2024-09-17_Kazan/Sergey Solovev - Debugging PostgreSQL planner"


# Run initialization script: files downloading, applying patches, etc...
./init.sh

# Go to PostgreSQL source code directory
cd postgresql

# Run build using dev script (parallel with 8 threads)
./dev/build.sh -j 8

# Initialize DB and setup schema for tests
./dev/run.sh --init-db --run-db --psql --script=../schema_constrexcl.sql --stop-db

# Run VS Code (if you have) and open main work file
code . --goto src/backend/optimizer/util/constrexcl.c

After this you can run scripts in queries_constrexcl.sql using psql.

We will work with files:

src/backend/optimizer/util/constrexcl.c
src/backend/optimizer/util/clauses.c
src/backend/optimizer/plan/planmain.c

For full-fledged debugging you should install extra dependencies:

icu-i18n
zstd
zlib
pkg-config

And PERL package IPC::Run.

High-level planner architecture

Now the theory comes in. I will explain some parts not digging too dip. But if you want to touch hard parts you are welcome to READMEs - you can find many of them in PostgreSQL source code repository in src/backend/optimizer. These READMEs explain multiple aspects of the planner workflow.

Query processing algorithm

Let's kick off with query processing pipeline. It can be represented as 4 distinct stages:

Parsing
Rewriting
Planning
Execution

As you can guess we will talk about 3 stage - planning. It also can be divided into 4 stages:

Preprocessing
Optimization
Finding possible paths
Plan creation

1 and 2 stages perform some optimizations. Main difference that the Preprocessing works with Query tree and make "simple" optimizations, i.e. constant folding (calculate result of constant expressions).
But Optimization makes harder optimizations. Such optimizations works with "whole-query" knowledge: JOINs, constants, partitions, tables etc.

During 3 stage we find all possible (excluding those that known to be surely inefficient) ways to execute this query. i.e. table has indexes and after we performed some optimization it may be turned out, that we may not use explicit sorting, because Index only scan provides already sorted data.

On the last stage we find the best path for which we create execution plan. This plan will be used by Executor to actually run query.

Source code organization

In source code these stages organized in such way.

We have "main" functions - entry points for "main" activity:

query_planner - creates access paths for tables (i.e. SeqScan, IndexScan etc..) and also creates and initializes main data structures for further use.
grouping_planner - wrapper for query_planner that adds postprocessing logic after we retrieve data from tables: sorting, grouping etc...
subquery_planner - entry point for planning single subquery. It is called each time we encounter new subquery (recursively).
standard_planner - entry point for whole planner.

Schematically, this can be represented this way.

On top we have standard_planner. It prepares environment and calls subquery_planner for top query (top query is also a subquery, but without parent).

subquery_planner preprocess query tree and calls grouping_planner for running main planning logic.

grouping_planner runs query_planner and after that adds some postprocessing nodes for query plan: sorting, grouping, window functions etc...

query_planner initializes state of planner and performs optimizations. After optimizations it calls make_one_rel to actually find best access path.

make_one_rel finds best access path for whole relation (including strategy for JOIN search).

standard_join_search determines best JOIN strategy. It uses dynamic programming algorithm in opposite to GEQO (Genetic Query Optimizer) which is called when geqo_threshold number of tables in single JOIN reached.

standard_planner()
{
    /* Initialize global planner state */
    subquery_planner()
    {
        /* Query tree preprocessing */
        grouping_planner()
        {
            /* Process GROUP operations: SORT, GROUP BY, WINDOW, SET ops */
            query_planner()
            {
                /* Planner state initialization */
                /* Optimizations */
                /* Find access paths */
                make_one_rel()
                {
                    /* JOIN strategy */
                    standard_join_search()
                }
            }
            /* Add postprocessing nodes (group, sort, etc...) */
        }
        /* Best path choose */
    }
    /* Generating plan for best path */
}

Data structures

Now let's talk about type system.

Nodes and trees

PostgreSQL has it's own type system based on C-style inheritance.

Node - is a base structure for all. It has single member with type NodeTag - type discriminator.

This is simple enum which is created as T_ prefix + name of structure.

All possible nodes are already known, their values defined in src/include/nodes/node.h header file, or, starting with 16 version, are generated using code-gen in src/include/nodes/nodetags.h.

Implementations of these nodes stored in header files in src/include/nodes. Such files ends with *nodes.h:

src/include/nodes/primnodes.h
src/include/nodes/pathnodes.h
src/include/nodes/plannodes.h
src/include/nodes/execnodes.h
src/include/nodes/memnodes.h
src/include/nodes/miscnodes.h
src/include/nodes/replnodes.h
src/include/nodes/parsenodes.h
src/include/nodes/supportnodes.h

Node examples

This diagram shows tree with several Node types grouped by purpose (in my opinion). Totally, there are about 500 types, so take a look at most used ones.

List - is a dynamic array. It can store void *, int, Oid or TransactionId (only one specific type). Using it's tag we can define this data is stored in it:

Type	`NodeTag`
`void *`	`T_List`
`int`	`T_IntList`
`Oid`	`T_OidList`
`TransactionId`	`T_XidList`

NOTE: List is unique in way has 4 different tags for single structure.

Expr - is a base structure for nodes, which can be executed (expressions). You can encounter them in attribute list of SELECT or WHERE constraints. Examples:

Structure	Description	Evaluation result
`Var`	Table column	Value of specified column in tuple of specified table
`Const`	Constant	Constant value
`OpExpr`	Operator	Operator invocation with specified arguments
`FuncExpr`	Function	Function invocation with specified arguments
`BoolExpr`	Boolean expression	Evaluation of boolean expression (`NOT`, `AND`, `OR`)
`SubPlan`	Sub-SELECT	Result of SELECT query execution

Node and Expr are abstract, they do not have own NodeTag value.
They serve as markers: Node - common object of PostgreSQL type system, Expr - expression.

One more group - are planner nodes. They are used by the planner and contain data required for convenient access, i.e. tables in JOIN stores as set, not in tree format.

Query tree representation

First, look at how query is represented in code. This schema shows parts of query with corresponding data structures (nodes).

Query represents query tree for single query. If we find sub-query we create another Query.

Next, table representation. There is an important abstraction - Range Table.

Strictly speaking, Range table - it is everything that can be in FROM clause, data source. Each such element named Range Table Entry (rte):

Table
Function
Subquery
JOIN's
CTE
VALUES (), ()

RangeTblEntry - is a structure, that represents Range Table Entry. To distinguish different types of RTE enum RTEKind is used.

For query in the example we have:

tbl1 - RTE_RELATION
tbl2 - RTE_RELATION
tbl1 JOIN tbl2 - RTE_JOIN
generate_series - RTE_FUNCTION
tbl1 JOIN tbl2 LEFT OUTER JOIN generate_series - RTE_JOIN
(SELECT MAX(id) ... ) - RTE_SUBQUERY

Note that each query has it's own Range Table, so tbl3 - RTE for subquery and it is not in list above.

Query representation in planner

Now, how the planner sees the same query.

Main parts:

PlannerInfo - information about single query (just like Query).

RelOptInfo - planner information about 1 relation: table, function, subqeury, CTE, JOIN etc (just like RangeTblEntry). To distinguish different types of relations RelOptKind (another enum) is used.

In previous section you can notice that some RTEKind are coloured. Let's draw a parallel between RelOptKind and RTEKind.

RELOPT_BASEREL corresponds to RTE_RELATION (table), RTE_FUNCTION (function) and RTE_SUBQUERY (subquery). Basically, we do not need such precise information, all we need are 2 things: name (to be able to address them) and returned attributes list.

Such relations are called base relations. Planner likes to work with them and knowledge of relation origin is not that important.

RELOPT_JOINREL is created for RTE_JOIN. Here we can see one more difference with query tree. In query tree we have many RTE_JOIN (1 for each JOIN), but one only 1. The reason of that hides in storage format - planner stores tables for join as set. This simplifies work required for optimal JOIN search.

Another values of RelOptKind are not covered. But they are also useful, i.e. to support table inheritance or UNION ALL.

Extra structures

In it's work planner uses multiple auxiliary data structures. Now we will cover only 2 of them: RestrictInfo and EquivalenceClass.

RestrictInfo is a restriction (constraint) applied to query. i.e. it can be condition from WHERE or JOIN. In schema's query there are 3 restrictions:

t1.id = t2.id - JOIN condition
t1.value = t2.value - first condition AND in WHERE
1.value = 0 - second condition AND in WHERE

Any conditions/restrictions called qualifications (or quals)

EquivalenceClass is a set of values known to be equal to each other. In same query we have 2 equivalence classes:

t1.id and t2.id
t1.value, t2.value and 0

You can note that EquivalenceClass created using RestrictInfo. Both of them (ds) are important, because the help planner to find more optimal scan paths (examples):

RestrictInfo - which index to use. If we have index on t1.value, then we can use it because of t1.value = 0 qualification
EquivalenceClass - find dependencies between used data. If in previous example we have index on t2.value (not t1.value), then we can not use t1.value = 0 qual, but we t1.value and t2.value are in same EquivalenceClass, so we transitively conclude that t2.value = 0 and can use index.

Implementing Constraint Exclusion

Now, we know enough to begin development of planner.

On practice we implement "Constraint Exclusion" optimization - examine provided constraints to find which are mutually exclusive and remove such relations (tables).

For example, this query can not remove any tuple:

SELECT * FROM tbl1
WHERE 
    value > 0 
  AND
    value <= 0;

Such pattern will have next representation in Nodes:

We are looking for:

BoolExpr - boolean expression with AND condition, which has
Both expressions are OpExpr (operator invocation), having
Opposite operators with
Equal (by value) operands:
Left operand - table column (Var) and
Right operand - constant (Const)

When we find such pattern, so can conclude, that this relation can be removed - it will not return any data.

For simplicity we will search ONLY for this pattern - no OR/NOT, operands do not switch, operators must be placed together, etc.

Implementation

Now we are working in src/backend/optimizer/util/constrexcl.c

Firstly, we create helper function extract_operands - it will extract Var and Const from provided OpExpr.

An operator is also a function, and it also has arguments. They are stored in member args - List. We find binary operator, so it must have 2 arguments. To get length of list function list_length is used:

if (list_length(expr->args) != 2)
{
    return false;
}

According to pattern, first argument must be a table column (Var), and second - a constant (Const). To check type of Node use macro IsA(node, type) and to get first and last elements from List use linitial and llast macros, accordingly.

if (!IsA(linitial(args), Var))
{
    return false;
}

if (!IsA(llast(args), Const))
{
    return false;
}

*out_var = (Var *) linitial(args);
*out_const = (Const *) llast(args);

As a result, the whole function looks like this:

static bool
extract_operands(OpExpr *expr, Var **out_var, Const **out_const)
{
    if (list_length(expr->args) != 2)
    {
        return false;
    }

    if (!IsA(linitial(expr->args), Var))
    {
        return false;
    }

    if (!IsA(llast(expr->args), Const))
    {
        return false;
    }

    *out_var = (Var *) linitial(expr->args);
    *out_const = (Const *) llast(expr->args);
    return true;
}

Let's move on to the implementation of the main logic. It will be located in function is_mutually_exclusive. This function accepts 2 OpExprs and check that they matches the template.

At the beginning use previously written function to extract stored Var and Const from both OpExprs.

{
    Var *left_var;
    Const *left_const;
    Var *right_var;
    Const *right_const;

    if (!extract_operands(left, &left_var, &left_const))
    {
        return false;
    }

    if (!extract_operands(right, &right_var, &right_const))
    {
        return false;
    }
}

Now check that corresponding operands are equal. To check 2 nodes for equality use function equal.

This function accepts to void *, but works only with Node *

/* Table columns */
if (!equal(left_var, right_var))
{
    return false;
}

/* Constants */
if (!equal(left_const, right_const))
{
    return false;
}

Last step - check operators, they must be opposite. This can be done using table in system catalog pg_operator. We need to check column oprnegate - it contains Oid of opposite operator for given.

We will not use this table directly - in header file utils/cache/lsyscache.h there are multiple helper functions for working with system catalog. Function get_negator is one what we want - it returns Oid of opposite operator for given.

For small performance improvement add only 1 check, supposing that if opposite operator for left operator is right, then opposite for right is left. That is, they are symmetrical.

return get_negator(left->opno) == right-opno;

As a result, we have next function:

static bool
is_mutually_exclusive(OpExpr *left, OpExpr *right)
{
    Var *left_var;
    Const *left_const;
    Var *right_var;
    Const *right_const;

    if (!extract_operands(left, &left_var, &left_const))
    {
        return false;
    }
    if (!extract_operands(right, &right_var, &right_const))
    {
        return false;
    }

    if (!equal(left_var, right_var))
    {
        return false;
    }

    if (!equal(left_const, right_const))
    {
        return false;
    }

    return get_negator(left->opno) == right->opno;
}

The last thing we have to do is to add logic to the right place. First, add this to 1 stage - query tree preprocessing. It is contained in subquery_planner.

Main logic of preprocessing is contained in proprocess_expression function. It is a generic function, which passes through all nodes and performs preprocessing (with possible query tree rewriting).

In it we are interested in simplify_and_arguments (src/backend/optimizer/util/clauses.c) - it is called inside preprocess_expression and performs optimization of multiple qualifications in AND expression.

Why do we need this function? Because it has out parameter forceFalse. If it is set to true, then the whole list of qualifications can be replaced with constant FALSE. That is, we do not need to implement this yourself.

This function works as follows. It get list of conditions in AND and then it creates new list by iterating through all elements (performing some logic). We can add our logic to the end of each iteration: store previous qual in separate variable and check with current.

static List *
simplify_and_arguments(List *args,
                       eval_const_expressions_context *context,
                       bool *haveNull, bool *forceFalse)
{
    /* ... */
    while (unprocessed_args)
    {
        /* ... */
        /* Previous and current expressions must be operator invocation */
        if (IsA(arg, OpExpr) && newargs != NIL && IsA(llast(newargs), OpExpr))
        {
            /* Check for mutually exclusion */
            if (is_mutually_exclusive((OpExpr *)arg, (OpExpr *)llast(newargs)))
            {
                /* Telling to replace all expressions with single FALSE */
                *forceFalse = true;
                return NIL;
            }
        }

        newargs = lappend(newargs, arg);
    }

    return newargs;
}

Now test what we have got using this example. We have such schema:

CREATE TABLE tbl1(
    id BIGINT GENERATED ALWAYS AS IDENTITY,
    value INTEGER
);
CREATE TABLE tbl2(
    id BIGINT GENERATED ALWAYS AS IDENTITY,
    value INTEGER
);

To run DB and/or psql you can use script ./dev/run.sh --init-db --run-db --psql
Or using VS Code task Run psql

Test query:

EXPLAIN ANALYZE 
SELECT * FROM tbl1 
WHERE
    value > 0
  AND
    value <= 0;

Baseline is the following (vanilla pg):

                                          QUERY PLAN                                           
-----------------------------------------------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..43.90 rows=11 width=4) (actual time=0.004..0.004 rows=0 loops=1)
   Filter: ((value > 0) AND (value <= 0))
 Planning Time: 0.186 ms
 Execution Time: 0.015 ms
(4 rows)

We can see, that query was actually executed with filter applied. Now rebuild with our changes.

To build sources you can use script ./dev/build.sh, or using VS Code task Build/shortcut Ctrl + Shift + B

Before rerunning do not forget to stop DB - script ./dev/run.sh --stop-db, or using VS Code task Stop DB

And run that query again:

                                     QUERY PLAN                                     
------------------------------------------------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=0) (actual time=0.001..0.002 rows=0 loops=1)
   One-Time Filter: false
 Planning Time: 0.033 ms
 Execution Time: 0.013 ms
(4 rows)

This output tell us, that the whole output was substituted with empty set:

Result - node returning ready-made values
One-Time Filter: false - filter to decline all tuples

Lets run debugger and check how our logic works step by step. Set breakpoint at the start of is_mutually_exclusive.

To attach using debugger (using provided configuration files in this repository):

Obtain PID of backend (if run using scripts in this repo you will have PID shown after start of psql)

Start debugging session in VS Code (i.e. press F5)

Enter PID of backend into popped up window

Enter password if necessary

Run our query and wait for breakpoint to be reached.

Make a step into function extract_operands and look what is inside provided OpExpr.

I will use extension PostgreSQL Hacker Helper to look inside variables instead of built-in variables view.
Why? Because this extension knows about Nodes and reveal them using their real types.
I.e. given base Node * it will check it's type, cast to appropriate type and show that variable.
On next screenshot you can see how it reveals real Nodes inside provided List. Without this extension you have to manually enter numerous amounts of expression in Watch tab.

Reveal it's contents and see multiple members, but we need to check what is inside args - arguments of operator.

We can see 2 elements:

Var - table column
Const - constant

This function must correctly proceed and return true and set out parameters. Continue pressing F10 until we reach return - yes function works as expected.

Next, step out from function and see what is inside another OpExpr, variable right.

We see the same picture - 2 arguments: Var and Const. Now we will step over extract_operands, it should work correctly. But step at first equal function invocation, when comparing Vars.

Let's manually compare contents of both Var

The only thing that is different - location member. But this must be different, because it belongs to another part of query. Make step over and we reach next equal - variables points to the same table column.

Let's compare constants manually again.

Make step over and we reach last step - checking operators Oids. That means constants are also equal.

Take a look at Oids of operators - opno member of OpExpr. Right opno - 521.

Set breakpoint at return in function get_negator and continue execution (F5). When this breakpoint hits we can see that negator of left operator is equal to 523 - operator Oid of right part.

Our logic lives in preprocessing stage. That's significant drawback. Why? Because it handles only simple cases. Such query won't be optimized:

EXPLAIN ANALYZE
SELECT * FROM tbl1 t1 
    JOIN tbl2 t2 
       ON t1.value > 0 
    WHERE t1.value <= 0;

We also have both qualifications to understand this query will not return anything, but our code - does not.

In order to fix this we will move our code to next stage - planner optimizations.

As you can remember, this stage starts in query_planner, because members of PlannerInfo are initialized here. It is very huge structure, but all we need - is simple_rel_array - array of RelOptInfo (structure, representing relation/table).

New logic will work similarly to preprocessing stage: iterate through all qualifications and when find mutually exclusive ones - replace whole list with single FALSE (now we do it ourselves).

In RelOptInfo we need to work with member baserestrictinfo - list of qualifications imposed on the relation. If we have qualifications in JOIN (which relates only to 1 relation), then they will be moved into WHERE list.

We will iterate over all RelOptInfo and over all RestrictInfos in baserestrictinfo. And when find 2 adjacent mutually exclusive expressions, then replace the whole list of qualifications.

This logic will be inside single function which we will add to query_planner. Signature is following:

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
}

root - current query context
rel - relation which we exploring

Firstly, check we have at least 2 qualifications:

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    if (list_length(rel->baserestrictinfo) < 2)
    {
        return;
    }
}

Now main logic comes in - find 2 adjacent mutually exclusive OpExpr. We will store previous OpExpr in separate variable and initialize it with first element in baserestrictinfo array and start iterating from 2 element - use linitial macro and for_each_from correspondingly.

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    ListCell *lc;
    RestrictInfo *prev_rinfo;

    /* Read first element */
    prev_rinfo = linitial(rel->baserestrictinfo);

    /* Start iterating from 2 element */
    for_each_from(lc, rel->baserestrictinfo, 1)
    {
        /* Read next element */
        RestrictInfo *cur_rinfo = (RestrictInfo *)lfirst(lc);
        /* ... */
    }
}

When we get next element check previous and current qualifications both are OpExpr (using IsA) and (if so) check they are mutually exclusive (using is_mutually_exclusive).

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    /* Both qualifications are operator call */
    if (IsA(prev_rinfo->clause, OpExpr) && IsA(cur_rinfo->clause, OpExpr) &&
        /* Qualifications are mutually exclusive */
        is_mutually_exclusive((OpExpr *)prev_rinfo->clause, (OpExpr *)cur_rinfo->clause))
    {
        /* ... */
    }
}

If the check is successful, then replace the whole list with single element, constant FALSE and we are done.

This can be done using 3 separate functions:

makeBoolConst - create BoolExpr, SQL boolean constant
make_restrictinfo - create RestrictInfo with previously created boolean constant (it has multiple flags - we don't need them, so they are all false)
list_make1 - create List with 1 element

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    /* ... */

    /* Create qualification */
    RestrictInfo *false_rinfo = make_restrictinfo(root,
                                                  /* Create constant `FALSE` */
                                                  (Expr *)makeBoolConst(false, false),
                                                  false, false, false, false,
                                                  0, NULL, NULL, NULL);
    /* Create single element List */
    rel->baserestrictinfo = list_make1(false_rinfo);
}

But if check is not successful, then just update previous RestrictInfo variable.

The whole function looks like this:

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    ListCell *lc;
    RestrictInfo *prev_rinfo;

    if (list_length(rel->baserestrictinfo) < 2)
    {
        return;
    }

    prev_rinfo = linitial(rel->baserestrictinfo);

    for_each_from(lc, rel->baserestrictinfo, 1)
    {
        RestrictInfo *cur_rinfo = (RestrictInfo *)lfirst(lc);
        if (IsA(prev_rinfo->clause, OpExpr) && IsA(cur_rinfo->clause, OpExpr) &&
            is_mutually_exclusive((OpExpr *)prev_rinfo->clause, (OpExpr *)cur_rinfo->clause))
        {
            RestrictInfo *false_rinfo = make_restrictinfo(root,
                                                          (Expr *)makeBoolConst(false, false),
                                                          false, false, false, false,
                                                          0, NULL, NULL, NULL);
            rel->baserestrictinfo = list_make1(false_rinfo);
            return;
        }

        prev_rinfo = cur_rinfo;
    }
}

We wrote function for single relation, but query can have multple of them - simple_rel_array member of PlannerInfo. We will write another function collaptse_mutually_exclusive_quals for this:

void 
collapse_mutually_exclusive_quals(PlannerInfo *root)
{
}

We need to traverse the entire array and apply logic to each. But even here it's not that simple. First remark - array indexing starts with 1, not 0. This is because indexes of this array plays as IDs for range table entries in range table (Query->rtable). 0 element is always NULL. So loop looks like this:

void 
collapse_mutually_exclusive_quals(PlannerInfo *root)
{
    for (size_t i = 1; i < root->simple_rel_array_size; i++)
    {
        RelOptInfo *rel = root->simple_rel_array[i];
    }
}

Second remark - type of relation. As you can remember, RelOptInfo can be created for tables and JOINs, functions, etc. We need to check this.

Initially, we were designed logic to work with tables, but we do not need table-specific features (like storage format or something else) - all we need if just to get return attributes (columns), we do not event need name of table.

If you remeber, such relations called base rel. So starting from now we work with base relations - check that RelOptInfo is a base relation. This info stored in reloptkind member.

void 
collapse_mutually_exclusive_quals(PlannerInfo *root)
{
    for (size_t i = 1; i < root->simple_rel_array_size; i++)
    {
        RelOptInfo *rel = root->simple_rel_array[i];

        if (rel->reloptkind == RELOPT_BASEREL)
        {
            collapse_mutually_exclusive_quals_for_rel(root, rel);
        }
    }
}

Business logic is implemented, now it's time to integrate it into planner. We:

Use baserestrictinfo member
That stored in RelOptInfo
Which stored in simple_rel_array member

So add our code, when simple_rel_array will be initialized. If we study the code a little, we find that this is done in add_base_rels_to_query function, so add our code right after that function (in src/backend/optimizer/plan/planmain.c):

RelOptInfo *
query_planner(PlannerInfo *root,
              query_pathkeys_callback qp_callback, void *qp_extra)
{
    /* ... */
    add_base_rels_to_query(root, (Node *) parse->jointree);

    /* Constraint Exclusion */
    collapse_mutually_exclusive_quals(root);
}

Do not forget to remove our code from 1 stage (query tree preprocessing) in clause.c file

Stop old DB, rebuild, run psql and execute our query:

                                          QUERY PLAN                                           
-----------------------------------------------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..43.90 rows=11 width=4) (actual time=0.007..0.008 rows=0 loops=1)
   Filter: ((value > 0) AND (value <= 0))
 Planning Time: 0.042 ms
 Execution Time: 0.020 ms
(4 rows)

Our patch did not work, planner still uses table scanning. Let's run debugger and watch what happened. Set breakpoint at collapse_mutually_exclusive_quals function start and run query:

Make some steps (stepping inside other functions) and we will find, that check for list baserestrictinfo length did not pass - planner thinks that it is empty (NULL - empty list)

The reason is because most of main data structures (such PlannerInfo or RelOptInfo) very huge, so initialized during the work (on the fly), there is no single function doing that - initialization is split between multple functions.
We supposed that add_base_rels_to_query created baserestrictinfo then each element is initialized too. But that not true in this case - each RelOptInfo is not fully initialized, just basic properties.

So, this bug is fixed by proper finding place where baserestrictinfo array is initialized and available for use. It is deconstruct_join_tree - add our code right after this function invocation.

RelOptInfo *
query_planner(PlannerInfo *root,
              query_pathkeys_callback qp_callback, void *qp_extra)
{
    /* ... */
    joinlist = deconstruct_jointree(root);

    /* Move our code invocation down */
    collapse_mutually_exclusive_quals(root);
}

Stop DB, rebuild and run query again:

                                     QUERY PLAN                                     
------------------------------------------------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=0) (actual time=0.001..0.002 rows=0 loops=1)
   One-Time Filter: false
 Planning Time: 0.125 ms
 Execution Time: 0.012 ms
(4 rows)

Constraint Exclusion logic successfully applied to test query. Now let's test it on new case, with JOIN:

EXPLAIN ANALYZE 
SELECT * FROM tbl1 t1 
JOIN tbl2 t2 
   ON t1.value > 0 
WHERE t1.value <= 0;

When running this query, we get next result:

postgres=# EXPLAIN ANALYZE 
SELECT * FROM tbl1 t1 
JOIN tbl2 t2 
   ON t1.value > 0 
WHERE t1.value <= 0;
server closed the connection unexpectedly
        This probably means the server terminated abnormally
        before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.
The connection to the server was lost. Attempting reset: Failed.
!?>

Something went wrong: backend crashed and we can not send queries anymore. Log file will not get enough information to detect cause of error, so we will debug it.

Start psql, attach debugger, set breakpoint on collapse_mutually_exclusive_quals function and run query. When that breakpoint hits make some steps in for loop and stop at if statement with reloptkind check. Make another step and we stop at collapse_mutually_exclusive_quals_for_rel function invocation. Which means given rel is base rel - t1 or t2.

Make step into and we will stop at baserestrictinfo list length checking. If we look at this list we will see 2 RestrictInfo: both have OpExpr with Var and Const at each side respectively. That means planner moved condition from JOIN into WHERE list.

Next, after making some steps we test RestrictInfos to be mutually exclusive.

Test passed and now we are creating list with single constant FALSE.

After that we return to parent function and move to next relation. It also passes "base rel" check and collapse_mutually_exclusive_quals_for_rel in called. But this time baserestrictinfo list is empty - this must be t2 table, because it does not have any qualifications.

We return to parent again and move to next RelOptInfo (last). And when we stepping in if statement we get SEGFAULT. If we look at more close, we will see that rel is NULL.

This not extraordinary - this is normal situation. Why? Because we did not read comments for simple_rel_array:

struct PlannerInfo
{
    /*
     * simple_rel_array holds pointers to "base rels" and "other rels" (see
     * comments for RelOptInfo for more info).  It is indexed by rangetable
     * index (so entry 0 is always wasted).  Entries can be NULL when an RTE
     * does not correspond to a base relation, such as a join RTE or an
     * unreferenced view RTE; or if the RelOptInfo hasn't been made yet.
     */
    struct RelOptInfo **simple_rel_array pg_node_attr(array_size(simple_rel_array_size));
}

Take a closer look at 3 sentence: "Entries can be NULL when an RTE does not correspond to a base relation ...". So, if our rel was NULL, then it was not a base relation. What was that? Look at the corresponding rte:

It was JOIN, so that is because no RelOptInfo pointer was there.

Fix this bug with checking that rel is not NULL:

void 
collapse_mutually_exclusive_quals(PlannerInfo *root)
{
    for (size_t i = 1; i < root->simple_rel_array_size; i++)
    {
        RelOptInfo *rel = root->simple_rel_array[i];

        if (rel != NULL && rel->reloptkind == RELOPT_BASEREL)
        {
            collapse_mutually_exclusive_quals_for_rel(root, rel);
        }
    }
}

Also add a little Assert just for sure:

static void
collapse_mutually_exclusive_quals_for_rel(PlannerInfo *root, RelOptInfo *rel)
{
    ListCell *lc;
    RestrictInfo *prev_rinfo;

    Assert(rel != NULL);

    if (list_length(rel->baserestrictinfo) < 2)
    {
        return;
    }

    /* ... */
}

Stop DB, rebuild and run query:

                                     QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Result  (cost=0.00..0.00 rows=0 width=24) (actual time=0.002..0.002 rows=0 loops=1)
   One-Time Filter: false
 Planning Time: 0.046 ms
 Execution Time: 0.012 ms
(4 rows)

The bug is fixed, query executed successfully.

But it's worth nothing that it is not good to delete such information (list of predicates): we delete known information and wasing resources trying to apply this optimization.

Best way to do this is just to create new Path (Result with empty output) when we starting to generate all possible paths. And this is real PostgreSQL implementation. When GUC setting constraint_exclusion is set to on (by default partition to discard unnecessary partitions) PostgreSQL starts to find such mutually exclusive qualifications.

If we dig down we will see that constraint exclusion logic applied in function relation_excluded_by_constraints (self-explanatory name) which is called inside set_rel_size (when computing sizes for each relation to find best path). This function has a bit of complicated logic, but in short it does what we have done - traverse through all predicates and find the ones that are exclusive (O(n^2) complexity compared to O(n) in our implementation). Also, this tries to find mutually exclusive predicates by all possible means: trying to commute operators, if the function is immutable it will be evaluated (real function invocation) and so on.

I found this piece of code that find mutually exclusive operators:

static bool
operator_predicate_proof(Expr *predicate, Node *clause,
                         bool refute_it, bool weak)
{
    OpExpr *pred_opexpr,
           *clause_opexpr;
    Oid pred_collation,
        clause_collation;
    Oid pred_op,
        clause_op,
        test_op;
    Node *pred_leftop,
         *pred_rightop,
         *clause_leftop,
         *clause_rightop;

    /*
     * Both expressions must be binary opclauses, else we can't do anything.
     *
     * Note: in future we might extend this logic to other operator-based
     * constructs such as DistinctExpr.  But the planner isn't very smart
     * about DistinctExpr in general, and this probably isn't the first place
     * to fix if you want to improve that.
     */
    if (!is_opclause(predicate))
        return false;
    pred_opexpr = (OpExpr *) predicate;
    if (list_length(pred_opexpr->args) != 2)
        return false;
    if (!is_opclause(clause))
        return false;
    clause_opexpr = (OpExpr *) clause;
    if (list_length(clause_opexpr->args) != 2)
        return false;

    /*
     * If they're marked with different collations then we can't do anything.
     * This is a cheap test so let's get it out of the way early.
     */
    pred_collation = pred_opexpr->inputcollid;
    clause_collation = clause_opexpr->inputcollid;
    if (pred_collation != clause_collation)
        return false;

    /* Grab the operator OIDs now too.  We may commute these below. */
    pred_op = pred_opexpr->opno;
    clause_op = clause_opexpr->opno;

    /*
     * We have to match up at least one pair of input expressions.
     */
    pred_leftop = (Node *) linitial(pred_opexpr->args);
    pred_rightop = (Node *) lsecond(pred_opexpr->args);
    clause_leftop = (Node *) linitial(clause_opexpr->args);
    clause_rightop = (Node *) lsecond(clause_opexpr->args);

    if (equal(pred_leftop, clause_leftop))
    {
        if (equal(pred_rightop, clause_rightop))
        {
            /* We have x op1 y and x op2 y */
            return get_negator(pred_op) == clause_op;
        }
    }
    /* Omitted */
}

As you can see this code is very similar to ours, except collation checking. But the most interesting part in the omitted part (last). That's what i was talking about - all possible ways to find such operators: checking for different order of operands, test for commutative operators, checking for constant or constant function, operator evaluation etc.

Lifehacks

In the last part I will give you some lifehacks for the planner development.

Disable password prompt

When we attach with debugger to backend you will be prompted a password. This is a security feature, but not very convinient during development.

You can disable this:

Using configuration file /etc/sysctl.d/10-ptrace.conf - set kernel.yama.ptrace_scope = 0
By writing 0 to /proc/sys/kernel/yama/ptrace_scope - echo 0 | sudo tee /proc/sys/kernel/yama/ptrace_scope

You should combine them: apply 2 method to disable password prompt immediately and 1 to save changes between reboots. Otherwise you must use 2 method after each reboot.

Display backend PID

psql has it's own configuration file - .psqlrc. It contains commands to be executed when psql starts.

We need to now PID of backend to attach with the debugger. So this is good place to insert our SELECT pg_backend_pid();.

Next set environment variable PSQLRC equal to path to our .psqlrc - PSQLRC="/home/user/project/build/.psqlrc" (do not forget to export it to psql)

After that PID of backend will be displayed when psql starts.

TIP: using psql feature to write output to external file you can save PID in file for later use. For example, you can integrate this into VS Code to automatically attach to backend when pressing F5 (start debugging).

PostgreSQL debugging tools

Of course PostgreSQL has it's own debugging facilities. Most of them are related to Node displaying.

The first, in header file print.h declared many functions to output Node structures to log in custom format (not json/yaml).

The most basic function - pprint. It displays any provided Node to stdout. Other functions are specialized - print_expr, print_pathkeys, print_tl, print_slot, print_rt.

The second, 2 special feature macros. They must be enabled during compilation:

OPTIMIZER_DEBUG - common planner
GEQO_DEBUG - GEQO

If they are defined, then after certain stage result of it's work will be dumped to log.

The third, GUC settings:

debug_print_parse
debug_print_rewritten
debug_print_plan

If the setting is set to on, then after corresponding stage (query parsing, query tree rewriting and planning) result of it's work will be dumped to log.

But they output result, not separte steps.

Automation

This is not longer lifehack, but help

When working with PostgreSQL we can define 4 main stages:

Bootstrapping (configure invocation)
Compilation
Tests running
Run DB and psql

For each step we can write automation scripts. But when we are working with VS Code we can get a big benefit by integrating them into VS Code. You can do this using VS Code Tasks. For example, task for building can be the following:

{
    "label": "Build",
    "detail": "Build PostgreSQL and install into directory",
    "type": "shell",
    "command": "${workspaceFolder}/build.sh",
    "problemMatcher": [],
    "group": {
        "kind": "build",
        "isDefault": true
    }
}

With such setting you can run building by pressing Ctrl + Shift + B shortcut.

I have developed some scripts for automation. They are lying in dev folder. You can run them from terminal or whatever you want. In this folder you also can find README with tutorial and usage examples.

Also, there are VS Code configuration files for integration with these scripts. They are lying in .vscode folder.

PostgreSQL Hacker Helper

PostgreSQL Hacker Helper is a VS Code extension for PostgreSQL development.

Main feature of it is Node variables revealing using according to value of NodeTag. The extension known about them and when finds one cast it type according to it's NodeTag and displays in that way.

You have already seen this extensions, on screenshots, then we were debugging source code and revealing OpExpr, Var, Const variables.

As you can notice, it also knows about List - shows each member of array according to their NodeTag, not plain Node *.

It has a lot more features, like formatting using pgindent or extension files bootstrapping.

The extension supports almost all PostgreSQL versions - starting from 8.

Link to the extension here.

What we've done

In summary, we:

Got acquainted with planner work pipeline, it's main stages and corresponding functions
Learnt PostgreSQL type system with most used functions for work with them
Designed and implement our own optimization for the planner
Add our logic to different pipeline stages
Fixed code using the debugger# PostgreSQL planner development and debugging

And main thing: do not be afraid to try PostgreSQL Hacker Helper extension!

Forem: Sergey Solovev

Create and debug PostgreSQL extension using VS Code

Preparation

PostgreSQL setup

VS Code setup

Creating initial files

Initial code

Examine queries

is_sus_query implementation

contains_predicates implementation

Testing

Further improvements

Conclusion

Tip & tricks

The PostgreSQL Hacker Helper extension is one year old

pg_dphyp: teach PostgreSQL to JOIN tables in a different way

Join ordering algorithms

DPsize

GEQO

DPhyp

pg_dphyp extension

Set representation

DP-table

Hypergraph creation

Disconnected subgraphs

Hypergraph representation

Query plan building

Optimal neighborhood calculation

MySQL approach

Suffix cache

1-layered cache

2-layered cache

3-layered cache

Perfect cache

Hyperedge indexing

Query complexity

Testing

Conclusions

How to handle files?

Application

Operating system

Special syscall to flush data

Linux

Windows

macOS

Bypass OS page cache

Linux

Windows

Directory sync

Linux

Windows

fsync errors

fsyncgate

File system

File system integrity

Magic number

Checksum

File System consistency model

Atomicity

Reorderings

Write barrier

Other file systems

NTFS

APFS

Appliction fsync error handling

Storage

Time to failure

ECC

Access controller

Persistence properties

Atomicity

PowerSafe OverWrite

Runtime

Key takeways

File operations patterns

Create new file

File modification

Change of a small file

UNDO log

REDO log

`is_sus_query` implementation

`contains_predicates` implementation

Appliction `fsync` error handling