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

On Wednesday, October 7th, 2026 at 8:09 AM, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> wrote:
>
> On Wed, 7 Oct 2026 at 13:44, Greg Burd <greg(at)burd(dot)me> wrote:
> >
> > On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent <boekewurm+postgres(at)gmail(dot)com> wrote:
> > >
> > > On Tue, 6 Oct 2026 at 18:29, Greg Burd <greg(at)burd(dot)me> wrote:
> > > >
> > > > On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <greg(at)burd(dot)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