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

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

> On Thu, 1 Oct 2026, 21:10 Greg Burd, <greg(at)burd(dot)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(at)mail(dot)gmail(dot)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] https://postgr.es/m/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 ?