Last week I wrote about modular verification of systems through open TLA+ specs and rely-guarantee discharge. In this post, I apply the same approach to study the metastability mechanics of a retry storm. Through this modeling I show that when the system is metastable, it is due to some trigger/shock that displaced the system outside the rely-guarantee discharge conditions of its components. 

The model

I use the retrier-server example from the "Characterizing Metastable Faults and Failures" paper and model it in TLA+ as a composition of a retrier and a server component.

The shared interface between the two components consist of the following variables:

• qf: fresh work queued at the server
• qd: duplicate (retry) work queued at the server
• done: the count of fresh requests the server completed this round, which the retrier reads and clears
• turn: a flag forcing alternation between the retrier and server steps

The retrier has one private variable, p, which denotes the pending fresh requests: the requests sent and not yet acked. A retry is a duplicate of a request already counted in p, so sending one does not grow p. The server has no private state, and does not know about p.

The constants in the specs parametrize the most important system characteristics:

• S=3 is the server capacity to process units per round
• AMax=2 is the max arrivals of fresh requests per round; retries arrive on top of this
• T=2 denotes retry timeout in rounds.

Since AMax<S, client demand stays below server capacity, so under normal conditions the server coasts. Whatever goes wrong will be due to a trigger/shock. Recall that metastability is a three act play: a trigger creates a backlog, the trigger goes away, but the system fails to recover. Since we only study the last act here, I model the trigger by starting the system in an already displaced state: Q0 requests are already queued at the server (qf=Q0) and, none being answered yet, all still open on the retrier's ledger (p=Q0). 

How does this initial shock then convert into retries? In my model, the retrier does not keep track of latency directly, rather it counts what it is waiting on, and Little's law turns the count into a duration. With p-done requests still unacked and S served per round, the wait is about (p - done)/S, so the timeout fires exactly when p-done>S*T. Let's call that LatThresh=6. The first LatThresh pending requests are deemed within their latency budget. But, anything beyond that has been waiting longer than T and gets retried, spread over the T rounds of the timeout period. This flux (recomputed each round from what is still pending) is the number of duplicates the retrier emits into qd (not qf) on its turn.

flux == NatSub(p - done, LatThresh) \div T

The server serves Min(S, qf + qd) units per round, split between the qf and qd classes in proportion to their queue sizes. Only a fresh request service gets an ack on done. That is, a request earns one useful ack no matter how many copies of it get served, and serving a duplicate is treated as pure waste. So these retries/duplicates add queue load without subtracting anything from p (pending requests), and this is what fuels the retry storm. 

The open specs and their relies

Each component is model-checked in isolation by using an "Env" stub for its partner.

The retrier's stub (=EnvS=) emulates a server that serves Min(S, qf+qd) units (split any way between qf and qd, when =S= is less than qf+qd), and acks fresh completions. Against this,  the retrier establishes its accounting invariant

PAcct == p = qf + done

PAcct says that the value of the client's ledger p for pending requests is equal to the server's fresh queue + the acks in transit. In turn, the retrier guarantees that it won't send retries while qf <= LatThresh, and that total queue growth per turn is bounded by AMax plus the flux. Note the wording: the retrier acts on p (the flux formula reads p-done), but it states its guarantees over qf, which its partner can see. PAcct is the bridge between the two: since p-done=qf under it, the flux can be rewritten as NatSub(qf,LatThresh)\div T, and the retrier's step implies the server's stub only under PAcct.

The server's stub (EnvR) emulates fresh arrivals of at most AMax, and retries of at most NatSub(qf, LatThresh)\div T ( the same flux again, in its qf form). Against this, the server guarantees a stability basin: if qf + qd <= LatThresh at a round start, it stays there, inductively, forever.

The composition and two scenarios

Compose.tla drops both of the Env stubs and conjoins the Retrier and Server actions together:

Next == Rt!RetrierTick \/ (Sv!ServerTick /\ UNCHANGED p)

