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

Hello,

Attached v2. The only change from v1 is in the new gist regression test: two queries that print recomputed box distances now run under extra_float_digits = 0, as create_index_spgist.sql already does for its KNN output. macOS and Windows differed from Linux in the last digit of two of the 21 distances (0.5728001396647873 vs …874, 0.6099999999999997 vs …998) a libm / FMA variation in box_closept_point, not anything this patch does. The equality check that actually verifies the substituted values (same = total = 200) was already passing on every platform.

v2 applies cleanly to current master (85adc584e2b).

best.

-greg

On Thu, 1 Oct 2026, 21:10 Greg Burd, <greg@burd.me> wrote:

Hello hackers,

I'd like to see core improve the full text search index provided in
core at some point which these days means including BM25 (and likely
other) algorithm(s). To learn about that space I've been working on
an extension [1].

While working on that I stumbled onto something that seemed odd and
worth investing time in. It turns out that an index scan followed by
an order by doesn't do what I'd expected, it doesn't use the
orderbyvals returned by the index when ordering results.

SELECT id, body <=> 'search terms' AS score
FROM docs
ORDER BY body <=> 'search terms'
LIMIT 10;

In that query the executor will get the ranked set of results from
the index scan and ignore it and then turn around and re-compute a
rank value for each document in isolation.

BM25 ranking is over a corpus, not a single document so this was a
head scratcher because to me this looked like doing double the work
only to get incorrect results.

If it's getting incorrect results then that's probably an issue in
your extension's definitions.

I did some digging [2] and I find [3] I'm not alone [4]. And that I
agreed with Chris Cleveland's [5] statement:

It would also be nice if the orderbyval could be made available in
the projection. That way we could report the score() in the
result set.

Only to find later that Tom explained that this was a more subtle
issue that it seemed to be on the surface.

An index ordering operator is an optimization that the planner may
or may not choose to employ. If you've designed your code on the
assumption that that's the only possible plan, it will break for
any but the most trivial queries. [6]

Reading into Tom's objection what I take away is that one should not
make the operator's own value index-dependent, so that the same SQL
expression means different things under different plans, stop me if
I'm wrong.

Correct. An index's presence (or being selected in planning) must not
affect queries' row-data output, unless the query has sufficiently
incomplete ordering, or the query introspects the catalogs that
describe that index's existence (but that is besides the point). If
your operator relies on the whole table's corpus for weights, then
you'll have to figure out how the operator gets access to the whole
table's corpus' weights even outside index scan plans -- post-filter
ordering is a valid plan approach and sometimes the best plan option
available, even when there is a bm25/vector/etc. index available.

I propose that when the executor chooses an Index Scan and the AM
reports its value as exact (`xs_recheckorderby = false`), the
executor may substitute that value for a target-list occurrence of
the identical ORDER BY expression. It may not substitute anything
else.

What "value" are you talking about? Table and Index scans produce
their results in TupleSlots, and these don't contain the projected
order-by's expression.

Also note that it is not strictly necessary for indexes to know the
exact output of an order-by expression to know if the ordering it
outputs needs rechecking: E.g., a query that orders by distance from
a timestamp, but stores only the week number of the timestamps, can
still give you a correct ordering that doesn't need rechecking as long
as the index only has one value per week. The index won't necessarily
be able to produce the exact ordering value of the output tuple, but
it will produce data that is ordered in the same order as the
expression would be.

- For an AM whose value differs from the operator's (pgvector's
squared L2, every BM25 AM), the substitution is observable.

Then isn't every one of those indexes inherently breaking the AM contract?

The patch mirrors what Index Only Scan already does for indexed
columns. With IoS, setrefs rewrites target-list expressions that
match an index column into `INDEX_VAR` references. Here, it rewrites
target-list expressions that match an ORDER BY expression into
references to the scan's ORDER BY values.

It's not quite mirroring the IOS definitions, because it's missing an
equivalent for amroutine->amcanreturn(). See also my comment above
about truncated knowledge giving correct results in certain
situations: I think it's useful to be able to decouple "can return
tuples in the correct order, with fallback" from "will provide
complete and correct orderable values for IOS output, with fallback".

Okay, that's more than enough to see if anyone agrees that this is an
important things to fix and an approach that is making good
trade-offs or not.

I do agree that we should try fixing the double (or even triple, when
xs_recheckorderby) evaluation of order-by-operator expressions.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

PS.

[5] https://pg.ddx.io/m/pgsql-hackers/CABSN6VfLK5msEDSR8wPeMh_h3xNyr2Xs5NJK8+uOZp0bVxw7Hg@mail.gmail.com/

Was this mail not available in the project's own archives?

On Monday, October 5th, 2026 at 10:39 AM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Thu, 1 Oct 2026, 21:10 Greg Burd, <greg@burd.me> wrote:

Hello hackers,

I'd like to see core improve the full text search index provided in
core at some point which these days means including BM25 (and likely
other) algorithm(s). To learn about that space I've been working on
an extension [1].

While working on that I stumbled onto something that seemed odd and
worth investing time in. It turns out that an index scan followed by
an order by doesn't do what I'd expected, it doesn't use the
orderbyvals returned by the index when ordering results.

SELECT id, body <=> 'search terms' AS score
FROM docs
ORDER BY body <=> 'search terms'
LIMIT 10;

In that query the executor will get the ranked set of results from
the index scan and ignore it and then turn around and re-compute a
rank value for each document in isolation.

BM25 ranking is over a corpus, not a single document so this was a
head scratcher because to me this looked like doing double the work
only to get incorrect results.

If it's getting incorrect results then that's probably an issue in
your extension's definitions.

I did some digging [2] and I find [3] I'm not alone [4]. And that I
agreed with Chris Cleveland's [5] statement:

It would also be nice if the orderbyval could be made available in
the projection. That way we could report the score() in the
result set.

Only to find later that Tom explained that this was a more subtle
issue that it seemed to be on the surface.

An index ordering operator is an optimization that the planner may
or may not choose to employ. If you've designed your code on the
assumption that that's the only possible plan, it will break for
any but the most trivial queries. [6]

