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

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 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(at)mail(dot)gmail(dot)com/

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