The Aurora DSQL paper finally dropped. Reading it yesterday was an interesting experience, because I spent two years (2022-23) working with the AWS team that designed and built Aurora DSQL. Since I have been very familiar with the architecture, the paper's overview description of the system didn't excite me much. And if I am being honest, reading the paper also felt a bit dry, most likely because I am not doing the usual extra thinking to explore/understand the ideas in the paper. But taking a step back today, and leaving my subjective experience aside, I will try to elaborate on how the DSQL architecture is actually built on a set of aggressive and opinionated engineering bets. 

If I had to explain this architecture in a single sentence (just as I used to do for other teams at AWS) it would be this: We took a traditional monolithic database and blew out every single component into an independent, horizontally scalable service.

Exploding the Monolith

DSQL divides the database into the following specialized services:

• Query Processors (QP): Stateless virtual machines that run a custom PostgreSQL engine to parse queries and buffer writes locally.
• Storage Nodes: Sharded nodes that hold the data and use multiversion concurrency control (MVCC) to serve historical data to QP instantly.
• Adjudicators: The conflict-resolution layer that checks if a transaction handed of to them by QP is safe to commit.
• Journals: A highly available replication log that durably saves transactions across zones or regions. (Good for short term durability before this reaches the storage nodes. See my MemoryDB review.) 
• Crossbars: The routing layer that reads the updates from the Journals and sends changes to the right Storage Nodes.

The Big Architectural Bets in DSQL Design

Well, in addition to fully committing to the disaggregation principle, here are the other big bets in DSQL design.

The Synchronized Clock Bet: To get reads without coordination, DSQL relies entirely on highly synchronized physical clocks, in this case AWS TimeSync. A QP just checks its local clock and asks storage for data from that exact microsecond.

No Pessimistic Locking: Optimistic Concurrency Control (OCC) may lead to high abort rates for databases, but DSQL makes it work by pairing it with MVCC under Snapshot Isolation. Because readers look at a snapshot of the past, read-write conflicts are impossible. Awesome, but what about write-skew? When needed, customers should just use FOR UPDATE, and also design their schemas to force write-write conflicts for business logic violations.

Eventual Consistency is Dead: DSQL provides strong consistency (linearizability), arguing that developers simply cannot write correct business logic on eventually consistent systems. It’s a subtle point, but linearizability (a guarantee about single-object real-time operations) and snapshot isolation (a guarantee about multi-object transaction visibility) control different things, as Jepsen's consistency models outline. DSQL offers a consistent snapshot for your snapshot-isolated transactions, and that individual key operations strictly respect real-time ordering.

Forcing Guardrails: DSQL hard-caps transactions at 3,000 rows and 10MiB. The paper cites Little's Law to justify this, essentially forcing users to accept smaller transactions in exchange for highly predictable stable tail latency.

Linearized 2PC: For transactions that span multiple Adjudicators, traditional Two-Phase Commit (2PC) is too slow over wide area networks as it requires 2RTTs. DSQL uses a "Warp-inspired" trick where Adjudicators vote, but only the leader writes the final commit to its single Journal. This avoids coordinating multiple logs.

The Payoff

Independent Scalability: Compute, commit logic, and storage are completely separated. If you need more read capacity, you add storage nodes. If you have a spike in connections, the system spins up more QPs. You can also tune/optimize them separately, for example, potentially reconfigure adjudicator-range placement based on access patterns.

0-RTT Consistent Reads: Because the QP assigns a local timestamp and storage handles the rest, reading data requires zero coordination with a leader. It is almost as fast as your network latency to the storage node. This is a big win because in OLTP SQL, reads are significantly more common than writes. Even most writes (like UPDATES or INSERTS with unique indexes) are actually reads first.

1-RTT (or 1.5 RTT) Commits: Whether you write one row or a hundred, coordination only happens once at commit time, costing just 1 RTT (or slightly more for a multi-shard commit).

No "Slow Lock Holder" Problem: Because there are no pessimistic locks, a developer going to lunch with an open transaction terminal (exact quote from the paper) cannot bring down the database. Readers never block writers, and writers never block readers.

While it is hard to critique my old team, this won't be a true Murat Buffalo (now Bay Area?) review without pointing out the tradeoffs and shortcomings in the paper. Because of the long read-modify-commit duration during a transaction, DSQL may be prone to write-write conflicts on hot keys. This limits how many back-to-back operations you can squeeze into a single row (which is bad application design anyway). Under heavy contention, transactions will abort, whereas a traditional database may have queued them up. If two regions write to the same key, OCC will abort one of them, and unfortunately this conflict is only detected at commit time, meaning you pay the WAN network latency penalty before finding out you have to retry.

While the paper couldn't provide extensive evaluation, quantitative data on user adoption or business payoff, it does provide a candid Lessons Learned section which talks about some friction with respect to Foreign Key Constraints and high-locality sequences.

Building at Scale

I have one final takeaway that is somewhat counterintuitive: building a completely novel global production database didn't actually feel like as much effort as it should have.