Reading into Tom's objection what I take away is that one should not
make the operator's own value index-dependent, so that the same SQL
expression means different things under different plans, stop me if
I'm wrong.

Correct. An index's presence (or being selected in planning) must not
affect queries' row-data output, unless the query has sufficiently
incomplete ordering, or the query introspects the catalogs that
describe that index's existence (but that is besides the point). If
your operator relies on the whole table's corpus for weights, then
you'll have to figure out how the operator gets access to the whole
table's corpus' weights even outside index scan plans -- post-filter
ordering is a valid plan approach and sometimes the best plan option
available, even when there is a bm25/vector/etc. index available.

I get your point and I led with the wrong motivation. The BM25 case is
an extension problem: the operator has to find the corpus statistics
itself so that Seq Scan + Sort and Index Scan agree. I shouldn't have
framed any part of this as a way to display an index-derived number that
the operator can't reproduce.

Please read the patch as the thing you agreed with at the end of your
mail: avoiding the double (triple, with xs_recheckorderby) evaluation
of an ORDER BY operator whose value the index already computed.

I propose that when the executor chooses an Index Scan and the AM
reports its value as exact (`xs_recheckorderby = false`), the
executor may substitute that value for a target-list occurrence of
the identical ORDER BY expression. It may not substitute anything
else.

What "value" are you talking about? Table and Index scans produce
their results in TupleSlots, and these don't contain the projected
order-by's expression.

IndexScanDesc.xs_orderbyvals / xs_orderbynulls, which the AM fills via
index_store_float8_orderby_distances() and which IndexNextWithReorder
already uses to sort. The patch copies those (or, for a rechecked row,
the executor's recomputed values) into a one-row virtual slot and lets
the projection read them through an INNER_VAR instead of re-evaluating
the expression.

Also note that it is not strictly necessary for indexes to know the
exact output of an order-by expression to know if the ordering it
outputs needs rechecking: E.g., a query that orders by distance from
a timestamp, but stores only the week number of the timestamps, can
still give you a correct ordering that doesn't need rechecking as long
as the index only has one value per week. The index won't necessarily
be able to produce the exact ordering value of the output tuple, but
it will produce data that is ordered in the same order as the
expression would be.

- For an AM whose value differs from the operator's (pgvector's
squared L2, every BM25 AM), the substitution is observable.

Then isn't every one of those indexes inherently breaking the AM contract?

The patch mirrors what Index Only Scan already does for indexed
columns. With IoS, setrefs rewrites target-list expressions that
match an index column into `INDEX_VAR` references. Here, it rewrites
target-list expressions that match an ORDER BY expression into
references to the scan's ORDER BY values.

It's not quite mirroring the IOS definitions, because it's missing an
equivalent for amroutine->amcanreturn(). See also my comment above
about truncated knowledge giving correct results in certain
situations: I think it's useful to be able to decouple "can return
tuples in the correct order, with fallback" from "will provide
complete and correct orderable values for IOS output, with fallback".

Yes. This is the real hole in v1/v2. gist.sgml says that with
recheck = false the distance function's values need only order the
same as the operator, so xs_recheckorderby = false promises ordering,
not value, and a per-AM bool can't express a per-opclass property.

Okay, that's more than enough to see if anyone agrees that this is an
important things to fix and an approach that is making good
trade-offs or not.

I do agree that we should try fixing the double (or even triple, when
xs_recheckorderby) evaluation of order-by-operator expressions.

For v3 I intend to replace amorderbyvalsexact with a callback shaped
like amcanreturn: amcanreturnorderby(Relation, int attno), NULL by
default. GiST would answer true for an opclass whose distance
function is documented as returning the ordering operator's result
(in core, the point opclass; box/circle/polygon set recheck and never
reach this), false otherwise; SP-GiST likewise for the quad/kd point
opclasses. plancat.c already collects canreturn[] per column, and
indexorderbycols tells setrefs which column each ORDER BY key is on,
so the rewrite is gated per key, and an opclass that orders by a
truncated value is never asked to display one. That also decouples
the two things you listed: "can order correctly, with fallback" stays
xs_recheckorderby; "will return the exact ordering value" becomes the
new callback.

Does that shape look right to you before I write it?

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

PS.

[5] https://pg.ddx.io/m/pgsql-hackers/CABSN6VfLK5msEDSR8wPeMh_h3xNyr2Xs5NJK8+uOZp0bVxw7Hg@mail.gmail.com/

Was this mail not available in the project's own archives?

It is; sorry, that was my own mirror site https://pg.ddx.io and I have a
Tampermonkey script that converts links to it and this time I copy/pasted
the link and didn't normalize it to the one more likely to be available
in the future.

[5]: /messages/by-id/CABSN6VfLK5msEDSR8wPeMh_h3xNyr2Xs5NJK8+uOZp0bVxw7Hg@mail.gmail.com

PS: Have you tried the search at https://pg.ddx.io/search or used the MCP
server at https://pg.ddx.io/mcp ?

On Monday, October 5th, 2026 at 12:47 PM, Greg Burd <greg@burd.me> wrote:

On Monday, October 5th, 2026 at 10:39 AM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Thu, 1 Oct 2026, 21:10 Greg Burd, <greg@burd.me> wrote:

Hello hackers,

I'd like to see core improve the full text search index provided in
core at some point which these days means including BM25 (and likely
other) algorithm(s). To learn about that space I've been working on
an extension [1].

While working on that I stumbled onto something that seemed odd and
worth investing time in. It turns out that an index scan followed by
an order by doesn't do what I'd expected, it doesn't use the
orderbyvals returned by the index when ordering results.

SELECT id, body <=> 'search terms' AS score
FROM docs
ORDER BY body <=> 'search terms'
LIMIT 10;

In that query the executor will get the ranked set of results from
the index scan and ignore it and then turn around and re-compute a
rank value for each document in isolation.

BM25 ranking is over a corpus, not a single document so this was a
head scratcher because to me this looked like doing double the work
only to get incorrect results.

If it's getting incorrect results then that's probably an issue in
your extension's definitions.

I did some digging [2] and I find [3] I'm not alone [4]. And that I
agreed with Chris Cleveland's [5] statement:

