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

On Tuesday, October 6th, 2026 at 12:29 PM, Greg Burd <greg(at)burd(dot)me> wrote:
>
> What this means is a) this is a good performance win, and b) I now need to see
> if it makes sense to adjust the costing of this pattern given that some shapes
> are ~97% faster now. For instances, a vec_10k the plan costs ~50× what it
> actually does with this fix in place. I'll poke around and see if I come up
> with something that avoids tipping the decision in the wrong direction (away
> from an index scan) and add a patch in if I do.

I did, it's 0002. 0001 is v3 unchanged, rebased.

The problem: an ORDER BY expression is always in the scan/join target,
as a sort column if nothing else, and create_projection_path() charges
every path rows * cost(expr) for it. With 0001 the ordering Index Scan
never pays that, but Seq Scan + Sort and Bitmap Heap Scan + Sort still
do. So with a costly ORDER BY expression the kNN scan was overcharged
by up to ~32x and lost to Sort plans that ran 1.2-13x slower.

0002 adds a static path_target_cost() in pathnode.c that leaves out the
target entries a plain IndexScan takes from its ORDER BY values;
create_projection_path() and apply_projection_to_path() use it. The
"does the scan return this one" test, index_orderby_returnable(), is
shared with create_indexscan_plan(), so what is costed is what setrefs.c
builds. An expression that only contains the ORDER BY expression, e.g.
(expr) * 2, isn't rewritten and is still charged.

Same data dir, v3 vs v3+0002, -O2 without cassert, 200k rows, ORDER BY
slow_pt(p) <-> point(500,500) where slow_pt() is plpgsql at ~13us/call
declared COST 1000, median of 5 runs. "Sort" is Sort over a Bitmap Heap
Scan on a btree on grp:

---- v3 ---------- -- v3+0002 -------
WHERE plan est ms plan est ms
------------------ ---- ------ ------ ---- ----- -----
grp < 50 Sort 257908 1109.1 kNN 16428 85.7
grp < 20 Sort 99637 437.5 kNN 16428 83.1
grp < 10 Sort 47211 212.5 kNN 16428 81.1
grp < 10 LIMIT 2e4 Sort 47211 214.0 kNN 16428 83.5
grp < 5 Sort 22042 101.2 kNN 16428 81.1
grp < 2 Sort 6463 34.9 Sort 6463 35.4

grp < 2 rightly stays a Sort. Unfiltered and LIMIT cases were already
kNN on v3 and don't change plan. Costs are byte-identical to v3 for
circle_ops, Index Only Scan, bitmap scans and any query without a
returnable ORDER BY value in its target. Planning a kNN query took
~61us with and without 0002; a join query was too noisy to call either
way. The new gist test picks the kNN plan with 0002 and a Sort without
it.

Questions I'd expect, and why it's done this way:

* Why not fix it in cost_index() or amcostestimate? The charge isn't
made there. An IndexPath's own target is rel->reltarget (Vars only);
the ORDER BY expression is first charged when the scan/join target is
applied, so that's where the IndexScan's exemption has to be.

* Why re-sort rel->pathlist and partial_pathlist? Applying the target
used to add the same cost to every path, so
apply_scanjoin_target_to_paths() could assume order was kept. Now an
IndexPath can get cheaper relative to its siblings, and
add_path_precheck() and the linitial(partial_pathlist) callers rely
on that order. sort_pathlist_by_cost() is a stable insertion sort, a
single pass in the usual already-sorted case. To be clear: I haven't
produced a wrong plan from an unsorted list, this is defensive, and
the partial_pathlist half can't trigger today since neither GiST nor
SP-GiST is amcanparallel. Happy to drop it if people would rather.

* Doesn't this duplicate setrefs.c's matching? It repeats the equal()
walk over the target, yes, but on the same predicate. The two must
agree or we cost one plan and build another, and sharing
index_orderby_returnable() is the cheapest way I found to keep them
together without moving the setrefs decision into path creation.

Things I'm less sure of:

* An ordered IndexScan below a join (nestloop inner, merge join input)
isn't helped. That's consistent, since setrefs only rewrites the
scan's own targetlist and there the expression really is evaluated
above it, but it means the win is limited to the top scan/join rel.

* Matching is equal() on top-level entries only, so it's
representation-sensitive: an ORDER BY expression that's semantically
the same but built differently (an inserted RelabelType, say) is
neither rewritten nor discounted. Consistent, but a missed case.

* Cheap operators get a small discount too (cpu_operator_cost * rows for
point <-> point). That's correct per 0001's numbers, it was being
overcharged, but it does nudge qualifying point/box kNN plans slightly
cheaper than before.

* The discount is exactly the declared COST, like every other
expression cost. A truly expensive ORDER BY function left at the
default COST 100 still runs faster with 0001 but is planned as if it
were cheap, so 0002 may not flip its plan.

v4 applies to current master.

best.

-greg