B-tree block split: what's the impact?

**Ontem** às 18:25

B-tree block split: what's the impact?

Tópico: B-tree block split: what's the impact?
Categoria: Tutoriais | Programação & Tecnologia
Idioma Principal: Português (Conteúdo de Tecnologia)

Descrição do Conteúdo / Informações:
-------------------------------------------------------------------------
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.