Yes, it was a lot of work, but the execution felt surprisingly smooth after the team got going. I attribute this to two things: a great upfront design, and a deliberate choice to avoid reinventing the wheel. Rather than building everything from scratch, the team used the PostgreSQL engine for SQL parsing, execution, and the client protocol, while discarding its local storage and transaction processing layers. We didn't build a new replication log; we used AWS's existing internal Journal service. We were also equipped with hard-earned lessons from preceding AWS database projects, like JournalDB and the unfortunately named QLDB (Quantum Ledger Database).  Beyond the tooling, the team dynamics were excellent. Marc Brooker is technically brilliant, and he did a masterful job leading a talented team of principal engineers. Our weekly whiteboard thinking sessions were a lot of fun. Because the foundational architecture was so well-designed, the actual development felt significantly easier than at least what I would expect for a product of this magnitude. (But then again, I wasn't with the team for the last year of the project!)

Many databases use B+tree indexes, but they all differ. It's a sorted structure. The leaf pages are logically sorted so that a specific key value belongs to one page. A lookup by value reaches a single leaf page and either directly finds an entry for that value or immediately knows there's no entry with that key. When a page becomes full, it is split into two pages, each covering its own dedicated range. To find the right page, an internal page holds the range of values for the pages below. This internal page can become full, and a new level is added above it. Finally, at the highest level, there's a single internal page that is the root. A lookup always starts at the root and goes down to the leaves, following the branches of internal pages. In a traditional B+tree lookup, the cost is proportional to the height of the tree because the search starts at the root and descends to a leaf:

• 1 page to read when all fits in one leaf that is also the root (0 levels of internal pages, total height is 1). With small keys, this level can typically index hundreds of rows.
• 2 pages to read when there's one root that can list all leaf pages (1 level of internal page, total height is 2). With small keys, this level can typically index tens or hundreds of thousands of rows.
• 3 pages to read when there's one level of branches under the root (so 2 levels of internal pages, total height is 3). With small keys, this level can typically index millions of rows.

This means that finding one key within ten million rows may require traversing 3 index pages, where most of them are probably in cache given the small number of branches compared to the leaves. For a given index size, whatever the value you are looking for, it's always the same number of pages to read because the index is balanced (the commonly accepted meaning of the B in B+tree). This property is maintained because any page can split, but only splitting the root adds another level.

I've described how the height of an index can increase, impacting the cost of the lookup, as data grows, but do you know if your database can reduce the height of the B+tree when data is deleted?

I've been working with Oracle Database for a long time, and the answer is easy: the height of the B+tree index never decreases, even if you delete all rows, even if you coalesce the index, even if you shrink the index, until you completely rebuild it. Then I worked with PostgreSQL, which is famous for index bloat, and realized that the effective B+tree height can decrease even without a rebuild.

Oracle Database: reclaim levels with rebuild

I created a table with five million rows and an index on the ID, using a random 16-byte UUID:

drop table if exists bloat;

create table bloat ( id raw(16) constraint bloat_pkey primary key);

insert into bloat select uuid() from xmltable('1 to 5000000');

commit;

exec dbms_stats.gather_table_stats(user,'bloat');

I collect statistics on the logical structure of the index:

analyze index bloat_pkey validate structure;

select height-1 blevel, blocks pages, lf_blks leaf_pages, br_blks internal_pages from index_stats;

The result shows two levels of branches, with 40 internal pages including the root. There's one root at level 0 and 39 branches at level 1, addressing 24837 leaves:

    BLEVEL      PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
         2      25728      24837             40

This means that finding a key in the index requires reading 3 pages. I can verify this with the execution plan:

set linesize 200
alter session set statistics_level=all;
select * from bloat where id = uuid_to_raw('00000000000000000000000000000000');
select * from dbms_xplan.display_cursor(format=>'allstats last');

This confirms that three buffers were read before determining that the key does not exist:

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SQL_ID  7jxrrzwtd7aqd, child number 0
-------------------------------------
select * from bloat where id = uuid_to_raw('00000000000000000000000000000000')

Plan hash value: 1755540699

------------------------------------------------------------------------------------------
| Id  | Operation         | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            |      1 |        |      0 |00:00:00.01 |       3 |
|*  1 |  INDEX UNIQUE SCAN| BLOAT_PKEY |      1 |      1 |      0 |00:00:00.01 |       3 |
------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("ID"=UUID_TO_RAW('00000000000000000000000000000000'))

I delete all rows with an intermediate commit because undo is limited:

delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;

The lookup still traverses three levels of logically empty pages:

------------------------------------------------------------------------------------------
| Id  | Operation         | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            |      1 |        |      0 |00:00:00.01 |       3 |
|*  1 |  INDEX UNIQUE SCAN| BLOAT_PKEY |      1 |      1 |      0 |00:00:00.01 |       3 |
------------------------------------------------------------------------------------------

The B-tree index didn't change after the delete - same height and same number of pages:

    BLEVEL      PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
         2      25728      24837             40

Oracle can merge adjacent pages with a coalesce command:

alter index bloat_pkey coalesce;

This reduced the number of leaf and internal pages to the minimum possible while preserving the existing tree structure: one leaf page, one branch page, and the root page. The number of levels doesn't change, and the cost of the lookup remains the same:

    BLEVEL      PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
         2      25728          1              2

------------------------------------------------------------------------------------------
| Id  | Operation         | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            |      1 |        |      0 |00:00:00.01 |       3 |
|*  1 |  INDEX UNIQUE SCAN| BLOAT_PKEY |      1 |      1 |      0 |00:00:00.01 |       3 |
------------------------------------------------------------------------------------------

Oracle can shrink the allocated blocks:

alter index bloat_pkey shrink space;

This didn't reduce anything further:

    BLEVEL      PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
         2      25728          1              2


------------------------------------------------------------------------------------------
| Id  | Operation         | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            |      1 |        |      0 |00:00:00.01 |       3 |
|*  1 |  INDEX UNIQUE SCAN| BLOAT_PKEY |      1 |      1 |      0 |00:00:00.01 |       3 |
------------------------------------------------------------------------------------------

Finally, I need to rebuild the index to get one with a height that corresponds to an empty table:

alter index bloat_pkey rebuild online;

This is the correct size of an index with no rows - a single page that serves as both the root and the leaf:

    BLEVEL      PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
         0          8          1              0

------------------------------------------------------------------------------------------
| Id  | Operation         | Name       | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |            |      1 |        |      0 |00:00:00.01 |       1 |
|*  1 |  INDEX UNIQUE SCAN| BLOAT_PKEY |      1 |      1 |      0 |00:00:00.01 |       1 |
------------------------------------------------------------------------------------------

Oracle Database indexes can increase in height, but the height does not decrease automatically after deletions. Reclaiming levels requires an index rebuild. When a large amount of data is deleted, the cost of an index scan from the root to the leaf remains high until the index is rebuilt.

PostgreSQL

Here is a similar table containing five million rows:

drop table if exists bloat;
create table bloat ( id uuid constraint bloat_pkey primary key);
insert into bloat select uuidv4() from generate_series(1,5000000);
vacuum analyze bloat;

I use pgstattuple to collect and aggregate the index statistics:

create extension if not exists pgstattuple;
select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');

The result shows two levels of branches, with 111 internal pages including the root. There's one root at level 0 and 110 branches at level 1, addressing 24607 leaves:

 blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
      2 | 24719 |      24607 |            111

EXPLAIN ANALYZE shows an Index Only Scan that reads 3 pages, the root, one branch, and the leaf:

postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Only Scan using bloat_pkey on bloat (actual time=0.019..0.020 rows=0.00 loops=1)
   Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=3
 Planning Time: 0.065 ms
 Execution Time: 0.034 ms
(7 rows)

I delete all rows and run the same:

postgres=# delete from bloat;

DELETE 5000000

postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';

                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Only Scan using bloat_pkey on bloat (actual time=0.018..0.018 rows=0.00 loops=1)
   Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=3
 Planning Time: 0.066 ms
 Execution Time: 0.032 ms
(7 rows)

postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');

 blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
      2 | 24719 |      24607 |            111

The B-tree size and level remain the same after a delete because MVCC information is still present for transactions that may read a previous snapshot. After a while, autovacuum removes the dead index entries that are no longer visible to any transaction (you can also run VACUUM manually).

The PostgreSQL planner may prefer a sequential scan on an empty table, so I force an index scan to count how many index pages are read to find a key:

postgres=# set enable_seqscan to off;
SET

postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';

                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Only Scan using bloat_pkey on bloat (actual time=0.013..0.013 rows=0.00 loops=1)
   Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=1
 Planning Time: 0.158 ms
 Execution Time: 0.027 ms
(7 rows)

Only one page is read because a single root is sufficient to list the index entries of an empty table. No rebuild is required: regular autovacuum is sufficient.

If I check the index statistics, they still show two levels, with one root, one leaf, and a branch between them:

postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
 blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
      2 | 24719 |          1 |              2
(1 row)

You don't need a COALESCE command, as in Oracle, to merge adjacent blocks in a level. PostgreSQL did this after the regular VACUUM. However, similar to Oracle Database, the B-tree's height didn't decrease. Only its width at each level was reduced, with each level maintaining at least one page.

However, PostgreSQL can avoid traversing redundant upper levels. The purpose of internal pages is to determine which page to read at the lower level. If there's only one page at the level under the root, there's no need to read the root. We can start the scan at the highest level that has a single page. PostgreSQL keeps track of it as the "fast root". I can verify this from the index metadata, which I can read with the pageinspect extension:

postgres=#  create extension if not exists pageinspect;

CREATE EXTENSION

postgres=#  select * from bt_metap('bloat_pkey');

 magic  | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
 340322 |       4 |  295 |     2 |    14512 |         0 |                     24715 |                      -1 | t
(1 row)

The physical number of levels is "level," and the true root is at block 295, but there's another root, "fastroot," with a different address, 14512. It was one of the internal pages when the table was full, or even a leaf in our case. As data was deleted, it remained alone at its level, and the levels above, up to the root, had a single entry, in a single page.

PostgreSQL records this page as the fast root and can start searches from it, bypassing upper levels that contain only a single pointer. Because the table is now empty, this page effectively serves as a leaf page. That's how an Index Scan reads only one page. The logical level, or "fastlevel," is recorded in the index's metadata page so that the query planner can evaluate the cost correctly.

I don't need to rebuild this index, but I can:

postgres=# reindex index concurrently bloat_pkey ;
REINDEX
postgres=#  select * from bt_metap('bloat_pkey');
 magic  | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
 340322 |       4 |    0 |     0 |        0 |         0 |                         0 |                      -1 | t
(1 row)

postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
 blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
      0 |     1 |          0 |              0
(1 row)

After the rebuild, all statistics show that the B-tree has a single page.

postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';

                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Only Scan using bloat_pkey on bloat (actual time=0.005..0.005 rows=0.00 loops=1)
   Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=2
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.067 ms
 Execution Time: 0.021 ms
(9 rows)

You may wonder why two pages are read during execution. A clue is that one page is read during planning, even if you run it many times.

This is due to the rebuild with no DML to read and cache the metapage. Let's insert one row:

postgres=# insert into bloat select uuidv4();

INSERT 0 1

postgres=#  explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';

                                       QUERY PLAN
----------------------------------------------------------------------------------------
 Index Only Scan using bloat_pkey on bloat (actual time=0.010..0.010 rows=0.00 loops=1)
   Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=1
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.069 ms
 Execution Time: 0.024 ms
(9 rows)

postgres=#

During the planning phase, the system reads the index metapage (1 buffer) to obtain accurate statistics for cost estimation. In contrast, during execution, it relies on the relcache (rd_amcache) when available to prevent repeated metapage fetches. When REINDEX occurs, the relcache becomes invalid, requiring execution to read the index page again, increasing buffer usage to 2. After an INSERT, the relcache is updated with valid metadata, enabling execution to access the cached root location without extra buffer reads, keeping total buffer usage at 1.

Conclusion

The behavior of B+tree indexes after large deletions differs significantly between database engines.

PostgreSQL preserves the physical height of the B+tree after deletions, but VACUUM can reduce its effective traversal depth through a sophisticated fast root optimization. The index metadata page maintains two root pointers: the true root representing the physical tree height, and the fast root pointing to the lowest single-page level. This design, based on Lanin and Shasha's approach, allows PostgreSQL to bypass redundant upper levels that contain only a single pointer and start searches closer to the leaves.

The fast root pointer is adjusted atomically during page splits and deletions. When a page that is alone on its level splits, or when the next-to-last page on a level is deleted, PostgreSQL updates the fast root pointer as part of the atomic operation, with the metapage locked last to avoid deadlocks. The query planner uses the fast root level for cost estimation, ensuring accurate planning based on effective rather than physical height.

PostgreSQL also caches metadata in the relation cache to avoid fetching the metapage for every search, with validation checks to handle stale cached pointers. The physical tree remains unchanged, but lookups require fewer page accesses without any rebuild.

Oracle Database also preserves the physical structure of the index. Pages can be merged, and space can be reclaimed, but the height of the B+tree remains unchanged until the index is rebuilt. As a result, lookups continue to traverse the same number of levels even when the index contains few or no entries. A possible reason for the lack of a fast root optimization is Oracle's MVCC, where the root depends on the read snapshot, unlike PostgreSQL, where the index contains entries for all versions.

In both databases, a rebuild produces the smallest possible B+tree after a delete, according to the PCTFREE (Oracle) or FILLFACTOR (PostgreSQL) defined. The difference is that PostgreSQL can often recover most of the lookup efficiency automatically through regular vacuuming by maintaining a fast root, whereas Oracle requires an explicit rebuild to reclaim those levels. This applies only to deletions where you don't anticipate inserting the same amount, in which case it's better to retain the currently allocated structure and avoid future splits.

Percona Operator for MongoDB 1.23.0 makes the operator a place you move to, not just a place you start. A new ClusterSync component clones a live source and follows its change streams, so leaving a hosted service is a short cutover rather than a long outage. Alongside it, this release adds semantic vector search and … Continued

The post Percona Operator for MongoDB 1.23.0: ClusterSync Migration, Vector Search, and PVC Snapshot Backups appeared first on Percona.

In the previous post, Cypher graph queries on PostgreSQL with Apache AGE, I showed how to model and query a property graph in PostgreSQL using Apache AGE. The graph was materialized as vertices and edges stored in dedicated tables.
PostgreSQL 19, currently in beta, takes a different route for built-in support of graph queries. With SQL/PGQ, a property graph is defined as a logical model on top of existing relational tables, without duplicating the underlying data. In short:

• Apache AGE: the graph is a stored data structure.
• SQL/PGQ: the graph is a semantic layer over relational data.

Unlike graph databases, or extensions such as Apache AGE, SQL/PGQ (SQL Property Graph Queries) does not introduce a separate graph storage model. Property graphs are defined on top of existing relational tables. The data remains relational, while graph queries become another way to access it.

Relational model

I'll use the legendary EMP/DEPT schema from more than 45 years ago:

create table "department" (
    "deptno" integer primary key,
    "name"   text not null,
    "loc"    text not null
);

create table "employee" (
    "empno"  integer primary key,
    "name"   text not null,
    "job"    text not null,
    "mgr"    integer references "employee"("empno"),
    "deptno" integer not null references "department"("deptno"),
    "sal"    integer not null
);

insert into "department" ("deptno", "name", "loc") values
(10, 'Administration', 'New York'),
(20, 'Research',       'San Francisco'),
(30, 'Sales',          'Chicago'),
(40, 'Operations',     'Boston');

insert into "employee" ("empno", "name", "job", "mgr", "deptno", "sal") values
(7839, 'OATES',  'President', NULL, 10, 5000),
(7566, 'JONES',  'Manager',   7839, 20, 2975),
(7698, 'BLAKE',  'Manager',   7839, 30, 2850),
(7782, 'CLARK',  'Manager',   7839, 10, 2450),
(7788, 'SCOTT',  'Analyst',   7566, 20, 3000),
(7902, 'FORD',   'Analyst',   7566, 20, 3000),
(7999, 'WILSON', 'Analyst',   7566, 20, 2800),
(7876, 'ADAMS',  'Clerk',     7788, 20, 1100),
(7369, 'SMITH',  'Clerk',     7902, 20,  800),
(8000, 'JAKES',  'Clerk',     7999, 20, 1000),
(7499, 'ALLEN',  'Salesman',  7698, 30, 1600),
(7521, 'WARD',   'Salesman',  7698, 30, 1250),
(7654, 'MARTIN', 'Salesman',  7698, 30, 1250),
(7844, 'TURNER', 'Salesman',  7698, 30, 1500),
(7900, 'JAMES',  'Clerk',     7698, 30,  950),
(8001, 'CARTER', 'Salesman',  7698, 30, 1400),
(7934, 'MILLER', 'Clerk',     7782, 10, 1300);

The employee hierarchy is represented through a self-referencing foreign key employee.mgr -> employee.empno and the employee-department relationship through employee.deptno -> department.deptno. This is the same model that has been used for decades in relational databases.

This model can be queried with joins and when there is a variable level of joins, WITH RECURSIVE clause can iterate in them. However, the queries quickly become complex and you need to think about the graph traversal for each query.

Property graph definition

SQL/PGQ introduces a property graph definition on top of relational tables, allowing them to be queried as vertices and edges rather than through joins.

The graph definition maps tables to vertices and foreign-key relationships to edges:

create property graph "emp_dept_graph"
vertex tables (
    "department" label "department",
    "employee"   label "employee"
)
edge tables (
    "employee" as "reports"
        source key      ("empno") references "employee"   ("empno")
        destination key ("mgr")   references "employee"   ("empno")
        label           "reports_to",
    "employee" as"works"
        source key      ("empno")  references "employee"   ("empno")
        destination key ("deptno") references "department" ("deptno")
        label           "works_in"
);

Unlike Apache AGE, no vertices or edges are stored separately. PostgreSQL exposes existing rows as graph elements. The relational tables remain the source of truth. The property graph is a queryable layer that maps the relational model to a graph model.

Querying the graph

To find Jones's manager, the Cypher query was:

MATCH (:Employee {name:"JONES"})-[:REPORTS_TO]->(manager:Employee)
RETURN manager.name

The SQL/PGQ is similar, using ASCII art with () for vertices and -[]-> for edges, but closer to SQL:

postgres=# select * from graph_table (
    "emp_dept_graph"
    match
        (e is "employee" where e."name" = 'JONES')
        -[is "reports_to"]->
        (m is "employee")
    columns (
        m."name" as "manager_name"
    )
);

 manager_name