It would also be nice if the orderbyval could be made available in
the projection. That way we could report the score() in the
result set.

Only to find later that Tom explained that this was a more subtle
issue that it seemed to be on the surface.

An index ordering operator is an optimization that the planner may
or may not choose to employ. If you've designed your code on the
assumption that that's the only possible plan, it will break for
any but the most trivial queries. [6]

Reading into Tom's objection what I take away is that one should not
make the operator's own value index-dependent, so that the same SQL
expression means different things under different plans, stop me if
I'm wrong.

Correct. An index's presence (or being selected in planning) must not
affect queries' row-data output, unless the query has sufficiently
incomplete ordering, or the query introspects the catalogs that
describe that index's existence (but that is besides the point). If
your operator relies on the whole table's corpus for weights, then
you'll have to figure out how the operator gets access to the whole
table's corpus' weights even outside index scan plans -- post-filter
ordering is a valid plan approach and sometimes the best plan option
available, even when there is a bm25/vector/etc. index available.

I get your point and I led with the wrong motivation. The BM25 case is
an extension problem: the operator has to find the corpus statistics
itself so that Seq Scan + Sort and Index Scan agree. I shouldn't have
framed any part of this as a way to display an index-derived number that
the operator can't reproduce.

Please read the patch as the thing you agreed with at the end of your
mail: avoiding the double (triple, with xs_recheckorderby) evaluation
of an ORDER BY operator whose value the index already computed.

I propose that when the executor chooses an Index Scan and the AM
reports its value as exact (`xs_recheckorderby = false`), the
executor may substitute that value for a target-list occurrence of
the identical ORDER BY expression. It may not substitute anything
else.

What "value" are you talking about? Table and Index scans produce
their results in TupleSlots, and these don't contain the projected
order-by's expression.

IndexScanDesc.xs_orderbyvals / xs_orderbynulls, which the AM fills via
index_store_float8_orderby_distances() and which IndexNextWithReorder
already uses to sort. The patch copies those (or, for a rechecked row,
the executor's recomputed values) into a one-row virtual slot and lets
the projection read them through an INNER_VAR instead of re-evaluating
the expression.

Also note that it is not strictly necessary for indexes to know the
exact output of an order-by expression to know if the ordering it
outputs needs rechecking: E.g., a query that orders by distance from
a timestamp, but stores only the week number of the timestamps, can
still give you a correct ordering that doesn't need rechecking as long
as the index only has one value per week. The index won't necessarily
be able to produce the exact ordering value of the output tuple, but
it will produce data that is ordered in the same order as the
expression would be.

- For an AM whose value differs from the operator's (pgvector's
squared L2, every BM25 AM), the substitution is observable.

Then isn't every one of those indexes inherently breaking the AM contract?

The patch mirrors what Index Only Scan already does for indexed
columns. With IoS, setrefs rewrites target-list expressions that
match an index column into `INDEX_VAR` references. Here, it rewrites
target-list expressions that match an ORDER BY expression into
references to the scan's ORDER BY values.

It's not quite mirroring the IOS definitions, because it's missing an
equivalent for amroutine->amcanreturn(). See also my comment above
about truncated knowledge giving correct results in certain
situations: I think it's useful to be able to decouple "can return
tuples in the correct order, with fallback" from "will provide
complete and correct orderable values for IOS output, with fallback".

Yes. This is the real hole in v1/v2. gist.sgml says that with
recheck = false the distance function's values need only order the
same as the operator, so xs_recheckorderby = false promises ordering,
not value, and a per-AM bool can't express a per-opclass property.

Okay, that's more than enough to see if anyone agrees that this is an
important things to fix and an approach that is making good
trade-offs or not.

I do agree that we should try fixing the double (or even triple, when
xs_recheckorderby) evaluation of order-by-operator expressions.

For v3 I intend to replace amorderbyvalsexact with a callback shaped
like amcanreturn: amcanreturnorderby(Relation, int attno), NULL by
default. GiST would answer true for an opclass whose distance
function is documented as returning the ordering operator's result
(in core, the point opclass; box/circle/polygon set recheck and never
reach this), false otherwise; SP-GiST likewise for the quad/kd point
opclasses. plancat.c already collects canreturn[] per column, and
indexorderbycols tells setrefs which column each ORDER BY key is on,
so the rewrite is gated per key, and an opclass that orders by a
truncated value is never asked to display one. That also decouples
the two things you listed: "can order correctly, with fallback" stays
xs_recheckorderby; "will return the exact ordering value" becomes the
new callback.

Does that shape look right to you before I write it?

Attached v3 does what I described: amorderbyvalsexact is gone, replaced
by an optional amcanreturnorderby(Relation, attno) callback alongside
amcanreturn. plancat.c collects it per column into
IndexOptInfo.canreturnorderby[], create_indexscan_plan() turns that into
one bool per ORDER BY key via indexorderbycols, and setrefs.c gates each
key separately. GiST says yes only for point_ops and box_ops (their
leaf distance is the operator's own code; I verified 0 differences over
80k rows with boxes of real area), SP-GiST for quad_point_ops, kd_point_ops
and box_ops. Circle and polygon report lower bounds and are left alone. I
added circle_ops as a negative control in the regression test, and
polygon.out reverts to master.

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.

