Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1W7Afh-0005M5-0X for pgsql-hackers@arkaria.postgresql.org; Sat, 25 Jan 2014 21:21:45 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1W7Afg-0006vj-9r for pgsql-hackers@arkaria.postgresql.org; Sat, 25 Jan 2014 21:21:44 +0000 Received: from makus.postgresql.org ([2001:4800:7903:4::125]) by malur.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1W7Afc-0006vU-O4 for pgsql-hackers@postgresql.org; Sat, 25 Jan 2014 21:21:41 +0000 Received: from smtp-outbound-2.vmware.com ([208.91.2.13]) by makus.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1W7AfP-0000Bb-0A for pgsql-hackers@postgresql.org; Sat, 25 Jan 2014 21:21:38 +0000 Received: from sc9-mailhost3.vmware.com (sc9-mailhost3.vmware.com [10.113.161.73]) by smtp-outbound-2.vmware.com (Postfix) with ESMTP id A0664288B6; Sat, 25 Jan 2014 13:21:25 -0800 (PST) Received: from zcs-prod-ext-mta-2.vmware.com (zcs-prod-ext-mta-2.vmware.com [10.113.62.224]) by sc9-mailhost3.vmware.com (Postfix) with ESMTP id 9C7714041D; Sat, 25 Jan 2014 13:21:25 -0800 (PST) Received: from zcs-prod-ext-mta-2.vmware.com (localhost.localdomain [127.0.0.1]) by zcs-prod-ext-mta-2.vmware.com (Postfix) with ESMTP id 65D36C0053; Sat, 25 Jan 2014 13:22:04 -0800 (PST) Received: from [192.168.1.90] (zimbra-prod-ext-proxy-vip.vmware.com [10.113.63.87]) by zcs-prod-ext-mta-2.vmware.com (Postfix) with ESMTPSA; Sat, 25 Jan 2014 13:22:01 -0800 (PST) Message-ID: <52E42AD0.5060600@vmware.com> Date: Sat, 25 Jan 2014 23:21:20 +0200 From: Heikki Linnakangas Organization: VMware User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20131103 Icedove/17.0.10 MIME-Version: 1.0 To: Tomas Vondra CC: pgsql-hackers@postgresql.org Subject: Re: GIN improvements part2: fast scan References: <51C16235.3080308@vmware.com> <51C170A8.9060509@vmware.com> <51C4ACC5.2090707@vmware.com> <51D00FB6.9030008@vmware.com> <528533D9.3040501@vmware.com> <52E141BA.5000302@vmware.com> <52E4141E.60609@fuzzy.cz> In-Reply-To: <52E4141E.60609@fuzzy.cz> Content-Type: multipart/mixed; boundary="------------060203020309040604030703" X-Pg-Spam-Score: -7.5 (-------) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org This is a multi-part message in MIME format. --------------060203020309040604030703 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit On 01/25/2014 09:44 PM, Tomas Vondra wrote: > This is rather easy to reproduce - download the dump I already provided > two weeks ago [http://www.fuzzy.cz/tmp/message-b.data.gz] and load it > into a simple table: > > CREATE TABLE msgs (body tsvector); > COPY msgs FROM '/tmp/message-b.data'; > CREATE INDEX msgidx ON msgs USING gin(body); > ANALYZE msgs; > > And then run this query: > > SELECT body FROM msgs > WHERE body @@ plainto_tsquery('english','string | x') > AND body @@ plainto_tsquery('english','versions | equivalent') > AND body @@ plainto_tsquery('english','usually | contain'); > > It should run infinitely. I suspect it's not perfectly stable, i.e, the > this query may work fine / another one will block. In that case try to > run this [http://www.fuzzy.cz/tmp/random-queries.sql] - it's a file with > 1000 generated queries, at least one of them should block (that's how I > discovered the issue). Thanks, that's a great test suite! Indeed, it did get stuck for me as well. I tracked it down to a logic bug in entryGetItem; an && should've been ||. Also, it tickled an assertion in the debug LOG statement that bleated "entryLoadMoreItems, %u/%u, skip: %d" (I was using ItemPointerGetBlockNumber, which contains a check that the argument is a valid item pointer, which it isn't always in this case). Fixed that too. Attached is a new version of the patch set, with those bugs fixed. One interesting detail that I noticed while testing that query: Using EXPLAIN (BUFFERS) shows that we're actually accessing *more* pages with the patches than without it. The culprit is patch #3, which makes us re-descend the posting tree from root, rather than just stepping right from current page. I was very surprised by that at first - the patch was supposed to *reduce* the number of page's accessed, by not having to walk through all the leaf pages. But in this case, even when you're skipping some items, almost always the next item you're interested in is on the next posting tree page, so re-descending the tree is a waste and you land on the right sibling of the original page anyway. It's not a big waste, though. The upper levels of the tree are almost certainly in cache, so it's just a matter of some extra lw-locking and binary searching, which is cheap compared to actually decoding and copying all the items from the correct page. Indeed, I couldn't see any meaningful difference in query time with or without the patch. (I'm sure a different query that allows skipping more would show the patch to be a win - this was a worst case scenario) Alexander's patch contained a more complicated method for re-finding the right leaf page. It ascended the tree back up the same path it was originally descended, which is potentially faster if the tree is many-levels deep, and you only skip forward a little. In practice, posting trees are very compact, so to have a tree taller than 2 levels, it must contain millions of items. A 4-level tree would be humongous. So I don't think it's worth the complexity to try anything smarter than just re-descending from root. However, that difference in implementation shows up in EXPLAIN (BUFFERS) output; since Alexander's patch kept the stack of upper pages pinned, ascending and descending the tree did not increase the counters of pages accessed (I believe; I didn't actually test it), while descending from root does. - Heikki --------------060203020309040604030703 Content-Type: text/x-diff; name="0001-Optimize-GIN-multi-key-queries.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Optimize-GIN-multi-key-queries.patch" From 39bb64a56c43afa45b18b6d04376002005f22769 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Thu, 23 Jan 2014 15:41:43 +0200 Subject: [PATCH 1/4] Optimize GIN multi-key queries. In a multi-key search, ie. something like "col @> 'foo' AND col @> 'bar'", as soon as we find the next item that matches the first criteria, we don't need to check the second criteria for TIDs smaller the first match. That saves a lot of effort, especially if one of the first term is rare, while the second occurs very frequently. Based on ideas from Alexander Korotkov's fast scan patch --- src/backend/access/gin/ginget.c | 456 ++++++++++++++++++++++------------------ 1 file changed, 246 insertions(+), 210 deletions(-) diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index 4bdbd45..4e4b51a 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -68,29 +68,6 @@ callConsistentFn(GinState *ginstate, GinScanKey key) } /* - * Tries to refind previously taken ItemPointer on a posting page. - */ -static bool -needToStepRight(Page page, ItemPointer item) -{ - if (GinPageGetOpaque(page)->flags & GIN_DELETED) - /* page was deleted by concurrent vacuum */ - return true; - - if (ginCompareItemPointers(item, GinDataPageGetRightBound(page)) > 0 - && !GinPageRightMost(page)) - { - /* - * the item we're looking is > the right bound of the page, so it - * can't be on this page. - */ - return true; - } - - return false; -} - -/* * Goes to the next page if current offset is outside of bounds */ static bool @@ -447,8 +424,7 @@ restartScanEntry: page = BufferGetPage(entry->buffer); /* - * Copy page content to memory to avoid keeping it locked for - * a long time. + * Load the first page into memory. */ entry->list = GinDataLeafPageGetItems(page, &entry->nlist); @@ -518,88 +494,76 @@ startScan(IndexScanDesc scan) } /* - * Gets next ItemPointer from PostingTree. Note, that we copy - * page into GinScanEntry->list array and unlock page, but keep it pinned - * to prevent interference with vacuum + * Load the next batch of item pointers from a posting tree. + * + * Note that we copy the page into GinScanEntry->list array and unlock it, but + * keep it pinned to prevent interference with vacuum. */ static void -entryGetNextItem(GinState *ginstate, GinScanEntry entry) +entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advancePast) { Page page; int i; + LockBuffer(entry->buffer, GIN_SHARE); + page = BufferGetPage(entry->buffer); for (;;) { - if (entry->offset < entry->nlist) + entry->offset = InvalidOffsetNumber; + if (entry->list) { - entry->curItem = entry->list[entry->offset++]; - return; + pfree(entry->list); + entry->list = NULL; + entry->nlist = 0; } - LockBuffer(entry->buffer, GIN_SHARE); - page = BufferGetPage(entry->buffer); - for (;;) + /* + * We've processed all the entries on this page. If it was the last + * page in the tree, we're done. + */ + if (GinPageRightMost(page)) { - /* - * It's needed to go by right link. During that we should refind - * first ItemPointer greater that stored - */ - if (GinPageRightMost(page)) - { - UnlockReleaseBuffer(entry->buffer); - ItemPointerSetInvalid(&entry->curItem); - entry->buffer = InvalidBuffer; - entry->isFinished = TRUE; - return; - } + UnlockReleaseBuffer(entry->buffer); + entry->buffer = InvalidBuffer; + entry->isFinished = TRUE; + return; + } - entry->buffer = ginStepRight(entry->buffer, - ginstate->index, - GIN_SHARE); - page = BufferGetPage(entry->buffer); + if (GinPageGetOpaque(page)->flags & GIN_DELETED) + continue; /* page was deleted by concurrent vacuum */ - entry->offset = InvalidOffsetNumber; - if (entry->list) - { - pfree(entry->list); - entry->list = NULL; - } + /* + * Step to next page, following the right link. then find the first + * ItemPointer greater than advancePast. + */ + entry->buffer = ginStepRight(entry->buffer, + ginstate->index, + GIN_SHARE); + page = BufferGetPage(entry->buffer); + /* + * The first item > advancePast might not be on this page, but + * somewhere to the right, if the page was split. Keep following + * the right-links until we re-find the correct page. + */ + if (!GinPageRightMost(page) && + ginCompareItemPointers(&advancePast, GinDataPageGetRightBound(page)) >= 0) + { /* - * If the page was concurrently split, we have to re-find the - * item we were stopped on. If the page was split more than once, - * the item might not be on this page, but somewhere to the right. - * Keep following the right-links until we re-find the correct - * page. + * the item we're looking is > the right bound of the page, so it + * can't be on this page. */ - if (ItemPointerIsValid(&entry->curItem) && - needToStepRight(page, &entry->curItem)) - { - continue; - } + continue; + } - entry->list = GinDataLeafPageGetItems(page, &entry->nlist); + entry->list = GinDataLeafPageGetItems(page, &entry->nlist); - /* re-find the item we were stopped on. */ - if (ItemPointerIsValid(&entry->curItem)) - { - for (i = 0; i < entry->nlist; i++) - { - if (ginCompareItemPointers(&entry->curItem, - &entry->list[i]) < 0) - { - LockBuffer(entry->buffer, GIN_UNLOCK); - entry->offset = i + 1; - entry->curItem = entry->list[entry->offset - 1]; - return; - } - } - } - else + for (i = 0; i < entry->nlist; i++) + { + if (ginCompareItemPointers(&advancePast, &entry->list[i]) < 0) { LockBuffer(entry->buffer, GIN_UNLOCK); - entry->offset = 1; /* scan all items on the page. */ - entry->curItem = entry->list[entry->offset - 1]; + entry->offset = i; return; } } @@ -610,10 +574,10 @@ entryGetNextItem(GinState *ginstate, GinScanEntry entry) #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) ) /* - * Sets entry->curItem to next heap item pointer for one entry of one scan key, - * or sets entry->isFinished to TRUE if there are no more. + * Sets entry->curItem to next heap item pointer > advancePast, for one entry + * of one scan key, or sets entry->isFinished to TRUE if there are no more. * - * Item pointers must be returned in ascending order. + * Item pointers are returned in ascending order. * * Note: this can return a "lossy page" item pointer, indicating that the * entry potentially matches all items on that heap page. However, it is @@ -623,12 +587,20 @@ entryGetNextItem(GinState *ginstate, GinScanEntry entry) * current implementation this is guaranteed by the behavior of tidbitmaps. */ static void -entryGetItem(GinState *ginstate, GinScanEntry entry) +entryGetItem(GinState *ginstate, GinScanEntry entry, + ItemPointerData advancePast) { Assert(!entry->isFinished); + Assert(!ItemPointerIsValid(&entry->curItem) || + ginCompareItemPointers(&entry->curItem, &advancePast) <= 0); + if (entry->matchBitmap) { + /* A bitmap result */ + BlockNumber advancePastBlk = GinItemPointerGetBlockNumber(&advancePast); + OffsetNumber advancePastOff = GinItemPointerGetOffsetNumber(&advancePast); + do { if (entry->matchResult == NULL || @@ -646,6 +618,18 @@ entryGetItem(GinState *ginstate, GinScanEntry entry) } /* + * If all the matches on this page are <= advancePast, skip + * to next page. + */ + if (entry->matchResult->blockno < advancePastBlk || + (entry->matchResult->blockno == advancePastBlk && + entry->matchResult->offsets[entry->offset] <= advancePastOff)) + { + entry->offset = entry->matchResult->ntuples; + continue; + } + + /* * Reset counter to the beginning of entry->matchResult. Note: * entry->offset is still greater than matchResult->ntuples if * matchResult is lossy. So, on next call we will get next @@ -670,6 +654,17 @@ entryGetItem(GinState *ginstate, GinScanEntry entry) break; } + if (entry->matchResult->blockno == advancePastBlk) + { + /* + * Skip to the right offset on this page. We already checked + * in above loop that there is at least one item > advancePast + * on the page. + */ + while (entry->matchResult->offsets[entry->offset] <= advancePastOff) + entry->offset++; + } + ItemPointerSet(&entry->curItem, entry->matchResult->blockno, entry->matchResult->offsets[entry->offset]); @@ -678,29 +673,48 @@ entryGetItem(GinState *ginstate, GinScanEntry entry) } else if (!BufferIsValid(entry->buffer)) { - entry->offset++; - if (entry->offset <= entry->nlist) - entry->curItem = entry->list[entry->offset - 1]; - else + /* A posting list from an entry tuple */ + do { - ItemPointerSetInvalid(&entry->curItem); - entry->isFinished = TRUE; - } + if (entry->offset >= entry->nlist) + { + ItemPointerSetInvalid(&entry->curItem); + entry->isFinished = TRUE; + break; + } + + entry->curItem = entry->list[entry->offset++]; + } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0); + /* XXX: shouldn't we apply the fuzzy search limit here? */ } else { + /* A posting tree */ do { - entryGetNextItem(ginstate, entry); - } while (entry->isFinished == FALSE && - entry->reduceResult == TRUE && - dropItem(entry)); + /* If we've processed the current batch, load more items */ + while (entry->offset >= entry->nlist) + { + entryLoadMoreItems(ginstate, entry, advancePast); + + if (entry->isFinished) + { + ItemPointerSetInvalid(&entry->curItem); + return; + } + } + + entry->curItem = entry->list[entry->offset++]; + + } while (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0 || + (entry->reduceResult == TRUE && dropItem(entry))); } } /* - * Identify the "current" item among the input entry streams for this scan key, - * and test whether it passes the scan key qual condition. + * Identify the "current" item among the input entry streams for this scan key + * that is greater than advancePast, and test whether it passes the scan key + * qual condition. * * The current item is the smallest curItem among the inputs. key->curItem * is set to that value. key->curItemMatches is set to indicate whether that @@ -719,7 +733,8 @@ entryGetItem(GinState *ginstate, GinScanEntry entry) * logic in scanGetItem.) */ static void -keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key) +keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, + ItemPointerData advancePast) { ItemPointerData minItem; ItemPointerData curPageLossy; @@ -729,11 +744,20 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key) GinScanEntry entry; bool res; MemoryContext oldCtx; + bool allFinished; Assert(!key->isFinished); /* - * Find the minimum of the active entry curItems. + * 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 + * had to set curItem to a lossy-page pointer.) + */ + if (ginCompareItemPointers(&key->curItem, &advancePast) > 0) + return; + + /* + * Find the minimum item > advancePast among the active entry streams. * * Note: a lossy-page entry is encoded by a ItemPointer with max value for * offset (0xffff), so that it will sort after any exact entries for the @@ -741,16 +765,33 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key) * pointers, which is good. */ ItemPointerSetMax(&minItem); - + allFinished = true; for (i = 0; i < key->nentries; i++) { entry = key->scanEntry[i]; - if (entry->isFinished == FALSE && - ginCompareItemPointers(&entry->curItem, &minItem) < 0) - minItem = entry->curItem; + + /* + * Advance this stream if necessary. + * + * In particular, since entry->curItem was initialized with + * ItemPointerSetMin, this ensures we fetch the first item for each + * entry on the first call. + */ + while (entry->isFinished == FALSE && + ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + { + entryGetItem(ginstate, entry, advancePast); + } + + if (!entry->isFinished) + { + allFinished = FALSE; + if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) + minItem = entry->curItem; + } } - if (ItemPointerIsMax(&minItem)) + if (allFinished) { /* all entries are finished */ key->isFinished = TRUE; @@ -758,15 +799,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 - * had to set curItem to a lossy-page pointer.) - */ - if (ginCompareItemPointers(&key->curItem, &minItem) >= 0) - return; - - /* - * OK, advance key->curItem and perform consistentFn test. + * OK, set key->curItem and perform consistentFn test. */ key->curItem = minItem; @@ -895,117 +928,120 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key) * keyGetItem() the combination logic is known only to the consistentFn. */ static bool -scanGetItem(IndexScanDesc scan, ItemPointer advancePast, +scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, ItemPointerData *item, bool *recheck) { GinScanOpaque so = (GinScanOpaque) scan->opaque; - GinState *ginstate = &so->ginstate; - ItemPointerData myAdvancePast = *advancePast; uint32 i; - bool allFinished; bool match; - for (;;) + /*---------- + * Advance the scan keys in lock-step, until we find an item that + * matches all the keys. If any key reports isFinished, meaning its + * subset of the entries is exhausted, we can stop. Otherwise, set + * *item to the next matching item. + * + * Now *item contains the first ItemPointer after previous result that + * passed the consistentFn check for that exact TID, or a lossy reference + * to the same page. + * + * This logic works only if a keyGetItem stream can never contain both + * exact and lossy pointers for the same page. Else we could have a + * case like + * + * stream 1 stream 2 + * ... ... + * 42/6 42/7 + * 50/1 42/0xffff + * ... ... + * + * We would conclude that 42/6 is not a match and advance stream 1, + * thus never detecting the match to the lossy pointer in stream 2. + * (keyGetItem has a similar problem versus entryGetItem.) + *---------- + */ + ItemPointerSetMin(item); + do { - /* - * Advance any entries that are <= myAdvancePast. In particular, - * since entry->curItem was initialized with ItemPointerSetMin, this - * ensures we fetch the first item for each entry on the first call. - */ - allFinished = TRUE; - - for (i = 0; i < so->totalentries; i++) - { - GinScanEntry entry = so->entries[i]; - - while (entry->isFinished == FALSE && - ginCompareItemPointers(&entry->curItem, - &myAdvancePast) <= 0) - entryGetItem(ginstate, entry); - - if (entry->isFinished == FALSE) - allFinished = FALSE; - } - - if (allFinished) - { - /* all entries exhausted, so we're done */ - return false; - } - - /* - * Perform the consistentFn test for each scan key. If any key - * reports isFinished, meaning its subset of the entries is exhausted, - * we can stop. Otherwise, set *item to the minimum of the key - * curItems. - */ - ItemPointerSetMax(item); - - for (i = 0; i < so->nkeys; i++) + match = true; + for (i = 0; i < so->nkeys && match; i++) { GinScanKey key = so->keys + i; - keyGetItem(&so->ginstate, so->tempCtx, key); + /* Fetch the next item for this key. */ + keyGetItem(&so->ginstate, so->tempCtx, key, advancePast); if (key->isFinished) - return false; /* finished one of keys */ - - if (ginCompareItemPointers(&key->curItem, item) < 0) - *item = key->curItem; - } + return false; - Assert(!ItemPointerIsMax(item)); + /* + * If it's not a match, we can immediately conclude that nothing + * <= this item matches, without checking the rest of the keys. + */ + if (!key->curItemMatches) + { + advancePast = key->curItem; + match = false; + break; + } - /*---------- - * Now *item contains first ItemPointer after previous result. - * - * The item is a valid hit only if all the keys succeeded for either - * that exact TID, or a lossy reference to the same page. - * - * This logic works only if a keyGetItem stream can never contain both - * exact and lossy pointers for the same page. Else we could have a - * case like - * - * stream 1 stream 2 - * ... ... - * 42/6 42/7 - * 50/1 42/0xffff - * ... ... - * - * We would conclude that 42/6 is not a match and advance stream 1, - * thus never detecting the match to the lossy pointer in stream 2. - * (keyGetItem has a similar problem versus entryGetItem.) - *---------- - */ - match = true; - for (i = 0; i < so->nkeys; i++) - { - GinScanKey key = so->keys + i; + /* + * It's a match. We can conclude that nothing < matches, so + * the other key streams can skip to this item. + * Beware of lossy pointers, though; for a lossy pointer, we + * can only conclude that nothing smaller than this *page* + * matches. + */ + advancePast = key->curItem; + if (ItemPointerIsLossyPage(&advancePast)) + { + advancePast.ip_posid = 0; + } + else + { + Assert(advancePast.ip_posid > 0); + advancePast.ip_posid--; + } - if (key->curItemMatches) + /* + * If this is the first key, remember this location as a + * potential match. + * + * Otherwise, check if this is the same item that we checked the + * previous keys for (or a lossy pointer for the same page). If + * not, loop back to check the previous keys for this item (we + * will check this key again too, but keyGetItem returns quickly + * for that) + */ + if (i == 0) { - if (ginCompareItemPointers(item, &key->curItem) == 0) - continue; - if (ItemPointerIsLossyPage(&key->curItem) && - GinItemPointerGetBlockNumber(&key->curItem) == - GinItemPointerGetBlockNumber(item)) - continue; + *item = key->curItem; + } + else + { + if (ItemPointerIsLossyPage(&key->curItem) || + ItemPointerIsLossyPage(item)) + { + Assert (GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item)); + match = (GinItemPointerGetBlockNumber(&key->curItem) == + GinItemPointerGetBlockNumber(item)); + } + else + { + Assert(ginCompareItemPointers(&key->curItem, item) >= 0); + match = (ginCompareItemPointers(&key->curItem, item) == 0); + } } - match = false; - break; } + } while (!match); - if (match) - break; - - /* - * No hit. Update myAdvancePast to this TID, so that on the next pass - * we'll move to the next possible entry. - */ - myAdvancePast = *item; - } + Assert(!ItemPointerIsMin(item)); /* + * Now *item contains the first ItemPointer after previous result that + * passed the consistentFn check for that exact TID, or a lossy reference + * to the same page. + * * We must return recheck = true if any of the keys are marked recheck. */ *recheck = false; @@ -1536,7 +1572,7 @@ gingetbitmap(PG_FUNCTION_ARGS) { CHECK_FOR_INTERRUPTS(); - if (!scanGetItem(scan, &iptr, &iptr, &recheck)) + if (!scanGetItem(scan, iptr, &iptr, &recheck)) break; if (ItemPointerIsLossyPage(&iptr)) -- 1.8.5.2 --------------060203020309040604030703 Content-Type: text/x-diff; name="0002-Further-optimize-the-multi-key-GIN-searches.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0002-Further-optimize-the-multi-key-GIN-searches.patch" From 85e27d2aa08d134e03cb81026111c890c4778fb0 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Thu, 23 Jan 2014 15:47:54 +0200 Subject: [PATCH 2/4] Further optimize the multi-key GIN searches. If we're skipping past a certain TID, avoid decoding posting list segments that only contain smaller TIDs. --- src/backend/access/gin/gindatapage.c | 32 +++++++++++++++++++++++++++++--- src/backend/access/gin/ginget.c | 6 ++++-- src/include/access/gin_private.h | 2 +- 3 files changed, 34 insertions(+), 6 deletions(-) diff --git a/src/backend/access/gin/gindatapage.c b/src/backend/access/gin/gindatapage.c index 91934f0..534dae3 100644 --- a/src/backend/access/gin/gindatapage.c +++ b/src/backend/access/gin/gindatapage.c @@ -97,18 +97,44 @@ static void dataPlaceToPageLeafSplit(Buffer buf, /* * Read all TIDs from leaf data page to single uncompressed array. + * + * If advancePast is valid, the caller is only interested in TIDs > advancePast. + * This function can still return items smaller than that, so the caller + * must still check them, but passing it allows this function to skip some + * items as an optimization. */ ItemPointer -GinDataLeafPageGetItems(Page page, int *nitems) +GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast) { ItemPointer result; if (GinPageIsCompressed(page)) { - GinPostingList *ptr = GinDataLeafPageGetPostingList(page); + GinPostingList *seg = GinDataLeafPageGetPostingList(page); Size len = GinDataLeafPageGetPostingListSize(page); + Pointer endptr = ((Pointer) seg) + len; + GinPostingList *next; - result = ginPostingListDecodeAllSegments(ptr, len, nitems); + /* Skip to the segment containing advancePast+1 */ + if (ItemPointerIsValid(&advancePast)) + { + next = GinNextPostingListSegment(seg); + while ((Pointer) next < endptr && + ginCompareItemPointers(&next->first, &advancePast) <= 0) + { + seg = next; + next = GinNextPostingListSegment(seg); + } + len = endptr - (Pointer) seg; + } + + if (len > 0) + result = ginPostingListDecodeAllSegments(seg, len, nitems); + else + { + result = palloc(0); + *nitems = 0; + } } else { diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index 4e4b51a..e303700 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -400,6 +400,7 @@ restartScanEntry: BlockNumber rootPostingTree = GinGetPostingTree(itup); GinBtreeStack *stack; Page page; + ItemPointerData minItem; /* * We should unlock entry page before touching posting tree to @@ -426,7 +427,8 @@ restartScanEntry: /* * Load the first page into memory. */ - entry->list = GinDataLeafPageGetItems(page, &entry->nlist); + ItemPointerSetMin(&minItem); + entry->list = GinDataLeafPageGetItems(page, &entry->nlist, minItem); entry->predictNumberResult = stack->predictNumber * entry->nlist; @@ -556,7 +558,7 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advan continue; } - entry->list = GinDataLeafPageGetItems(page, &entry->nlist); + entry->list = GinDataLeafPageGetItems(page, &entry->nlist, advancePast); for (i = 0; i < entry->nlist; i++) { diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index 3f92c37..8c350b9 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -692,7 +692,7 @@ extern ItemPointer ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup, int *nitems); /* gindatapage.c */ -extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems); +extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerData advancePast); extern int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm); extern BlockNumber createPostingTree(Relation index, ItemPointerData *items, uint32 nitems, -- 1.8.5.2 --------------060203020309040604030703 Content-Type: text/x-diff; name="0003-Further-optimize-GIN-multi-key-searches.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0003-Further-optimize-GIN-multi-key-searches.patch" From 13792c0d32fc97f2b0a4ff6543858f0ef0d8c2a7 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Thu, 23 Jan 2014 16:55:51 +0200 Subject: [PATCH 3/4] Further optimize GIN multi-key searches. When skipping over some items in a posting tree, re-find the new location by descending the tree from root, rather than walking the right links. This can save a lot of I/O. --- src/backend/access/gin/gindatapage.c | 9 ++-- src/backend/access/gin/ginget.c | 90 +++++++++++++++++++++++++++--------- src/include/access/gin_private.h | 3 +- 3 files changed, 75 insertions(+), 27 deletions(-) diff --git a/src/backend/access/gin/gindatapage.c b/src/backend/access/gin/gindatapage.c index 534dae3..2f86c6a 100644 --- a/src/backend/access/gin/gindatapage.c +++ b/src/backend/access/gin/gindatapage.c @@ -1635,16 +1635,15 @@ ginInsertItemPointers(Relation index, BlockNumber rootBlkno, * Starts a new scan on a posting tree. */ GinBtreeStack * -ginScanBeginPostingTree(Relation index, BlockNumber rootBlkno) +ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno) { - GinBtreeData btree; GinBtreeStack *stack; - ginPrepareDataScan(&btree, index, rootBlkno); + ginPrepareDataScan(btree, index, rootBlkno); - btree.fullScan = TRUE; + btree->fullScan = TRUE; - stack = ginFindLeafPage(&btree, TRUE); + stack = ginFindLeafPage(btree, TRUE); return stack; } diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index e303700..4285a03 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -99,12 +99,13 @@ static void scanPostingTree(Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree) { + GinBtreeData btree; GinBtreeStack *stack; Buffer buffer; Page page; /* Descend to the leftmost leaf page */ - stack = ginScanBeginPostingTree(index, rootPostingTree); + stack = ginScanBeginPostingTree(&btree, index, rootPostingTree); buffer = stack->buffer; IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */ @@ -412,7 +413,8 @@ restartScanEntry: LockBuffer(stackEntry->buffer, GIN_UNLOCK); needUnlock = FALSE; - stack = ginScanBeginPostingTree(ginstate->index, rootPostingTree); + stack = ginScanBeginPostingTree(&entry->btree, ginstate->index, + rootPostingTree); entry->buffer = stack->buffer; /* @@ -506,8 +508,50 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advan { Page page; int i; + bool stepright; + + /* + * We have two strategies for finding the correct page: step right from + * the current page, or descend the tree again from the root. If + * advancePast equals the current item, the next matching item should be + * on the next page, so we step right. Otherwise, descend from root. + */ + if (ginCompareItemPointers(&entry->curItem, &advancePast) == 0) + { + stepright = true; + LockBuffer(entry->buffer, GIN_SHARE); + } + else + { + GinBtreeStack *stack; + + ReleaseBuffer(entry->buffer); + + /* + * Set the search key, and find the correct leaf page. + * + * XXX: This is off by one, we're searching for an item > advancePast, + * but we're asking the tree for the next item >= advancePast. It only + * makes a difference in the corner case that advancePast is the + * right bound of a page, in which case we'll scan one page + * unnecessarily. Other than that it's harmless. + */ + entry->btree.itemptr = advancePast; + entry->btree.fullScan = false; + stack = ginFindLeafPage(&entry->btree, true); + + /* we don't need the stack, just the buffer. */ + entry->buffer = stack->buffer; + IncrBufferRefCount(entry->buffer); + freeGinBtreeStack(stack); + stepright = false; + } + + elog(DEBUG2, "entryLoadMoreItems, %u/%u, skip: %d", + GinItemPointerGetBlockNumber(&advancePast), + GinItemPointerGetOffsetNumber(&advancePast), + !stepright); - LockBuffer(entry->buffer, GIN_SHARE); page = BufferGetPage(entry->buffer); for (;;) { @@ -519,31 +563,35 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, ItemPointerData advan entry->nlist = 0; } - /* - * We've processed all the entries on this page. If it was the last - * page in the tree, we're done. - */ - if (GinPageRightMost(page)) + if (stepright) { - UnlockReleaseBuffer(entry->buffer); - entry->buffer = InvalidBuffer; - entry->isFinished = TRUE; - return; + /* + * We've processed all the entries on this page. If it was the last + * page in the tree, we're done. + */ + if (GinPageRightMost(page)) + { + UnlockReleaseBuffer(entry->buffer); + entry->buffer = InvalidBuffer; + entry->isFinished = TRUE; + return; + } + + /* + * Step to next page, following the right link. then find the first + * ItemPointer greater than advancePast. + */ + entry->buffer = ginStepRight(entry->buffer, + ginstate->index, + GIN_SHARE); + page = BufferGetPage(entry->buffer); } + stepright = true; if (GinPageGetOpaque(page)->flags & GIN_DELETED) continue; /* page was deleted by concurrent vacuum */ /* - * Step to next page, following the right link. then find the first - * ItemPointer greater than advancePast. - */ - entry->buffer = ginStepRight(entry->buffer, - ginstate->index, - GIN_SHARE); - page = BufferGetPage(entry->buffer); - - /* * The first item > advancePast might not be on this page, but * somewhere to the right, if the page was split. Keep following * the right-links until we re-find the correct page. diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index 8c350b9..a12dfc3 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -703,7 +703,7 @@ extern void GinPageDeletePostingItem(Page page, OffsetNumber offset); extern void ginInsertItemPointers(Relation index, BlockNumber rootBlkno, ItemPointerData *items, uint32 nitem, GinStatsData *buildStats); -extern GinBtreeStack *ginScanBeginPostingTree(Relation index, BlockNumber rootBlkno); +extern GinBtreeStack *ginScanBeginPostingTree(GinBtree btree, Relation index, BlockNumber rootBlkno); extern void ginDataFillRoot(GinBtree btree, Page root, BlockNumber lblkno, Page lpage, BlockNumber rblkno, Page rpage); extern void ginPrepareDataScan(GinBtree btree, Relation index, BlockNumber rootBlkno); @@ -803,6 +803,7 @@ typedef struct GinScanEntryData bool isFinished; bool reduceResult; uint32 predictNumberResult; + GinBtreeData btree; } GinScanEntryData; typedef struct GinScanOpaqueData -- 1.8.5.2 --------------060203020309040604030703 Content-Type: text/x-diff; name="0004-Add-the-concept-of-a-ternary-consistent-check-and-us.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0004-Add-the-concept-of-a-ternary-consistent-check-and-us.pa"; filename*1="tch" From c9087c8d5d3501deceb433966206d4d69e135042 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Thu, 23 Jan 2014 23:08:43 +0200 Subject: [PATCH 4/4] Add the concept of a ternary consistent check, and use it to skip entries. When we have loaded the next item from some, but not all, entries in a scan, it might be possible to prove that there cannot be any matches with smaller item pointer coming from the other entries. In that case, we can fast-forward those entries to the smallest item among the already-fetched sources. There is no support for opclass-defined ternary consistent functions yet, but there is a shim function that calls the regular, boolean, consistent function "both ways", when only one input is unknown. Per the concept by Alexander Korotkov --- src/backend/access/gin/Makefile | 2 +- src/backend/access/gin/ginget.c | 414 ++++++++++++++++++++++---------------- src/backend/access/gin/ginlogic.c | 136 +++++++++++++ src/include/access/gin_private.h | 23 ++- 4 files changed, 397 insertions(+), 178 deletions(-) create mode 100644 src/backend/access/gin/ginlogic.c 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 4285a03..f2f9dc6 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 */ @@ -460,6 +425,8 @@ startScanKey(GinState *ginstate, GinScanKey key) key->curItemMatches = false; key->recheckCurItem = false; key->isFinished = false; + + GinInitConsistentMethod(ginstate, key); } static void @@ -789,18 +756,19 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, ItemPointerData minItem; ItemPointerData curPageLossy; uint32 i; - uint32 lossyEntry; bool haveLossyEntry; GinScanEntry entry; - bool res; MemoryContext oldCtx; bool allFinished; + bool allUnknown; + int minUnknown; + GinLogicValue res; Assert(!key->isFinished); /* * 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) @@ -814,155 +782,256 @@ keyGetItem(GinState *ginstate, MemoryContext tempCtx, GinScanKey key, * same page. So we'll prefer to return exact pointers not lossy * pointers, which is good. */ - ItemPointerSetMax(&minItem); - allFinished = true; - for (i = 0; i < key->nentries; i++) + oldCtx = CurrentMemoryContext; + + for (;;) { - entry = key->scanEntry[i]; + ItemPointerSetMax(&minItem); + allFinished = true; + allUnknown = true; + minUnknown = -1; + for (i = 0; i < key->nentries; i++) + { + entry = key->scanEntry[i]; - /* - * Advance this stream if necessary. - * - * In particular, since entry->curItem was initialized with - * 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 (entry->isFinished) + continue; + allFinished = false; + + if (!entry->isFinished && + ginCompareItemPointers(&entry->curItem, &advancePast) > 0) + { + allUnknown = false; + if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) + minItem = entry->curItem; + } + else if (minUnknown == -1) + minUnknown = i; + } + + if (allFinished) { - entryGetItem(ginstate, entry, advancePast); + /* all entries are finished */ + key->isFinished = TRUE; + return; } - if (!entry->isFinished) + if (allUnknown) { - allFinished = FALSE; - if (ginCompareItemPointers(&entry->curItem, &minItem) < 0) - minItem = entry->curItem; + /* + * We must have an item from at least one source to have a match. + * Fetch the next item > advancePast from the first (non-finished) + * entry stream. + */ + entry = key->scanEntry[minUnknown]; + entryGetItem(ginstate, entry, advancePast); + continue; } - } - if (allFinished) - { - /* all entries are finished */ - key->isFinished = TRUE; - return; - } + /* + * We now have minItem set to the minimum among input streams *that* + * we know. Some streams might be in unknown state, meaning we don't + * know the next value from that input. + * + * Determine if any items between advancePast and minItem might match. + * Such items might come from one of the unknown sources, but it's + * possible that the consistent function can refute them all, ie. + * the consistent logic says that they cannot match without any of the + * sources that we have loaded. + */ + if (minUnknown != -1) + { + for (i = 0; i < key->nentries; i++) + { + entry = key->scanEntry[i]; + if (entry->isFinished) + key->entryRes[i] = GIN_FALSE; + else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + { + /* this source is 'unloaded' */ + key->entryRes[i] = GIN_MAYBE; + } + else + { + /* + * we know the next item from this source to be >= minItem, + * hence it's false for any items before < minItem + */ + key->entryRes[i] = GIN_FALSE; + } + } - /* - * OK, set key->curItem and perform consistentFn test. - */ - key->curItem = minItem; + MemoryContextSwitchTo(tempCtx); + res = key->triConsistentFn(key); + MemoryContextSwitchTo(oldCtx); - /* - * 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 - * 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. - * - * 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. - */ - ItemPointerSetLossyPage(&curPageLossy, - GinItemPointerGetBlockNumber(&key->curItem)); + if (res == GIN_FALSE) + { + /* + * All items between advancePast and minItem have been refuted. + * Proceed with minItem. + */ + advancePast = minItem; + advancePast.ip_posid--; + } + else + { + /* + * There might be matches smaller than minItem coming from one + * of the unknown sources. Load more items, and retry. + */ + entry = key->scanEntry[minUnknown]; + entryGetItem(ginstate, entry, advancePast); + continue; + } + } - lossyEntry = 0; - haveLossyEntry = false; - for (i = 0; i < key->nentries; i++) - { - entry = key->scanEntry[i]; - if (entry->isFinished == FALSE && - ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0) + /* + * Ok, we now know that there are no matches < minItem. Proceed to + * check if it's a match. + */ + key->curItem = minItem; + ItemPointerSetLossyPage(&curPageLossy, + GinItemPointerGetBlockNumber(&minItem)); + + /* + * 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. + * + * 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.) + * + * An exception is that we don't need to try it both ways (ie. pass + * MAYBE) if the lossy pointer is in a "hidden" entry, because the + * consistentFn's result can't depend on that (but mark the result as + * 'recheck'). + * + * 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. + */ + haveLossyEntry = false; + for (i = 0; i < key->nentries; i++) { - if (haveLossyEntry) + entry = key->scanEntry[i]; + if (entry->isFinished == FALSE && + ginCompareItemPointers(&entry->curItem, &curPageLossy) == 0) { - /* Multiple lossy entries, punt */ + key->entryRes[i] = GIN_MAYBE; + haveLossyEntry = true; + } + else + key->entryRes[i] = GIN_FALSE; + } + + if (haveLossyEntry) + { + MemoryContextSwitchTo(tempCtx); + res = key->triConsistentFn(key); + MemoryContextSwitchTo(oldCtx); + + if (res == GIN_TRUE || res == GIN_MAYBE) + { + /* Some of the lossy items on the heap page might match, punt */ key->curItem = curPageLossy; key->curItemMatches = true; key->recheckCurItem = true; return; } - lossyEntry = i; - haveLossyEntry = true; } - } - /* prepare for calling consistentFn in temp context */ - oldCtx = MemoryContextSwitchTo(tempCtx); + /* + * Let's call the consistent function to check if this is a match. + * + * 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. 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. + * + * We might also not have advanced all the entry streams up to this + * point yet. It's possible that the consistent function can + * nevertheless decide that this is definitely a match or not a match, + * even though we don't know if those unknown entries match, so we + * pass them as MAYBE. + */ + for (i = 0; i < key->nentries; i++) + { + entry = key->scanEntry[i]; + if (entry->isFinished) + key->entryRes[i] = GIN_FALSE; + else if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0) + key->entryRes[i] = GIN_MAYBE; /* not loaded yet */ + 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] = GIN_FALSE; + } - if (haveLossyEntry) - { - /* Single lossy-page entry, so see if whole page matches */ - memset(key->entryRes, FALSE, key->nentries); - key->entryRes[lossyEntry] = TRUE; + MemoryContextSwitchTo(tempCtx); + res = key->triConsistentFn(key); + MemoryContextSwitchTo(oldCtx); - if (callConsistentFn(ginstate, key)) + switch (res) { - /* Yes, so clean up ... */ - MemoryContextSwitchTo(oldCtx); - MemoryContextReset(tempCtx); - - /* and return lossy pointer for whole page */ - key->curItem = curPageLossy; - key->curItemMatches = true; - key->recheckCurItem = true; - return; - } - } + case GIN_TRUE: + key->curItemMatches = true; + /* triConsistentFn set recheckCurItem */ + break; - /* - * 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. - * - * 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; - else - key->entryRes[i] = FALSE; - } - if (haveLossyEntry) - key->entryRes[lossyEntry] = TRUE; + case GIN_FALSE: + key->curItemMatches = false; + break; - res = callConsistentFn(ginstate, key); + case GIN_MAYBE: + /* + * The consistent function cannot decide with the information + * we've got. If there are any "unknown" sources left, advance + * one of them and try again, in the hope that it can decide + * with the extra information. + */ + if (minUnknown != -1) + { + entry = key->scanEntry[minUnknown]; + entryGetItem(ginstate, entry, advancePast); + continue; + } + key->curItemMatches = true; + key->recheckCurItem = true; + break; - if (!res && haveLossyEntry && lossyEntry < key->nuserentries) - { - /* try the other way for the lossy item */ - key->entryRes[lossyEntry] = FALSE; + 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; + } - res = callConsistentFn(ginstate, key); + /* + * We have a tuple, and we know if it mathes 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. + */ + break; } - key->curItemMatches = res; - /* If we matched a lossy entry, force recheckCurItem = true */ - if (haveLossyEntry) - key->recheckCurItem = true; - /* clean up after consistentFn calls */ MemoryContextSwitchTo(oldCtx); MemoryContextReset(tempCtx); @@ -1055,7 +1124,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 @@ -1066,21 +1135,20 @@ scanGetItem(IndexScanDesc scan, ItemPointerData advancePast, if (i == 0) { *item = key->curItem; + continue; + } + + if (ItemPointerIsLossyPage(&key->curItem) || + ItemPointerIsLossyPage(item)) + { + Assert (GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item)); + match = (GinItemPointerGetBlockNumber(&key->curItem) == + GinItemPointerGetBlockNumber(item)); } else { - if (ItemPointerIsLossyPage(&key->curItem) || - ItemPointerIsLossyPage(item)) - { - Assert (GinItemPointerGetBlockNumber(&key->curItem) >= GinItemPointerGetBlockNumber(item)); - match = (GinItemPointerGetBlockNumber(&key->curItem) == - GinItemPointerGetBlockNumber(item)); - } - else - { - Assert(ginCompareItemPointers(&key->curItem, item) >= 0); - match = (ginCompareItemPointers(&key->curItem, item) == 0); - } + Assert(ginCompareItemPointers(&key->curItem, item) >= 0); + match = (ginCompareItemPointers(&key->curItem, item) == 0); } } } while (!match); @@ -1297,7 +1365,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); @@ -1554,7 +1622,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..e499c6e --- /dev/null +++ b/src/backend/access/gin/ginlogic.c @@ -0,0 +1,136 @@ +/*------------------------------------------------------------------------- + * + * 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. + * + * If there is only one MAYBE input, our strategy is to try the consistentFn + * both ways. If it returns TRUE for both, the tuple matches regardless of + * the MAYBE input, so we return TRUE. Likewise, if it returns FALSE for both, + * we return FALSE. Otherwise return MAYBE. + */ +static GinLogicValue +shimTriConsistentFn(GinScanKey key) +{ + bool foundMaybe = false; + int maybeEntry = -1; + int i; + bool boolResult1; + bool boolResult2; + bool recheck1; + bool recheck2; + + for (i = 0; i < key->nentries; i++) + { + if (key->entryRes[i] == GIN_MAYBE) + { + if (foundMaybe) + return GIN_MAYBE; /* more than one MAYBE input */ + maybeEntry = i; + foundMaybe = true; + } + } + + /* + * If none of the inputs were MAYBE, so we can just call consistent + * function as is. + */ + if (!foundMaybe) + return normalBoolConsistentFn(key); + + /* Try the consistent function with the maybe-input set both ways */ + key->entryRes[maybeEntry] = GIN_TRUE; + boolResult1 = normalBoolConsistentFn(key); + recheck1 = key->recheckCurItem; + + key->entryRes[maybeEntry] = GIN_FALSE; + boolResult2 = normalBoolConsistentFn(key); + recheck2 = key->recheckCurItem; + + if (!boolResult1 && !boolResult2) + return GIN_FALSE; + + key->recheckCurItem = recheck1 || recheck2; + if (boolResult1 && boolResult2) + return GIN_TRUE; + else + return GIN_MAYBE; +} + +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/include/access/gin_private.h b/src/include/access/gin_private.h index a12dfc3..6d6a49a 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); @@ -733,10 +748,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) */ @@ -749,6 +760,10 @@ typedef struct GinScanKeyData /* 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; -- 1.8.5.2 --------------060203020309040604030703 Content-Type: text/plain Content-Disposition: inline Content-Transfer-Encoding: 8bit MIME-Version: 1.0 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers --------------060203020309040604030703--