--------------
 OATES

(1 row)

This query is conceptually equivalent to:

select m."name" as "manager_name"
 from "employee" e
 join "employee" m on m."empno" = e."mgr"
 where e."name" = 'JONES'
;

but expressed as a graph pattern.

Both have the same execution plan except for the alias names:

                                QUERY PLAN
---------------------------------------------------------------------------
 Hash Join  (cost=1.22..2.47 rows=1 width=6)
   Hash Cond: (employee_1.empno = employee.mgr)
   ->  Seq Scan on employee employee_1  (cost=0.00..1.17 rows=17 width=10)
   ->  Hash  (cost=1.21..1.21 rows=1 width=8)
         ->  Seq Scan on employee  (cost=0.00..1.21 rows=1 width=8)
               Filter: (name = 'JONES'::text)

With such a simple query, SQL does not look particularly complex. However, it already reveals a limitation of the relational model where relationships are not first-class citizens. Rather than navigating the domain model through named associations such as "reports to" or "works in", SQL developers must understand the physical schema and determine, for each query, which columns can be combined through joins.

The relational model was deliberately designed to do the opposite of graph or document databases, with their network or hierarchical models: relationships are represented indirectly through business values rather than explicit links, allowing entities to be stored independently of pointers, access patterns, or traversal directions.

