nbtree-arch-pgcon

nbtree: An architectural perspective

Video (lacks original animations): https://www.youtube.com/watch?v=p5RaATILoiE

Many PostgreSQL users have a basic understanding of how Postgres nbtree indexes work internally (e.g., how the structure is maintained, high level details of how a new level is added to the tree, the role of VACUUM in garbage collection). A smaller number have some understanding of advanced topics (e.g., details of Lehman & Yao's B-Link technique, details of crash recovery). Even an experienced backend hacker could be forgiven for concluding that this is all well explored territory, leaving little room for improvement, since all the important components are already in place.

This view of things is based on a correct premise, and yet cannot explain why nbtree doesn't perform well with certain specific real world workloads. For example, there is an excessive amount of nbtree index bloat created by the industry standard TPC-C benchmark, despite the fact that TPC's transactions rarely update indexed columns, and therefore handily avoid so-called "write amplification". Certain pieces are missing.

Code enhancements (authored by the speaker) that will appear in PostgreSQL 12 will significantly improve matters for affected workloads. In some ways, this work is based on a return to decades old fundamentals. In other ways, it is based on practical experience, involving analyzing real-world index structures in an effort to learn where problems may lie.

This talk will cover:

• A review of the design of nbtree, especially its high level goals.

• The importance of thinking in terms of invariants — the rules underlying what belongs where in the index.

• Interesting ways in which nbtree exceeds what is truly required by the invariants, and how that can be exploited to improve performance.

• Possible future work aimed at reducing CPU cache misses while descending a B-Tree.

• The big picture — how all these techniques are complementary, and worth more than the sum of their parts

Transcript

1. https://speakerdeck.com/peterg/nbtree-arch-pgcon nbtree: An architectural perspective PGCon 2019 — May 30, 2019
2. https://speakerdeck.com/peterg/nbtree-arch-pgcon Peter 
 Geoghegan @petervgeoghegan
3. https://speakerdeck.com/peterg/nbtree-arch-pgcon My perspective Good mental model important for working on the nbtree code. - Perhaps this talk will make that easier. Must approximate reality, while leaving out inessential details that hinder understanding. PostgreSQL 12 work will be discussed along the way.
4. https://speakerdeck.com/peterg/nbtree-arch-pgcon Overview 1. Big picture with B-Trees What’s the point of this “high key” business, anyway? 2. Seeing the forest for the trees Reasoning about nbtree invariants when designing enhancements. 3. A place for everything, and everything in its place How reliably unique keys simplify many things. 4. Future work Outlook for future improvements.
5. https://speakerdeck.com/peterg/nbtree-arch-pgcon Big picture with B-Trees Page splits add new pages. Recursive growth — page splits occur in leaf pages that fill with tuples pointing to table, and cascade upwards to maintain tree. Actually bush-like — very short, and very, very wide. - New levels added to tree at logarithmic intervals, during root page split. Just a few localized atomic operations that affect only a few pages at a time used for everything.
6. https://speakerdeck.com/peterg/nbtree-arch-pgcon The key space Every page “owns” a range of values in the key space/key domain. - Starts out with a single root page (also a leaf), that owns the range “-∞” through to “+∞”. - Splitting rightmost leaf page creates new leaf page that owns a range starting just after the final tuple in new left half, through to the sentinel “+∞”. We always have one particular page that any possible new tuple should go on (at least on Postgres 12).
7. https://speakerdeck.com/peterg/nbtree-arch-pgcon Protecting tree structure Locks used to protect physical structure as tree grows. - Must prevent the tree structure from becoming inconsistent (e.g., in a state that causes an index scan to skip over relevant data). - Various schemes used over past 40+ years. nbtree uses Lehman & Yao algorithm. - Have right sibling pointer and high key. - Sometimes called “B-Link Trees”.
8. Figure 3. A B-link tree page split IP.I ~ IP.I '~1 ' I ~l.~,..l'r,..I / \ ... \ ° . . ° , , ° , , ,°° (a) Example B-link tree node n-1 keys n pointers I1"" 111~,~,,itlll " " " I 't-~////~1 t ..... ,~ ~ , ~ t ..... ,~ d+ 1 d+l pointers pointers (b) Before half-split / ..... \ (c) After half-split n-1 keys n pomters I "" .l,I I.I II ' I,l'"l ,,,/~s _.H,, ~ kT.. i~////~f_ " z ~ / ..... \ d+2 d+l pointers pointers n keys n +1 pointers Jzl "'" ,~[r%.,i~tl I.I I I ' d+2 d+l pointers pointers (d) After key propagation Pictured: Diagram from “Performance of B+Tree Concurrency Control Algorithms“ by V. Srinivasan and Michael J. Carey
9. https://speakerdeck.com/peterg/nbtree-arch-pgcon Moving right to recover B-Link trees (Lehman and Yao B-Trees) take an optimistic approach, in contrast with earlier, pessimistic designs. Concurrent page splits might confuse searches that descend tree — can be dealt with a few ways. Earlier approaches involved “coupling” locks, preventing concurrent page splits altogether. Lehman and Yao’s algorithm detects and recovers from concurrent splits instead.
10. https://speakerdeck.com/peterg/nbtree-arch-pgcon Recovering from a concurrent page split Lehman and Yao divide complicated page split into two simpler atomic steps. - Initial step creates new right sibling, and shares tuples amongst original (left) page and new right page. - Second step inserts new downlink for right page. Meanwhile, scans must check high key after descending on to a page — verifies that this is still the page covering the value of interest.
11. https://speakerdeck.com/peterg/nbtree-arch-pgcon Overview 1. Big picture with B-Trees What’s the point of this “high key” business, anyway? 2. Seeing the forest for the trees Reasoning about nbtree invariants when designing enhancements. 3. A place for everything, and everything in its place How reliably unique keys simplify many things. 4. Future work Outlook for future improvements.
12. https://speakerdeck.com/peterg/nbtree-arch-pgcon
13. https://speakerdeck.com/peterg/nbtree-arch-pgcon -∞ ↧ Papa ↧ +∞ ↧ Charlie ↧ Golf ↧ Mike ↧ Papa "-∞" ↧ Tango November Oscar Papa et Kilo Lima Mike Mike Quebec Romeo Sierra Tang
14. https://speakerdeck.com/peterg/nbtree-arch-pgcon -∞ ↧ Papa ↧ +∞ -∞ ↧ Charlie ↧ Golf ↧ Mike ↧ Papa "-∞" ↧ Tango ↧ X-Ray ↧ +∞ November Oscar Papa Alfa Bravo Charlie Delta Echo Foxtrot Golf Juliet Kilo Lima Mike Mike Quebec Romeo Sierra Tango Uniform Victor XRay XRay Yankee Zulu +∞
15. https://speakerdeck.com/peterg/nbtree-arch-pgcon Seeing the forest for the trees Lehman and Yao paper not a particularly good guide to nbtree. nbtree is concerned with distinctions that L&Y either ignore or couldn’t possibly anticipate. - Variable-sized keys. - Page model, IndexTuple struct format. Few true special cases, despite appearances to the contrary. Problem made worse by generally odd approach L&Y take.
16. – Lanin & Sasha paper (LS86) [emphasis added], from “2.2 Locks” “The locking model used in [LY81] assumed that an entire node could be read or written in one indivisible operation … Since the atomicity of node reads and writes is not a reasonable assumption in some environments (such as when the structure is in primary memory), and in order to make comparisons to other algorithms easier, we use a more general locking scheme similar to the one in [BS77]”
17. https://speakerdeck.com/peterg/nbtree-arch-pgcon Terminology Terminology makes things harder — equivalent but not identical representation lets nbtree use IndexTuple struct for everything. This is convenient for low-level page code, but can make high- level discussions confusing. Pivot tuples. - Contain separator keys and/or downlinks — guide scans. - Usually have both together, sometimes just separator (high key), other times just a downlink (“-∞” tuple). Non-pivot tuples. - Only on leaf level, cannot be truncated, always point to table.
18. https://speakerdeck.com/peterg/nbtree-arch-pgcon Invariants Carefully considering how to satisfy invariants can simplify the design of nbtree enhancements. Relationship between separator keys and real keys can be fairly loose. - Values in same domain as entries, but it’s okay if they don’t actually match any real entry (non-pivot key). - Separators are a good target for prefix compression (a generic optimization) — there is seldom any need to decompress, and a good whole-page prefix is already available.
19. https://speakerdeck.com/peterg/nbtree-arch-pgcon Invariants (cont.) Good B-Tree designs not only anticipate future work — they simplify it as a concomitant advantage. Subtrees can be isolated and reasoned about as independent units. - All subtrees own discrete range in the key space. - Page deletion relies on this to isolate subtree undergoing deletion (multi-level deletion). - Prefix compression of leaf page items would probably work based on similar principles — if only because compression based on current keys might break page deletion.
20. https://speakerdeck.com/peterg/nbtree-arch-pgcon Overview 1. Big picture with B-Trees What’s the point of this “high key” business, anyway? 2. Seeing the forest for the trees Reasoning about nbtree invariants when designing enhancements. 3. A place for everything, and everything in its place How reliably unique keys simplify many things. 4. Future work Outlook for future improvements.
21. https://speakerdeck.com/peterg/nbtree-arch-pgcon A place for everything, and everything in its place Uniqueness required by Lehman and Yao. nbtree treats heap TID as tiebreaker column in v12. L&Y’s requirement now met, finally. TIDs are reliably unique, so now keys are themselves unique. - Needed for “retail index tuple deletion”. - Surprisingly helpful in other ways.
22. https://speakerdeck.com/peterg/nbtree-arch-pgcon Heap TID as a tiebreaker For the most part, “heap TID column” is not special, at least internally. Inserts must specify heap TID. “Retail index tuple deletion” would have to work in the same way, since it’s necessary to unambiguously identify the same tuple when there are (logical) duplicates.
23. https://speakerdeck.com/peterg/nbtree-arch-pgcon The false economy of “getting tired” when inserting duplicates Old approach had insertion place a duplicate anywhere it wanted to among leaf pages that have ever had duplicates. - Go through pages that store duplicates on the leaf level until some free space is located… - …or until we “get tired” — implementation unable to spend too long locating theoretically available free space. - Getting tired occurs at random — give up and split page. Insertion won’t “get tired” with Postgres 12 indexes, which can make affected indexes ~16% smaller in simple cases. Gitlab may have been affected [1]. [1] https://about.gitlab.com/handbook/engineering/infrastructure/blueprint/201901-postgres-bloat/
24. https://speakerdeck.com/peterg/nbtree-arch-pgcon Realistic small Postgres 12 index (root page + 3 leaf pages) -∞ ↧ 367, '-∞' ↧ 733, '-∞' ↧ +∞ 1, '(0,1)' 2, '(0,2)' ... 366, '(5,61)' 367, '-∞' 366 non-pivot items & high key 367, '(6,1)' 368, '(6,2)' ... 732, '(11,61)' 733, '-∞' 366 non-pivot items & high key 733, '(12,1)' 734, '(12,2)' ... +∞ 2+ non-pivot items, implicit +∞ high key
25. https://speakerdeck.com/peterg/nbtree-arch-pgcon Realistic small Postgres 12 index (root page + 3 leaf pages) -∞ ↧ 367, '-∞' ↧ 733, '-∞' ↧ +∞ (5,61)' 367, '-∞' high key 367, '(6,1)' 368, '(6,2)' ... 732, '(11,61)' 733, '-∞' 366 non-pivot items & high key 733, '(12, 2+ non-piv
26. 12 l R. Bayer and K. Unterauer Bigbird, Burt, Cookiemonster, Ernie, Snuffleopogus In order to insert the key “Grouch” with its record, we must split this leaf into two as follows: Bigbird, Burt, Cookiemonster Ernie, Grouch, Snuffleopogus Instead of storing the key “Ernie” in the index, it obviously suffices to use one of the one-letter strings “D”, “E” for the same purpose. In general we can select any string s with the property Cookiemonster < s 5 Ernie (1) and store it in the index part to separate the two nodes. We call such a string s a separator (between Cookiemonster and Ernie). It seems prudent to choose one of the shortest separators. Note. If the keys are words over some alphabet and the ordering of the keys is the alphabetic order, then the following property, called the pre$x property, holds: Let x and y be any two keys such that x < y. Then there is a unique prefix g of y such that (a) g is a separator between x and y, and (b) no other separator between x and y is shorter than g. For the rest of this paper, we assume that the Pictured: Diagram from “Prefix B-Trees“ by Bayer and Unterauer, 1977
27. https://speakerdeck.com/peterg/nbtree-arch-pgcon Classic suffix truncation applied to earlier example -∞ ↧ P ↧ +∞ -∞ ↧ D ↧ G ↧ N ↧ P "-∞" ↧ T ↧ Y ↧ +∞ November Oscar P Alfa Bravo D Delta Echo Foxtrot G Juliet Kilo Lima Mike N Quebec Romeo Sierra T Uniform Victor XRay Y Yankee Zulu +∞
28. https://speakerdeck.com/peterg/nbtree-arch-pgcon Classic suffix truncation applied to earlier example -∞ ↧ D ↧ G ↧ N ↧ P ↧ T ↧ Y ↧ +∞ Alfa Bravo D Delta Echo Foxtrot G Juliet Kilo Lima Mike N November Oscar P Quebec Romeo Sierra T Uniform Victor XRay Y Yankee Zulu +∞
29. https://speakerdeck.com/peterg/nbtree-arch-pgcon Choosing a split point Leaf page splits primarily about equalizing free space on each side, to meet future needs. Also only place where new separator keys are made. - New high key for left page becomes separator before new downlink in parent for right page. - Internal page splits only use copies (truncating an already-truncated key would be wrong). Suffix truncation occurs when new separator created by leaf split.
30. https://speakerdeck.com/peterg/nbtree-arch-pgcon Choosing a split point (cont.) Algorithm can give some weight to suffix truncation, while continuing to make space utilization the first priority. Even very small adjustments can help suffix truncation a lot. Algorithm won’t accept a totally lopsided split to make suffix truncation more effective.
31. a split point anywhere between the short arrows is acceptable, a single letter suffices. A single comparison of the two keys defining the range of acceptable split points can determine the shortest possible separa- tor key. For example, in Figure 3.6, a comparison between “Johnson, Lucy” and “Smith, Eric” shows their first difference in the first letter, indicating that a separator key with a single letter suffices. Any letter … Johnson, Kim Johnson, Lucy Johnson, Mitch Miller, Aaron Miller, Bertram Miller, Cyril Miller, Doris Smith, Eric Smith, Frank … Fig. 3.6 Finding a separator key during a leaf split. Pictured: Diagram from “Modern B-Tree Techniques“ by Goetz Graefe — Prefix B-Trees chapter
32. https://speakerdeck.com/peterg/nbtree-arch-pgcon Choosing a split point (cont.) Algorithm in Postgres 12 takes a holistic view of the problem. May make slight adjustment with simple, common cases (e.g. pgbench indexes). But sometimes radically different to previous approach! - Behavior with duplicates is important with heap TID as a tiebreaker column. - A 50:50 page split is essentially a guess, and not necessarily a good one. - A 90:10 page split (rightmost split) is well known case where split point is based on inferring insertion patterns.
33. https://speakerdeck.com/peterg/nbtree-arch-pgcon TPC-C indexes and “split after new tuple” optimization Insertion pattern is very often not random Successive splits over short period of time that affect same area are very common. Multi-column indexes may have auto-incrementing identifiers grouped by an order number or similar. Industry standard TPC-C benchmark has lots of this. All indexes taken together are ~40% smaller with Postgres 12.
34. 1.2 Database Entities, Relationships, and Characteristics 1.2.1 The components of the TPC-C database are defined to consist of nine separate and individual tables. The relationships among these tables are defined in the entity-relationship diagram shown below and are subject to the rules specified in Clause 1.4. Warehouse Dis trict His tory Customer New-Order Order Order-Line Item Stock W W*10 3k 1+ W*30k W*30k+ 5-15 0-1 1+ W*30k+ W*9k+ W*300k+ 3+ 100k W W*100k 100k 10 Legend: • All numbers shown illustrate the database population requirements (see Clause 4.3). • The numbers in the entity blocks represent the cardinality of the tables (number of rows). These numbers are factored by W, the number of Warehouses, to illustrate the database scaling. (see Clause 4). • The numbers next to the relationship arrows represent the cardinality of the relationships (average number of children per parent). • The plus (+) symbol is used after the cardinality of a relationship or table to illustrate that this number is TPC-C’s order system is more or less a circular buffer, or queue https://github.com/petergeoghegan/benchmarksql Pictured: Diagram from TPC-C spec, Revision 5.11
35. https://speakerdeck.com/peterg/nbtree-arch-pgcon 1,1 1,2 1,3 2,1 “Split after new tuple” example Order numbers: Line items: Initial state: one page, already 100% full 1, 2 1, 2, 3…
36. https://speakerdeck.com/peterg/nbtree-arch-pgcon 1,1 1,2 1,3 2,1 50:50 page splits: Optimized page splits: 1,1 1,2 1,3 1,4 1,5 1,6 2,1 1,1 1,2 1,3 1,4 1,5 1,6 2,1 Insert 4, 5, 6…
37. https://speakerdeck.com/peterg/nbtree-arch-pgcon 50:50 page splits: Optimized page splits: 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2,1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 2,1 Insert 7, 8, 9… (Last slide’s state)
38. https://speakerdeck.com/peterg/nbtree-arch-pgcon 50:50 page splits: Optimized page splits: 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,10 1,11 1,12 2,1 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,10 1,11 1,12 2,1 Insert 10,11,12… (Last slide’s state)
39. https://speakerdeck.com/peterg/nbtree-arch-pgcon Overview 1. Big picture with B-Trees What’s the point of this “high key” business, anyway? 2. Seeing the forest for the trees Reasoning about nbtree invariants when designing enhancements. 3. A place for everything, and everything in its place How reliably unique keys simplify many things. 4. Future work Outlook for future improvements.
40. https://speakerdeck.com/peterg/nbtree-arch-pgcon Future work [1] https://wiki.postgresql.org/wiki/Key_normalization Key normalization [1] — make separator keys into conditioned binary string that is simply strcmp()’d during index scans, regardless of “tuple shape”. - Prefix compression. - “Classic” suffix truncation. Go even further — “abbreviated keys” in internal pages?
41. https://speakerdeck.com/peterg/nbtree-arch-pgcon CPU cache misses Binary searches incur cache misses during descent of tree — these can be minimized. - Abbreviated keys in line pointer array. These optimizations can be natural adjuncts. - Lehman & Yao don’t care about how values are represented on the page. - “Modern B-Tree techniques” survey paper is a great reference.
42. https://speakerdeck.com/peterg/nbtree-arch-pgcon Index tuple header with offsets May need to accommodate table access methods with row identifiers that are not at all like TIDs. Tuple header offset makes it easy for that to be accessed quickly, but also accessed as just another attribute. Skip scans. [Dynamic] prefix truncation.
43. https://speakerdeck.com/peterg/nbtree-arch-pgcon Conclusions It pays to consult multiple sources when working on nbtree codebase. - If only to confirm your original understanding. - Terminology causes problems — sometimes subtle distinctions matter a lot. Visualizing real indexes using tools like contrib/ pageinspect can be very helpful.
44. https://speakerdeck.com/peterg/nbtree-arch-pgcon Thanks!