From: Heikki Linnakangas <hlinnaka@iki.fi>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: KNN-GiST with recheck
Date: Fri, 15 May 2015 02:30:05 +0300
Message-ID: <55552FFD.8030808@iki.fi> (raw)
In-Reply-To: <55552F9D.4090603@iki.fi>
References: <CAPpHfdvn5jxgh-rVMz7c2vXoYW_W7dGrJjQkVAtaCr=-ZMCADA@mail.gmail.com>
<CAPpHfdvEpZAJrMBkNrCguG4fCK5QtZjARPti7LnL5chsSuD=Sg@mail.gmail.com>
<20140926011800.GA8130@momjian.us>
<CAPpHfdvDMS1_jqnzZ0FbGePWwCvStj4_h0xU2hYTnLcC6of3Rg@mail.gmail.com>
<20140929021631.GG12447@momjian.us>
<CAPpHfdvdL0dtoNBmbCsJ=W0bFE7A87hLOtoBN7Pe4hnXkQ9LxA@mail.gmail.com>
<20141006093609.GA12899@hasegeli.com>
<5490357C.8090800@vmware.com>
<CAPpHfdtm=A3hrw4=mhNxN6U2Q9bx4BYDhW8gRLxgaZD3MAQKCA@mail.gmail.com>
<CAPpHfdstkF4RW_1cYje=EZyTx5VRgUK_+L3c2ucBASdD156tVg@mail.gmail.com>
<CAPpHfduGjVpTLVxwXmeMuFqR-ykH-ERdewF-KHxSQiRdw29-7g@mail.gmail.com>
<54EC8D3E.2000908@2ndquadrant.com>
<CAPpHfdsZVJnMMOuTUusJQmcR1QeRN4qc93-KE014_JHqYU717g@mail.gmail.com>
<CAPpHfdv40pmc7N3CcpBDEcTAnLT6dWaN76LP5Q9xzTvvdwRMQg@mail.gmail.com>
<5553A2FF.1030501@iki.fi>
<CAPpHfdtGyAnZK6fRFAmSyR5+AbccgxTajLvGYzdvpUg70Wsg2A@mail.gmail.com>
<CAPpHfdvDk4=VRPUGvLL0rwVTys247shUeckcURQ42Y3-2tidAg@mail.gmail.com>
<55552F9D.4090603@iki.fi>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 05/15/2015 02:28 AM, Heikki Linnakangas wrote:
> I think this is now ready for committing, but I'm pretty tired now so
> I'll read through this one more time in the morning, so that I won't
> wake up to a red buildfarm.
Forgot to attach the latest patch, here you go.
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:0001-Allow-GiST-distance-function-to-return-merely-a-lowe.patch (application/x-patch, 44.0K) download
From df00d9c972a760e1ed777a7c9b1603dad1d3f134 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <heikki.linnakangas@iki.fi>
Date: Fri, 15 May 2015 00:56:27 +0300
Subject: [PATCH 1/1] Allow GiST distance function to return merely a
lower-bound.
The distance function can now set *recheck = false, like index quals. The
executor will then re-check the ORDER BY expressions, and use a queue to
reorder the results on the fly.
This makes it possible to do kNN-searches on polygons and circles, which
store a bounding box in the index, rather than the exact value.
Alexander Korotkov and me
---
doc/src/sgml/gist.sgml | 35 ++-
src/backend/access/gist/gistget.c | 22 +-
src/backend/access/gist/gistproc.c | 37 +++
src/backend/access/gist/gistscan.c | 5 +
src/backend/executor/nodeIndexscan.c | 351 ++++++++++++++++++++++++++++-
src/backend/optimizer/plan/createplan.c | 69 ++++--
src/backend/utils/adt/geo_ops.c | 27 +++
src/include/access/genam.h | 3 +
src/include/access/relscan.h | 9 +
src/include/catalog/catversion.h | 2 +-
src/include/catalog/pg_amop.h | 2 +
src/include/catalog/pg_amproc.h | 2 +
src/include/catalog/pg_operator.h | 8 +-
src/include/catalog/pg_proc.h | 4 +
src/include/nodes/execnodes.h | 19 ++
src/include/nodes/plannodes.h | 12 +-
src/include/utils/geo_decls.h | 3 +
src/test/regress/expected/create_index.out | 78 +++++++
src/test/regress/sql/create_index.sql | 12 +
19 files changed, 663 insertions(+), 37 deletions(-)
diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgmlindex e7d1ff9..1291f8d 100644--- a/doc/src/sgml/gist.sgml+++ b/doc/src/sgml/gist.sgml@@ -105,6 +105,7 @@
<literal>~=</>
</entry>
<entry>
+ <literal><-></>
</entry>
</row>
<row>
@@ -163,6 +164,7 @@
<literal>~=</>
</entry>
<entry>
+ <literal><-></>
</entry>
</row>
<row>
@@ -207,6 +209,12 @@
</table>
<para>
+ Currently, ordering by the distance operator <literal><-></>+ is supported only with <literal>point</> by the operator classes+ of the geometric types.+ </para>++ <para>
For historical reasons, the <literal>inet_ops</> operator class is
not the default class for types <type>inet</> and <type>cidr</>.
To use it, mention the class name in <command>CREATE INDEX</>,
@@ -780,6 +788,7 @@ my_distance(PG_FUNCTION_ARGS)
data_type *query = PG_GETARG_DATA_TYPE_P(1);
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
/* Oid subtype = PG_GETARG_OID(3); */
+ /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
data_type *key = DatumGetDataType(entry->key);
double retval;
@@ -792,14 +801,24 @@ my_distance(PG_FUNCTION_ARGS)
</programlisting>
The arguments to the <function>distance</> function are identical to
- the arguments of the <function>consistent</> function, except that no- recheck flag is used. The distance to a leaf index entry must always- be determined exactly, since there is no way to re-order the tuples- once they are returned. Some approximation is allowed when determining- the distance to an internal tree node, so long as the result is never- greater than any child's actual distance. Thus, for example, distance- to a bounding box is usually sufficient in geometric applications. The- result value can be any finite <type>float8</> value. (Infinity and+ the arguments of the <function>consistent</> function.+ </para>++ <para>+ Some approximation is allowed when determining the distance, as long as+ the result is never greater than the entry's actual distance. Thus, for+ example, distance to a bounding box is usually sufficient in geometric+ applications. For an internal tree node, the distance returned must not+ be greater than the distance to any of the child nodes. If the returned+ distance is not accurate, the function must set *recheck to false. (This+ is not necessary for internal tree nodes; for them, the calculation is+ always assumed to be inaccurate). The executor will calculate the+ accurate distance after fetching the tuple from the heap, and reorder+ the tuples if necessary.+ </para>++ <para>+ The result value can be any finite <type>float8</> value. (Infinity and
minus infinity are used internally to handle cases such as nulls, so it
is not recommended that <function>distance</> functions return these
values.)
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.cindex e4c00c2..90cb3e0 100644--- a/src/backend/access/gist/gistget.c+++ b/src/backend/access/gist/gistget.c@@ -176,6 +176,7 @@ gistindex_keytest(IndexScanDesc scan,
else
{
Datum dist;
+ bool recheck;
GISTENTRY de;
gistdentryinit(giststate, key->sk_attno - 1, &de,
@@ -192,16 +193,21 @@ gistindex_keytest(IndexScanDesc scan,
* always be zero, but might as well pass it for possible future
* use.)
*
- * Note that Distance functions don't get a recheck argument. We- * can't tolerate lossy distance calculations on leaf tuples;- * there is no opportunity to re-sort the tuples afterwards.+ * Distance functions get a recheck argument as well. In this+ * case the returned distance is the lower bound of distance+ * and needs to be rechecked. We return single recheck flag+ * which means that both quals and distances are to be+ * rechecked.
*/
- dist = FunctionCall4Coll(&key->sk_func,+ dist = FunctionCall5Coll(&key->sk_func,
key->sk_collation,
PointerGetDatum(&de),
key->sk_argument,
Int32GetDatum(key->sk_strategy),
- ObjectIdGetDatum(key->sk_subtype));+ ObjectIdGetDatum(key->sk_subtype),+ PointerGetDatum(&recheck));++ *recheck_p |= recheck;
*distance_p = DatumGetFloat8(dist);
}
@@ -434,6 +440,7 @@ getNextNearest(IndexScanDesc scan)
{
GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
bool res = false;
+ int i;
if (scan->xs_itup)
{
@@ -454,6 +461,11 @@ getNextNearest(IndexScanDesc scan)
/* found a heap item at currently minimal distance */
scan->xs_ctup.t_self = item->data.heap.heapPtr;
scan->xs_recheck = item->data.heap.recheck;
+ for (i = 0; i < scan->numberOfOrderBys; i++)+ {+ scan->xs_orderbyvals[i] = Float8GetDatum(item->distances[i]);+ scan->xs_orderbynulls[i] = false;+ }
/* in an index-only scan, also return the reconstructed tuple. */
if (scan->xs_want_itup)
diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.cindex 9d21e3f..38dad11 100644--- a/src/backend/access/gist/gistproc.c+++ b/src/backend/access/gist/gistproc.c@@ -1478,3 +1478,40 @@ gist_point_distance(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8(distance);
}
++/*+ * The inexact GiST distance method for geometric types that store bounding+ * boxes.+ *+ * Compute lossy distance from point to index entries. The result is inexact+ * because index entries are bounding boxes, not the exact shapes of the+ * indexed geometric types. We use distance from point to MBR of index entry.+ * This is correct lower bound estimate of distance from point to indexed+ * geometric type.+ */+Datum+gist_bbox_distance(PG_FUNCTION_ARGS)+{+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);+ StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);+ bool *recheck = (bool *) PG_GETARG_POINTER(4);+ double distance;+ StrategyNumber strategyGroup = strategy / GeoStrategyNumberOffset;++ /* Bounding box distance is always inexact. */+ *recheck = true;++ switch (strategyGroup)+ {+ case PointStrategyNumberGroup:+ distance = computeDistance(false,+ DatumGetBoxP(entry->key),+ PG_GETARG_POINT_P(1));+ break;+ default:+ elog(ERROR, "unknown strategy number: %d", strategy);+ distance = 0.0; /* keep compiler quiet */+ }++ PG_RETURN_FLOAT8(distance);+}diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.cindex 6f65398..099849a 100644--- a/src/backend/access/gist/gistscan.c+++ b/src/backend/access/gist/gistscan.c@@ -85,6 +85,11 @@ gistbeginscan(PG_FUNCTION_ARGS)
/* workspaces with size dependent on numberOfOrderBys: */
so->distances = palloc(sizeof(double) * scan->numberOfOrderBys);
so->qual_ok = true; /* in case there are zero keys */
+ if (scan->numberOfOrderBys > 0)+ {+ scan->xs_orderbyvals = palloc(sizeof(Datum) * scan->numberOfOrderBys);+ scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys);+ }
scan->opaque = so;
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.cindex 48fa919..9386768 100644--- a/src/backend/executor/nodeIndexscan.c+++ b/src/backend/executor/nodeIndexscan.c@@ -16,6 +16,7 @@
* INTERFACE ROUTINES
* ExecIndexScan scans a relation using an index
* IndexNext retrieve next tuple using index
+ * IndexNextWithReorder same, but recheck ORDER BY expressions
* ExecInitIndexScan creates and initializes state info.
* ExecReScanIndexScan rescans the indexed relation.
* ExecEndIndexScan releases all storage.
@@ -28,14 +29,92 @@
#include "access/relscan.h"
#include "executor/execdebug.h"
#include "executor/nodeIndexscan.h"
+#include "lib/pairingheap.h"
#include "optimizer/clauses.h"
#include "utils/array.h"
+#include "utils/datum.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
+/*+ * When an ordering operator is used, tuples fetched from the index that+ * need to be reordered are queued in a pairing heap, as ReorderTuples.+ */+typedef struct+{+ pairingheap_node ph_node;+ HeapTuple htup;+ Datum *orderbyvals;+ bool *orderbynulls;+} ReorderTuple;++static int+cmp_orderbyvals(const Datum *adist, const bool *anulls,+ const Datum *bdist, const bool *bnulls,+ IndexScanState *node)+{+ int i;+ int result;++ for (i = 0; i < node->iss_NumOrderByKeys; i++)+ {+ SortSupport ssup = &node->iss_SortSupport[i];++ /* Handle nulls. We only support NULLS LAST. */+ if (anulls[i] && !bnulls[i])+ return 1;+ else if (!anulls[i] && bnulls[i])+ return -1;+ else if (anulls[i] && bnulls[i])+ return 0;++ result = ssup->comparator(adist[i], bdist[i], ssup);+ if (result != 0)+ return result;+ }++ return 0;+}++/*+ * Pairing heap provides getting topmost (greatest) element while KNN provides+ * ascending sort. That's why we inverse the sort order.+ */+static int+reorderbuffer_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)+{+ ReorderTuple *rta = (ReorderTuple *) a;+ ReorderTuple *rtb = (ReorderTuple *) b;+ IndexScanState *node = (IndexScanState *) arg;++ return -cmp_orderbyvals(rta->orderbyvals, rta->orderbynulls,+ rtb->orderbyvals, rtb->orderbynulls,+ node);+}++static void+copyOrderByVals(IndexScanState *node,+ const Datum *src_datums, const bool *src_nulls,+ Datum *dst_datums, bool *dst_nulls)+{+ int i;++ for (i = 0; i < node->iss_NumOrderByKeys; i++)+ {+ if (!src_nulls[i])+ dst_datums[i] = datumCopy(src_datums[i],+ node->iss_OrderByTypByVals[i],+ node->iss_OrderByTypLens[i]);+ else+ dst_datums[i] = (Datum) 0;+ dst_nulls[i] = src_nulls[i];+ }+}
static TupleTableSlot *IndexNext(IndexScanState *node);
+static TupleTableSlot *IndexNextWithReorder(IndexScanState *node);+static void EvalOrderByExpressions(IndexScanState *node, ExprContext *econtext);
/* ----------------------------------------------------------------
@@ -110,10 +189,221 @@ IndexNext(IndexScanState *node)
* if we get here it means the index scan failed so we are at the end of
* the scan..
*/
+ node->iss_ReachedEnd = true;+ return ExecClearTuple(slot);+}++/* ----------------------------------------------------------------+ * IndexNextWithReorder+ *+ * Like IndexNext, but his version can also re-check any+ * ORDER BY expressions, and reorder the tuples as necessary.+ * ----------------------------------------------------------------+ */+static TupleTableSlot *+IndexNextWithReorder(IndexScanState *node)+{+ EState *estate;+ ExprContext *econtext;+ IndexScanDesc scandesc;+ HeapTuple tuple;+ TupleTableSlot *slot;+ MemoryContext oldContext;+ ReorderTuple *topmost = NULL;+ ReorderTuple *queued;+ bool was_exact;+ Datum *lastfetched_vals;+ bool *lastfetched_nulls;+ int cmp;++ estate = node->ss.ps.state;+ /* only forward scan is supported with reordering. */+ Assert (!ScanDirectionIsBackward(((IndexScan *) node->ss.ps.plan)->indexorderdir));+ Assert (ScanDirectionIsForward(estate->es_direction));+ scandesc = node->iss_ScanDesc;+ econtext = node->ss.ps.ps_ExprContext;+ slot = node->ss.ss_ScanTupleSlot;++ for (;;)+ {+ /*+ * Check the reorder queue first. If the topmost tuple in the queue+ * has an ORDER BY value smaller than (or equal to) the value last+ * returned by the index, we can return it now.+ */+ if (!pairingheap_is_empty(node->iss_ReorderQueue))+ {+ topmost = (ReorderTuple *) pairingheap_first(node->iss_ReorderQueue);++ if (node->iss_ReachedEnd ||+ cmp_orderbyvals(topmost->orderbyvals,+ topmost->orderbynulls,+ scandesc->xs_orderbyvals,+ scandesc->xs_orderbynulls,+ node) <= 0)+ {+ (void) pairingheap_remove_first(node->iss_ReorderQueue);++ tuple = topmost->htup;+ pfree(topmost->orderbyvals);+ pfree(topmost->orderbynulls);+ pfree(topmost);++ /* Pass 'true', as the tuple in the queue is a palloc'd copy */+ ExecStoreTuple(tuple, slot, InvalidBuffer, true);+ return slot;+ }+ }+ else if (node->iss_ReachedEnd)+ {+ /* Queue is empty, and no more tuples from index. We're done. */+ return ExecClearTuple(slot);+ }++ /*+ * Fetch next tuple from the index.+ */+ next_indextuple:+ tuple = index_getnext(scandesc, ForwardScanDirection);+ if (!tuple)+ {+ /*+ * No more tuples from the index. But we still need to drain any+ * remaining tuples from the queue before we're done.+ */+ node->iss_ReachedEnd = true;+ continue;+ }++ /*+ * Store the scanned tuple in the scan tuple slot of the scan state.+ * Note: we pass 'false' because tuples returned by amgetnext are+ * pointers onto disk pages and must not be pfree()'d.+ */+ ExecStoreTuple(tuple, /* tuple to store */+ slot, /* slot to store in */+ scandesc->xs_cbuf, /* buffer containing tuple */+ false); /* don't pfree */++ /*+ * If the index was lossy, we have to recheck the index quals and+ * ORDER BY expressions using the fetched tuple.+ */+ if (scandesc->xs_recheck)+ {+ econtext->ecxt_scantuple = slot;+ ResetExprContext(econtext);+ if (!ExecQual(node->indexqualorig, econtext, false))+ {+ /* Fails recheck, so drop it and loop back for another */+ InstrCountFiltered2(node, 1);+ goto next_indextuple;+ }++ EvalOrderByExpressions(node, econtext);++ /*+ * Was the ORDER BY value returned by the index accurate? The+ * recheck flag means that the index can return inaccurate+ * values, but then again, the value returned for any particular+ * tuple could also be exactly correct. Compare the value returned+ * by the index with the recalculated value. (If the value happened+ * to be accurate, we can often avoid pushing the tuple to the+ * queue, just to pop it back out again.)+ */+ cmp = cmp_orderbyvals(node->iss_OrderByValues,+ node->iss_OrderByNulls,+ scandesc->xs_orderbyvals,+ scandesc->xs_orderbynulls,+ node);+ if (cmp < 0)+ elog(ERROR, "index returned tuples in wrong order");+ else if (cmp == 0)+ was_exact = true;+ else+ was_exact = false;+ lastfetched_vals = node->iss_OrderByValues;+ lastfetched_nulls = node->iss_OrderByNulls;+ }+ else+ {+ was_exact = true;+ lastfetched_vals = scandesc->xs_orderbyvals;+ lastfetched_nulls = scandesc->xs_orderbynulls;+ }++ /*+ * Can we return this tuple immediately, or does it need to be pushed+ * to the reorder queue? If the ORDER BY expression values returned+ * by the index were inaccurate, we can't return it yet, because the+ * next tuple from the index might need to come before this one. Also,+ * we can't return it yet if there are any smaller tuples in the+ * queue already.+ */+ if (!was_exact || (topmost && cmp_orderbyvals(lastfetched_vals,+ lastfetched_nulls,+ topmost->orderbyvals,+ topmost->orderbynulls,+ node) > 0))+ {+ /* Put this to the queue */+ oldContext = MemoryContextSwitchTo(estate->es_query_cxt);+ queued = (ReorderTuple *) palloc(sizeof(ReorderTuple));+ queued->htup = heap_copytuple(tuple);+ queued->orderbyvals =+ (Datum *) palloc(sizeof(Datum) * scandesc->numberOfOrderBys);+ queued->orderbynulls =+ (bool *) palloc(sizeof(bool) * scandesc->numberOfOrderBys);+ copyOrderByVals(node, lastfetched_vals, lastfetched_nulls,+ queued->orderbyvals, queued->orderbynulls);+ pairingheap_add(node->iss_ReorderQueue, &queued->ph_node);++ MemoryContextSwitchTo(oldContext);++ continue;+ }+ else+ {+ /* Can return this tuple immediately. */+ return slot;+ }+ }++ /*+ * if we get here it means the index scan failed so we are at the end of+ * the scan..+ */
return ExecClearTuple(slot);
}
/*
+ * Calculate the expressions in the ORDER BY clause, based on the heap tuple.+ */+static void+EvalOrderByExpressions(IndexScanState *node, ExprContext *econtext)+{+ int i;+ ListCell *l;+ MemoryContext oldContext;++ oldContext = MemoryContextSwitchTo(econtext->ecxt_per_tuple_memory);++ i = 0;+ foreach(l, node->indexorderbyorig)+ {+ ExprState *orderby = (ExprState *) lfirst(l);++ node->iss_OrderByValues[i] = ExecEvalExpr(orderby,+ econtext,+ &node->iss_OrderByNulls[i],+ NULL);+ i++;+ }++ MemoryContextSwitchTo(oldContext);+}++/*
* IndexRecheck -- access method routine to recheck a tuple in EvalPlanQual
*/
static bool
@@ -147,9 +437,14 @@ ExecIndexScan(IndexScanState *node)
if (node->iss_NumRuntimeKeys != 0 && !node->iss_RuntimeKeysReady)
ExecReScan((PlanState *) node);
- return ExecScan(&node->ss,- (ExecScanAccessMtd) IndexNext,- (ExecScanRecheckMtd) IndexRecheck);+ if (node->iss_NumOrderByKeys > 0)+ return ExecScan(&node->ss,+ (ExecScanAccessMtd) IndexNextWithReorder,+ (ExecScanRecheckMtd) IndexRecheck);+ else+ return ExecScan(&node->ss,+ (ExecScanAccessMtd) IndexNext,+ (ExecScanRecheckMtd) IndexRecheck);
}
/* ----------------------------------------------------------------
@@ -465,6 +760,7 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
IndexScanState *indexstate;
Relation currentRelation;
bool relistarget;
+ int i;
/*
* create state structure
@@ -501,6 +797,9 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
indexstate->indexqualorig = (List *)
ExecInitExpr((Expr *) node->indexqualorig,
(PlanState *) indexstate);
+ indexstate->indexorderbyorig = (List *)+ ExecInitExpr((Expr *) node->indexorderbyorig,+ (PlanState *) indexstate);
/*
* tuple table initialization
@@ -581,6 +880,52 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
NULL, /* no ArrayKeys */
NULL);
+ /* Initialize sort support, if we need to re-check ORDER BY exprs */+ if (indexstate->iss_NumOrderByKeys > 0)+ {+ int numOrderByKeys = indexstate->iss_NumOrderByKeys;++ /*+ * Prepare sort support, and look up the distance type for each+ * ORDER BY expression.+ */+ indexstate->iss_SortSupport =+ palloc0(numOrderByKeys * sizeof(SortSupportData));+ indexstate->iss_OrderByTypByVals =+ palloc(numOrderByKeys * sizeof(bool));+ indexstate->iss_OrderByTypLens =+ palloc(numOrderByKeys * sizeof(int16));+ for (i = 0; i < indexstate->iss_NumOrderByKeys; i++)+ {+ Oid orderbyType;+ Oid opfamily;+ int16 strategy;++ PrepareSortSupportFromOrderingOp(node->indexorderbyops[i],+ &indexstate->iss_SortSupport[i]);++ if (!get_ordering_op_properties(node->indexorderbyops[i],+ &opfamily, &orderbyType, &strategy))+ {+ elog(LOG, "operator %u is not a valid ordering operator",+ node->indexorderbyops[i]);+ }+ get_typlenbyval(orderbyType,+ &indexstate->iss_OrderByTypLens[i],+ &indexstate->iss_OrderByTypByVals[i]);+ }++ /* allocate arrays to hold the re-calculated distances */+ indexstate->iss_OrderByValues =+ palloc(indexstate->iss_NumOrderByKeys * sizeof(Datum));+ indexstate->iss_OrderByNulls =+ palloc(indexstate->iss_NumOrderByKeys * sizeof(bool));++ /* and initialize the reorder queue */+ indexstate->iss_ReorderQueue = pairingheap_allocate(reorderbuffer_cmp,+ indexstate);+ }+
/*
* If we have runtime keys, we need an ExprContext to evaluate them. The
* node's standard context won't do because we want to reset that context
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.cindex c809237..6403a7b 100644--- a/src/backend/optimizer/plan/createplan.c+++ b/src/backend/optimizer/plan/createplan.c@@ -22,6 +22,7 @@
#include "access/skey.h"
#include "access/sysattr.h"
#include "catalog/pg_class.h"
+#include "catalog/pg_operator.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
@@ -102,7 +103,7 @@ static void copy_plan_costsize(Plan *dest, Plan *src);
static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
Oid indexid, List *indexqual, List *indexqualorig,
- List *indexorderby, List *indexorderbyorig,+ List *indexorderby, List *indexorderbyorig, Oid *indexorderbyops,
ScanDirection indexscandir);
static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
Index scanrelid, Oid indexid,
@@ -167,8 +168,8 @@ static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
Oid **p_sortOperators,
Oid **p_collations,
bool **p_nullsFirst);
-static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,- TargetEntry *tle,+static EquivalenceMember *find_ec_member_for_expr(EquivalenceClass *ec,+ Expr *tlexpr,
Relids relids);
static Material *make_material(Plan *lefttree);
@@ -1158,6 +1159,7 @@ create_indexscan_plan(PlannerInfo *root,
List *stripped_indexquals;
List *fixed_indexquals;
List *fixed_indexorderbys;
+ Oid *indexorderbyops = NULL;
ListCell *l;
/* it should be a base rel... */
@@ -1269,6 +1271,42 @@ create_indexscan_plan(PlannerInfo *root,
replace_nestloop_params(root, (Node *) indexorderbys);
}
+ if (best_path->path.pathkeys && indexorderbys)+ {+ int numOrderBys = list_length(indexorderbys);+ int i;+ ListCell *pathkeyCell,+ *exprCell;+ PathKey *pathkey;+ Expr *expr;+ EquivalenceMember *em;++ indexorderbyops = (Oid *) palloc(numOrderBys * sizeof(Oid));++ /*+ * Get ordering operator for each pathkey. Pathkey contains pointer+ * to equivalence class. But it's not enough because we need the+ * expression datatype to lookup opfamily member. That's why we've+ * to dig and equivalence member.+ */+ i = 0;+ forboth (pathkeyCell, best_path->path.pathkeys, exprCell, indexorderbys)+ {+ pathkey = (PathKey *) lfirst(pathkeyCell);+ expr = (Expr *) lfirst(exprCell);++ /* Find equivalence member for the order by expression */+ em = find_ec_member_for_expr(pathkey->pk_eclass, expr, NULL);++ /* Get sort operator from opfamily */+ indexorderbyops[i] = get_opfamily_member(pathkey->pk_opfamily,+ em->em_datatype,+ em->em_datatype,+ pathkey->pk_strategy);+ i++;+ }+ }+
/* Finally ready to build the plan node */
if (indexonly)
scan_plan = (Scan *) make_indexonlyscan(tlist,
@@ -1288,6 +1326,7 @@ create_indexscan_plan(PlannerInfo *root,
stripped_indexquals,
fixed_indexorderbys,
indexorderbys,
+ indexorderbyops,
best_path->indexscandir);
copy_path_costsize(&scan_plan->plan, &best_path->path);
@@ -3344,6 +3383,7 @@ make_indexscan(List *qptlist,
List *indexqualorig,
List *indexorderby,
List *indexorderbyorig,
+ Oid *indexorderbyops,
ScanDirection indexscandir)
{
IndexScan *node = makeNode(IndexScan);
@@ -3360,6 +3400,7 @@ make_indexscan(List *qptlist,
node->indexqualorig = indexqualorig;
node->indexorderby = indexorderby;
node->indexorderbyorig = indexorderbyorig;
+ node->indexorderbyops = indexorderbyops;
node->indexorderdir = indexscandir;
return node;
@@ -3990,7 +4031,7 @@ prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
if (tle)
{
- em = find_ec_member_for_tle(ec, tle, relids);+ em = find_ec_member_for_expr(ec, tle->expr, relids);
if (em)
{
/* found expr at right place in tlist */
@@ -4021,7 +4062,7 @@ prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
foreach(j, tlist)
{
tle = (TargetEntry *) lfirst(j);
- em = find_ec_member_for_tle(ec, tle, relids);+ em = find_ec_member_for_expr(ec, tle->expr, relids);
if (em)
{
/* found expr already in tlist */
@@ -4142,23 +4183,21 @@ prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
}
/*
- * find_ec_member_for_tle- * Locate an EquivalenceClass member matching the given TLE, if any+ * find_ec_member_for_expr+ * Locate an EquivalenceClass member matching the given expression, if any
*
* Child EC members are ignored unless they match 'relids'.
*/
static EquivalenceMember *
-find_ec_member_for_tle(EquivalenceClass *ec,- TargetEntry *tle,- Relids relids)+find_ec_member_for_expr(EquivalenceClass *ec,+ Expr *expr,+ Relids relids)
{
- Expr *tlexpr;
ListCell *lc;
/* We ignore binary-compatible relabeling on both ends */
- tlexpr = tle->expr;- while (tlexpr && IsA(tlexpr, RelabelType))- tlexpr = ((RelabelType *) tlexpr)->arg;+ while (expr && IsA(expr, RelabelType))+ expr = ((RelabelType *) expr)->arg;
foreach(lc, ec->ec_members)
{
@@ -4184,7 +4223,7 @@ find_ec_member_for_tle(EquivalenceClass *ec,
while (emexpr && IsA(emexpr, RelabelType))
emexpr = ((RelabelType *) emexpr)->arg;
- if (equal(emexpr, tlexpr))+ if (equal(emexpr, expr))
return em;
}
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.cindex 39a7855..a3af08a 100644--- a/src/backend/utils/adt/geo_ops.c+++ b/src/backend/utils/adt/geo_ops.c@@ -2657,6 +2657,18 @@ dist_ppoly(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8(result);
}
+Datum+dist_polyp(PG_FUNCTION_ARGS)+{+ POLYGON *poly = PG_GETARG_POLYGON_P(0);+ Point *point = PG_GETARG_POINT_P(1);+ float8 result;++ result = dist_ppoly_internal(point, poly);++ PG_RETURN_FLOAT8(result);+}+
static double
dist_ppoly_internal(Point *pt, POLYGON *poly)
{
@@ -5112,6 +5124,21 @@ dist_pc(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8(result);
}
+/*+ * Distance from a circle to a point+ */+Datum+dist_cpoint(PG_FUNCTION_ARGS)+{+ CIRCLE *circle = PG_GETARG_CIRCLE_P(0);+ Point *point = PG_GETARG_POINT_P(1);+ float8 result;++ result = point_dt(point, &circle->center) - circle->radius;+ if (result < 0)+ result = 0;+ PG_RETURN_FLOAT8(result);+}
/* circle_center - returns the center point of the circle.
*/
diff --git a/src/include/access/genam.h b/src/include/access/genam.hindex d86590a..f129c4b 100644--- a/src/include/access/genam.h+++ b/src/include/access/genam.h@@ -147,7 +147,10 @@ extern void index_restrpos(IndexScanDesc scan);
extern ItemPointer index_getnext_tid(IndexScanDesc scan,
ScanDirection direction);
extern HeapTuple index_fetch_heap(IndexScanDesc scan);
+extern bool index_get_heap_values(IndexScanDesc scan, ItemPointer heapPtr,+ Datum values[INDEX_MAX_KEYS], bool isnull[INDEX_MAX_KEYS]);
extern HeapTuple index_getnext(IndexScanDesc scan, ScanDirection direction);
+
extern int64 index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap);
extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info,
diff --git a/src/include/access/relscan.h b/src/include/access/relscan.hindex 9bb6362..7ee0206 100644--- a/src/include/access/relscan.h+++ b/src/include/access/relscan.h@@ -91,6 +91,15 @@ typedef struct IndexScanDescData
/* NB: if xs_cbuf is not InvalidBuffer, we hold a pin on that buffer */
bool xs_recheck; /* T means scan keys must be rechecked */
+ /*+ * If fetching with an ordering operator, the values of the ORDER BY+ * expression of the last returned heap tuple according to the index. If+ * xs_recheck is true, this needs to be rechecked just like the scan keys,+ * and the value returned here is a lower-bound on the actual value.+ */+ Datum *xs_orderbyvals;+ bool *xs_orderbynulls;+
/* state data for traversing HOT chains in index_getnext */
bool xs_continue_hot; /* T if must keep walking HOT chain */
} IndexScanDescData;
diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.hindex a350832..b6a6da9 100644--- a/src/include/catalog/catversion.h+++ b/src/include/catalog/catversion.h@@ -53,6 +53,6 @@
*/
/* yyyymmddN */
-#define CATALOG_VERSION_NO 201505121+#define CATALOG_VERSION_NO 201505151
#endif
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.hindex 5aab896..ed44e05 100644--- a/src/include/catalog/pg_amop.h+++ b/src/include/catalog/pg_amop.h@@ -650,6 +650,7 @@ DATA(insert ( 2594 604 604 11 s 2577 783 0 ));
DATA(insert ( 2594 604 604 12 s 2576 783 0 ));
DATA(insert ( 2594 604 604 13 s 2861 783 0 ));
DATA(insert ( 2594 604 604 14 s 2860 783 0 ));
+DATA(insert ( 2594 604 600 15 o 4588 783 1970 ));
/*
* gist circle_ops
@@ -669,6 +670,7 @@ DATA(insert ( 2595 718 718 11 s 1514 783 0 ));
DATA(insert ( 2595 718 718 12 s 2590 783 0 ));
DATA(insert ( 2595 718 718 13 s 2865 783 0 ));
DATA(insert ( 2595 718 718 14 s 2864 783 0 ));
+DATA(insert ( 2595 718 600 15 o 4586 783 1970 ));
/*
* gin array_ops (these anyarray operators are used with all the opclasses
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.hindex e3de3b5..2aca30c 100644--- a/src/include/catalog/pg_amproc.h+++ b/src/include/catalog/pg_amproc.h@@ -208,6 +208,7 @@ DATA(insert ( 2594 604 604 4 2580 ));
DATA(insert ( 2594 604 604 5 2581 ));
DATA(insert ( 2594 604 604 6 2582 ));
DATA(insert ( 2594 604 604 7 2584 ));
+DATA(insert ( 2594 604 604 8 4589 ));
DATA(insert ( 2595 718 718 1 2591 ));
DATA(insert ( 2595 718 718 2 2583 ));
DATA(insert ( 2595 718 718 3 2592 ));
@@ -215,6 +216,7 @@ DATA(insert ( 2595 718 718 4 2580 ));
DATA(insert ( 2595 718 718 5 2581 ));
DATA(insert ( 2595 718 718 6 2582 ));
DATA(insert ( 2595 718 718 7 2584 ));
+DATA(insert ( 2595 718 718 8 4589 ));
DATA(insert ( 3655 3614 3614 1 3654 ));
DATA(insert ( 3655 3614 3614 2 3651 ));
DATA(insert ( 3655 3614 3614 3 3648 ));
diff --git a/src/include/catalog/pg_operator.h b/src/include/catalog/pg_operator.hindex 34ebb50..8f08543 100644--- a/src/include/catalog/pg_operator.h+++ b/src/include/catalog/pg_operator.h@@ -1015,9 +1015,13 @@ DATA(insert OID = 1520 ( "<->" PGNSP PGUID b f f 718 718 701 1520 0 ci
DESCR("distance between");
DATA(insert OID = 1521 ( "#" PGNSP PGUID l f f 0 604 23 0 0 poly_npoints - - ));
DESCR("number of points");
-DATA(insert OID = 1522 ( "<->" PGNSP PGUID b f f 600 718 701 0 0 dist_pc - - ));+DATA(insert OID = 1522 ( "<->" PGNSP PGUID b f f 600 718 701 4586 0 dist_pc - - ));
DESCR("distance between");
-DATA(insert OID = 3276 ( "<->" PGNSP PGUID b f f 600 604 701 0 0 dist_ppoly - - ));+DATA(insert OID = 4586 ( "<->" PGNSP PGUID b f f 718 600 701 1522 0 dist_cpoint - - ));+DESCR("distance between");+DATA(insert OID = 3276 ( "<->" PGNSP PGUID b f f 600 604 701 4588 0 dist_ppoly - - ));+DESCR("distance between");+DATA(insert OID = 4588 ( "<->" PGNSP PGUID b f f 604 600 701 3276 0 dist_polyp - - ));
DESCR("distance between");
DATA(insert OID = 1523 ( "<->" PGNSP PGUID b f f 718 604 701 0 0 dist_cpoly - - ));
DESCR("distance between");
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.hindex a1e2442..f0a8cd7 100644--- a/src/include/catalog/pg_proc.h+++ b/src/include/catalog/pg_proc.h@@ -856,6 +856,8 @@ DATA(insert OID = 727 ( dist_sl PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 70
DATA(insert OID = 728 ( dist_cpoly PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 701 "718 604" _null_ _null_ _null_ _null_ _null_ dist_cpoly _null_ _null_ _null_ ));
DATA(insert OID = 729 ( poly_distance PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 701 "604 604" _null_ _null_ _null_ _null_ _null_ poly_distance _null_ _null_ _null_ ));
DATA(insert OID = 3275 ( dist_ppoly PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 701 "600 604" _null_ _null_ _null_ _null_ _null_ dist_ppoly _null_ _null_ _null_ ));
+DATA(insert OID = 4587 ( dist_polyp PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 701 "604 600" _null_ _null_ _null_ _null_ _null_ dist_polyp _null_ _null_ _null_ ));+DATA(insert OID = 4585 ( dist_cpoint PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 701 "718 600" _null_ _null_ _null_ _null_ _null_ dist_cpoint _null_ _null_ _null_ ));
DATA(insert OID = 740 ( text_lt PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "25 25" _null_ _null_ _null_ _null_ _null_ text_lt _null_ _null_ _null_ ));
DATA(insert OID = 741 ( text_le PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "25 25" _null_ _null_ _null_ _null_ _null_ text_le _null_ _null_ _null_ ));
@@ -4165,6 +4167,8 @@ DATA(insert OID = 2179 ( gist_point_consistent PGNSP PGUID 12 1 0 0 0 f f f f t
DESCR("GiST support");
DATA(insert OID = 3064 ( gist_point_distance PGNSP PGUID 12 1 0 0 0 f f f f t f i 4 0 701 "2281 600 23 26" _null_ _null_ _null_ _null_ _null_ gist_point_distance _null_ _null_ _null_ ));
DESCR("GiST support");
+DATA(insert OID = 4589 ( gist_bbox_distance PGNSP PGUID 12 1 0 0 0 f f f f t f i 4 0 701 "2281 600 23 26" _null_ _null_ _null_ _null_ _null_ gist_bbox_distance _null_ _null_ _null_ ));+DESCR("GiST support");
/* GIN */
DATA(insert OID = 2731 ( gingetbitmap PGNSP PGUID 12 1 0 0 0 f f f f t f v 2 0 20 "2281 2281" _null_ _null_ _null_ _null_ _null_ gingetbitmap _null_ _null_ _null_ ));
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.hindex 5ad2cc2..95e8a7f 100644--- a/src/include/nodes/execnodes.h+++ b/src/include/nodes/execnodes.h@@ -17,6 +17,7 @@
#include "access/genam.h"
#include "access/heapam.h"
#include "executor/instrument.h"
+#include "lib/pairingheap.h"
#include "nodes/params.h"
#include "nodes/plannodes.h"
#include "utils/reltrigger.h"
@@ -1262,6 +1263,7 @@ typedef struct
* IndexScanState information
*
* indexqualorig execution state for indexqualorig expressions
+ * indexorderbyorig execution state for indexorderbyorig expressions
* ScanKeys Skey structures for index quals
* NumScanKeys number of ScanKeys
* OrderByKeys Skey structures for index ordering operators
@@ -1272,12 +1274,20 @@ typedef struct
* RuntimeContext expr context for evaling runtime Skeys
* RelationDesc index relation descriptor
* ScanDesc index scan descriptor
+ *+ * ReorderQueue tuples that need reordering due to re-check+ * ReachedEnd have we fetched all tuples from index already?+ * OrderByValues values of ORDER BY exprs of last fetched tuple+ * SortSupport for reordering ORDER BY exprs+ * OrderByTypByVals is the datatype of order by expression pass-by-value?+ * OrderByTypLens typlens of the datatypes of order by expressions
* ----------------
*/
typedef struct IndexScanState
{
ScanState ss; /* its first field is NodeTag */
List *indexqualorig;
+ List *indexorderbyorig;
ScanKey iss_ScanKeys;
int iss_NumScanKeys;
ScanKey iss_OrderByKeys;
@@ -1288,6 +1298,15 @@ typedef struct IndexScanState
ExprContext *iss_RuntimeContext;
Relation iss_RelationDesc;
IndexScanDesc iss_ScanDesc;
++ /* These are needed for re-checking ORDER BY expr ordering */+ pairingheap *iss_ReorderQueue;+ bool iss_ReachedEnd;+ Datum *iss_OrderByValues;+ bool *iss_OrderByNulls;+ SortSupport iss_SortSupport;+ bool *iss_OrderByTypByVals;+ int16 *iss_OrderByTypLens;
} IndexScanState;
/* ----------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.hindex 1494b33..9c02e20 100644--- a/src/include/nodes/plannodes.h+++ b/src/include/nodes/plannodes.h@@ -311,8 +311,13 @@ typedef Scan SeqScan;
* index column order. Only the expressions are provided, not the auxiliary
* sort-order information from the ORDER BY SortGroupClauses; it's assumed
* that the sort ordering is fully determinable from the top-level operators.
- * indexorderbyorig is unused at run time, but is needed for EXPLAIN.- * (Note these fields are used for amcanorderbyop cases, not amcanorder cases.)+ * indexorderbyorig is used at runtime to recheck the ordering, if the index+ * cannot calculate an accurate ordering. It is also needed for EXPLAIN.+ *+ * indexorderbyops is an array of operators used to sort the ORDER BY+ * expressions, used together with indexorderbyorig to recheck ordering at run+ * time. (Note these fields are used for amcanorderbyop cases, not amcanorder+ * cases.)
*
* indexorderdir specifies the scan ordering, for indexscans on amcanorder
* indexes (for other indexes it should be "don't care").
@@ -325,7 +330,8 @@ typedef struct IndexScan
List *indexqual; /* list of index quals (usually OpExprs) */
List *indexqualorig; /* the same in original form */
List *indexorderby; /* list of index ORDER BY exprs */
- List *indexorderbyorig; /* the same in original form */+ List *indexorderbyorig; /* the same in original form */+ Oid *indexorderbyops; /* operators to sort ORDER BY exprs */
ScanDirection indexorderdir; /* forward or backward or don't care */
} IndexScan;
diff --git a/src/include/utils/geo_decls.h b/src/include/utils/geo_decls.hindex 4377baa..2311d35 100644--- a/src/include/utils/geo_decls.h+++ b/src/include/utils/geo_decls.h@@ -394,8 +394,10 @@ extern Datum circle_diameter(PG_FUNCTION_ARGS);
extern Datum circle_radius(PG_FUNCTION_ARGS);
extern Datum circle_distance(PG_FUNCTION_ARGS);
extern Datum dist_pc(PG_FUNCTION_ARGS);
+extern Datum dist_cpoint(PG_FUNCTION_ARGS);
extern Datum dist_cpoly(PG_FUNCTION_ARGS);
extern Datum dist_ppoly(PG_FUNCTION_ARGS);
+extern Datum dist_polyp(PG_FUNCTION_ARGS);
extern Datum circle_center(PG_FUNCTION_ARGS);
extern Datum cr_circle(PG_FUNCTION_ARGS);
extern Datum box_circle(PG_FUNCTION_ARGS);
@@ -420,6 +422,7 @@ extern Datum gist_circle_consistent(PG_FUNCTION_ARGS);
extern Datum gist_point_compress(PG_FUNCTION_ARGS);
extern Datum gist_point_consistent(PG_FUNCTION_ARGS);
extern Datum gist_point_distance(PG_FUNCTION_ARGS);
+extern Datum gist_bbox_distance(PG_FUNCTION_ARGS);
extern Datum gist_point_fetch(PG_FUNCTION_ARGS);
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.outindex abe64e5..a95fe29 100644--- a/src/test/regress/expected/create_index.out+++ b/src/test/regress/expected/create_index.out@@ -372,6 +372,36 @@ SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth
48
(1 row)
+SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;+ f1 +-------------------------------------------------+ ((240,359),(240,455),(337,455),(337,359))+ ((662,163),(662,187),(759,187),(759,163))+ ((1000,0),(0,1000))+ ((0,1000),(1000,1000))+ ((1346,344),(1346,403),(1444,403),(1444,344))+ ((278,1409),(278,1457),(369,1457),(369,1409))+ ((907,1156),(907,1201),(948,1201),(948,1156))+ ((1517,971),(1517,1043),(1594,1043),(1594,971))+ ((175,1820),(175,1850),(259,1850),(259,1820))+ ((2424,81),(2424,160),(2424,160),(2424,81))+(10 rows)++SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+ f1 +-----------------------------------+ <(288.5,407),68.2367203197809>+ <(710.5,175),49.9624859269432>+ <(323.5,1433),51.4417145903983>+ <(927.5,1178.5),30.4384625104489>+ <(1395,373.5),57.1948424248201>+ <(1555.5,1007),52.7091073724456>+ <(217,1835),44.5982062419555>+ <(489,2421.5),22.3886131772381>+ <(2424,120.5),39.5>+ <(751.5,2655),20.4022057631032>+(10 rows)+
-- Now check the results from plain indexscan
SET enable_seqscan = OFF;
SET enable_indexscan = ON;
@@ -1152,6 +1182,54 @@ SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth
48
(1 row)
+EXPLAIN (COSTS OFF)+SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;+ QUERY PLAN +-----------------------------------------------------+ Limit+ -> Index Scan using ggpolygonind on gpolygon_tbl+ Order By: (f1 <-> '(0,0)'::point)+(3 rows)++SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;+ f1 +-------------------------------------------------+ ((240,359),(240,455),(337,455),(337,359))+ ((662,163),(662,187),(759,187),(759,163))+ ((1000,0),(0,1000))+ ((0,1000),(1000,1000))+ ((1346,344),(1346,403),(1444,403),(1444,344))+ ((278,1409),(278,1457),(369,1457),(369,1409))+ ((907,1156),(907,1201),(948,1201),(948,1156))+ ((1517,971),(1517,1043),(1594,1043),(1594,971))+ ((175,1820),(175,1850),(259,1850),(259,1820))+ ((2424,81),(2424,160),(2424,160),(2424,81))+(10 rows)++EXPLAIN (COSTS OFF)+SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+ QUERY PLAN +---------------------------------------------------+ Limit+ -> Index Scan using ggcircleind on gcircle_tbl+ Order By: (f1 <-> '(200,300)'::point)+(3 rows)++SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+ f1 +-----------------------------------+ <(288.5,407),68.2367203197809>+ <(710.5,175),49.9624859269432>+ <(323.5,1433),51.4417145903983>+ <(927.5,1178.5),30.4384625104489>+ <(1395,373.5),57.1948424248201>+ <(1555.5,1007),52.7091073724456>+ <(217,1835),44.5982062419555>+ <(489,2421.5),22.3886131772381>+ <(2424,120.5),39.5>+ <(751.5,2655),20.4022057631032>+(10 rows)+
-- Now check the results from bitmap indexscan
SET enable_seqscan = OFF;
SET enable_indexscan = OFF;
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sqlindex f779fa0..5df9008 100644--- a/src/test/regress/sql/create_index.sql+++ b/src/test/regress/sql/create_index.sql@@ -224,6 +224,10 @@ SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth
SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
+SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;++SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+
-- Now check the results from plain indexscan
SET enable_seqscan = OFF;
SET enable_indexscan = ON;
@@ -437,6 +441,14 @@ EXPLAIN (COSTS OFF)
SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
+EXPLAIN (COSTS OFF)+SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;+SELECT * FROM gpolygon_tbl ORDER BY f1 <-> '(0,0)'::point LIMIT 10;++EXPLAIN (COSTS OFF)+SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+SELECT * FROM gcircle_tbl ORDER BY f1 <-> '(200,300)'::point LIMIT 10;+
-- Now check the results from bitmap indexscan
SET enable_seqscan = OFF;
SET enable_indexscan = OFF;
--
2.1.4
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: hlinnaka@iki.fi, aekorotkov@gmail.com, tomas.vondra@2ndquadrant.com
Subject: Re: KNN-GiST with recheck
In-Reply-To: <55552FFD.8030808@iki.fi>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox