diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml index 14a1aa5..0ad4f73 100644 --- a/doc/src/sgml/indices.sgml +++ b/doc/src/sgml/indices.sgml @@ -282,6 +282,14 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10; + If used with an ordering operator, SP-GiST indexes + can optimize nearest-neighbor search. + For SP-GiST operator classes that support distance ordering, the + corresponding operator is specified in the Ordering Operators + column in . + + + index GIN diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml index 1816fdf..5358bbb 100644 --- a/doc/src/sgml/spgist.sgml +++ b/doc/src/sgml/spgist.sgml @@ -630,7 +630,9 @@ CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ... typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ + ScanKey orderbyKeys; /* array of ordering operators and comparison values */ int nkeys; /* length of array */ + int norderbys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ @@ -653,6 +655,7 @@ typedef struct spgInnerConsistentOut int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ void **traversalValues; /* opclass-specific traverse values */ + double **distances; /* associated distances */ } spgInnerConsistentOut; @@ -667,6 +670,8 @@ typedef struct spgInnerConsistentOut In particular it is not necessary to check sk_flags to see if the comparison value is NULL, because the SP-GiST core code will filter out such conditions. + orderbyKeys, of length norderbys, + describes ordering operators (if any) in the same fashion. reconstructedValue is the value reconstructed for the parent tuple; it is (Datum) 0 at the root level or if the inner_consistent function did not provide a value at the @@ -709,6 +714,11 @@ typedef struct spgInnerConsistentOut of spgConfigOut.leafType type reconstructed for each child node to be visited; otherwise, leave reconstructedValues as NULL. + distances> if the ordered search is carried out, + the implementation is supposed to fill them in accordance to the + ordering operators provided in orderbyKeys> + (nodes with lowest distances will be processed first). Leave it + NULL otherwise. If it is desired to pass down additional out-of-band information (traverse values) to lower levels of the tree search, set traversalValues to an array of the appropriate @@ -717,6 +727,7 @@ typedef struct spgInnerConsistentOut Note that the inner_consistent function is responsible for palloc'ing the nodeNumbers, levelAdds, + distances, reconstructedValues, and traversalValues arrays in the current memory context. However, any output traverse values pointed to by @@ -747,7 +758,9 @@ CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ... typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ - int nkeys; /* length of array */ + ScanKey orderbykeys; /* array of ordering operators and comparison values */ + int nkeys; /* length of scankeys array */ + int norderbys; /* length of orderbykeys array */ Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ @@ -759,8 +772,10 @@ typedef struct spgLeafConsistentIn typedef struct spgLeafConsistentOut { - Datum leafValue; /* reconstructed original data, if any */ - bool recheck; /* set true if operator must be rechecked */ + Datum leafValue; /* reconstructed original data, if any */ + bool recheck; /* set true if operator must be rechecked */ + bool recheckDistances; /* set true if distances must be rechecked */ + double *distances; /* associated distances */ } spgLeafConsistentOut; @@ -775,6 +790,8 @@ typedef struct spgLeafConsistentOut In particular it is not necessary to check sk_flags to see if the comparison value is NULL, because the SP-GiST core code will filter out such conditions. + The array orderbykeys, of length norderbys, + describes the ordering operators in the same fashion. reconstructedValue is the value reconstructed for the parent tuple; it is (Datum) 0 at the root level or if the inner_consistent function did not provide a value at the @@ -803,6 +820,13 @@ typedef struct spgLeafConsistentOut recheck may be set to true if the match is uncertain and so the operator(s) must be re-applied to the actual heap tuple to verify the match. + If the ordered search is performed, distances + should be set in accordance with the ordering operator provided, otherwise + implementation is supposed to set it to NULL. + If at least one of returned distances is not exact, the function must set + recheckDistances to true. In this case, the executor + calculates the exact distances after fetching the tuple from the heap, + and reorders the tuples if necessary. diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml index 9f5c0c3..1c459c4 100644 --- a/doc/src/sgml/xindex.sgml +++ b/doc/src/sgml/xindex.sgml @@ -1242,7 +1242,7 @@ SELECT sum(x) OVER (ORDER BY x RANGE BETWEEN 5 PRECEDING AND 10 FOLLOWING) Ordering Operators - Some index access methods (currently, only GiST) support the concept of + Some index access methods (currently, only GiST and SP-GiST) support the concept of ordering operators. What we have been discussing so far are search operators. A search operator is one for which the index can be searched to find all rows satisfying diff --git a/src/backend/access/spgist/README b/src/backend/access/spgist/README index 09ab21a..cb38650 100644 --- a/src/backend/access/spgist/README +++ b/src/backend/access/spgist/README @@ -41,7 +41,12 @@ contain exactly one inner tuple. When the search traversal algorithm reaches an inner tuple, it chooses a set of nodes to continue tree traverse in depth. If it reaches a leaf page it -scans a list of leaf tuples to find the ones that match the query. +scans a list of leaf tuples to find the ones that match the query. SP-GiSTs +also support ordered searches - that is during the scan is performed, +implementation can choose to map floating-point distances to inner and leaf +tuples and the traversal will be performed by the closest-first model. It +can be usefull e.g. for performing nearest-neighbour searches on the dataset. + The insertion algorithm descends the tree similarly, except it must choose just one node to descend to from each inner tuple. Insertion might also have diff --git a/src/backend/access/spgist/spgscan.c b/src/backend/access/spgist/spgscan.c index c728080..880057e 100644 --- a/src/backend/access/spgist/spgscan.c +++ b/src/backend/access/spgist/spgscan.c @@ -15,79 +15,158 @@ #include "postgres.h" +#include + +#include "access/genam.h" #include "access/relscan.h" #include "access/spgist_private.h" #include "miscadmin.h" #include "storage/bufmgr.h" +#include "utils/builtins.h" #include "utils/datum.h" +#include "utils/lsyscache.h" #include "utils/memutils.h" #include "utils/rel.h" - typedef void (*storeRes_func) (SpGistScanOpaque so, ItemPointer heapPtr, - Datum leafValue, bool isnull, bool recheck); + Datum leafValue, bool isNull, bool recheck, + bool recheckDist, double *distances); -typedef struct ScanStackEntry +/* + * Pairing heap comparison function for the SpGistSearchItem queue + */ +static int +pairingheap_SpGistSearchItem_cmp(const pairingheap_node *a, + const pairingheap_node *b, void *arg) { - Datum reconstructedValue; /* value reconstructed from parent */ - void *traversalValue; /* opclass-specific traverse value */ - int level; /* level of items on this page */ - ItemPointerData ptr; /* block and offset to scan from */ -} ScanStackEntry; + const SpGistSearchItem *sa = (const SpGistSearchItem *) a; + const SpGistSearchItem *sb = (const SpGistSearchItem *) b; + IndexScanDesc scan = (IndexScanDesc) arg; + int i; + + if (sa->isNull) + { + if (!sb->isNull) + return -1; + } + else if (sb->isNull) + { + return 1; + } + else + { + /* Order according to distance comparison */ + for (i = 0; i < scan->numberOfOrderBys; i++) + { + if (isnan(sa->distances[i]) && isnan(sb->distances[i])) + continue; /* NaN == NaN */ + if (isnan(sa->distances[i])) + return -1; /* NaN > number */ + if (isnan(sb->distances[i])) + return 1; /* number < NaN */ + if (sa->distances[i] != sb->distances[i]) + return (sa->distances[i] < sb->distances[i]) ? 1 : -1; + } + } + + /* Leaf items go before inner pages, to ensure a depth-first search */ + if (sa->isLeaf && !sb->isLeaf) + return 1; + if (!sa->isLeaf && sb->isLeaf) + return -1; + return 0; +} -/* Free a ScanStackEntry */ static void -freeScanStackEntry(SpGistScanOpaque so, ScanStackEntry *stackEntry) +spgFreeSearchItem(SpGistScanOpaque so, SpGistSearchItem *item) { if (!so->state.attLeafType.attbyval && - DatumGetPointer(stackEntry->reconstructedValue) != NULL) - pfree(DatumGetPointer(stackEntry->reconstructedValue)); - if (stackEntry->traversalValue) - pfree(stackEntry->traversalValue); + DatumGetPointer(item->value) != NULL) + pfree(DatumGetPointer(item->value)); + + if (item->traversalValue) + pfree(item->traversalValue); - pfree(stackEntry); + pfree(item); } -/* Free the entire stack */ +/* + * Add SpGistSearchItem to queue + * + * Called in queue context + */ static void -freeScanStack(SpGistScanOpaque so) +spgAddSearchItemToQueue(SpGistScanOpaque so, SpGistSearchItem *item) { - ListCell *lc; + if (so->queue) + pairingheap_add(so->queue, &item->phNode); + else + so->scanStack = lcons(item, so->scanStack); +} - foreach(lc, so->scanStack) - { - freeScanStackEntry(so, (ScanStackEntry *) lfirst(lc)); - } - list_free(so->scanStack); - so->scanStack = NIL; +static SpGistSearchItem * +spgAllocSearchItem(SpGistScanOpaque so, bool isnull, double *distances) +{ + /* allocate distance array only for non-NULL items */ + SpGistSearchItem *item = + palloc(SizeOfSpGistSearchItem(isnull ? 0 : so->numberOfOrderBys)); + + item->isNull = isnull; + + if (!isnull && so->numberOfOrderBys > 0) + memcpy(item->distances, distances, + so->numberOfOrderBys * sizeof(double)); + + return item; +} + +static void +spgAddStartItem(SpGistScanOpaque so, bool isnull) +{ + SpGistSearchItem *startEntry = + spgAllocSearchItem(so, isnull, so->zeroDistances); + + ItemPointerSet(&startEntry->heapPtr, + isnull ? SPGIST_NULL_BLKNO : SPGIST_ROOT_BLKNO, + FirstOffsetNumber); + startEntry->isLeaf = false; + startEntry->level = 0; + startEntry->value = (Datum) 0; + startEntry->traversalValue = NULL; + startEntry->recheckDist = false; + startEntry->recheckQual = false; + + spgAddSearchItemToQueue(so, startEntry); } /* - * Initialize scanStack to search the root page, resetting + * Initialize queue to search the root page, resetting * any previously active scan */ static void resetSpGistScanOpaque(SpGistScanOpaque so) { - ScanStackEntry *startEntry; - - freeScanStack(so); + MemoryContext oldCtx = MemoryContextSwitchTo(so->queueCxt); if (so->searchNulls) - { - /* Stack a work item to scan the null index entries */ - startEntry = (ScanStackEntry *) palloc0(sizeof(ScanStackEntry)); - ItemPointerSet(&startEntry->ptr, SPGIST_NULL_BLKNO, FirstOffsetNumber); - so->scanStack = lappend(so->scanStack, startEntry); - } + /* Add a work item to scan the null index entries */ + spgAddStartItem(so, true); if (so->searchNonNulls) + /* Add a work item to scan the non-null index entries */ + spgAddStartItem(so, false); + + MemoryContextSwitchTo(oldCtx); + + if (so->numberOfOrderBys > 0) { - /* Stack a work item to scan the non-null index entries */ - startEntry = (ScanStackEntry *) palloc0(sizeof(ScanStackEntry)); - ItemPointerSet(&startEntry->ptr, SPGIST_ROOT_BLKNO, FirstOffsetNumber); - so->scanStack = lappend(so->scanStack, startEntry); + /* Must pfree distances to avoid memory leak */ + int i; + + for (i = 0; i < so->nPtrs; i++) + if (so->distances[i]) + pfree(so->distances[i]); } if (so->want_itup) @@ -122,6 +201,9 @@ spgPrepareScanKeys(IndexScanDesc scan) int nkeys; int i; + so->numberOfOrderBys = scan->numberOfOrderBys; + so->orderByData = scan->orderByData; + if (scan->numberOfKeys <= 0) { /* If no quals, whole-index scan is required */ @@ -182,8 +264,9 @@ spgbeginscan(Relation rel, int keysz, int orderbysz) { IndexScanDesc scan; SpGistScanOpaque so; + int i; - scan = RelationGetIndexScan(rel, keysz, 0); + scan = RelationGetIndexScan(rel, keysz, orderbysz); so = (SpGistScanOpaque) palloc0(sizeof(SpGistScanOpaqueData)); if (keysz > 0) @@ -191,6 +274,7 @@ spgbeginscan(Relation rel, int keysz, int orderbysz) else so->keyData = NULL; initSpGistState(&so->state, scan->indexRelation); + so->tempCxt = AllocSetContextCreate(CurrentMemoryContext, "SP-GiST search temporary context", ALLOCSET_DEFAULT_SIZES); @@ -201,6 +285,36 @@ spgbeginscan(Relation rel, int keysz, int orderbysz) /* Set up indexTupDesc and xs_hitupdesc in case it's an index-only scan */ so->indexTupDesc = scan->xs_hitupdesc = RelationGetDescr(rel); + if (scan->numberOfOrderBys > 0) + { + so->zeroDistances = palloc(sizeof(double) * scan->numberOfOrderBys); + so->infDistances = palloc(sizeof(double) * scan->numberOfOrderBys); + + for (i = 0; i < scan->numberOfOrderBys; i++) + { + so->zeroDistances[i] = 0.0; + so->infDistances[i] = get_float8_infinity(); + } + + scan->xs_orderbyvals = palloc0(sizeof(Datum) * scan->numberOfOrderBys); + scan->xs_orderbynulls = palloc(sizeof(bool) * scan->numberOfOrderBys); + memset(scan->xs_orderbynulls, true, sizeof(bool) * scan->numberOfOrderBys); + } + + so->queueCxt = AllocSetContextCreate(CurrentMemoryContext, + "SP-GiST queue context", + ALLOCSET_DEFAULT_SIZES); + + fmgr_info_copy(&so->innerConsistentFn, + index_getprocinfo(rel, 1, SPGIST_INNER_CONSISTENT_PROC), + CurrentMemoryContext); + + fmgr_info_copy(&so->leafConsistentFn, + index_getprocinfo(rel, 1, SPGIST_LEAF_CONSISTENT_PROC), + CurrentMemoryContext); + + so->indexCollation = rel->rd_indcollation[0]; + scan->opaque = so; return scan; @@ -211,21 +325,58 @@ spgrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys, ScanKey orderbys, int norderbys) { SpGistScanOpaque so = (SpGistScanOpaque) scan->opaque; + MemoryContext oldCxt; /* clear traversal context before proceeding to the next scan */ MemoryContextReset(so->traversalCxt); /* copy scankeys into local storage */ if (scankey && scan->numberOfKeys > 0) - { memmove(scan->keyData, scankey, scan->numberOfKeys * sizeof(ScanKeyData)); + + if (orderbys && scan->numberOfOrderBys > 0) + { + int i; + + memmove(scan->orderByData, orderbys, + scan->numberOfOrderBys * sizeof(ScanKeyData)); + + so->orderByTypes = (Oid *) palloc(sizeof(Oid) * scan->numberOfOrderBys); + + for (i = 0; i < scan->numberOfOrderBys; i++) + { + ScanKey skey = &scan->orderByData[i]; + + /* + * Look up the datatype returned by the original ordering + * operator. SP-GiST always uses a float8 for the distance function, + * but the ordering operator could be anything else. + * + * XXX: The distance function is only allowed to be lossy if the + * ordering operator's result type is float4 or float8. Otherwise + * we don't know how to return the distance to the executor. But + * we cannot check that here, as we won't know if the distance + * function is lossy until it returns *recheck = true for the + * first time. + */ + so->orderByTypes[i] = get_func_rettype(skey->sk_func.fn_oid); + } } /* preprocess scankeys, set up the representation in *so */ spgPrepareScanKeys(scan); - /* set up starting stack entries */ + so->scanStack = NIL; + + MemoryContextReset(so->queueCxt); + oldCxt = MemoryContextSwitchTo(so->queueCxt); + /* initialize queue only for distance-ordered scans */ + so->queue = scan->numberOfOrderBys <= 0 ? NULL : + pairingheap_allocate(pairingheap_SpGistSearchItem_cmp, scan); + MemoryContextSwitchTo(oldCxt); + + /* set up starting queue entries */ resetSpGistScanOpaque(so); } @@ -236,65 +387,349 @@ spgendscan(IndexScanDesc scan) MemoryContextDelete(so->tempCxt); MemoryContextDelete(so->traversalCxt); + MemoryContextDelete(so->queueCxt); + + if (scan->numberOfOrderBys > 0) + { + pfree(so->zeroDistances); + pfree(so->infDistances); + } +} + +/* + * Leaf SpGistSearchItem constructor, called in queue context + */ +static SpGistSearchItem * +spgNewHeapItem(SpGistScanOpaque so, int level, ItemPointer heapPtr, + Datum leafValue, bool recheckQual, bool recheckDist, bool isnull, + double *distances) +{ + SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances); + + item->level = level; + item->heapPtr = *heapPtr; + /* copy value to queue cxt out of tmp cxt */ + item->value = isnull ? (Datum) 0 : + datumCopy(leafValue, so->state.attLeafType.attbyval, + so->state.attLeafType.attlen); + item->traversalValue = NULL; + item->isLeaf = true; + item->recheckQual = recheckQual; + item->recheckDist = recheckDist; + + return item; } /* * Test whether a leaf tuple satisfies all the scan keys * - * *leafValue is set to the reconstructed datum, if provided - * *recheck is set true if any of the operators are lossy + * *reportedSome is set to true if: + * the scan is not ordered AND the item satisfies the scankeys */ static bool -spgLeafTest(Relation index, SpGistScanOpaque so, +spgLeafTest(SpGistScanOpaque so, SpGistSearchItem *item, SpGistLeafTuple leafTuple, bool isnull, - int level, Datum reconstructedValue, - void *traversalValue, - Datum *leafValue, bool *recheck) + bool *reportedSome, storeRes_func storeRes) { + Datum leafValue; + double *distances; bool result; - Datum leafDatum; - spgLeafConsistentIn in; - spgLeafConsistentOut out; - FmgrInfo *procinfo; - MemoryContext oldCtx; + bool recheckQual; + bool recheckDist; if (isnull) { /* Should not have arrived on a nulls page unless nulls are wanted */ Assert(so->searchNulls); - *leafValue = (Datum) 0; - *recheck = false; - return true; + leafValue = (Datum) 0; + distances = NULL; + recheckQual = false; + recheckDist = false; + result = true; + } + else + { + spgLeafConsistentIn in; + spgLeafConsistentOut out; + + /* use temp context for calling leaf_consistent */ + MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt); + + in.scankeys = so->keyData; + in.nkeys = so->numberOfKeys; + in.orderbykeys = so->orderByData; + in.norderbys = so->numberOfOrderBys; + in.reconstructedValue = item->value; + in.traversalValue = item->traversalValue; + in.level = item->level; + in.returnData = so->want_itup; + in.leafDatum = SGLTDATUM(leafTuple, &so->state); + + out.leafValue = (Datum) 0; + out.recheck = false; + out.distances = NULL; + out.recheckDistances = false; + + result = DatumGetBool(FunctionCall2Coll(&so->leafConsistentFn, + so->indexCollation, + PointerGetDatum(&in), + PointerGetDatum(&out))); + recheckQual = out.recheck; + recheckDist = out.recheckDistances; + leafValue = out.leafValue; + distances = out.distances; + + MemoryContextSwitchTo(oldCxt); } - leafDatum = SGLTDATUM(leafTuple, &so->state); + if (result) + { + /* item passes the scankeys */ + if (so->numberOfOrderBys > 0) + { + /* the scan is ordered -> add the item to the queue */ + MemoryContext oldCxt = MemoryContextSwitchTo(so->queueCxt); + SpGistSearchItem *heapItem = spgNewHeapItem(so, item->level, + &leafTuple->heapPtr, + leafValue, + recheckQual, + recheckDist, + isnull, + distances); + + spgAddSearchItemToQueue(so, heapItem); + + MemoryContextSwitchTo(oldCxt); + } + else + { + /* non-ordered scan, so report the item right away */ + Assert(!recheckDist); + storeRes(so, &leafTuple->heapPtr, leafValue, isnull, + recheckQual, false, NULL); + *reportedSome = true; + } + } - /* use temp context for calling leaf_consistent */ - oldCtx = MemoryContextSwitchTo(so->tempCxt); + return result; +} - in.scankeys = so->keyData; - in.nkeys = so->numberOfKeys; - in.reconstructedValue = reconstructedValue; - in.traversalValue = traversalValue; - in.level = level; - in.returnData = so->want_itup; - in.leafDatum = leafDatum; +/* A bundle initializer for inner_consistent methods */ +static void +spgInitInnerConsistentIn(spgInnerConsistentIn *in, + SpGistScanOpaque so, + SpGistSearchItem *item, + SpGistInnerTuple innerTuple) +{ + in->scankeys = so->keyData; + in->nkeys = so->numberOfKeys; + in->norderbys = so->numberOfOrderBys; + in->orderbyKeys = so->orderByData; + in->reconstructedValue = item->value; + in->traversalMemoryContext = so->traversalCxt; + in->traversalValue = item->traversalValue; + in->level = item->level; + in->returnData = so->want_itup; + in->allTheSame = innerTuple->allTheSame; + in->hasPrefix = (innerTuple->prefixSize > 0); + in->prefixDatum = SGITDATUM(innerTuple, &so->state); + in->nNodes = innerTuple->nNodes; + in->nodeLabels = spgExtractNodeLabels(&so->state, innerTuple); +} - out.leafValue = (Datum) 0; - out.recheck = false; +static SpGistSearchItem * +spgMakeInnerItem(SpGistScanOpaque so, + SpGistSearchItem *parentItem, + SpGistNodeTuple tuple, + spgInnerConsistentOut *out, int i, bool isnull, + double *distances) +{ + SpGistSearchItem *item = spgAllocSearchItem(so, isnull, distances); + + item->heapPtr = tuple->t_tid; + item->level = out->levelAdds ? parentItem->level + out->levelAdds[i] + : parentItem->level; + + /* Must copy value out of temp context */ + item->value = out->reconstructedValues + ? datumCopy(out->reconstructedValues[i], + so->state.attLeafType.attbyval, + so->state.attLeafType.attlen) + : (Datum) 0; + + /* + * Elements of out.traversalValues should be allocated in + * in.traversalMemoryContext, which is actually a long + * lived context of index scan. + */ + item->traversalValue = + out->traversalValues ? out->traversalValues[i] : NULL; + + item->isLeaf = false; + item->recheckQual = false; + item->recheckDist = false; + + return item; +} - procinfo = index_getprocinfo(index, 1, SPGIST_LEAF_CONSISTENT_PROC); - result = DatumGetBool(FunctionCall2Coll(procinfo, - index->rd_indcollation[0], - PointerGetDatum(&in), - PointerGetDatum(&out))); +static void +spgInnerTest(SpGistScanOpaque so, SpGistSearchItem *item, + SpGistInnerTuple innerTuple, bool isnull) +{ + MemoryContext oldCxt = MemoryContextSwitchTo(so->tempCxt); + spgInnerConsistentOut out; + int nNodes = innerTuple->nNodes; + int i; - *leafValue = out.leafValue; - *recheck = out.recheck; + memset(&out, 0, sizeof(out)); - MemoryContextSwitchTo(oldCtx); + if (!isnull) + { + spgInnerConsistentIn in; - return result; + spgInitInnerConsistentIn(&in, so, item, innerTuple); + + /* use user-defined inner consistent method */ + FunctionCall2Coll(&so->innerConsistentFn, + so->indexCollation, + PointerGetDatum(&in), + PointerGetDatum(&out)); + } + else + { + /* force all children to be visited */ + out.nNodes = nNodes; + out.nodeNumbers = (int *) palloc(sizeof(int) * nNodes); + for (i = 0; i < nNodes; i++) + out.nodeNumbers[i] = i; + } + + /* If allTheSame, they should all or none of 'em match */ + if (innerTuple->allTheSame) + if (out.nNodes != 0 && out.nNodes != nNodes) + elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple"); + + if (out.nNodes) + { + /* collect node pointers */ + SpGistNodeTuple node; + SpGistNodeTuple *nodes = (SpGistNodeTuple *) palloc( + sizeof(SpGistNodeTuple) * nNodes); + + SGITITERATE(innerTuple, i, node) + { + nodes[i] = node; + } + + MemoryContextSwitchTo(so->queueCxt); + + for (i = 0; i < out.nNodes; i++) + { + int nodeN = out.nodeNumbers[i]; + SpGistSearchItem *innerItem; + double *distances; + + Assert(nodeN >= 0 && nodeN < nNodes); + + node = nodes[nodeN]; + + if (!ItemPointerIsValid(&node->t_tid)) + continue; + + /* + * Use infinity distances if innerConsistent() failed to return + * them or if is a NULL item (their distances are really unused). + */ + distances = out.distances ? out.distances[i] : so->infDistances; + + innerItem = spgMakeInnerItem(so, item, node, &out, i, isnull, + distances); + + spgAddSearchItemToQueue(so, innerItem); + } + } + + MemoryContextSwitchTo(oldCxt); +} + +/* Returns a next item in an (ordered) scan or null if the index is exhausted */ +static SpGistSearchItem * +spgGetNextQueueItem(SpGistScanOpaque so) +{ + SpGistSearchItem *item; + + if (so->queue) + { + if (pairingheap_is_empty(so->queue)) + return NULL; /* Done when both heaps are empty */ + + item = (SpGistSearchItem *) pairingheap_remove_first(so->queue); + } + else + { + if (!so->scanStack) + return NULL; /* there are no more items to scan */ + + item = (SpGistSearchItem *) linitial(so->scanStack); + so->scanStack = list_delete_first(so->scanStack); + } + + /* Return item; caller is responsible to pfree it */ + return item; +} + +enum SpGistSpecialOffsetNumbers +{ + SpGistBreakOffsetNumber = InvalidOffsetNumber, + SpGistRedirectOffsetNumber = MaxOffsetNumber + 1, + SpGistErrorOffsetNumber = MaxOffsetNumber + 2 +}; + +static OffsetNumber +spgTestLeafTuple(SpGistScanOpaque so, + SpGistSearchItem *item, + Page page, OffsetNumber offset, + bool isnull, bool isroot, + bool *reportedSome, + storeRes_func storeRes) +{ + SpGistLeafTuple leafTuple = (SpGistLeafTuple) + PageGetItem(page, PageGetItemId(page, offset)); + + if (leafTuple->tupstate != SPGIST_LIVE) + { + if (!isroot) /* all tuples on root should be live */ + { + if (leafTuple->tupstate == SPGIST_REDIRECT) + { + /* redirection tuple should be first in chain */ + Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr)); + /* transfer attention to redirect point */ + item->heapPtr = ((SpGistDeadTuple) leafTuple)->pointer; + Assert(ItemPointerGetBlockNumber(&item->heapPtr) != SPGIST_METAPAGE_BLKNO); + return SpGistRedirectOffsetNumber; + } + + if (leafTuple->tupstate == SPGIST_DEAD) + { + /* dead tuple should be first in chain */ + Assert(offset == ItemPointerGetOffsetNumber(&item->heapPtr)); + /* No live entries on this page */ + Assert(leafTuple->nextOffset == InvalidOffsetNumber); + return SpGistBreakOffsetNumber; + } + } + + /* We should not arrive at a placeholder */ + elog(ERROR, "unexpected SPGiST tuple state: %d", leafTuple->tupstate); + return SpGistErrorOffsetNumber; + } + + Assert(ItemPointerIsValid(&leafTuple->heapPtr)); + + spgLeafTest(so, item, leafTuple, isnull, reportedSome, storeRes); + + return leafTuple->nextOffset; } /* @@ -313,247 +748,101 @@ spgWalk(Relation index, SpGistScanOpaque so, bool scanWholeIndex, while (scanWholeIndex || !reportedSome) { - ScanStackEntry *stackEntry; - BlockNumber blkno; - OffsetNumber offset; - Page page; - bool isnull; - - /* Pull next to-do item from the list */ - if (so->scanStack == NIL) - break; /* there are no more pages to scan */ + SpGistSearchItem *item = spgGetNextQueueItem(so); - stackEntry = (ScanStackEntry *) linitial(so->scanStack); - so->scanStack = list_delete_first(so->scanStack); + if (item == NULL) + break; /* No more items in queue -> done */ redirect: /* Check for interrupts, just in case of infinite loop */ CHECK_FOR_INTERRUPTS(); - blkno = ItemPointerGetBlockNumber(&stackEntry->ptr); - offset = ItemPointerGetOffsetNumber(&stackEntry->ptr); - - if (buffer == InvalidBuffer) + if (item->isLeaf) { - buffer = ReadBuffer(index, blkno); - LockBuffer(buffer, BUFFER_LOCK_SHARE); + /* We store heap items in the queue only in case of ordered search */ + Assert(so->numberOfOrderBys > 0); + storeRes(so, &item->heapPtr, item->value, item->isNull, + item->recheckQual, item->recheckDist, item->distances); + reportedSome = true; } - else if (blkno != BufferGetBlockNumber(buffer)) + else { - UnlockReleaseBuffer(buffer); - buffer = ReadBuffer(index, blkno); - LockBuffer(buffer, BUFFER_LOCK_SHARE); - } - /* else new pointer points to the same page, no work needed */ + BlockNumber blkno = ItemPointerGetBlockNumber(&item->heapPtr); + OffsetNumber offset = ItemPointerGetOffsetNumber(&item->heapPtr); + Page page; + bool isnull; - page = BufferGetPage(buffer); - TestForOldSnapshot(snapshot, index, page); + if (buffer == InvalidBuffer) + { + buffer = ReadBuffer(index, blkno); + LockBuffer(buffer, BUFFER_LOCK_SHARE); + } + else if (blkno != BufferGetBlockNumber(buffer)) + { + UnlockReleaseBuffer(buffer); + buffer = ReadBuffer(index, blkno); + LockBuffer(buffer, BUFFER_LOCK_SHARE); + } - isnull = SpGistPageStoresNulls(page) ? true : false; + /* else new pointer points to the same page, no work needed */ - if (SpGistPageIsLeaf(page)) - { - SpGistLeafTuple leafTuple; - OffsetNumber max = PageGetMaxOffsetNumber(page); - Datum leafValue = (Datum) 0; - bool recheck = false; + page = BufferGetPage(buffer); + TestForOldSnapshot(snapshot, index, page); + + isnull = SpGistPageStoresNulls(page) ? true : false; - if (SpGistBlockIsRoot(blkno)) + if (SpGistPageIsLeaf(page)) { - /* When root is a leaf, examine all its tuples */ - for (offset = FirstOffsetNumber; offset <= max; offset++) - { - leafTuple = (SpGistLeafTuple) - PageGetItem(page, PageGetItemId(page, offset)); - if (leafTuple->tupstate != SPGIST_LIVE) - { - /* all tuples on root should be live */ - elog(ERROR, "unexpected SPGiST tuple state: %d", - leafTuple->tupstate); - } + /* Page is a leaf - that is, all it's tuples are heap items */ + OffsetNumber max = PageGetMaxOffsetNumber(page); - Assert(ItemPointerIsValid(&leafTuple->heapPtr)); - if (spgLeafTest(index, so, - leafTuple, isnull, - stackEntry->level, - stackEntry->reconstructedValue, - stackEntry->traversalValue, - &leafValue, - &recheck)) - { - storeRes(so, &leafTuple->heapPtr, - leafValue, isnull, recheck); - reportedSome = true; - } + if (SpGistBlockIsRoot(blkno)) + { + /* When root is a leaf, examine all its tuples */ + for (offset = FirstOffsetNumber; offset <= max; offset++) + (void) spgTestLeafTuple(so, item, page, offset, + isnull, true, + &reportedSome, storeRes); } - } - else - { - /* Normal case: just examine the chain we arrived at */ - while (offset != InvalidOffsetNumber) + else { - Assert(offset >= FirstOffsetNumber && offset <= max); - leafTuple = (SpGistLeafTuple) - PageGetItem(page, PageGetItemId(page, offset)); - if (leafTuple->tupstate != SPGIST_LIVE) + /* Normal case: just examine the chain we arrived at */ + while (offset != InvalidOffsetNumber) { - if (leafTuple->tupstate == SPGIST_REDIRECT) - { - /* redirection tuple should be first in chain */ - Assert(offset == ItemPointerGetOffsetNumber(&stackEntry->ptr)); - /* transfer attention to redirect point */ - stackEntry->ptr = ((SpGistDeadTuple) leafTuple)->pointer; - Assert(ItemPointerGetBlockNumber(&stackEntry->ptr) != SPGIST_METAPAGE_BLKNO); + Assert(offset >= FirstOffsetNumber && offset <= max); + offset = spgTestLeafTuple(so, item, page, offset, + isnull, false, + &reportedSome, storeRes); + if (offset == SpGistRedirectOffsetNumber) goto redirect; - } - if (leafTuple->tupstate == SPGIST_DEAD) - { - /* dead tuple should be first in chain */ - Assert(offset == ItemPointerGetOffsetNumber(&stackEntry->ptr)); - /* No live entries on this page */ - Assert(leafTuple->nextOffset == InvalidOffsetNumber); - break; - } - /* We should not arrive at a placeholder */ - elog(ERROR, "unexpected SPGiST tuple state: %d", - leafTuple->tupstate); } - - Assert(ItemPointerIsValid(&leafTuple->heapPtr)); - if (spgLeafTest(index, so, - leafTuple, isnull, - stackEntry->level, - stackEntry->reconstructedValue, - stackEntry->traversalValue, - &leafValue, - &recheck)) - { - storeRes(so, &leafTuple->heapPtr, - leafValue, isnull, recheck); - reportedSome = true; - } - - offset = leafTuple->nextOffset; } } - } - else /* page is inner */ - { - SpGistInnerTuple innerTuple; - spgInnerConsistentIn in; - spgInnerConsistentOut out; - FmgrInfo *procinfo; - SpGistNodeTuple *nodes; - SpGistNodeTuple node; - int i; - MemoryContext oldCtx; - - innerTuple = (SpGistInnerTuple) PageGetItem(page, - PageGetItemId(page, offset)); - - if (innerTuple->tupstate != SPGIST_LIVE) - { - if (innerTuple->tupstate == SPGIST_REDIRECT) - { - /* transfer attention to redirect point */ - stackEntry->ptr = ((SpGistDeadTuple) innerTuple)->pointer; - Assert(ItemPointerGetBlockNumber(&stackEntry->ptr) != SPGIST_METAPAGE_BLKNO); - goto redirect; - } - elog(ERROR, "unexpected SPGiST tuple state: %d", - innerTuple->tupstate); - } - - /* use temp context for calling inner_consistent */ - oldCtx = MemoryContextSwitchTo(so->tempCxt); - - in.scankeys = so->keyData; - in.nkeys = so->numberOfKeys; - in.reconstructedValue = stackEntry->reconstructedValue; - in.traversalMemoryContext = so->traversalCxt; - in.traversalValue = stackEntry->traversalValue; - in.level = stackEntry->level; - in.returnData = so->want_itup; - in.allTheSame = innerTuple->allTheSame; - in.hasPrefix = (innerTuple->prefixSize > 0); - in.prefixDatum = SGITDATUM(innerTuple, &so->state); - in.nNodes = innerTuple->nNodes; - in.nodeLabels = spgExtractNodeLabels(&so->state, innerTuple); - - /* collect node pointers */ - nodes = (SpGistNodeTuple *) palloc(sizeof(SpGistNodeTuple) * in.nNodes); - SGITITERATE(innerTuple, i, node) - { - nodes[i] = node; - } - - memset(&out, 0, sizeof(out)); - - if (!isnull) - { - /* use user-defined inner consistent method */ - procinfo = index_getprocinfo(index, 1, SPGIST_INNER_CONSISTENT_PROC); - FunctionCall2Coll(procinfo, - index->rd_indcollation[0], - PointerGetDatum(&in), - PointerGetDatum(&out)); - } - else - { - /* force all children to be visited */ - out.nNodes = in.nNodes; - out.nodeNumbers = (int *) palloc(sizeof(int) * in.nNodes); - for (i = 0; i < in.nNodes; i++) - out.nodeNumbers[i] = i; - } - - MemoryContextSwitchTo(oldCtx); - - /* If allTheSame, they should all or none of 'em match */ - if (innerTuple->allTheSame) - if (out.nNodes != 0 && out.nNodes != in.nNodes) - elog(ERROR, "inconsistent inner_consistent results for allTheSame inner tuple"); - - for (i = 0; i < out.nNodes; i++) + else /* page is inner */ { - int nodeN = out.nodeNumbers[i]; + SpGistInnerTuple innerTuple = (SpGistInnerTuple) + PageGetItem(page, PageGetItemId(page, offset)); - Assert(nodeN >= 0 && nodeN < in.nNodes); - if (ItemPointerIsValid(&nodes[nodeN]->t_tid)) + if (innerTuple->tupstate != SPGIST_LIVE) { - ScanStackEntry *newEntry; - - /* Create new work item for this node */ - newEntry = palloc(sizeof(ScanStackEntry)); - newEntry->ptr = nodes[nodeN]->t_tid; - if (out.levelAdds) - newEntry->level = stackEntry->level + out.levelAdds[i]; - else - newEntry->level = stackEntry->level; - /* Must copy value out of temp context */ - if (out.reconstructedValues) - newEntry->reconstructedValue = - datumCopy(out.reconstructedValues[i], - so->state.attLeafType.attbyval, - so->state.attLeafType.attlen); - else - newEntry->reconstructedValue = (Datum) 0; - - /* - * Elements of out.traversalValues should be allocated in - * in.traversalMemoryContext, which is actually a long - * lived context of index scan. - */ - newEntry->traversalValue = (out.traversalValues) ? - out.traversalValues[i] : NULL; - - so->scanStack = lcons(newEntry, so->scanStack); + if (innerTuple->tupstate == SPGIST_REDIRECT) + { + /* transfer attention to redirect point */ + item->heapPtr = ((SpGistDeadTuple) innerTuple)->pointer; + Assert(ItemPointerGetBlockNumber(&item->heapPtr) != + SPGIST_METAPAGE_BLKNO); + goto redirect; + } + elog(ERROR, "unexpected SPGiST tuple state: %d", + innerTuple->tupstate); } + + spgInnerTest(so, item, innerTuple, isnull); } } - /* done with this scan stack entry */ - freeScanStackEntry(so, stackEntry); + /* done with this scan item */ + spgFreeSearchItem(so, item); /* clear temp context before proceeding to the next one */ MemoryContextReset(so->tempCxt); } @@ -562,11 +851,14 @@ redirect: UnlockReleaseBuffer(buffer); } + /* storeRes subroutine for getbitmap case */ static void storeBitmap(SpGistScanOpaque so, ItemPointer heapPtr, - Datum leafValue, bool isnull, bool recheck) + Datum leafValue, bool isnull, bool recheck, bool recheckDist, + double *distances) { + Assert(!recheckDist && !distances); tbm_add_tuples(so->tbm, heapPtr, 1, recheck); so->ntids++; } @@ -590,11 +882,26 @@ spggetbitmap(IndexScanDesc scan, TIDBitmap *tbm) /* storeRes subroutine for gettuple case */ static void storeGettuple(SpGistScanOpaque so, ItemPointer heapPtr, - Datum leafValue, bool isnull, bool recheck) + Datum leafValue, bool isnull, bool recheck, bool recheckDist, + double *distances) { Assert(so->nPtrs < MaxIndexTuplesPerPage); so->heapPtrs[so->nPtrs] = *heapPtr; so->recheck[so->nPtrs] = recheck; + so->recheckDist[so->nPtrs] = recheckDist; + + if (so->numberOfOrderBys > 0) + { + if (isnull) + so->distances[so->nPtrs] = NULL; + else + { + Size size = sizeof(double) * so->numberOfOrderBys; + + so->distances[so->nPtrs] = memcpy(palloc(size), distances, size); + } + } + if (so->want_itup) { /* @@ -623,14 +930,29 @@ spggettuple(IndexScanDesc scan, ScanDirection dir) { if (so->iPtr < so->nPtrs) { - /* continuing to return tuples from a leaf page */ + /* continuing to return reported tuples */ scan->xs_ctup.t_self = so->heapPtrs[so->iPtr]; scan->xs_recheck = so->recheck[so->iPtr]; scan->xs_hitup = so->reconTups[so->iPtr]; + + if (so->numberOfOrderBys > 0) + index_store_float8_orderby_distances(scan, so->orderByTypes, + so->distances[so->iPtr], + so->recheckDist[so->iPtr]); so->iPtr++; return true; } + if (so->numberOfOrderBys > 0) + { + /* Must pfree distances to avoid memory leak */ + int i; + + for (i = 0; i < so->nPtrs; i++) + if (so->distances[i]) + pfree(so->distances[i]); + } + if (so->want_itup) { /* Must pfree reconstructed tuples to avoid memory leak */ diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c index 4a9b5da..ffbba78 100644 --- a/src/backend/access/spgist/spgutils.c +++ b/src/backend/access/spgist/spgutils.c @@ -15,17 +15,26 @@ #include "postgres.h" +#include "access/amvalidate.h" +#include "access/htup_details.h" #include "access/reloptions.h" #include "access/spgist_private.h" #include "access/transam.h" #include "access/xact.h" +#include "catalog/pg_amop.h" +#include "optimizer/paths.h" #include "storage/bufmgr.h" #include "storage/indexfsm.h" #include "storage/lmgr.h" #include "utils/builtins.h" +#include "utils/catcache.h" #include "utils/index_selfuncs.h" #include "utils/lsyscache.h" +#include "utils/syscache.h" +extern Expr *spgcanorderbyop(IndexOptInfo *index, + PathKey *pathkey, int pathkeyno, + Expr *orderby_clause, int *indexcol_p); /* * SP-GiST handler function: return IndexAmRoutine with access method parameters @@ -39,7 +48,7 @@ spghandler(PG_FUNCTION_ARGS) amroutine->amstrategies = 0; amroutine->amsupport = SPGISTNProc; amroutine->amcanorder = false; - amroutine->amcanorderbyop = false; + amroutine->amcanorderbyop = true; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = false; @@ -61,7 +70,7 @@ spghandler(PG_FUNCTION_ARGS) amroutine->amcanreturn = spgcanreturn; amroutine->amcostestimate = spgcostestimate; amroutine->amoptions = spgoptions; - amroutine->amproperty = NULL; + amroutine->amproperty = spgproperty; amroutine->amvalidate = spgvalidate; amroutine->ambeginscan = spgbeginscan; amroutine->amrescan = spgrescan; @@ -949,3 +958,82 @@ SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size, return offnum; } + +/* + * spgproperty() -- Check boolean properties of indexes. + * + * This is optional for most AMs, but is required for SP-GiST because the core + * property code doesn't support AMPROP_DISTANCE_ORDERABLE. + */ +bool +spgproperty(Oid index_oid, int attno, + IndexAMProperty prop, const char *propname, + bool *res, bool *isnull) +{ + Oid opclass, + opfamily, + opcintype; + CatCList *catlist; + int i; + + /* Only answer column-level inquiries */ + if (attno == 0) + return false; + + switch (prop) + { + case AMPROP_DISTANCE_ORDERABLE: + break; + default: + return false; + } + + /* + * Currently, SP-GiST distance-ordered scans require that there be a + * distance operator in the opclass with the default types. So we assume + * that if such a operator exists, then there's a reason for it. + */ + + /* First we need to know the column's opclass. */ + opclass = get_index_column_opclass(index_oid, attno); + if (!OidIsValid(opclass)) + { + *isnull = true; + return true; + } + + /* Now look up the opclass family and input datatype. */ + if (!get_opclass_opfamily_and_input_type(opclass, &opfamily, &opcintype)) + { + *isnull = true; + return true; + } + + /* And now we can check whether the operator is provided. */ + catlist = SearchSysCacheList1(AMOPSTRATEGY, + ObjectIdGetDatum(opfamily)); + + *res = false; + + for (i = 0; i < catlist->n_members; i++) + { + HeapTuple amoptup = &catlist->members[i]->tuple; + Form_pg_amop amopform = (Form_pg_amop) GETSTRUCT(amoptup); + + if (amopform->amoppurpose == AMOP_ORDER && + (amopform->amoplefttype == opcintype || + amopform->amoprighttype == opcintype) && + opfamily_can_sort_type(amopform->amopsortfamily, + get_op_rettype(amopform->amopopr))) + { + *res = true; + break; + } + } + + ReleaseSysCacheList(catlist); + + *isnull = false; + + return true; +} diff --git a/src/backend/access/spgist/spgvalidate.c b/src/backend/access/spgist/spgvalidate.c index 619c357..898fc38 100644 --- a/src/backend/access/spgist/spgvalidate.c +++ b/src/backend/access/spgist/spgvalidate.c @@ -187,6 +187,7 @@ spgvalidate(Oid opclassoid) { HeapTuple oprtup = &oprlist->members[i]->tuple; Form_pg_amop oprform = (Form_pg_amop) GETSTRUCT(oprtup); + Oid op_rettype; /* TODO: Check that only allowed strategy numbers exist */ if (oprform->amopstrategy < 1 || oprform->amopstrategy > 63) @@ -200,20 +201,26 @@ spgvalidate(Oid opclassoid) result = false; } - /* spgist doesn't support ORDER BY operators */ - if (oprform->amoppurpose != AMOP_SEARCH || - OidIsValid(oprform->amopsortfamily)) + /* spgist supports ORDER BY operators */ + if (oprform->amoppurpose != AMOP_SEARCH) { - ereport(INFO, - (errcode(ERRCODE_INVALID_OBJECT_DEFINITION), - errmsg("operator family \"%s\" of access method %s contains invalid ORDER BY specification for operator %s", - opfamilyname, "spgist", - format_operator(oprform->amopopr)))); - result = false; + /* ... and operator result must match the claimed btree opfamily */ + op_rettype = get_op_rettype(oprform->amopopr); + if (!opfamily_can_sort_type(oprform->amopsortfamily, op_rettype)) + { + ereport(INFO, + (errcode(ERRCODE_INVALID_OBJECT_DEFINITION), + errmsg("operator family \"%s\" of access method %s contains invalid ORDER BY specification for operator %s", + opfamilyname, "spgist", + format_operator(oprform->amopopr)))); + result = false; + } } + else + op_rettype = BOOLOID; /* Check operator signature --- same for all spgist strategies */ - if (!check_amop_signature(oprform->amopopr, BOOLOID, + if (!check_amop_signature(oprform->amopopr, op_rettype, oprform->amoplefttype, oprform->amoprighttype)) { diff --git a/src/include/access/spgist.h b/src/include/access/spgist.h index c6d7e22..e626efc 100644 --- a/src/include/access/spgist.h +++ b/src/include/access/spgist.h @@ -136,7 +136,9 @@ typedef struct spgPickSplitOut typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ + ScanKey orderbyKeys; int nkeys; /* length of array */ + int norderbys; Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ @@ -159,6 +161,7 @@ typedef struct spgInnerConsistentOut int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ void **traversalValues; /* opclass-specific traverse values */ + double **distances; /* associated distances */ } spgInnerConsistentOut; /* @@ -167,7 +170,10 @@ typedef struct spgInnerConsistentOut typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ + ScanKey orderbykeys; /* array of ordering operators and comparison + * values */ int nkeys; /* length of array */ + int norderbys; Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ @@ -181,6 +187,8 @@ typedef struct spgLeafConsistentOut { Datum leafValue; /* reconstructed original data, if any */ bool recheck; /* set true if operator must be rechecked */ + bool recheckDistances; /* set true if distances must be rechecked */ + double *distances; /* associated distances */ } spgLeafConsistentOut; diff --git a/src/include/access/spgist_private.h b/src/include/access/spgist_private.h index 99365c8..e1ad281 100644 --- a/src/include/access/spgist_private.h +++ b/src/include/access/spgist_private.h @@ -16,8 +16,10 @@ #include "access/itup.h" #include "access/spgist.h" +#include "lib/rbtree.h" #include "nodes/tidbitmap.h" #include "storage/buf.h" +#include "storage/relfilenode.h" #include "utils/relcache.h" @@ -130,12 +132,35 @@ typedef struct SpGistState bool isBuild; /* true if doing index build */ } SpGistState; +typedef struct SpGistSearchItem +{ + pairingheap_node phNode; /* pairing heap node */ + Datum value; /* value reconstructed from parent or + * leafValue if heaptuple */ + void *traversalValue; /* opclass-specific traverse value */ + int level; /* level of items on this page */ + ItemPointerData heapPtr; /* heap info, if heap tuple */ + bool isNull; /* SearchItem is NULL item */ + bool isLeaf; /* SearchItem is heap item */ + bool recheckQual; /* qual recheck is needed */ + bool recheckDist; /* distance recheck is needed */ + + /* array with numberOfOrderBys entries */ + double distances[FLEXIBLE_ARRAY_MEMBER]; +} SpGistSearchItem; + +#define SizeOfSpGistSearchItem(n_distances) \ + (offsetof(SpGistSearchItem, distances) + sizeof(double) * (n_distances)) + /* * Private state of an index scan */ typedef struct SpGistScanOpaqueData { SpGistState state; /* see above */ + List *scanStack; /* list of SpGistSearchItem (unordered scans) */ + pairingheap *queue; /* queue of unvisited items (ordered scans) */ + MemoryContext queueCxt; /* context holding the queue */ MemoryContext tempCxt; /* short-lived memory context */ MemoryContext traversalCxt; /* memory context for traversalValues */ @@ -146,9 +171,17 @@ typedef struct SpGistScanOpaqueData /* Index quals to be passed to opclass (null-related quals removed) */ int numberOfKeys; /* number of index qualifier conditions */ ScanKey keyData; /* array of index qualifier descriptors */ + int numberOfOrderBys; + ScanKey orderByData; + Oid *orderByTypes; + + FmgrInfo innerConsistentFn; + FmgrInfo leafConsistentFn; + Oid indexCollation; - /* Stack of yet-to-be-visited pages */ - List *scanStack; /* List of ScanStackEntrys */ + /* Pre-allocated workspace arrays: */ + double *zeroDistances; + double *infDistances; /* These fields are only used in amgetbitmap scans: */ TIDBitmap *tbm; /* bitmap being filled */ @@ -161,7 +194,9 @@ typedef struct SpGistScanOpaqueData int iPtr; /* index for scanning through same */ ItemPointerData heapPtrs[MaxIndexTuplesPerPage]; /* TIDs from cur page */ bool recheck[MaxIndexTuplesPerPage]; /* their recheck flags */ + bool recheckDist[MaxIndexTuplesPerPage]; /* distance recheck flags */ HeapTuple reconTups[MaxIndexTuplesPerPage]; /* reconstructed tuples */ + double *distances[MaxIndexTuplesPerPage]; /* distances (for recheck) */ /* * Note: using MaxIndexTuplesPerPage above is a bit hokey since @@ -410,6 +445,9 @@ extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size, OffsetNumber *startOffset, bool errorOK); +extern bool spgproperty(Oid index_oid, int attno, + IndexAMProperty prop, const char *propname, + bool *res, bool *isnull); /* spgdoinsert.c */ extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN,