Re: Let an ordering index scan hand its ORDER BY value to the target list

On Wednesday, October 7th, 2026 at 11:45 AM, Greg Burd <greg(at)burd(dot)me> wrote:
> 0004: the estimate is fixed, but Heikki's exact query still picks Seq
> Scan + Sort, as I said in the v5 mail.

v7 attached rebased on a14041d437f. 0001-0004 are unchanged. 0005 fixes
that exact query case, and 0006 extends it to joins and partitioned tables.

I split them so 0005 can be taken without 0006. Why? Because 0006 does
add value, but it comes at a price of planning time. I don't know if
we're okay with that or not, so it's separated in a way that if it doesn't
merge that's okay. It's also possible that someone might point out a
way to keep the good parts and avoid the overhead.

Heikki's example from 2023 [1]:

CREATE INDEX ON atab (i, expensive(i));
SELECT expensive(i) FROM atab ORDER BY expensive(i);

0004 got the index-only scan's estimate right, but the path never got
that far. Every path for the rel carries the same reltarget, just Vars,
so the IOS looks a little more expensive than the seq scan and
add_path() tosses it. expensive(i) only gets charged afterwards, and by
then the seq scan has won. 0005 gives the IOS path its own target,
reltarget plus the returnable index expressions the query's tlist uses,
and add_path() keeps base-rel paths whose targets differ. That's
what Tom sketched in 2023 [2], with one extra target per index rather
than one per combination of expressions, which was Heikki's worry [1].

0004: Sort (cost=250809..) -> Seq Scan 17.3 ms
0005: Sort (cost=930..) -> Index Only Scan 0.85 ms

That's on 10k rows with a plpgsql function that does real work. On 100k
rows, paired runs (two sessions of 11 randomized blocks, c8id.4xlarge):
ORDER BY expensive(i) -95.6%, no ORDER BY -97.1%, WHERE i < 90000
-97.1%. Those force serial plans. With parallel query on, 0004 already
finds a parallel IOS for the 100k case, and 0005 is 7.5 ms vs 8.6 ms.

0005 only handles the query's sole base rel and an exact tlist entry.

0006 carries the value further. A join emits what its inputs emit, so
it reaches the top from any depth, and fix_join_expr() picks it up from
the input's tlist as it already does for 0003's ORDER BY values. The
cost model credits it wherever it appears in an expression, since
setrefs replaces it there too. That covers expensive(i) + 1 in the
tlist and expensive(i) in a filter. For a partitioned table, an Append
whose children all emit the value emits it too. Against 0005:

expensive(i) + 1, one table -97.0%
join -77.4%
three-way join -35.8%
partitioned table, joined -70.1%
joins without such an expression within +/-0.5%

0006 also changes the add_path() rule. In 0005 two paths whose targets
differ never dominate each other, which keeps more than it needs to. A
kNN path from 0003 that is cheaper and already ordered can no longer
discard the seq scan, though the seq scan can never win. 0006 compares
the extra values the way pathkeys are compared: a path that emits a
superset of another's values can dominate it, but not the other way
round.

The cost is planning time. Every join path over an input that emits a
value is kept next to the one it would have replaced, and that compounds
up the join tree. So 0006 emits a value only if it costs more than 10
times cpu_operator_cost, the same test make_sort_input_target() uses to
postpone an expression past a sort. Planning time against 0005, N-way
joins, median of 50:

rels no expr cheap expr expensive expr
3 -0.5% -0.7% +6.1%
7 +1.9% +2.0% +76.7% (5.1 -> 9.0 ms)
11 +2.0% +2.3% +83.2% (14.9 -> 27.2 ms)

Planner memory (EXPLAIN (MEMORY)) follows the same pattern:

rels no expr cheap expr expensive expr
3 94 -> 96 kB 95 -> 97 kB 94 -> 120 kB
7 4.4 -> 4.4 MB 4.4 -> 4.4 MB 4.4 -> 8.5 MB
11 13.4 -> 13.4 MB 13.4 -> 13.4 MB 13.4 -> 26.4 MB

Paths kept by add_path() only go up 19% at eleven rels (649 -> 755).
The memory goes on the join paths that get built and then rejected:
6,014 become 41,751, most with their own PathTarget. It's transient
planner memory, freed when planning ends. The
backend's peak RSS for that query goes from 37 MB to 50 MB. Executor
memory doesn't grow: the plans are no wider, and the plain join drops
its 742 kB hash table because it switches to a merge join.

In those joins execution still came out ahead (seven rels 58 -> 34 ms
executing plus 6.0 -> 9.1 ms planning). But +80% planning time and
twice the planner memory at eleven rels is a real price. I'd like an
opinion on whether that trade is acceptable, or whether the value
should stop being carried at some join depth.

Two tarballs are attached, each with a .nocfbot suffix so cfbot
doesn't treat it as the patch set. cf7392-bench-r2.tar.gz.nocfbot is
everything that was in the gist I linked last time, which isn't a
durable archive. cf7392-bench-0006.tar.gz.nocfbot has the harness, raw
samples and correctness script for 0005 and 0006.

best.

-greg

[1] https://postgr.es/m/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi
[2] https://postgr.es/m/2935085.1703806977@sss.pgh.pa.us