标签：#internals

I recently commented on Jonathan Lewis’s blog, Savepoint Funny , where I compared how PostgreSQL handles uniqueness differently: “PostgreSQL resolves uniqueness through heap tuple visibility". This deserves a more detailed explanation. In Oracle, unique indexes store unique entries because the B-tree key is the index key, preventing duplicates. Non-unique indexes add the ROWID to ensure that all entries are physically unique, even when indexed column values are duplicated. In PostgreSQL, all indexes, even unique ones, created explicitly by CREATE UNIQUE INDEX or implicitly to enforce a unique constraint, behave like non-unique indexes by appending the TID (tuple ID, similar to Oracle's ROWID) to the index key. This indicates that the index itself doesn't guarantee physical uniqueness, allowing multiple entries to have identical logical keys but point to different heap tuples. The actual uniqueness verification occurs at the heap level, not within the index entries. Initially, this might seem unusual—a unique index that permits duplicates. However, PostgreSQL requires this because of its MVCC system. MVCC allows duplicate entries to coexist in an index, since they can represent different versions of the same logical row. Still, PostgreSQL must guarantee that no MVCC snapshot views two rows with the same index key. Oracle doesn't face this issue because its MVCC implementation also versions index blocks, allowing a single index version to maintain unique keys. Let’s show that. Page inspect In PostgreSQL, the heap contains the table data, and index entries point to heap tuples. Visibility depends on the heap header, especially the transaction information. Index scans often visit the heap pages to check visibility, except for index-only scans, which use the heap's visibility maps as an optimization. B-tree indexes can store entries for multiple versions of the same logical row, including versions that are no longer visible to current snapshots. To ensure uniqueness, the

We opened Chapter 1 with a single line, SELECT * FROM users WHERE id = 1 . For that line to leave the client and come back as a result row, the PostgreSQL backend went through five stages. First it decided which processing path the message should take; then the parser and analyzer turned the text into a tree and gave it meaning from the catalog. The rewriter expanded views and injected policies to transform the tree, the planner weighed the possible execution paths by cost and picked the cheapest one, and the executor followed that plan, pulling up one tuple at a time and sending them back to the client. Chapter 1 was a story about how a query is processed . What tree a given SQL becomes, what plan it turns into, in what order it runs. From start to finish, a chain of logical transformations. But what every one of those stages ultimately deals with is data. The executor pulls up tuples, yet where on disk those tuples lie and in what shape, how they come up into memory, Chapter 1 never asked. When the planner judged an index scan cheaper than a sequential scan, it never opened up what that index physically is. Chapter 1 followed only the logical journey of a query, leaving untouched the substance of the data that journey stands on. Chapter 2, Storage & Access Methods, opens up that substance. In what unit data sits on disk (page), where disk and memory meet (buffer manager), where and how a row survives (heap), and how that row is found quickly (B-tree and the specialized indexes). The very tuple the planner weighed by cost and the executor pulled up in Chapter 1, where it actually came from and how it came to be there, is what Chapter 2 reveals. If Chapter 1 was the logical life of a query, Chapter 2 is the physical dwelling of data. We now look at how the data a query reaches for actually lives on disk.

A scan node sits at the leaf of the tree and pulls rows from a single table. A join node sits in the middle and brings together the rows that its two children send up. It takes one row from users , one row from orders , checks whether they belong to the same user, and if they match, emits the combined row. PostgreSQL has three nodes for this one job: NestLoop, HashJoin, and MergeJoin. The reason a single task splits into three nodes is much like the reason scans did. There is more than one way to find matching pairs from two inputs, and which way is cheapest depends on the size of the inputs and the shape of the join condition. Deciding which way is cheapest, by costing the alternatives, was the planner's job in an earlier chapter. This section looks at what those three nodes actually do when they execute. Given the same two tables, the three find matches in completely different ways, and that difference in approach is exactly what tells them apart. How the three nodes route requests All three join nodes are internal nodes with two children. One child is called the outer, the other the inner. All three run on the Volcano model's pull framework: when the parent asks for the next row, the join node takes rows from its two children, builds one matched row, and sends it up. The only difference is the order and manner in which it routes pull requests to its two children. NestLoop pulls the inner from the start all over again for each outer row it receives. HashJoin slurps the inner in one pass to build an index in memory, then takes outer rows one at a time and probes that index. MergeJoin, on the assumption that both sides are sorted in the same order, advances both sides one step at a time in lockstep. NestLoop: rescan the inner for every outer row The simplest method is NestLoop. As the name says, the loops are nested. The outer loop takes one row from the outer; the inner loop scans the inner from beginning to end, looking for inner rows that match that outer row. Wh

By the time 1.4 ends, the planner has produced one PlannedStmt. Inside it is an execution tree built from Plan nodes, frozen into a form you can follow step by step, something like "go into the primary key index on users, fetch the one matching row, then output that whole row." But that is still only a blueprint. Reading actual pages off disk, picking out the rows that match the condition, handing results back to the caller: none of that has happened yet. The stage that takes that blueprint and produces actual rows is the executor. The difference between the planner and the executor is the difference between deciding and doing. The planner was the stage that weighed "which index, in what order, with what join method" by cost and chose . The executor takes the chosen approach and carries it out as is . There is nothing left to choose. It just runs the nodes baked into the plan tree and pulls rows out of them. To run it, the executor takes the Plan tree it received and turns it into a PlanState tree. The Plan tree is the static blueprint the planner made, and it does not change during execution. But to actually run, each node needs state that changes as execution proceeds: which row it is reading now, whether the hash table is fully built, what tuple it has buffered from a child. So when execution begins, a PlanState tree with the exact same shape as the Plan tree is created. The blueprint Plan tree is left untouched, and the running state lives in that PlanState tree instead. How the executor produces result rows is the heart of the stage. The executor does not build the entire result set at once and stack it up. Instead, it asks the topmost node of the tree for "the next row," and that request travels down the tree to the leaves. When a leaf scan node reads one row from a page and passes it up to its parent, that row climbs up one level at a time through joins and filters until it reaches the top. The top sends that single row to the caller (the client, or the targe

Everything from 1.4.1 through 1.4.9 happened inside a single function, standard_planner() . Building paths, costing them, searching for a join order, estimating cardinality from statistics: all of it runs inside that one function. Yet PostgreSQL does not call standard_planner() directly. It puts another function, planner() , one step ahead of it, and has planner() call standard_planner() . And planner() can be made to call some other function instead of standard_planner() . That replacement is what the planner hook enables. When pg_stat_statements measures per-query planning time, or pg_hint_plan rewrites a plan according to hints, it all goes through this hook. Let's look at how PostgreSQL provides a way to observe or change planning behavior without touching a single line of the core, and how external code plugs into it. All planner() does is check the hook The body of planner() is essentially this. if ( planner_hook ) result = ( * planner_hook ) ( parse , query_string , cursorOptions , boundParams ); else result = standard_planner ( parse , query_string , cursorOptions , boundParams ); planner_hook is a global function pointer. Its default value is NULL , in which case standard_planner() is called right away. A plain PostgreSQL build always takes this path: planner_hook is empty, so the incoming query goes straight to standard_planner() . The key here is the type of planner_hook . typedef PlannedStmt * ( * planner_hook_type ) ( Query * parse , const char * query_string , int cursorOptions , ParamListInfo boundParams ); This signature is identical, down to the character, to that of planner() and standard_planner() . It takes the same Query and returns the same PlannedStmt (the execution plan). So external code only has to write a planner function matching this type and store its address in planner_hook . Let's call this function, written by external code to register in planner_hook , a custom planner function. The moment its address is stored, every planning reque