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

On Tuesday, October 6th, 2026 at 12:29 PM, Greg Burd <greg@burd.me> wrote:
>
> 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.  For instances, a vec_10k the plan costs ~50× what it
> actually does with this fix in place.  I'll poke around and see if I come up
> with something that avoids tipping the decision in the wrong direction (away
> from an index scan) and add a patch in if I do.

I did, it's 0002.  0001 is v3 unchanged, rebased.

The problem: an ORDER BY expression is always in the scan/join target,
as a sort column if nothing else, and create_projection_path() charges
every path rows * cost(expr) for it.  With 0001 the ordering Index Scan
never pays that, but Seq Scan + Sort and Bitmap Heap Scan + Sort still
do.  So with a costly ORDER BY expression the kNN scan was overcharged
by up to ~32x and lost to Sort plans that ran 1.2-13x slower.

0002 adds a static path_target_cost() in pathnode.c that leaves out the
target entries a plain IndexScan takes from its ORDER BY values;
create_projection_path() and apply_projection_to_path() use it.  The
"does the scan return this one" test, index_orderby_returnable(), is
shared with create_indexscan_plan(), so what is costed is what setrefs.c
builds.  An expression that only contains the ORDER BY expression, e.g.
(expr) * 2, isn't rewritten and is still charged.

Same data dir, v3 vs v3+0002, -O2 without cassert, 200k rows, ORDER BY
slow_pt(p) <-> point(500,500) where slow_pt() is plpgsql at ~13us/call
declared COST 1000, median of 5 runs.  "Sort" is Sort over a Bitmap Heap
Scan on a btree on grp:

                       ---- v3 ----------     -- v3+0002 -------
   WHERE               plan    est     ms     plan  est     ms
   ------------------  ----  ------  ------   ----  -----  -----
   grp < 50            Sort  257908  1109.1   kNN   16428   85.7
   grp < 20            Sort   99637   437.5   kNN   16428   83.1
   grp < 10            Sort   47211   212.5   kNN   16428   81.1
   grp < 10 LIMIT 2e4  Sort   47211   214.0   kNN   16428   83.5
   grp < 5             Sort   22042   101.2   kNN   16428   81.1
   grp < 2             Sort    6463    34.9   Sort   6463   35.4

grp < 2 rightly stays a Sort.  Unfiltered and LIMIT cases were already
kNN on v3 and don't change plan.  Costs are byte-identical to v3 for
circle_ops, Index Only Scan, bitmap scans and any query without a
returnable ORDER BY value in its target.  Planning a kNN query took
~61us with and without 0002; a join query was too noisy to call either
way.  The new gist test picks the kNN plan with 0002 and a Sort without
it.

Questions I'd expect, and why it's done this way:

* Why not fix it in cost_index() or amcostestimate?  The charge isn't
  made there.  An IndexPath's own target is rel->reltarget (Vars only);
  the ORDER BY expression is first charged when the scan/join target is
  applied, so that's where the IndexScan's exemption has to be.

* Why re-sort rel->pathlist and partial_pathlist?  Applying the target
  used to add the same cost to every path, so
  apply_scanjoin_target_to_paths() could assume order was kept.  Now an
  IndexPath can get cheaper relative to its siblings, and
  add_path_precheck() and the linitial(partial_pathlist) callers rely
  on that order.  sort_pathlist_by_cost() is a stable insertion sort, a
  single pass in the usual already-sorted case.  To be clear: I haven't
  produced a wrong plan from an unsorted list, this is defensive, and
  the partial_pathlist half can't trigger today since neither GiST nor
  SP-GiST is amcanparallel.  Happy to drop it if people would rather.

* Doesn't this duplicate setrefs.c's matching?  It repeats the equal()
  walk over the target, yes, but on the same predicate.  The two must
  agree or we cost one plan and build another, and sharing
  index_orderby_returnable() is the cheapest way I found to keep them
  together without moving the setrefs decision into path creation.

Things I'm less sure of:

* An ordered IndexScan below a join (nestloop inner, merge join input)
  isn't helped.  That's consistent, since setrefs only rewrites the
  scan's own targetlist and there the expression really is evaluated
  above it, but it means the win is limited to the top scan/join rel.

* Matching is equal() on top-level entries only, so it's
  representation-sensitive: an ORDER BY expression that's semantically
  the same but built differently (an inserted RelabelType, say) is
  neither rewritten nor discounted.  Consistent, but a missed case.

* Cheap operators get a small discount too (cpu_operator_cost * rows for
  point <-> point).  That's correct per 0001's numbers, it was being
  overcharged, but it does nudge qualifying point/box kNN plans slightly
  cheaper than before.

* The discount is exactly the declared COST, like every other
  expression cost.  A truly expensive ORDER BY function left at the
  default COST 100 still runs faster with 0001 but is planned as if it
  were cheap, so 0002 may not flip its plan.

v4 applies to current master.

best.

-greg