Everybody knows that B-tree indexes provide logarithmic lookups, but what does that actually mean in PostgreSQL?
How many index entries fit in a page? When does a page split? When does the tree gain another level? How much additional WAL is generated? How many more buffers are touched during an index lookup?
PostgreSQL exposes enough information to observe all of this directly. One command and two extensions included in PostgreSQL contrib are particularly useful:

• EXPLAIN (analyze, buffers, wal) for observing the buffer activity and WAL generated by DML on indexes
• pageinspect for inspecting internal page structures
• pgstattuple for gathering statistics about index pages

By inserting rows one at a time and collecting B-tree statistics after each insert, we can watch the index grow from a single page to a multi-level B-tree and correlate page splits with WAL generation and buffer accesses.

Inspecting the B-Tree Metadata with bt_metap()

The pageinspect extension is a low-level debugging tool that exposes information stored in table and index pages.
Block 0 of every B-tree index is the metapage. It stores information about the root page, the current tree depth, and other metadata.

postgres=# create extension if not exists pageinspect;
CREATE EXTENSION

postgres=# \x
Expanded display is on.

postgres=# select * from bt_metap('demo_pkey');
-[ RECORD 1 ]-------------+-------
magic                     | 340322
version                   | 4
root                      | 53194
level                     | 3
fastroot                  | 53194
fastlevel                 | 3
last_cleanup_num_delpages | 0
last_cleanup_num_tuples   | -1
allequalimage             | t

postgres=# \x
Expanded display is off.

The values come directly from BTMetaPageData:

