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

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.

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.

This proposal does not change what `body <=> q` means anywhere so
hopefully doesn't fall into that trap. What the patch changes is much
narrower.

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.

- For an AM whose exact value equals the operator's result (GiST on
  points, btree_gist, pg_trgm `<->`), the substitution is a pure
  optimization with no observable change. That is the pgvector
  case raised by Heikki.

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

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.

I think I've addressed Tom's 2023 concern, "the planner [must] not
spend too much effort on looking for subexpression matches" [7]
because only top-level target-list entries are compared, against a
list that is almost always of length 1. An ORDER BY expression buried
inside a larger target expression is not matched. To me that's not a
wrong answer but a missed optimization, possibly future work.  Feel
free to disagree (Tom). :)

I update EXPLAIN to avoid confusion, before an `EXPLAIN VERBOSE`
prints `Output: id, (body <=> '...'::wquery)` but with the patch it
prints the expression, by de-parsing the `INDEX_VAR` back through
`indexorderbyorig`, the same way IndexOnlyScan's `INDEX_VAR`s are
de-parsed through `indextlist`. It adds one line, `Order By Values
Used: 1`, so a user can tell the two behaviors apart and I've added a
regression test watching for that to validate it is happening in
practice.

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.

best.

-greg

[1] https://codeberg.org/gregburd/pg_weave (not finished yet)
    https://codeberg.org/gregburd/pg_fts (works great!)
    https://codeberg.org/gregburd/pg_turbovec (works great!)
    https://codeberg.org/gregburd/pg_tre (approximate REGEX index?! noice, also works great!)
[2] https://pg.ddx.io/search and https://pg.ddx.io/mcp
[3] https://www.postgresql.org/message-id/CAEze2WgJOTFoCV1U2MfVSo0w9CLG=oYzMNUXeExRTipVkJYy+g@mail.gmail.com/
[4] https://www.postgresql.org/message-id/2ca5865b-4693-40e5-8f78-f3b45d5378fb%40iki.fi
[5] https://pg.ddx.io/m/pgsql-hackers/CABSN6VfLK5msEDSR8wPeMh_h3xNyr2Xs5NJK8+uOZp0bVxw7Hg@mail.gmail.com/
[6] https://www.postgresql.org/message-id/2246002.1714670501%40sss.pgh.pa.us
[7] https://www.postgresql.org/message-id/1052850.1703258655@sss.pgh.pa.us