Foreign key constraints in SQL add information about those relationships and enforce referential integrity during inserts, updates, and deletes. However, they do not provide a queryable graph structure or predefined navigation paths. Queries ignore the foreign keys and still need to specify how relationships are traversed with join predicates.

SQL/PGQ restores that semantic layer by defining a graph model on top of relational data. Associations from the domain model become explicit graph edges, allowing queries to traverse relationships by their business meaning rather than by manually assembling joins between columns.

Combining relationships

Graph patterns become more expressive when traversing multiple relationships. To retrieve both Jones's manager and that manager's department:

postgres=# select * from graph_table (
    "emp_dept_graph"
    match
        (e is "employee" where e."name" = 'JONES')
        -[is "reports_to"]->
        (m is "employee")
        -[is "works_in"]->
        (d is "department")
    columns (
        m.name as "manager_name",
        d.name as "department_name"
    )
);

 manager_name | department_name
--------------+-----------------
 OATES        | Administration

(1 row)

The equivalent relational query would require two joins and a self-join.

Traversing hierarchies

The EMP table is famous for hierarchical queries. To find the manager's manager of JAKES:

postgres=# select * from graph_table (
    "emp_dept_graph"
    match
        (e is "employee" where e."name" = 'JAKES')
        -[is "reports_to"]->()-[is "reports_to"]->
        (m is "employee")
    columns (
        m."name" as "manager_name"
    )
);

 manager_name
--------------
 JONES

(1 row)