Oops, in the last email I'd claimed the box opclass was lossy; it isn't
(gist_box_distance's recheck is under #ifdef NOT_USED). The rechecked path
is still covered by the existing polygon tests, now without a rewrite.

indexam.sgml documents the callback and says explicitly that
xs_recheckorderby = false promises ordering, not value, which was your point.

best.

-greg

On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg@burd.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. 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.

best.

-greg

Results
=======

c7i.4xlarge (Xeon 8488C, 1 NUMA node), AL2023, gcc 11.5, -O2, no cassert.
master e8f4f9e3ce2 vs v3. 1M-row tables, fully prewarmed, shared_buffers=4GB,
JIT off, parallelism off, server+client pinned to one core, A/B alternated
per-run, 11 runs each, median. Plans verified: every patched query shows
Order By Values Used: 1 except the circle control as expected.

query ORDER BY key master patched delta
(ms) (ms)
----------------- ----------------------------- ------- -------- -------
gist_point_1k p <-> pt 2.08 2.01 -3.2%
gist_point_100k p <-> pt 70.58 66.18 -6.2%
spg_point_100k p <-> pt (SP-GiST) 75.07 70.64 -5.9%
gist_box_100k b <-> pt 68.49 68.58 +0.1%
gist_circle_100k c <-> pt (lossy, no rewrite) 117.93 116.88 -0.9%
slow_1k plpgsql expr index (~13us) 15.64 2.26 -85.6%
slow_10k plpgsql expr index (~13us) 139.17 8.14 -94.2%
vec_1k 128-dim float8[] L2 distance 20.12 0.59 -97.1%
vec_10k 128-dim float8[] L2 distance 197.38 4.16 -97.9%

Stdev <= 3.3% for all rows.

On Tuesday, October 6th, 2026 at 12:29 PM, Greg Burd <greg@burd.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

On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg@burd.me> wrote:

On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg@burd.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.

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?

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg@burd.me> wrote:

On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg@burd.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]/messages/by-id/2246002.1714670501@sss.pgh.pa.us 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]/messages/by-id/2ca5865b-4693-40e5-8f78-f3b45d5378fb@iki.fi[3]/messages/by-id/2935085.1703806977@sss.pgh.pa.us[4]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi and Tom's reply /messages/by-id/3227129.1703874197@sss.pgh.pa.us:

Heikki's patch was returned with feedback in CF 2024-03 and hasn't been
picked up since [5]https://commitfest.postgresql.org/patch/4717/. This series is not that patch: it doesn't touch
resjunk or the junk filter, which Tom said he wanted to keep [4]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi and Tom's reply /messages/by-id/3227129.1703874197@sss.pgh.pa.us. But
Tom's review [3]/messages/by-id/2935085.1703806977@sss.pgh.pa.us 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]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi and Tom's reply /messages/by-id/3227129.1703874197@sss.pgh.pa.us 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]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi and Tom's reply /messages/by-id/3227129.1703874197@sss.pgh.pa.us, 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]https://github.com/gburd/pg_fts, fts_reuse_distance() in pg_fts_customscan.c (commit efca0cf). 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]: /messages/by-id/2246002.1714670501@sss.pgh.pa.us
[2]: /messages/by-id/2ca5865b-4693-40e5-8f78-f3b45d5378fb@iki.fi
[3]: /messages/by-id/2935085.1703806977@sss.pgh.pa.us
[4]: /messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi and Tom's reply /messages/by-id/3227129.1703874197@sss.pgh.pa.us
and Tom's reply /messages/by-id/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)
pg_fts_customscan.c (commit efca0cf)

On Wed, 7 Oct 2026 at 13:44, Greg Burd <greg@burd.me> wrote:

On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg@burd.me> wrote:

On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg@burd.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.

[...]

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.

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.

No, I do think that it is very important to keep this in mind, too:
We don't just avoid evaluating the possibly expensive distance up to 2
more times per row than necessary, but also avoid re-projecting the
index column definition itself (which clearly can be extremely
costly).

That column projection is something I'd mostly overlooked when trying
to figure out the performance difference: Whilst detoasting is a part
in that re-projection cost, it is not necessarily the most expensive
part of re-evaluating the full order-by expression.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

On Wednesday, October 7th, 2026 at 8:09 AM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Wed, 7 Oct 2026 at 13:44, Greg Burd <greg@burd.me> wrote:

On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg@burd.me> wrote:

On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg@burd.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.

[...]

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.

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.

No, I do think that it is very important to keep this in mind, too:
We don't just avoid evaluating the possibly expensive distance up to 2
more times per row than necessary, but also avoid re-projecting the
index column definition itself (which clearly can be extremely
costly).

That column projection is something I'd mostly overlooked when trying
to figure out the performance difference: Whilst detoasting is a part
in that re-projection cost, it is not necessarily the most expensive
part of re-evaluating the full order-by expression.

Agreed, and thanks: I undersold it. The expression-index result is real:
the patch avoids re-projecting the indexed expression, and that' is the
expensive part there.

Kind regards,

