Hello hackers, I'd like to see core improve the full text search index provided in core at some point which these days means including BM25 (and likely other) algorithm(s). To learn about that space I've been working on an extension [1].
While working on that I stumbled onto something that seemed odd and worth investing time in. It turns out that an index scan followed by an order by doesn't do what I'd expected, it doesn't use the orderbyvals returned by the index when ordering results. SELECT id, body <=> 'search terms' AS score FROM docs ORDER BY body <=> 'search terms' LIMIT 10; In that query the executor will get the ranked set of results from the index scan and ignore it and then turn around and re-compute a rank value for each document in isolation. BM25 ranking is over a corpus, not a single document so this was a head scratcher because to me this looked like doing double the work only to get incorrect results. I did some digging [2] and I find [3] I'm not alone [4]. And that I agreed with Chris Cleveland's [5] statement: > It would also be nice if the orderbyval could be made available in > the projection. That way we could report the score() in the > result set. Only to find later that Tom explained that this was a more subtle issue that it seemed to be on the surface. > An index ordering operator is an optimization that the planner may > or may not choose to employ. If you've designed your code on the > assumption that that's the only possible plan, it will break for > any but the most trivial queries. [6] Reading into Tom's objection what I take away is that one should not make the operator's own value index-dependent, so that the same SQL expression means different things under different plans, stop me if I'm wrong. This proposal does not change what `body <=> q` means anywhere so hopefully doesn't fall into that trap. What the patch changes is much narrower. I propose that when the executor chooses an Index Scan and the AM reports its value as exact (`xs_recheckorderby = false`), the executor may substitute that value for a target-list occurrence of the identical ORDER BY expression. It may not substitute anything else. - For an AM whose exact value equals the operator's result (GiST on points, btree_gist, pg_trgm `<->`), the substitution is a pure optimization with no observable change. That is the pgvector case raised by Heikki. - For an AM whose value differs from the operator's (pgvector's squared L2, every BM25 AM), the substitution is observable. The patch mirrors what Index Only Scan already does for indexed columns. With IoS, setrefs rewrites target-list expressions that match an index column into `INDEX_VAR` references. Here, it rewrites target-list expressions that match an ORDER BY expression into references to the scan's ORDER BY values. I think I've addressed Tom's 2023 concern, "the planner [must] not spend too much effort on looking for subexpression matches" [7] because only top-level target-list entries are compared, against a list that is almost always of length 1. An ORDER BY expression buried inside a larger target expression is not matched. To me that's not a wrong answer but a missed optimization, possibly future work. Feel free to disagree (Tom). :) I update EXPLAIN to avoid confusion, before an `EXPLAIN VERBOSE` prints `Output: id, (body <=> '...'::wquery)` but with the patch it prints the expression, by de-parsing the `INDEX_VAR` back through `indexorderbyorig`, the same way IndexOnlyScan's `INDEX_VAR`s are de-parsed through `indextlist`. It adds one line, `Order By Values Used: 1`, so a user can tell the two behaviors apart and I've added a regression test watching for that to validate it is happening in practice. Okay, that's more than enough to see if anyone agrees that this is an important things to fix and an approach that is making good trade-offs or not. best. -greg [1] https://codeberg.org/gregburd/pg_weave (not finished yet) https://codeberg.org/gregburd/pg_fts (works great!) https://codeberg.org/gregburd/pg_turbovec (works great!) https://codeberg.org/gregburd/pg_tre (approximate REGEX index?! noice, also works great!) [2] https://pg.ddx.io/search and https://pg.ddx.io/mcp [3] https://www.postgresql.org/message-id/CAEze2WgJOTFoCV1U2MfVSo0w9CLG=oyzmnuxeexrtipvkjy...@mail.gmail.com/ [4] https://www.postgresql.org/message-id/2ca5865b-4693-40e5-8f78-f3b45d5378fb%40iki.fi [5] https://pg.ddx.io/m/pgsql-hackers/cabsn6vflk5msedsr8wpemh_h3xnyr2xs5njk8+uozp0bvxw...@mail.gmail.com/ [6] https://www.postgresql.org/message-id/2246002.1714670501%40sss.pgh.pa.us [7] https://www.postgresql.org/message-id/[email protected]
From 1c2ff55d92802d0419940bcf0963568f0981ca09 Mon Sep 17 00:00:00 2001 From: Greg Burd <[email protected]> Date: Thu, 1 Oct 2026 10:19:05 -0400 Subject: [PATCH v1] 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. For an expensive distance operator that is wasted work; for an AM whose ordering value depends on index-wide state the displayed number is not the number the rows were ordered by. Add IndexAmRoutine.amorderbyvalsexact. When an AM sets it, setrefs.c replaces each top-level target list expression that is equal() to the i'th 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. A lossy AM's lower bound is never displayed. Only float4/float8 ORDER BY expressions qualify, as those are the only types index_store_float8_orderby_distances() can deliver. 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, polygon expected output). GiST and SP-GiST set the flag; their non-rechecked distances are the operator's result, so for them this is a pure optimization. Other AMs default to false and are unaffected. --- doc/src/sgml/indexam.sgml | 19 ++++ src/backend/access/gist/gist.c | 1 + 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 | 4 + src/backend/optimizer/plan/setrefs.c | 56 ++++++++++ src/backend/optimizer/util/plancat.c | 2 + src/backend/utils/adt/ruleutils.c | 31 ++++++ src/include/access/amapi.h | 9 ++ src/include/nodes/execnodes.h | 7 ++ src/include/nodes/pathnodes.h | 1 + src/include/nodes/plannodes.h | 9 ++ src/test/regress/expected/box.out | 12 +-- src/test/regress/expected/gist.out | 130 ++++++++++++++++++++++++ src/test/regress/expected/polygon.out | 6 +- src/test/regress/sql/gist.sql | 60 +++++++++++ 17 files changed, 432 insertions(+), 11 deletions(-) diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml index f48da318530..a263f85c003 100644 --- a/doc/src/sgml/indexam.sgml +++ b/doc/src/sgml/indexam.sgml @@ -109,6 +109,8 @@ typedef struct IndexAmRoutine bool amcanorder; /* does AM support ORDER BY result of an operator on indexed column? */ bool amcanorderbyop; + /* are the AM's non-rechecked ORDER BY values exact enough to display? */ + bool amorderbyvalsexact; /* does AM support hashing using API consistent with the hash AM? */ bool amcanhash; /* do operators within an opfamily have consistent equality semantics? */ @@ -989,6 +991,23 @@ 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 approximations that the executor must recompute from the heap + tuple. If the access method also sets + <structfield>amorderbyvalsexact</structfield> to true, it promises that + whenever <literal>xs_recheckorderby</literal> is false, the values in + <literal>xs_orderbyvals</literal> are the values the query should see; + the executor may then return them directly for a target list entry + that is the same expression as the <literal>ORDER BY</literal> key, + instead of evaluating the operator again. An access method whose + ordering values differ from what the operator would compute on the + heap tuple (because they are approximate, or depend on index-wide + state) must leave this false unless it intends that difference to be + visible. + </para> </listitem> </itemizedlist> </para> diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c index 8565e225be7..1a43314aaf7 100644 --- a/src/backend/access/gist/gist.c +++ b/src/backend/access/gist/gist.c @@ -65,6 +65,7 @@ gisthandler(PG_FUNCTION_ARGS) .amoptsprocnum = GIST_OPTIONS_PROC, .amcanorder = false, .amcanorderbyop = true, + .amorderbyvalsexact = true, .amcanhash = false, .amconsistentequality = false, .amconsistentordering = false, diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c index f2ee333f60d..1d8f0cffec0 100644 --- a/src/backend/access/spgist/spgutils.c +++ b/src/backend/access/spgist/spgutils.c @@ -50,6 +50,7 @@ spghandler(PG_FUNCTION_ARGS) .amoptsprocnum = SPGIST_OPTIONS_PROC, .amcanorder = false, .amcanorderbyop = true, + .amorderbyvalsexact = true, .amcanhash = false, .amconsistentequality = false, .amconsistentordering = false, 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..6504fed2bf1 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 an AM with amorderbyvalsexact). `vals`/`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..7635707d300 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -3033,6 +3033,10 @@ create_indexscan_plan(PlannerInfo *root, indexorderbyops, best_path->indexscandir); + if (!indexonly && indexorderbys != NIL) + ((IndexScan *) scan_plan)->indexorderbyexact = + indexinfo->amorderbyvalsexact; + 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 8a641402a96..3ecea955800 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); @@ -701,6 +702,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: @@ -1360,6 +1363,59 @@ 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. + * + * If the index AM promises that the ORDER BY values it reports for an exact + * (non-rechecked) row are the values the query should see + * (amorderbyvalsexact), 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 || splan->indexorderbyorig == NIL) + return; + + foreach(lc, splan->scan.plan.targetlist) + { + TargetEntry *tle = lfirst_node(TargetEntry, lc); + ListCell *lo; + int i = 0; + + foreach(lo, splan->indexorderbyorig) + { + Expr *orig = (Expr *) lfirst(lo); + Oid typ = exprType((Node *) orig); + + i++; + if ((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..5e691a7fb65 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -305,6 +305,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, /* We copy just the fields we need, not all of rd_indam */ amroutine = indexRelation->rd_indam; info->amcanorderbyop = amroutine->amcanorderbyop; + info->amorderbyvalsexact = amroutine->amorderbyvalsexact; info->amoptionalkey = amroutine->amoptionalkey; info->amsearcharray = amroutine->amsearcharray; info->amsearchnulls = amroutine->amsearchnulls; @@ -406,6 +407,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, else { info->amcanorderbyop = false; + info->amorderbyvalsexact = false; info->amoptionalkey = false; info->amsearcharray = false; info->amsearchnulls = false; 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..e19f7df2454 100644 --- a/src/include/access/amapi.h +++ b/src/include/access/amapi.h @@ -247,6 +247,15 @@ typedef struct IndexAmRoutine bool amcanorder; /* does AM support ORDER BY result of an operator on indexed column? */ bool amcanorderbyop; + + /* + * When an ordering scan reports xs_recheckorderby = false, may the + * executor substitute the AM's xs_orderbyvals for an identical ORDER BY + * expression in the scan's target list, rather than re-evaluating it? + * Setting this asserts that the value the AM reports IS the value the + * query should display. See nodeIndexscan.c. + */ + bool amorderbyvalsexact; /* does AM support hashing using API consistent with the hash AM? */ bool amcanhash; /* do operators within an opfamily have consistent equality semantics? */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 91bb0bd2e13..07a404e665b 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..1e4f2bd64e7 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -1434,6 +1434,7 @@ typedef struct IndexOptInfo * (IndexAmRoutine). These fields are not set for partitioned indexes. */ bool amcanorderbyop; + bool amorderbyvalsexact; bool amoptionalkey; bool amsearcharray; bool amsearchnulls; diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 09a1ec73180..295d2b9db69 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -616,6 +616,15 @@ typedef struct IndexScan List *indexorderbyops; /* forward or backward or don't care */ ScanDirection indexorderdir; + + /* + * May setrefs.c replace target-list occurrences of an indexorderbyorig + * expression with INNER_VAR references to the scan's ORDER BY values? + * Copied from the AM's amorderbyvalsexact. indexorderbytlist counts the + * replacements actually made (0 if none), for EXPLAIN. + */ + bool 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..dd52c687535 100644 --- a/src/test/regress/expected/gist.out +++ b/src/test/regress/expected/gist.out @@ -387,6 +387,136 @@ 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 (amorderbyvalsexact). +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's distance to a point is lossy, so this exercises the +-- recheck and reorder-queue paths; the displayed values must match 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) + +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.5020956084253276 + (5.6,5.6),(5.6,5.6) | 0.5060632371551997 + (5.5,5.5),(5.5,5.5) | 0.5080354318352215 + (5.65,5.65),(5.65,5.65) | 0.5197114584074514 + (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.5478138369920934 + (5.75,5.75),(5.75,5.75) | 0.5728001396647873 + (5.35,5.35),(5.35,5.35) | 0.5797413216254301 + (5.8,5.8),(5.8,5.8) | 0.6099999999999997 + (5.3,5.3),(5.3,5.3) | 0.6181423784210239 + (5.85,5.85),(5.85,5.85) | 0.6527633568147031 + (5.25,5.25),(5.25,5.25) | 0.6618912297349167 + (5.9,5.9),(5.9,5.9) | 0.7000714249274858 + (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.7616429609731844 + (6,6),(6,6) | 0.8050465825031491 + (5.1,5.1),(5.1,5.1) | 0.8161494961096287 + (5.05,5.05),(5.05,5.05) | 0.8729833904490971 + (5,5),(5,5) | 0.9317188417113825 +(21 rows) + +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). +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.5020956084253276 + (5.6,5.6),(5.6,5.6) | 0.5060632371551997 + (5.5,5.5),(5.5,5.5) | 0.5080354318352215 +(3 rows) + +drop index gist_tbl_box_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/expected/polygon.out b/src/test/regress/expected/polygon.out index c01848f103e..e9560664870 100644 --- a/src/test/regress/expected/polygon.out +++ b/src/test/regress/expected/polygon.out @@ -283,10 +283,10 @@ SET enable_bitmapscan = OFF; EXPLAIN (COSTS OFF) SELECT rank() OVER (ORDER BY p <-> point '123,456') n, p <-> point '123,456' dist, id FROM quad_poly_tbl WHERE p <@ polygon '((300,300),(400,600),(600,500),(700,200))'; - QUERY PLAN ---------------------------------------------------------------------------------- + QUERY PLAN +---------------------------------------------------------------------------------- WindowAgg - Window: w1 AS (ORDER BY (p <-> '(123,456)'::point) ROWS UNBOUNDED PRECEDING) + Window: w1 AS (ORDER BY ((p <-> '(123,456)'::point)) ROWS UNBOUNDED PRECEDING) -> Index Scan using quad_poly_tbl_idx on quad_poly_tbl Index Cond: (p <@ '((300,300),(400,600),(600,500),(700,200))'::polygon) Order By: (p <-> '(123,456)'::point) diff --git a/src/test/regress/sql/gist.sql b/src/test/regress/sql/gist.sql index 57dcc082450..e1f4e0b9685 100644 --- a/src/test/regress/sql/gist.sql +++ b/src/test/regress/sql/gist.sql @@ -169,6 +169,66 @@ 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 (amorderbyvalsexact). +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's distance to a point is lossy, so this exercises the +-- recheck and reorder-queue paths; the displayed values must match 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); + +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); + +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). +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; + +drop index gist_tbl_box_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); -- 2.50.1
