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

On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> wrote:
> On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg(at)burd(dot)me> wrote:
> >
> > On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg(at)burd(dot)me> wrote:
> > >
> > > I've not yet measured performance or memory difference due to this change,
> > > net should be better but I should quantify that at some point.
> >
> > I've run a test in EC2 to answer this question, details at the end but this
> > change is significant for some important shapes. For a cheap operator
> > (point <-> point, 100k rows) the patch is 3-6% faster. The slot fetch is
> > cheaper than re-evaluating hypot(). For an expensive one it removes the
> > re-evaluation entirely: a 128-dim float8[] distance over 10k rows goes from
> > 197 ms to 4 ms, a plpgsql expression index from 139 ms to 8 ms. box_ops is a
> > wash (+0.1%). The circle_ops control, which doesn't qualify and gets no
> > rewrite, is unchanged (-0.9%, within the 1% stdev), so an opclass that
> > answers no pays nothing.
> >
> > 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.

Hey Matthias,

v5 attached. 0001 is v3 unchanged, 0002 is v4's costing patch plus commuted
matching, 0003 and 0004 are new.

> Do you have the details on what was tested to get to these results?
> And how it came to be that the results are 97% faster?
>
> The index still produces the projected distance output, which
> shouldn't be much cheaper for the index than a plan-level operator
> evaluation. Assuming 1 projection per row inside the index (which is
> reasonable for any ANN index I'm aware of) the theoretical savings are
> at most 66% (= 1 - (2/3), because you save one projection for
> xs_recheckorderby, and one projection for the plan node ORDER BY
> output column; the one inside the index remains). Or did I miss
> something -- is detoasting such an expensive factor here?

Your model is right for an index that computes the distance at scan
time, which is what pgvector's HNSW does. The 97% case is an expression
index:

CREATE INDEX ON vecs USING gist (point(vdist(v, qv()), 0));
SELECT id, point(vdist(v, qv()), 0) <-> point(0,0) FROM vecs
ORDER BY point(vdist(v, qv()), 0) <-> point(0,0) LIMIT 10000;

vdist() is a 128-dim SQL L2 distance. It runs once per row at CREATE
INDEX and the result is stored; at scan time GiST only computes point
<-> point on the stored key. So the index's "projection" is the cheap
operator, and the expensive function is evaluated zero times instead of
once per returned row. The cost moved to build time, it didn't go
away. For an AM that computes the expensive distance in amgettuple,
expect your 1/3 to 2/3 depending on recheck, not 97%. I've posted the
script and raw CSV if anyone wants to rerun them in a gist.

https://gist.github.com/gburd/3f6acd95583845f4924a548167a58e07

In hindsight that was not a fair statistic to quote, the measure should
have been limited to the impact of the change. Benchmarking is hard,
and this time I wasn't trying to cheat, but I guess that 97% shouldn't
have been the lead or it should have been made clear what I'd measured.

> Kind regards,
>
> Matthias van de Meent
> Databricks (https://www.databricks.com)

May 2024 in [1] Tom said:

"I'm uninterested in making the world safe for a design that's going
to fail if the planner doesn't choose an indexscan on a specific
index."

I agree with this, and I think I've stuck to it with the changes I've
proposed in the planner. amcanreturnorderby is a promise that for a
non-rechecked row the index's value is exactly the operator's result.
So a query's output doesn't depend on whether the index was chosen: a
Seq Scan + Sort shows the same number, it just pays more for it. An AM
whose score needs index-wide state can't make that promise and gets
nothing from this.

and then:

"Note that even if this indexscan is chosen, that doesn't ensure that
we won't need an explicit sort later [...] So it's far from trivial
to decide that the scan node doesn't need to emit the sort column."

We don't decide that. The scan still emits the sort column; it just
doesn't compute it again. A Sort, Limit WITH TIES or Merge Append
above it reads the same Datum it always did.

Later Tom and Heikki, in December 2023 [2][3][4]:

Heikki's patch was returned with feedback in CF 2024-03 and hasn't been
picked up since [5]. This series is not that patch: it doesn't touch
resjunk or the junk filter, which Tom said he wanted to keep [4]. But
Tom's review [3] asked for three things, and they map onto this series
like this:

1) "say we have an index on f(x) and the query requires sorting by f(x)
[...] we need to not charge the evaluation cost of f() for that plan"

That's 0002 for kNN. It also matches a commuted ORDER BY now: "const
<-> col" becomes "col <-> const" for the index, and v4 missed a target
entry written the first way.

2) "you're only munging the final top-level targetlist not anything for
lower plan levels [...] it leaves everything on the table as soon as
there's more than one level of plan involved"