SQL/PGQ standard allows the -[is "reports_to"]->{2} syntax where the {2} quantifier specifies a traversal depth of exactly two relationships, but this is not supported in PostgreSQL 19 so I used -[is "reports_to"]->()-[is "reports_to"]-> instead.

PostgreSQL 19 implements the core SQL/PGQ functionality needed to define property graphs over relational tables and query them with graph pattern matching. However, many advanced graph features are not yet supported, including path variables, shortest-path search, variable-length traversals, path analytics, and advanced path pattern expressions. The list is in sqlfeatures.txt.

Relational and graph models

The EMP/DEPT example has been used for decades to explain relational modeling, self-referencing relationships, and hierarchical queries. SQL/PGQ introduces a new way to query the same data, but it does not change how the data is stored. Tables, primary keys, foreign keys, indexes, constraints, the optimizer, and storage structures remain unchanged.

This is an interesting evolution of database history. The relational model was created in part to move away from the navigational nature of hierarchical and network databases, where applications followed predefined links and access paths. By representing relationships through values rather than pointers, relational databases achieved data independence: the schema describes the data without embedding specific navigation patterns or application use cases.

SQL/PGQ does not reverse that design choice. Relational tables remain the source of truth, and relationships are still represented through values rather than pointers. Instead, it adds a semantic layer that maps the relational schema to the domain model. Relationships that exist implicitly through foreign keys and join predicates become explicit graph edges such as reports_to or works_in. It is like an in-database Object-Relational Mapper (ORM) for graph use cases.

The benefit is primarily developer experience. Applications can navigate the domain model through graph patterns rather than reconstructing relationships from foreign keys and joins in every query. The relational model keeps its flexibility and data independence, while SQL/PGQ provides a more natural way to express traversals and relationship-oriented queries.

PostgreSQL 19 brings this graph abstraction directly into standard SQL. Graph queries run on the same tables, indexes, optimizer, and execution engine as traditional relational queries, without introducing a separate graph storage model.

In that sense, SQL/PGQ is not a return to hierarchical or network databases. The relational model remains the foundation. SQL/PGQ simply adds a semantic mapping between relational structures and business relationships, making graph-oriented queries easier to express while preserving the data independence that made relational databases successful in the first place.

On December 1, 2025, MariaDB announced that MySQL Galera Cluster will reach end of life on September 30, 2026. After that date, the MySQL build of Galera stops receiving maintenance and binary releases, and all new clustering features land only in MariaDB Galera Cluster. MariaDB’s recommended path is an in-place migration onto their own server. … Continued

The post How to Migrate from MySQL Galera Cluster to Percona XtraDB Cluster appeared first on Percona.

Metastability has been studied in previous work as a self-sustaining degradation in goodput that persists even after the trigger is gone. The degraded state loiters on entirely due to the system's own internal feedback loops (retries, queues), and there is no simple reset button to press in distributed systems. So this is not a rare exotic problem. Since production systems would have already been hardened to handle the obvious failures, what remains is these hard-to-detect emergent failures. The "Metastable Failures in the Wild" paper (OSDI'22) reports 22 incidents across 11 organizations. Four of the 15 major AWS outages in a decade were metastable failures, with durations ranging from 1.5 to 73 hours. 

This paper (June 2026) argues that the systems community has treated metastability phenomenologically, which led people to chase symptoms rather than causes. The paper sets out to give the first analytical causal account of these failures. This framing leads to two connections I found delightful. The first casts a metastable failure as a sin of composition among self-stabilizing systems. The second ties the healing mechanism to scheduling. Since I have worked on self-stabilizing systems for a long time (between 1998-2010), and thought hard about how they compose, these two connections really excite me.

I do have some reservations, though, which I will get to in my review. The paper overlooks prior work on the composition of stabilizing systems. It also pulls a bit of a sleight-of-hand in its formalization to argue that the metastable fault tolerance (MFT) design can be done via local pairwise reasoning between components. I don't buy that as I explain below.

These reservations do not dampen how much I enjoyed this paper. This is an idea paper, and it has been a while since I saw one of these in distributed systems. Moreover, the author list includes two of my all-time favorite distributed systems researchers: Robbert Van Renesse and Lorenzo Alvisi.

So let's dive in.

Sins of Composition and Self-Stabilization

The authors give formal definitions of a metastable fault and a metastable failure, and they draw a distinction between the two.

A metastable fault is what they beautifully call a sin of composition. (I am guessing this is Lorenzo being poetic.) Loosely speaking, the metastable fault appears when two or more components that are perfectly stable on their own get wired together into a cyclic interference/destruction loop. When a shock (say overload or loss of cache) then triggers the system, each component runs its local corrective action to stabilize itself, and in doing so it destabilizes its neighbor.

Let me back up and explain self-stabilization. A self-stabilizing system can start in any state and, with no outside intervention, converge on its own to a legitimate state and stay there. It lays out an elegant unified framework to tolerate any transient fault: A transient fault just leaves the system in some arbitrary state, and stabilization gradually heals it from there. 

The paper leans hard on this stabilization theory going back to the 1980s. It defines a potential function (also called a variant or metric function) $f$ for each component, measuring how far the component is from a good state. A component is stabilizing if it eventually drives $f$ to zero, provided it runs inside a well-behaved "environment" $E$.

To formulate composition of stabilizing components, they add a compatibility check: if component A can stabilize when B is stable, and B can stabilize when A is stable, the two are compatible. But compatibility is not enough for guaranteeing composition of stabilization. Right after a shock, neither component is stable, so they hit a bootstrapping problem. Each waits for the other to recover first, and they get stuck in mutual destabilization, as their actions during recovery interfere with each other's healing progress.

This "sin of composition" is defined as the metastable fault. The fault turns into a failure only when the shock lands and the system's scheduler keeps favoring the locally stabilizing but globally destabilizing interactions over the stabilizing ones.

None of this surprises a stabilization researcher. Stabilization is famously hard to compose, precisely because the recovery strategies of the components interfere with each other. The challenge is to keep the components from corrupting each other during recovery. One clean way is layered composition: let the lower layer stabilize first (the higher layer can read it but not write to it), and let recovery flow upward. In general, though, when you compose systems you have to design the correction actions deliberately, check that they don't interfere, and prove they stabilize together.

Overreaching for Local Reasoning

The paper's theoretical framework defines metastability nicely, however, I disagree with the claim that finding and fixing the fault is a local pairwise activity. That claim rests on the developer guessing the right potential function $f$ and the right environment predicate $E$. And it is not possible to derive a good potential function without reasoning about the system globally.