Let's call qf + qd the backlog, all work queued at the server. We will use two properties over the backlog to frame our findings. The healthy states is Good == qf + qd <= S + AMax, a backlog of no more than one round's arrivals on top of what the server clears in a round. And stabilization is the property that the system eventually reaches =Good= and stays there, written <>[]Good. Secondly, Bounded == qf + qd <= 50 is a simple safety cap saying the backlog never blows past 50.

With these in hand, let's run two configurations on either side of LatThresh=6.

Q0 = 5, just inside of LatThresh. Everything passes, including stabilization. The reachable state space is small because inside the basin the retrier sends zero retries. So, the healthy case is trivial.

Q0 = 18, well outside of LatThresh. Here Bounded fails, and the violation trace shows a retry storm in action. 

The columns show that done collapses to 1 and stays there. The server does 3 units a round and gets only one useful completion, because the proportional split hands the rest to duplicates. Since p rises, flux stays at 6-7 a round.  The original stuck requests stay stuck in qf, and fresh arrivals add 1-2 items per round as well. Unfortunately, the system generates three times more load from its own retries than from its customers.

Why do the discharge proofs not help here? It's because both guarantees carry an "if". The retrier promises no retries if qf<=LatThresh. The server promises that the stability basin holds if retries are bounded. At Q0=5 the two conditions hold each other up through a circular induction with a base case. At Q0=18 both implications are still true, but since there are conditional guarantees, they just never apply since the base case is missing. 

Mapping the basin

The two runs above are two samples of a function from Q0 to a long-run outcome. We can sweep Q0 to see the whole picture, but first let's give precise definitions to explain the outcomes better.

We have already seen the good outcome, guaranteed recovery, the property <>[]Good that passed at Q0=5. A companion check confirms that from Q0=5 no reachable state is one of permanent failure.

The bad outcome is *permanent failure*: a state from which no continuation ever recovers. To certify it we need a concrete region of such states: Trapped == qf >= 8*S  /\  qd >= 3*qf

How would qf, the fresh queue, get this large? With qd>=3*qf, duplicates own at least three quarters of the queue, so fresh work's share of the proportional split rounds down to zero, and all three units of capacity go to duplicates, every round. Since qf receives up to AMax arrivals per round and loses nothing, the fresh queue creeps up, even though the server capacity S=3 exceeds max fresh arrivals AMax=2. 

A large =qf= is what keeps the trap fed. Zero fresh service means done=0, so by PAcct the pending ledger is p=qf. With qf >= 8*S =24, the flux is (24 - 6) \div 2 = 9 duplicates per round which swamps the 3 the server drains per round and this causes qd to grow three times faster than qf grows. The server runs at 100% utilization and accomplishes nothing useful, forever. Note that Trapped is a conservative region: it does not cover every doomed state (the sweep below finds dooming displacements well outside it), but it is a region where doom is provable by closure. 

To show this more formally, we show two things. First, the trap is reachable: from Q0=30, assert ~Trapped as an invariant and TLC violates it -- the trace is the descent into the trap. Second, the trap is closed: for this, set Init=Trapped, so every trapped state is a start state, and verify no execution leaves the Trapped state. Reachable plus closed is an impossibility certificate built from two invariant checks.

"Does Q0 recover?" is the stabilization check: does =<>[]Good= hold? And "Is =Q0= doomed?" is the reachability check: assert ~Trapped as an invariant and see whether TLC finds a path into the trap.  So the sweep is a for-loop that runs both checks at each Q0.

Our two example runs were rows one and three: Q0=5 recovers, Q0=18 is doomed. The middle band, where neither fate applies, is worth exploring.

In the middle band Q0= 7..9 the stabilization property fails: under sustained load the backlog neither drains nor explodes, since inflow (2 arrivals + 1 retry) exactly matches capacity 3, and the system orbits forever. But the trap is unreachable, and an additional check shows recovery is still possible. If we restrict fresh arrivals to zero, <>Good passes. 

The same quiet-recovery check also passes at Q0=10,15,20, displacements from which the trap is reachable. There is no contradiction here though. These states are not in the trap (that needs qf >= 24, qd >= 72), the trap is merely downstream of them. "Trap reachable" says some continuation falls in. "Quiet recovers" says the continuation that cuts arrivals does not get captured by the trap. Above Q0=10 you are at the risk of getting trapped, but if you shed load now, you can stay out.