• magic: A constant (340322) used to verify the file is a B-tree.
• version: The B-tree layout version.
• root: The block number of the "true" root. It can change when the root block is split to add a level.
• level: The distance from the true root to leaf pages
• fastroot and fastlevel: the block number and level of the effective root from which B-tree searches start. They can let searches skip upper levels that contain only a single page (more info in the [README].(https://github.com/postgres/postgres/blob/REL_19_BETA2/src/backend/access/nbtree/README#L362))
• last_cleanup_num_delpages: Pages deleted during the last VACUUM.
• allequalimage: Optimization flag indicating if the index can use "deduplication" safely.

B-tree searches start at fastroot rather than necessarily at the true root. Starting from a page at fastlevel, PostgreSQL follows downlinks until it reaches the leaf page containing the relevant key range.

Collecting Statistics With pgstatindex()

Where pageinspect exposes internal metadata, pgstattuple can scan the index and provide aggregated statistics related to bloat and fragmentation.

postgres=# create extension if not exists pgstattuple;
CREATE EXTENSION

postgres=# \x
Expanded display is on.

postgres=# select * from pgstatindex('demo_pkey');
-[ RECORD 1 ]------+----------
version            | 4
tree_level         | 3
index_size         | 586776576
root_block_no      | 53194
internal_pages     | 351
leaf_pages         | 71276
empty_pages        | 0
deleted_pages      | 0
avg_leaf_density   | 69.04
leaf_fragmentation | 49.84

postgres=# \x
Expanded display is off.

This function returns:

• tree_level: the level of the root page, with leaf pages at level 0. It is therefore also the number of downward links followed from the root to reach a leaf page.
• index_size: Total size in bytes calculated from the total number of pages
• internal_pages: counts of non-leaf pages, so the branches including the root, found during the scan.
• leaf_pages: counts the leaf pages found during the scan, so the ones storing the index entries with the heap tuple identifier of the row (TID)
• empty_pages: half-dead pages, which are empty but still present in the tree
• deleted_pages: pages deleted from the tree and available for reuse
• avg_leaf_density: the average percentage of usable leaf-page space occupied by index tuples. A low value can indicate unused space or bloat, although page splits also naturally leave free space.
• leaf_fragmentation: Measures how many leaf pages are physically out of order.

Test setup

I've run the following to insert rows and display the B-tree statistics after each insert:

-- create a table with an index (the primary key)
drop table demo;
create table demo ( id uuid primary key);

-- get B-tree statistics
create extension if not exists pgstattuple;
select * from pgstatindex('demo_pkey');
create extension if not exists pageinspect;
select * from bt_metap('demo_pkey');

-- insert a row with random value for the indexed column,
-- display the index statistics and repeat
\x
explain ( analyze, buffers, wal, costs off )
insert into demo (id) values ( uuidv4() )
\;
select * from pgstatindex('demo_pkey')
\watch i=0.01

I used the following AWK script to parse the result, display one line per row inserted, and flag when the WAL size generated by the insert is different from the preceding:

awk -F"|" '
/Insert/{ rows=rows + 1 }
/WAL/{ wal = $2 }
/Buffer/{ buf = $2 }
$1~/^[a-z_]+ */ { sub(/ *$/,"",$1 ) ; val[$1]=$2 }
/^$/ && val["tree_level"]!="" {
 key=wal " " val["tree_level"]
 if ( key != prev ) {pre="+"} else {pre=" "}
 printf "%1s %8d rows, %4d levels, %4d internal, %6d leaf, %6.2f MB, %3d%%, last insert: %-28s %-50s\n", pre, rows, val["tree_level"], val["internal_pages"], val["leaf_pages"], val["index_size"] / 1024 / 1024, val["avg_leaf_density"], wal, buf
 val["tree_level"]=""
 prev=key
}
' | grep -C3 '^+'

The First Split

In this test, the first 291 index entries fit in a single page - 0 internal pages, only one leaf, which is also the root:

+        1 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,   0%, last insert:    WAL: records=3 bytes=233     Buffers: shared hit=4 dirtied=3 written=2
+        2 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,   0%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
         3 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,   1%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2
         4 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,   1%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2
         5 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,   1%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2
--
       289 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,  99%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2
       290 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,  99%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2
       291 rows,    0 levels,    0 internal,      1 leaf,   0.02 MB,  99%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=2

In this test, most inserts generate two WAL records: one for the heap insertion and one for the index insertion. We see the average leaf density increase steadily to 99% as the root page fills.

The page is now full and must be split to insert the 292nd index entry. PostgreSQL creates a new root page above two leaf pages, resulting in a B-tree with one level:

+      292 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  50%, last insert:    WAL: records=3 bytes=1057    Buffers: shared hit=3 dirtied=2 written=2
+      293 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  50%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=5
       294 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  50%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       295 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  50%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       296 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  51%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
--
       321 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  55%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       322 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  55%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       323 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  55%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3

The split generates three WAL records instead of two. The next insert touches five shared buffers, while subsequent inserts stabilize at three: the heap page, the root page, and one leaf page.

This continues until those pages are full and must be split, with one more leaf page and one more WAL record for the one that had to split:

       323 rows,    1 levels,    1 internal,      2 leaf,   0.03 MB,  55%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
+      324 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  37%, last insert:    WAL: records=3 bytes=3799    Buffers: shared hit=5 dirtied=1 written=1
+      325 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  37%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       326 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  37%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       327 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  37%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       328 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  37%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
...
       645 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  74%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       646 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  74%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       647 rows,    1 levels,    1 internal,      3 leaf,   0.04 MB,  74%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
+      648 rows,    1 levels,    1 internal,      4 leaf,   0.05 MB,  55%, last insert:    WAL: records=3 bytes=3775    Buffers: shared hit=5 dirtied=1 written=1
+      649 rows,    1 levels,    1 internal,      4 leaf,   0.05 MB,  55%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       650 rows,    1 levels,    1 internal,      4 leaf,   0.05 MB,  56%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
+      651 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  45%, last insert:    WAL: records=3 bytes=3775    Buffers: shared hit=5 dirtied=1 written=1
+      652 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  45%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       653 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  45%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       654 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  45%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
       655 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  45%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
...
      1256 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  86%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
      1257 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  86%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
      1258 rows,    1 levels,    1 internal,      5 leaf,   0.05 MB,  86%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
+     1259 rows,    1 levels,    1 internal,      6 leaf,   0.06 MB,  72%, last insert:    WAL: records=3 bytes=3799    Buffers: shared hit=5 dirtied=1 written=1
+     1260 rows,    1 levels,    1 internal,      6 leaf,   0.06 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
      1261 rows,    1 levels,    1 internal,      6 leaf,   0.06 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
      1262 rows,    1 levels,    1 internal,      6 leaf,   0.06 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
      1263 rows,    1 levels,    1 internal,      6 leaf,   0.06 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3

This pattern continues until, in this test, the root page is full of downlinks to 291 leaf pages, so that it must be split into two internal pages, with a new root above, increasing the level to 2:

     61343 rows,    1 levels,    1 internal,    291 leaf,   2.29 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
     61344 rows,    1 levels,    1 internal,    291 leaf,   2.29 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
     61345 rows,    1 levels,    1 internal,    291 leaf,   2.29 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=3
+    61346 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=4 bytes=6017    Buffers: shared hit=6 dirtied=4 written=3
+    61347 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=6
     61348 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61349 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61350 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
...
     61408 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61409 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61410 rows,    2 levels,    3 internal,    292 leaf,   2.31 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
+    61411 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=3 bytes=3775    Buffers: shared hit=6 dirtied=1 written=1
+    61412 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61413 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61414 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61415 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
...
     61543 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61544 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61545 rows,    2 levels,    3 internal,    293 leaf,   2.32 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
+    61546 rows,    2 levels,    3 internal,    294 leaf,   2.33 MB,  72%, last insert:    WAL: records=3 bytes=3775    Buffers: shared hit=6 dirtied=1 written=1
+    61547 rows,    2 levels,    3 internal,    294 leaf,   2.33 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61548 rows,    2 levels,    3 internal,    294 leaf,   2.33 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61549 rows,    2 levels,    3 internal,    294 leaf,   2.33 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     61550 rows,    2 levels,    3 internal,    294 leaf,   2.33 MB,  72%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4

The split that increased the level wrote 4 WAL records. The next inserts then filled one page, writing 2 WAL records (leaf + heap). In this test, inserts now touch four shared buffers instead of three because the index has one additional level. Leaf splits that do not have to split an internal page write 3 WAL records.

At this point, the tree contains three internal pages: one root page at level 2 and two branch pages at level 1. The leaf pages are at level 0.

When a branch page at level 1 becomes full, it is split. This does not increase the tree level as long as the new downlink can be inserted into the root page at level 2:

     80439 rows,    2 levels,    3 internal,    398 leaf,   3.14 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     80440 rows,    2 levels,    3 internal,    398 leaf,   3.14 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     80441 rows,    2 levels,    3 internal,    398 leaf,   3.14 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
+    80442 rows,    2 levels,    4 internal,    399 leaf,   3.16 MB,  69%, last insert:    WAL: records=4 bytes=7415    Buffers: shared hit=8 dirtied=2 written=2
+    80443 rows,    2 levels,    4 internal,    399 leaf,   3.16 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     80444 rows,    2 levels,    4 internal,    399 leaf,   3.16 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     80445 rows,    2 levels,    4 internal,    399 leaf,   3.16 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4
     80446 rows,    2 levels,    4 internal,    399 leaf,   3.16 MB,  69%, last insert:    WAL: records=2 bytes=143     Buffers: shared hit=4

When there are so many branch pages at level 1 that their downlinks fill the root at level 2, the root must split. This happened in my example when the index reached 417.92 MB with 53193 leaf pages and 300 internal pages.

This is when I ran bt_metap() and pgstatindex() and obtained the result shown at the beginning of this post, with a 3-level B-tree.

Conclusion

B-tree indexes grow through a series of page splits. In this test, most inserts are inexpensive, touching one leaf page and generating two WAL records. Occasionally, a leaf page becomes full, triggering a split and additional WAL. More rarely, a branch page splits. Rarest of all are root splits, which add another level to the tree.

This experiment illustrates the write amplification inherent in B-trees, but also shows why they scale so well. The first additional level appeared after only a few hundred rows. The next required more than sixty thousand rows. The third required an index over 400 MB in size.

Page splits occur often enough to keep the tree balanced, while increases in tree level happen much more gradually. Even large PostgreSQL indexes therefore remain shallow. Their internal pages are also likely to remain cached because there are relatively few of them. For indexed queries that return table rows, the more significant I/O cost is often fetching heap pages rather than traversing the B-tree itself.

TL;DR: Starting with PBM 2.15.0 and PCSM 0.9.0, every release artifact – binary tarballs, RPM and DEB packages, and Docker images – ships a CycloneDX 1.6 Software Bill of Materials in JSON. Scan it with Trivy, Grype, or any CycloneDX-compatible tool. For Docker images, the fastest path is a Trivy image –sbom-sources oci <image>. There … Continued

The post Alert on CVEs in Your Percona Tools for MongoDB on Day One appeared first on Percona.

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.