From fa194ee8db4590b607cfbf4ae3889ad9ff2ca33e Mon Sep 17 00:00:00 2001 From: shubhambaraiss Date: Tue, 11 Jul 2017 05:26:52 +0530 Subject: [PATCH] Predicate locking in gin index --- src/backend/access/gin/ginbtree.c | 22 + src/backend/access/gin/gindatapage.c | 10 +- src/backend/access/gin/ginget.c | 50 +- src/backend/access/gin/gininsert.c | 18 +- src/backend/access/gin/ginutil.c | 2 +- src/backend/access/gin/ginvacuum.c | 12 +- src/backend/storage/lmgr/README-SSI | 11 + src/include/access/gin_private.h | 2 +- src/test/isolation/expected/predicate-gin.out | 799 ++++++++++++++++++++++++++ src/test/isolation/isolation_schedule | 1 + src/test/isolation/specs/predicate-gin.spec | 120 ++++ 11 files changed, 1033 insertions(+), 14 deletions(-) create mode 100644 src/test/isolation/expected/predicate-gin.out create mode 100644 src/test/isolation/specs/predicate-gin.spec diff --git a/src/backend/access/gin/ginbtree.c b/src/backend/access/gin/ginbtree.c index b02cb8a..8184dc0 100644 --- a/src/backend/access/gin/ginbtree.c +++ b/src/backend/access/gin/ginbtree.c @@ -17,6 +17,7 @@ #include "access/gin_private.h" #include "access/ginxlog.h" #include "access/xloginsert.h" +#include "storage/predicate.h" #include "miscadmin.h" #include "utils/memutils.h" #include "utils/rel.h" @@ -515,6 +516,19 @@ ginPlaceToPage(GinBtree btree, GinBtreeStack *stack, btree->fillRoot(btree, newrootpg, BufferGetBlockNumber(lbuffer), newlpage, BufferGetBlockNumber(rbuffer), newrpage); + + if (GinPageIsLeaf(BufferGetPage(stack->buffer))) + { + + PredicateLockPageSplit(btree->index, + BufferGetBlockNumber(stack->buffer), + BufferGetBlockNumber(lbuffer)); + + PredicateLockPageSplit(btree->index, + BufferGetBlockNumber(stack->buffer), + BufferGetBlockNumber(rbuffer)); + } + } else { @@ -524,6 +538,14 @@ ginPlaceToPage(GinBtree btree, GinBtreeStack *stack, GinPageGetOpaque(newrpage)->rightlink = savedRightLink; GinPageGetOpaque(newlpage)->flags |= GIN_INCOMPLETE_SPLIT; GinPageGetOpaque(newlpage)->rightlink = BufferGetBlockNumber(rbuffer); + + if (GinPageIsLeaf(BufferGetPage(stack->buffer))) + { + + PredicateLockPageSplit(btree->index, + BufferGetBlockNumber(stack->buffer), + BufferGetBlockNumber(rbuffer)); + } } /* diff --git a/src/backend/access/gin/gindatapage.c b/src/backend/access/gin/gindatapage.c index 2e5ea47..0a3f22f 100644 --- a/src/backend/access/gin/gindatapage.c +++ b/src/backend/access/gin/gindatapage.c @@ -20,6 +20,7 @@ #include "lib/ilist.h" #include "miscadmin.h" #include "utils/rel.h" +#include "storage/predicate.h" /* * Min, Max and Target size of posting lists stored on leaf pages, in bytes. @@ -1759,7 +1760,7 @@ leafRepackItems(disassembledLeaf *leaf, ItemPointer remaining) */ BlockNumber createPostingTree(Relation index, ItemPointerData *items, uint32 nitems, - GinStatsData *buildStats) + GinStatsData *buildStats, Buffer entrybuffer) { BlockNumber blkno; Buffer buffer; @@ -1810,6 +1811,12 @@ createPostingTree(Relation index, ItemPointerData *items, uint32 nitems, page = BufferGetPage(buffer); blkno = BufferGetBlockNumber(buffer); + /* + * Copy a predicate lock from entry tree leaf (containing posting list) + * to posting tree. + */ + PredicateLockPageSplit(index, BufferGetBlockNumber(entrybuffer), blkno); + START_CRIT_SECTION(); PageRestoreTempPage(tmppage, page); @@ -1904,6 +1911,7 @@ ginInsertItemPointers(Relation index, BlockNumber rootBlkno, btree.itemptr = insertdata.items[insertdata.curitem]; stack = ginFindLeafPage(&btree, false, NULL); + CheckForSerializableConflictIn(btree.index, NULL, stack->buffer); ginInsertValue(&btree, stack, &insertdata, buildStats); } } diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c index 56a5bf4..13c5304 100644 --- a/src/backend/access/gin/ginget.c +++ b/src/backend/access/gin/ginget.c @@ -16,9 +16,11 @@ #include "access/gin_private.h" #include "access/relscan.h" +#include "storage/predicate.h" #include "miscadmin.h" #include "utils/datum.h" #include "utils/memutils.h" +#include "utils/rel.h" /* GUC parameter */ int GinFuzzySearchLimit = 0; @@ -37,7 +39,7 @@ typedef struct pendingPosition * Goes to the next page if current offset is outside of bounds */ static bool -moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack) +moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack, Snapshot snapshot) { Page page = BufferGetPage(stack->buffer); @@ -51,6 +53,8 @@ moveRightIfItNeeded(GinBtreeData *btree, GinBtreeStack *stack) stack->buffer = ginStepRight(stack->buffer, btree->index, GIN_SHARE); stack->blkno = BufferGetBlockNumber(stack->buffer); + if (!GinGetUseFastUpdate(btree->index)) + PredicateLockPage(btree->index, stack->blkno, snapshot); stack->off = FirstOffsetNumber; } @@ -73,6 +77,10 @@ scanPostingTree(Relation index, GinScanEntry scanEntry, /* Descend to the leftmost leaf page */ stack = ginScanBeginPostingTree(&btree, index, rootPostingTree, snapshot); buffer = stack->buffer; + + if (!GinGetUseFastUpdate(index)) + PredicateLockPage(index, BufferGetBlockNumber(buffer), snapshot); + IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */ freeGinBtreeStack(stack); @@ -94,6 +102,9 @@ scanPostingTree(Relation index, GinScanEntry scanEntry, break; /* no more pages */ buffer = ginStepRight(buffer, index, GIN_SHARE); + + if (!GinGetUseFastUpdate(index)) + PredicateLockPage(index, BufferGetBlockNumber(buffer), snapshot); } UnlockReleaseBuffer(buffer); @@ -131,6 +142,9 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, attnum = scanEntry->attnum; attr = btree->ginstate->origTupdesc->attrs[attnum - 1]; + if (!GinGetUseFastUpdate(btree->index)) + PredicateLockPage(btree->index, stack->buffer, snapshot); + for (;;) { Page page; @@ -141,7 +155,7 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, /* * stack->off points to the interested entry, buffer is already locked */ - if (moveRightIfItNeeded(btree, stack) == false) + if (moveRightIfItNeeded(btree, stack, snapshot) == false) return true; page = BufferGetPage(stack->buffer); @@ -250,7 +264,7 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack, Datum newDatum; GinNullCategory newCategory; - if (moveRightIfItNeeded(btree, stack) == false) + if (moveRightIfItNeeded(btree, stack, snapshot) == false) elog(ERROR, "lost saved point in index"); /* must not happen !!! */ page = BufferGetPage(stack->buffer); @@ -323,6 +337,15 @@ restartScanEntry: ginstate); stackEntry = ginFindLeafPage(&btreeEntry, true, snapshot); page = BufferGetPage(stackEntry->buffer); + + /* + * If fast update is enabled, we acquire a predicate lock on the entire + * relation as fast update postpones the insertion of tuples into index + * structure due to which we can't detect rw conflicts. + */ + if (GinGetUseFastUpdate(ginstate->index)) + PredicateLockRelation(ginstate->index, snapshot); + /* ginFindLeafPage() will have already checked snapshot age. */ needUnlock = TRUE; @@ -391,6 +414,9 @@ restartScanEntry: rootPostingTree, snapshot); entry->buffer = stack->buffer; + if (!GinGetUseFastUpdate(ginstate->index)) + PredicateLockPage(ginstate->index, BufferGetBlockNumber(entry->buffer), snapshot); + /* * We keep buffer pinned because we need to prevent deletion of * page during scan. See GIN's vacuum implementation. RefCount is @@ -414,6 +440,9 @@ restartScanEntry: } else if (GinGetNPosting(itup) > 0) { + if (!GinGetUseFastUpdate(ginstate->index)) + PredicateLockPage(ginstate->index, BufferGetBlockNumber(stackEntry->buffer), snapshot); + entry->list = ginReadTuple(ginstate, entry->attnum, itup, &entry->nlist); entry->predictNumberResult = entry->nlist; @@ -633,6 +662,9 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, entry->btree.fullScan = false; stack = ginFindLeafPage(&entry->btree, true, snapshot); + if (!GinGetUseFastUpdate(ginstate->index)) + PredicateLockPage(ginstate->index, BufferGetBlockNumber(stack->buffer), snapshot); + /* we don't need the stack, just the buffer. */ entry->buffer = stack->buffer; IncrBufferRefCount(entry->buffer); @@ -677,6 +709,11 @@ entryLoadMoreItems(GinState *ginstate, GinScanEntry entry, entry->buffer = ginStepRight(entry->buffer, ginstate->index, GIN_SHARE); + + if (!GinGetUseFastUpdate(ginstate->index)) + PredicateLockPage(ginstate->index, BufferGetBlockNumber(entry->buffer), snapshot); + + page = BufferGetPage(entry->buffer); } stepright = true; @@ -1733,6 +1770,13 @@ scanPendingInsert(IndexScanDesc scan, TIDBitmap *tbm, int64 *ntids) return; } + /* + * If fast update is disabled, but some items still exist in the pending + * list, then a predicate lock on the entire relation is required. + */ + if (!GinGetUseFastUpdate(scan->indexRelation)) + PredicateLockRelation(scan->indexRelation, scan->xs_snapshot); + pos.pendingBuffer = ReadBuffer(scan->indexRelation, blkno); LockBuffer(pos.pendingBuffer, GIN_SHARE); pos.firstOffset = FirstOffsetNumber; diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c index 5378011..661b605 100644 --- a/src/backend/access/gin/gininsert.c +++ b/src/backend/access/gin/gininsert.c @@ -22,6 +22,7 @@ #include "storage/bufmgr.h" #include "storage/smgr.h" #include "storage/indexfsm.h" +#include "storage/predicate.h" #include "utils/memutils.h" #include "utils/rel.h" @@ -48,7 +49,7 @@ static IndexTuple addItemPointersToLeafTuple(GinState *ginstate, IndexTuple old, ItemPointerData *items, uint32 nitem, - GinStatsData *buildStats) + GinStatsData *buildStats, Buffer buffer) { OffsetNumber attnum; Datum key; @@ -99,7 +100,8 @@ addItemPointersToLeafTuple(GinState *ginstate, postingRoot = createPostingTree(ginstate->index, oldItems, oldNPosting, - buildStats); + buildStats, + buffer); /* Now insert the TIDs-to-be-added into the posting tree */ ginInsertItemPointers(ginstate->index, postingRoot, @@ -127,7 +129,7 @@ static IndexTuple buildFreshLeafTuple(GinState *ginstate, OffsetNumber attnum, Datum key, GinNullCategory category, ItemPointerData *items, uint32 nitem, - GinStatsData *buildStats) + GinStatsData *buildStats, Buffer buffer) { IndexTuple res = NULL; GinPostingList *compressedList; @@ -157,7 +159,7 @@ buildFreshLeafTuple(GinState *ginstate, * Initialize a new posting tree with the TIDs. */ postingRoot = createPostingTree(ginstate->index, items, nitem, - buildStats); + buildStats, buffer); /* And save the root link in the result tuple */ GinSetPostingTree(res, postingRoot); @@ -217,17 +219,19 @@ ginEntryInsert(GinState *ginstate, return; } + CheckForSerializableConflictIn(btree.index, NULL, stack->buffer); /* modify an existing leaf entry */ itup = addItemPointersToLeafTuple(ginstate, itup, - items, nitem, buildStats); + items, nitem, buildStats, stack->buffer); insertdata.isDelete = TRUE; } else { + CheckForSerializableConflictIn(btree.index, NULL, stack->buffer); /* no match, so construct a new leaf entry */ itup = buildFreshLeafTuple(ginstate, attnum, key, category, - items, nitem, buildStats); + items, nitem, buildStats, stack->buffer); } /* Insert the new or modified leaf tuple */ @@ -513,6 +517,8 @@ gininsert(Relation index, Datum *values, bool *isnull, memset(&collector, 0, sizeof(GinTupleCollector)); + CheckForSerializableConflictIn(index, NULL, InvalidBuffer); + for (i = 0; i < ginstate->origTupdesc->natts; i++) ginHeapTupleFastCollect(ginstate, &collector, (OffsetNumber) (i + 1), diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c index 91e4a8c..5cfb45d 100644 --- a/src/backend/access/gin/ginutil.c +++ b/src/backend/access/gin/ginutil.c @@ -49,7 +49,7 @@ ginhandler(PG_FUNCTION_ARGS) amroutine->amsearchnulls = false; amroutine->amstorage = true; amroutine->amclusterable = false; - amroutine->ampredlocks = false; + amroutine->ampredlocks = true; amroutine->amcanparallel = false; amroutine->amkeytype = InvalidOid; diff --git a/src/backend/access/gin/ginvacuum.c b/src/backend/access/gin/ginvacuum.c index 31425e9..1e52313 100644 --- a/src/backend/access/gin/ginvacuum.c +++ b/src/backend/access/gin/ginvacuum.c @@ -22,6 +22,7 @@ #include "postmaster/autovacuum.h" #include "storage/indexfsm.h" #include "storage/lmgr.h" +#include "storage/predicate.h" #include "utils/memutils.h" struct GinVacuumState @@ -153,11 +154,18 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn LockBuffer(lBuffer, GIN_EXCLUSIVE); + page = BufferGetPage(dBuffer); + rightlink = GinPageGetOpaque(page)->rightlink; + + /* + * Any insert which would have gone on the leaf block will now go to its + * right sibling. + */ + PredicateLockPageCombine(gvs->index, deleteBlkno, rightlink); + START_CRIT_SECTION(); /* Unlink the page by changing left sibling's rightlink */ - page = BufferGetPage(dBuffer); - rightlink = GinPageGetOpaque(page)->rightlink; page = BufferGetPage(lBuffer); GinPageGetOpaque(page)->rightlink = rightlink; diff --git a/src/backend/storage/lmgr/README-SSI b/src/backend/storage/lmgr/README-SSI index a9dc01f..6bbdfef 100644 --- a/src/backend/storage/lmgr/README-SSI +++ b/src/backend/storage/lmgr/README-SSI @@ -379,6 +379,17 @@ level during a GiST search. An index insert at the leaf level can then be trusted to ripple up to all levels and locations where conflicting predicate locks may exist. + * Gin searches acquire predicate locks only on the leaf pages +of entry tree and posting tree. We acquire a predicate lock on entry +tree leaf pages only when entry has a posting list. If entry tree has +a pointer to posting tree, we skip locking entry tree leaf page and lock +only posting tree leaf pages. If, however, fast update is enabled, a +predicate lock on the index relation is required as fast update postpones +the insertion of tuples into index structure by temporarily storing them +into pending list due to which we are unable to detect all r-w conflicts. +During a page split, a predicate lock is copied from the original page +to the new page. + * The effects of page splits, overflows, consolidations, and removals must be carefully reviewed to ensure that predicate locks aren't "lost" during those operations, or kept with pages which could diff --git a/src/include/access/gin_private.h b/src/include/access/gin_private.h index adfdb0c..03c4103 100644 --- a/src/include/access/gin_private.h +++ b/src/include/access/gin_private.h @@ -217,7 +217,7 @@ extern ItemPointer GinDataLeafPageGetItems(Page page, int *nitems, ItemPointerDa extern int GinDataLeafPageGetItemsToTbm(Page page, TIDBitmap *tbm); extern BlockNumber createPostingTree(Relation index, ItemPointerData *items, uint32 nitems, - GinStatsData *buildStats); + GinStatsData *buildStats, Buffer entrybuffer); extern void GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset); extern void GinPageDeletePostingItem(Page page, OffsetNumber offset); extern void ginInsertItemPointers(Relation index, BlockNumber rootBlkno, diff --git a/src/test/isolation/expected/predicate-gin.out b/src/test/isolation/expected/predicate-gin.out new file mode 100644 index 0000000..e80c897 --- /dev/null +++ b/src/test/isolation/expected/predicate-gin.out @@ -0,0 +1,799 @@ +Parsed test spec with 2 sessions + +starting permutation: rxy1 wx1 c1 rxy2 wy2 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10050 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; + +starting permutation: rxy2 wy2 c2 rxy1 wx1 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10050 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; + +starting permutation: rxy3 wx3 c1 rxy4 wy4 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; + +starting permutation: rxy4 wy4 c2 rxy3 wx3 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; + +starting permutation: rxy1 wx1 rxy2 c1 wy2 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step c1: COMMIT; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c2: COMMIT; + +starting permutation: rxy1 wx1 rxy2 wy2 c1 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 wx1 rxy2 wy2 c2 c1 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 rxy2 wx1 c1 wy2 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c2: COMMIT; + +starting permutation: rxy1 rxy2 wx1 wy2 c1 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 rxy2 wx1 wy2 c2 c1 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 rxy2 wy2 wx1 c1 c2 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 rxy2 wy2 wx1 c2 c1 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy1 rxy2 wy2 c2 wx1 c1 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c1: COMMIT; + +starting permutation: rxy2 rxy1 wx1 c1 wy2 c2 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c2: COMMIT; + +starting permutation: rxy2 rxy1 wx1 wy2 c1 c2 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 rxy1 wx1 wy2 c2 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 rxy1 wy2 wx1 c1 c2 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 rxy1 wy2 wx1 c2 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 rxy1 wy2 c2 wx1 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step c2: COMMIT; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c1: COMMIT; + +starting permutation: rxy2 wy2 rxy1 wx1 c1 c2 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c1: COMMIT; +step c2: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 wy2 rxy1 wx1 c2 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +step c2: COMMIT; +step c1: COMMIT; +ERROR: could not serialize access due to read/write dependencies among transactions + +starting permutation: rxy2 wy2 rxy1 c2 wx1 c1 +step rxy2: select count(*) from gin_tbl where p @> array[5,6]; +count + +10000 +step wy2: insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; +step rxy1: select count(*) from gin_tbl where p @> array[4,5]; +count + +10000 +step c2: COMMIT; +step wx1: insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; +ERROR: could not serialize access due to read/write dependencies among transactions +step c1: COMMIT; + +starting permutation: rxy3 wx3 rxy4 c1 wy4 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step c1: COMMIT; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; + +starting permutation: rxy3 wx3 rxy4 wy4 c1 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy3 wx3 rxy4 wy4 c2 c1 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy3 rxy4 wx3 c1 wy4 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; + +starting permutation: rxy3 rxy4 wx3 wy4 c1 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy3 rxy4 wx3 wy4 c2 c1 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy3 rxy4 wy4 wx3 c1 c2 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy3 rxy4 wy4 wx3 c2 c1 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy3 rxy4 wy4 c2 wx3 c1 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; + +starting permutation: rxy4 rxy3 wx3 c1 wy4 c2 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; + +starting permutation: rxy4 rxy3 wx3 wy4 c1 c2 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy4 rxy3 wx3 wy4 c2 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy4 rxy3 wy4 wx3 c1 c2 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy4 rxy3 wy4 wx3 c2 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy4 rxy3 wy4 c2 wx3 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step c2: COMMIT; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; + +starting permutation: rxy4 wy4 rxy3 wx3 c1 c2 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; +step c2: COMMIT; + +starting permutation: rxy4 wy4 rxy3 wx3 c2 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c2: COMMIT; +step c1: COMMIT; + +starting permutation: rxy4 wy4 rxy3 c2 wx3 c1 +step rxy4: + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + +count + +4 +step wy4: insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; +step rxy3: + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + +count + +4 +step c2: COMMIT; +step wx3: insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; +step c1: COMMIT; diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule index 32c965b..de9322b 100644 --- a/src/test/isolation/isolation_schedule +++ b/src/test/isolation/isolation_schedule @@ -62,3 +62,4 @@ test: sequence-ddl test: async-notify test: vacuum-reltuples test: timeouts +test: predicate-gin diff --git a/src/test/isolation/specs/predicate-gin.spec b/src/test/isolation/specs/predicate-gin.spec new file mode 100644 index 0000000..b362eb3 --- /dev/null +++ b/src/test/isolation/specs/predicate-gin.spec @@ -0,0 +1,120 @@ +# Test for page level predicate locking in gin +# +# Test to verify serialization failures and to check reduced false positives +# +# To verify serialization failures, queries and permutations are written in such +# a way that an index scan(from one transaction) and an index insert(from another +# transaction) will try to access the same part(sub-tree) of the index. +# +# To check reduced false positives, queries and permutations are written in such +# a way that an index scan(from one transaction) and an index insert(from another +# transaction) will try to access different parts(sub-tree) of the index. + + +setup +{ + create table gin_tbl(id int4, p int4[]); + create index ginidx on gin_tbl using gin(p) with + (fastupdate = off); + insert into gin_tbl select g, array[g, g*2,g*3] from generate_series(1, 10000) g; + insert into gin_tbl select g, array[4,5,6] from generate_series(10001, 20000) g; +} + +teardown +{ + DROP TABLE gin_tbl; +} + +session "s1" +setup { + BEGIN ISOLATION LEVEL SERIALIZABLE; + set enable_seqscan=off; + } +step "rxy1" { select count(*) from gin_tbl where p @> array[4,5]; } +step "wx1" { insert into gin_tbl select g, array[5,6] + from generate_series(20001, 20050) g; } +step "rxy3" { + select count(*) from gin_tbl where p @> array[1,2] or + p @> array[100,200] or p @> array[500,1000] or p @> array[1000,2000]; + } +step "wx3" { insert into gin_tbl select g, array[g,g*2] + from generate_series(1, 50) g; } +step "c1" { COMMIT; } + +session "s2" +setup { + BEGIN ISOLATION LEVEL SERIALIZABLE; + set enable_seqscan=off; + } + +step "rxy2" { select count(*) from gin_tbl where p @> array[5,6]; } +step "wy2" { insert into gin_tbl select g, array[4,5] + from generate_series(20051, 20100) g; } +step "rxy4" { + select count(*) from gin_tbl where p @> array[4000,8000] or + p @> array[5000,10000] or p @> array[6000,12000] or + p @> array[8000,16000]; + } +step "wy4" { insert into gin_tbl select g, array[g,g*2] + from generate_series(10000, 10050) g; } +step "c2" { COMMIT; } + +# An index scan(from one transaction) and an index insert(from another transaction) +# try to access the same part of the index but one transaction commits before other +# transaction begins so no r-w conflict. + +permutation "rxy1" "wx1" "c1" "rxy2" "wy2" "c2" +permutation "rxy2" "wy2" "c2" "rxy1" "wx1" "c1" + +# An index scan(from one transaction) and an index insert(from another transaction) +# try to access different parts of the index and also one transaction commits before +# other transaction begins, so no r-w conflict. + +permutation "rxy3" "wx3" "c1" "rxy4" "wy4" "c2" +permutation "rxy4" "wy4" "c2" "rxy3" "wx3" "c1" + + +# An index scan(from one transaction) and an index insert(from another transaction) +# try to access the same part of the index and one transaction begins before other +# transaction commits so there is a r-w conflict. + +permutation "rxy1" "wx1" "rxy2" "c1" "wy2" "c2" +permutation "rxy1" "wx1" "rxy2" "wy2" "c1" "c2" +permutation "rxy1" "wx1" "rxy2" "wy2" "c2" "c1" +permutation "rxy1" "rxy2" "wx1" "c1" "wy2" "c2" +permutation "rxy1" "rxy2" "wx1" "wy2" "c1" "c2" +permutation "rxy1" "rxy2" "wx1" "wy2" "c2" "c1" +permutation "rxy1" "rxy2" "wy2" "wx1" "c1" "c2" +permutation "rxy1" "rxy2" "wy2" "wx1" "c2" "c1" +permutation "rxy1" "rxy2" "wy2" "c2" "wx1" "c1" +permutation "rxy2" "rxy1" "wx1" "c1" "wy2" "c2" +permutation "rxy2" "rxy1" "wx1" "wy2" "c1" "c2" +permutation "rxy2" "rxy1" "wx1" "wy2" "c2" "c1" +permutation "rxy2" "rxy1" "wy2" "wx1" "c1" "c2" +permutation "rxy2" "rxy1" "wy2" "wx1" "c2" "c1" +permutation "rxy2" "rxy1" "wy2" "c2" "wx1" "c1" +permutation "rxy2" "wy2" "rxy1" "wx1" "c1" "c2" +permutation "rxy2" "wy2" "rxy1" "wx1" "c2" "c1" +permutation "rxy2" "wy2" "rxy1" "c2" "wx1" "c1" + +# An index scan(from one transaction) and an index insert(from another transaction) +# try to access different parts of the index so no r-w conflict. + +permutation "rxy3" "wx3" "rxy4" "c1" "wy4" "c2" +permutation "rxy3" "wx3" "rxy4" "wy4" "c1" "c2" +permutation "rxy3" "wx3" "rxy4" "wy4" "c2" "c1" +permutation "rxy3" "rxy4" "wx3" "c1" "wy4" "c2" +permutation "rxy3" "rxy4" "wx3" "wy4" "c1" "c2" +permutation "rxy3" "rxy4" "wx3" "wy4" "c2" "c1" +permutation "rxy3" "rxy4" "wy4" "wx3" "c1" "c2" +permutation "rxy3" "rxy4" "wy4" "wx3" "c2" "c1" +permutation "rxy3" "rxy4" "wy4" "c2" "wx3" "c1" +permutation "rxy4" "rxy3" "wx3" "c1" "wy4" "c2" +permutation "rxy4" "rxy3" "wx3" "wy4" "c1" "c2" +permutation "rxy4" "rxy3" "wx3" "wy4" "c2" "c1" +permutation "rxy4" "rxy3" "wy4" "wx3" "c1" "c2" +permutation "rxy4" "rxy3" "wy4" "wx3" "c2" "c1" +permutation "rxy4" "rxy3" "wy4" "c2" "wx3" "c1" +permutation "rxy4" "wy4" "rxy3" "wx3" "c1" "c2" +permutation "rxy4" "wy4" "rxy3" "wx3" "c2" "c1" +permutation "rxy4" "wy4" "rxy3" "c2" "wx3" "c1" -- 1.9.1