On Tuesday, October 6th, 2026 at 5:57 PM, Matthias van de Meent
<[email protected]> wrote:
> On Tue, 6 Oct 2026 at 18:29, Greg Burd <[email protected]> wrote:
> >
> > On Monday, October 5th, 2026 at 2:14 PM, Greg Burd <[email protected]> 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. For a cheap operator
> > (point <-> point, 100k rows) the patch is 3-6% faster. The slot fetch is
> > cheaper than re-evaluating hypot(). For an expensive one it removes the
> > re-evaluation entirely: a 128-dim float8[] distance over 10k rows goes from
> > 197 ms to 4 ms, a plpgsql expression index from 139 ms to 8 ms. box_ops is
> > a
> > wash (+0.1%). The circle_ops control, which doesn't qualify and gets no
> > rewrite, is unchanged (-0.9%, within the 1% stdev), so an opclass that
> > answers no pays nothing.
> >
> > 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.
Hey Matthias,
v5 attached. 0001 is v3 unchanged, 0002 is v4's costing patch plus commuted
matching, 0003 and 0004 are new.
> 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.
> Kind regards,
>
> Matthias van de Meent
> Databricks (https://www.databricks.com)
May 2024 in [1] Tom said:
"I'm uninterested in making the world safe for a design that's going
to fail if the planner doesn't choose an indexscan on a specific
index."
I agree with this, and I think I've stuck to it with the changes I've
proposed in the planner. amcanreturnorderby is a promise that for a
non-rechecked row the index's value is exactly the operator's result.
So a query's output doesn't depend on whether the index was chosen: a
Seq Scan + Sort shows the same number, it just pays more for it. An AM
whose score needs index-wide state can't make that promise and gets
nothing from this.
and then:
"Note that even if this indexscan is chosen, that doesn't ensure that
we won't need an explicit sort later [...] So it's far from trivial
to decide that the scan node doesn't need to emit the sort column."
We don't decide that. The scan still emits the sort column; it just
doesn't compute it again. A Sort, Limit WITH TIES or Merge Append
above it reads the same Datum it always did.
Later Tom and Heikki, in December 2023 [2][3][4]:
Heikki's patch was returned with feedback in CF 2024-03 and hasn't been
picked up since [5]. This series is not that patch: it doesn't touch
resjunk or the junk filter, which Tom said he wanted to keep [4]. But
Tom's review [3] asked for three things, and they map onto this series
like this:
1) "say we have an index on f(x) and the query requires sorting by f(x)
[...] we need to not charge the evaluation cost of f() for that plan"
That's 0002 for kNN. It also matches a commuted ORDER BY now: "const
<-> col" becomes "col <-> const" for the index, and v4 missed a target
entry written the first way.
2) "you're only munging the final top-level targetlist not anything for
lower plan levels [...] it leaves everything on the table as soon as
there's more than one level of plan involved"
That's 0003. Below a join, an ordering Index Scan's target was
rel->reltarget (Vars only), so the join computed the ORDER BY expression
itself and 0001 never fired. 0003 gives such an IndexPath its own
target, rel->reltarget plus the returnable ORDER BY expressions, but
only when the final targetlist needs them. fix_join_expr() already
matches whole non-Var input expressions, so the join's copy becomes a
reference with no setrefs change. The join isn't charged for it either.
3) Heikki [4] showed an index-only scan on (i, expensive(i)) costed at
25M though it reads expensive(i) from the index. That's 0004: with
his example the IoS estimate goes from 25000266 to 266.
Tom also suggested waiting for the index-scan/IOS unification [4], which
has since become the amgetbatch work. The commit ddce1da5b1b has
table_index_getnext_slot, but not amgetbatch. This series doesn't touch
the AM or table AM interface, only nodeIndexscan.c and the planner, so I
don't think it needs to wait. If amgetbatch reshapes nodeIndexscan.c
first, rebasing 0001 is mechanical.
On whether this should be core at all: pg_fts v1.9.0 (a bm25 index I've
developed) does the same thing from an extension [6]. A planner hook
swaps resjunk entries for a C function that returns a "current distance"
the AM stashed in a backend global. It works for one AM, but the global
is clobbered if another ordering scan on the same index runs between
gettuple and projection, such as a correlated subquery in the tlist.
The slot-based version in 0001 has no such hazard, which is the main
reason I'd rather fix it here.
0003 numbers
Same data dir, v4 vs v5, -O2 without cassert, 200k-row fact table with
a GiST index on slow_pt(p) (plpgsql, ~13us/call, COST 1000), joined to
a 1001-row dimension, median of 3 runs:
SELECT f.id, d.region, slow_pt(f.p) <-> point(500,500)
FROM f JOIN d ON d.cat = f.cat WHERE <filter>
ORDER BY slow_pt(f.p) <-> point(500,500);
---- v4 ------------ ---- v5 -----------
filter plan est ms plan est ms
-------------- ---- ------ ------ ---- ----- -----
region < 9 kNN 471724 2304.1 kNN 21224 152.5
region < 6 Sort 316379 1464.4 kNN 21224 145.3
region < 4 Sort 212272 984.3 kNN 21224 144.9
region < 2 Sort 108315 496.5 kNN 21224 138.3
region = 0 Sort 56436 256.4 kNN 21224 140.5
"kNN" is Nested Loop over the ordered GiST scan with a Memoize on the
dimension; "Sort" is Sort over a hash join. With LIMIT 1000 the plan
was already kNN on v4 and stays kNN; 0003 removes the per-row
evaluation, 15-22 ms -> 2.3-8.4 ms. For the opposite case I also ran
very selective filters (d.cat < 10, < 3, = 0), where the Sort plan
really is cheaper. v5 keeps it, 7-32 ms against 100-138 ms for the
forced kNN plan.
Things I'm less sure of:
* Only immediate join inputs are considered (looking through Material
and Memoize). That covers what I could build, since the value can't
reach a higher join without going through this join's own tlist.
Someone may find a shape I missed.
* 0003 is limited to plain base rels. Appendrel children are left out
because Append and MergeAppend build their own child tlists. The
MergeAppend-over-kNN case already worked through the scan/join target,
so I didn't widen the change for it.
* 0004 only fixes the estimate. It changes the plan when the IOS path
is already in contention, kept for its pathkeys or a qual. It doesn't
make an IOS win on the expression alone. Heikki's exact query (no
WHERE, ORDER BY expensive(i), index on (i, expensive(i))) still picks
Seq Scan + Sort, because the base rel's paths are compared before the
expression is charged to any of them. Fixing that means giving IOS
paths their own targets the way 0003 does for kNN. I tried to do
that, and add_path() still kept the seq scan with nothing to tell them
apart. This needs discussion, likely a new thread to get it right.
* Matching is still equal() on top-level entries, plus the commuted
form. A different spelling of the same value isn't matched; the
result is correct, just not optimized. This seems worthy of a bit
more attention in the next series.
* The discount is only as good as the declared COST. With the default
COST 100, an expensive function still runs faster under 0001 but is
planned as if cheap, so 0002/0003 may not flip the plan. That's how
procost works everywhere; prosupport with SupportRequestCost is the
fix for an extension that knows better, right?
Thanks for reading.
best.
-greg
[1] https://postgr.es/m/[email protected]
[2] https://postgr.es/m/[email protected]
[3] https://postgr.es/m/[email protected]
[4] https://postgr.es/m/[email protected]
and Tom's reply https://postgr.es/m/[email protected]
[5] https://commitfest.postgresql.org/patch/4717/
[6] https://github.com/gburd/pg_fts, fts_reuse_distance() in
pg_fts_customscan.c (commit efca0cf)From 82a84654f12b5601e7757ab2317e19601b224824 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Wed, 7 Oct 2026 01:50:14 +0000
Subject: [PATCH v5 4/4] Don't charge an index-only scan for index expressions
it returns
An index-only scan on an index with an expression column reads that
expression's value from the index: set_indexonlyscan_references()
replaces a target list entry equal() to a returnable index expression
with a reference to that column. But the planner still charges the
scan the full cost of evaluating the expression for every row, as if it
computed it. Heikki Linnakangas showed this in the 2023 junk-column
thread with an index on (i, expensive(i)) and a function of COST
1000000: the index-only scan was estimated at 25 million, like the
Seq Scan that really does evaluate expensive(i).
path_target_cost() now also handles index-only scan paths: a top-level
target expression equal() to a returnable index expression costs
nothing. cost_index() already goes through path_target_cost(), so the
index-only scan's estimate drops to what it actually does.
This corrects the estimate of an index-only scan path that is already
in the running, e.g. one kept for its pathkeys. It does not make such a
path win the base relation's add_path() comparison when its only merit
is the cheaper expression: at that point every path of the rel carries
rel->reltarget, which holds only Vars, and the expression is charged to
all of them alike afterwards. Doing that would mean giving index-only
paths their own targets, as the previous commit does for ordering
Index Scans; that's left for later.
Author: Greg Burd <[email protected]>
Discussion: https://postgr.es/m/8s5lT8erXzBMugXJQ6Wginbp_gc2B4hmCYhF0Q0GpnuK87eCAOcKs5K31AWCwraCNFIQt42wwkow_MPPubHg485MWv-zDBY4NL_JX9yJEEg=@burd.me
Discussion: https://postgr.es/m/[email protected]
---
src/backend/optimizer/util/pathnode.c | 59 ++++++++++++++++++++++++++-
src/test/regress/expected/gist.out | 33 +++++++++++++++
src/test/regress/sql/gist.sql | 23 +++++++++++
3 files changed, 113 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 377491cf4f2..44d82fad603 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -2791,6 +2791,57 @@ orderby_tlist_match(Expr *expr, Expr *orderby)
equal(lsecond(a->args), linitial(b->args));
}
+/*
+ * indexonly_target_cost
+ * path_target_cost() for an index-only scan path.
+ *
+ * setrefs.c's set_indexonlyscan_references() matches target expressions
+ * against the index's returnable columns, expression columns included, and
+ * replaces a match with a reference to that column: the scan reads the
+ * value the index stored instead of computing it. So a top-level target
+ * expression equal() to a returnable index expression costs nothing. Only
+ * top-level entries are considered, as elsewhere; that's what's normally in
+ * a scan's target.
+ */
+static QualCost
+indexonly_target_cost(PlannerInfo *root, IndexPath *ipath, PathTarget *target)
+{
+ QualCost cost = target->cost;
+ IndexOptInfo *index = ipath->indexinfo;
+ ListCell *lc;
+
+ if (index->indexprs == NIL)
+ return cost; /* only Vars, which cost nothing anyway */
+
+ foreach(lc, target->exprs)
+ {
+ Node *expr = (Node *) lfirst(lc);
+ ListCell *lt;
+ int i = 0;
+
+ if (IsA(expr, Var))
+ continue;
+
+ foreach(lt, index->indextlist)
+ {
+ TargetEntry *tle = lfirst_node(TargetEntry, lt);
+
+ if (index->canreturn[i++] && !IsA(tle->expr, Var) &&
+ equal(expr, tle->expr))
+ {
+ QualCost ecost;
+
+ cost_qual_eval_node(&ecost, expr, root);
+ cost.startup -= ecost.startup;
+ cost.per_tuple -= ecost.per_tuple;
+ break;
+ }
+ }
+ }
+
+ return cost;
+}
+
/*
* join_target_cost
* path_target_cost() for a join path.
@@ -2851,8 +2902,9 @@ join_target_cost(PlannerInfo *root, JoinPath *jpath, PathTarget *target)
* Return the cost 'path' pays to evaluate 'target'.
*
* Normally that's just target->cost. A join path doesn't pay for entries
- * an input already emits (see join_target_cost()). And a plain IndexScan
- * takes any
+ * an input already emits (see join_target_cost()), nor an index-only scan
+ * for entries it reads from the index (see indexonly_target_cost()). And a
+ * plain IndexScan takes any
* top-level target expression that is a returnable ORDER BY expression
* (see orderby_tlist_match()) from its ORDER BY values instead of
* evaluating it (setrefs.c rewrites it into a reference to them), so it
@@ -2869,6 +2921,9 @@ path_target_cost(PlannerInfo *root, Path *path, PathTarget *target)
if (IsA(path, NestPath) || IsA(path, MergePath) || IsA(path, HashPath))
return join_target_cost(root, (JoinPath *) path, target);
+ if (IsA(path, IndexPath) && path->pathtype == T_IndexOnlyScan)
+ return indexonly_target_cost(root, (IndexPath *) path, target);
+
if (!IsA(path, IndexPath) || path->pathtype != T_IndexScan)
return cost;
ipath = (IndexPath *) path;
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.out
index 4fc2b084df1..457d1c41ae4 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -722,6 +722,39 @@ drop table gist_join_fact;
drop table gist_join_dim;
drop function gist_join_pt(point);
drop sequence gist_join_cnt;
+-- An index-only scan isn't charged for evaluating a target expression it
+-- reads from a returnable index expression column: it reads the stored
+-- value instead. (Not GiST-specific; btree returns expression columns.)
+create function gist_ios_costly(int) returns int
+ language plpgsql immutable strict cost 100000
+ as $$ begin return $1; end $$;
+create temp table gist_ios_cost (i int);
+insert into gist_ios_cost select g from generate_series(1, 10000) g;
+create index on gist_ios_cost (i, gist_ios_costly(i));
+vacuum analyze gist_ios_cost;
+create function gist_ios_total(q text) returns float8 language plpgsql as
+$$ declare j json; begin
+ execute 'explain (format json) ' || q into j;
+ return (j->0->'Plan'->>'Total Cost')::float8;
+ end $$;
+explain (verbose, costs off)
+select gist_ios_costly(i) from gist_ios_cost order by i;
+ QUERY PLAN
+--------------------------------------------------------------------------------------
+ Index Only Scan using gist_ios_cost_i_gist_ios_costly_i_idx on pg_temp.gist_ios_cost
+ Output: (gist_ios_costly(i)), i
+(2 rows)
+
+select gist_ios_total('select gist_ios_costly(i) from gist_ios_cost order by i')
+ < 10000 as ios_expr_is_free;
+ ios_expr_is_free
+------------------
+ t
+(1 row)
+
+drop function gist_ios_total(text);
+drop table gist_ios_cost;
+drop function gist_ios_costly(int);
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql
index 9e7bc0fd176..e84ef688212 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -354,6 +354,29 @@ drop table gist_join_dim;
drop function gist_join_pt(point);
drop sequence gist_join_cnt;
+-- An index-only scan isn't charged for evaluating a target expression it
+-- reads from a returnable index expression column: it reads the stored
+-- value instead. (Not GiST-specific; btree returns expression columns.)
+create function gist_ios_costly(int) returns int
+ language plpgsql immutable strict cost 100000
+ as $$ begin return $1; end $$;
+create temp table gist_ios_cost (i int);
+insert into gist_ios_cost select g from generate_series(1, 10000) g;
+create index on gist_ios_cost (i, gist_ios_costly(i));
+vacuum analyze gist_ios_cost;
+create function gist_ios_total(q text) returns float8 language plpgsql as
+$$ declare j json; begin
+ execute 'explain (format json) ' || q into j;
+ return (j->0->'Plan'->>'Total Cost')::float8;
+ end $$;
+explain (verbose, costs off)
+select gist_ios_costly(i) from gist_ios_cost order by i;
+select gist_ios_total('select gist_ios_costly(i) from gist_ios_cost order by i')
+ < 10000 as ios_expr_is_free;
+drop function gist_ios_total(text);
+drop table gist_ios_cost;
+drop function gist_ios_costly(int);
+
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
--
2.50.1
From 7d530cc229b305758f06dcdc033060fc2f708575 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Thu, 1 Oct 2026 10:19:05 -0400
Subject: [PATCH v5 1/4] Let an ordering index scan hand its ORDER BY values to
the target list
An Index Scan that orders by an operator (ORDER BY col <-> const)
computes each returned row's ORDER BY value inside the index AM and
reports it in xs_orderbyvals. If the same expression also appears in
the target list, the executor then evaluates it a second time in the
scan's projection (a third time if the AM asked for a recheck). For an
expensive distance operator that is wasted work.
The AM contract only requires a non-rechecked distance to sort the same
way as the operator's result, not to equal it, so the executor cannot
substitute it blindly. Add an optional IndexAmRoutine callback,
amcanreturnorderby(Relation, attno), shaped like amcanreturn: it asks
the AM whether the given column's opclass reports, for a non-rechecked
leaf entry, exactly the value the ordering operator would return.
plancat.c collects the answer per column alongside canreturn[], and
create_indexscan_plan() carries one bool per ORDER BY key into the
IndexScan via indexorderbycols.
For each qualifying key, setrefs.c replaces a top-level target list
expression that is equal() to that indexorderbyorig expression with
Var(INNER_VAR, i), and nodeIndexscan.c stores the returned row's ORDER
BY values in a virtual slot it installs as the projection's inner tuple
(a scan node has no inner plan, so INNER_VAR is otherwise unused
there). The values stored are the AM's for a row it reported exact,
the recomputed ones for a row it asked to recheck, a reorder queue
entry's copy for a queued row, and freshly recomputed ones for an
EvalPlanQual test tuple. Only float4/float8 ORDER BY expressions
qualify, as those are the only types
index_store_float8_orderby_distances() can deliver.
GiST answers yes for the core point and box opclasses, whose leaf
distance is computed by the operator's own code; SP-GiST likewise for
quad_point_ops, kd_point_ops and box_ops. The polygon and circle
opclasses report lower bounds and are not affected, nor is any other
AM or any out-of-core opclass, which all default to no.
EXPLAIN VERBOSE deparses the INNER_VAR back to the ORDER BY expression
and reports "Order By Values Used: N". Above such a scan, an upper
node's reference to the value now prints with one more pair of
parentheses, the same way any reference to a computed scan column does
(box expected output).
Author: Greg Burd <[email protected]>
Discussion: https://postgr.es/m/8s5lT8erXzBMugXJQ6Wginbp_gc2B4hmCYhF0Q0GpnuK87eCAOcKs5K31AWCwraCNFIQt42wwkow_MPPubHg485MWv-zDBY4NL_JX9yJEEg=@burd.me
---
doc/src/sgml/indexam.sgml | 31 +++++
src/backend/access/gist/gist.c | 1 +
src/backend/access/gist/gistget.c | 25 ++++
src/backend/access/index/indexam.c | 22 ++++
src/backend/access/spgist/spgscan.c | 24 ++++
src/backend/access/spgist/spgutils.c | 1 +
src/backend/commands/explain.c | 4 +
src/backend/executor/nodeIndexscan.c | 91 +++++++++++++-
src/backend/optimizer/plan/createplan.c | 14 +++
src/backend/optimizer/plan/setrefs.c | 60 +++++++++
src/backend/optimizer/util/plancat.c | 3 +
src/backend/utils/adt/ruleutils.c | 31 +++++
src/include/access/amapi.h | 8 ++
src/include/access/genam.h | 1 +
src/include/access/gist_private.h | 1 +
src/include/access/spgist.h | 1 +
src/include/nodes/execnodes.h | 7 ++
src/include/nodes/pathnodes.h | 5 +-
src/include/nodes/plannodes.h | 11 ++
src/test/regress/expected/box.out | 12 +-
src/test/regress/expected/gist.out | 160 ++++++++++++++++++++++++
src/test/regress/sql/gist.sql | 80 ++++++++++++
src/tools/pgindent/typedefs.list | 1 +
23 files changed, 585 insertions(+), 9 deletions(-)
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml
index f48da318530..0f1ccd9ffa3 100644
--- a/doc/src/sgml/indexam.sgml
+++ b/doc/src/sgml/indexam.sgml
@@ -157,6 +157,7 @@ typedef struct IndexAmRoutine
ambulkdelete_function ambulkdelete;
amvacuumcleanup_function amvacuumcleanup;
amcanreturn_function amcanreturn; /* can be NULL */
+ amcanreturnorderby_function amcanreturnorderby; /* can be NULL */
amcostestimate_function amcostestimate;
amgettreeheight_function amgettreeheight; /* can be NULL */
amoptions_function amoptions;
@@ -481,6 +482,25 @@ amcanreturn (Relation indexRelation, int attno);
<para>
<programlisting>
+bool
+amcanreturnorderby (Relation indexRelation, int attno);
+</programlisting>
+ Check whether, for an ordering scan on the given column, the values the
+ access method reports in <literal>scan->xs_orderbyvals</literal> with
+ <literal>xs_recheckorderby</literal> false are exactly the values the
+ ordering operator would return for the heap tuple. If so, the executor
+ may return them for a target list entry that is the same expression as
+ the <literal>ORDER BY</literal> key, instead of evaluating the operator
+ again. The function must answer for the operator class bound to the
+ column, not for the access method as a whole: an operator class whose
+ distances merely sort like the operator's result, or depend on anything
+ other than the indexed value, must answer false. If the
+ <structfield>amcanreturnorderby</structfield> field is set to NULL, no
+ substitution is made.
+ </para>
+
+ <para>
+<programlisting>
void
amcostestimate (PlannerInfo *root,
IndexPath *path,
@@ -495,6 +515,7 @@ amcostestimate (PlannerInfo *root,
in <xref linkend="index-cost-estimation"/>, below.
</para>
+
<para>
<programlisting>
int
@@ -989,6 +1010,16 @@ amtranslatecmptype (CompareType cmptype, Oid opfamily, Oid opcintype);
of that form can be passed to <function>amrescan</function> as described
previously.
</para>
+ <para>
+ Such an access method returns each entry's ordering values in
+ <literal>scan->xs_orderbyvals</literal>, and sets
+ <literal>scan->xs_recheckorderby</literal> to true when those values are
+ only lower bounds that the executor must recompute from the heap
+ tuple. When <literal>xs_recheckorderby</literal> is false the values
+ need only sort in the same order as the ordering operator's results;
+ they need not equal them. See <function>amcanreturnorderby</function>
+ below for how an access method can promise that they do.
+ </para>
</listitem>
</itemizedlist>
</para>
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 8565e225be7..f6c4592a1f5 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -93,6 +93,7 @@ gisthandler(PG_FUNCTION_ARGS)
.ambulkdelete = gistbulkdelete,
.amvacuumcleanup = gistvacuumcleanup,
.amcanreturn = gistcanreturn,
+ .amcanreturnorderby = gistcanreturnorderby,
.amcostestimate = gistcostestimate,
.amgettreeheight = NULL,
.amoptions = gistoptions,
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 111c310f9df..f71578a3aed 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -23,6 +23,7 @@
#include "pgstat.h"
#include "storage/predicate.h"
#include "utils/float.h"
+#include "utils/fmgroids.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -813,3 +814,27 @@ gistcanreturn(Relation index, int attno)
else
return false;
}
+
+/*
+ * Are the distances the given column's opclass reports for a leaf entry,
+ * when it does not set *recheck, the ordering operator's own result?
+ *
+ * The GiST contract only requires a non-rechecked distance to *sort* like
+ * the operator's result, so we cannot assume this of an arbitrary opclass.
+ * The core point and box opclasses compute the leaf distance with the same
+ * code as the operator, so the executor may return their values in place of
+ * re-evaluating the operator. Other opclasses say no, as before.
+ */
+bool
+gistcanreturnorderby(Relation index, int attno)
+{
+ Oid distproc;
+
+ if (attno > IndexRelationGetNumberOfKeyAttributes(index))
+ return false;
+
+ distproc = index_getprocid(index, attno, GIST_DISTANCE_PROC);
+
+ return (distproc == F_GIST_POINT_DISTANCE ||
+ distproc == F_GIST_BOX_DISTANCE);
+}
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index db811056991..0ff85161d3d 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -716,6 +716,28 @@ index_can_return(Relation indexRelation, int attno)
return indexRelation->rd_indam->amcanreturn(indexRelation, attno);
}
+/* ----------------
+ * index_can_return_orderby
+ *
+ * For an ordering scan on the given column, are the distances the AM
+ * reports with xs_recheckorderby = false the ordering operator's own
+ * result, so that the executor may return them in place of
+ * re-evaluating the operator? (xs_recheckorderby = false alone only
+ * promises that they sort the same way.)
+ * ----------------
+ */
+bool
+index_can_return_orderby(Relation indexRelation, int attno)
+{
+ RELATION_CHECKS;
+
+ /* amcanreturnorderby is optional; assume false if not provided by AM */
+ if (indexRelation->rd_indam->amcanreturnorderby == NULL)
+ return false;
+
+ return indexRelation->rd_indam->amcanreturnorderby(indexRelation, attno);
+}
+
/* ----------------
* index_getprocid
*
diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c
index 2cc5f06f5d7..3896985c5fa 100644
--- a/src/backend/access/spgist/spgscan.c
+++ b/src/backend/access/spgist/spgscan.c
@@ -24,6 +24,7 @@
#include "storage/bufmgr.h"
#include "utils/datum.h"
#include "utils/float.h"
+#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -1088,3 +1089,26 @@ spgcanreturn(Relation index, int attno)
return cache->config.canReturnData;
}
+
+/*
+ * Are the distances the opclass reports for a leaf tuple, when it does not
+ * set recheckDistances, the ordering operator's own result?
+ *
+ * As for GiST, the contract only requires them to sort like the operator's
+ * result. The core point and box opclasses compute leaf distances with the
+ * operator's own code; polygon sets recheckDistances and never qualifies.
+ */
+bool
+spgcanreturnorderby(Relation index, int attno)
+{
+ Oid leafproc;
+
+ if (attno != 1)
+ return false;
+
+ leafproc = index_getprocid(index, attno, SPGIST_LEAF_CONSISTENT_PROC);
+
+ return (leafproc == F_SPG_QUAD_LEAF_CONSISTENT ||
+ (leafproc == F_SPG_BOX_QUAD_LEAF_CONSISTENT &&
+ index->rd_opcintype[0] == BOXOID));
+}
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c
index f2ee333f60d..d07e197a594 100644
--- a/src/backend/access/spgist/spgutils.c
+++ b/src/backend/access/spgist/spgutils.c
@@ -78,6 +78,7 @@ spghandler(PG_FUNCTION_ARGS)
.ambulkdelete = spgbulkdelete,
.amvacuumcleanup = spgvacuumcleanup,
.amcanreturn = spgcanreturn,
+ .amcanreturnorderby = spgcanreturnorderby,
.amcostestimate = spgcostestimate,
.amgettreeheight = NULL,
.amoptions = spgoptions,
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 96f2f0e2e74..924f70af2e4 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -1974,6 +1974,10 @@ ExplainNode(PlanState *planstate, List *ancestors,
planstate, es);
show_scan_qual(((IndexScan *) plan)->indexorderbyorig,
"Order By", planstate, ancestors, es);
+ if (es->verbose && ((IndexScan *) plan)->indexorderbytlist > 0)
+ ExplainPropertyInteger("Order By Values Used", NULL,
+ ((IndexScan *) plan)->indexorderbytlist,
+ es);
show_scan_qual(plan->qual, "Filter", planstate, ancestors, es);
if (plan->qual)
show_instrumentation_count("Rows Removed by Filter", 1,
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c
index 129d005f187..f1dbf7c1b25 100644
--- a/src/backend/executor/nodeIndexscan.c
+++ b/src/backend/executor/nodeIndexscan.c
@@ -163,6 +163,33 @@ IndexNext(IndexScanState *node)
return ExecClearTuple(slot);
}
+/*
+ * Hand the ORDER BY values of the row about to be returned to the projection,
+ * when the targetlist asks for them (indexorderbytlist > 0, set by setrefs.c
+ * only for keys whose opclass passes amcanreturnorderby). vals and nulls
+ * are what the caller established as this row's ordering values: the AM's
+ * when it reported them exact, the recomputed ones when it asked for a
+ * recheck, or a reorder queue entry's copy. Never a lossy AM's lower bound.
+ */
+static inline void
+IndexStoreOrderByValues(IndexScanState *node, const Datum *vals,
+ const bool *nulls)
+{
+ TupleTableSlot *oslot = node->iss_OrderBySlot;
+ int i;
+
+ if (oslot == NULL)
+ return;
+ ExecClearTuple(oslot);
+ for (i = 0; i < node->iss_NumOrderByKeys; i++)
+ {
+ oslot->tts_values[i] = vals[i];
+ oslot->tts_isnull[i] = nulls[i];
+ }
+ ExecStoreVirtualTuple(oslot);
+ node->ss.ps.ps_ExprContext->ecxt_innertuple = oslot;
+}
+
/* ----------------------------------------------------------------
* IndexNextWithReorder
*
@@ -251,6 +278,9 @@ IndexNextWithReorder(IndexScanState *node)
{
HeapTuple tuple;
+ /* before the pop frees the entry's copies */
+ IndexStoreOrderByValues(node, topmost->orderbyvals,
+ topmost->orderbynulls);
tuple = reorderqueue_pop(node);
/* Pass 'true', as the tuple in the queue is a palloc'd copy */
@@ -352,6 +382,7 @@ next_indextuple:
else
{
/* Can return this tuple immediately. */
+ IndexStoreOrderByValues(node, lastfetched_vals, lastfetched_nulls);
return slot;
}
}
@@ -404,7 +435,22 @@ IndexRecheck(IndexScanState *node, TupleTableSlot *slot)
/* Does the tuple meet the indexqual condition? */
econtext->ecxt_scantuple = slot;
- return ExecQualAndReset(node->indexqualorig, econtext);
+ if (!ExecQualAndReset(node->indexqualorig, econtext))
+ return false;
+
+ /*
+ * The EPQ test tuple never went through IndexNext, so the ORDER BY values
+ * the targetlist reads (if any) are not those of this row. Recompute
+ * them from the tuple, as we would for a rechecked row.
+ */
+ if (node->iss_OrderBySlot != NULL)
+ {
+ EvalOrderByExpressions(node, econtext);
+ IndexStoreOrderByValues(node, node->iss_OrderByValues,
+ node->iss_OrderByNulls);
+ }
+
+ return true;
}
@@ -954,7 +1000,24 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
* Initialize result type and projection.
*/
ExecInitResultTypeTL(&indexstate->ss.ps);
- ExecAssignScanProjectionInfo(&indexstate->ss);
+
+ /*
+ * A targetlist that reads the ORDER BY values (INNER_VAR Vars, see
+ * setrefs.c) is never the scan tuple's physical layout, so it always
+ * projects; ExecConditionalAssignProjectionInfo would assert on the
+ * INNER_VAR while testing whether it can skip projection.
+ */
+ if (node->indexorderbytlist > 0)
+ {
+ ExecInitResultSlot(&indexstate->ss.ps, &TTSOpsVirtual);
+ indexstate->ss.ps.resultops = &TTSOpsVirtual;
+ indexstate->ss.ps.resultopsfixed = true;
+ indexstate->ss.ps.resultopsset = true;
+ ExecAssignProjectionInfo(&indexstate->ss.ps,
+ indexstate->ss.ss_ScanTupleSlot->tts_tupleDescriptor);
+ }
+ else
+ ExecAssignScanProjectionInfo(&indexstate->ss);
/*
* initialize child expressions
@@ -1024,6 +1087,30 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
NULL, /* no ArrayKeys */
NULL);
+ /*
+ * A targetlist that reads the ORDER BY values needs a slot to read them
+ * from, typed as the ORDER BY expressions (setrefs.c built it so).
+ */
+ if (node->indexorderbytlist > 0)
+ {
+ TupleDesc odesc;
+ ListCell *lc;
+ AttrNumber attno = 0;
+
+ odesc = CreateTemplateTupleDesc(list_length(node->indexorderbyorig));
+ foreach(lc, node->indexorderbyorig)
+ {
+ Node *expr = (Node *) lfirst(lc);
+
+ attno++;
+ TupleDescInitEntry(odesc, attno, NULL, exprType(expr),
+ exprTypmod(expr), 0);
+ }
+ TupleDescFinalize(odesc);
+ indexstate->iss_OrderBySlot =
+ ExecAllocTableSlot(&estate->es_tupleTable, odesc, &TTSOpsVirtual, 0);
+ }
+
/* Initialize sort support, if we need to re-check ORDER BY exprs */
if (indexstate->iss_NumOrderByKeys > 0)
{
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 2f8a08ad78e..c0f22b278c3 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -3033,6 +3033,20 @@ create_indexscan_plan(PlannerInfo *root,
indexorderbyops,
best_path->indexscandir);
+ if (!indexonly && indexorderbys != NIL)
+ {
+ List *exact = NIL;
+ ListCell *lc;
+
+ foreach(lc, best_path->indexorderbycols)
+ {
+ int indexcol = lfirst_int(lc);
+
+ exact = lappend_int(exact, indexinfo->canreturnorderby[indexcol]);
+ }
+ ((IndexScan *) scan_plan)->indexorderbyexact = exact;
+ }
+
copy_generic_path_info(&scan_plan->plan, &best_path->path);
return scan_plan;
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 327c0febe89..3cf0f18dfbb 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -134,6 +134,7 @@ static bool flatten_rtes_walker(Node *node, flatten_rtes_walker_context *cxt);
static void add_rte_to_flat_rtable(PlannerGlobal *glob, List *rteperminfos,
RangeTblEntry *rte);
static Plan *set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset);
+static void replace_orderby_tlist_refs(IndexScan *splan);
static Plan *set_indexonlyscan_references(PlannerInfo *root,
IndexOnlyScan *plan,
int rtoffset);
@@ -702,6 +703,8 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
splan->indexorderbyorig =
fix_scan_list(root, splan->indexorderbyorig,
rtoffset, NUM_EXEC_QUAL(plan));
+ /* after both are fixed, so equal() compares like with like */
+ replace_orderby_tlist_refs(splan);
}
break;
case T_IndexOnlyScan:
@@ -1365,6 +1368,63 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
return plan;
}
+/*
+ * replace_orderby_tlist_refs
+ * Let an ordering IndexScan hand its ORDER BY values to its targetlist.
+ *
+ * For each ORDER BY key whose index column's opclass promises that the
+ * distances it reports for an exact (non-rechecked) row are the ordering
+ * operator's own result (indexorderbyexact[i], from amcanreturnorderby),
+ * replace each top-level targetlist expression that is equal() to the i'th
+ * indexorderbyorig expression with Var(INNER_VAR, i + 1). nodeIndexscan.c
+ * then fills a virtual slot with the ORDER BY values of every returned row --
+ * the AM's for an exact row, the recomputed ones for a rechecked row -- and
+ * installs it as the projection's inner tuple. A scan node has no inner
+ * plan, so INNER_VAR is otherwise unused here.
+ *
+ * Only float8/float4 expressions qualify: those are the only types
+ * index_store_float8_orderby_distances() can deliver.
+ */
+static void
+replace_orderby_tlist_refs(IndexScan *splan)
+{
+ ListCell *lc;
+ int nrepl = 0;
+
+ if (splan->indexorderbyexact == NIL)
+ return;
+ Assert(list_length(splan->indexorderbyexact) ==
+ list_length(splan->indexorderbyorig));
+
+ foreach(lc, splan->scan.plan.targetlist)
+ {
+ TargetEntry *tle = lfirst_node(TargetEntry, lc);
+ ListCell *lo,
+ *le;
+ int i = 0;
+
+ forboth(lo, splan->indexorderbyorig, le, splan->indexorderbyexact)
+ {
+ Expr *orig = (Expr *) lfirst(lo);
+ Oid typ = exprType((Node *) orig);
+
+ i++;
+ if (lfirst_int(le) &&
+ (typ == FLOAT8OID || typ == FLOAT4OID) &&
+ equal(tle->expr, orig))
+ {
+ tle->expr = (Expr *) makeVar(INNER_VAR, i, typ,
+ exprTypmod((Node *) orig),
+ exprCollation((Node *) orig),
+ 0);
+ nrepl++;
+ break;
+ }
+ }
+ }
+ splan->indexorderbytlist = nrepl;
+}
+
/*
* set_indexonlyscan_references
* Do set_plan_references processing on an IndexOnlyScan
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index d067368cfc1..c6a2d0e9f6e 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -280,11 +280,14 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->opfamily = palloc_array(Oid, nkeycolumns);
info->opcintype = palloc_array(Oid, nkeycolumns);
info->canreturn = palloc_array(bool, ncolumns);
+ info->canreturnorderby = palloc_array(bool, ncolumns);
for (i = 0; i < ncolumns; i++)
{
info->indexkeys[i] = index->indkey.values[i];
info->canreturn[i] = index_can_return(indexRelation, i + 1);
+ info->canreturnorderby[i] =
+ index_can_return_orderby(indexRelation, i + 1);
}
for (i = 0; i < nkeycolumns; i++)
diff --git a/src/backend/utils/adt/ruleutils.c b/src/backend/utils/adt/ruleutils.c
index 5e8e1683db0..dca0d43e9ce 100644
--- a/src/backend/utils/adt/ruleutils.c
+++ b/src/backend/utils/adt/ruleutils.c
@@ -180,6 +180,8 @@ typedef struct
List *outer_tlist; /* referent for OUTER_VAR Vars */
List *inner_tlist; /* referent for INNER_VAR Vars */
List *index_tlist; /* referent for INDEX_VAR Vars */
+ List *orderby_tlist; /* IndexScan: referent for INNER_VAR Vars that
+ * stand for its ORDER BY values */
/* Special namespace representing a function signature: */
char *funcname;
int numargs;
@@ -5227,6 +5229,23 @@ set_deparse_plan(deparse_namespace *dpns, Plan *plan)
dpns->index_tlist = ((CustomScan *) plan)->custom_scan_tlist;
else
dpns->index_tlist = NIL;
+
+ /*
+ * An IndexScan whose targetlist reads its own ORDER BY values (see
+ * replace_orderby_tlist_refs in setrefs.c) uses INNER_VAR Vars numbered
+ * by ORDER BY key; they deparse as the ORDER BY expressions.
+ */
+ dpns->orderby_tlist = NIL;
+ if (IsA(plan, IndexScan) && ((IndexScan *) plan)->indexorderbytlist > 0)
+ {
+ ListCell *lc;
+ AttrNumber i = 0;
+
+ foreach(lc, ((IndexScan *) plan)->indexorderbyorig)
+ dpns->orderby_tlist = lappend(dpns->orderby_tlist,
+ makeTargetEntry((Expr *) lfirst(lc),
+ ++i, NULL, false));
+ }
}
/*
@@ -7988,6 +8007,18 @@ resolve_special_varno(Node *node, deparse_context *context,
context->appendparents = save_appendparents;
return;
}
+ else if (var->varno == INNER_VAR && dpns->orderby_tlist)
+ {
+ TargetEntry *tle;
+
+ tle = get_tle_by_resno(dpns->orderby_tlist, var->varattno);
+ if (!tle)
+ elog(ERROR, "bogus varattno for ORDER BY value var: %d", var->varattno);
+
+ resolve_special_varno((Node *) tle->expr, context,
+ callback, callback_arg);
+ return;
+ }
else if (var->varno == INNER_VAR && dpns->inner_tlist)
{
TargetEntry *tle;
diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h
index 79240333530..ba535175d61 100644
--- a/src/include/access/amapi.h
+++ b/src/include/access/amapi.h
@@ -144,6 +144,13 @@ typedef IndexBulkDeleteResult *(*amvacuumcleanup_function) (IndexVacuumInfo *inf
/* can indexscan return IndexTuples? */
typedef bool (*amcanreturn_function) (Relation indexRelation, int attno);
+/*
+ * Are the ORDER BY distances this column's opclass reports for an exact
+ * (xs_recheckorderby = false) leaf entry the ordering operator's own result?
+ */
+typedef bool (*amcanreturnorderby_function) (Relation indexRelation,
+ int attno);
+
/* estimate cost of an indexscan */
typedef void (*amcostestimate_function) (PlannerInfo *root,
IndexPath *path,
@@ -300,6 +307,7 @@ typedef struct IndexAmRoutine
ambulkdelete_function ambulkdelete;
amvacuumcleanup_function amvacuumcleanup;
amcanreturn_function amcanreturn; /* can be NULL */
+ amcanreturnorderby_function amcanreturnorderby; /* can be NULL */
amcostestimate_function amcostestimate;
amgettreeheight_function amgettreeheight; /* can be NULL */
amoptions_function amoptions;
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index 1bfdc1ef6b1..717e04d3f2b 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -194,6 +194,7 @@ extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info,
extern IndexBulkDeleteResult *index_vacuum_cleanup(IndexVacuumInfo *info,
IndexBulkDeleteResult *istat);
extern bool index_can_return(Relation indexRelation, int attno);
+extern bool index_can_return_orderby(Relation indexRelation, int attno);
extern RegProcedure index_getprocid(Relation irel, AttrNumber attnum,
uint16 procnum);
extern FmgrInfo *index_getprocinfo(Relation irel, AttrNumber attnum,
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h
index 39fdd27f5b9..e0fbdb043af 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -462,6 +462,7 @@ extern void gistkillitems(IndexScanDesc scan);
extern bool gistgettuple(IndexScanDesc scan, ScanDirection dir);
extern int64 gistgetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
extern bool gistcanreturn(Relation index, int attno);
+extern bool gistcanreturnorderby(Relation index, int attno);
/* gistvalidate.c */
extern bool gistvalidate(Oid opclassoid);
diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h
index 083d93f8ffd..cd5ddbc63d2 100644
--- a/src/include/access/spgist.h
+++ b/src/include/access/spgist.h
@@ -210,6 +210,7 @@ extern void spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
extern int64 spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm);
extern bool spggettuple(IndexScanDesc scan, ScanDirection dir);
extern bool spgcanreturn(Relation index, int attno);
+extern bool spgcanreturnorderby(Relation index, int attno);
/* spgvacuum.c */
extern IndexBulkDeleteResult *spgbulkdelete(IndexVacuumInfo *info,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 0998c9b2b9d..a202848608f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1751,6 +1751,13 @@ typedef struct IndexScanState
bool *iss_OrderByTypByVals;
int16 *iss_OrderByTypLens;
Size iss_PscanLen;
+
+ /*
+ * When the plan's targetlist reads the ORDER BY values (indexorderbytlist
+ * > 0), the values of the row being returned, as a virtual slot installed
+ * as the projection's inner tuple.
+ */
+ TupleTableSlot *iss_OrderBySlot;
} IndexScanState;
/* ----------------
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 1c6d1fe3d04..e7d447e0889 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1312,7 +1312,8 @@ typedef struct RelAggInfo
* IndexOptInfo
* Per-index information for planning/optimization
*
- * indexkeys[] and canreturn[] each have ncolumns entries.
+ * indexkeys[], canreturn[] and canreturnorderby[] each have ncolumns
+ * entries.
*
* indexcollations[], opfamily[], and opcintype[] each have nkeycolumns
* entries. These don't contain any information about INCLUDE columns.
@@ -1395,6 +1396,8 @@ typedef struct IndexOptInfo
bytea **opclassoptions pg_node_attr(read_write_ignore);
/* which index cols can be returned in an index-only scan? */
bool *canreturn pg_node_attr(array_size(ncolumns));
+ /* which index cols' exact ORDER BY distances are the operator's result? */
+ bool *canreturnorderby pg_node_attr(array_size(ncolumns));
/* OID of the access method (in pg_am) */
Oid relam;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 09a1ec73180..5d462f284fb 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -616,6 +616,17 @@ typedef struct IndexScan
List *indexorderbyops;
/* forward or backward or don't care */
ScanDirection indexorderdir;
+
+ /*
+ * Per indexorderbyorig entry: may setrefs.c replace a target-list
+ * occurrence of that expression with an INNER_VAR reference to the scan's
+ * ORDER BY value? True when the index column's opclass reports exact
+ * distances that are the operator's result (amcanreturnorderby).
+ * indexorderbytlist counts the replacements actually made (0 if none),
+ * for EXPLAIN.
+ */
+ List *indexorderbyexact;
+ int indexorderbytlist;
} IndexScan;
/* ----------------
diff --git a/src/test/regress/expected/box.out b/src/test/regress/expected/box.out
index 10760870ce7..60d92a26e1e 100644
--- a/src/test/regress/expected/box.out
+++ b/src/test/regress/expected/box.out
@@ -594,10 +594,10 @@ SET enable_bitmapscan = OFF;
EXPLAIN (COSTS OFF)
SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
FROM quad_box_tbl;
- QUERY PLAN
---------------------------------------------------------------------------------
+ QUERY PLAN
+----------------------------------------------------------------------------------
WindowAgg
- Window: w1 AS (ORDER BY (b <-> '(123,456)'::point) ROWS UNBOUNDED PRECEDING)
+ Window: w1 AS (ORDER BY ((b <-> '(123,456)'::point)) ROWS UNBOUNDED PRECEDING)
-> Index Scan using quad_box_tbl_idx on quad_box_tbl
Order By: (b <-> '(123,456)'::point)
(4 rows)
@@ -617,10 +617,10 @@ WHERE seq.id IS NULL OR idx.id IS NULL;
EXPLAIN (COSTS OFF)
SELECT rank() OVER (ORDER BY b <-> point '123,456') n, b <-> point '123,456' dist, id
FROM quad_box_tbl WHERE b <@ box '((200,300),(500,600))';
- QUERY PLAN
---------------------------------------------------------------------------------
+ QUERY PLAN
+----------------------------------------------------------------------------------
WindowAgg
- Window: w1 AS (ORDER BY (b <-> '(123,456)'::point) ROWS UNBOUNDED PRECEDING)
+ Window: w1 AS (ORDER BY ((b <-> '(123,456)'::point)) ROWS UNBOUNDED PRECEDING)
-> Index Scan using quad_box_tbl_idx on quad_box_tbl
Index Cond: (b <@ '(500,600),(200,300)'::box)
Order By: (b <-> '(123,456)'::point)
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.out
index ac79f94aa80..42396fdf5ef 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -387,6 +387,166 @@ select p from gist_tbl order by circle(p,1) <-> point(0,0) limit 1;
select p from gist_tbl order by circle(p,1) <-> point(0,0) limit 1;
ERROR: lossy distance functions are not supported in index-only scans
+drop index gist_tbl_multi_index;
+-- Test that an ordering Index Scan returns the AM's ORDER BY values to a
+-- targetlist entry equal to the ORDER BY expression, instead of evaluating
+-- the expression again, for an opclass that passes amcanreturnorderby.
+set enable_indexonlyscan = off;
+-- An expression index over a counting function proves the operator is not
+-- re-evaluated: the count stays at zero for the rows returned.
+create sequence gist_cnt_seq;
+create function gist_cnt_pt(point) returns point language plpgsql immutable
+ as $$ begin perform nextval('public.gist_cnt_seq'); return $1; end $$;
+create index gist_tbl_cnt_index on gist_tbl using gist (gist_cnt_pt(p));
+explain (verbose, costs off)
+select p, gist_cnt_pt(p) <-> point(0.201, 0.201) as dist
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0.201, 0.201) limit 3;
+ QUERY PLAN
+------------------------------------------------------------------------
+ Limit
+ Output: p, ((gist_cnt_pt(p) <-> '(0.201,0.201)'::point))
+ -> Index Scan using gist_tbl_cnt_index on public.gist_tbl
+ Output: p, ((gist_cnt_pt(p) <-> '(0.201,0.201)'::point))
+ Order By: (gist_cnt_pt(gist_tbl.p) <-> '(0.201,0.201)'::point)
+ Order By Values Used: 1
+(6 rows)
+
+select setval('gist_cnt_seq', 1, false);
+ setval
+--------
+ 1
+(1 row)
+
+select p, gist_cnt_pt(p) <-> point(0.201, 0.201) as dist
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0.201, 0.201) limit 3;
+ p | dist
+-------------+-----------------------
+ (0.2,0.2) | 0.0014142135623730963
+ (0.25,0.25) | 0.06929646455628163
+ (0.15,0.15) | 0.07212489168102787
+(3 rows)
+
+select nextval('gist_cnt_seq') - 1 as calls_during_scan;
+ calls_during_scan
+-------------------
+ 0
+(1 row)
+
+-- Every copy of the ORDER BY expression is served from the index; an
+-- expression that merely contains it is not.
+explain (verbose, costs off)
+select gist_cnt_pt(p) <-> point(0,0) as d1,
+ (gist_cnt_pt(p) <-> point(0,0)) * 2 as d2,
+ gist_cnt_pt(p) <-> point(0,0) as d3
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0,0) limit 2;
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Limit
+ Output: ((gist_cnt_pt(p) <-> '(0,0)'::point)), (((gist_cnt_pt(p) <-> '(0,0)'::point) * '2'::double precision)), ((gist_cnt_pt(p) <-> '(0,0)'::point))
+ -> Index Scan using gist_tbl_cnt_index on public.gist_tbl
+ Output: ((gist_cnt_pt(p) <-> '(0,0)'::point)), ((gist_cnt_pt(p) <-> '(0,0)'::point) * '2'::double precision), ((gist_cnt_pt(p) <-> '(0,0)'::point))
+ Order By: (gist_cnt_pt(gist_tbl.p) <-> '(0,0)'::point)
+ Order By Values Used: 2
+(6 rows)
+
+drop index gist_tbl_cnt_index;
+drop function gist_cnt_pt(point);
+drop sequence gist_cnt_seq;
+-- The box opclass computes its exact leaf distance with the operator's own
+-- code, so it qualifies too. The values must equal the operator's.
+create index gist_tbl_box_index on gist_tbl using gist (b);
+explain (verbose, costs off)
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91);
+ QUERY PLAN
+--------------------------------------------------------
+ Index Scan using gist_tbl_box_index on public.gist_tbl
+ Output: b, ((b <-> '(5.2,5.91)'::point))
+ Index Cond: (gist_tbl.b <@ '(6,6),(5,5)'::box)
+ Order By: (gist_tbl.b <-> '(5.2,5.91)'::point)
+ Order By Values Used: 1
+(5 rows)
+
+-- the distance numbers are not exactly the same across platforms
+set extra_float_digits = 0;
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91);
+ b | dist
+-------------------------+-------------------
+ (5.55,5.55),(5.55,5.55) | 0.502095608425328
+ (5.6,5.6),(5.6,5.6) | 0.5060632371552
+ (5.5,5.5),(5.5,5.5) | 0.508035431835221
+ (5.65,5.65),(5.65,5.65) | 0.519711458407451
+ (5.45,5.45),(5.45,5.45) | 0.523545604508337
+ (5.7,5.7),(5.7,5.7) | 0.54230987451825
+ (5.4,5.4),(5.4,5.4) | 0.547813836992093
+ (5.75,5.75),(5.75,5.75) | 0.572800139664787
+ (5.35,5.35),(5.35,5.35) | 0.57974132162543
+ (5.8,5.8),(5.8,5.8) | 0.61
+ (5.3,5.3),(5.3,5.3) | 0.618142378421024
+ (5.85,5.85),(5.85,5.85) | 0.652763356814703
+ (5.25,5.25),(5.25,5.25) | 0.661891229734917
+ (5.9,5.9),(5.9,5.9) | 0.700071424927486
+ (5.2,5.2),(5.2,5.2) | 0.71
+ (5.95,5.95),(5.95,5.95) | 0.751065909225016
+ (5.15,5.15),(5.15,5.15) | 0.761642960973184
+ (6,6),(6,6) | 0.805046582503149
+ (5.1,5.1),(5.1,5.1) | 0.816149496109629
+ (5.05,5.05),(5.05,5.05) | 0.872983390449097
+ (5,5),(5,5) | 0.931718841711383
+(21 rows)
+
+reset extra_float_digits;
+select count(*) filter (where dist = b <-> point(5.2, 5.91)) as same,
+ count(*) as total
+ from (select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ order by b <-> point(5.2, 5.91) limit 200) ss;
+ same | total
+------+-------
+ 200 | 200
+(1 row)
+
+-- Same, under row locking (the tuple is re-fetched by LockRows).
+set extra_float_digits = 0;
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91)
+ limit 3 for update;
+ b | dist
+-------------------------+-------------------
+ (5.55,5.55),(5.55,5.55) | 0.502095608425328
+ (5.6,5.6),(5.6,5.6) | 0.5060632371552
+ (5.5,5.5),(5.5,5.5) | 0.508035431835221
+(3 rows)
+
+reset extra_float_digits;
+drop index gist_tbl_box_index;
+-- The circle opclass's distance is a lower bound that is always rechecked,
+-- and its opclass does not pass amcanreturnorderby: the targetlist is left
+-- alone and the operator is evaluated as before.
+create index gist_tbl_circle_index on gist_tbl using gist (c);
+explain (verbose, costs off)
+select c <-> point(5.2, 5.91) as dist from gist_tbl
+ order by c <-> point(5.2, 5.91) limit 3;
+ QUERY PLAN
+-----------------------------------------------------------------
+ Limit
+ Output: ((c <-> '(5.2,5.91)'::point))
+ -> Index Scan using gist_tbl_circle_index on public.gist_tbl
+ Output: (c <-> '(5.2,5.91)'::point)
+ Order By: (gist_tbl.c <-> '(5.2,5.91)'::point)
+(5 rows)
+
+select count(*) filter (where dist = c <-> point(5.2, 5.91)) as same,
+ count(*) as total
+ from (select c, c <-> point(5.2, 5.91) as dist from gist_tbl
+ order by c <-> point(5.2, 5.91) limit 200) ss;
+ same | total
+------+-------
+ 200 | 200
+(1 row)
+
+drop index gist_tbl_circle_index;
+reset enable_indexonlyscan;
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql
index 57dcc082450..4d775f1d6e7 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -169,6 +169,86 @@ explain (verbose, costs off)
select p from gist_tbl order by circle(p,1) <-> point(0,0) limit 1;
select p from gist_tbl order by circle(p,1) <-> point(0,0) limit 1;
+drop index gist_tbl_multi_index;
+
+-- Test that an ordering Index Scan returns the AM's ORDER BY values to a
+-- targetlist entry equal to the ORDER BY expression, instead of evaluating
+-- the expression again, for an opclass that passes amcanreturnorderby.
+set enable_indexonlyscan = off;
+
+-- An expression index over a counting function proves the operator is not
+-- re-evaluated: the count stays at zero for the rows returned.
+create sequence gist_cnt_seq;
+create function gist_cnt_pt(point) returns point language plpgsql immutable
+ as $$ begin perform nextval('public.gist_cnt_seq'); return $1; end $$;
+create index gist_tbl_cnt_index on gist_tbl using gist (gist_cnt_pt(p));
+
+explain (verbose, costs off)
+select p, gist_cnt_pt(p) <-> point(0.201, 0.201) as dist
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0.201, 0.201) limit 3;
+
+select setval('gist_cnt_seq', 1, false);
+select p, gist_cnt_pt(p) <-> point(0.201, 0.201) as dist
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0.201, 0.201) limit 3;
+select nextval('gist_cnt_seq') - 1 as calls_during_scan;
+
+-- Every copy of the ORDER BY expression is served from the index; an
+-- expression that merely contains it is not.
+explain (verbose, costs off)
+select gist_cnt_pt(p) <-> point(0,0) as d1,
+ (gist_cnt_pt(p) <-> point(0,0)) * 2 as d2,
+ gist_cnt_pt(p) <-> point(0,0) as d3
+ from gist_tbl order by gist_cnt_pt(p) <-> point(0,0) limit 2;
+
+drop index gist_tbl_cnt_index;
+drop function gist_cnt_pt(point);
+drop sequence gist_cnt_seq;
+
+-- The box opclass computes its exact leaf distance with the operator's own
+-- code, so it qualifies too. The values must equal the operator's.
+create index gist_tbl_box_index on gist_tbl using gist (b);
+
+explain (verbose, costs off)
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91);
+
+-- the distance numbers are not exactly the same across platforms
+set extra_float_digits = 0;
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91);
+reset extra_float_digits;
+
+select count(*) filter (where dist = b <-> point(5.2, 5.91)) as same,
+ count(*) as total
+ from (select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ order by b <-> point(5.2, 5.91) limit 200) ss;
+
+-- Same, under row locking (the tuple is re-fetched by LockRows).
+set extra_float_digits = 0;
+select b, b <-> point(5.2, 5.91) as dist from gist_tbl
+ where b <@ box(point(5,5), point(6,6)) order by b <-> point(5.2, 5.91)
+ limit 3 for update;
+reset extra_float_digits;
+
+drop index gist_tbl_box_index;
+
+-- The circle opclass's distance is a lower bound that is always rechecked,
+-- and its opclass does not pass amcanreturnorderby: the targetlist is left
+-- alone and the operator is evaluated as before.
+create index gist_tbl_circle_index on gist_tbl using gist (c);
+
+explain (verbose, costs off)
+select c <-> point(5.2, 5.91) as dist from gist_tbl
+ order by c <-> point(5.2, 5.91) limit 3;
+
+select count(*) filter (where dist = c <-> point(5.2, 5.91)) as same,
+ count(*) as total
+ from (select c, c <-> point(5.2, 5.91) as dist from gist_tbl
+ order by c <-> point(5.2, 5.91) limit 200) ss;
+
+drop index gist_tbl_circle_index;
+reset enable_indexonlyscan;
+
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index d001f56efae..d534a8f5bb3 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3565,6 +3565,7 @@ ambuildempty_function
ambuildphasename_function
ambulkdelete_function
amcanreturn_function
+amcanreturnorderby_function
amcostestimate_function
amendscan_function
amestimateparallelscan_function
--
2.50.1
From a1f4a758f811b0697a0ba4ab4263b2a8edafe499 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Wed, 7 Oct 2026 01:50:09 +0000
Subject: [PATCH v5 3/4] Let an ordering index scan below a join emit its ORDER
BY values
With the previous two commits, an ordering Index Scan returns its ORDER
BY values to a target list entry that matches the ORDER BY expression,
and isn't charged for it. But that only happens when the scan is the
top of the scan/join tree. When the scan is below a join, its target
is rel->reltarget, which holds only the Vars the rest of the query
needs; the join computes the ORDER BY expression from those Vars, once
per joined row, though the scan already had the value. Tom Lane
pointed at this in the 2023 junk-column thread: a fix that only munges
the final targetlist "leaves everything on the table as soon as there's
more than one level of plan involved".
Give such an IndexPath its own PathTarget: a copy of rel->reltarget
with each returnable ORDER BY expression appended, but only if the
query needs that expression above the scan (a top-level entry of the
final targetlist, which includes sort columns). Most index paths keep
sharing rel->reltarget as before. The appended expressions cost the
scan nothing (cost_index() now uses path_target_cost()). Above the
scan, setrefs.c's fix_join_expr() already matches whole non-Var
expressions against the input targetlists before descending into them,
so the join's copy becomes a reference to the scan's output with no
setrefs change; and the join isn't charged for it either, since
path_target_cost() leaves out of a join path's target the entries an
input already emits (looking through Material and Memoize).
use_physical_tlist() must not replace such a scan's targetlist with a
physical one, which has only Vars; index_path_emits_orderby() tells it.
Scope: plain IndexScan paths on plain base relations only. Not
IndexOnlyScan (no ORDER BY value plumbing), not appendrel children
(Append/MergeAppend build their own child targetlists, and the
MergeAppend-over-kNN case already works through the scan/join target),
and only ORDER BY expressions that pass index_orderby_returnable().
Because the join reads the value from the scan's output, an outer join
nulls it correctly with the rest of that side's columns.
Author: Greg Burd <[email protected]>
Discussion: https://postgr.es/m/8s5lT8erXzBMugXJQ6Wginbp_gc2B4hmCYhF0Q0GpnuK87eCAOcKs5K31AWCwraCNFIQt42wwkow_MPPubHg485MWv-zDBY4NL_JX9yJEEg=@burd.me
Discussion: https://postgr.es/m/[email protected]
---
src/backend/optimizer/path/costsize.c | 12 +-
src/backend/optimizer/plan/createplan.c | 9 ++
src/backend/optimizer/util/pathnode.c | 182 +++++++++++++++++++++++-
src/include/optimizer/pathnode.h | 3 +
src/test/regress/expected/gist.out | 91 ++++++++++++
src/test/regress/sql/gist.sql | 45 ++++++
6 files changed, 336 insertions(+), 6 deletions(-)
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 7bbddb8bee4..a844701b1d1 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -564,6 +564,7 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
Cost min_IO_cost,
max_IO_cost;
QualCost qpqual_cost;
+ QualCost tlist_cost;
Cost cpu_per_tuple;
double tuples_fetched;
double pages_fetched;
@@ -799,9 +800,14 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
cpu_run_cost += cpu_per_tuple * tuples_fetched;
- /* tlist eval costs are paid per output row, not per tuple scanned */
- startup_cost += path->path.pathtarget->cost.startup;
- cpu_run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
+ /*
+ * tlist eval costs are paid per output row, not per tuple scanned. An
+ * ordering IndexScan doesn't pay for target entries it takes from its
+ * ORDER BY values.
+ */
+ tlist_cost = path_target_cost(root, (Path *) path, path->path.pathtarget);
+ startup_cost += tlist_cost.startup;
+ cpu_run_cost += tlist_cost.per_tuple * path->path.rows;
/* Adjust costing for parallelism, if used. */
if (path->path.parallel_workers > 0)
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 1cc87997a9a..507c1c8fb35 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -934,6 +934,15 @@ use_physical_tlist(PlannerInfo *root, Path *path, int flags)
return false;
}
+ /*
+ * Nor if a plain index scan path was asked to emit its ORDER BY values
+ * (see index_path_orderby_target()); a physical tlist has only Vars, so
+ * whatever needs them would compute them again.
+ */
+ if (path->pathtype == T_IndexScan &&
+ index_path_emits_orderby((IndexPath *) path))
+ return false;
+
/*
* For an index-only scan, the "physical tlist" is the index's indextlist.
* We can only return that without a projection if all the index's columns
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 303df571757..377491cf4f2 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1070,6 +1070,120 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer
return pathnode;
}
+/*
+ * index_path_orderby_target
+ * Choose the PathTarget for an ordering plain IndexScan path.
+ *
+ * Normally an IndexPath emits rel->reltarget, which holds only the Vars (and
+ * PlaceHolderVars) the rest of the query needs. An ORDER BY expression is
+ * not in it: it is computed by whatever plan node first needs it. When the
+ * scan is the top of the scan/join tree that is the scan itself, and
+ * setrefs.c lets it take the value from its ORDER BY values. But when the
+ * scan is below a join, the join computes the expression from the Vars,
+ * once per joined row, though the scan already had the value.
+ *
+ * So if the scan can return any of its ORDER BY values (see
+ * index_orderby_returnable()), and the query needs that expression above
+ * the scan (it is in the final targetlist, which includes sort columns),
+ * give the path a copy of rel->reltarget with those expressions appended.
+ * They cost the scan nothing (path_target_cost() exempts them), and
+ * setrefs.c's fix_join_expr() matches them in the parent join's expressions,
+ * replacing its copy with a reference to the scan's output.
+ *
+ * Restricted to plain base relations: an appendrel child's paths are wrapped
+ * by Append/MergeAppend, which build their own targetlists, and the top-level
+ * scan/join target already handles the unjoined case. Returns
+ * rel->reltarget unchanged when there's nothing to add, which is the common
+ * case, so most paths share it as before.
+ */
+static PathTarget *
+index_path_orderby_target(PlannerInfo *root, IndexOptInfo *index,
+ List *indexorderbys, List *indexorderbycols)
+{
+ RelOptInfo *rel = index->rel;
+ PathTarget *target = NULL;
+ ListCell *lo,
+ *lcol;
+
+ if (indexorderbys == NIL || rel->reloptkind != RELOPT_BASEREL ||
+ root->processed_tlist == NIL)
+ return rel->reltarget;
+
+ forboth(lo, indexorderbys, lcol, indexorderbycols)
+ {
+ Expr *orderby = (Expr *) lfirst(lo);
+ bool needed = false;
+ ListCell *lt;
+
+ if (!index_orderby_returnable(index, lfirst_int(lcol), orderby))
+ continue;
+
+ /*
+ * Only if some top-level targetlist entry is this expression; an
+ * expression that merely contains it would not be rewritten, and
+ * emitting the value would just widen the tuple.
+ */
+ foreach(lt, root->processed_tlist)
+ {
+ TargetEntry *tle = lfirst_node(TargetEntry, lt);
+
+ if (orderby_tlist_match(tle->expr, orderby))
+ {
+ needed = true;
+ break;
+ }
+ }
+ if (!needed)
+ continue;
+
+ if (target == NULL)
+ target = copy_pathtarget(rel->reltarget);
+ add_column_to_pathtarget(target, orderby, 0);
+ }
+
+ if (target == NULL)
+ return rel->reltarget;
+
+ /* add_column_to_pathtarget doesn't maintain cost and width */
+ return set_pathtarget_cost_width(root, target);
+}
+
+/*
+ * index_path_emits_orderby
+ * Does this plain IndexScan path's target hold a value it takes from its
+ * ORDER BY values?
+ *
+ * use_physical_tlist() must not replace such a target with the scan's
+ * physical tlist, which has only Vars, or whatever needs the value would
+ * compute it again.
+ */
+bool
+index_path_emits_orderby(IndexPath *ipath)
+{
+ ListCell *lc;
+
+ if (ipath->path.pathtype != T_IndexScan || ipath->indexorderbys == NIL)
+ return false;
+
+ foreach(lc, ipath->path.pathtarget->exprs)
+ {
+ Expr *expr = (Expr *) lfirst(lc);
+ ListCell *lo,
+ *lcol;
+
+ if (IsA(expr, Var))
+ continue;
+ forboth(lo, ipath->indexorderbys, lcol, ipath->indexorderbycols)
+ {
+ if (index_orderby_returnable(ipath->indexinfo, lfirst_int(lcol),
+ (Expr *) lfirst(lo)) &&
+ orderby_tlist_match(expr, (Expr *) lfirst(lo)))
+ return true;
+ }
+ }
+ return false;
+}
+
/*
* create_index_path
* Creates a path node for an index scan.
@@ -1109,7 +1223,9 @@ create_index_path(PlannerInfo *root,
pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
pathnode->path.parent = rel;
- pathnode->path.pathtarget = rel->reltarget;
+ pathnode->path.pathtarget = indexonly ? rel->reltarget :
+ index_path_orderby_target(root, index, indexorderbys,
+ indexorderbycols);
pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
required_outer);
pathnode->path.parallel_aware = false;
@@ -2675,24 +2791,84 @@ orderby_tlist_match(Expr *expr, Expr *orderby)
equal(lsecond(a->args), linitial(b->args));
}
+/*
+ * join_target_cost
+ * path_target_cost() for a join path.
+ *
+ * A join takes any top-level target expression that one of its inputs
+ * already emits from that input's output instead of evaluating it again:
+ * setrefs.c's fix_join_expr() matches whole non-Var expressions against the
+ * input targetlists before descending into them. Join inputs ordinarily
+ * emit only Vars and PlaceHolderVars, so this changes nothing; but an
+ * ordering IndexScan input may emit the ORDER BY values it returns (see
+ * index_path_orderby_target()). Look through Material and Memoize, which
+ * pass their input's targetlist up unchanged. We look only at the join's
+ * immediate inputs; the value can't reach a higher join without passing
+ * through this one's targetlist, which is the joinrel's and has only Vars.
+ */
+static QualCost
+join_target_cost(PlannerInfo *root, JoinPath *jpath, PathTarget *target)
+{
+ QualCost cost = target->cost;
+ Path *inputs[2] = {jpath->outerjoinpath, jpath->innerjoinpath};
+ ListCell *lc;
+
+ foreach(lc, target->exprs)
+ {
+ Node *expr = (Node *) lfirst(lc);
+
+ if (IsA(expr, Var) || IsA(expr, PlaceHolderVar))
+ continue;
+
+ for (int i = 0; i < 2; i++)
+ {
+ Path *input = inputs[i];
+
+ while (IsA(input, MaterialPath) || IsA(input, MemoizePath))
+ input = IsA(input, MaterialPath) ?
+ ((MaterialPath *) input)->subpath :
+ ((MemoizePath *) input)->subpath;
+
+ if (IsA(input, IndexPath) &&
+ index_path_emits_orderby((IndexPath *) input) &&
+ list_member(input->pathtarget->exprs, expr))
+ {
+ QualCost ecost;
+
+ cost_qual_eval_node(&ecost, expr, root);
+ cost.startup -= ecost.startup;
+ cost.per_tuple -= ecost.per_tuple;
+ break;
+ }
+ }
+ }
+
+ return cost;
+}
+
/*
* path_target_cost
* Return the cost 'path' pays to evaluate 'target'.
*
- * Normally that's just target->cost. But a plain IndexScan takes any
+ * Normally that's just target->cost. A join path doesn't pay for entries
+ * an input already emits (see join_target_cost()). And a plain IndexScan
+ * takes any
* top-level target expression that is a returnable ORDER BY expression
* (see orderby_tlist_match()) from its ORDER BY values instead of
* evaluating it (setrefs.c rewrites it into a reference to them), so it
* doesn't pay for those. Each target entry
* is counted at most once, as setrefs.c rewrites it once.
*/
-static QualCost
+QualCost
path_target_cost(PlannerInfo *root, Path *path, PathTarget *target)
{
QualCost cost = target->cost;
IndexPath *ipath;
ListCell *lc;
+ if (IsA(path, NestPath) || IsA(path, MergePath) || IsA(path, HashPath))
+ return join_target_cost(root, (JoinPath *) path, target);
+
if (!IsA(path, IndexPath) || path->pathtype != T_IndexScan)
return cost;
ipath = (IndexPath *) path;
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index fad229234fd..8fcfe60aba3 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -229,6 +229,9 @@ extern void sort_pathlist_by_cost(List *pathlist);
extern bool index_orderby_returnable(IndexOptInfo *index, int indexcol,
Expr *orderby);
extern bool orderby_tlist_match(Expr *expr, Expr *orderby);
+extern QualCost path_target_cost(PlannerInfo *root, Path *path,
+ PathTarget *target);
+extern bool index_path_emits_orderby(IndexPath *ipath);
extern ProjectionPath *create_projection_path(PlannerInfo *root,
RelOptInfo *rel,
Path *subpath,
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.out
index df37c8096d1..4fc2b084df1 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -631,6 +631,97 @@ reset enable_seqscan;
reset enable_bitmapscan;
reset enable_indexonlyscan;
drop table gist_commute;
+-- An ordering Index Scan below a join emits the ORDER BY value it returns,
+-- so the join above reads it instead of evaluating the expression again.
+-- The counting function shows the expression is evaluated zero times.
+create sequence gist_join_cnt;
+create function gist_join_pt(point) returns point
+ language plpgsql immutable strict cost 1000
+ as $$ begin perform nextval('public.gist_join_cnt'); return $1; end $$;
+create temp table gist_join_fact as
+ select g as id, point(g % 101, g % 103) as p from generate_series(1, 1000) g;
+create index on gist_join_fact using gist (gist_join_pt(p));
+create temp table gist_join_dim as select g as id from generate_series(1, 1000, 2) g;
+create index on gist_join_dim (id);
+vacuum analyze gist_join_fact;
+vacuum analyze gist_join_dim;
+set enable_seqscan = off;
+set enable_bitmapscan = off;
+set enable_indexonlyscan = off;
+set enable_hashjoin = off;
+set enable_mergejoin = off;
+set enable_sort = off;
+explain (verbose, costs off)
+select f.id, gist_join_pt(f.p) <-> point(5,5) as d
+ from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+ QUERY PLAN
+--------------------------------------------------------------------------------------------
+ Limit
+ Output: f.id, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ -> Nested Loop
+ Output: f.id, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ -> Index Scan using gist_join_fact_gist_join_pt_p_idx on pg_temp.gist_join_fact f
+ Output: f.id, f.p, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ Order By: (gist_join_pt(f.p) <-> '(5,5)'::point)
+ Order By Values Used: 1
+ -> Index Scan using gist_join_dim_id_idx on pg_temp.gist_join_dim j
+ Output: j.id
+ Index Cond: (j.id = f.id)
+(11 rows)
+
+select setval('gist_join_cnt', 1, false);
+ setval
+--------
+ 1
+(1 row)
+
+select f.id, gist_join_pt(f.p) <-> point(5,5) as d
+ from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+ id | d
+-----+--------------------
+ 5 | 0
+ 107 | 1.4142135623730951
+ 209 | 2.8284271247461903
+(3 rows)
+
+select nextval('gist_join_cnt') - 1 as calls_during_join;
+ calls_during_join
+-------------------
+ 0
+(1 row)
+
+-- Nothing extra is emitted when the query doesn't need the value above the
+-- scan.
+explain (verbose, costs off)
+select f.id from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+ QUERY PLAN
+--------------------------------------------------------------------------------------------
+ Limit
+ Output: f.id, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ -> Nested Loop
+ Output: f.id, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ -> Index Scan using gist_join_fact_gist_join_pt_p_idx on pg_temp.gist_join_fact f
+ Output: f.id, f.p, ((gist_join_pt(f.p) <-> '(5,5)'::point))
+ Order By: (gist_join_pt(f.p) <-> '(5,5)'::point)
+ Order By Values Used: 1
+ -> Index Scan using gist_join_dim_id_idx on pg_temp.gist_join_dim j
+ Output: j.id
+ Index Cond: (j.id = f.id)
+(11 rows)
+
+reset enable_seqscan;
+reset enable_bitmapscan;
+reset enable_indexonlyscan;
+reset enable_hashjoin;
+reset enable_mergejoin;
+reset enable_sort;
+drop table gist_join_fact;
+drop table gist_join_dim;
+drop function gist_join_pt(point);
+drop sequence gist_join_cnt;
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql
index 87492a11df4..9e7bc0fd176 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -309,6 +309,51 @@ reset enable_bitmapscan;
reset enable_indexonlyscan;
drop table gist_commute;
+-- An ordering Index Scan below a join emits the ORDER BY value it returns,
+-- so the join above reads it instead of evaluating the expression again.
+-- The counting function shows the expression is evaluated zero times.
+create sequence gist_join_cnt;
+create function gist_join_pt(point) returns point
+ language plpgsql immutable strict cost 1000
+ as $$ begin perform nextval('public.gist_join_cnt'); return $1; end $$;
+create temp table gist_join_fact as
+ select g as id, point(g % 101, g % 103) as p from generate_series(1, 1000) g;
+create index on gist_join_fact using gist (gist_join_pt(p));
+create temp table gist_join_dim as select g as id from generate_series(1, 1000, 2) g;
+create index on gist_join_dim (id);
+vacuum analyze gist_join_fact;
+vacuum analyze gist_join_dim;
+set enable_seqscan = off;
+set enable_bitmapscan = off;
+set enable_indexonlyscan = off;
+set enable_hashjoin = off;
+set enable_mergejoin = off;
+set enable_sort = off;
+explain (verbose, costs off)
+select f.id, gist_join_pt(f.p) <-> point(5,5) as d
+ from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+select setval('gist_join_cnt', 1, false);
+select f.id, gist_join_pt(f.p) <-> point(5,5) as d
+ from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+select nextval('gist_join_cnt') - 1 as calls_during_join;
+-- Nothing extra is emitted when the query doesn't need the value above the
+-- scan.
+explain (verbose, costs off)
+select f.id from gist_join_fact f join gist_join_dim j on j.id = f.id
+ order by gist_join_pt(f.p) <-> point(5,5) limit 3;
+reset enable_seqscan;
+reset enable_bitmapscan;
+reset enable_indexonlyscan;
+reset enable_hashjoin;
+reset enable_mergejoin;
+reset enable_sort;
+drop table gist_join_fact;
+drop table gist_join_dim;
+drop function gist_join_pt(point);
+drop sequence gist_join_cnt;
+
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
--
2.50.1
From 6aac246ef5e848462514bf5b68b58f3f9c748d13 Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Wed, 7 Oct 2026 01:50:04 +0000
Subject: [PATCH v5 2/4] Don't charge an ordering index scan for ORDER BY
values it returns
The previous commit lets a plain Index Scan return its ORDER BY values
to a target list entry that matches the ORDER BY expression, instead of
evaluating that expression again. The planner didn't know that. An
ORDER BY expression is always part of the scan/join target (as a sort
column, if nothing else), and apply_scanjoin_target_to_paths() charges
every path rows * cost(expression) when it applies that target. For
the Index Scan that cost is now never paid, while Seq Scan + Sort and
Bitmap Heap Scan + Sort really do pay it, once per row. With a costly
ORDER BY expression the planner therefore overestimated the kNN scan by
up to ~32x and picked a Sort plan that was up to 13x slower.
Teach create_projection_path() and apply_projection_to_path() to cost
the target a path pays for with a new helper, path_target_cost(), which
for a plain IndexScan leaves out top-level target expressions the scan
will take from its ORDER BY values. The test for "will take" is
index_orderby_returnable() plus orderby_tlist_match(); setrefs.c's
rewrite and create_indexscan_plan() use the same two, so the cost model
and the plan cannot drift apart. orderby_tlist_match() accepts the
expression equal() to the ORDER BY key, and also its commuted form:
match_clause_to_ordering_op() turns "const <-> col" into "col <-> const"
for the index, so a target entry written the original way is the same
value but not equal() to the key. An expression that only contains the
ORDER BY expression, e.g. (expr) * 2, isn't rewritten and is still
charged.
Because this makes an IndexPath cheaper relative to its siblings,
apply_scanjoin_target_to_paths() can no longer assume that applying the
target preserves the cost ordering of rel->pathlist and
rel->partial_pathlist, which add_path_precheck() and the
linitial(partial_pathlist) callers rely on. Re-sort them with a new
sort_pathlist_by_cost(), a stable insertion sort that is a single pass
in the usual already-sorted case.
Nothing changes for an index whose opclass does not pass
amcanreturnorderby, for IndexOnlyScan, for bitmap scans, or for any
query without a returnable ORDER BY expression in the target.
Author: Greg Burd <[email protected]>
Discussion: https://postgr.es/m/8s5lT8erXzBMugXJQ6Wginbp_gc2B4hmCYhF0Q0GpnuK87eCAOcKs5K31AWCwraCNFIQt42wwkow_MPPubHg485MWv-zDBY4NL_JX9yJEEg=@burd.me
---
src/backend/optimizer/plan/createplan.c | 17 +--
src/backend/optimizer/plan/planner.c | 10 +-
src/backend/optimizer/plan/setrefs.c | 16 ++-
src/backend/optimizer/util/pathnode.c | 171 +++++++++++++++++++++++-
src/include/optimizer/pathnode.h | 4 +
src/test/regress/expected/gist.out | 92 ++++++++++++-
src/test/regress/sql/gist.sql | 60 +++++++++
7 files changed, 342 insertions(+), 28 deletions(-)
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index c0f22b278c3..1cc87997a9a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -3036,14 +3036,15 @@ create_indexscan_plan(PlannerInfo *root,
if (!indexonly && indexorderbys != NIL)
{
List *exact = NIL;
- ListCell *lc;
-
- foreach(lc, best_path->indexorderbycols)
- {
- int indexcol = lfirst_int(lc);
-
- exact = lappend_int(exact, indexinfo->canreturnorderby[indexcol]);
- }
+ ListCell *lo,
+ *lc;
+
+ /* must agree with path_target_cost() in pathnode.c */
+ forboth(lo, best_path->indexorderbys, lc, best_path->indexorderbycols)
+ exact = lappend_int(exact,
+ index_orderby_returnable(indexinfo,
+ lfirst_int(lc),
+ (Expr *) lfirst(lo)));
((IndexScan *) scan_plan)->indexorderbyexact = exact;
}
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index edaa42d713a..3b70b8a378f 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -8259,8 +8259,10 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
* If the tlist exprs are the same, we can just inject the sortgroupref
* information into the existing pathtargets. Otherwise, replace each
* path with a projection path that generates the SRF-free scan/join
- * target. This can't change the ordering of paths within rel->pathlist,
- * so we just modify the list in place.
+ * target. We modify the lists in place. That usually adds the same cost
+ * to every path, but a plain IndexScan doesn't pay for target entries it
+ * takes from its ORDER BY values, so it can become cheaper relative to
+ * the others; restore the cost ordering afterwards.
*/
foreach(lc, rel->pathlist)
{
@@ -8281,6 +8283,8 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
lfirst(lc) = newpath;
}
}
+ if (!tlist_same_exprs)
+ sort_pathlist_by_cost(rel->pathlist);
/* Likewise adjust the targets for any partial paths. */
foreach(lc, rel->partial_pathlist)
@@ -8302,6 +8306,8 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
lfirst(lc) = newpath;
}
}
+ if (!tlist_same_exprs)
+ sort_pathlist_by_cost(rel->partial_pathlist);
/*
* Now, if final scan/join target contains SRFs, insert ProjectSetPath(s)
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 3cf0f18dfbb..df5777df900 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -1375,15 +1375,19 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
* For each ORDER BY key whose index column's opclass promises that the
* distances it reports for an exact (non-rechecked) row are the ordering
* operator's own result (indexorderbyexact[i], from amcanreturnorderby),
- * replace each top-level targetlist expression that is equal() to the i'th
- * indexorderbyorig expression with Var(INNER_VAR, i + 1). nodeIndexscan.c
+ * replace each top-level targetlist expression that is the i'th
+ * indexorderbyorig expression (equal() to it, or its commuted form; see
+ * orderby_tlist_match()) with Var(INNER_VAR, i + 1). nodeIndexscan.c
* then fills a virtual slot with the ORDER BY values of every returned row --
* the AM's for an exact row, the recomputed ones for a rechecked row -- and
* installs it as the projection's inner tuple. A scan node has no inner
* plan, so INNER_VAR is otherwise unused here.
*
- * Only float8/float4 expressions qualify: those are the only types
- * index_store_float8_orderby_distances() can deliver.
+ * indexorderbyexact[i] comes from index_orderby_returnable(), which also
+ * limits this to float8/float4, the only types
+ * index_store_float8_orderby_distances() can deliver. The planner costs
+ * the scan with the same test (path_target_cost() in pathnode.c), so what
+ * is costed is what is built.
*/
static void
replace_orderby_tlist_refs(IndexScan *splan)
@@ -1409,9 +1413,7 @@ replace_orderby_tlist_refs(IndexScan *splan)
Oid typ = exprType((Node *) orig);
i++;
- if (lfirst_int(le) &&
- (typ == FLOAT8OID || typ == FLOAT4OID) &&
- equal(tle->expr, orig))
+ if (lfirst_int(le) && orderby_tlist_match(tle->expr, orig))
{
tle->expr = (Expr *) makeVar(INNER_VAR, i, typ,
exprTypmod((Node *) orig),
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 67c47fd7c6c..303df571757 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -15,10 +15,12 @@
#include "postgres.h"
#include "access/htup_details.h"
+#include "catalog/pg_type.h"
#include "executor/nodeSetOp.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "nodes/extensible.h"
+#include "nodes/nodeFuncs.h"
#include "optimizer/appendinfo.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
@@ -28,6 +30,7 @@
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
#include "parser/parsetree.h"
+#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/selfuncs.h"
@@ -2577,6 +2580,155 @@ create_hashjoin_path(PlannerInfo *root,
return pathnode;
}
+/*
+ * sort_pathlist_by_cost
+ * Restore the ordering add_path() and add_partial_path() maintain
+ * (fewest disabled nodes, then lowest total cost) after the costs of
+ * paths already in the list were changed in place.
+ *
+ * This is a stable insertion sort: it costs one pass when the list is still
+ * in order, which is the usual case, and keeps equal-cost paths in the order
+ * they were added.
+ */
+void
+sort_pathlist_by_cost(List *pathlist)
+{
+ for (int i = 1; i < list_length(pathlist); i++)
+ {
+ Path *path = list_nth(pathlist, i);
+ int j;
+
+ for (j = i; j > 0; j--)
+ {
+ Path *prev = list_nth(pathlist, j - 1);
+
+ if (prev->disabled_nodes < path->disabled_nodes ||
+ (prev->disabled_nodes == path->disabled_nodes &&
+ prev->total_cost <= path->total_cost))
+ break;
+ lfirst(list_nth_cell(pathlist, j)) = prev;
+ }
+ lfirst(list_nth_cell(pathlist, j)) = path;
+ }
+}
+
+/*
+ * index_orderby_returnable
+ * Will an IndexScan on 'index' hand back the value of ORDER BY expression
+ * 'orderby', bound to index column 'indexcol', to its targetlist?
+ *
+ * create_indexscan_plan() records this per key for setrefs.c, and
+ * path_target_cost() uses it to cost the path, so that the cost we assign to
+ * a path is the cost of the plan we build from it. The opclass must promise
+ * exact values (amcanreturnorderby), and the expression must be of a type
+ * the AM can deliver.
+ */
+bool
+index_orderby_returnable(IndexOptInfo *index, int indexcol, Expr *orderby)
+{
+ Oid typ;
+
+ if (index->canreturnorderby == NULL || !index->canreturnorderby[indexcol])
+ return false;
+
+ typ = exprType((Node *) orderby);
+ return (typ == FLOAT8OID || typ == FLOAT4OID);
+}
+
+/*
+ * orderby_tlist_match
+ * Is targetlist expression 'expr' the value of ORDER BY expression
+ * 'orderby'?
+ *
+ * 'orderby' is an IndexPath's indexorderbys entry, which has the index key
+ * on the left; match_clause_to_ordering_op() commutes "const OP key" into
+ * that form. So a targetlist entry that the user wrote in the original
+ * "const OP key" form is the same value but not equal() to it. Accept it
+ * if it is the commuted operator applied to the swapped arguments; an
+ * operator's commutator yields the same result by definition.
+ *
+ * Shared by path_target_cost() and setrefs.c's replace_orderby_tlist_refs()
+ * so that what is costed is what is built.
+ */
+bool
+orderby_tlist_match(Expr *expr, Expr *orderby)
+{
+ OpExpr *a,
+ *b;
+
+ if (equal(expr, orderby))
+ return true;
+
+ if (!IsA(expr, OpExpr) || !IsA(orderby, OpExpr))
+ return false;
+ a = (OpExpr *) expr;
+ b = (OpExpr *) orderby;
+ if (list_length(a->args) != 2 || list_length(b->args) != 2)
+ return false;
+ if (a->opresulttype != b->opresulttype ||
+ a->opcollid != b->opcollid ||
+ a->inputcollid != b->inputcollid ||
+ get_commutator(a->opno) != b->opno)
+ return false;
+
+ return equal(linitial(a->args), lsecond(b->args)) &&
+ equal(lsecond(a->args), linitial(b->args));
+}
+
+/*
+ * path_target_cost
+ * Return the cost 'path' pays to evaluate 'target'.
+ *
+ * Normally that's just target->cost. But a plain IndexScan takes any
+ * top-level target expression that is a returnable ORDER BY expression
+ * (see orderby_tlist_match()) from its ORDER BY values instead of
+ * evaluating it (setrefs.c rewrites it into a reference to them), so it
+ * doesn't pay for those. Each target entry
+ * is counted at most once, as setrefs.c rewrites it once.
+ */
+static QualCost
+path_target_cost(PlannerInfo *root, Path *path, PathTarget *target)
+{
+ QualCost cost = target->cost;
+ IndexPath *ipath;
+ ListCell *lc;
+
+ if (!IsA(path, IndexPath) || path->pathtype != T_IndexScan)
+ return cost;
+ ipath = (IndexPath *) path;
+ if (ipath->indexorderbys == NIL)
+ return cost;
+
+ foreach(lc, target->exprs)
+ {
+ Node *expr = (Node *) lfirst(lc);
+ ListCell *lo,
+ *lcol;
+
+ if (IsA(expr, Var))
+ continue; /* costs nothing anyway */
+
+ forboth(lo, ipath->indexorderbys, lcol, ipath->indexorderbycols)
+ {
+ Expr *orderby = (Expr *) lfirst(lo);
+
+ if (index_orderby_returnable(ipath->indexinfo, lfirst_int(lcol),
+ orderby) &&
+ orderby_tlist_match((Expr *) expr, orderby))
+ {
+ QualCost ecost;
+
+ cost_qual_eval_node(&ecost, expr, root);
+ cost.startup -= ecost.startup;
+ cost.per_tuple -= ecost.per_tuple;
+ break;
+ }
+ }
+ }
+
+ return cost;
+}
+
/*
* create_projection_path
* Creates a pathnode that represents performing a projection.
@@ -2637,6 +2789,9 @@ create_projection_path(PlannerInfo *root,
if (is_projection_capable_path(subpath) ||
equal(oldtarget->exprs, target->exprs))
{
+ QualCost oldcost = path_target_cost(root, subpath, oldtarget);
+ QualCost newcost = path_target_cost(root, subpath, target);
+
/* No separate Result node needed */
pathnode->dummypp = true;
@@ -2646,10 +2801,10 @@ create_projection_path(PlannerInfo *root,
pathnode->path.rows = subpath->rows;
pathnode->path.disabled_nodes = subpath->disabled_nodes;
pathnode->path.startup_cost = subpath->startup_cost +
- (target->cost.startup - oldtarget->cost.startup);
+ (newcost.startup - oldcost.startup);
pathnode->path.total_cost = subpath->total_cost +
- (target->cost.startup - oldtarget->cost.startup) +
- (target->cost.per_tuple - oldtarget->cost.per_tuple) * subpath->rows;
+ (newcost.startup - oldcost.startup) +
+ (newcost.per_tuple - oldcost.per_tuple) * subpath->rows;
}
else
{
@@ -2701,6 +2856,7 @@ apply_projection_to_path(PlannerInfo *root,
PathTarget *target)
{
QualCost oldcost;
+ QualCost newcost;
/*
* If given path can't project, we might need a Result node, so make a
@@ -2713,12 +2869,13 @@ apply_projection_to_path(PlannerInfo *root,
* We can just jam the desired tlist into the existing path, being sure to
* update its cost estimates appropriately.
*/
- oldcost = path->pathtarget->cost;
+ oldcost = path_target_cost(root, path, path->pathtarget);
+ newcost = path_target_cost(root, path, target);
path->pathtarget = target;
- path->startup_cost += target->cost.startup - oldcost.startup;
- path->total_cost += target->cost.startup - oldcost.startup +
- (target->cost.per_tuple - oldcost.per_tuple) * path->rows;
+ path->startup_cost += newcost.startup - oldcost.startup;
+ path->total_cost += newcost.startup - oldcost.startup +
+ (newcost.per_tuple - oldcost.per_tuple) * path->rows;
/*
* If the path happens to be a Gather or GatherMerge path, we'd like to
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index da2d9b384b5..fad229234fd 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -225,6 +225,10 @@ extern HashPath *create_hashjoin_path(PlannerInfo *root,
Relids required_outer,
List *hashclauses);
+extern void sort_pathlist_by_cost(List *pathlist);
+extern bool index_orderby_returnable(IndexOptInfo *index, int indexcol,
+ Expr *orderby);
+extern bool orderby_tlist_match(Expr *expr, Expr *orderby);
extern ProjectionPath *create_projection_path(PlannerInfo *root,
RelOptInfo *rel,
Path *subpath,
diff --git a/src/test/regress/expected/gist.out b/src/test/regress/expected/gist.out
index 42396fdf5ef..df37c8096d1 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -547,6 +547,90 @@ select count(*) filter (where dist = c <-> point(5.2, 5.91)) as same,
drop index gist_tbl_circle_index;
reset enable_indexonlyscan;
+-- The planner must not charge an ordering Index Scan for evaluating a
+-- targetlist entry it takes from its ORDER BY values. With a costly ORDER BY
+-- expression, the kNN scan should win over Seq Scan + Sort even when the
+-- filter is selective, since the Sort plan really does evaluate it per row.
+create function gist_costly_pt(point) returns point
+ language plpgsql immutable strict cost 10000
+ as $$ begin return $1; end $$;
+create temp table gist_costly (id int, p point, grp int);
+insert into gist_costly
+ select g, point(g % 101, g % 103), g % 100 from generate_series(1, 10000) g;
+create index on gist_costly using gist (gist_costly_pt(p));
+create index on gist_costly (grp);
+vacuum analyze gist_costly;
+set enable_bitmapscan = off;
+explain (costs off)
+select id, gist_costly_pt(p) <-> point(0,0) as dist from gist_costly
+ where grp < 5 order by gist_costly_pt(p) <-> point(0,0);
+ QUERY PLAN
+------------------------------------------------------------------
+ Index Scan using gist_costly_gist_costly_pt_p_idx on gist_costly
+ Order By: (gist_costly_pt(p) <-> '(0,0)'::point)
+ Filter: (grp < 5)
+(3 rows)
+
+-- The ORDER BY value is in every plan's target (as a sort column), so the
+-- kNN scan used to be charged rows * cost(gist_costly_pt) for it, ~2.5e5
+-- here. It is now charged nothing for it; an expression that merely
+-- contains it is still evaluated, and charged.
+create function gist_costly_total(q text) returns float8 language plpgsql as
+$$ declare j json; begin
+ execute 'explain (format json) ' || q into j;
+ return (j->0->'Plan'->>'Total Cost')::float8;
+ end $$;
+set enable_sort = off;
+select gist_costly_total('select id, gist_costly_pt(p) <-> point(0,0)
+ from gist_costly order by gist_costly_pt(p) <-> point(0,0)') < 10000
+ as returned_is_free,
+ gist_costly_total('select id, (gist_costly_pt(p) <-> point(0,0)) * 2
+ from gist_costly order by gist_costly_pt(p) <-> point(0,0)') > 100000
+ as nested_is_charged;
+ returned_is_free | nested_is_charged
+------------------+-------------------
+ t | t
+(1 row)
+
+reset enable_sort;
+drop function gist_costly_total(text);
+reset enable_bitmapscan;
+drop table gist_costly;
+drop function gist_costly_pt(point);
+-- The ORDER BY expression written as "const OP key" is commuted into
+-- "key OP const" for the index; a targetlist entry in the original form is
+-- still the same value, and is still taken from the scan.
+create temp table gist_commute as
+ select g as id, point(g % 101, g % 103) as p from generate_series(1, 1000) g;
+create index on gist_commute using gist (p);
+vacuum analyze gist_commute;
+set enable_seqscan = off;
+set enable_bitmapscan = off;
+set enable_indexonlyscan = off;
+explain (verbose, costs off)
+select point(5,5) <-> p as d from gist_commute order by point(5,5) <-> p limit 3;
+ QUERY PLAN
+-------------------------------------------------------------------
+ Limit
+ Output: ((p <-> '(5,5)'::point))
+ -> Index Scan using gist_commute_p_idx on pg_temp.gist_commute
+ Output: ((p <-> '(5,5)'::point))
+ Order By: (gist_commute.p <-> '(5,5)'::point)
+ Order By Values Used: 1
+(6 rows)
+
+select point(5,5) <-> p as d from gist_commute order by point(5,5) <-> p limit 3;
+ d
+--------------------
+ 0
+ 1.4142135623730951
+ 1.4142135623730951
+(3 rows)
+
+reset enable_seqscan;
+reset enable_bitmapscan;
+reset enable_indexonlyscan;
+drop table gist_commute;
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
@@ -568,10 +652,10 @@ explain (costs off)
select lower(r) = repeat('7', 200)::numeric as lower_ok,
upper(r) = repeat('8', 200)::numeric as upper_ok
from gist_ios_tupdesc where r && numrange(null, null);
- QUERY PLAN
---------------------------------------------------------------------
- Index Only Scan using gist_ios_tupdesc_a_r_idx on gist_ios_tupdesc
- Index Cond: (r && '(,)'::numrange)
+ QUERY PLAN
+----------------------------------
+ Seq Scan on gist_ios_tupdesc
+ Filter: (r && '(,)'::numrange)
(2 rows)
select lower(r) = repeat('7', 200)::numeric as lower_ok,
diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql
index 4d775f1d6e7..87492a11df4 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -249,6 +249,66 @@ select count(*) filter (where dist = c <-> point(5.2, 5.91)) as same,
drop index gist_tbl_circle_index;
reset enable_indexonlyscan;
+-- The planner must not charge an ordering Index Scan for evaluating a
+-- targetlist entry it takes from its ORDER BY values. With a costly ORDER BY
+-- expression, the kNN scan should win over Seq Scan + Sort even when the
+-- filter is selective, since the Sort plan really does evaluate it per row.
+create function gist_costly_pt(point) returns point
+ language plpgsql immutable strict cost 10000
+ as $$ begin return $1; end $$;
+create temp table gist_costly (id int, p point, grp int);
+insert into gist_costly
+ select g, point(g % 101, g % 103), g % 100 from generate_series(1, 10000) g;
+create index on gist_costly using gist (gist_costly_pt(p));
+create index on gist_costly (grp);
+vacuum analyze gist_costly;
+set enable_bitmapscan = off;
+
+explain (costs off)
+select id, gist_costly_pt(p) <-> point(0,0) as dist from gist_costly
+ where grp < 5 order by gist_costly_pt(p) <-> point(0,0);
+
+-- The ORDER BY value is in every plan's target (as a sort column), so the
+-- kNN scan used to be charged rows * cost(gist_costly_pt) for it, ~2.5e5
+-- here. It is now charged nothing for it; an expression that merely
+-- contains it is still evaluated, and charged.
+create function gist_costly_total(q text) returns float8 language plpgsql as
+$$ declare j json; begin
+ execute 'explain (format json) ' || q into j;
+ return (j->0->'Plan'->>'Total Cost')::float8;
+ end $$;
+set enable_sort = off;
+select gist_costly_total('select id, gist_costly_pt(p) <-> point(0,0)
+ from gist_costly order by gist_costly_pt(p) <-> point(0,0)') < 10000
+ as returned_is_free,
+ gist_costly_total('select id, (gist_costly_pt(p) <-> point(0,0)) * 2
+ from gist_costly order by gist_costly_pt(p) <-> point(0,0)') > 100000
+ as nested_is_charged;
+reset enable_sort;
+drop function gist_costly_total(text);
+
+reset enable_bitmapscan;
+drop table gist_costly;
+drop function gist_costly_pt(point);
+
+-- The ORDER BY expression written as "const OP key" is commuted into
+-- "key OP const" for the index; a targetlist entry in the original form is
+-- still the same value, and is still taken from the scan.
+create temp table gist_commute as
+ select g as id, point(g % 101, g % 103) as p from generate_series(1, 1000) g;
+create index on gist_commute using gist (p);
+vacuum analyze gist_commute;
+set enable_seqscan = off;
+set enable_bitmapscan = off;
+set enable_indexonlyscan = off;
+explain (verbose, costs off)
+select point(5,5) <-> p as d from gist_commute order by point(5,5) <-> p limit 3;
+select point(5,5) <-> p as d from gist_commute order by point(5,5) <-> p limit 3;
+reset enable_seqscan;
+reset enable_bitmapscan;
+reset enable_indexonlyscan;
+drop table gist_commute;
+
-- Test that an index-only scan deforms the tuple it reconstructs with the
-- descriptor the AM formed it with, not the scan slot's descriptor.
create temp table gist_ios_tupdesc (a inet, r numrange);
--
2.50.1