Note that "quiet" stops fresh arrivals, but the retries keep firing, since flux is driven by p, not by new traffic. Quiet works before the trap because with no new arrivals the fresh queue drains, acks flow, p falls, and the flux dies out on its own. Inside the trap that path is long gone: fresh service is starved to zero, so p never falls and the retries feed themselves regardless of arrivals. To act on the retries directly you need a different lever, capping the retry flux itself. That is the fix below, and unlike quiet it works from every state.

Fixing the retry law

The fix is to give the retrier a budget B. This is a hard cap on how many retries it may emit per round, no matter how large its pending backlog grows. (This is the token bucket/retry circuit breaker approach that production SDKs already implement.) In the spec this is a one-line change to the flux rule:

flux == Min(rawflux, B)

Choose B so that AMax+B < S. Then the total inflow per round, arrivals plus retries, is below the server's capacity in every state, not just inside the basin. This removes the "if" from the stability argument: the basin guarantee was conditional on retries staying bounded, and now they always are. A check with TLC confirms that stabilization holds from =Q0 = 30=, deep in trap territory.

The TLC results hold at S=3, AMax=2, T=2, but I also got Claude Code write TLAPS proofs of the discharges and the basin induction, checked with tlapm, which lift them to all parameter values. The two basin theorems make the fix visible as a deleted assumption: the uncapped one requires Q0 <= LatThresh as an explicit hypothesis, the budgeted one holds with no hypothesis on Q0.

There is a second fix, from the server's side, and it may be the better one. The trap has two root causes: unbounded retries and the proportional split, and removing either dissolves it. If we swap the server to fresh-first service, the trapped states drain with no client change at all. The mechanism has two phases: fresh work is now served at full capacity, so acks start flowing, and p keeps decreasing, which drains the flux. After that, the leftover capacity chews through the accumulated qd. TLC confirms recovery from the deepest corner of the trap (qf=30, qd=120), in about 70 rounds. The retrier's guarantees survive the swap (its rely never depended on a specific split policy). The server-side fix also scales where the budget approach fails: with =N= clients each holding budget B, safety needs N * (AMax + B) < S, whereas one fresh-first server protects itself against any number of clients.

Conclusion: did composition matter?

Would a monolithic spec have found the storm just as well? Yes, but what the compositional framing put on the table is the contract itself. In our runs, the storm sustained itself while every contract check kept passing: the system failed with no component at fault. That observation cannot even be stated without making the contracts explicit. And once we state the contracts, we zero in on the problem. Both original guarantees were conditional, holding only inside the basin. Both of our fixes were contract edits: the retry budget strengthens the retrier's guarantee to "at most B retries, from every state", and fresh-first strengthens the server's, letting each partner's rely hold unconditionally. The monolithic model shows the backlog grows, whereas the compositional one is needed to show which promise was too weak, and strengthening that promise is the fix.

Specs and configs are available here: https://github.com/muratdem/retry-stab-modular-spec

Mongorewind: Rewind Your MongoDB Test Data Without Restoring a Backup One day, my friend Martín told me about a problem he and his team were dealing with.  Every time they needed to run a pre-production test, they had to restore a copy of the production database into their test cluster. That process alone takes about … Continued

The post Mongorewind: Rewind Your MongoDB Test Data Without Restoring a Backup appeared first on Percona.

Percona Server for MySQL now ships with a fully open source OpenID Connect (OIDC) authentication plugin, available starting with Percona Server for MySQL 8.4.11-11 and 9.7.2-2 (not yet released as of this writing). It allows a MySQL account to authenticate against any standards-compliant Identity Provider (IdP) instead of relying on a locally stored password, closing … Continued

The post OpenID Connect Authentication for MySQL, Now Fully Open Source appeared first on Percona.

Today, tech folk are scrambling to change their workflows to meet newly inflated 5X productivity quotas, while getting pummeled under the cognitive debt of agent-generated code. With every new model release, the gap is widening and humans are becoming more of a bottleneck in the loop, approaching closer to obsolescence as "coders".