Matthias van de Meent
Databricks (https://www.databricks.com)

Two corrections to my last mail. 0001 does add an index-AM callback,
amcanreturnorderby (it doesn't touch the table AM). And it doesn't remove
a recheck: on a rechecked tuple it reuses the recomputed value. For the
opclasses that qualify today, recheck is always false, so the saving is
one projection per row.

I also found that my vector generator repeated a single vector across all
200k rows (an uncorrelated scalar subquery), so the vec_* rows were
measured on degenerate data. The slow_* rows don't have that problem.
I'll rerun with the harness fixed and post the corrected numbers.

best.

-greg

On Wednesday, October 7th, 2026 at 8:59 AM, Greg Burd <greg@burd.me> wrote:

I'll rerun with the harness fixed and post the corrected numbers.

Here they are. The gist has a new revision with the harness, every
sample and every plan [1]https://gist.github.com/gburd/3f6acd95583845f4924a548167a58e07; the old revision is still in its history.

What changed in the harness: one vector per row, AB/BA order randomized
per block, both builds run on copies of one data directory, a working
pg_prewarm, and each patch measured against its own parent commit. It
also fails on any error, and each patched build's values are checked
against the operator before anything is timed. Two sessions, 21
blocks each for the executor and 11 for the planner, c7i.4xlarge. The
95% intervals below are over the pooled blocks.

0001, executor, same plan for both:

expression index, SQL 128-d dist., LIMIT 10k -93.6% [-93.6, -93.5]
" LIMIT 1k -88.1% [-88.2, -88.0]
expression index, plpgsql, LIMIT 10k -92.2% [-92.3, -92.2]
" LIMIT 10 -53.4% [-53.9, -52.8]
box <-> point, boxes rarely contain the point -27.1% [-27.6, -26.5]
point <-> point, GiST, LIMIT 100k -2.2% [ -3.1, -1.3]
point <-> point, SP-GiST, LIMIT 100k -1.0% [ -1.7, -0.4]
box <-> point, 1/4 contain the point +0.3% [ -0.7, +1.2]
circle_ops (doesn't qualify), control +0.1% [ -0.4, +0.6]

The vector rows were -97/-98% on the bad data; with real vectors they
are -88/-94%. I'm withdrawing the -3 to -6% I gave for points. The
0003 vs 0004 builds run identical code for queries whose plan 0004
doesn't change, and still differ by 2.8-3.7%, so a couple of percent
between two builds isn't evidence of anything. Points and the control
are within that. The box result is new. dist_bp() returns 0 at once
for a box that contains the point, so the earlier tie-heavy data could
not show any saving.

0002, default settings, plan flips from Sort to the kNN scan:

grp < 50 -90.3% grp < 10 -51.8%
grp < 20 -76.2% grp < 5 +1.5% [+0.6, +2.5]

grp < 5 sits at the crossover. The kNN plan touches about 200k buffers
to Sort's 1.7k, the estimate is optimistic there, and the flip gains
nothing. That's within the build noise, but it's the worst case I
found.

0003, below a join: -44% to -90% where the plan flips from Sort to
the kNN nested loop, and -93.5% at region < 9, where the plan was
already kNN and the join now reads the value instead of evaluating it.
Selective filters keep the Sort plan, as before. Timing both shapes
under one binary confirms the planner's choice at both ends: region < 4
kNN 159 ms vs Sort 1047 ms, cat < 3 Sort 17 ms vs kNN 152 ms.

0004: the estimate is fixed, but Heikki's exact query still picks Seq
Scan + Sort, as I said in the v5 mail.

Planning time differs by at most 0.02 ms in any pair.

[1]: https://gist.github.com/gburd/3f6acd95583845f4924a548167a58e07

best.

-greg

On Wednesday, October 7th, 2026 at 11:45 AM, Greg Burd <greg@burd.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]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi:

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]/messages/by-id/2935085.1703806977@sss.pgh.pa.us, with one extra target per index rather
than one per combination of expressions, which was Heikki's worry [1]/messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi.

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]: /messages/by-id/356d5811-d8f0-4c29-a601-b61334337b11@iki.fi
[2]: /messages/by-id/2935085.1703806977@sss.pgh.pa.us

On Thursday, October 8th, 2026 at 10:25 AM, Greg Burd <greg@burd.me> wrote:

An ordered or parallel Append still computes the expression above
itself. That could be added if anyone cares.

I cared, so v8 adds 0007, which closes the gaps I listed. 0001-0006 are
unchanged from v7.

* The nullable side of an outer join. Above the join, the query's
copy of expensive(a.i) has the join's bit in a.i's nullingrels and
the scan's copy doesn't, so they never matched. But the join
null-extends the scan's value along with the Vars, so the two agree
on every row whenever the expression is strict. For a strict one,
0007 relabels the value with the joinrel's Vars as it passes it up.
At an outer join, setrefs matches it ignoring nullingrels, as it
already does for Vars there (NRM_SUPERSET), and the cost model credits
it the same way. A non-strict expression is still computed above the
join. Heikki's expensive() from 2023 isn't declared STRICT, so it's
in that group.

* Partial paths. 0006 emitted only parallel-safe values from them, but
a worker never evaluates the expression: it reads the stored value,
and everything above it references the column. So a PARALLEL
RESTRICTED function's index can feed a parallel plan now. Gather and
Gather Merge pass the values up.

* Ordered Append, MergeAppend and parallel Append, built the same way
as 0006's unordered Append.

Against 0006, paired runs as before (two sessions of 11 blocks; the
sessions agreed to within 0.4 points):

LEFT JOIN, nullable side -62%
FULL JOIN -95% (173 -> 8.8 ms)
coalesce(expensive(a.i), -1), nullable -40%
partitioned, ordered Append, merge join -29%
partitioned join, parallel allowed -19%
inner join / no expression index within +/-0.6%

The FULL JOIN number is a plan change. Without the value the planner
picks a hash full join over two seq scans and computes expensive() for
every row; with it, a merge full join over the index-only scan.

0007 costs very little at plan time: at most +2.5% planning over 0006
(eleven-rel inner join with the expression). Planner memory is the same
for inner joins and up to 3% higher for LEFT JOINs with the expression
(60 -> 62 kB at three rels).

MERGE was the one surprise. The first version stripped nullingrels
with remove_nulling_relids(), which errors on a MERGE's ROWID_VAR, and
merge.out and updatable_views.out caught it. 0007 uses its own small
mutator now. To check parallel safety, the correctness run has a
PARALLEL RESTRICTED indexed function that raises an error if it's ever
evaluated in a worker. A canary marked PARALLEL SAFE with the same
check does fail, so the check works. 48 query shapes under seven
settings (including debug_parallel_query), compared with
enable_indexonlyscan off: no mismatches. 0006 and 0007 each build
without warnings and pass the meson suite on master (16b94c40120).

The harness and samples are in cf7392-bench-0007.tar.gz.nocfbot.

best.

-greg

Hello again,

I spent some time running this code on metal instances in EC2 to see how
it performs. The microbenchmarks so far time single queries. I wanted
to see what the series does to a whole workload, including workloads
where it has nothing to do, so I ran HammerDB against v8. As I hinted
at earlier, the server was an EC2 i7i.metal-24xl (96 vCPU, 755 GB, local
NVMe, shared_buffers=192GB on huge pages), with three c8i.4xlarge
driving traffic to it.

To see the impact of different additions I've proposed in this thread I
tested three different builds:
base (a14041d437f)
0006 (v8 0001-0006), and
0007 (v8 0001-0007).

I randomized the run order within each block. I created weighted mixes
by taking TPROC-H at SF 30 and adding two plpgsql functions declared COST
5000, plus four indexes on them. Each of 96 VUs picks a query shape the
series improves with probability w, or a neutral one on the same tables
otherwise.

Three blocks of 180 s:

base q/s 0006 0007
w = 0.8 893 +7.9% [+7.4, +8.4] +196% [+191, +201]
w = 0.2 2140 +4.3% [+3.0, +5.6] +70% [+68, +72]
w = 0 4118 +0.4% [-0.4, +1.3] +1.5% [+0.7, +2.2]

