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

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

> > 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] 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 ?