While the programmer's job description is getting completely refactored, writing remains surprisingly unaffected. LLMs have gotten very good at generating code, but I am appalled at the absolute shit they spew as prose. They always follow the same robotic cadence and cliches, and sprinkle the same tired vocabulary all around. They take my broken yet soulful writing and transform it into a plastic soulless word slop in the name of improving prose. Their writing communicates no actual understanding and insight. I think we are all developing a visceral ick reaction to AI writing. It is trapped in the uncanny valley, and it may be stuck there for a long time.

I am increasingly convinced LLMs will not threaten decent writers anytime soon. My prediction rests on the three observations below. Tell me where my logic breaks.

The plateau on prose

The stuck-in-slop state of LLM writing is not from lack of trying. AI labs already tried hard on improving prose and hit a wall. LLM giants would have loved to ship better writing capability to conquer marketing, copywriting, and publishing at zero marginal cost.

Look at image, voice, and heck video models. They got good quickly, because they can be scaled with more parameters and compute. Compared to their rapid progress, text models plateaued hard on expression, depth, and authenticity. I think it is wicked hard to bride the final 20% (also applies for image, voice, video models).

Writing is a wicked problem

In systems theory, a wicked problem is a problem that lacks a definitive formulation, a clear stopping rule, and an objectively correct solution. Writing is the ultimate wicked problem, because the context is constantly shifting, a piece is never truly finished editing, and the true metric for success is fundamentally subjective.

Mapping domains along this wickedness spectrum explains why AI dominates certain fields but produces utter slop in others:

• Math sits on the left of the spectrum. Specifications are concise, and verification is binary and automated. Since the feedback loop is perfectly closed, AI models can rapidly solve math problems and prove results automatically.
• Code relies on formal logic and test-driven feedback. An LLM can generate functional code because compilers, unit tests, and model checkers can instantly catch errors. Verification is largely mechanical.
• Structured domains like law and finance also have some explicit boundaries as they are governed by regulatory frameworks and evaluated on empirical data.
• Writing sits at the far extreme of the spectrum. There is no well defined specification to the task at hand, and there is no ground truth or objective verification of the output. The ultimate measure of success is resonance inside another human mind. This is why AI models fail to make progress on good writing.

Writing may be an AI-complete problem

Unlike coding, which is a single-mind interaction with a deterministic compiler, prose is a dual-mind problem governed by Theory of Mind. It requires the ability to continuously simulate a reader's internal mental state in real time. To write simply and persuasively, you must track what the reader already knows, manage their cognitive load sentence by sentence, and predict how an argument will land.

Since LLMs lack an active mental model of a specific human reader, they are just  optimizing for the statistical probability of the next word over a vast dataset. They cannot empathize with the human reader, as they don't have the human lived experience. And they have zero skin in the game.

Comparative advantage and costly signals 

To land this plane, let's pull in David Ricardo and classical economics. The law of comparative advantage states that even if one party can produce everything more efficiently than another, both still benefit from specializing where their relative opportunity cost is lowest. In other words, even if AI has an absolute advantage in typing speed and generating volume at zero marginal cost, our human labor is still governed by the opportunity cost of where our scarce resources would be least wasted.

The opportunity cost for a human burning their scarce cognitive capacity on generic and repetitive tasks is now infinitely high. Instead, human effort shines where AI fails, that is for navigating wicked-problems and pushing for creativity.