The loop is closed, so the q/s gain tracks how slow the positive queries
are on base and won't carry over to another mix.

Per query on 0007, at w = 0.2 (w = 0.8 is within two points):

kNN on fgeo(), distance returned -64% (0001)
the same below a join -53% (0003)
fnorm() from an IOS stock doesn't choose -55% (0004, 0005)
fnorm() on the nullable side of LEFT JOIN -85% (0007; 0006 -1%)

FWIW, this patch series has nothing to add in cases where stock already
picks an index-only scan that returns the expression.

At w = 0 the neutral queries are within 3%. At w = 0.8 one of them is
7-10% slower on both builds and another 10% slower on 0007. Run alone
they take the same time in all three builds (5.56, 5.58 and 5.51 ms;
0.049, 0.047 and 0.047 ms). At w = 0.8, 0007 runs three times as many
queries alongside them.

Backend memory summed over the 96 backends is 417-447 MB at w = 0 in
every build. At w > 0 it is 12-17% lower on the patched builds, sampled
at the end of each run.

No expression indexes, TPROC-C at 1000 warehouses. With
log_nested_statements, auto_explain logged 21 distinct plans inside the
transaction functions. They are identical in all three builds.

48 VUs, 3 blocks 0006 +1.6% [-4.5, +8.1]
0007 -0.4% [-9.5, +9.7]
192 VUs, 10 blocks 0006 -4.9% [-11.4, +2.2]
0007 -3.7% [-10.4, +3.4]

At 192 VUs, 8 of the 30 runs hit a storm of waits on the relation
extension lock (about 300 to 2300 logged waits each), and those runs
lost up to 27% NOPM. base had 1 of 10 and 0006 and 0007 had 4 and 3. A
one-sided Fisher test gives p = 0.15 for that split. Over the pairs
where neither run had a storm, 0006 is -1.2% [-5.1, +2.9] (6 pairs) and
0007 is -0.2% [-2.6, +2.2] (7). The plans are the same, and the
executor changes touch only index scans with ORDER BY operators, which
TPROC-C doesn't use, so I can't see how the series would cause the
storms. Thirty runs don't rule it out either. Backend memory summed
over the 195 backends was 1238 (stock), 1238 (0006) and 1242MB (0007) so
only ~4MB overhead.

TPROC-H at SF 30, DOP 8. All 22 plans are identical.

base 0006 0007
power, 5 runs 4.35 s +0.1% -0.6% (CI within +/-5%)
throughput, 6 streams 4.70 s +0.2% +0.0% (2 runs, +/-7%)
planning, 22 queries 18.47 ms +1.2% +0.8%
planner memory 6609 kB +0.2% +0.2%

Q5 and Q10 jump between run times with the same plan in every build (Q5
takes 2.2 or 2.75 s), so their medians move by up to 22% depending on
which times a build drew. The other queries are within 4%, except Q6 on
0006 (+6.5%) and Q15 (-5% and -7%).

I did find one real cost. One of the positive templates is an inner
hash join over an index-only scan that stock already picks, returning
fnorm(s_phone). The plan shape doesn't change, but with the series that
query is 2-8% slower in the mixes and 8% slower alone (30.6 -> 33.2 ms
over 300k rows). 0006 made use_physical_tlist() refuse any path that
emits extra values, so the index-only scan now projects every row: in
one EXPLAIN ANALYZE the node goes from 15.3 ms to 17.9-19.2 ms. base
returns the index's physical tlist, which holds the fnorm() column
already. Keeping the physical tlist when every value the path emits is
in its indextlist should fix it. I haven't tried that yet.

The scripts, raw results and plans are in
cf7392-bench-hammerdb.tar.gz.nocfbot. Its README lists the runs I
dropped and why. To me this seems like something that started as
a simple idea, but then grew into something that has value for a wide
set of query shapes with minimal overhead.

thanks for looking.

best.

-greg

Hi Greg,

I tested your patch with a ranked GIN prototype - essentially GIN with
RUM-like ordering, where the index scan computes the BM25 score and returns
tuples in score order.
This is a very natural use case for amcanreturnorderby: the index already
has the exact score, so there is no reason to calculate the same expression
again above the index scan.
With the patch, the score produced by the index is reused directly. On my
tests this removes the redundant score calculation and gives about 1.7 -
2.2x speedup for full scans, and about 2x on larger toasted documents.
The costing change is useful too. Without it, the planner can still charge
the ordered index scan for evaluating an expression which the index has
already evaluated, and may choose a Seq Scan + Sort instead. With the patch
this distinction is visible to the planner.
One remaining issue on my side is that the cost of BM25 scoring depends
heavily on document size/detoasting, so a single static function COST is
not enough. But that seems like a separate costing problem.
So at least for ranked GIN/RUM-style access methods, this patch provides
exactly the missing interface between the index AM and executor.

Thanks, Oleg

On Wed, Oct 7, 2026, 18:45 Greg Burd <greg@burd.me> wrote:

On Monday, October 12th, 2026 at 8:34 AM, Oleg Bartunov <obartunov@postgrespro.ru> wrote:

Hi Greg,

Hey Oleg!

Thank you for taking the time to try this, and for writing up what you
found. So much of GIN and kNN search came from you and your colleagues
that it means a lot to hear the changes make sense from your side.
Until now only GiST and SP-GiST implemented amcanreturnorderby, with
functions I wrote to be slow, so yours is the first test against a
ranking AM. I'm glad the costing in 0002 helped too.

I tested your patch with a ranked GIN prototype - essentially GIN with RUM-like ordering, where the index scan computes the BM25 score and returns tuples in score order.

If you can share the prototype, or a script that builds a table and
runs your queries, I'd like to run it before I post each version.

This is a very natural use case for amcanreturnorderby: the index already has the exact score, so there is no reason to calculate the same expression again above the index scan.

Yes, it is my pg_fts[1]https://github.com/gburd/pg_fts bm25 extension that highlighted this issue for me.

With the patch, the score produced by the index is reused directly. On my tests this removes the redundant score calculation and gives about 1.7 - 2.2x speedup for full scans, and about 2x on larger toasted documents.

