On Tuesday, October 6th, 2026 at 12:29 PM, Greg Burd <[email protected]> wrote:
>
> What this means is a) this is a good performance win, and b) I now need to see
> if it makes sense to adjust the costing of this pattern given that some shapes
> are ~97% faster now. For instances, a vec_10k the plan costs ~50× what it
> actually does with this fix in place. I'll poke around and see if I come up
> with something that avoids tipping the decision in the wrong direction (away
> from an index scan) and add a patch in if I do.
I did, it's 0002. 0001 is v3 unchanged, rebased.
The problem: an ORDER BY expression is always in the scan/join target,
as a sort column if nothing else, and create_projection_path() charges
every path rows * cost(expr) for it. With 0001 the ordering Index Scan
never pays that, but Seq Scan + Sort and Bitmap Heap Scan + Sort still
do. So with a costly ORDER BY expression the kNN scan was overcharged
by up to ~32x and lost to Sort plans that ran 1.2-13x slower.
0002 adds a static path_target_cost() in pathnode.c that leaves out the
target entries a plain IndexScan takes from its ORDER BY values;
create_projection_path() and apply_projection_to_path() use it. The
"does the scan return this one" test, index_orderby_returnable(), is
shared with create_indexscan_plan(), so what is costed is what setrefs.c
builds. An expression that only contains the ORDER BY expression, e.g.
(expr) * 2, isn't rewritten and is still charged.
Same data dir, v3 vs v3+0002, -O2 without cassert, 200k rows, ORDER BY
slow_pt(p) <-> point(500,500) where slow_pt() is plpgsql at ~13us/call
declared COST 1000, median of 5 runs. "Sort" is Sort over a Bitmap Heap
Scan on a btree on grp:
---- v3 ---------- -- v3+0002 -------
WHERE plan est ms plan est ms
------------------ ---- ------ ------ ---- ----- -----
grp < 50 Sort 257908 1109.1 kNN 16428 85.7
grp < 20 Sort 99637 437.5 kNN 16428 83.1
grp < 10 Sort 47211 212.5 kNN 16428 81.1
grp < 10 LIMIT 2e4 Sort 47211 214.0 kNN 16428 83.5
grp < 5 Sort 22042 101.2 kNN 16428 81.1
grp < 2 Sort 6463 34.9 Sort 6463 35.4
grp < 2 rightly stays a Sort. Unfiltered and LIMIT cases were already
kNN on v3 and don't change plan. Costs are byte-identical to v3 for
circle_ops, Index Only Scan, bitmap scans and any query without a
returnable ORDER BY value in its target. Planning a kNN query took
~61us with and without 0002; a join query was too noisy to call either
way. The new gist test picks the kNN plan with 0002 and a Sort without
it.
Questions I'd expect, and why it's done this way:
* Why not fix it in cost_index() or amcostestimate? The charge isn't
made there. An IndexPath's own target is rel->reltarget (Vars only);
the ORDER BY expression is first charged when the scan/join target is
applied, so that's where the IndexScan's exemption has to be.
* Why re-sort rel->pathlist and partial_pathlist? Applying the target
used to add the same cost to every path, so
apply_scanjoin_target_to_paths() could assume order was kept. Now an
IndexPath can get cheaper relative to its siblings, and
add_path_precheck() and the linitial(partial_pathlist) callers rely
on that order. sort_pathlist_by_cost() is a stable insertion sort, a
single pass in the usual already-sorted case. To be clear: I haven't
produced a wrong plan from an unsorted list, this is defensive, and
the partial_pathlist half can't trigger today since neither GiST nor
SP-GiST is amcanparallel. Happy to drop it if people would rather.
* Doesn't this duplicate setrefs.c's matching? It repeats the equal()
walk over the target, yes, but on the same predicate. The two must
agree or we cost one plan and build another, and sharing
index_orderby_returnable() is the cheapest way I found to keep them
together without moving the setrefs decision into path creation.
Things I'm less sure of:
* An ordered IndexScan below a join (nestloop inner, merge join input)
isn't helped. That's consistent, since setrefs only rewrites the
scan's own targetlist and there the expression really is evaluated
above it, but it means the win is limited to the top scan/join rel.
* Matching is equal() on top-level entries only, so it's
representation-sensitive: an ORDER BY expression that's semantically
the same but built differently (an inserted RelabelType, say) is
neither rewritten nor discounted. Consistent, but a missed case.
* Cheap operators get a small discount too (cpu_operator_cost * rows for
point <-> point). That's correct per 0001's numbers, it was being
overcharged, but it does nudge qualifying point/box kNN plans slightly
cheaper than before.
* The discount is exactly the declared COST, like every other
expression cost. A truly expensive ORDER BY function left at the
default COST 100 still runs faster with 0001 but is planned as if it
were cheap, so 0002 may not flip its plan.
v4 applies to current master.
best.
-greg
From 0ff2019944291b2c9c7fdd590a9cf346397c220c Mon Sep 17 00:00:00 2001
From: Greg Burd <[email protected]>
Date: Tue, 6 Oct 2026 18:59:26 +0000
Subject: [PATCH v4 2/2] 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 is equal() to 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 ~30x and picked a Sort plan that was 2-13x slower.
Teach create_projection_path() and apply_projection_to_path() to cost
the target an IndexPath pays for with a new static helper,
path_target_cost(), which leaves out top-level target expressions the
scan will take from its ORDER BY values. The test for "will take" is
index_orderby_returnable(), which create_indexscan_plan() now also uses
to fill IndexScan.indexorderbyexact, so the cost model and setrefs.c's
rewrite are the same predicate and cannot drift apart. Expressions
that only contain the ORDER BY expression are not rewritten by setrefs
and are 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() relies 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: their
costs are identical to before.
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 | 11 +-
src/backend/optimizer/util/pathnode.c | 129 ++++++++++++++++++++++--
src/include/optimizer/pathnode.h | 3 +
src/test/regress/expected/gist.out | 50 +++++++++
src/test/regress/sql/gist.sql | 42 ++++++++
7 files changed, 240 insertions(+), 22 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..d16bd7d5cd3 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -1382,8 +1382,11 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
* 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 +1412,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) && equal(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..d34d50f3a69 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"
@@ -2577,6 +2579,114 @@ 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);
+}
+
+/*
+ * 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 equal() to a returnable ORDER BY expression
+ * 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) &&
+ equal(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 +2747,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 +2759,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 +2814,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 +2827,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..c13a91b12ee 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -225,6 +225,9 @@ 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 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..158a05e7ad4 100644
--- a/src/test/regress/expected/gist.out
+++ b/src/test/regress/expected/gist.out
@@ -547,6 +547,56 @@ 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);
-- 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 4d775f1d6e7..8271be1b538 100644
--- a/src/test/regress/sql/gist.sql
+++ b/src/test/regress/sql/gist.sql
@@ -249,6 +249,48 @@ 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);
+
-- 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 v4 1/2] 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