This is where economics meets evolutionary biology, as "human proof-of-work" becomes the ultimate costly signal. In nature, a costly signal (like a peacock’s tail or an elk's antlers) works because it is expensive to produce and impossible to fake. As AI slop saturates the web, with the same token (pardon my pun), the economic value shifts entirely to an authentic human voice.

Unlike tech folk, writers don't have to change a damn thing about how they work to optimize their comparative advantage and capture this costly signal. As AI is stripping away the accidental complexity of software to expose its inherent complexity, tech workers are struggling to adjust. But good writers have always been wrestling with the inherent complexity of communication at the wicked frontier, and they remain untouched. And maybe programming itself is becoming a form of writing: more opinionated, more architectural, and more about connecting with human intent.

A common way to explain PostgreSQL's INCLUDE clause is that it helps with index-only scans. That's true, but it misses an important detail. Even before PostgreSQL 11, which introduced the INCLUDE clause, PostgreSQL was already capable of supporting covering indexes:

postgres=# create table demo ( id text primary key, value text)
;
CREATE TABLE

postgres=# insert into demo(id, value)
           select
             md5(g::text),       -- using text to see it with pageinspect
             md5((g%1000)::text) -- using text to see it with pageinspect
from generate_series(1,1000000) g
;
INSERT 0 1000000

postgres=# create index demo_idx1
           on demo(value, id)
;
CREATE INDEX

postgres=# vacuum analyze
;
VACUUM

postgres=# explain (verbose, analyze, buffers)
select id from demo
  where value <= '01'
;
                                                               QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using demo_idx1 on public.demo  (cost=0.55..566.29 rows=8785 width=33) (actual time=0.008..0.551 rows=4000.00 loops=1)
   Output: id
   Index Cond: (demo.value <= '01'::text)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=50
 Query Identifier: -9119705436468283309
 Planning:
   Buffers: shared hit=5
 Planning Time: 0.118 ms
 Execution Time: 0.710 ms

The Index Only Scan covers all filtering (Index Cond: (demo.value <= '01'::text)) and projection (Output: id) without an INCLUDE clause.

Here is another example with output in PostgreSQL 8.4 and 9.3. Index-only scan for B-tree indexes was introduced in 9.2, and INCLUDE came later in 11.

This proves that you don't need an INCLUDE clause to create a covering index for a query. The same is true for other databases: Oracle users have built covering indexes that way for decades without an equivalent to the INCLUDE clause. Adding extra columns to the index can eliminate table access when the query needs those column values.

So why did PostgreSQL introduce a new syntax?

Let's create the covering index using an INCLUDE clause:

postgres=# create index demo_idx2
  on demo(value) include (id)
;
CREATE INDEX

The planner chooses it because the estimated cost is slightly lower:

postgres=# explain (verbose, analyze, buffers)
select id from demo
  where value <= '01'
;
                                                               QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using demo_idx2 on public.demo  (cost=0.55..566.29 rows=8785 width=33) (actual time=0.015..1.011 rows=4000.00 loops=1)
   Output: id
   Index Cond: (demo.value <= '01'::text)
   Heap Fetches: 0
   Index Searches: 1
   Buffers: shared hit=50
 Query Identifier: -9119705436468283309
 Planning:
   Buffers: shared hit=5
 Planning Time: 0.132 ms
 Execution Time: 1.323 ms
(11 rows)

The two indexes have the same size in this example:

postgres=# select relname, pg_size_pretty(pg_relation_size(oid))
           from pg_class where relname in ('demo_idx1','demo_idx2')
;
  relname  | pg_size_pretty
-----------+----------------
 demo_idx2 | 91 MB
 demo_idx1 | 91 MB

Both indexes store value and id in their leaf tuples, so both can support index-only scans. The difference is in the B-tree key space. For demo_idx1, ordering is based on (value, id, TID), so both user columns participate in navigation. For demo_idx2, ordering is based on (value, TID), and id is stored as additional payload and is therefore absent from pivot tuples and other upper B-tree levels.

This is visible in the number of index key attributes:

postgres=# select indnatts, indnkeyatts from pg_index 
           where indexrelid='demo_idx1'::regclass
;
 indnatts | indnkeyatts
----------+-------------
        2 |           2


postgres=# select indnatts, indnkeyatts from pg_index 
           where indexrelid='demo_idx2'::regclass
;
 indnatts | indnkeyatts
----------+-------------
        2 |           1

Pageinspect can show more details

I check the index names and enable the extension:

postgres=# \d demo

              Table "public.demo"
 Column | Type | Collation | Nullable | Default
--------+------+-----------+----------+---------
 id     | text |           | not null |
 value  | text |           |          |
Indexes:
    "demo_pkey" PRIMARY KEY, btree (id)
    "demo_idx1" btree (value, id)
    "demo_idx2" btree (value) INCLUDE (id)

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

Here are some entries from an internal page of the B-tree with all columns in the key:

postgres=# select * from bt_multi_page_stats('demo_idx1', 1, -1)     
           where type='i' order by blkno desc limit 1
\gset
postgres=# select itemoffset, ctid, itemlen, nulls, vars, dead, htid, encode(decode(replace(substr(data,4),' ',''), 'hex'),'escape'), data
           from bt_page_items('demo_idx1', :blkno) order by itemoffset limit 4
;

 itemoffset |   ctid    | itemlen | nulls | vars | dead | htid |                                          encode                                           |                                                                                                          data
------------+-----------+---------+-------+------+------+------+-------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
          1 | (11666,0) |       8 | f     | f    |      |      |                                                                                           |
          2 | (11667,2) |      80 | f     | t    |      |      | ffeabd223de0d4eacb9a3e6e53e5448dCe370679455dd6faf22304e9943c1f2fa\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 65 33 37 30 36 37 39 34 35 35 64 64 36 66 61 66 32 32 33 30 34 65 39 39 34 33 63 31 66 32 66 61 00 00 00 00 00 00
          3 | (11668,2) |      80 | f     | t    |      |      | ffeabd223de0d4eacb9a3e6e53e5448dCf9ae9b3ef06aa649c69149c580697d44\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 66 39 61 65 39 62 33 65 66 30 36 61 61 36 34 39 63 36 39 31 34 39 63 35 38 30 36 39 37 64 34 34 00 00 00 00 00 00
(3 rows)

You can recognize the same value (ffeabd223de0d4eacb9a3e6e53e5448d) for two id (e370679455dd6faf22304e9943c1f2fa and f9ae9b3ef06aa649c69149c580697d44)

Here are entries from a leaf page of this index:

postgres=# select * from bt_multi_page_stats('demo_idx1', 1, -1)     
           where type='l' order by blkno desc limit 1
\gset
postgres=# select itemoffset, ctid, itemlen, nulls, vars, dead, htid, encode(decode(replace(substr(data,4),' ',''), 'hex'),'escape'), data
           from bt_page_items('demo_idx1', :blkno) order by itemoffset limit 4
;
 itemoffset |   ctid    | itemlen | nulls | vars | dead |   htid    |                                          encode                                           |                                                                                                          data
------------+-----------+---------+-------+------+------+-----------+-------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
          1 | (2574,81) |      80 | f     | t    | f    | (2574,81) | ffeabd223de0d4eacb9a3e6e53e5448dCf9ae9b3ef06aa649c69149c580697d44\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 66 39 61 65 39 62 33 65 66 30 36 61 61 36 34 39 63 36 39 31 34 39 63 35 38 30 36 39 37 64 34 34 00 00 00 00 00 00
          2 | (10612,3) |      80 | f     | t    | f    | (10612,3) | ffeabd223de0d4eacb9a3e6e53e5448dCfa133607fa7a0fc0aa0c4eb5af973b0e\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 66 61 31 33 33 36 30 37 66 61 37 61 30 66 63 30 61 61 30 63 34 65 62 35 61 66 39 37 33 62 30 65 00 00 00 00 00 00
          3 | (1291,4)  |      80 | f     | t    | f    | (1291,4)  | ffeabd223de0d4eacb9a3e6e53e5448dCfa684bc1a44ca31270e620437a302582\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 66 61 36 38 34 62 63 31 61 34 34 63 61 33 31 32 37 30 65 36 32 30 34 33 37 61 33 30 32 35 38 32 00 00 00 00 00 00
          4 | (2994,61) |      80 | f     | t    | f    | (2994,61) | ffeabd223de0d4eacb9a3e6e53e5448dCfa81207e0ef8bf7c472f22d1093f9d8c\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 66 61 38 31 32 30 37 65 30 65 66 38 62 66 37 63 34 37 32 66 32 32 64 31 30 39 33 66 39 64 38 63 00 00 00 00 00 00
(4 rows)

You can recognize similar data. The leaves simply add the TID, which is exposed here as htid (heap tuple identifier). The entries are ordered by (value, id):

 fe9fc289c3ff0af142b6d3bead98a923 c8ea21e50b29b5e7081dd060e311fc7f (2574,81)
 fe9fc289c3ff0af142b6d3bead98a923 b22ba7ef4b85c722a92da83a480dd63f (10612,3)
 fe9fc289c3ff0af142b6d3bead98a923 b24f3bf60138d0b322d72be638626170 (1291,4)
 fe9fc289c3ff0af142b6d3bead98a923 b35b3291bb326500fbf6237f593f56ff (2994,61)

Let's look at the other index where id is in INCLUDE rather than the key. The leaves have similar length and format:

postgres=# select * from bt_multi_page_stats('demo_idx2', 1, -1)     
           where type='l' order by blkno desc limit 1
\gset
postgres=# select itemoffset, ctid, itemlen, nulls, vars, dead, htid, encode(decode(replace(substr(data,4),' ',''), 'hex'),'escape'), data
           from bt_page_items('demo_idx2', :blkno) order by itemoffset limit 4
;
 itemoffset |    ctid    | itemlen | nulls | vars | dead |    htid    |                                          encode                                           |                                                                                                          data
------------+------------+---------+-------+------+------+------------+-------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
          1 | (12081,14) |      80 | f     | t    | f    | (12081,14) | ffeabd223de0d4eacb9a3e6e53e5448dCe54b7a956b88f1a26234f9666332f40f\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 65 35 34 62 37 61 39 35 36 62 38 38 66 31 61 32 36 32 33 34 66 39 36 36 36 33 33 32 66 34 30 66 00 00 00 00 00 00
          2 | (12093,42) |      80 | f     | t    | f    | (12093,42) | ffeabd223de0d4eacb9a3e6e53e5448dC65e6c0b6c51f50809d390bd6af75262f\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 36 35 65 36 63 30 62 36 63 35 31 66 35 30 38 30 39 64 33 39 30 62 64 36 61 66 37 35 32 36 32 66 00 00 00 00 00 00
          3 | (12105,70) |      80 | f     | t    | f    | (12105,70) | ffeabd223de0d4eacb9a3e6e53e5448dC0053cd459922f1a843b5af3e5b384c61\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 30 30 35 33 63 64 34 35 39 39 32 32 66 31 61 38 34 33 62 35 61 66 33 65 35 62 33 38 34 63 36 31 00 00 00 00 00 00
          4 | (12118,17) |      80 | f     | t    | f    | (12118,17) | ffeabd223de0d4eacb9a3e6e53e5448dC37b9ccdafd5e83b27cf23bb1e0089e63\000\000\000\000\000\000 | 43 66 66 65 61 62 64 32 32 33 64 65 30 64 34 65 61 63 62 39 61 33 65 36 65 35 33 65 35 34 34 38 64 43 33 37 62 39 63 63 64 61 66 64 35 65 38 33 62 32 37 63 66 32 33 62 62 31 65 30 30 38 39 65 36 33 00 00 00 00 00 00
(4 rows)

However, can see that the entries are ordered by (value, TID) even if id values are present in the index entries:

 ffeabd223de0d4eacb9a3e6e53e5448d (12081,14) e54b7a956b88f1a26234f9666332f40f
 ffeabd223de0d4eacb9a3e6e53e5448d (12093,42) 65e6c0b6c51f50809d390bd6af75262f
 ffeabd223de0d4eacb9a3e6e53e5448d (12105,70) 0053cd459922f1a843b5af3e5b384c61
 ffeabd223de0d4eacb9a3e6e53e5448d (12118,17) 37b9ccdafd5e83b27cf23bb1e0089e63

That's one physical difference between the two indexes: the sort order. The columns in INCLUDE are not part of the key. They are just additional payload. This has some pros and cons that we will cover later.

There's another difference in the B-tree internal pages (root and branches) which store key ranges:

postgres=# select * from bt_multi_page_stats('demo_idx2', 1, -1)     
           where type='i' order by blkno desc limit 1
\
                                    
                                    
                                    

                                        by Franck Pachot