It is also worthwhile to discuss about the environment predicate $E$. In the classical stabilization literature, $E$ is usually trivial or vacuous, because a self-stabilizing system is supposed to recover from any state. The paper improves on this for compositionality by defining $E$ to capture the assumption that a component's neighbors behave well. But this generalization punts the hard parts to the developer: which environment predicate actually holds for the composed components, and which potential function is right for each component. These are questions that require global reasoning. Assuming a benevolent environment predicate $E$ in which everything else behaves perfectly ignores the reality that in a distributed system the "environment" is the other components, which are just as likely to be failing. Note that both the  Definition 3 (compatibility) and Definition 4 (destabilizing action) quantify over a single global environment predicate E for the whole composition.

Use the Graph to Fix, Not Just to Flag

The authors extract a composition blueprint, a directed graph of writes-to relations among components, which they search for cycles of destabilizing actions. But they use the graph only defensively, to flag faults. Once a fault is found, the proposed fix is to hand-inject ad-hoc timers that delay the destabilizing actions.

This leaves the constructive side of self-stabilization on the table. Leal and Arora's "Scalable self-stabilization via composition" (ICDCS 2004) showed you can enforce correct composition by leveraging this graph directly. The motivation for Leal (my academic brother) and Arora (my advisor) was to address the interference problem between actions which forces global reasoning over the whole system, and that reasoning explodes as systems grow. The key idea in their framework was to make two relations explicit: for each component, which other components it can corrupt, and which components must be corrected first before it can correct itself. Given per-component stabilizers (detectors and correctors), they offer several ways to coordinate correction depending on what you actually know about the corruption and correction relations. This framework aims to reduce design and reasoning to local activity between a component and its neighbors in order to allow local recovery and avoid blocking of components and distributed reset as much as possible. In other words, it proposed a topological answer to the sins of composition. Instead of guessed empirical timers and tentative scheduling, you use the direction of the edges to enforce the scheduling discipline.

I ran into a similar problem in my own work, "A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks". There we used layered/hierarchical healing, and tuned the timing of the corrective actions: we deliberately delayed the propagation waves of correction to higher levels of the hierarchy, so that more recent waves from lower levels could catch up. That delay gave us fault-local stabilization instead of a global cascade of corruption.

Scheduling as a First-Class Citizen

The paper also introduces Nyx, a DSL that forces you to model queues and resources explicitly and promotes the scheduler to a first-class citizen. The goal is to defer destabilizing interactions until stabilizing ones have achieved global stability. I like the intuition, but I think the paper reaches too far, and assumes a "God scheduler" that can serialize and control all concurrent actions from above. A central coordinator like that does not scale, and is not feasible to have in distributed systems. But the good news is that once you have framed the problem as a scheduling problem, you may not need a God scheduler to fix it. You can implement the fix with locally tuned timers. You don't have to be perfect; you only have to rig the odds toward stabilization.

Reading this paper gave me a concrete next step for MESSI, the metastability simulator tool Aleksey Charapko had developed to catch failures that hide in the seams between system components. We introduced MESSI in our recent paper, "A Case for Simulation-Driven Resilience in Agentic Data Systems". It models any subsystem as a graph of Logic Nodes (which express policy: where does this work go next?) and Processors (which express resource constraints, via delays for both service time and queuing time). Runs are deterministic and replayable, with full internal state captured every tick, and the runtime is scriptable, so you can inject failures, slowdowns, and config changes mid-run. The premise here is that production is too complex to tune by trial and error, so we need to trace how overload propagates before we deploy. To explore the effects of scheduling in MESSI,  we can add a ~SendAt()~ method, that allows delaying a potentially destabilizing message by a prescribed amount.

In sum, this is a thought-provoking paper. It correctly reframes metastability: not a mere symptom of overload, but a fundamental failure of recovery to compose across distributed boundaries. A metastable fault becomes a failure only under destructive interference among components. I think the paper's formal verification framework demands too much subjective guesswork to be practical, and its bet on the scheduler as a central coordinator may not be feasible. But the diagnosis of metastability is really a good one. Once you can name the interference (the sin of composition), accounting for it becomes a much more tractable problem.

Finally, I am adding a link to my marked up copy of the paper. Even with the availability of LLMs, I still believe in deep manual reading, and illustrating one's thought-processes to teach/train others.

The cover image above compares two representations of the same data model, separated by more than 45 years: one shows a PostgreSQL extension for Visual Studio Code visualizing a graph with Apache AGE, and the other displays the employee hierarchy from the Oracle 2.3 User Guide. Hierarchical and graph traversal queries have long been a topic in relational databases. Early SQL, or SEQUEL, used employee-department and manager relationships, which led to the need for graph traversal syntax beyond self-joins. The first commercial RDBMS had a CONNECT BY syntax (see Oracle 2.3 User Guide), later replaced by recursive WITH clauses in the SQL standard. PostgreSQL 19 adds SQL/PGQ support for property graph queries. Meanwhile, NoSQL graph databases like Neo4j, with Cypher, have gained popularity, and this capability is now accessible in PostgreSQL via the Apache AGE extension.

Apache AGE on PostgreSQL

I've built a small example based on the legendary EMP-DEPT schema from 45 years ago, running on Azure, because, according to https://www.pgextensions.org/, it is the only managed service that supports it:

I'm using HorizonDB, the PostgreSQL-compatible managed service for enterprise workloads, which is currently in preview (but you can also use the free ghcr.io/pglayers/pglayers-azure:17 image from pglayers). I've enabled Apache AGE by adding it to the azure.extensions list:

postgres=> \dconfig azure.extensions

                List of configuration parameters

    Parameter     |                    Value
------------------+----------------------------------------------
 azure.extensions | pg_diskann,vector,pg_textsearch,azure_ai,age

postgres=> \dconfig server_version

                List of configuration parameters
   Parameter    |                     Value
----------------+-----------------------------------------------
 server_version | 17.9 (Azure HorizonDB (81895d42565)(release))

The example is deliberately straightforward. Besides the departments reference, it includes the employee entity, and one relationship: each employee's immediate manager. In the relational model, both are stored in the same table, with the manager relationship represented through a self-referencing foreign key. SQL handles such relationships using joins, with CONNECT BY or WITH RECURSIVE for graph structures. Apache AGE represents relationships as graph edges and supports openCypher syntax, significantly simplifying complex graph queries.

Graph model

Property graph databases model the same information differently than relational databases. Entities are represented as nodes (aka vertices), and relationships (aka edges) connect them. Rather than reconstructing relationships through joins, relationships are stored explicitly as graph edges and traversed using graph patterns.

I install the extension and set the search path to include ag_catalog with the Apache AGE functions and datatypes:

create extension if not exists age;

set search_path = "$user", public, ag_catalog;

I generate a graph, which is equivalent to a schema:

select create_graph('emp_dept_graph');

