diff --git a/src/backend/access/gin/Makefile b/src/backend/access/gin/Makefile index aabc62f..db4f496 100644 --- a/src/backend/access/gin/Makefile +++ b/src/backend/access/gin/Makefile @@ -14,6 +14,6 @@ include $(top_builddir)/src/Makefile.global OBJS = ginutil.o gininsert.o ginxlog.o ginentrypage.o gindatapage.o \ ginbtree.o ginscan.o ginget.o ginvacuum.o ginarrayproc.o \ - ginbulk.o ginfast.o ginpostinglist.o + ginbulk.o ginfast.o ginpostinglist.o ginlogic.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index a45d722..b6f521c 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -32,41 +32,6 @@ typedef struct pendingPosition bool *hasMatchKey; } pendingPosition; - -/* - * Convenience function for invoking a key's consistentFn - */ -static bool -callConsistentFn(GinState *ginstate, GinScanKey key) -{ - /* - * If we're dealing with a dummy EVERYTHING key, we don't want to call the - * consistentFn; just claim it matches. - */ - if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING) - { - key->recheckCurItem = false; - return true; - } - - /* - * Initialize recheckCurItem in case the consistentFn doesn't know it - * should set it. The safe assumption in that case is to force recheck. - */ - key->recheckCurItem = true; - - return DatumGetBool(FunctionCall8Coll(&ginstate->consistentFn[key->attnum - 1], - ginstate->supportCollation[key->attnum - 1], - PointerGetDatum(key->entryRes), - UInt16GetDatum(key->strategy), - key->query, - UInt32GetDatum(key->nuserentries), - PointerGetDatum(key->extra_data), - PointerGetDatum(&key->recheckCurItem), - PointerGetDatum(key->queryValues), - PointerGetDatum(key->queryCategories))); -} - /* * Goes to the next page if current offset is outside of bounds */ @@ -453,13 +418,95 @@ restartScanEntry: freeGinBtreeStack(stackEntry); } +/* + * Comparison function for scan entry indexes. Sorts by predictNumberResult, + * least frequent items first. + */ +static int +entryIndexByFrequencyCmp(const void *a1, const void *a2, void *arg) +{ + const GinScanKey key = (const GinScanKey) arg; + int i1 = *(const int *) a1; + int i2 = *(const int *) a2; + uint32 n1 = key->scanEntry[i1]->predictNumberResult; + uint32 n2 = key->scanEntry[i2]->predictNumberResult; + + if (n1 < n2) + return -1; + else if (n1 == n2) + return 0; + else + return 1; +} + static void -startScanKey(GinState *ginstate, GinScanKey key) +startScanKey(GinState *ginstate, GinScanOpaque so, GinScanKey key) { + MemoryContext oldCtx = CurrentMemoryContext; + int i; + int *entryIndexes; + ItemPointerSetMin(&key->curItem); key->curItemMatches = false; key->recheckCurItem = false; key->isFinished = false; + + /* + * Divide the entries into two groups, requiredEntries and otherEntries. + * Entries in otherEntries alone are not enough for a match, without any + * items from requiredEntries, but are needed by the consistent function + * to decide if an item matches. When scanning, we can skip over items in + * otherEntries that have no corresponding matches in requiredEntries. + * That speeds up considerably queries like "frequent & rare", if the + * frequent term can be put in otherEntries. + * + * There can be many legal ways to divide them entries into these two + * groups. A conservative division is to just put everything in + * requiredEntries group, but the more you can put in otherEntries, the + * more you can skip during the scan. To maximize skipping, we try to put + * as many frequent items as possible into otherEntries, and less frequent + * ones into requiredEntries. To do that, sort the entries by frequency + * (predictNumberResult), and put entries into requiredEntries in that + * order, until the consistent function says that none of the remaining + * entries can form a match, without any items from requiredEntries. + */ + key->requiredEntries = palloc(key->nentries * sizeof(GinScanEntry)); + key->otherEntries = palloc(key->nentries * sizeof(GinScanEntry)); + key->nrequired = key->nother = 0; + + if (key->nentries > 1) + { + MemoryContextSwitchTo(so->tempCtx); + + entryIndexes = (int *) palloc(sizeof(int) * key->nentries); + for (i = 0; i < key->nentries; i++) + entryIndexes[i] = i; + + qsort_arg(entryIndexes, key->nentries, sizeof(int), + entryIndexByFrequencyCmp, key); + + for (i = 0; i < key->nentries; i++) + key->entryRes[i] = GIN_MAYBE; + + for (i = 0; i < key->nentries; i++) + { + key->requiredEntries[key->nrequired++] = key->scanEntry[entryIndexes[i]]; + key->entryRes[entryIndexes[i]] = GIN_FALSE; + + if (key->triConsistentFn(key) == GIN_FALSE) + break; + } + for (i = i + 1; i < key->nentries; i++) + key->otherEntries[key->nother++] = key->scanEntry[entryIndexes[i]]; + + /* clean up after consistentFn calls (also frees entryIndexes) */ + MemoryContextSwitchTo(oldCtx); + MemoryContextReset(so->tempCtx); + } + else + { + key->requiredEntries[key->nrequired++] = key->scanEntry[0]; + } } static void @@ -494,7 +541,7 @@ startScan(IndexScanDesc scan) } for (i = 0; i < so->nkeys; i++) - startScanKey(ginstate, so->keys + i); + startScanKey(ginstate, so, so->keys + i); } /* @@ -812,10 +859,9 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData minItem; ItemPointerData curPageLossy; uint32 i; - uint32 lossyEntry; bool haveLossyEntry; GinScanEntry entry; - bool res; + GinLogicValue res; MemoryContext oldCtx; bool allFinished; @@ -823,7 +869,7 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, /* * We might have already tested this item; if so, no need to repeat work. - * (Note: the ">" case can happen, if minItem is exact but we previously + * (Note: the ">" case can happen, if advancePast is exact but we previously * had to set curItem to a lossy-page pointer.) */ if (ginCompareItemPointers(&key->curItem, &advancePast) > 0) @@ -839,9 +885,12 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, */ ItemPointerSetMax(&minItem); allFinished = true; - for (i = 0; i < key->nentries; i++) + for (i = 0; i < key->nrequired; i++) { - entry = key->scanEntry[i]; + entry = key->requiredEntries[i]; + + if (entry->isFinished) + continue; /* * Advance this stream if necessary. @@ -850,18 +899,16 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, * ItemPointerSetMin, this ensures we fetch the first item for each * entry on the first call. */ - while (entry->isFinished == FALSE && - ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) { entryGetItem(ginstate, entry, advancePast); + if (entry->isFinished) + continue; } - if (!entry->isFinished) - { - allFinished = FALSE; - if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) - minItem = entry->curItem; - } + allFinished = false; + if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) + minItem = entry->curItem; } if (allFinished) @@ -872,38 +919,96 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, } /* - * OK, set key->curItem and perform consistentFn test. + * Ok, we now know that there are no matches < minItem. + * + * If minItem is lossy, it means that there there were no exact items on + * the page among requiredEntries, because lossy pointers sort after exact + * items. However, there might be exact items for the same page among + * otherEntries, so we mustn't advance past them. */ - key->curItem = minItem; + if (ItemPointerIsLossyPage(&minItem)) + { + if (GinItemPointerGetBlockNumber(&advancePast) < + GinItemPointerGetBlockNumber(&minItem)) + { + advancePast.ip_blkid = minItem.ip_blkid; + advancePast.ip_posid = 0; + } + } + else + { + Assert(minItem.ip_posid > 0); + advancePast = minItem; + advancePast.ip_posid--; + } + + /* + * We might not have loaded all the entry streams for this TID yet. We + * could call the consistent function, passing MAYBE for those entries, to + * see if it can decide if this TID matches based on the information we + * have. But if the consistent-function is expensive, and cannot in fact + * decide with partial information, that could be a big loss. So, load all + * the additional entries, before calling the consistent function. + */ + for (i = 0; i < key->nother; i++) + { + entry = key->otherEntries[i]; + + if (entry->isFinished) + continue; + + if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + { + entryGetItem(ginstate, entry, advancePast); + if (entry->isFinished) + continue; + } + + /* + * Normally, none of the items in otherEntries can have a curItem + * larger than minItem. But if minItem is a lossy page, then there + * might be exact items on the same page among otherEntries. + */ + if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) + { + Assert(ItemPointerIsLossyPage(&minItem)); + minItem = entry->curItem; + } + } /* + * Ok, we've advanced all the entries up to minItem now. Set key->curItem, + * and perform consistentFn test. + * * Lossy-page entries pose a problem, since we don't know the correct * entryRes state to pass to the consistentFn, and we also don't know what * its combining logic will be (could be AND, OR, or even NOT). If the * logic is OR then the consistentFn might succeed for all items in the * lossy page even when none of the other entries match. * - * If we have a single lossy-page entry then we check to see if the - * consistentFn will succeed with only that entry TRUE. If so, we return - * a lossy-page pointer to indicate that the whole heap page must be + * Our strategy is to call the tri-state consistent function, with the + * lossy-page entries set to MAYBE, and all the other entries FALSE. If it + * returns FALSE, none of the lossy items alone are enough for a match, so + * we don't need to return a lossy-page pointer. Otherwise, return a + * lossy-page pointer to indicate that the whole heap page must be * checked. (On subsequent calls, we'll do nothing until minItem is past * the page altogether, thus ensuring that we never return both regular * and lossy pointers for the same page.) * - * This idea could be generalized to more than one lossy-page entry, but - * ideally lossy-page entries should be infrequent so it would seldom be - * the case that we have more than one at once. So it doesn't seem worth - * the extra complexity to optimize that case. If we do find more than - * one, we just punt and return a lossy-page pointer always. + * An exception is that it doesn't matter what we pass for lossy pointers + * in "hidden" entries, because the consistentFn's result can't depend on + * them. We could pass them as MAYBE as well, but if we're using the + * "shim" implementation of a tri-state consistent function (see + * ginlogic.c), it's better to pass as few MAYBEs as possible. So pass + * them as TRUE. * * Note that only lossy-page entries pointing to the current item's page * should trigger this processing; we might have future lossy pages in the * entry array, but they aren't relevant yet. */ + key->curItem = minItem; ItemPointerSetLossyPage(&curPageLossy, GinItemPointerGetBlockNumber(&key->curItem)); - - lossyEntry = 0; haveLossyEntry = false; for (i = 0; i < key->nentries; i++) { @@ -911,17 +1016,14 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, if (entry->isFinished == FALSE && ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0) { - if (haveLossyEntry) - { - /* Multiple lossy entries, punt */ - key->curItem = curPageLossy; - key->curItemMatches = true; - key->recheckCurItem = true; - return; - } - lossyEntry = i; + if (i < key->nuserentries) + key->entryRes[i] = GIN_MAYBE; + else + key->entryRes[i] = GIN_TRUE; haveLossyEntry = true; } + else + key->entryRes[i] = GIN_FALSE; } /* prepare for calling consistentFn in temp context */ @@ -929,11 +1031,10 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, if (haveLossyEntry) { - /* Single lossy-page entry, so see if whole page matches */ - memset(key->entryRes, FALSE, key->nentries); - key->entryRes[lossyEntry] = TRUE; + /* Have lossy-page entries, so see if whole page matches */ + res = key->triConsistentFn(key); - if (callConsistentFn(ginstate, key)) + if (res == GIN_TRUE || res == GIN_MAYBE) { /* Yes, so clean up ... */ MemoryContextSwitchTo(oldCtx); @@ -950,41 +1051,69 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, /* * At this point we know that we don't need to return a lossy whole-page * pointer, but we might have matches for individual exact item pointers, - * possibly in combination with a lossy pointer. Our strategy if there's - * a lossy pointer is to try the consistentFn both ways and return a hit - * if it accepts either one (forcing the hit to be marked lossy so it will - * be rechecked). An exception is that we don't need to try it both ways - * if the lossy pointer is in a "hidden" entry, because the consistentFn's - * result can't depend on that. + * possibly in combination with a lossy pointer. Pass lossy pointers as + * MAYBE to the ternary consistent function, to let it decide if this + * tuple satisfies the overall key, even though we don't know whether the + * lossy entries match. * * Prepare entryRes array to be passed to consistentFn. */ for (i = 0; i < key->nentries; i++) { entry = key->scanEntry[i]; - if (entry->isFinished == FALSE && - ginCompareItemPointers(&entry->curItem, &key->curItem) == 0) - key->entryRes[i] = TRUE; + if (entry->isFinished) + key->entryRes[i] = GIN_FALSE; +#if 0 + /* + * This case can't currently happen, because we't loaded all the + * entries for this item earlier. + */ + else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + key->entryRes[i] = GIN_MAYBE; +#endif + else if (ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0) + key->entryRes[i] = GIN_MAYBE; + else if (ginCompareItemPointers(&entry->curItem, &minItem) == 0) + key->entryRes[i] = GIN_TRUE; else - key->entryRes[i] = FALSE; + key->entryRes[i] = GIN_FALSE; } - if (haveLossyEntry) - key->entryRes[lossyEntry] = TRUE; - res = callConsistentFn(ginstate, key); + res = key->triConsistentFn(key); - if (!res && haveLossyEntry && lossyEntry < key->nuserentries) + switch (res) { - /* try the other way for the lossy item */ - key->entryRes[lossyEntry] = FALSE; + case GIN_TRUE: + key->curItemMatches = true; + /* triConsistentFn set recheckCurItem */ + break; + + case GIN_FALSE: + key->curItemMatches = false; + break; - res = callConsistentFn(ginstate, key); + case GIN_MAYBE: + key->curItemMatches = true; + key->recheckCurItem = true; + break; + + default: + /* + * the 'default' case shouldn't happen, but if the consistent + * function returns something bogus, this is the safe result + */ + key->curItemMatches = true; + key->recheckCurItem = true; + break; } - key->curItemMatches = res; - /* If we matched a lossy entry, force recheckCurItem = true */ - if (haveLossyEntry) - key->recheckCurItem = true; + /* + * We have a tuple, and we know if it matches or not. If it's a + * non-match, we could continue to find the next matching tuple, but + * let's break out and give scanGetItem a chance to advance the other + * keys. They might be able to skip past to a much higher TID, allowing + * us to save work. + */ /* clean up after consistentFn calls */ MemoryContextSwitchTo(oldCtx); @@ -1080,7 +1209,7 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, /* * If this is the first key, remember this location as a - * potential match. + * potential match, and proceed to check the rest of the keys. * * Otherwise, check if this is the same item that we checked the * previous keys for (or a lossy pointer for the same page). If @@ -1322,7 +1451,7 @@ collectMatchesForHeapRow(IndexScanDesc scan, pendingPosition *pos) { GinScanKey key = so->keys + i; - memset(key->entryRes, FALSE, key->nentries); + memset(key->entryRes, GIN_FALSE, key->nentries); } memset(pos->hasMatchKey, FALSE, so->nkeys); @@ -1579,7 +1708,7 @@ scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids) { GinScanKey key = so->keys + i; - if (!callConsistentFn(&so->ginstate, key)) + if (!key->boolConsistentFn(key)) { match = false; break; diff --git a/src/backend/access/gin/ginlogic.c b/src/backend/access/gin/ginlogic.c new file mode 100644 index 0000000..c46a28c --- /dev/null +++ b/src/backend/access/gin/ginlogic.c @@ -0,0 +1,149 @@ +/*------------------------------------------------------------------------- + * + * ginlogic.c + * routines for performing binary- and ternary-logic consistent checks. + * + * + * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/access/gin/ginlogic.c + *------------------------------------------------------------------------- + */ + +#include "postgres.h" + +#include "access/gin_private.h" +#include "access/reloptions.h" +#include "catalog/pg_collation.h" +#include "catalog/pg_type.h" +#include "miscadmin.h" +#include "storage/indexfsm.h" +#include "storage/lmgr.h" + +/* + * A dummy consistent function for an EVERYTHING key. Just claim it matches. + */ +static bool +trueConsistentFn(GinScanKey key) +{ + key->recheckCurItem = false; + return true; +} +static GinLogicValue +trueTriConsistentFn(GinScanKey key) +{ + return GIN_MAYBE; +} + +/* + * A function for calling a regular, binary logic, consistent function. + */ +static bool +normalBoolConsistentFn(GinScanKey key) +{ + /* + * Initialize recheckCurItem in case the consistentFn doesn't know it + * should set it. The safe assumption in that case is to force recheck. + */ + key->recheckCurItem = true; + + return DatumGetBool(FunctionCall8Coll(key->consistentFmgrInfo, + key->collation, + PointerGetDatum(key->entryRes), + UInt16GetDatum(key->strategy), + key->query, + UInt32GetDatum(key->nuserentries), + PointerGetDatum(key->extra_data), + PointerGetDatum(&key->recheckCurItem), + PointerGetDatum(key->queryValues), + PointerGetDatum(key->queryCategories))); +} + +/* + * This function implements a tri-state consistency check, using a boolean + * consistent function provided by the opclass. + * + * Our strategy is to call consistentFn with MAYBE inputs replaced with every + * combination of TRUE/FALSE. If consistentFn returns the same value for every + * combination, that's the overall result. Otherwise, return MAYBE. Testing + * every combination is O(n^2), so this is only feasible for a small number of + * MAYBE inputs. + */ +static GinLogicValue +shimTriConsistentFn(GinScanKey key) +{ +#define MAX_MAYBE_ENTRIES 8 + int nmaybe; + int maybeEntries[MAX_MAYBE_ENTRIES]; + int i; + bool boolResult; + bool recheck; + GinLogicValue curResult; + + nmaybe = 0; + for (i = 0; i < key->nentries; i++) + { + if (key->entryRes[i] == GIN_MAYBE) + { + if (nmaybe >= MAX_MAYBE_ENTRIES) + return GIN_MAYBE; + maybeEntries[nmaybe++] = i; + } + } + + /* + * If none of the inputs were MAYBE, so we can just call consistent + * function as is. + */ + if (nmaybe == 0) + return normalBoolConsistentFn(key); + + /* Try the consistent function with the maybe-inputs set both ways */ + for (i = 0; i < nmaybe; i++) + key->entryRes[maybeEntries[i]] = GIN_FALSE; + curResult = normalBoolConsistentFn(key); + + for (;;) + { + /* Twiddle the entries for next combination. */ + for (i = 0; i < nmaybe; i++) + { + if (key->entryRes[maybeEntries[i]] == GIN_FALSE) + { + key->entryRes[maybeEntries[i]] = GIN_TRUE; + break; + } + else + key->entryRes[maybeEntries[i]] = GIN_FALSE; + } + if (i == nmaybe) + break; + + boolResult = normalBoolConsistentFn(key); + recheck |= key->recheckCurItem; + + if (curResult != boolResult) + return GIN_MAYBE; + } + + return curResult; +} + +void +GinInitConsistentMethod(GinState *ginstate, GinScanKey key) +{ + if (key->searchMode == GIN_SEARCH_MODE_EVERYTHING) + { + key->boolConsistentFn = trueConsistentFn; + key->triConsistentFn = trueTriConsistentFn; + } + else + { + key->consistentFmgrInfo = &ginstate->consistentFn[key->attnum - 1]; + key->collation = ginstate->supportCollation[key->attnum - 1]; + key->boolConsistentFn = normalBoolConsistentFn; + key->triConsistentFn = shimTriConsistentFn; + } +} diff --git a/src/backend/access/gin/ginscan.c b/src/backend/access/gin/ginscan.c index b80b294..ed29d8d 100644 --- a/src/backend/access/gin/ginscan.c +++ b/src/backend/access/gin/ginscan.c @@ -164,6 +164,8 @@ ginFillScanKey(GinScanOpaque so, OffsetNumber attnum, key->recheckCurItem = false; key->isFinished = false; + GinInitConsistentMethod(ginstate, key); + for (i = 0; i < nQueryValues; i++) { Datum queryKey; diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index bb0ab31..a8fe448 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -17,6 +17,8 @@ #include "storage/bufmgr.h" #include "utils/rbtree.h" +typedef struct GinScanKeyData *GinScanKey; +typedef struct GinScanEntryData *GinScanEntry; /* * Page opaque data in an inverted index page. @@ -588,6 +590,19 @@ extern OffsetNumber gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple); extern Datum gintuple_get_key(GinState *ginstate, IndexTuple tuple, GinNullCategory *category); +/* ginlogic.c */ + +enum +{ + GIN_FALSE = 0, + GIN_TRUE = 1, + GIN_MAYBE = 2 +} GinLogicValueEnum; + +typedef char GinLogicValue; + +extern void GinInitConsistentMethod(GinState *ginstate, GinScanKey key); + /* gininsert.c */ extern Datum ginbuild(PG_FUNCTION_ARGS); extern Datum ginbuildempty(PG_FUNCTION_ARGS); @@ -732,10 +747,6 @@ extern void ginVacuumPostingTreeLeaf(Relation rel, Buffer buf, GinVacuumState *g * nuserentries is the number that extractQueryFn returned (which is what * we report to consistentFn). The "user" entries must come first. */ -typedef struct GinScanKeyData *GinScanKey; - -typedef struct GinScanEntryData *GinScanEntry; - typedef struct GinScanKeyData { /* Real number of entries in scanEntry[] (always > 0) */ @@ -746,8 +757,25 @@ typedef struct GinScanKeyData /* array of GinScanEntry pointers, one per extracted search condition */ GinScanEntry *scanEntry; + /* + * requiredEntries contains entries, such that at least one of the entries + * in this set must match, for the overall qual to match. + * + * otherEntries contains additional entries that are needed by the + * consistent function to decide if an item matches, but are not sufficient + * to satisfy the qual without entries from requiredEntries. + */ + GinScanEntry *requiredEntries; + int nrequired; + GinScanEntry *otherEntries; + int nother; + /* array of check flags, reported to consistentFn */ bool *entryRes; + bool (*boolConsistentFn) (GinScanKey key); + bool (*triConsistentFn) (GinScanKey key); + FmgrInfo *consistentFmgrInfo; + Oid collation; /* other data needed for calling consistentFn */ Datum query;