Yes, that's what I was shooting for.

The costing change is useful too. Without it, the planner can still charge the ordered index scan for evaluating an expression which the index has already evaluated, and may choose a Seq Scan + Sort instead. With the patch this distinction is visible to the planner.
One remaining issue on my side is that the cost of BM25 scoring depends heavily on document size/detoasting, so a single static function COST is not enough. But that seems like a separate costing problem.
So at least for ranked GIN/RUM-style access methods, this patch provides exactly the missing interface between the index AM and executor.

You're right that one static COST can't follow document size. I
haven't tried this yet, so take it as a question: could the AM's
amcostestimate scale the scoring cost by the column's average width,
or could a support function answer SupportRequestCost? I agree it's
a separate problem from this series either way.

Thanks, Oleg

If you have time to review the series, I'd be grateful to see
your name on the commitfest entry [2]https://commitfest.postgresql.org/patch/7392/. Please don't feel obliged.

best.

-greg

[1]: https://github.com/gburd/pg_fts
[2]: https://commitfest.postgresql.org/patch/7392/

Hello,

v9 attached, rebased on master (6b9f40d49ae). It fixes a bug I found
in 0001.

The bug: box_ops shouldn't have qualified for amcanreturnorderby. Its
GiST and SP-GiST leaf distances are exact arithmetic on the box, but
<->(box, point) goes through dist_bp(), which treats a point within
EPSILON of an edge's line as on it. So the index can hand back a
value that differs from the operator's in the last digits:

-- box ((0,0),(1,1)), point (0.9999996, 2)
operator 1.00000000000008
GiST/SP-GiST scan 1

Only the point opclasses qualify now (GiST point_ops, SP-GiST
quad_point_ops and kd_point_ops), whose leaf distance calls
point_distance() itself. That also withdraws the box <-> point result
in my numbers mail (-27.1%). The other numbers posted on this thread
don't involve box_ops.

The other changes:

* amcanreturnorderby takes (opfamily, opcintype, orderbyop) instead of
(Relation, attno), like amtranslatecmptype. Whether the values are
exact depends on the ordering operator, and one opfamily can hold
several. The planner keeps the callback in IndexOptInfo like
amcostestimate, so plancat.c no longer fills a per-column array.
(0001, 0002)

* An ordering IndexScan's ORDER BY value now has to pass the same
10 * cpu_operator_cost test as an index-only scan's before it is
carried up through a join. A plain point distance used to turn off
add_path_precheck() for every join above the scan, only for the
join to drop the value. (0006)

* use_physical_tlist() lets an index-only scan return its indextlist
when every extra value is already an index column, which fixes the
8% overhead the HammerDB run found (index-only scan node 11.5-12.2 ms
-> 9.6-10.2 ms in an A/B on that query). (0006)

* apply_scanjoin_target_to_paths() re-sorts a path list whenever it
replaced any path with a projection. It used to re-sort only when
the targets' exprs differed, but a path that emits extra values gets
a projection even when they're the same, and its cost can move.
(0005)

* At an outer join, setrefs.c's search_indexed_tlist_for_nulled_expr()
now requires the upper copy's nullingrels to be a superset of the
input's, as the comment always claimed and as it does for Vars. It
also strips each input tlist once rather than once per candidate,
and the cost side checks strictness only on a match. (0007)

* The ordered Append and MergeAppend collect their children the way
generate_orderedappend_paths() does, so child_append_relid_sets
means what it should. (0007)

* expr_contains() and strip_nullingrels() moved to clauses.c, and
credit_free_context is in typedefs.list from 0006. A few smaller
cleanups too, and some stale comments fixed.

New tests:
- SP-GiST point value equality, plus the box case above;
- the reorder queue with one exact and one lossy key;
- a LATERAL rescan;
- FULL JOIN, Gather Merge and Parallel Append;
- an isolation spec, eval-plan-qual-knn, showing that EvalPlanQual
hands back the updated row's distance.

best.

-greg

Hello,

v10 attached. It applies to master as of 126976a8ffc, and fixes an
assertion failure in 0001, a flaky test cfbot caught in 0007, and
several smaller problems.

The bug: IndexStoreOrderByValues() asserted that every ORDER BY key is
passed by value, but only the keys the target list reads have to be.
Another key can be by-reference: btree_gist's <-> on timestamps returns
an interval. So this crashed a cassert build:

CREATE INDEX ON t USING gist (p, ts); -- btree_gist
SELECT p <-> point(3,4), ts <-> '...' FROM t
ORDER BY p <-> point(3,4), ts <-> '...';

The fix stores only by-value keys and gives the others a null, since
nothing reads them. There's a btree_gist test for it now. Non-assert
builds were safe, they only kept a pointer they never used.

cfbot's 32-bit job failed on v9 in the pass that runs the regression
suite against an already running server. The Parallel Append test in
0007 used two partitions of the same size, so the order of the children
in the plan depended on how many pages VACUUM could mark all-visible
while other sessions held snapshots. The partitions now differ in
size. I reproduced the flip by holding a snapshot during VACUUM, and
checked that the new order holds and that the other parallel tests
keep their plans with nothing all-visible.

The rest:

* The series' tests in gist.sql reset enable_seqscan and
enable_bitmapscan to their defaults, which the file had turned off.
That turned the existing gist_ios_tupdesc test into a Seq Scan, so it
no longer tested what it was written for. The file's settings are
now restored before that test, and its output matches master again.

* Two tests could not fail. The box EPSILON check compared the
operator with itself. It now compares the scan's value with the
operator's, and fails when box_ops is allowed to qualify. The 0002
plan test ran with seqscan off. Now it runs with seqscan on, and it
flips to Seq Scan + Sort when the costing change is reverted. (0001,
0002)

* Tests that printed raw <-> distances now run with
extra_float_digits = 0. The join tests pin the join method, so
the plans don't depend on close hash-versus-merge costs. The test
that an index on only one partition doesn't count now runs EXPLAIN
VERBOSE, so it shows the join computing the value. (0001-0003,
0006, 0007)