PostgreSQL can now execute Cypher queries against this graph by calling cypher() with the graph name and query, returning an agtype result.

Graph nodes (vertices () )

In Apache AGE, all Cypher queries are in dollar-quoted strings. The following creates the nodes for the departments:

select * from cypher('emp_dept_graph', $openCypher$
CREATE
(:Department { deptno:10, name:"Administration", loc:"New York" }),
(:Department { deptno:20, name:"Research",       loc:"San Francisco" }),
(:Department { deptno:30, name:"Sales",          loc:"Chicago" }),
(:Department { deptno:40, name:"Operations",     loc:"Boston" })
$openCypher$) AS (result agtype);

The parentheses () draw a node (think of an ASCII art version of a graph), (:Department) adds a label to it, and the JSON-like { deptno:40, name:'Operations', loc:'Boston'} adds properties as key-value pairs, similar to JSON.

I do the same to create the employees, without specifying their department, only their own properties:

select * from cypher('emp_dept_graph', $openCypher$
CREATE
(:Employee {empno:7839,name:"OATES",job:"President",sal:5000}),
(:Employee {empno:7566,name:"JONES",job:"Manager",sal:2975}),
(:Employee {empno:7698,name:"BLAKE",job:"Manager",sal:2850}),
(:Employee {empno:7782,name:"CLARK",job:"Manager",sal:2450}),
(:Employee {empno:7788,name:"SCOTT",job:"Analyst",sal:3000}),
(:Employee {empno:7902,name:"FORD",job:"Analyst",sal:3000}),
(:Employee {empno:7999,name:"WILSON",job:"Analyst",sal:2800}),
(:Employee {empno:7876,name:"ADAMS",job:"Clerk",sal:1100}),
(:Employee {empno:7369,name:"SMITH",job:"Clerk",sal:800}),
(:Employee {empno:8000,name:"JAKES",job:"Clerk",sal:1000}),
(:Employee {empno:7499,name:"ALLEN",job:"Salesman",sal:1600}),
(:Employee {empno:7521,name:"WARD",job:"Salesman",sal:1250}),
(:Employee {empno:7654,name:"MARTIN",job:"Salesman",sal:1250}),
(:Employee {empno:7844,name:"TURNER",job:"Salesman",sal:1500}),
(:Employee {empno:7900,name:"JAMES",job:"Clerk",sal:950}),
(:Employee {empno:8001,name:"CARTER",job:"Salesman",sal:1400}),
(:Employee {empno:7934,name:"MILLER",job:"Clerk",sal:1300})
$openCypher$) AS (result agtype);

The nodes are stored with their properties. Now I can define the relationships to form a graph.

Graph relationships (edges -[]->)

I'll add the relationship to show where an employee works in a department, and their position in the hierarchy.

In a SQL model, employees reference their department via a DEPTNO foreign key and their manager through an MGR foreign key, with the manager being another employee. In relational databases, relationships are represented by key values rather than direct pointers between rows, and entities are independent of the navigation between them. Instead, the department number and manager's employee number are attributes of the employee entity, and relationships are established during queries with joins. Simple many-to-one relationships are represented by foreign keys. However, more complex relationships, such as many-to-many relationships or relationships with their own attributes, require an additional association table.

In a graph database, relationships are at the core of the model. The nodes are the entities and the edges are the relationships. In ASCII art, this can be described as: (:Employee)-[:WORKS_IN]->(:Department).

In SQL, relationships are queried using joins, and prior to the JOIN syntax, they were expressed as a Cartesian product in the FROM clause, with a WHERE clause to filter the desired combinations. A similar approach applies here. To establish the employee-department relationship, I define the set of (:Employee), (:Department) pairs that represent where each employee works and create a -[:WORKS_IN]-> edge between them.

select * from cypher('emp_dept_graph', $openCypher$
MATCH (e:Employee),(d:Department)
WHERE
       (e.empno=7839 AND d.deptno=10)
    OR (e.empno=7782 AND d.deptno=10)
    OR (e.empno=7934 AND d.deptno=10)
    OR (e.empno=7566 AND d.deptno=20)
    OR (e.empno=7788 AND d.deptno=20)
    OR (e.empno=7902 AND d.deptno=20)
    OR (e.empno=7369 AND d.deptno=20)
    OR (e.empno=7876 AND d.deptno=20)
    OR (e.empno=7999 AND d.deptno=20)
    OR (e.empno=8000 AND d.deptno=20)
    OR (e.empno=7698 AND d.deptno=30)
    OR (e.empno=7499 AND d.deptno=30)
    OR (e.empno=7521 AND d.deptno=30)
    OR (e.empno=7654 AND d.deptno=30)
    OR (e.empno=7844 AND d.deptno=30)
    OR (e.empno=7900 AND d.deptno=30)
    OR (e.empno=8001 AND d.deptno=30)
CREATE (e)-[:WORKS_IN]->(d)
$openCypher$) AS (result agtype);

Here is a similar query to declare the employee-manager relationship as (:Employee)-[:REPORTS_TO ]->(:Employee):

select * from cypher('emp_dept_graph', $openCypher$
MATCH (e:Employee),(m:Employee)
WHERE
       (e.empno=7566 AND m.empno=7839)
    OR (e.empno=7698 AND m.empno=7839)
    OR (e.empno=7782 AND m.empno=7839)
    OR (e.empno=7788 AND m.empno=7566)
    OR (e.empno=7902 AND m.empno=7566)
    OR (e.empno=7999 AND m.empno=7566)
    OR (e.empno=7876 AND m.empno=7788)
    OR (e.empno=7369 AND m.empno=7902)
    OR (e.empno=8000 AND m.empno=7999)
    OR (e.empno=7499 AND m.empno=7698)
    OR (e.empno=7521 AND m.empno=7698)
    OR (e.empno=7654 AND m.empno=7698)
    OR (e.empno=7844 AND m.empno=7698)
    OR (e.empno=7900 AND m.empno=7698)
    OR (e.empno=8001 AND m.empno=7698) 
    OR (e.empno=7934 AND m.empno=7782)
CREATE (e)-[:REPORTS_TO { manager_level: 1 }]->(m)
$openCypher$ ) AS (result agtype);

To show an example of a relationship property, I've added the manager level using Cypher map syntax, which looks like JSON.

AGE Internals

Apache AGE stores metadata in two catalog tables:

postgres=> select * from ag_catalog.ag_graph
;

 graphid |      name      |   namespace
---------+----------------+----------------
    26064 | emp_dept_graph | emp_dept_graph

(1 row)

postgres=> select * from ag_catalog.ag_label
;

       name       | graph | id | kind |            relation             |        seq_name
