28.08.2019 6:19, Peter Geoghegan wrote:
On Fri, Aug 16, 2019 at 8:56 AM Anastasia Lubennikova
<a.lubennik...@postgrespro.ru> wrote:
Now the algorithm is the following:
- In case page split is needed, pass both tuples to _bt_split().
_bt_findsplitloc() is now aware of upcoming replacement of origtup with
neworigtup, so it uses correct item size where needed.
It seems that now all replace operations are crash-safe. The new patch passes
all regression tests, so I think it's ready for review again.
I think that the way this works within nbtsplitloc.c is too
complicated. In v5, the only thing that nbtsplitloc.c knew about
deduplication was that it could be sure that suffix truncation would
at least make a posting list into a single heap TID in the worst case.
This consideration was mostly about suffix truncation, not
deduplication, which seemed like a good thing to me. _bt_split() and
_bt_findsplitloc() should know as little as possible about posting
lists.
Obviously it will sometimes be necessary to deal with the case where a
posting list is about to become too big (i.e. it's about to go over
BTMaxItemSize()), and so must be split. Less often, a page split will
be needed because of one of these posting list splits. These are two
complicated areas (posting list splits and page splits), and it would
be a good idea to find a way to separate them as much as possible.
Remember, nbtsplitloc.c works by pretending that the new item that
cannot fit on the page is already on its own imaginary version of the
page that *can* fit the new item, along with everything else from the
original/actual page. That gets *way* too complicated when it has to
deal with the fact that the new item is being merged with an existing
item. Perhaps nbtsplitloc.c could also "pretend" that the new item is
always a plain tuple, without knowing anything about posting lists.
Almost like how it worked in v5.
We always want posting lists to be as close to the BTMaxItemSize()
size as possible, because that helps with space utilization. In v5 of
the patch, this was what happened, because, in effect, we didn't try
to do anything complicated with the new item. This worked well, apart
from the crash safety issue. Maybe we can simulate the v5 approach,
giving us the best of all worlds (good space utilization, simplicity,
and crash safety). Something like this:
* Posting list splits should always result in one posting list that is
at or just under BTMaxItemSize() in size, plus one plain tuple to its
immediate right on the page. This is similar to the more common case
where we cannot add additional tuples to a posting list due to the
BTMaxItemSize() restriction, and so end up with a single tuple (or a
smaller posting list with the same value) to the right of a
BTMaxItemSize()-sized posting list tuple. I don't see a reason to
split a posting list in the middle -- we should always split to the
right, leaving the posting list as large as possible.
* When there is a simple posting list split, with no page split, the
logic required is fairly straightforward: We rewrite the posting list
in-place so that our new item goes wherever it belongs in the existing
posting list on the page (we memmove() the posting list to make space
for the new TID, basically). The old last/rightmost TID in the
original posting list becomes a new, plain tuple. We may need a new
WAL record for this, but it's not that different to a regular leaf
page insert.
* When this happens to result in a page split, we then have a "fake"
new item -- the right half of the posting list that we split, which is
always a plain item. Obviously we need to be a bit careful with the
WAL logging, but the space accounting within _bt_split() and
_bt_findsplitloc() can work just the same as now. nbtsplitloc.c can
work like it did in v5, when the only thing it knew about posting
lists was that _bt_truncate() always removes them, maybe leaving a
single TID behind in the new high key. (Note also that it's not okay
to remove the conservative assumption about at least having space for
one heap TID within _bt_recsplitloc() -- that needs to be restored to
its v5 state in the next version of the patch.)
Because deduplication is lazy, there is little value in doing
deduplication of the new item (which may or may not be the fake new
item). The nbtsplitloc.c logic will "trap" duplicates on the same page
today, so we can just let deduplication of the new item happen at a
later time. _bt_split() can almost pretend that posting lists don't
exist, and nbtsplitloc.c needs to know nothing about posting lists
(apart from the way that _bt_truncate() behaves with posting lists).
We "lie" to _bt_findsplitloc(), and tell it that the new item is our
fake new item -- it doesn't do anything that will be broken by that
lie, because it doesn't care about the actual content of posting
lists. And, we can fix the "fake new item is not actually real new
item" issue at one point within _bt_split(), just as we're about to
WAL log.
What do you think of that approach?
I think it's a good idea. Thank you for such a detailed description of
various
cases. I already started to simplify this code, while debugging amcheck
error
in v8. At first, I rewrote it to split posting tuple into a posting and a
regular tuple instead of two posting tuples.
Your explanation helped me to understand that this approach can be
extended to
the case of insertion into posting list, that doesn't trigger posting
split,
and that nbtsplitloc indeed doesn't need to know about posting tuples
specific.
The code is much cleaner now.
The new version is attached. It passes regression tests. I also run land
and
tpch test. They pass amcheck rootdescend and if I interpreted results
correctly, the new version shows slightly better compression.
\l+
tpch | anastasia | UTF8 | ru_RU.UTF-8 | ru_RU.UTF-8 | | 31
GB | pg_default |
land | anastasia | UTF8 | ru_RU.UTF-8 | ru_RU.UTF-8 | | 6380
MB | pg_default |
Some individual indexes are larger, some are smaller compared to the
expected output.
This patch is based on v6, so it again contains "compression" instead of
"deduplication"
in variable names and comments. I will rename them when code becomes
more stable.
--
Anastasia Lubennikova
Postgres Professional:http://www.postgrespro.com
The Russian Postgres Company
diff --git a/contrib/amcheck/verify_nbtree.c b/contrib/amcheck/verify_nbtree.c
index 05e7d67..504bca2 100644
--- a/contrib/amcheck/verify_nbtree.c
+++ b/contrib/amcheck/verify_nbtree.c
@@ -924,6 +924,7 @@ bt_target_page_check(BtreeCheckState *state)
size_t tupsize;
BTScanInsert skey;
bool lowersizelimit;
+ ItemPointer scantid;
CHECK_FOR_INTERRUPTS();
@@ -994,29 +995,73 @@ bt_target_page_check(BtreeCheckState *state)
/*
* Readonly callers may optionally verify that non-pivot tuples can
- * each be found by an independent search that starts from the root
+ * each be found by an independent search that starts from the root.
+ * Note that we deliberately don't do individual searches for each
+ * "logical" posting list tuple, since the posting list itself is
+ * validated by other checks.
*/
if (state->rootdescend && P_ISLEAF(topaque) &&
!bt_rootdescend(state, itup))
{
char *itid,
*htid;
+ ItemPointer tid = BTreeTupleGetHeapTID(itup);
itid = psprintf("(%u,%u)", state->targetblock, offset);
htid = psprintf("(%u,%u)",
- ItemPointerGetBlockNumber(&(itup->t_tid)),
- ItemPointerGetOffsetNumber(&(itup->t_tid)));
+ ItemPointerGetBlockNumber(tid),
+ ItemPointerGetOffsetNumber(tid));
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("could not find tuple using search from root page in index \"%s\"",
RelationGetRelationName(state->rel)),
- errdetail_internal("Index tid=%s points to heap tid=%s page lsn=%X/%X.",
+ errdetail_internal("Index tid=%s min heap tid=%s page lsn=%X/%X.",
itid, htid,
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn)));
}
+ /*
+ * If tuple is actually a posting list, make sure posting list TIDs
+ * are in order.
+ */
+ if (BTreeTupleIsPosting(itup))
+ {
+ ItemPointerData last;
+ ItemPointer current;
+
+ ItemPointerCopy(BTreeTupleGetHeapTID(itup), &last);
+
+ for (int i = 1; i < BTreeTupleGetNPosting(itup); i++)
+ {
+
+ current = BTreeTupleGetPostingN(itup, i);
+
+ if (ItemPointerCompare(current, &last) <= 0)
+ {
+ char *itid,
+ *htid;
+
+ itid = psprintf("(%u,%u)", state->targetblock, offset);
+ htid = psprintf("(%u,%u)",
+ ItemPointerGetBlockNumberNoCheck(current),
+ ItemPointerGetOffsetNumberNoCheck(current));
+
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("posting list heap TIDs out of order in index \"%s\"",
+ RelationGetRelationName(state->rel)),
+ errdetail_internal("Index tid=%s min heap tid=%s page lsn=%X/%X.",
+ itid, htid,
+ (uint32) (state->targetlsn >> 32),
+ (uint32) state->targetlsn)));
+ }
+
+ ItemPointerCopy(current, &last);
+ }
+ }
+
/* Build insertion scankey for current page offset */
skey = bt_mkscankey_pivotsearch(state->rel, itup);
@@ -1074,12 +1119,33 @@ bt_target_page_check(BtreeCheckState *state)
{
IndexTuple norm;
- norm = bt_normalize_tuple(state, itup);
- bloom_add_element(state->filter, (unsigned char *) norm,
- IndexTupleSize(norm));
- /* Be tidy */
- if (norm != itup)
- pfree(norm);
+ if (BTreeTupleIsPosting(itup))
+ {
+ IndexTuple onetup;
+
+ /* Fingerprint all elements of posting tuple one by one */
+ for (int i = 0; i < BTreeTupleGetNPosting(itup); i++)
+ {
+ onetup = BTreeGetNthTupleOfPosting(itup, i);
+
+ norm = bt_normalize_tuple(state, onetup);
+ bloom_add_element(state->filter, (unsigned char *) norm,
+ IndexTupleSize(norm));
+ /* Be tidy */
+ if (norm != onetup)
+ pfree(norm);
+ pfree(onetup);
+ }
+ }
+ else
+ {
+ norm = bt_normalize_tuple(state, itup);
+ bloom_add_element(state->filter, (unsigned char *) norm,
+ IndexTupleSize(norm));
+ /* Be tidy */
+ if (norm != itup)
+ pfree(norm);
+ }
}
/*
@@ -1087,7 +1153,8 @@ bt_target_page_check(BtreeCheckState *state)
*
* If there is a high key (if this is not the rightmost page on its
* entire level), check that high key actually is upper bound on all
- * page items.
+ * page items. If this is a posting list tuple, we'll need to set
+ * scantid to be highest TID in posting list.
*
* We prefer to check all items against high key rather than checking
* just the last and trusting that the operator class obeys the
@@ -1127,6 +1194,9 @@ bt_target_page_check(BtreeCheckState *state)
* tuple. (See also: "Notes About Data Representation" in the nbtree
* README.)
*/
+ scantid = skey->scantid;
+ if (!BTreeTupleIsPivot(itup))
+ skey->scantid = BTreeTupleGetMaxTID(itup);
if (!P_RIGHTMOST(topaque) &&
!(P_ISLEAF(topaque) ? invariant_leq_offset(state, skey, P_HIKEY) :
invariant_l_offset(state, skey, P_HIKEY)))
@@ -1150,6 +1220,7 @@ bt_target_page_check(BtreeCheckState *state)
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn)));
}
+ skey->scantid = scantid;
/*
* * Item order check *
@@ -1164,11 +1235,13 @@ bt_target_page_check(BtreeCheckState *state)
*htid,
*nitid,
*nhtid;
+ ItemPointer tid;
itid = psprintf("(%u,%u)", state->targetblock, offset);
+ tid = BTreeTupleGetHeapTID(itup);
htid = psprintf("(%u,%u)",
- ItemPointerGetBlockNumberNoCheck(&(itup->t_tid)),
- ItemPointerGetOffsetNumberNoCheck(&(itup->t_tid)));
+ ItemPointerGetBlockNumberNoCheck(tid),
+ ItemPointerGetOffsetNumberNoCheck(tid));
nitid = psprintf("(%u,%u)", state->targetblock,
OffsetNumberNext(offset));
@@ -1177,9 +1250,11 @@ bt_target_page_check(BtreeCheckState *state)
state->target,
OffsetNumberNext(offset));
itup = (IndexTuple) PageGetItem(state->target, itemid);
+
+ tid = BTreeTupleGetHeapTID(itup);
nhtid = psprintf("(%u,%u)",
- ItemPointerGetBlockNumberNoCheck(&(itup->t_tid)),
- ItemPointerGetOffsetNumberNoCheck(&(itup->t_tid)));
+ ItemPointerGetBlockNumberNoCheck(tid),
+ ItemPointerGetOffsetNumberNoCheck(tid));
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
@@ -1189,10 +1264,10 @@ bt_target_page_check(BtreeCheckState *state)
"higher index tid=%s (points to %s tid=%s) "
"page lsn=%X/%X.",
itid,
- P_ISLEAF(topaque) ? "heap" : "index",
+ P_ISLEAF(topaque) ? "min heap" : "index",
htid,
nitid,
- P_ISLEAF(topaque) ? "heap" : "index",
+ P_ISLEAF(topaque) ? "min heap" : "index",
nhtid,
(uint32) (state->targetlsn >> 32),
(uint32) state->targetlsn)));
@@ -1953,10 +2028,11 @@ bt_tuple_present_callback(Relation index, HeapTuple htup, Datum *values,
* verification. In particular, it won't try to normalize opclass-equal
* datums with potentially distinct representations (e.g., btree/numeric_ops
* index datums will not get their display scale normalized-away here).
- * Normalization may need to be expanded to handle more cases in the future,
- * though. For example, it's possible that non-pivot tuples could in the
- * future have alternative logically equivalent representations due to using
- * the INDEX_ALT_TID_MASK bit to implement intelligent deduplication.
+ * Caller does normalization for non-pivot tuples that have their own posting
+ * list, since dummy CREATE INDEX callback code generates new tuples with the
+ * same normalized representation. Compression is performed
+ * opportunistically, and in general there is no guarantee about how or when
+ * compression will be applied.
*/
static IndexTuple
bt_normalize_tuple(BtreeCheckState *state, IndexTuple itup)
@@ -2560,14 +2636,16 @@ static inline ItemPointer
BTreeTupleGetHeapTIDCareful(BtreeCheckState *state, IndexTuple itup,
bool nonpivot)
{
- ItemPointer result = BTreeTupleGetHeapTID(itup);
+ ItemPointer result;
BlockNumber targetblock = state->targetblock;
- if (result == NULL && nonpivot)
+ if (BTreeTupleIsPivot(itup) == nonpivot)
ereport(ERROR,
(errcode(ERRCODE_INDEX_CORRUPTED),
errmsg("block %u or its right sibling block or child block in index \"%s\" contains non-pivot tuple that lacks a heap TID",
targetblock, RelationGetRelationName(state->rel))));
+ result = BTreeTupleGetHeapTID(itup);
+
return result;
}
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index b84bf1c..1751133 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -47,15 +47,17 @@ static void _bt_insertonpg(Relation rel, BTScanInsert itup_key,
BTStack stack,
IndexTuple itup,
OffsetNumber newitemoff,
- bool split_only_page);
+ bool split_only_page, int in_posting_offset);
static Buffer _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf,
Buffer cbuf, OffsetNumber newitemoff, Size newitemsz,
- IndexTuple newitem);
+ IndexTuple newitem, IndexTuple neworigtup);
static void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf,
BTStack stack, bool is_root, bool is_only);
static bool _bt_pgaddtup(Page page, Size itemsize, IndexTuple itup,
OffsetNumber itup_off);
static void _bt_vacuum_one_page(Relation rel, Buffer buffer, Relation heapRel);
+static void insert_itupprev_to_page(Page page, BTCompressState *compressState);
+static void _bt_compress_one_page(Relation rel, Buffer buffer, Relation heapRel);
/*
* _bt_doinsert() -- Handle insertion of a single index tuple in the tree.
@@ -297,10 +299,12 @@ top:
* search bounds established within _bt_check_unique when insertion is
* checkingunique.
*/
+ insertstate.in_posting_offset = 0;
newitemoff = _bt_findinsertloc(rel, &insertstate, checkingunique,
stack, heapRel);
- _bt_insertonpg(rel, itup_key, insertstate.buf, InvalidBuffer, stack,
- itup, newitemoff, false);
+
+ _bt_insertonpg(rel, itup_key, insertstate.buf, InvalidBuffer,
+ stack, itup, newitemoff, false, insertstate.in_posting_offset);
}
else
{
@@ -435,6 +439,7 @@ _bt_check_unique(Relation rel, BTInsertState insertstate, Relation heapRel,
/* okay, we gotta fetch the heap tuple ... */
curitup = (IndexTuple) PageGetItem(page, curitemid);
+ Assert(!BTreeTupleIsPosting(curitup));
htid = curitup->t_tid;
/*
@@ -759,6 +764,26 @@ _bt_findinsertloc(Relation rel,
_bt_vacuum_one_page(rel, insertstate->buf, heapRel);
insertstate->bounds_valid = false;
}
+
+ /*
+ * If the target page is full, try to compress the page
+ */
+ if (PageGetFreeSpace(page) < insertstate->itemsz && !checkingunique)
+ {
+ _bt_compress_one_page(rel, insertstate->buf, heapRel);
+ insertstate->bounds_valid = false; /* paranoia */
+
+ /*
+ * FIXME: _bt_vacuum_one_page() won't have cleared the
+ * BTP_HAS_GARBAGE flag when it didn't kill items. Maybe we
+ * should clear the BTP_HAS_GARBAGE flag bit from the page when
+ * compression avoids a page split -- _bt_vacuum_one_page() is
+ * expecting a page split that takes care of it.
+ *
+ * (On the other hand, maybe it doesn't matter very much. A
+ * comment update seems like the bare minimum we should do.)
+ */
+ }
}
else
{
@@ -900,6 +925,75 @@ _bt_stepright(Relation rel, BTInsertState insertstate, BTStack stack)
insertstate->bounds_valid = false;
}
+
+/*
+ * Replace tuple on newitemoff offset with neworigtup,
+ * and insert newitup right after it.
+ *
+ * It's essential to do this atomic to be crash safe.
+ *
+ * NOTE All checks of free space must be done before calling this function.
+ *
+ * For use in posting tuple's update.
+ */
+void
+_bt_replace_and_insert(Buffer buf,
+ Page page,
+ IndexTuple neworigtup, IndexTuple newitup,
+ OffsetNumber newitemoff, bool need_xlog)
+{
+ Size newitupsz = IndexTupleSize(newitup);
+ IndexTuple origtup = (IndexTuple) PageGetItem(page,
+ PageGetItemId(page, newitemoff));
+
+ Assert(BTreeTupleIsPosting(origtup));
+ Assert(BTreeTupleIsPosting(neworigtup));
+ Assert(!BTreeTupleIsPosting(newitup));
+ Assert(MAXALIGN(IndexTupleSize(origtup)) == MAXALIGN(IndexTupleSize(neworigtup)));
+
+ newitupsz = MAXALIGN(newitupsz);
+
+ START_CRIT_SECTION();
+
+ /*
+ * Since we always replace posting tuple with tuple of same size
+ * (only posting list may changes), can do simple inplace update.
+ */
+ memcpy(origtup, neworigtup, MAXALIGN(IndexTupleSize(neworigtup)));
+
+ if (!_bt_pgaddtup(page, newitupsz, newitup, OffsetNumberNext(newitemoff)))
+ elog(ERROR, "failed to insert compressed item in index");
+
+ if (BufferIsValid(buf))
+ {
+ MarkBufferDirty(buf);
+
+ /* Xlog stuff */
+ if (need_xlog)
+ {
+ xl_btree_insert xlrec;
+ XLogRecPtr recptr;
+
+ xlrec.offnum = newitemoff;
+ xlrec.origtup_off = MAXALIGN(IndexTupleSize(newitup));
+
+ XLogBeginInsert();
+ XLogRegisterData((char *) &xlrec, SizeOfBtreeInsert);
+
+ Assert(P_ISLEAF((BTPageOpaque) PageGetSpecialPointer(page)));
+
+ XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
+ XLogRegisterBufData(0, (char *) newitup, MAXALIGN(IndexTupleSize(newitup)));
+ XLogRegisterBufData(0, (char *) neworigtup, MAXALIGN(IndexTupleSize(neworigtup)));
+
+ recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_INSERT_LEAF);
+
+ PageSetLSN(page, recptr);
+ }
+ }
+ END_CRIT_SECTION();
+}
+
/*----------
* _bt_insertonpg() -- Insert a tuple on a particular page in the index.
*
@@ -936,11 +1030,13 @@ _bt_insertonpg(Relation rel,
BTStack stack,
IndexTuple itup,
OffsetNumber newitemoff,
- bool split_only_page)
+ bool split_only_page,
+ int in_posting_offset)
{
Page page;
BTPageOpaque lpageop;
Size itemsz;
+ IndexTuple neworigtup = NULL;
page = BufferGetPage(buf);
lpageop = (BTPageOpaque) PageGetSpecialPointer(page);
@@ -964,6 +1060,120 @@ _bt_insertonpg(Relation rel,
itemsz = MAXALIGN(itemsz); /* be safe, PageAddItem will do this but we
* need to be consistent */
+ if (in_posting_offset)
+ {
+ /* get old posting tuple */
+ ItemId itemid = PageGetItemId(page, newitemoff);
+ int nipd;
+ IndexTuple origtup;
+ char *src;
+ char *dest;
+ size_t ntocopy;
+
+ origtup = (IndexTuple) PageGetItem(page, itemid);
+ Assert(BTreeTupleIsPosting(origtup));
+ nipd = BTreeTupleGetNPosting(origtup);
+ Assert(in_posting_offset < nipd);
+ Assert(itup_key->scantid != NULL);
+ Assert(itup_key->heapkeyspace);
+
+ elog(DEBUG4, "origtup (%u,%u) is min, (%u,%u) is max, (%u,%u) is new",
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(origtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(origtup)),
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetMaxTID(origtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetMaxTID(origtup)),
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetMaxTID(itup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetMaxTID(itup)));
+
+ /* generate neworigtup */
+
+ /*
+ * Handle corner cases (1)
+ * - itup TID is smaller than leftmost orightup TID
+ */
+ if (ItemPointerCompare(BTreeTupleGetHeapTID(itup),
+ BTreeTupleGetHeapTID(origtup)) < 0)
+ {
+ in_posting_offset = InvalidOffsetNumber;
+ newitemoff = OffsetNumberPrev(newitemoff); //TODO Is it needed?
+ elog(DEBUG4, "itup is to the left of origtup newitemoff %u", newitemoff);
+ }
+ /*
+ * Handle corner cases (2)
+ * - itup TID is larger than rightmost orightup TID
+ */
+ else if (ItemPointerCompare(BTreeTupleGetMaxTID(origtup),
+ BTreeTupleGetHeapTID(itup)) < 0)
+ {
+ /* do nothing */
+ in_posting_offset = InvalidOffsetNumber;
+ //newitemoff = OffsetNumberNext(newitemoff); //TODO Is it needed?
+ elog(DEBUG4, "itup is to the right of origtup newitemoff %u", newitemoff);
+ }
+ /* Handle insertion into the middle of the posting list */
+ else
+ {
+ neworigtup = CopyIndexTuple(origtup);
+ src = (char *) BTreeTupleGetPostingN(neworigtup, in_posting_offset);
+ dest = (char *) src + sizeof(ItemPointerData);
+ ntocopy = (nipd - in_posting_offset - 1)*sizeof(ItemPointerData);
+
+ elog(DEBUG4, "itup is inside origtup"
+ " nipd %d in_posting_offset %d ntocopy %lu newitemoff %u",
+ nipd, in_posting_offset, ntocopy, newitemoff);
+ elog(DEBUG4, "neworigtup before N %d (%u,%u) to (%u,%u)",
+ BTreeTupleIsPosting(neworigtup)?BTreeTupleGetNPosting(neworigtup):0,
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(neworigtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(neworigtup)),
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetMaxTID(neworigtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetMaxTID(neworigtup)));
+
+ elog(DEBUG4, "itup before (%u,%u)",
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(itup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(itup)));
+ elog(DEBUG4, "src before (%u,%u)",
+ ItemPointerGetBlockNumberNoCheck((ItemPointer) src),
+ ItemPointerGetOffsetNumberNoCheck((ItemPointer) src));
+ elog(DEBUG4, "dest before (%u,%u)",
+ ItemPointerGetBlockNumberNoCheck((ItemPointer) dest),
+ ItemPointerGetOffsetNumberNoCheck((ItemPointer) dest));
+ /* move itemp pointers in posting list to free space for incoming one */
+ memmove(dest, src, ntocopy);
+
+ /* copy new item pointer to posting list */
+ ItemPointerCopy(&itup->t_tid, (ItemPointer) src);
+
+ /* copy old rightmost item pointer to new tuple, that we're going to insert */
+ ItemPointerCopy(BTreeTupleGetPostingN(origtup, nipd-1), &itup->t_tid);
+
+ elog(DEBUG4, "neworigtup N %d (%u,%u) to (%u,%u)",
+ BTreeTupleIsPosting(neworigtup)?BTreeTupleGetNPosting(neworigtup):0,
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(neworigtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(neworigtup)),
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetMaxTID(neworigtup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetMaxTID(neworigtup)));
+
+// for (int i = 0; i < BTreeTupleGetNPosting(neworigtup); i++)
+// {
+// elog(WARNING, "neworigtup item n %d (%u,%u)",
+// i,
+// ItemPointerGetBlockNumberNoCheck(BTreeTupleGetPostingN(neworigtup, i)),
+// ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetPostingN(neworigtup, i)));
+// }
+
+ elog(DEBUG4, "itup (%u,%u)",
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(itup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(itup)));
+
+ Assert(!BTreeTupleIsPosting(itup));
+ Assert(ItemPointerCompare(BTreeTupleGetHeapTID(neworigtup),
+ BTreeTupleGetMaxTID(neworigtup)) < 0);
+
+ Assert(ItemPointerCompare(BTreeTupleGetMaxTID(neworigtup),
+ BTreeTupleGetHeapTID(itup)) < 0);
+ }
+ }
+
/*
* Do we need to split the page to fit the item on it?
*
@@ -996,7 +1206,8 @@ _bt_insertonpg(Relation rel,
BlockNumberIsValid(RelationGetTargetBlock(rel))));
/* split the buffer into left and right halves */
- rbuf = _bt_split(rel, itup_key, buf, cbuf, newitemoff, itemsz, itup);
+ rbuf = _bt_split(rel, itup_key, buf, cbuf,
+ newitemoff, itemsz, itup, neworigtup);
PredicateLockPageSplit(rel,
BufferGetBlockNumber(buf),
BufferGetBlockNumber(rbuf));
@@ -1033,70 +1244,152 @@ _bt_insertonpg(Relation rel,
itup_off = newitemoff;
itup_blkno = BufferGetBlockNumber(buf);
- /*
- * If we are doing this insert because we split a page that was the
- * only one on its tree level, but was not the root, it may have been
- * the "fast root". We need to ensure that the fast root link points
- * at or above the current page. We can safely acquire a lock on the
- * metapage here --- see comments for _bt_newroot().
- */
- if (split_only_page)
+ if (neworigtup == NULL)
{
- Assert(!P_ISLEAF(lpageop));
+ /*
+ * If we are doing this insert because we split a page that was the
+ * only one on its tree level, but was not the root, it may have been
+ * the "fast root". We need to ensure that the fast root link points
+ * at or above the current page. We can safely acquire a lock on the
+ * metapage here --- see comments for _bt_newroot().
+ */
+ if (split_only_page)
+ {
+ Assert(!P_ISLEAF(lpageop));
+
+ metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
+ metapg = BufferGetPage(metabuf);
+ metad = BTPageGetMeta(metapg);
+
+ if (metad->btm_fastlevel >= lpageop->btpo.level)
+ {
+ /* no update wanted */
+ _bt_relbuf(rel, metabuf);
+ metabuf = InvalidBuffer;
+ }
+ }
- metabuf = _bt_getbuf(rel, BTREE_METAPAGE, BT_WRITE);
- metapg = BufferGetPage(metabuf);
- metad = BTPageGetMeta(metapg);
+ /*
+ * Every internal page should have exactly one negative infinity item
+ * at all times. Only _bt_split() and _bt_newroot() should add items
+ * that become negative infinity items through truncation, since
+ * they're the only routines that allocate new internal pages. Do not
+ * allow a retail insertion of a new item at the negative infinity
+ * offset.
+ */
+ if (!P_ISLEAF(lpageop) && newitemoff == P_FIRSTDATAKEY(lpageop))
+ elog(ERROR, "cannot insert second negative infinity item in block %u of index \"%s\"",
+ itup_blkno, RelationGetRelationName(rel));
+
+ /* Do the update. No ereport(ERROR) until changes are logged */
+ START_CRIT_SECTION();
+
+ if (!_bt_pgaddtup(page, itemsz, itup, newitemoff))
+ elog(PANIC, "failed to add new item to block %u in index \"%s\"",
+ itup_blkno, RelationGetRelationName(rel));
+
+ MarkBufferDirty(buf);
- if (metad->btm_fastlevel >= lpageop->btpo.level)
+ if (BufferIsValid(metabuf))
{
- /* no update wanted */
- _bt_relbuf(rel, metabuf);
- metabuf = InvalidBuffer;
+ /* upgrade meta-page if needed */
+ if (metad->btm_version < BTREE_NOVAC_VERSION)
+ _bt_upgrademetapage(metapg);
+ metad->btm_fastroot = itup_blkno;
+ metad->btm_fastlevel = lpageop->btpo.level;
+ MarkBufferDirty(metabuf);
}
- }
- /*
- * Every internal page should have exactly one negative infinity item
- * at all times. Only _bt_split() and _bt_newroot() should add items
- * that become negative infinity items through truncation, since
- * they're the only routines that allocate new internal pages. Do not
- * allow a retail insertion of a new item at the negative infinity
- * offset.
- */
- if (!P_ISLEAF(lpageop) && newitemoff == P_FIRSTDATAKEY(lpageop))
- elog(ERROR, "cannot insert second negative infinity item in block %u of index \"%s\"",
- itup_blkno, RelationGetRelationName(rel));
+ /* clear INCOMPLETE_SPLIT flag on child if inserting a downlink */
+ if (BufferIsValid(cbuf))
+ {
+ Page cpage = BufferGetPage(cbuf);
+ BTPageOpaque cpageop = (BTPageOpaque) PageGetSpecialPointer(cpage);
- /* Do the update. No ereport(ERROR) until changes are logged */
- START_CRIT_SECTION();
+ Assert(P_INCOMPLETE_SPLIT(cpageop));
+ cpageop->btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
+ MarkBufferDirty(cbuf);
+ }
- if (!_bt_pgaddtup(page, itemsz, itup, newitemoff))
- elog(PANIC, "failed to add new item to block %u in index \"%s\"",
- itup_blkno, RelationGetRelationName(rel));
+ /* XLOG stuff */
+ if (RelationNeedsWAL(rel))
+ {
+ xl_btree_insert xlrec;
+ xl_btree_metadata xlmeta;
+ uint8 xlinfo;
+ XLogRecPtr recptr;
- MarkBufferDirty(buf);
+ xlrec.offnum = itup_off;
+ xlrec.origtup_off = 0;
- if (BufferIsValid(metabuf))
- {
- /* upgrade meta-page if needed */
- if (metad->btm_version < BTREE_NOVAC_VERSION)
- _bt_upgrademetapage(metapg);
- metad->btm_fastroot = itup_blkno;
- metad->btm_fastlevel = lpageop->btpo.level;
- MarkBufferDirty(metabuf);
- }
+ XLogBeginInsert();
+ XLogRegisterData((char *) &xlrec, SizeOfBtreeInsert);
- /* clear INCOMPLETE_SPLIT flag on child if inserting a downlink */
- if (BufferIsValid(cbuf))
- {
- Page cpage = BufferGetPage(cbuf);
- BTPageOpaque cpageop = (BTPageOpaque) PageGetSpecialPointer(cpage);
+ if (P_ISLEAF(lpageop))
+ xlinfo = XLOG_BTREE_INSERT_LEAF;
+ else
+ {
+ /*
+ * Register the left child whose INCOMPLETE_SPLIT flag was
+ * cleared.
+ */
+ XLogRegisterBuffer(1, cbuf, REGBUF_STANDARD);
+
+ xlinfo = XLOG_BTREE_INSERT_UPPER;
+ }
+
+ if (BufferIsValid(metabuf))
+ {
+ Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
+ xlmeta.version = metad->btm_version;
+ xlmeta.root = metad->btm_root;
+ xlmeta.level = metad->btm_level;
+ xlmeta.fastroot = metad->btm_fastroot;
+ xlmeta.fastlevel = metad->btm_fastlevel;
+ xlmeta.oldest_btpo_xact = metad->btm_oldest_btpo_xact;
+ xlmeta.last_cleanup_num_heap_tuples =
+ metad->btm_last_cleanup_num_heap_tuples;
+
+ XLogRegisterBuffer(2, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
+ XLogRegisterBufData(2, (char *) &xlmeta, sizeof(xl_btree_metadata));
+
+ xlinfo = XLOG_BTREE_INSERT_META;
+ }
+
+ XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
+ XLogRegisterBufData(0, (char *) itup, IndexTupleSize(itup));
+
+ recptr = XLogInsert(RM_BTREE_ID, xlinfo);
+
+ if (BufferIsValid(metabuf))
+ {
+ PageSetLSN(metapg, recptr);
+ }
+ if (BufferIsValid(cbuf))
+ {
+ PageSetLSN(BufferGetPage(cbuf), recptr);
+ }
- Assert(P_INCOMPLETE_SPLIT(cpageop));
- cpageop->btpo_flags &= ~BTP_INCOMPLETE_SPLIT;
- MarkBufferDirty(cbuf);
+ PageSetLSN(page, recptr);
+ }
+ END_CRIT_SECTION();
}
+ else
+ {
+ /*
+ * Insert new tuple on place of existing posting tuple.
+ * Delete old posting tuple, and insert updated tuple instead.
+ *
+ * If split was needed, both neworigtup and newrighttup are initialized
+ * and both will be inserted, otherwise newrighttup is NULL.
+ *
+ * It only can happen on leaf page.
+ */
+ elog(DEBUG4, "_bt_insertonpg. _bt_replace_and_insert %s newitemoff %u",
+ RelationGetRelationName(rel), newitemoff);
+ _bt_replace_and_insert(buf, page, neworigtup,
+ itup, newitemoff, RelationNeedsWAL(rel));
+ }
/*
* Cache the block information if we just inserted into the rightmost
@@ -1107,69 +1400,6 @@ _bt_insertonpg(Relation rel,
if (P_RIGHTMOST(lpageop) && P_ISLEAF(lpageop) && !P_ISROOT(lpageop))
cachedBlock = BufferGetBlockNumber(buf);
- /* XLOG stuff */
- if (RelationNeedsWAL(rel))
- {
- xl_btree_insert xlrec;
- xl_btree_metadata xlmeta;
- uint8 xlinfo;
- XLogRecPtr recptr;
-
- xlrec.offnum = itup_off;
-
- XLogBeginInsert();
- XLogRegisterData((char *) &xlrec, SizeOfBtreeInsert);
-
- if (P_ISLEAF(lpageop))
- xlinfo = XLOG_BTREE_INSERT_LEAF;
- else
- {
- /*
- * Register the left child whose INCOMPLETE_SPLIT flag was
- * cleared.
- */
- XLogRegisterBuffer(1, cbuf, REGBUF_STANDARD);
-
- xlinfo = XLOG_BTREE_INSERT_UPPER;
- }
-
- if (BufferIsValid(metabuf))
- {
- Assert(metad->btm_version >= BTREE_NOVAC_VERSION);
- xlmeta.version = metad->btm_version;
- xlmeta.root = metad->btm_root;
- xlmeta.level = metad->btm_level;
- xlmeta.fastroot = metad->btm_fastroot;
- xlmeta.fastlevel = metad->btm_fastlevel;
- xlmeta.oldest_btpo_xact = metad->btm_oldest_btpo_xact;
- xlmeta.last_cleanup_num_heap_tuples =
- metad->btm_last_cleanup_num_heap_tuples;
-
- XLogRegisterBuffer(2, metabuf, REGBUF_WILL_INIT | REGBUF_STANDARD);
- XLogRegisterBufData(2, (char *) &xlmeta, sizeof(xl_btree_metadata));
-
- xlinfo = XLOG_BTREE_INSERT_META;
- }
-
- XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
- XLogRegisterBufData(0, (char *) itup, IndexTupleSize(itup));
-
- recptr = XLogInsert(RM_BTREE_ID, xlinfo);
-
- if (BufferIsValid(metabuf))
- {
- PageSetLSN(metapg, recptr);
- }
- if (BufferIsValid(cbuf))
- {
- PageSetLSN(BufferGetPage(cbuf), recptr);
- }
-
- PageSetLSN(page, recptr);
- }
-
- END_CRIT_SECTION();
-
/* release buffers */
if (BufferIsValid(metabuf))
_bt_relbuf(rel, metabuf);
@@ -1211,10 +1441,20 @@ _bt_insertonpg(Relation rel,
*
* Returns the new right sibling of buf, pinned and write-locked.
* The pin and lock on buf are maintained.
+ *
+ * TODO improve comment
+ * The real *new* item is already inside neorigtup in the correct place according to TID order
+ * And "newitem" contains rightmost ItemPointerData trimmed from posting list.
+ * Insertion consists of two steps
+ * - replace original item at newitemoff with neworigtup
+ * This operation doesn't change origtup size, so all calculations
+ * of splitloc remain the same.
+ * - insert newitem right after that as if we inserted a regular tuple
*/
static Buffer
_bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
- OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem)
+ OffsetNumber newitemoff, Size newitemsz, IndexTuple newitem,
+ IndexTuple neworigtup)
{
Buffer rbuf;
Page origpage;
@@ -1236,12 +1476,19 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
OffsetNumber firstright;
OffsetNumber maxoff;
OffsetNumber i;
+ OffsetNumber replaceitemoff = InvalidOffsetNumber;
bool newitemonleft,
isleaf;
IndexTuple lefthikey;
int indnatts = IndexRelationGetNumberOfAttributes(rel);
int indnkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
+ if (neworigtup != NULL)
+ {
+ replaceitemoff = newitemoff;
+ newitemoff = OffsetNumberNext(newitemoff);
+ }
+
/*
* origpage is the original page to be split. leftpage is a temporary
* buffer that receives the left-sibling data, which will be copied back
@@ -1340,6 +1587,8 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
itemid = PageGetItemId(origpage, firstright);
itemsz = ItemIdGetLength(itemid);
item = (IndexTuple) PageGetItem(origpage, itemid);
+ if (firstright == replaceitemoff)
+ item = neworigtup;
}
/*
@@ -1373,6 +1622,8 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
Assert(lastleftoff >= P_FIRSTDATAKEY(oopaque));
itemid = PageGetItemId(origpage, lastleftoff);
lastleft = (IndexTuple) PageGetItem(origpage, itemid);
+ if (lastleftoff == replaceitemoff)
+ lastleft = neworigtup;
}
Assert(lastleft != item);
@@ -1480,6 +1731,13 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
itemsz = ItemIdGetLength(itemid);
item = (IndexTuple) PageGetItem(origpage, itemid);
+ /* TODO add comment */
+ if (i == replaceitemoff)
+ {
+ item = neworigtup;
+ Assert(neworigtup != NULL);
+ }
+
/* does new item belong before this one? */
if (i == newitemoff)
{
@@ -1652,6 +1910,7 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
xlrec.level = ropaque->btpo.level;
xlrec.firstright = firstright;
xlrec.newitemoff = newitemoff;
+ xlrec.replaceitemoff = replaceitemoff;
XLogBeginInsert();
XLogRegisterData((char *) &xlrec, SizeOfBtreeSplit);
@@ -1681,6 +1940,10 @@ _bt_split(Relation rel, BTScanInsert itup_key, Buffer buf, Buffer cbuf,
item = (IndexTuple) PageGetItem(origpage, itemid);
XLogRegisterBufData(0, (char *) item, MAXALIGN(IndexTupleSize(item)));
+ if (replaceitemoff)
+ XLogRegisterBufData(0, (char *) neworigtup,
+ MAXALIGN(IndexTupleSize(neworigtup)));
+
/*
* Log the contents of the right page in the format understood by
* _bt_restore_page(). The whole right page will be recreated.
@@ -1835,7 +2098,7 @@ _bt_insert_parent(Relation rel,
/* Recursively insert into the parent */
_bt_insertonpg(rel, NULL, pbuf, buf, stack->bts_parent,
new_item, stack->bts_offset + 1,
- is_only);
+ is_only, InvalidOffsetNumber);
/* be tidy */
pfree(new_item);
@@ -2307,3 +2570,206 @@ _bt_vacuum_one_page(Relation rel, Buffer buffer, Relation heapRel)
* the page.
*/
}
+
+/*
+ * Add new item (compressed or not) to the page, while compressing it.
+ * If insertion failed, return false.
+ * Caller should consider this as compression failure and
+ * leave page uncompressed.
+ */
+static void
+insert_itupprev_to_page(Page page, BTCompressState *compressState)
+{
+ IndexTuple to_insert;
+ OffsetNumber offnum = PageGetMaxOffsetNumber(page);
+
+ if (compressState->ntuples == 0)
+ to_insert = compressState->itupprev;
+ else
+ {
+ IndexTuple postingtuple;
+
+ /* form a tuple with a posting list */
+ postingtuple = BTreeFormPostingTuple(compressState->itupprev,
+ compressState->ipd,
+ compressState->ntuples);
+ to_insert = postingtuple;
+ pfree(compressState->ipd);
+ }
+
+ /* Add the new item into the page */
+ offnum = OffsetNumberNext(offnum);
+
+ elog(DEBUG4, "insert_itupprev_to_page. compressState->ntuples %d IndexTupleSize %zu free %zu",
+ compressState->ntuples, IndexTupleSize(to_insert), PageGetFreeSpace(page));
+
+ if (PageAddItem(page, (Item) to_insert, IndexTupleSize(to_insert),
+ offnum, false, false) == InvalidOffsetNumber)
+ elog(ERROR, "failed to add tuple to page while compresing it");
+
+ if (compressState->ntuples > 0)
+ pfree(to_insert);
+ compressState->ntuples = 0;
+}
+
+/*
+ * Before splitting the page, try to compress items to free some space.
+ * If compression didn't succeed, buffer will contain old state of the page.
+ * This function should be called after lp_dead items
+ * were removed by _bt_vacuum_one_page().
+ */
+static void
+_bt_compress_one_page(Relation rel, Buffer buffer, Relation heapRel)
+{
+ OffsetNumber offnum,
+ minoff,
+ maxoff;
+ Page page = BufferGetPage(buffer);
+ Page newpage;
+ BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
+ bool use_compression = false;
+ BTCompressState *compressState = NULL;
+ int natts = IndexRelationGetNumberOfAttributes(rel);
+ OffsetNumber deletable[MaxOffsetNumber];
+ int ndeletable = 0;
+
+ /*
+ * Don't use compression for indexes with INCLUDEd columns and unique
+ * indexes.
+ */
+ use_compression = (IndexRelationGetNumberOfKeyAttributes(rel) ==
+ IndexRelationGetNumberOfAttributes(rel) &&
+ !rel->rd_index->indisunique);
+ if (!use_compression)
+ return;
+
+ /* init compress state needed to build posting tuples */
+ compressState = (BTCompressState *) palloc0(sizeof(BTCompressState));
+ compressState->ipd = NULL;
+ compressState->ntuples = 0;
+ compressState->itupprev = NULL;
+ compressState->maxitemsize = BTMaxItemSize(page);
+ compressState->maxpostingsize = 0;
+
+ minoff = P_FIRSTDATAKEY(opaque);
+ maxoff = PageGetMaxOffsetNumber(page);
+
+
+ /*
+ * Delete dead tuples if any.
+ * We cannot simply skip them in the cycle below, because it's neccessary
+ * to generate special Xlog record containing such tuples to compute
+ * latestRemovedXid on a standby server later.
+ *
+ * This should not affect performance, since it only can happen in a rare
+ * situation when BTP_HAS_GARBAGE flag was not set and _bt_vacuum_one_page
+ * was not called, or _bt_vacuum_one_page didn't remove all dead items.
+ */
+ for (offnum = minoff;
+ offnum <= maxoff;
+ offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemid = PageGetItemId(page, P_HIKEY);
+
+ if (ItemIdIsDead(itemid))
+ deletable[ndeletable++] = offnum;
+ }
+
+ if (ndeletable > 0)
+ _bt_delitems_delete(rel, buffer, deletable, ndeletable, heapRel);
+
+ /*
+ * Scan over all items to see which ones can be compressed
+ */
+ minoff = P_FIRSTDATAKEY(opaque);
+ maxoff = PageGetMaxOffsetNumber(page);
+ newpage = PageGetTempPageCopySpecial(page);
+ elog(DEBUG4, "_bt_compress_one_page rel: %s,blkno: %u",
+ RelationGetRelationName(rel), BufferGetBlockNumber(buffer));
+
+ /* Copy High Key if any */
+ if (!P_RIGHTMOST(opaque))
+ {
+ ItemId itemid = PageGetItemId(page, P_HIKEY);
+ Size itemsz = ItemIdGetLength(itemid);
+ IndexTuple item = (IndexTuple) PageGetItem(page, itemid);
+
+ if (PageAddItem(newpage, (Item) item, itemsz, P_HIKEY,
+ false, false) == InvalidOffsetNumber)
+ elog(ERROR, "failed to add highkey during compression");
+ }
+
+ /*
+ * Iterate over tuples on the page, try to compress them into posting
+ * lists and insert into new page.
+ */
+ for (offnum = minoff;
+ offnum <= maxoff;
+ offnum = OffsetNumberNext(offnum))
+ {
+ ItemId itemId = PageGetItemId(page, offnum);
+ IndexTuple itup = (IndexTuple) PageGetItem(page, itemId);
+
+ if (compressState->itupprev != NULL)
+ {
+ int n_equal_atts =
+ _bt_keep_natts_fast(rel, compressState->itupprev, itup);
+ int itup_ntuples = BTreeTupleIsPosting(itup) ?
+ BTreeTupleGetNPosting(itup) : 1;
+
+ if (n_equal_atts > natts)
+ {
+ /*
+ * When tuples are equal, create or update posting.
+ *
+ * If posting is too big, insert it on page and continue.
+ */
+ if (compressState->maxitemsize >
+ MAXALIGN(((IndexTupleSize(compressState->itupprev)
+ + (compressState->ntuples + itup_ntuples + 1) * sizeof(ItemPointerData)))))
+ {
+ _bt_add_posting_item(compressState, itup);
+ }
+ else
+ {
+ insert_itupprev_to_page(newpage, compressState);
+ }
+ }
+ else
+ {
+ insert_itupprev_to_page(newpage, compressState);
+ }
+ }
+
+ /*
+ * Copy the tuple into temp variable itupprev to compare it with the
+ * following tuple and maybe unite them into a posting tuple
+ */
+ if (compressState->itupprev)
+ pfree(compressState->itupprev);
+ compressState->itupprev = CopyIndexTuple(itup);
+
+ Assert(IndexTupleSize(compressState->itupprev) <= compressState->maxitemsize);
+ }
+
+ /* Handle the last item. */
+ insert_itupprev_to_page(newpage, compressState);
+
+ START_CRIT_SECTION();
+
+ PageRestoreTempPage(newpage, page);
+ MarkBufferDirty(buffer);
+
+ /* Log full page write */
+ if (RelationNeedsWAL(rel))
+ {
+ XLogRecPtr recptr;
+
+ recptr = log_newpage_buffer(buffer, true);
+ PageSetLSN(page, recptr);
+ }
+
+ END_CRIT_SECTION();
+
+ elog(DEBUG4, "_bt_compress_one_page. success");
+}
diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c
index 268f869..fca35a4 100644
--- a/src/backend/access/nbtree/nbtpage.c
+++ b/src/backend/access/nbtree/nbtpage.c
@@ -983,14 +983,52 @@ _bt_page_recyclable(Page page)
void
_bt_delitems_vacuum(Relation rel, Buffer buf,
OffsetNumber *itemnos, int nitems,
+ OffsetNumber *remainingoffset,
+ IndexTuple *remaining, int nremaining,
BlockNumber lastBlockVacuumed)
{
Page page = BufferGetPage(buf);
BTPageOpaque opaque;
+ Size itemsz;
+ Size remaining_sz = 0;
+ char *remaining_buf = NULL;
+
+ /* XLOG stuff, buffer for remainings */
+ if (nremaining && RelationNeedsWAL(rel))
+ {
+ Size offset = 0;
+
+ for (int i = 0; i < nremaining; i++)
+ remaining_sz += MAXALIGN(IndexTupleSize(remaining[i]));
+
+ remaining_buf = palloc0(remaining_sz);
+ for (int i = 0; i < nremaining; i++)
+ {
+ itemsz = IndexTupleSize(remaining[i]);
+ memcpy(remaining_buf + offset, (char *) remaining[i], itemsz);
+ offset += MAXALIGN(itemsz);
+ }
+ Assert(offset == remaining_sz);
+ }
/* No ereport(ERROR) until changes are logged */
START_CRIT_SECTION();
+ /* Handle posting tuples here */
+ for (int i = 0; i < nremaining; i++)
+ {
+ /* At first, delete the old tuple. */
+ PageIndexTupleDelete(page, remainingoffset[i]);
+
+ itemsz = IndexTupleSize(remaining[i]);
+ itemsz = MAXALIGN(itemsz);
+
+ /* Add tuple with remaining ItemPointers to the page. */
+ if (PageAddItem(page, (Item) remaining[i], itemsz, remainingoffset[i],
+ false, false) == InvalidOffsetNumber)
+ elog(ERROR, "failed to rewrite compressed item in index while doing vacuum");
+ }
+
/* Fix the page */
if (nitems > 0)
PageIndexMultiDelete(page, itemnos, nitems);
@@ -1020,6 +1058,8 @@ _bt_delitems_vacuum(Relation rel, Buffer buf,
xl_btree_vacuum xlrec_vacuum;
xlrec_vacuum.lastBlockVacuumed = lastBlockVacuumed;
+ xlrec_vacuum.nremaining = nremaining;
+ xlrec_vacuum.ndeleted = nitems;
XLogBeginInsert();
XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
@@ -1033,6 +1073,19 @@ _bt_delitems_vacuum(Relation rel, Buffer buf,
if (nitems > 0)
XLogRegisterBufData(0, (char *) itemnos, nitems * sizeof(OffsetNumber));
+ /*
+ * Here we should save offnums and remaining tuples themselves. It's
+ * important to restore them in correct order. At first, we must
+ * handle remaining tuples and only after that other deleted items.
+ */
+ if (nremaining > 0)
+ {
+ Assert(remaining_buf != NULL);
+ XLogRegisterBufData(0, (char *) remainingoffset,
+ nremaining * sizeof(OffsetNumber));
+ XLogRegisterBufData(0, remaining_buf, remaining_sz);
+ }
+
recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_VACUUM);
PageSetLSN(page, recptr);
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 4cfd528..a85c67b 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -97,6 +97,8 @@ static void btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
BTCycleId cycleid, TransactionId *oldestBtpoXact);
static void btvacuumpage(BTVacState *vstate, BlockNumber blkno,
BlockNumber orig_blkno);
+static ItemPointer btreevacuumPosting(BTVacState *vstate, IndexTuple itup,
+ int *nremaining);
/*
@@ -1069,7 +1071,8 @@ btvacuumscan(IndexVacuumInfo *info, IndexBulkDeleteResult *stats,
RBM_NORMAL, info->strategy);
LockBufferForCleanup(buf);
_bt_checkpage(rel, buf);
- _bt_delitems_vacuum(rel, buf, NULL, 0, vstate.lastBlockVacuumed);
+ _bt_delitems_vacuum(rel, buf, NULL, 0, NULL, NULL, 0,
+ vstate.lastBlockVacuumed);
_bt_relbuf(rel, buf);
}
@@ -1193,6 +1196,9 @@ restart:
OffsetNumber offnum,
minoff,
maxoff;
+ IndexTuple remaining[MaxOffsetNumber];
+ OffsetNumber remainingoffset[MaxOffsetNumber];
+ int nremaining;
/*
* Trade in the initial read lock for a super-exclusive write lock on
@@ -1229,6 +1235,7 @@ restart:
* callback function.
*/
ndeletable = 0;
+ nremaining = 0;
minoff = P_FIRSTDATAKEY(opaque);
maxoff = PageGetMaxOffsetNumber(page);
if (callback)
@@ -1242,31 +1249,81 @@ restart:
itup = (IndexTuple) PageGetItem(page,
PageGetItemId(page, offnum));
- htup = &(itup->t_tid);
- /*
- * During Hot Standby we currently assume that
- * XLOG_BTREE_VACUUM records do not produce conflicts. That is
- * only true as long as the callback function depends only
- * upon whether the index tuple refers to heap tuples removed
- * in the initial heap scan. When vacuum starts it derives a
- * value of OldestXmin. Backends taking later snapshots could
- * have a RecentGlobalXmin with a later xid than the vacuum's
- * OldestXmin, so it is possible that row versions deleted
- * after OldestXmin could be marked as killed by other
- * backends. The callback function *could* look at the index
- * tuple state in isolation and decide to delete the index
- * tuple, though currently it does not. If it ever did, we
- * would need to reconsider whether XLOG_BTREE_VACUUM records
- * should cause conflicts. If they did cause conflicts they
- * would be fairly harsh conflicts, since we haven't yet
- * worked out a way to pass a useful value for
- * latestRemovedXid on the XLOG_BTREE_VACUUM records. This
- * applies to *any* type of index that marks index tuples as
- * killed.
- */
- if (callback(htup, callback_state))
- deletable[ndeletable++] = offnum;
+ if (BTreeTupleIsPosting(itup))
+ {
+ int nnewipd = 0;
+ ItemPointer newipd = NULL;
+
+ elog(DEBUG4, "rel %s btreevacuumPosting offnum %u",
+ RelationGetRelationName(vstate->info->index), offnum);
+
+ newipd = btreevacuumPosting(vstate, itup, &nnewipd);
+
+ if (nnewipd == 0)
+ {
+ /*
+ * All TIDs from posting list must be deleted, we can
+ * delete whole tuple in a regular way.
+ */
+ deletable[ndeletable++] = offnum;
+ }
+ else if (nnewipd == BTreeTupleGetNPosting(itup))
+ {
+ /*
+ * All TIDs from posting tuple must remain. Do
+ * nothing, just cleanup.
+ */
+ pfree(newipd);
+ }
+ else if (nnewipd < BTreeTupleGetNPosting(itup))
+ {
+ /* Some TIDs from posting tuple must remain. */
+ Assert(nnewipd > 0);
+ Assert(newipd != NULL);
+
+ /*
+ * Form new tuple that contains only remaining TIDs.
+ * Remember this tuple and the offset of the old tuple
+ * to update it in place.
+ */
+ remainingoffset[nremaining] = offnum;
+ remaining[nremaining] = BTreeFormPostingTuple(itup, newipd, nnewipd);
+ nremaining++;
+ pfree(newipd);
+
+ Assert(IndexTupleSize(itup) <= BTMaxItemSize(page));
+ }
+ }
+ else
+ {
+ htup = &(itup->t_tid);
+
+ /*
+ * During Hot Standby we currently assume that
+ * XLOG_BTREE_VACUUM records do not produce conflicts.
+ * That is only true as long as the callback function
+ * depends only upon whether the index tuple refers to
+ * heap tuples removed in the initial heap scan. When
+ * vacuum starts it derives a value of OldestXmin.
+ * Backends taking later snapshots could have a
+ * RecentGlobalXmin with a later xid than the vacuum's
+ * OldestXmin, so it is possible that row versions deleted
+ * after OldestXmin could be marked as killed by other
+ * backends. The callback function *could* look at the
+ * index tuple state in isolation and decide to delete the
+ * index tuple, though currently it does not. If it ever
+ * did, we would need to reconsider whether
+ * XLOG_BTREE_VACUUM records should cause conflicts. If
+ * they did cause conflicts they would be fairly harsh
+ * conflicts, since we haven't yet worked out a way to
+ * pass a useful value for latestRemovedXid on the
+ * XLOG_BTREE_VACUUM records. This applies to *any* type
+ * of index that marks index tuples as killed.
+ */
+ if (callback(htup, callback_state))
+ deletable[ndeletable++] = offnum;
+ }
}
}
@@ -1274,7 +1331,7 @@ restart:
* Apply any needed deletes. We issue just one _bt_delitems_vacuum()
* call per page, so as to minimize WAL traffic.
*/
- if (ndeletable > 0)
+ if (ndeletable > 0 || nremaining > 0)
{
/*
* Notice that the issued XLOG_BTREE_VACUUM WAL record includes
@@ -1291,6 +1348,7 @@ restart:
* that.
*/
_bt_delitems_vacuum(rel, buf, deletable, ndeletable,
+ remainingoffset, remaining, nremaining,
vstate->lastBlockVacuumed);
/*
@@ -1376,6 +1434,47 @@ restart:
}
/*
+ * btreevacuumPosting() -- vacuums a posting tuple.
+ *
+ * Returns new palloc'd posting list with remaining items.
+ * Posting list size is returned via nremaining.
+ *
+ * If all items are dead,
+ * nremaining is 0 and resulting posting list is NULL.
+ */
+static ItemPointer
+btreevacuumPosting(BTVacState *vstate, IndexTuple itup, int *nremaining)
+{
+ int remaining = 0;
+ int nitem = BTreeTupleGetNPosting(itup);
+ ItemPointer tmpitems = NULL,
+ items = BTreeTupleGetPosting(itup);
+
+ /*
+ * Check each tuple in the posting list, save alive tuples into tmpitems
+ */
+ for (int i = 0; i < nitem; i++)
+ {
+ elog(DEBUG4, "rel %s btreevacuumPosting i %d, (%u,%u)",
+ RelationGetRelationName(vstate->info->index),
+ i,
+ ItemPointerGetBlockNumberNoCheck( (items + i)),
+ ItemPointerGetOffsetNumberNoCheck((items + i)));
+
+ if (vstate->callback(items + i, vstate->callback_state))
+ continue;
+
+ if (tmpitems == NULL)
+ tmpitems = palloc(sizeof(ItemPointerData) * nitem);
+
+ tmpitems[remaining++] = items[i];
+ }
+
+ *nremaining = remaining;
+ return tmpitems;
+}
+
+/*
* btcanreturn() -- Check whether btree indexes support index-only scans.
*
* btrees always do, so this is trivial.
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 7f77ed2..72e52bc 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -30,6 +30,9 @@ static bool _bt_readpage(IndexScanDesc scan, ScanDirection dir,
OffsetNumber offnum);
static void _bt_saveitem(BTScanOpaque so, int itemIndex,
OffsetNumber offnum, IndexTuple itup);
+static void _bt_savepostingitem(BTScanOpaque so, int itemIndex,
+ OffsetNumber offnum, ItemPointer iptr,
+ IndexTuple itup, int i);
static bool _bt_steppage(IndexScanDesc scan, ScanDirection dir);
static bool _bt_readnextpage(IndexScanDesc scan, BlockNumber blkno, ScanDirection dir);
static bool _bt_parallel_readpage(IndexScanDesc scan, BlockNumber blkno,
@@ -497,7 +500,8 @@ _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
/* We have low <= mid < high, so mid points at a real slot */
- result = _bt_compare(rel, key, page, mid);
+ result = _bt_compare_posting(rel, key, page, mid,
+ &(insertstate->in_posting_offset));
if (result >= cmpval)
low = mid + 1;
@@ -526,6 +530,55 @@ _bt_binsrch_insert(Relation rel, BTInsertState insertstate)
return low;
}
+/*
+ * Compare insertion-type scankey to tuple on a page,
+ * taking into account posting tuples.
+ * If the key of the posting tuple is equal to scankey,
+ * find exact position inside the posting list,
+ * using TID as extra attribute.
+ */
+int32
+_bt_compare_posting(Relation rel,
+ BTScanInsert key,
+ Page page,
+ OffsetNumber offnum,
+ int *in_posting_offset)
+{
+ IndexTuple itup;
+ int result;
+
+ itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
+ result = _bt_compare(rel, key, page, offnum);
+
+ if (BTreeTupleIsPosting(itup) && result == 0)
+ {
+ int low,
+ high,
+ mid,
+ res;
+
+ low = 0;
+ /* "high" is past end of posting list for loop invariant */
+ high = BTreeTupleGetNPosting(itup);
+
+ while (high > low)
+ {
+ mid = low + ((high - low) / 2);
+ res = ItemPointerCompare(key->scantid,
+ BTreeTupleGetPostingN(itup, mid));
+
+ if (res >= 1)
+ low = mid + 1;
+ else
+ high = mid;
+ }
+
+ *in_posting_offset = high;
+ }
+
+ return result;
+}
+
/*----------
* _bt_compare() -- Compare insertion-type scankey to tuple on a page.
*
@@ -658,61 +711,120 @@ _bt_compare(Relation rel,
* Use the heap TID attribute and scantid to try to break the tie. The
* rules are the same as any other key attribute -- only the
* representation differs.
+ *
+ * When itup is a posting tuple, the check becomes more complex. It is
+ * possible that the scankey belongs to the tuple's posting list TID
+ * range.
+ *
+ * _bt_compare() is multipurpose, so it just returns 0 for a fact that key
+ * matches tuple at this offset.
+ *
+ * Use special _bt_compare_posting() wrapper function to handle this case
+ * and perform recheck for posting tuple, finding exact position of the
+ * scankey.
*/
- heapTid = BTreeTupleGetHeapTID(itup);
- if (key->scantid == NULL)
+ if (!BTreeTupleIsPosting(itup))
{
+ heapTid = BTreeTupleGetHeapTID(itup);
+ if (key->scantid == NULL)
+ {
+ /*
+ * Most searches have a scankey that is considered greater than a
+ * truncated pivot tuple if and when the scankey has equal values
+ * for attributes up to and including the least significant
+ * untruncated attribute in tuple.
+ *
+ * For example, if an index has the minimum two attributes (single
+ * user key attribute, plus heap TID attribute), and a page's high
+ * key is ('foo', -inf), and scankey is ('foo', <omitted>), the
+ * search will not descend to the page to the left. The search
+ * will descend right instead. The truncated attribute in pivot
+ * tuple means that all non-pivot tuples on the page to the left
+ * are strictly < 'foo', so it isn't necessary to descend left. In
+ * other words, search doesn't have to descend left because it
+ * isn't interested in a match that has a heap TID value of -inf.
+ *
+ * However, some searches (pivotsearch searches) actually require
+ * that we descend left when this happens. -inf is treated as a
+ * possible match for omitted scankey attribute(s). This is
+ * needed by page deletion, which must re-find leaf pages that are
+ * targets for deletion using their high keys.
+ *
+ * Note: the heap TID part of the test ensures that scankey is
+ * being compared to a pivot tuple with one or more truncated key
+ * attributes.
+ *
+ * Note: pg_upgrade'd !heapkeyspace indexes must always descend to
+ * the left here, since they have no heap TID attribute (and
+ * cannot have any -inf key values in any case, since truncation
+ * can only remove non-key attributes). !heapkeyspace searches
+ * must always be prepared to deal with matches on both sides of
+ * the pivot once the leaf level is reached.
+ */
+ if (key->heapkeyspace && !key->pivotsearch &&
+ key->keysz == ntupatts && heapTid == NULL)
+ return 1;
+
+ /* All provided scankey arguments found to be equal */
+ return 0;
+ }
+
/*
- * Most searches have a scankey that is considered greater than a
- * truncated pivot tuple if and when the scankey has equal values for
- * attributes up to and including the least significant untruncated
- * attribute in tuple.
- *
- * For example, if an index has the minimum two attributes (single
- * user key attribute, plus heap TID attribute), and a page's high key
- * is ('foo', -inf), and scankey is ('foo', <omitted>), the search
- * will not descend to the page to the left. The search will descend
- * right instead. The truncated attribute in pivot tuple means that
- * all non-pivot tuples on the page to the left are strictly < 'foo',
- * so it isn't necessary to descend left. In other words, search
- * doesn't have to descend left because it isn't interested in a match
- * that has a heap TID value of -inf.
- *
- * However, some searches (pivotsearch searches) actually require that
- * we descend left when this happens. -inf is treated as a possible
- * match for omitted scankey attribute(s). This is needed by page
- * deletion, which must re-find leaf pages that are targets for
- * deletion using their high keys.
- *
- * Note: the heap TID part of the test ensures that scankey is being
- * compared to a pivot tuple with one or more truncated key
- * attributes.
- *
- * Note: pg_upgrade'd !heapkeyspace indexes must always descend to the
- * left here, since they have no heap TID attribute (and cannot have
- * any -inf key values in any case, since truncation can only remove
- * non-key attributes). !heapkeyspace searches must always be
- * prepared to deal with matches on both sides of the pivot once the
- * leaf level is reached.
+ * Treat truncated heap TID as minus infinity, since scankey has a key
+ * attribute value (scantid) that would otherwise be compared directly
*/
- if (key->heapkeyspace && !key->pivotsearch &&
- key->keysz == ntupatts && heapTid == NULL)
+ Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel));
+ if (heapTid == NULL)
return 1;
- /* All provided scankey arguments found to be equal */
- return 0;
+ Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel));
+ return ItemPointerCompare(key->scantid, heapTid);
}
+ else
+ {
+ heapTid = BTreeTupleGetHeapTID(itup);
+ if (key->scantid != NULL && heapTid != NULL)
+ {
+ int cmp = ItemPointerCompare(key->scantid, heapTid);
- /*
- * Treat truncated heap TID as minus infinity, since scankey has a key
- * attribute value (scantid) that would otherwise be compared directly
- */
- Assert(key->keysz == IndexRelationGetNumberOfKeyAttributes(rel));
- if (heapTid == NULL)
- return 1;
+ if (cmp == -1 || cmp == 0)
+ {
+ elog(DEBUG4, "offnum %d Scankey (%u,%u) is less than or equal to posting tuple (%u,%u)",
+ offnum, ItemPointerGetBlockNumberNoCheck(key->scantid),
+ ItemPointerGetOffsetNumberNoCheck(key->scantid),
+ ItemPointerGetBlockNumberNoCheck(heapTid),
+ ItemPointerGetOffsetNumberNoCheck(heapTid));
+ return cmp;
+ }
- Assert(ntupatts >= IndexRelationGetNumberOfKeyAttributes(rel));
- return ItemPointerCompare(key->scantid, heapTid);
+ heapTid = BTreeTupleGetMaxTID(itup);
+ cmp = ItemPointerCompare(key->scantid, heapTid);
+ if (cmp == 1)
+ {
+ elog(DEBUG4, "offnum %d Scankey (%u,%u) is greater than posting tuple (%u,%u)",
+ offnum, ItemPointerGetBlockNumberNoCheck(key->scantid),
+ ItemPointerGetOffsetNumberNoCheck(key->scantid),
+ ItemPointerGetBlockNumberNoCheck(heapTid),
+ ItemPointerGetOffsetNumberNoCheck(heapTid));
+ return cmp;
+ }
+
+ /*
+ * if we got here, scantid is inbetween of posting items of the
+ * tuple
+ */
+ elog(DEBUG4, "offnum %d Scankey (%u,%u) is between posting items (%u,%u) and (%u,%u)",
+ offnum, ItemPointerGetBlockNumberNoCheck(key->scantid),
+ ItemPointerGetOffsetNumberNoCheck(key->scantid),
+ ItemPointerGetBlockNumberNoCheck(BTreeTupleGetHeapTID(itup)),
+ ItemPointerGetOffsetNumberNoCheck(BTreeTupleGetHeapTID(itup)),
+ ItemPointerGetBlockNumberNoCheck(heapTid),
+ ItemPointerGetOffsetNumberNoCheck(heapTid));
+ return 0;
+ }
+ }
+
+ return 0;
}
/*
@@ -1449,6 +1561,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
/* initialize tuple workspace to empty */
so->currPos.nextTupleOffset = 0;
+ so->currPos.prevTupleOffset = 0;
/*
* Now that the current page has been made consistent, the macro should be
@@ -1483,8 +1596,22 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
if (_bt_checkkeys(scan, itup, indnatts, dir, &continuescan))
{
/* tuple passes all scan key conditions, so remember it */
- _bt_saveitem(so, itemIndex, offnum, itup);
- itemIndex++;
+ if (!BTreeTupleIsPosting(itup))
+ {
+ _bt_saveitem(so, itemIndex, offnum, itup);
+ itemIndex++;
+ }
+ else
+ {
+ /* Return posting list "logical" tuples */
+ for (int i = 0; i < BTreeTupleGetNPosting(itup); i++)
+ {
+ _bt_savepostingitem(so, itemIndex, offnum,
+ BTreeTupleGetPostingN(itup, i),
+ itup, i);
+ itemIndex++;
+ }
+ }
}
/* When !continuescan, there can't be any more matches, so stop */
if (!continuescan)
@@ -1517,7 +1644,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
if (!continuescan)
so->currPos.moreRight = false;
- Assert(itemIndex <= MaxIndexTuplesPerPage);
+ Assert(itemIndex <= MaxPostingIndexTuplesPerPage);
so->currPos.firstItem = 0;
so->currPos.lastItem = itemIndex - 1;
so->currPos.itemIndex = 0;
@@ -1525,7 +1652,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
else
{
/* load items[] in descending order */
- itemIndex = MaxIndexTuplesPerPage;
+ itemIndex = MaxPostingIndexTuplesPerPage;
offnum = Min(offnum, maxoff);
@@ -1567,8 +1694,23 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
if (passes_quals && tuple_alive)
{
/* tuple passes all scan key conditions, so remember it */
- itemIndex--;
- _bt_saveitem(so, itemIndex, offnum, itup);
+ if (!BTreeTupleIsPosting(itup))
+ {
+ itemIndex--;
+ _bt_saveitem(so, itemIndex, offnum, itup);
+ }
+ else
+ {
+ /* Return posting list "logical" tuples */
+ /* XXX: Maybe this loop should be backwards? */
+ for (int i = 0; i < BTreeTupleGetNPosting(itup); i++)
+ {
+ itemIndex--;
+ _bt_savepostingitem(so, itemIndex, offnum,
+ BTreeTupleGetPostingN(itup, i),
+ itup, i);
+ }
+ }
}
if (!continuescan)
{
@@ -1582,8 +1724,8 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
Assert(itemIndex >= 0);
so->currPos.firstItem = itemIndex;
- so->currPos.lastItem = MaxIndexTuplesPerPage - 1;
- so->currPos.itemIndex = MaxIndexTuplesPerPage - 1;
+ so->currPos.lastItem = MaxPostingIndexTuplesPerPage - 1;
+ so->currPos.itemIndex = MaxPostingIndexTuplesPerPage - 1;
}
return (so->currPos.firstItem <= so->currPos.lastItem);
@@ -1596,6 +1738,8 @@ _bt_saveitem(BTScanOpaque so, int itemIndex,
{
BTScanPosItem *currItem = &so->currPos.items[itemIndex];
+ Assert(!BTreeTupleIsPosting(itup));
+
currItem->heapTid = itup->t_tid;
currItem->indexOffset = offnum;
if (so->currTuples)
@@ -1608,6 +1752,33 @@ _bt_saveitem(BTScanOpaque so, int itemIndex,
}
}
+/* Save an index item into so->currPos.items[itemIndex] for posting tuples. */
+static void
+_bt_savepostingitem(BTScanOpaque so, int itemIndex, OffsetNumber offnum,
+ ItemPointer iptr, IndexTuple itup, int i)
+{
+ BTScanPosItem *currItem = &so->currPos.items[itemIndex];
+
+ currItem->heapTid = *iptr;
+ currItem->indexOffset = offnum;
+
+ if (so->currTuples)
+ {
+ if (i == 0)
+ {
+ /* save key. the same for all tuples in the posting */
+ Size itupsz = BTreeTupleGetPostingOffset(itup);
+
+ currItem->tupleOffset = so->currPos.nextTupleOffset;
+ memcpy(so->currTuples + so->currPos.nextTupleOffset, itup, itupsz);
+ so->currPos.nextTupleOffset += MAXALIGN(itupsz);
+ so->currPos.prevTupleOffset = currItem->tupleOffset;
+ }
+ else
+ currItem->tupleOffset = so->currPos.prevTupleOffset;
+ }
+}
+
/*
* _bt_steppage() -- Step to next page containing valid data for scan
*
diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c
index ab19692..d7207e0 100644
--- a/src/backend/access/nbtree/nbtsort.c
+++ b/src/backend/access/nbtree/nbtsort.c
@@ -288,6 +288,8 @@ static void _bt_sortaddtup(Page page, Size itemsize,
static void _bt_buildadd(BTWriteState *wstate, BTPageState *state,
IndexTuple itup);
static void _bt_uppershutdown(BTWriteState *wstate, BTPageState *state);
+static void _bt_buildadd_posting(BTWriteState *wstate, BTPageState *state,
+ BTCompressState *compressState);
static void _bt_load(BTWriteState *wstate,
BTSpool *btspool, BTSpool *btspool2);
static void _bt_begin_parallel(BTBuildState *buildstate, bool isconcurrent,
@@ -963,6 +965,11 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup)
* Overwrite the old item with new truncated high key directly.
* oitup is already located at the physical beginning of tuple
* space, so this should directly reuse the existing tuple space.
+ *
+ * If lastleft tuple was a posting tuple, we'll truncate its
+ * posting list in _bt_truncate as well. Note that it is also
+ * applicable only to leaf pages, since internal pages never
+ * contain posting tuples.
*/
ii = PageGetItemId(opage, OffsetNumberPrev(last_off));
lastleft = (IndexTuple) PageGetItem(opage, ii);
@@ -1002,6 +1009,7 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup)
* the minimum key for the new page.
*/
state->btps_minkey = CopyIndexTuple(oitup);
+ Assert(BTreeTupleIsPivot(state->btps_minkey));
/*
* Set the sibling links for both pages.
@@ -1043,6 +1051,7 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup)
Assert(state->btps_minkey == NULL);
state->btps_minkey = CopyIndexTuple(itup);
/* _bt_sortaddtup() will perform full truncation later */
+ BTreeTupleClearBtIsPosting(state->btps_minkey);
BTreeTupleSetNAtts(state->btps_minkey, 0);
}
@@ -1128,6 +1137,91 @@ _bt_uppershutdown(BTWriteState *wstate, BTPageState *state)
}
/*
+ * Add new tuple (posting or non-posting) to the page while building index.
+ */
+static void
+_bt_buildadd_posting(BTWriteState *wstate, BTPageState *state,
+ BTCompressState *compressState)
+{
+ IndexTuple to_insert;
+
+ /* Return, if there is no tuple to insert */
+ if (state == NULL)
+ return;
+
+ if (compressState->ntuples == 0)
+ to_insert = compressState->itupprev;
+ else
+ {
+ IndexTuple postingtuple;
+
+ /* form a tuple with a posting list */
+ postingtuple = BTreeFormPostingTuple(compressState->itupprev,
+ compressState->ipd,
+ compressState->ntuples);
+ to_insert = postingtuple;
+ pfree(compressState->ipd);
+ }
+
+ _bt_buildadd(wstate, state, to_insert);
+
+ if (compressState->ntuples > 0)
+ pfree(to_insert);
+ compressState->ntuples = 0;
+}
+
+/*
+ * Save item pointer(s) of itup to the posting list in compressState.
+ *
+ * Helper function for _bt_load() and _bt_compress_one_page().
+ *
+ * Note: caller is responsible for size check to ensure that resulting tuple
+ * won't exceed BTMaxItemSize.
+ */
+void
+_bt_add_posting_item(BTCompressState *compressState, IndexTuple itup)
+{
+ int nposting = 0;
+
+ if (compressState->ntuples == 0)
+ {
+ compressState->ipd = palloc0(compressState->maxitemsize);
+
+ if (BTreeTupleIsPosting(compressState->itupprev))
+ {
+ /* if itupprev is posting, add all its TIDs to the posting list */
+ nposting = BTreeTupleGetNPosting(compressState->itupprev);
+ memcpy(compressState->ipd,
+ BTreeTupleGetPosting(compressState->itupprev),
+ sizeof(ItemPointerData) * nposting);
+ compressState->ntuples += nposting;
+ }
+ else
+ {
+ memcpy(compressState->ipd, compressState->itupprev,
+ sizeof(ItemPointerData));
+ compressState->ntuples++;
+ }
+ }
+
+ if (BTreeTupleIsPosting(itup))
+ {
+ /* if tuple is posting, add all its TIDs to the posting list */
+ nposting = BTreeTupleGetNPosting(itup);
+ memcpy(compressState->ipd + compressState->ntuples,
+ BTreeTupleGetPosting(itup),
+ sizeof(ItemPointerData) * nposting);
+ compressState->ntuples += nposting;
+ }
+ else
+ {
+ memcpy(compressState->ipd + compressState->ntuples, itup,
+ sizeof(ItemPointerData));
+ compressState->ntuples++;
+ }
+}
+
+/*
* Read tuples in correct sort order from tuplesort, and load them into
* btree leaves.
*/
@@ -1141,9 +1235,20 @@ _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
bool load1;
TupleDesc tupdes = RelationGetDescr(wstate->index);
int i,
- keysz = IndexRelationGetNumberOfKeyAttributes(wstate->index);
+ keysz = IndexRelationGetNumberOfKeyAttributes(wstate->index),
+ natts = IndexRelationGetNumberOfAttributes(wstate->index);
SortSupport sortKeys;
int64 tuples_done = 0;
+ bool use_compression = false;
+ BTCompressState *compressState = NULL;
+
+ /*
+ * Don't use compression for indexes with INCLUDEd columns and unique
+ * indexes.
+ */
+ use_compression = (IndexRelationGetNumberOfKeyAttributes(wstate->index) ==
+ IndexRelationGetNumberOfAttributes(wstate->index) &&
+ !wstate->index->rd_index->indisunique);
if (merge)
{
@@ -1257,19 +1362,89 @@ _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
}
else
{
- /* merge is unnecessary */
- while ((itup = tuplesort_getindextuple(btspool->sortstate,
- true)) != NULL)
+ if (!use_compression)
{
- /* When we see first tuple, create first index page */
- if (state == NULL)
- state = _bt_pagestate(wstate, 0);
+ /* merge is unnecessary */
+ while ((itup = tuplesort_getindextuple(btspool->sortstate,
+ true)) != NULL)
+ {
+ /* When we see first tuple, create first index page */
+ if (state == NULL)
+ state = _bt_pagestate(wstate, 0);
- _bt_buildadd(wstate, state, itup);
+ _bt_buildadd(wstate, state, itup);
- /* Report progress */
- pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
- ++tuples_done);
+ /* Report progress */
+ pgstat_progress_update_param(PROGRESS_CREATEIDX_TUPLES_DONE,
+ ++tuples_done);
+ }
+ }
+ else
+ {
+ /* init compress state needed to build posting tuples */
+ compressState = (BTCompressState *) palloc0(sizeof(BTCompressState));
+ compressState->ipd = NULL;
+ compressState->ntuples = 0;
+ compressState->itupprev = NULL;
+ compressState->maxitemsize = 0;
+ compressState->maxpostingsize = 0;
+
+ while ((itup = tuplesort_getindextuple(btspool->sortstate,
+ true)) != NULL)
+ {
+ /* When we see first tuple, create first index page */
+ if (state == NULL)
+ {
+ state = _bt_pagestate(wstate, 0);
+ compressState->maxitemsize = BTMaxItemSize(state->btps_page);
+ }
+
+ if (compressState->itupprev != NULL)
+ {
+ int n_equal_atts = _bt_keep_natts_fast(wstate->index,
+ compressState->itupprev, itup);
+
+ if (n_equal_atts > natts)
+ {
+ /*
+ * Tuples are equal. Create or update posting.
+ *
+ * Else If posting is too big, insert it on page and
+ * continue.
+ */
+ if ((compressState->ntuples + 1) * sizeof(ItemPointerData) <
+ compressState->maxpostingsize)
+ _bt_add_posting_item(compressState, itup);
+ else
+ _bt_buildadd_posting(wstate, state,
+ compressState);
+ }
+ else
+ {
+ /*
+ * Tuples are not equal. Insert itupprev into index.
+ * Save current tuple for the next iteration.
+ */
+ _bt_buildadd_posting(wstate, state, compressState);
+ }
+ }
+
+ /*
+ * Save the tuple to compare it with the next one and maybe
+ * unite them into a posting tuple.
+ */
+ if (compressState->itupprev)
+ pfree(compressState->itupprev);
+ compressState->itupprev = CopyIndexTuple(itup);
+
+ /* compute max size of posting list */
+ compressState->maxpostingsize = compressState->maxitemsize -
+ IndexInfoFindDataOffset(compressState->itupprev->t_info) -
+ MAXALIGN(IndexTupleSize(compressState->itupprev));
+ }
+
+ /* Handle the last item */
+ _bt_buildadd_posting(wstate, state, compressState);
}
}
diff --git a/src/backend/access/nbtree/nbtsplitloc.c b/src/backend/access/nbtree/nbtsplitloc.c
index 1c1029b..0ead2ea 100644
--- a/src/backend/access/nbtree/nbtsplitloc.c
+++ b/src/backend/access/nbtree/nbtsplitloc.c
@@ -459,6 +459,7 @@ _bt_recsplitloc(FindSplitData *state,
int16 leftfree,
rightfree;
Size firstrightitemsz;
+ Size postingsubhikey = 0;
bool newitemisfirstonright;
/* Is the new item going to be the first item on the right page? */
@@ -466,10 +467,33 @@ _bt_recsplitloc(FindSplitData *state,
&& !newitemonleft);
if (newitemisfirstonright)
+ {
firstrightitemsz = state->newitemsz;
+
+ /* Calculate posting list overhead, if any */
+ if (state->is_leaf && BTreeTupleIsPosting(state->newitem))
+ postingsubhikey = IndexTupleSize(state->newitem) -
+ BTreeTupleGetPostingOffset(state->newitem);
+ }
else
+ {
firstrightitemsz = firstoldonrightsz;
+ /* Calculate posting list overhead, if any */
+ if (state->is_leaf)
+ {
+ ItemId itemid;
+ IndexTuple newhighkey;
+
+ itemid = PageGetItemId(state->page, firstoldonright);
+ newhighkey = (IndexTuple) PageGetItem(state->page, itemid);
+
+ if (BTreeTupleIsPosting(newhighkey))
+ postingsubhikey = IndexTupleSize(newhighkey) -
+ BTreeTupleGetPostingOffset(newhighkey);
+ }
+ }
+
/* Account for all the old tuples */
leftfree = state->leftspace - olddataitemstoleft;
rightfree = state->rightspace -
@@ -492,9 +516,13 @@ _bt_recsplitloc(FindSplitData *state,
* adding a heap TID to the left half's new high key when splitting at the
* leaf level. In practice the new high key will often be smaller and
* will rarely be larger, but conservatively assume the worst case.
+ * Truncation always truncates away any posting list that appears in the
+ * first right tuple, though, so it's safe to subtract that overhead
+ * (while still conservatively assuming that truncation might have to add
+ * back a single heap TID using the pivot tuple heap TID representation).
*/
if (state->is_leaf)
- leftfree -= (int16) (firstrightitemsz +
+ leftfree -= (int16) ((firstrightitemsz - postingsubhikey) +
MAXALIGN(sizeof(ItemPointerData)));
else
leftfree -= (int16) firstrightitemsz;
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 4c7b2d0..7be2542 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -111,8 +111,12 @@ _bt_mkscankey(Relation rel, IndexTuple itup)
key->nextkey = false;
key->pivotsearch = false;
key->keysz = Min(indnkeyatts, tupnatts);
- key->scantid = key->heapkeyspace && itup ?
- BTreeTupleGetHeapTID(itup) : NULL;
+
+ if (itup && key->heapkeyspace)
+ key->scantid = BTreeTupleGetHeapTID(itup);
+ else
+ key->scantid = NULL;
+
skey = key->scankeys;
for (i = 0; i < indnkeyatts; i++)
{
@@ -1787,7 +1791,9 @@ _bt_killitems(IndexScanDesc scan)
ItemId iid = PageGetItemId(page, offnum);
IndexTuple ituple = (IndexTuple) PageGetItem(page, iid);
- if (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid))
+ /* No microvacuum for posting tuples */
+ if (!BTreeTupleIsPosting(ituple) &&
+ (ItemPointerEquals(&ituple->t_tid, &kitem->heapTid)))
{
/* found the item */
ItemIdMarkDead(iid);
@@ -2145,6 +2151,16 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
pivot = index_truncate_tuple(itupdesc, firstright, keepnatts);
+ if (BTreeTupleIsPosting(firstright))
+ {
+ BTreeTupleClearBtIsPosting(pivot);
+ BTreeTupleSetNAtts(pivot, keepnatts);
+ pivot->t_info &= ~INDEX_SIZE_MASK;
+ pivot->t_info |= BTreeTupleGetPostingOffset(firstright);
+ }
+
+ Assert(!BTreeTupleIsPosting(pivot));
+
/*
* If there is a distinguishing key attribute within new pivot tuple,
* there is no need to add an explicit heap TID attribute
@@ -2161,6 +2177,8 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
* attribute to the new pivot tuple.
*/
Assert(natts != nkeyatts);
+ Assert(!BTreeTupleIsPosting(lastleft));
+ Assert(!BTreeTupleIsPosting(firstright));
newsize = IndexTupleSize(pivot) + MAXALIGN(sizeof(ItemPointerData));
tidpivot = palloc0(newsize);
memcpy(tidpivot, pivot, IndexTupleSize(pivot));
@@ -2168,6 +2186,27 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
pfree(pivot);
pivot = tidpivot;
}
+ else if (BTreeTupleIsPosting(firstright))
+ {
+ /*
+ * No truncation was possible, since key attributes are all equal. But
+ * the tuple is a compressed tuple with a posting list, so we still
+ * must truncate it.
+ *
+ * It's necessary to add a heap TID attribute to the new pivot tuple.
+ */
+ newsize = BTreeTupleGetPostingOffset(firstright) +
+ MAXALIGN(sizeof(ItemPointerData));
+ pivot = palloc0(newsize);
+ memcpy(pivot, firstright, BTreeTupleGetPostingOffset(firstright));
+
+ pivot->t_info &= ~INDEX_SIZE_MASK;
+ pivot->t_info |= newsize;
+ BTreeTupleClearBtIsPosting(pivot);
+ BTreeTupleSetAltHeapTID(pivot);
+
+ Assert(!BTreeTupleIsPosting(pivot));
+ }
else
{
/*
@@ -2205,7 +2244,7 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
*/
pivotheaptid = (ItemPointer) ((char *) pivot + newsize -
sizeof(ItemPointerData));
- ItemPointerCopy(&lastleft->t_tid, pivotheaptid);
+ ItemPointerCopy(BTreeTupleGetMaxTID(lastleft), pivotheaptid);
/*
* Lehman and Yao require that the downlink to the right page, which is to
@@ -2216,9 +2255,12 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
* tiebreaker.
*/
#ifndef DEBUG_NO_TRUNCATE
- Assert(ItemPointerCompare(&lastleft->t_tid, &firstright->t_tid) < 0);
- Assert(ItemPointerCompare(pivotheaptid, &lastleft->t_tid) >= 0);
- Assert(ItemPointerCompare(pivotheaptid, &firstright->t_tid) < 0);
+ Assert(ItemPointerCompare(BTreeTupleGetMaxTID(lastleft),
+ BTreeTupleGetHeapTID(firstright)) < 0);
+ Assert(ItemPointerCompare(pivotheaptid,
+ BTreeTupleGetHeapTID(lastleft)) >= 0);
+ Assert(ItemPointerCompare(pivotheaptid,
+ BTreeTupleGetHeapTID(firstright)) < 0);
#else
/*
@@ -2231,7 +2273,7 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
* attribute values along with lastleft's heap TID value when lastleft's
* TID happens to be greater than firstright's TID.
*/
- ItemPointerCopy(&firstright->t_tid, pivotheaptid);
+ ItemPointerCopy(BTreeTupleGetHeapTID(firstright), pivotheaptid);
/*
* Pivot heap TID should never be fully equal to firstright. Note that
@@ -2240,7 +2282,8 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright,
*/
ItemPointerSetOffsetNumber(pivotheaptid,
OffsetNumberPrev(ItemPointerGetOffsetNumber(pivotheaptid)));
- Assert(ItemPointerCompare(pivotheaptid, &firstright->t_tid) < 0);
+ Assert(ItemPointerCompare(pivotheaptid,
+ BTreeTupleGetHeapTID(firstright)) < 0);
#endif
BTreeTupleSetNAtts(pivot, nkeyatts);
@@ -2330,6 +2373,25 @@ _bt_keep_natts(Relation rel, IndexTuple lastleft, IndexTuple firstright,
* leaving excessive amounts of free space on either side of page split.
* Callers can rely on the fact that attributes considered equal here are
* definitely also equal according to _bt_keep_natts.
+ *
+ * To build a posting tuple we need to ensure that all attributes
+ * of both tuples are equal. Use this function to compare them.
+ * TODO: maybe it's worth to rename the function.
+ *
+ * XXX: Obviously we need infrastructure for making sure it is okay to use
+ * this for posting list stuff. For example, non-deterministic collations
+ * cannot use compression, and will not work with what we have now.
+ *
+ * XXX: Even then, we probably also need to worry about TOAST as a special
+ * case. Don't repeat bugs like the amcheck bug that was fixed in commit
+ * eba775345d23d2c999bbb412ae658b6dab36e3e8. As the test case added in that
+ * commit shows, we need to worry about pg_attribute.attstorage changing in
+ * the underlying table due to an ALTER TABLE (and maybe a few other things
+ * like that). In general, the "TOAST input state" of a TOASTable datum isn't
+ * something that we make many guarantees about today, so even with C
+ * collation text we could in theory get different answers from
+ * _bt_keep_natts_fast() and _bt_keep_natts(). This needs to be nailed down
+ * in some way.
*/
int
_bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright)
@@ -2415,7 +2477,7 @@ _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
* Non-pivot tuples currently never use alternative heap TID
* representation -- even those within heapkeyspace indexes
*/
- if ((itup->t_info & INDEX_ALT_TID_MASK) != 0)
+ if (BTreeTupleIsPivot(itup))
return false;
/*
@@ -2470,7 +2532,7 @@ _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
* that to decide if the tuple is a pre-v11 tuple.
*/
return tupnatts == 0 ||
- ((itup->t_info & INDEX_ALT_TID_MASK) == 0 &&
+ (!BTreeTupleIsPivot(itup) &&
ItemPointerGetOffsetNumber(&(itup->t_tid)) == P_HIKEY);
}
else
@@ -2497,7 +2559,7 @@ _bt_check_natts(Relation rel, bool heapkeyspace, Page page, OffsetNumber offnum)
* heapkeyspace index pivot tuples, regardless of whether or not there are
* non-key attributes.
*/
- if ((itup->t_info & INDEX_ALT_TID_MASK) == 0)
+ if (!BTreeTupleIsPivot(itup))
return false;
/*
@@ -2549,6 +2611,8 @@ _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
if (!needheaptidspace && itemsz <= BTMaxItemSizeNoHeapTid(page))
return;
+ /* TODO correct error messages for posting tuples */
+
/*
* Internal page insertions cannot fail here, because that would mean that
* an earlier leaf level insertion that should have failed didn't
@@ -2575,3 +2639,79 @@ _bt_check_third_page(Relation rel, Relation heap, bool needheaptidspace,
"or use full text indexing."),
errtableconstraint(heap, RelationGetRelationName(rel))));
}
+
+/*
+ * Given a basic tuple that contains key datum and posting list,
+ * build a posting tuple.
+ *
+ * Basic tuple can be a posting tuple, but we only use key part of it,
+ * all ItemPointers must be passed via ipd.
+ *
+ * If nipd == 1 fallback to building a non-posting tuple.
+ * It is necessary to avoid storage overhead after posting tuple was vacuumed.
+ */
+IndexTuple
+BTreeFormPostingTuple(IndexTuple tuple, ItemPointerData *ipd, int nipd)
+{
+ uint32 keysize,
+ newsize = 0;
+ IndexTuple itup;
+
+ /* We only need key part of the tuple */
+ if (BTreeTupleIsPosting(tuple))
+ keysize = BTreeTupleGetPostingOffset(tuple);
+ else
+ keysize = IndexTupleSize(tuple);
+
+ Assert(nipd > 0);
+
+ /* Add space needed for posting list */
+ if (nipd > 1)
+ newsize = SHORTALIGN(keysize) + sizeof(ItemPointerData) * nipd;
+ else
+ newsize = keysize;
+
+ newsize = MAXALIGN(newsize);
+ itup = palloc0(newsize);
+ memcpy(itup, tuple, keysize);
+ itup->t_info &= ~INDEX_SIZE_MASK;
+ itup->t_info |= newsize;
+
+ if (nipd > 1)
+ {
+ /* Form posting tuple, fill posting fields */
+
+ /* Set meta info about the posting list */
+ itup->t_info |= INDEX_ALT_TID_MASK;
+ BTreeSetPostingMeta(itup, nipd, SHORTALIGN(keysize));
+
+ /* sort the list to preserve TID order invariant */
+ qsort((void *) ipd, nipd, sizeof(ItemPointerData),
+ (int (*) (const void *, const void *)) ItemPointerCompare);
+
+ /* Copy posting list into the posting tuple */
+ memcpy(BTreeTupleGetPosting(itup), ipd,
+ sizeof(ItemPointerData) * nipd);
+ }
+ else
+ {
+ /* To finish building of a non-posting tuple, copy TID from ipd */
+ itup->t_info &= ~INDEX_ALT_TID_MASK;
+ ItemPointerCopy(ipd, &itup->t_tid);
+ }
+
+ return itup;
+}
+
+/*
+ * Opposite of BTreeFormPostingTuple.
+ * returns regular tuple that contains the key,
+ * the tid of the new tuple is the nth tid of original tuple's posting list
+ * result tuple palloc'd in a caller's context.
+ */
+IndexTuple
+BTreeGetNthTupleOfPosting(IndexTuple tuple, int n)
+{
+ Assert(BTreeTupleIsPosting(tuple));
+ return BTreeFormPostingTuple(tuple, BTreeTupleGetPostingN(tuple, n), 1);
+}
diff --git a/src/backend/access/nbtree/nbtxlog.c b/src/backend/access/nbtree/nbtxlog.c
index dd5315c..2015a5b 100644
--- a/src/backend/access/nbtree/nbtxlog.c
+++ b/src/backend/access/nbtree/nbtxlog.c
@@ -163,6 +163,7 @@ btree_xlog_insert(bool isleaf, bool ismeta, XLogReaderState *record)
Buffer buffer;
Page page;
+
/*
* Insertion to an internal page finishes an incomplete split at the child
* level. Clear the incomplete-split flag in the child. Note: during
@@ -178,9 +179,23 @@ btree_xlog_insert(bool isleaf, bool ismeta, XLogReaderState *record)
{
Size datalen;
char *datapos = XLogRecGetBlockData(record, 0, &datalen);
+ IndexTuple neworigtup = NULL;
+
page = BufferGetPage(buffer);
+ if (xlrec->origtup_off > 0)
+ {
+ IndexTuple origtup = (IndexTuple) PageGetItem(page,
+ PageGetItemId(page, xlrec->offnum));
+ neworigtup = (IndexTuple) (datapos + xlrec->origtup_off);
+
+ Assert(MAXALIGN(IndexTupleSize(origtup)) == MAXALIGN(IndexTupleSize(neworigtup)));
+
+ memcpy(origtup, neworigtup, MAXALIGN(IndexTupleSize(neworigtup)));
+ xlrec->offnum = OffsetNumberNext(xlrec->offnum);
+ }
+
if (PageAddItem(page, (Item) datapos, datalen, xlrec->offnum,
false, false) == InvalidOffsetNumber)
elog(PANIC, "btree_xlog_insert: failed to add item");
@@ -265,9 +280,11 @@ btree_xlog_split(bool onleft, XLogReaderState *record)
BTPageOpaque lopaque = (BTPageOpaque) PageGetSpecialPointer(lpage);
OffsetNumber off;
IndexTuple newitem = NULL,
- left_hikey = NULL;
+ left_hikey = NULL,
+ replaceitem = NULL;
Size newitemsz = 0,
- left_hikeysz = 0;
+ left_hikeysz = 0,
+ replaceitemsz = 0;
Page newlpage;
OffsetNumber leftoff;
@@ -287,6 +304,14 @@ btree_xlog_split(bool onleft, XLogReaderState *record)
datapos += left_hikeysz;
datalen -= left_hikeysz;
+ if (xlrec->replaceitemoff)
+ {
+ replaceitem = (IndexTuple) datapos;
+ replaceitemsz = MAXALIGN(IndexTupleSize(replaceitem));
+ datapos += replaceitemsz;
+ datalen -= replaceitemsz;
+ }
+
Assert(datalen == 0);
newlpage = PageGetTempPageCopySpecial(lpage);
@@ -304,6 +329,15 @@ btree_xlog_split(bool onleft, XLogReaderState *record)
Size itemsz;
IndexTuple item;
+ if (off == xlrec->replaceitemoff)
+ {
+ if (PageAddItem(newlpage, (Item) replaceitem, replaceitemsz, leftoff,
+ false, false) == InvalidOffsetNumber)
+ elog(ERROR, "failed to add new item to left page after split");
+ leftoff = OffsetNumberNext(leftoff);
+ continue;
+ }
+
/* add the new item if it was inserted on left page */
if (onleft && off == xlrec->newitemoff)
{
@@ -386,8 +420,8 @@ btree_xlog_vacuum(XLogReaderState *record)
Buffer buffer;
Page page;
BTPageOpaque opaque;
-#ifdef UNUSED
xl_btree_vacuum *xlrec = (xl_btree_vacuum *) XLogRecGetData(record);
+#ifdef UNUSED
/*
* This section of code is thought to be no longer needed, after analysis
@@ -478,14 +512,34 @@ btree_xlog_vacuum(XLogReaderState *record)
if (len > 0)
{
- OffsetNumber *unused;
- OffsetNumber *unend;
+ if (xlrec->nremaining)
+ {
+ OffsetNumber *remainingoffset;
+ IndexTuple remaining;
+ Size itemsz;
+
+ remainingoffset = (OffsetNumber *)
+ (ptr + xlrec->ndeleted * sizeof(OffsetNumber));
+ remaining = (IndexTuple) ((char *) remainingoffset +
+ xlrec->nremaining * sizeof(OffsetNumber));
+
+ /* Handle posting tuples */
+ for (int i = 0; i < xlrec->nremaining; i++)
+ {
+ PageIndexTupleDelete(page, remainingoffset[i]);
- unused = (OffsetNumber *) ptr;
- unend = (OffsetNumber *) ((char *) ptr + len);
+ itemsz = MAXALIGN(IndexTupleSize(remaining));
+
+ if (PageAddItem(page, (Item) remaining, itemsz, remainingoffset[i],
+ false, false) == InvalidOffsetNumber)
+ elog(PANIC, "btree_xlog_vacuum: failed to add remaining item");
+
+ remaining = (IndexTuple) ((char *) remaining + itemsz);
+ }
+ }
- if ((unend - unused) > 0)
- PageIndexMultiDelete(page, unused, unend - unused);
+ if (xlrec->ndeleted)
+ PageIndexMultiDelete(page, (OffsetNumber *) ptr, xlrec->ndeleted);
}
/*
diff --git a/src/backend/access/rmgrdesc/nbtdesc.c b/src/backend/access/rmgrdesc/nbtdesc.c
index a14eb79..243e464 100644
--- a/src/backend/access/rmgrdesc/nbtdesc.c
+++ b/src/backend/access/rmgrdesc/nbtdesc.c
@@ -31,6 +31,7 @@ btree_desc(StringInfo buf, XLogReaderState *record)
xl_btree_insert *xlrec = (xl_btree_insert *) rec;
appendStringInfo(buf, "off %u", xlrec->offnum);
+ appendStringInfo(buf, "origtup_off %lu", xlrec->origtup_off);
break;
}
case XLOG_BTREE_SPLIT_L:
@@ -46,8 +47,10 @@ btree_desc(StringInfo buf, XLogReaderState *record)
{
xl_btree_vacuum *xlrec = (xl_btree_vacuum *) rec;
- appendStringInfo(buf, "lastBlockVacuumed %u",
- xlrec->lastBlockVacuumed);
+ appendStringInfo(buf, "lastBlockVacuumed %u; nremaining %u; ndeleted %u",
+ xlrec->lastBlockVacuumed,
+ xlrec->nremaining,
+ xlrec->ndeleted);
break;
}
case XLOG_BTREE_DELETE:
diff --git a/src/include/access/itup.h b/src/include/access/itup.h
index 744ffb6..b10c0d5 100644
--- a/src/include/access/itup.h
+++ b/src/include/access/itup.h
@@ -141,6 +141,10 @@ typedef IndexAttributeBitMapData * IndexAttributeBitMap;
* On such a page, N tuples could take one MAXALIGN quantum less space than
* estimated here, seemingly allowing one more tuple than estimated here.
* But such a page always has at least MAXALIGN special space, so we're safe.
+ *
+ * Note: btree leaf pages may contain posting tuples, which store duplicates
+ * in a more effective way, so they may contain more tuples.
+ * Use MaxPostingIndexTuplesPerPage instead.
*/
#define MaxIndexTuplesPerPage \
((int) ((BLCKSZ - SizeOfPageHeaderData) / \
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 52eafe6..d2700fc 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -234,8 +234,7 @@ typedef struct BTMetaPageData
* t_tid | t_info | key values | INCLUDE columns, if any
*
* t_tid points to the heap TID, which is a tiebreaker key column as of
- * BTREE_VERSION 4. Currently, the INDEX_ALT_TID_MASK status bit is never
- * set for non-pivot tuples.
+ * BTREE_VERSION 4.
*
* All other types of index tuples ("pivot" tuples) only have key columns,
* since pivot tuples only exist to represent how the key space is
@@ -252,6 +251,39 @@ typedef struct BTMetaPageData
* omitted rather than truncated, since its representation is different to
* the non-pivot representation.)
*
+ * Non-pivot posting tuple format:
+ * t_tid | t_info | key values | INCLUDE columns, if any | posting_list[]
+ *
+ * In order to store duplicated keys more effectively,
+ * we use special format of tuples - posting tuples.
+ * posting_list is an array of ItemPointerData.
+ *
+ * This type of compression never applies to system indexes, unique indexes
+ * or indexes with INCLUDEd columns.
+ *
+ * To differ posting tuples we use INDEX_ALT_TID_MASK flag in t_info and
+ * BT_IS_POSTING flag in t_tid.
+ * These flags redefine the content of the posting tuple's tid:
+ * - t_tid.ip_blkid contains offset of the posting list.
+ * - t_tid offset field contains number of posting items this tuple contain
+ *
+ * The 12 least significant offset bits from t_tid are used to represent
+ * the number of posting items in posting tuples, leaving 4 status
+ * bits (BT_RESERVED_OFFSET_MASK bits), 3 of which that are reserved for
+ * future use.
+ * BT_N_POSTING_OFFSET_MASK is large enough to store any number of posting
+ * tuples, which is constrainted by BTMaxItemSize.
+
+ * If page contains so many duplicates, that they do not fit into one posting
+ * tuple (bounded by BTMaxItemSize and ), page may contain several posting
+ * tuples with the same key.
+ * Also page can contain both posting and non-posting tuples with the same key.
+ * Currently, posting tuples always contain at least two TIDs in the posting
+ * list.
+ *
+ * Posting tuples always have the same number of attributes as the index has
+ * generally.
+ *
* Pivot tuple format:
*
* t_tid | t_info | key values | [heap TID]
@@ -281,23 +313,144 @@ typedef struct BTMetaPageData
* bits (BT_RESERVED_OFFSET_MASK bits), 3 of which that are reserved for
* future use. BT_N_KEYS_OFFSET_MASK should be large enough to store any
* number of columns/attributes <= INDEX_MAX_KEYS.
+ * BT_IS_POSTING bit must be unset for pivot tuples, since we use it
+ * to distinct posting tuples from pivot tuples.
*
* Note well: The macros that deal with the number of attributes in tuples
- * assume that a tuple with INDEX_ALT_TID_MASK set must be a pivot tuple,
- * and that a tuple without INDEX_ALT_TID_MASK set must be a non-pivot
- * tuple (or must have the same number of attributes as the index has
- * generally in the case of !heapkeyspace indexes). They will need to be
- * updated if non-pivot tuples ever get taught to use INDEX_ALT_TID_MASK
- * for something else.
+ * assume that a tuple with INDEX_ALT_TID_MASK set must be a pivot tuple or
+ * non-pivot posting tuple, and that a tuple without INDEX_ALT_TID_MASK set
+ * must be a non-pivot tuple (or must have the same number of attributes as
+ * the index has generally in the case of !heapkeyspace indexes).
*/
#define INDEX_ALT_TID_MASK INDEX_AM_RESERVED_BIT
/* Item pointer offset bits */
#define BT_RESERVED_OFFSET_MASK 0xF000
#define BT_N_KEYS_OFFSET_MASK 0x0FFF
+#define BT_N_POSTING_OFFSET_MASK 0x0FFF
#define BT_HEAP_TID_ATTR 0x1000
+#define BT_IS_POSTING 0x2000
+
+#define BTreeTupleIsPosting(itup) \
+ ( \
+ ((itup)->t_info & INDEX_ALT_TID_MASK && \
+ ((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) != 0))\
+ )
+
+#define BTreeTupleIsPivot(itup) \
+ ( \
+ ((itup)->t_info & INDEX_ALT_TID_MASK && \
+ ((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) == 0))\
+ )
+
+/*
+ * MaxPostingIndexTuplesPerPage is an upper bound on the number of tuples
+ * that can fit on one btree leaf page.
+ *
+ * Btree leaf pages may contain posting tuples, which store duplicates
+ * in a more effective way, so MaxPostingIndexTuplesPerPage is larger then
+ * MaxIndexTuplesPerPage.
+ *
+ * Each leaf page must contain at least three items, so estimate it as
+ * if we have three posting tuples with minimal size keys.
+ */
+#define MaxPostingIndexTuplesPerPage \
+ ((int) ((BLCKSZ - SizeOfPageHeaderData - \
+ 3*((MAXALIGN(sizeof(IndexTupleData) + 1) + sizeof(ItemIdData))) )) / \
+ (sizeof(ItemPointerData)))
+
+/*
+ * Btree-private state needed to build posting tuples.
+ * ipd is a posting list - an array of ItemPointerData.
+ *
+ * Iterating over tuples during index build or applying compression to a
+ * single page, we remember a tuple in itupprev, then compare the next one
+ * with it. If tuples are equal, save their TIDs in the posting list.
+ * ntuples contains the size of the posting list.
+ *
+ * Use maxitemsize and maxpostingsize to ensure that resulting posting tuple
+ * will satisfy BTMaxItemSize.
+ */
+typedef struct BTCompressState
+{
+ Size maxitemsize;
+ Size maxpostingsize;
+ IndexTuple itupprev;
+ int ntuples;
+ ItemPointerData *ipd;
+} BTCompressState;
+
+/* macros to work with posting tuples *BEGIN* */
+#define BTreeTupleSetBtIsPosting(itup) \
+ do { \
+ Assert((itup)->t_info & INDEX_ALT_TID_MASK); \
+ Assert(!((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) != 0)); \
+ ItemPointerSetOffsetNumber(&(itup)->t_tid, \
+ ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) | BT_IS_POSTING); \
+ } while(0)
+
+#define BTreeTupleClearBtIsPosting(itup) \
+ do { \
+ ItemPointerSetOffsetNumber(&(itup)->t_tid, \
+ ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & ~BT_IS_POSTING); \
+ } while(0)
+
+#define BTreeTupleGetNPosting(itup) \
+ ( \
+ AssertMacro(BTreeTupleIsPosting(itup)), \
+ ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_N_POSTING_OFFSET_MASK \
+ )
+
+#define BTreeTupleSetNPosting(itup, n) \
+ do { \
+ ItemPointerSetOffsetNumber(&(itup)->t_tid, (n) & BT_N_POSTING_OFFSET_MASK); \
+ BTreeTupleSetBtIsPosting(itup); \
+ } while(0)
+
+/*
+ * If tuple is posting, t_tid.ip_blkid contains offset of the posting list.
+ * Caller is responsible for checking BTreeTupleIsPosting to ensure that it
+ * will get what is expected.
+ */
+#define BTreeTupleGetPostingOffset(itup) \
+ ( \
+ AssertMacro(BTreeTupleIsPosting(itup)), \
+ ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid)) \
+ )
+#define BTreeTupleSetPostingOffset(itup, offset) \
+ ( \
+ AssertMacro(BTreeTupleIsPosting(itup)), \
+ ItemPointerSetBlockNumber(&((itup)->t_tid), (offset)) \
+ )
+#define BTreeSetPostingMeta(itup, nposting, off) \
+ do { \
+ BTreeTupleSetNPosting(itup, nposting); \
+ BTreeTupleSetPostingOffset(itup, off); \
+ } while(0)
+
+#define BTreeTupleGetPosting(itup) \
+ (ItemPointerData*) ((char*)(itup) + BTreeTupleGetPostingOffset(itup))
+#define BTreeTupleGetPostingN(itup,n) \
+ (ItemPointerData*) (BTreeTupleGetPosting(itup) + (n))
+
+/*
+ * Posting tuples always contain more than one TID. The minimum TID can be
+ * accessed using BTreeTupleGetHeapTID(). The maximum is accessed using
+ * BTreeTupleGetMaxTID().
+ */
+#define BTreeTupleGetMaxTID(itup) \
+ ( \
+ ((itup)->t_info & INDEX_ALT_TID_MASK && \
+ ((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING))) ? \
+ ( \
+ (ItemPointer) (BTreeTupleGetPosting(itup) + (BTreeTupleGetNPosting(itup)-1)) \
+ ) \
+ : \
+ (ItemPointer) &((itup)->t_tid) \
+ )
+/* macros to work with posting tuples *END* */
-/* Get/set downlink block number */
+/* Get/set downlink block number */
#define BTreeInnerTupleGetDownLink(itup) \
ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid))
#define BTreeInnerTupleSetDownLink(itup, blkno) \
@@ -326,7 +479,8 @@ typedef struct BTMetaPageData
*/
#define BTreeTupleGetNAtts(itup, rel) \
( \
- (itup)->t_info & INDEX_ALT_TID_MASK ? \
+ ((itup)->t_info & INDEX_ALT_TID_MASK && \
+ ((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) == 0)) ? \
( \
ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_N_KEYS_OFFSET_MASK \
) \
@@ -335,6 +489,7 @@ typedef struct BTMetaPageData
)
#define BTreeTupleSetNAtts(itup, n) \
do { \
+ Assert(!BTreeTupleIsPosting(itup)); \
(itup)->t_info |= INDEX_ALT_TID_MASK; \
ItemPointerSetOffsetNumber(&(itup)->t_tid, (n) & BT_N_KEYS_OFFSET_MASK); \
} while(0)
@@ -342,6 +497,8 @@ typedef struct BTMetaPageData
/*
* Get tiebreaker heap TID attribute, if any. Macro works with both pivot
* and non-pivot tuples, despite differences in how heap TID is represented.
+ *
+ * For non-pivot posting tuples this returns the first tid from posting list.
*/
#define BTreeTupleGetHeapTID(itup) \
( \
@@ -351,7 +508,10 @@ typedef struct BTMetaPageData
(ItemPointer) (((char *) (itup) + IndexTupleSize(itup)) - \
sizeof(ItemPointerData)) \
) \
- : (itup)->t_info & INDEX_ALT_TID_MASK ? NULL : (ItemPointer) &((itup)->t_tid) \
+ : (itup)->t_info & INDEX_ALT_TID_MASK ? \
+ (((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) != 0) ? \
+ (ItemPointer) BTreeTupleGetPosting(itup) : NULL) \
+ : (ItemPointer) &((itup)->t_tid) \
)
/*
* Set the heap TID attribute for a tuple that uses the INDEX_ALT_TID_MASK
@@ -360,6 +520,7 @@ typedef struct BTMetaPageData
#define BTreeTupleSetAltHeapTID(itup) \
do { \
Assert((itup)->t_info & INDEX_ALT_TID_MASK); \
+ Assert(!((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING) != 0)); \
ItemPointerSetOffsetNumber(&(itup)->t_tid, \
ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) | BT_HEAP_TID_ATTR); \
} while(0)
@@ -500,6 +661,12 @@ typedef struct BTInsertStateData
Buffer buf;
/*
+ * if _bt_binsrch_insert() found the location inside existing posting
+ * list, save the position inside the list.
+ */
+ int in_posting_offset;
+
+ /*
* Cache of bounds within the current buffer. Only used for insertions
* where _bt_check_unique is called. See _bt_binsrch_insert and
* _bt_findinsertloc for details.
@@ -566,6 +733,8 @@ typedef struct BTScanPosData
* location in the associated tuple storage workspace.
*/
int nextTupleOffset;
+ /* prevTupleOffset is for posting list handling */
+ int prevTupleOffset;
/*
* The items array is always ordered in index order (ie, increasing
@@ -578,7 +747,7 @@ typedef struct BTScanPosData
int lastItem; /* last valid index in items[] */
int itemIndex; /* current index in items[] */
- BTScanPosItem items[MaxIndexTuplesPerPage]; /* MUST BE LAST */
+ BTScanPosItem items[MaxPostingIndexTuplesPerPage]; /* MUST BE LAST */
} BTScanPosData;
typedef BTScanPosData *BTScanPos;
@@ -732,7 +901,9 @@ extern bool _bt_doinsert(Relation rel, IndexTuple itup,
IndexUniqueCheck checkUnique, Relation heapRel);
extern Buffer _bt_getstackbuf(Relation rel, BTStack stack, BlockNumber child);
extern void _bt_finish_split(Relation rel, Buffer bbuf, BTStack stack);
-
+extern void _bt_replace_and_insert(Buffer buf, Page page,
+ IndexTuple neworigtup, IndexTuple newitup,
+ OffsetNumber newitemoff, bool need_xlog);
/*
* prototypes for functions in nbtsplitloc.c
*/
@@ -762,6 +933,8 @@ extern void _bt_delitems_delete(Relation rel, Buffer buf,
OffsetNumber *itemnos, int nitems, Relation heapRel);
extern void _bt_delitems_vacuum(Relation rel, Buffer buf,
OffsetNumber *itemnos, int nitems,
+ OffsetNumber *remainingoffset,
+ IndexTuple *remaining, int nremaining,
BlockNumber lastBlockVacuumed);
extern int _bt_pagedel(Relation rel, Buffer buf);
@@ -774,6 +947,8 @@ extern Buffer _bt_moveright(Relation rel, BTScanInsert key, Buffer buf,
bool forupdate, BTStack stack, int access, Snapshot snapshot);
extern OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate);
extern int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum);
+extern int32 _bt_compare_posting(Relation rel, BTScanInsert key, Page page,
+ OffsetNumber offnum, int *in_posting_offset);
extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
extern bool _bt_next(IndexScanDesc scan, ScanDirection dir);
extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost,
@@ -812,6 +987,9 @@ extern bool _bt_check_natts(Relation rel, bool heapkeyspace, Page page,
OffsetNumber offnum);
extern void _bt_check_third_page(Relation rel, Relation heap,
bool needheaptidspace, Page page, IndexTuple newtup);
+extern IndexTuple BTreeFormPostingTuple(IndexTuple tuple, ItemPointerData *ipd,
+ int nipd);
+extern IndexTuple BTreeGetNthTupleOfPosting(IndexTuple tuple, int n);
/*
* prototypes for functions in nbtvalidate.c
@@ -824,5 +1002,7 @@ extern bool btvalidate(Oid opclassoid);
extern IndexBuildResult *btbuild(Relation heap, Relation index,
struct IndexInfo *indexInfo);
extern void _bt_parallel_build_main(dsm_segment *seg, shm_toc *toc);
+extern void _bt_add_posting_item(BTCompressState *compressState,
+ IndexTuple itup);
#endif /* NBTREE_H */
diff --git a/src/include/access/nbtxlog.h b/src/include/access/nbtxlog.h
index afa614d..f1ef584 100644
--- a/src/include/access/nbtxlog.h
+++ b/src/include/access/nbtxlog.h
@@ -61,16 +61,24 @@ typedef struct xl_btree_metadata
* This data record is used for INSERT_LEAF, INSERT_UPPER, INSERT_META.
* Note that INSERT_META implies it's not a leaf page.
*
- * Backup Blk 0: original page (data contains the inserted tuple)
+ * Backup Blk 0: original page (data contains the inserted tuple);
+ * if origtup_off is not 0, data also contains 'neworigtup' -
+ * tuple to replace original (see comments in bt_replace_and_insert()).
+ * TODO probably it would be enough to keep just a flag to point out that
+ * data contains 'neworigtup' and compute its offset
+ * as we know it follows the tuple, but I am afraid that
+ * it will break alignment, will it?
* Backup Blk 1: child's left sibling, if INSERT_UPPER or INSERT_META
* Backup Blk 2: xl_btree_metadata, if INSERT_META
+ *
*/
typedef struct xl_btree_insert
{
OffsetNumber offnum;
+ Size origtup_off;
} xl_btree_insert;
-#define SizeOfBtreeInsert (offsetof(xl_btree_insert, offnum) + sizeof(OffsetNumber))
+#define SizeOfBtreeInsert (offsetof(xl_btree_insert, origtup_off) + sizeof(Size))
/*
* On insert with split, we save all the items going into the right sibling
@@ -96,6 +104,12 @@ typedef struct xl_btree_insert
* An IndexTuple representing the high key of the left page must follow with
* either variant.
*
+ * In case, split included insertion into the middle of the posting tuple, and
+ * thus required posting tuple replacement, it also contains 'neworigtup',
+ * which must replace original posting tuple at replaceitemoff offset.
+ * TODO further optimization is to add it to xlog only if it remains on the
+ * left page.
+ *
* Backup Blk 1: new right page
*
* The right page's data portion contains the right page's tuples in the form
@@ -113,9 +127,10 @@ typedef struct xl_btree_split
uint32 level; /* tree level of page being split */
OffsetNumber firstright; /* first item moved to right page */
OffsetNumber newitemoff; /* new item's offset (if placed on left page) */
+ OffsetNumber replaceitemoff; /* offset of the posting item to replace with (neworigtup) */
} xl_btree_split;
-#define SizeOfBtreeSplit (offsetof(xl_btree_split, newitemoff) + sizeof(OffsetNumber))
+#define SizeOfBtreeSplit (offsetof(xl_btree_split, replaceitemoff) + sizeof(OffsetNumber))
/*
* This is what we need to know about delete of individual leaf index tuples.
@@ -173,10 +188,19 @@ typedef struct xl_btree_vacuum
{
BlockNumber lastBlockVacuumed;
- /* TARGET OFFSET NUMBERS FOLLOW */
+ /*
+ * This field helps us to find beginning of the remaining tuples from
+ * postings which follow array of offset numbers.
+ */
+ uint32 nremaining;
+ uint32 ndeleted;
+
+ /* REMAINING OFFSET NUMBERS FOLLOW (nremaining values) */
+ /* REMAINING TUPLES TO INSERT FOLLOW (if nremaining > 0) */
+ /* TARGET OFFSET NUMBERS FOLLOW (if any) */
} xl_btree_vacuum;
-#define SizeOfBtreeVacuum (offsetof(xl_btree_vacuum, lastBlockVacuumed) + sizeof(BlockNumber))
+#define SizeOfBtreeVacuum (offsetof(xl_btree_vacuum, ndeleted) + sizeof(BlockNumber))
/*
* This is what we need to know about marking an empty branch for deletion.