* indexorderbyexact is now read_write_ignore: only setrefs.c reads it.
indexorderbytlist, which is a count and not a List, is renamed
indexorderbynused. It now counts the distinct ORDER BY values the
target list reads, so "Order By Values Used" in EXPLAIN can't exceed
the number of ORDER BY keys when the target list repeats one.
ruleutils.c checks dpns->plan for NULL before looking at it, as its
neighboring branches do. (0001)

* index_path_orderby_target() no longer adds the same value twice
when two ORDER BY keys are equal. (0003)

* add_extras_append_path() goes on to build the parallel Append when
some child has no non-partial path that emits the values. Before,
it gave up on all three Appends. (0007)

* Smaller cleanups: no Bitmapset allocations in path_target_cost()'s
outer-join test, one nestloop Material guard instead of two, a
shared query_tlist_exprs(), an Assert in join_path_target(), an
early return in indexonly_free_exprs() for indexes with no
expression columns, and some comments fixed. (0001, 0006, 0007)

0005 is unchanged. Each patch builds without warnings and passes the
regress, isolation and btree_gist suites on its own. The series passes
the running-server pass and CI on Linux (32- and 64-bit), macOS,
Windows and MinGW.

best.

-greg

Hello,

v11 attached, now eight patches. It brings back the box opclasses,
documents the EXPLAIN line, and cuts the planning overhead of what was
0006 and is now 0007. Oleg, the end of this mail I hope to answer
your point about a static COST.

The new 0001 is a geometry fix that stands on its own. The distance
between a point and a box went through the line-segment code, whose
EPSILON comparisons can pick the wrong edge for a point near an edge's
line. The point (0.9999996,2) is 1 from the box ((0,0),(1,1)), but
<-> said 1.00000000000008. GiST and SP-GiST compute the true distance
and order kNN scans by it, so on master an index scan can return rows
out of the operator's order:

CREATE TABLE b (id int, b box);
INSERT INTO b VALUES (1, '((0,0),(1,1))'),
(2, box(point(0.4999996, 0), point(1.4999996, 0.99999999999996)));
CREATE INDEX ON b USING gist (b);
SET enable_seqscan = off;
SELECT id, b <-> point(0.9999996, 2) FROM b
ORDER BY b <-> point(0.9999996, 2);
id | ?column?
----+------------------
1 | 1.00000000000008
2 | 1.00000000000004

SP-GiST does the same. A box's edges are parallel to the axes, so the
closest point is the point clamped to the box. 0001 computes it that
way and has both AMs call the same function. In a randomized check of
80 points against 50,000 boxes, master's operator differed from the
exact distance for 7.5% of sampled pairs, and both AMs returned rows
out of order. With 0001 both counts are zero. Four rows of the
geometry regression output change, all corrections. 0001 could go in
before the rest.

With the distances equal, 0002 lets GiST and SP-GiST box_ops return
them. In v9 I had withdrawn box_ops because of this mismatch.

0002 also documents "Order By Values Used": in the EXPLAIN chapter
next to the other per-node lines, and in the nearest-neighbor
paragraph of the index types chapter.

0007 reduces the planning cost of carrying a value through joins.
That cost came from the prechecks. add_path_precheck() can't see the
values, so v10 skipped it for every join path over an input that
emits one, and built each path in full. 0007 now adds
add_path_precheck_extras() and add_partial_path_precheck_extras(),
which take the values the path will emit. They let an existing path
dominate the new one only if it emits them all too. The old functions
keep their signatures. These are the N-way joins with the expensive
expression from the v7 mail [1]/messages/by-id/O7LiKSyMJH9pKrU0jxstopxs00AioGMev0lpPwq2uhUwzurMTQBFUKOdFPq0LXd4GHxxrIpajWq9Vy8QwkCsb3LgJrCdgfU7fn36dc4FFWQ=@burd.me, on a c6id.metal (Xeon 8375C, turbo
off, server and client pinned to separate cores), median of 41
planning times in each of five rounds, v10 and v11 interleaved:

rels overhead v10 overhead v11 planner memory v10 -> v11
7 +69% +32% 8.5 -> 6.5 MB
11 +90% +49% 26.3 -> 19.3 MB

"Overhead" is against the same join without the expression, which
plans in 5.8 ms at seven rels and 17.5 ms at eleven, within 1% of v10.
The five rounds agreed to within 1%. The plans and estimated costs of
all 18 join queries in that set were byte for byte the same in v10 and
v11.

The planner already decides early whether to carry a value at all. It
carries one only if the value costs more than 10 times
cpu_operator_cost to compute, so queries without such an expression
plan as before. The remaining overhead appears only when the value is
worth carrying. It comes from the extra paths add_path() keeps, and
those are what make the join over an index-only scan possible.

Oleg, about COST not following document size: I don't think the series
needs to solve this. The planner gets every function's cost from
add_function_cost(), and when the function has a support function,
that is where SupportRequestCost comes in. The request carries the
FuncExpr itself, so a ranking function's support function can look at
its tsvector argument, find the column's average width in its
statistics, and scale the per-call cost by it. The series computes
its credit (0003, 0005, 0007) with cost_qual_eval_node(), which goes
through add_function_cost(), so it uses that estimate as-is. To
check, I indexed a COST 100000 function and the planner chose the
index-only scan. Then I attached regress.c's test_support_func, which
answers 2 * cpu_operator_cost, and the planner went back to a seq
scan, with no change to the series.

The estimate is still an average per row, as all costs are. A
document much longer than average costs more than the planner thinks,
but the credit and the charge use the same estimate, so the comparison
between plans stays fair. On the index side, your AM's
amcostestimate can scale its own scoring cost by the same width.

0007 also stops collecting index expressions the children's index-only
scans can't return, which used to stop the Append from passing up the
ones they can, and 0008 adds a NULL check. Everything else is as in
v10. The series applies to master as of 0019a1ecf4c.

best.

-greg

[1]: /messages/by-id/O7LiKSyMJH9pKrU0jxstopxs00AioGMev0lpPwq2uhUwzurMTQBFUKOdFPq0LXd4GHxxrIpajWq9Vy8QwkCsb3LgJrCdgfU7fn36dc4FFWQ=@burd.me