------------------+-------+----+------+---------------------------------+-------------------------
 _ag_label_vertex | 26064 |  1 | v    | emp_dept_graph._ag_label_vertex | _ag_label_vertex_id_seq
 _ag_label_edge   | 26064 |  2 | e    | emp_dept_graph._ag_label_edge   | _ag_label_edge_id_seq
 Department       | 26064 |  3 | v    | emp_dept_graph."Department"     | Department_id_seq
 Employee         | 26064 |  4 | v    | emp_dept_graph."Employee"       | Employee_id_seq
 WORKS_IN         | 26064 |  5 | e    | emp_dept_graph."WORKS_IN"       | WORKS_IN_id_seq
 REPORTS_TO       | 26064 |  6 | e    | emp_dept_graph."REPORTS_TO"     | REPORTS_TO_id_seq

(6 rows)

The data is stored in nodes and edges tables:

postgres=> \d emp_dept_graph."Department"
                                                                        Table "emp_dept_graph.Department"
   Column   |  Type   | Collation | Nullable |                                                              Default
------------+---------+-----------+----------+-----------------------------------------------------------------------------------------------------------------------------------
 id         | graphid |           | not null | _graphid(_label_id('emp_dept_graph'::name, 'Department'::name)::integer, nextval('emp_dept_graph."Department_id_seq"'::regclass))
 properties | agtype  |           | not null | agtype_build_map()
Indexes:
    "Department_pkey" PRIMARY KEY, btree (id)
Inherits: emp_dept_graph._ag_label_vertex

postgres=> select * from emp_dept_graph."Department"
;
       id        |                                         properties
-----------------+---------------------------------------------------------------------------------------------
 844424930131969 | {"loc": "New York", "name": "Administration", "deptno": 10, "disp_label": "Administration"}
 844424930131970 | {"loc": "San Francisco", "name": "Research", "deptno": 20, "disp_label": "Research"}
 844424930131971 | {"loc": "Chicago", "name": "Sales", "deptno": 30, "disp_label": "Sales"}
 844424930131972 | {"loc": "Boston", "name": "Operations", "deptno": 40, "disp_label": "Operations"}

(4 rows)

postgres=> \d emp_dept_graph."WORKS_IN"
                                                                       Table "emp_dept_graph.WORKS_IN"
   Column   |  Type   | Collation | Nullable |                                                            Default
------------+---------+-----------+----------+-------------------------------------------------------------------------------------------------------------------------------
 id         | graphid |           | not null | _graphid(_label_id('emp_dept_graph'::name, 'WORKS_IN'::name)::integer, nextval('emp_dept_graph."WORKS_IN_id_seq"'::regclass))
 start_id   | graphid |           | not null |
 end_id     | graphid |           | not null |
 properties | agtype  |           | not null | agtype_build_map()
Indexes:
    "WORKS_IN_end_id_idx" btree (end_id)
    "WORKS_IN_start_id_idx" btree (start_id)
Inherits: emp_dept_graph._ag_label_edge

postgres=> select * from emp_dept_graph."WORKS_IN"
;
        id        |     start_id     |     end_id      | properties
------------------+------------------+-----------------+------------
 1407374883553281 | 1125899906842625 | 844424930131969 | {}
 1407374883553282 | 1125899906842626 | 844424930131970 | {}
 1407374883553283 | 1125899906842627 | 844424930131971 | {}
 1407374883553284 | 1125899906842628 | 844424930131969 | {}
 1407374883553285 | 1125899906842629 | 844424930131970 | {}
 1407374883553286 | 1125899906842630 | 844424930131970 | {}
 1407374883553287 | 1125899906842631 | 844424930131970 | {}
 1407374883553288 | 1125899906842632 | 844424930131970 | {}
 1407374883553289 | 1125899906842633 | 844424930131970 | {}
 1407374883553290 | 1125899906842634 | 844424930131970 | {}
 1407374883553291 | 1125899906842635 | 844424930131971 | {}
 1407374883553292 | 1125899906842636 | 844424930131971 | {}
 1407374883553293 | 1125899906842637 | 844424930131971 | {}
 1407374883553294 | 1125899906842638 | 844424930131971 | {}
 1407374883553295 | 1125899906842639 | 844424930131971 | {}
 1407374883553296 | 1125899906842640 | 844424930131971 | {}
 1407374883553297 | 1125899906842641 | 844424930131969 | {}

(17 rows)

Looking at the table definitions, I can prevent duplicates by creating the following UNIQUE indexes:

CREATE UNIQUE INDEX department_deptno_uix
ON emp_dept_graph."Department"
(
    (agtype_access_operator(properties, '"deptno"'))
);

CREATE UNIQUE INDEX employee_empno_uix
ON emp_dept_graph."Employee"
(
    (agtype_access_operator(properties, '"empno"'))
);

CREATE UNIQUE INDEX works_in_uix
ON emp_dept_graph."WORKS_IN"(start_id,end_id);

CREATE UNIQUE INDEX reports_to_uix
ON emp_dept_graph."REPORTS_TO"(start_id,end_id);

I can also create a GIN index on the properties to accelerate searches by a property value:

CREATE INDEX employee_properties_gin
ON emp_dept_graph."Employee"
USING gin (properties);

Let's examine some queries and their corresponding translations on internal tables and indexes.

Query

I have already used the MATCH clause to identify the combinations of employees and departments to create the edges.

To find the manager of Jones (:Employee {name:"JONES"}), I match the relationship with a variable -[:REPORTS_TO]->(manager) and return manager.name property.

postgres=> SELECT * FROM cypher('emp_dept_graph', $openCypher$
MATCH (:Employee {name:"JONES"})-[:REPORTS_TO]->(manager)
RETURN manager.name
$openCypher$) AS (
  manager agtype
);

 manager
---------
 "OATES"

(1 row)

I can add the department of the manager to the result by navigating through -[:WORKS_IN]->:

postgres=> SELECT *
FROM cypher('emp_dept_graph', $openCypher$
MATCH (:Employee {name:"JONES"})
      -[:REPORTS_TO]->(manager)
      -[:WORKS_IN]->(department)
RETURN manager.name, department.name
$openCypher$) AS (
  manager agtype,
  department agtype
);

 manager |    department
---------+------------------
 "OATES" | "Administration"

(1 row)

I can get the manager's manager with -[:REPORTS_TO]->()-[:REPORTS_TO]->(manager) but also with -[:REPORTS_TO*2]->:

postgres=> SELECT *
FROM cypher('emp_dept_graph', $openCypher$
MATCH (:Employee {name:"JAKES"})-[:REPORTS_TO*2]->(manager)
RETURN manager.name
$openCypher$) AS <... (truncated)