That's 0003. Below a join, an ordering Index Scan's target was
rel->reltarget (Vars only), so the join computed the ORDER BY expression
itself and 0001 never fired. 0003 gives such an IndexPath its own
target, rel->reltarget plus the returnable ORDER BY expressions, but
only when the final targetlist needs them. fix_join_expr() already
matches whole non-Var input expressions, so the join's copy becomes a
reference with no setrefs change. The join isn't charged for it either.

3) Heikki [4] showed an index-only scan on (i, expensive(i)) costed at
25M though it reads expensive(i) from the index. That's 0004: with
his example the IoS estimate goes from 25000266 to 266.

Tom also suggested waiting for the index-scan/IOS unification [4], which
has since become the amgetbatch work. The commit ddce1da5b1b has
table_index_getnext_slot, but not amgetbatch. This series doesn't touch
the AM or table AM interface, only nodeIndexscan.c and the planner, so I
don't think it needs to wait. If amgetbatch reshapes nodeIndexscan.c
first, rebasing 0001 is mechanical.

On whether this should be core at all: pg_fts v1.9.0 (a bm25 index I've
developed) does the same thing from an extension [6]. A planner hook
swaps resjunk entries for a C function that returns a "current distance"
the AM stashed in a backend global. It works for one AM, but the global
is clobbered if another ordering scan on the same index runs between
gettuple and projection, such as a correlated subquery in the tlist.
The slot-based version in 0001 has no such hazard, which is the main
reason I'd rather fix it here.

0003 numbers

Same data dir, v4 vs v5, -O2 without cassert, 200k-row fact table with
a GiST index on slow_pt(p) (plpgsql, ~13us/call, COST 1000), joined to
a 1001-row dimension, median of 3 runs:

SELECT f.id, d.region, slow_pt(f.p) <-> point(500,500)
FROM f JOIN d ON d.cat = f.cat WHERE <filter>
ORDER BY slow_pt(f.p) <-> point(500,500);

---- v4 ------------ ---- v5 -----------
filter plan est ms plan est ms
-------------- ---- ------ ------ ---- ----- -----
region < 9 kNN 471724 2304.1 kNN 21224 152.5
region < 6 Sort 316379 1464.4 kNN 21224 145.3
region < 4 Sort 212272 984.3 kNN 21224 144.9
region < 2 Sort 108315 496.5 kNN 21224 138.3
region = 0 Sort 56436 256.4 kNN 21224 140.5

"kNN" is Nested Loop over the ordered GiST scan with a Memoize on the
dimension; "Sort" is Sort over a hash join. With LIMIT 1000 the plan
was already kNN on v4 and stays kNN; 0003 removes the per-row
evaluation, 15-22 ms -> 2.3-8.4 ms. For the opposite case I also ran
very selective filters (d.cat < 10, < 3, = 0), where the Sort plan
really is cheaper. v5 keeps it, 7-32 ms against 100-138 ms for the
forced kNN plan.

Things I'm less sure of:

* Only immediate join inputs are considered (looking through Material
and Memoize). That covers what I could build, since the value can't
reach a higher join without going through this join's own tlist.
Someone may find a shape I missed.

* 0003 is limited to plain base rels. Appendrel children are left out
because Append and MergeAppend build their own child tlists. The
MergeAppend-over-kNN case already worked through the scan/join target,
so I didn't widen the change for it.

* 0004 only fixes the estimate. It changes the plan when the IOS path
is already in contention, kept for its pathkeys or a qual. It doesn't
make an IOS win on the expression alone. Heikki's exact query (no
WHERE, ORDER BY expensive(i), index on (i, expensive(i))) still picks
Seq Scan + Sort, because the base rel's paths are compared before the
expression is charged to any of them. Fixing that means giving IOS
paths their own targets the way 0003 does for kNN. I tried to do
that, and add_path() still kept the seq scan with nothing to tell them
apart. This needs discussion, likely a new thread to get it right.

* Matching is still equal() on top-level entries, plus the commuted
form. A different spelling of the same value isn't matched; the
result is correct, just not optimized. This seems worthy of a bit
more attention in the next series.

* The discount is only as good as the declared COST. With the default
COST 100, an expensive function still runs faster under 0001 but is
planned as if cheap, so 0002/0003 may not flip the plan. That's how
procost works everywhere; prosupport with SupportRequestCost is the
fix for an extension that knows better, right?

Thanks for reading.

best.

-greg

[1] https://postgr.es/m/2246002.1714670501@sss.pgh.pa.us
[2] https://postgr.es/m/2ca5865b-4693-40e5-8f78-f3b45d5378fb@iki.fi
[3] https://postgr.es/m/2935085.1703806977@sss.pgh.pa.us
[4] https://postgr.es/m/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi
and Tom's reply https://postgr.es/m/3227129.1703874197@sss.pgh.pa.us
[5] https://commitfest.postgresql.org/patch/4717/
[6] https://github.com/gburd/pg_fts, fts_reuse_distance() in
pg_fts_customscan.c (commit efca0cf)