Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hj0Vj-0000uH-5E for pgsql-hackers@arkaria.postgresql.org; Thu, 04 Jul 2019 12:06:49 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hj0Vh-00015Y-CB for pgsql-hackers@arkaria.postgresql.org; Thu, 04 Jul 2019 12:06:45 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hj0Vg-00015R-RQ for pgsql-hackers@lists.postgresql.org; Thu, 04 Jul 2019 12:06:45 +0000 Received: from cyclops.postgrespro.ru ([93.174.131.138] helo=mail.postgrespro.ru) by magus.postgresql.org with esmtp (Exim 4.89) (envelope-from ) id 1hj0Vd-00055W-05 for pgsql-hackers@postgresql.org; Thu, 04 Jul 2019 12:06:44 +0000 Received: from localhost (localhost [127.0.0.1]) by mail.postgrespro.ru (Postfix) with ESMTP id A944A21C4316 for ; Thu, 4 Jul 2019 15:06:39 +0300 (MSK) X-Virus-Scanned: Debian amavisd-new at postgrespro.ru X-Spam-Flag: NO X-Spam-Score: 0 X-Spam-Level: X-Spam-Status: No, score=x tagged_above=-99 required=4 WHITELISTED tests=[] autolearn=unavailable Received: from [192.168.27.74] (gw.postgrespro.ru [93.174.131.141]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mail.postgrespro.ru (Postfix) with ESMTPSA id 3ED3821C4303 for ; Thu, 4 Jul 2019 15:06:39 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1562241999; bh=2y83Miamh5N/sq9uq7sSbjVWPDtPUV3zfaK4ZttTPJY=; h=From:Subject:To:References:Date:In-Reply-To; b=WMO9oJp6U1wC20a+hFAeIG+eBZOioWm0Z3ZJpCm5c3iqaIRzXXs0KxmNNpIT9n1Ti PwVws/2AXyMLsVHzr9jabEtqGpbiTFz4keR+1e3XPeSML7T4LYRKwhf4ggPc/fNGV/ 7c3rfJ3/ys9oBO1VOkSZRBZ3S/KPe+hvyhtQUPRg= From: Anastasia Lubennikova Subject: Re: [HACKERS] [WIP] Effective storage of duplicates in B-tree index. To: pgsql-hackers@postgresql.org References: <55E4051B.7020209@postgrespro.ru> <56AA2081.1080001@postgrespro.ru> <56AA3E06.8040006@postgrespro.ru> <56AB6D30.2040900@postgrespro.ru> <20160129184733.2ca9026a@fujitsu> <56AB9866.6050207@postgrespro.ru> <56C5FCE1.1090509@postgrespro.ru> <56C5FF80.5050905@postgrespro.ru> <56E6B64E.6000101@pgmasters.net> <56E84834.2070003@postgrespro.ru> <56EC38A9.9030303@postgrespro.ru> Message-ID: <4ab6e2db-bcee-f4cf-0916-3a06e6ccbb55@postgrespro.ru> Date: Thu, 4 Jul 2019 15:06:38 +0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 In-Reply-To: <56EC38A9.9030303@postgrespro.ru> Content-Type: multipart/mixed; boundary="------------B094494E4371AEA342B2A256" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk This is a multi-part message in MIME format. --------------B094494E4371AEA342B2A256 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 8bit The new version of the patch is attached. This version is even simpler than the previous one, thanks to the recent btree design changes and all the feedback I received. I consider it ready for review and testing. [feature overview] This patch implements the deduplication of btree non-pivot tuples on leaf pages in a manner similar to GIN index "posting lists". Non-pivot posting tuple has following format: t_tid | t_info | key values | posting_list[] Where t_tid and t_info fields are used to store meta info about tuple's posting list. posting list is an array of ItemPointerData. Currently, compression is applied to all indexes except system indexes, unique indexes, and indexes with included columns. On insertion, compression applied not to each tuple, but to the page before split. If the target page is full, we try to compress it. [benchmark results] idx ON tbl(c1); index contains 10000000 integer values i - number of distinct values in the index. So i=1 means that all rows have the same key, and i=10000000 means that all keys are different. i / old size (MB) / new size (MB) 1            215    88 1000        215    90 100000        215    71 10000000    214    214 For more, see the attached diagram with test results. [future work] Many things can be improved in this feature. Personally, I'd prefer to keep this patch as small as possible and work on other improvements after a basic part is committed. Though, I understand that some of these can be considered essential for this patch to be approved. 1. Implement a split of the posting tuples on a page split. 2. Implement microvacuum of posting tuples. 3. Add a flag into pg_index, which allows enabling/disabling compression for a particular index. 4. Implement posting list compression. -- Anastasia Lubennikova Postgres Professional:http://www.postgrespro.com The Russian Postgres Company --------------B094494E4371AEA342B2A256 Content-Type: text/x-patch; name="btree_compression_pg12_v1.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="btree_compression_pg12_v1.patch" diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c index 602f884..fce499b 100644 --- a/src/backend/access/nbtree/nbtinsert.c +++ b/src/backend/access/nbtree/nbtinsert.c @@ -20,6 +20,7 @@ #include "access/tableam.h" #include "access/transam.h" #include "access/xloginsert.h" +#include "catalog/catalog.h" #include "miscadmin.h" #include "storage/lmgr.h" #include "storage/predicate.h" @@ -56,6 +57,8 @@ static void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf, 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 bool 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. @@ -759,6 +762,12 @@ _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) + _bt_compress_one_page(rel, insertstate->buf, heapRel); } else { @@ -806,6 +815,11 @@ _bt_findinsertloc(Relation rel, } /* + * Before considering moving right, try to compress the page + */ + _bt_compress_one_page(rel, insertstate->buf, heapRel); + + /* * Nope, so check conditions (b) and (c) enumerated above * * The earlier _bt_check_unique() call may well have established a @@ -2286,3 +2300,232 @@ _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 bool +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(DEBUG4, "insert_itupprev_to_page. failed"); + /* + * this may happen if tuple is bigger than freespace + * fallback to uncompressed page case + */ + if (compressState->ntuples > 0) + pfree(to_insert); + return false; + } + + if (compressState->ntuples > 0) + pfree(to_insert); + compressState->ntuples = 0; + return true; +} + +/* + * 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 n_posting_on_page = 0; + int natts = IndexRelationGetNumberOfAttributes(rel); + + /* + * Don't use compression for indexes with INCLUDEd columns, + * system indexes and unique indexes. + */ + use_compression = ((IndexRelationGetNumberOfKeyAttributes(rel) == + IndexRelationGetNumberOfAttributes(rel)) + && (!IsSystemRelation(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; + + /* + * Scan over all items to see which ones can be compressed + */ + minoff = P_FIRSTDATAKEY(opaque); + maxoff = PageGetMaxOffsetNumber(page); + + /* + * Heuristic to avoid trying to compress page + * that has already contain mostly compressed items + */ + for (offnum = minoff; + offnum <= maxoff; + offnum = OffsetNumberNext(offnum)) + { + ItemId itemid = PageGetItemId(page, P_HIKEY); + IndexTuple item = (IndexTuple) PageGetItem(page, itemid); + + if (BTreeTupleIsPosting(item)) + n_posting_on_page++; + } + /* + * If we have only 10 uncompressed items on the full page, + * it probably won't worth to compress them. + */ + if (maxoff - n_posting_on_page < 10) + return; + + 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) + { + /* + * Should never happen. Anyway, fallback gently to scenario of + * incompressible page and just return from function. + */ + elog(DEBUG4, "_bt_compress_one_page. failed to insert highkey to newpage"); + return; + } + } + + /* 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); + + /* + * We do not expect to meet any DEAD items, since this + * function is called right after _bt_vacuum_one_page(). + * If for some reason we found dead item, don't compress it, + * to allow upcoming microvacuum or vacuum clean it up. + */ + if(ItemIdIsDead(itemId)) + continue; + + 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) + { + /* Tuples are equal. Create or update posting. */ + if (compressState->maxitemsize > + MAXALIGN(((IndexTupleSize(compressState->itupprev) + + (compressState->ntuples + itup_ntuples+1)*sizeof(ItemPointerData))))) + add_item_to_posting(compressState, itup); + else + /* If posting is too big, insert it on page and continue.*/ + if (!insert_itupprev_to_page(newpage, compressState)) + { + elog(DEBUG4, "_bt_compress_one_page. failed to insert posting"); + return; + } + } + else + { + /* + * Tuples are not equal. Insert itupprev into index. + * Save current tuple for the next iteration. + */ + if (!insert_itupprev_to_page(newpage, compressState)) + { + elog(DEBUG4, "_bt_compress_one_page. failed to insert posting"); + return; + } + } + } + + /* + * 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.*/ + if (!insert_itupprev_to_page(newpage, compressState)) + { + elog(DEBUG4, "_bt_compress_one_page. failed to insert posting for last item"); + return; + } + + 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"); + return; +} diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c index de4d4ef..681077f 100644 --- a/src/backend/access/nbtree/nbtpage.c +++ b/src/backend/access/nbtree/nbtpage.c @@ -1024,14 +1024,54 @@ _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; + int i; + Size itemsz; + Size remaining_sz = 0; + char *remaining_buf = NULL; + + /* XLOG stuff, buffer for remainings */ + if (nremaining && RelationNeedsWAL(rel)) + { + Size offset = 0; + + for (i = 0; i < nremaining; i++) + remaining_sz += MAXALIGN(IndexTupleSize(remaining[i])); + + remaining_buf = palloc0(remaining_sz); + for (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 (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); @@ -1061,6 +1101,9 @@ _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); @@ -1074,6 +1117,20 @@ _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 85e54ac..5a7d7bd 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -97,8 +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); /* * Btree handler function: return IndexAmRoutine with access method parameters * and callbacks. @@ -1069,7 +1069,7 @@ 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 +1193,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 +1232,7 @@ restart: * callback function. */ ndeletable = 0; + nremaining = 0; minoff = P_FIRSTDATAKEY(opaque); maxoff = PageGetMaxOffsetNumber(page); if (callback) @@ -1242,31 +1246,77 @@ 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; + + 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 +1324,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 +1341,7 @@ restart: * that. */ _bt_delitems_vacuum(rel, buf, deletable, ndeletable, + remainingoffset, remaining, nremaining, vstate->lastBlockVacuumed); /* @@ -1376,6 +1427,43 @@ 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 i, + 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 (i = 0; i < nitem; 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 c655dad..594936d 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -30,6 +30,8 @@ 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, @@ -1410,6 +1412,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum) int itemIndex; bool continuescan; int indnatts; + int i; /* * We must have the buffer pinned and locked, but the usual macro can't be @@ -1456,6 +1459,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 @@ -1490,8 +1494,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)) + { + for (i = 0; i < BTreeTupleGetNPosting(itup); i++) + { + _bt_savePostingitem(so, itemIndex, offnum, + BTreeTupleGetPostingN(itup, i), + itup, i); + itemIndex++; + } + } + else + { + _bt_saveitem(so, itemIndex, offnum, itup); + itemIndex++; + } + } /* When !continuescan, there can't be any more matches, so stop */ if (!continuescan) @@ -1524,7 +1542,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; @@ -1532,7 +1550,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum) else { /* load items[] in descending order */ - itemIndex = MaxIndexTuplesPerPage; + itemIndex = MaxPostingIndexTuplesPerPage; offnum = Min(offnum, maxoff); @@ -1574,8 +1592,22 @@ _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)) + { + for (i = 0; i < BTreeTupleGetNPosting(itup); i++) + { + itemIndex--; + _bt_savePostingitem(so, itemIndex, offnum, + BTreeTupleGetPostingN(itup, i), + itup, i); + } + } + else + { + itemIndex--; + _bt_saveitem(so, itemIndex, offnum, itup); + } + } if (!continuescan) { @@ -1589,8 +1621,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); @@ -1603,6 +1635,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) @@ -1615,6 +1649,34 @@ _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 * @@ -2221,6 +2283,7 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir) /* OK, itemIndex says what to return */ currItem = &so->currPos.items[so->currPos.itemIndex]; + scan->xs_heaptid = currItem->heapTid; if (scan->xs_want_itup) scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset); diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c index d0b9013..59f702b 100644 --- a/src/backend/access/nbtree/nbtsort.c +++ b/src/backend/access/nbtree/nbtsort.c @@ -65,6 +65,7 @@ #include "access/xact.h" #include "access/xlog.h" #include "access/xloginsert.h" +#include "catalog/catalog.h" #include "catalog/index.h" #include "commands/progress.h" #include "miscadmin.h" @@ -76,6 +77,7 @@ #include "utils/tuplesort.h" + /* Magic numbers for parallel state sharing */ #define PARALLEL_KEY_BTREE_SHARED UINT64CONST(0xA000000000000001) #define PARALLEL_KEY_TUPLESORT UINT64CONST(0xA000000000000002) @@ -288,6 +290,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 insert_itupprev_to_page_buildadd(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, @@ -972,6 +976,11 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup) * only shift the line pointer array back and forth, and overwrite * the tuple space previously occupied by oitup. This is fairly * cheap. + * + * 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); @@ -1011,6 +1020,7 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup) * the minimum key for the new page. */ state->btps_minkey = CopyIndexTuple(oitup); + Assert(!BTreeTupleIsPosting(state->btps_minkey)); /* * Set the sibling links for both pages. @@ -1050,8 +1060,35 @@ _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup) if (last_off == P_HIKEY) { Assert(state->btps_minkey == NULL); - state->btps_minkey = CopyIndexTuple(itup); - /* _bt_sortaddtup() will perform full truncation later */ + + /* + * Stashed copy must be a non-posting tuple, + * with truncated posting list and correct t_tid + * since we're going to use it to build downlink. + */ + if (BTreeTupleIsPosting(itup)) + { + Size keytupsz; + IndexTuple keytup; + + /* + * Form key tuple, that doesn't contain any ipd. + * NOTE: since we'll need TID later, set t_tid to + * the first t_tid from posting list. + */ + keytupsz = BTreeTupleGetPostingOffset(itup); + keytup = palloc0(keytupsz); + memcpy(keytup, itup, keytupsz); + + keytup->t_info &= ~INDEX_SIZE_MASK; + keytup->t_info |= keytupsz; + ItemPointerCopy(BTreeTupleGetPosting(itup), &keytup->t_tid); + state->btps_minkey = CopyIndexTuple(keytup); + pfree(keytup); + } + else + state->btps_minkey = CopyIndexTuple(itup); /* _bt_sortaddtup() will perform full truncation later */ + BTreeTupleSetNAtts(state->btps_minkey, 0); } @@ -1137,6 +1174,87 @@ _bt_uppershutdown(BTWriteState *wstate, BTPageState *state) } /* + * Add new tuple (posting or non-posting) to the page, while building index. + */ +void +insert_itupprev_to_page_buildadd(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 +add_item_to_posting(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. */ @@ -1150,9 +1268,21 @@ _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, + * system indexes and unique indexes. + */ + use_compression = ((IndexRelationGetNumberOfKeyAttributes(wstate->index) == + IndexRelationGetNumberOfAttributes(wstate->index)) + && (!IsSystemRelation(wstate->index)) + && (!wstate->index->rd_index->indisunique)); if (merge) { @@ -1266,19 +1396,83 @@ _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. */ + if ((compressState->ntuples+1)*sizeof(ItemPointerData) < compressState->maxpostingsize) + add_item_to_posting(compressState, itup); + else + /* If posting is too big, insert it on page and continue.*/ + insert_itupprev_to_page_buildadd(wstate, state, compressState); + } + else + { + /* + * Tuples are not equal. Insert itupprev into index. + * Save current tuple for the next iteration. + */ + insert_itupprev_to_page_buildadd(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 */ + insert_itupprev_to_page_buildadd(wstate, state, compressState); } } diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 93fab26..8b77b69 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -1787,7 +1787,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 +2147,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 @@ -2168,6 +2180,26 @@ _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 +2237,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 +2248,9 @@ _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), BTreeTupleGetMinTID(firstright)) < 0); + Assert(ItemPointerCompare(pivotheaptid, BTreeTupleGetMinTID(lastleft)) >= 0); + Assert(ItemPointerCompare(pivotheaptid, BTreeTupleGetMinTID(firstright)) < 0); #else /* @@ -2231,7 +2263,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(BTreeTupleGetMinTID(firstright), pivotheaptid); /* * Pivot heap TID should never be fully equal to firstright. Note that @@ -2240,7 +2272,7 @@ _bt_truncate(Relation rel, IndexTuple lastleft, IndexTuple firstright, */ ItemPointerSetOffsetNumber(pivotheaptid, OffsetNumberPrev(ItemPointerGetOffsetNumber(pivotheaptid))); - Assert(ItemPointerCompare(pivotheaptid, &firstright->t_tid) < 0); + Assert(ItemPointerCompare(pivotheaptid, BTreeTupleGetMinTID(firstright)) < 0); #endif BTreeTupleSetNAtts(pivot, nkeyatts); @@ -2330,6 +2362,10 @@ _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. */ int _bt_keep_natts_fast(Relation rel, IndexTuple lastleft, IndexTuple firstright) @@ -2415,7 +2451,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 +2506,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 +2533,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 +2585,7 @@ _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 +2612,59 @@ _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; + 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; + + 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)); + + /* 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 */ + ItemPointerCopy(ipd, &itup->t_tid); + } + + return itup; +} diff --git a/src/backend/access/nbtree/nbtxlog.c b/src/backend/access/nbtree/nbtxlog.c index 6532a25..16224b4 100644 --- a/src/backend/access/nbtree/nbtxlog.c +++ b/src/backend/access/nbtree/nbtxlog.c @@ -384,8 +384,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 @@ -476,14 +476,36 @@ btree_xlog_vacuum(XLogReaderState *record) if (len > 0) { - OffsetNumber *unused; - OffsetNumber *unend; + if (xlrec->nremaining) + { + int i; + OffsetNumber *remainingoffset; + IndexTuple remaining; + Size itemsz; + + remainingoffset = (OffsetNumber *) + (ptr + xlrec->ndeleted * sizeof(OffsetNumber)); + remaining = (IndexTuple) ((char *) remainingoffset + + xlrec->nremaining * sizeof(OffsetNumber)); - unused = (OffsetNumber *) ptr; - unend = (OffsetNumber *) ((char *) ptr + len); + /* Handle posting tuples */ + for (i = 0; i < xlrec->nremaining; i++) + { + PageIndexTupleDelete(page, remainingoffset[i]); + + 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/include/access/itup.h b/src/include/access/itup.h index 744ffb6..85ee040 100644 --- a/src/include/access/itup.h +++ b/src/include/access/itup.h @@ -141,6 +141,11 @@ 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 a3583f2..57ee21e 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, + * BTREE_VERSION 5 introduced new 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,149 @@ 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, + * 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). They will need to be - * updated if non-pivot tuples ever get taught to use INDEX_ALT_TID_MASK - * for something else. + * 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))\ + ) -/* Get/set downlink block number */ +#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) \ + ( \ + 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 + * he will get what he expects + */ +#define BTreeTupleGetPostingOffset(itup) \ + ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid)) +#define BTreeTupleSetPostingOffset(itup, offset) \ + 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 several TIDs. + * Some functions that use TID as a tiebreaker, + * to ensure correct order of TID keys they can use two macros below: + */ +#define BTreeTupleGetMinTID(itup) \ + ( \ + ((itup)->t_info & INDEX_ALT_TID_MASK && \ + ((ItemPointerGetOffsetNumberNoCheck(&(itup)->t_tid) & BT_IS_POSTING))) ? \ + ( \ + (ItemPointer) BTreeTupleGetPosting(itup) \ + ) \ + : \ + (ItemPointer) &((itup)->t_tid) \ + ) +#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 */ #define BTreeInnerTupleGetDownLink(itup) \ ItemPointerGetBlockNumberNoCheck(&((itup)->t_tid)) #define BTreeInnerTupleSetDownLink(itup, blkno) \ @@ -326,15 +484,18 @@ 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 \ ) \ : \ IndexRelationGetNumberOfAttributes(rel) \ ) + #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 +503,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 tuple it returns the first tid from posting list. */ #define BTreeTupleGetHeapTID(itup) \ ( \ @@ -351,7 +514,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 +526,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) @@ -567,6 +734,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 @@ -579,7 +748,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; @@ -763,6 +932,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); @@ -813,7 +984,8 @@ 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); /* * prototypes for functions in nbtvalidate.c */ @@ -825,5 +997,6 @@ 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 add_item_to_posting(BTCompressState *compressState, + IndexTuple itup); #endif /* NBTREE_H */ diff --git a/src/include/access/nbtxlog.h b/src/include/access/nbtxlog.h index 9beccc8..c213bfa 100644 --- a/src/include/access/nbtxlog.h +++ b/src/include/access/nbtxlog.h @@ -172,11 +172,19 @@ typedef struct xl_btree_reuse_page typedef struct xl_btree_vacuum { BlockNumber lastBlockVacuumed; + /* + * This field helps us to find beginning of the remaining tuples + * from postings which follow array of offset numbers. + */ + uint32 nremaining; + uint32 ndeleted; - /* TARGET OFFSET NUMBERS FOLLOW */ + /* 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. --------------B094494E4371AEA342B2A256 Content-Type: image/png; name="btree_compression_test_result.png" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="btree_compression_test_result.png" iVBORw0KGgoAAAANSUhEUgAAAvEAAAFzCAYAAAC3qFavAABCWElEQVR42u29B5wUZZ7/v3e3 F18X9u727vbu9m7vyGGQnFEykgXJQUAlLCAgYZVldB3TLnvCygmSDAsGQAmSRaIIyiAq/FeS gIigIBlJkp+fn8d76l/TU91VM84w0z3v9+tVL7pCV9eneuh619Pf5+kfGAAAAAAASCp+wCkA AAAAAEDiAQAAAAAAiQcAAAAAACQeAAAAAACJBwAAAAAAJB4AAAAAAJB4AAAAAAAkHgAAAAAA kHgAAAAAAEDiAQAAAACQeAAAAAAAQOIBAAAAAACJBwAAAABA4gEAAAAAAIkHAAAAAAAkHgAA AAAAiQcAAAAAACQeAAAAAACQeAAAAAAAJB4AAAAAAJB4AAAAAABA4oskp0+fNr169TJr167N l/2//fbbplu3bub48eOcbAAAAIBUl/hnnnnG/OxnP7MCePXq1YTbdujQwfzgBz+w08cff5zy J/sf//EfbdZ/+Zd/Cd22bt263rmRsPs5d+6cqV69ul339NNP58uxTpw40e6/QoUK5uTJk/xP KeIk+nsEAACAFJD4f//3f/cu9tu2bSsQiVfr8WOPPWZuueUW8zd/8zdWnuvUqWOmTZtmLl++ nG37xo0be8fx8MMPZ1t/5MgRb3358uUTvvbLL7/sbfub3/wmXyS+S5cudrla4r8P33zzjXnj jTdM165dTc2aNbOt7927t32d5s2b58n7EvZ64vz58yY9Pd2ULFnS/Nmf/Zn5h3/4B9O6dWuT mZnJtnG2ReIBAACQ+O+N5Pmv/uqvrBgHCXN+S/xHH31kfvrTn3r7jZ1q1aplvvrqq7gSL2Ha vXt3oZX4lStX2mX/9E//ZL7++uscnx+9J0uXLjV33XWX+du//duEuc6cOWN+/OMf2/Wvvvpq rt6PnLyettX7E/S+/emf/qlZsWIF28Zsi8QDAAAg8TedvJZ4Sadf4NX6PnbsWPPII4+Y4sWL e8ubNm0aV+I1NWzYsNBKfJMmTeJ+YxCF3//+94FyGC/XQw895JXV5PfrjR8/3lt/6623mtmz Z9v37k/+5E/ssv/4j/8w165dY1vftkg8AAAAEp+vF/s1a9bY1sW/+Iu/MP/6r/9qfvWrX5n2 7dtnkfgXX3zRm+/Zs6f33BdeeMFb3qdPn7iv7YRTU6dOncyNGze8dWfPnjXlypXz1qt1OJ7E a3rppZdyLPGS8yBhXbVqVTaJnzVrlildurRt+VfJRGxte9B5/Pzzz80f/dEf2WWbN2/O9vqH Dh0y/fr1syVNarH9t3/7Nzuv4/dLtdYp84QJE0Jz6XXcNu+99563fN68eebv//7vbcmSf/9B Eh/19apUqeJ9G+LvUNu/f3/vea4jL9sGd2hW6ZPb5v333/eW79+/31uu/hSOJUuWmBYtWti/ Tf3fLFOmjBk1alQ2UQ/6e3Q3Ffo79nPHHXd42+7du9dbfuHCBZORkWG312vpW54777wzsOxu +fLl9mZa3zjpG5xKlSqZ//mf/7H7AAAAgJsk8evWrbMiFyu3P/zhD7NI/PXr103FihXt/B// 8R/bZaqjdq3rKtP54osv4r52iRIlvP3t3Lkz23q1aLr13bt3D5R4Jyb//M//bE6dOpUvEu9e I3bSjU2i8zhz5kw7L6mJbYndt2+f+clPfhK4X7XcOtFWKZG/DCcsl15H/Qq0jQTMcfvtt3vP nTFjRtxzEvX19N67v5G0tLQs6/zfbvzud79j2//bNojnnnvO2+bJJ5/0lqs/iFuub6eEvimK V3amG0t1oM4riddNtEQ86LUk9OvXr/ee/9vf/jbucekGJKxMDwAAAInPI4l3Yq6pY8eOZs6c Oeb+++/PcnF25TQSXresbdu2VjiCJDeWixcvetv93d/9XeA2aqkOkki/xA8fPtx7rJbPnEi8 RnGZMmVKlk6yakm9cuVKFonX1LJlS/Paa69ZMXbSppuaw4cPxz2PgwcP9ur6Y3FlNpoGDBhg 5s6da0cIcsv03MA/gAi5VJakbfQaDtXI//Vf/7UVuEQ3VlFfT6VQbl39+vWzrFu2bJm3Tt+2 sO132wahvzcn1/6ysM6dO2cRa4nwn//5n9t5fTOmb1k+/fRT+02X204jTeWVxLu/XU133323 WbBggW1Z1425lpUtW9Zup5t2t0zfCuiYjh07Ztq1a+c9/5VXXuGTGwAAkPj8lnhdxN28Lsr+ EpdmzZoF1sTr63233F3QJRoasSMeuti756hsJohLly5522i0jyCJ37JliyfEKl2R3OR1Tbxu MpzYixEjRnjPmT59elxpcnLUqlWruDcnep5DrehqhXfnPrcS36ZNm0BZy9UfXJzXk3zGk9c3 33zTW/fggw+y7f9tGw/Ju7aRpOvmVv/nVJaiZSp/SoRKcNxr3HvvvXki8ToG3fC5fip+hg0b 5m37ySef2G+/3Lz+X7rPC+1Hw55q8pcJAQAAIPH5JPGLFy/25ocOHZpl23gdW3fs2JGt5OT5 559P+LoqJ3Hbula9WFRPG0Xi9+zZ47VSSnriteDnVuJjO7YuWrTIe46EPp403XbbbXZeI734 UV2z2/YXv/hFlnVqJZcAffbZZ7mWeNc6qxp4JL7wS/ykSZO87d566y2zdetWb/7RRx/1tlPp jvqh6O9K761K2Pz/53r06JEnEv/BBx/ELY/xTxp5SbhvfjSpQ/qQIUPM66+/bktyAAAA4CZJ vL8OXcNPRpF44Tr3uWH1woZT9Au6asaDUEtfUGt9rMQLlbm4Zerol58Sv2HDhmwlPEHS5JbF Srw6yQbVQX8fqfajFllto46I+SXx/jISjcjiR50c/SVKbJt4dKIvv/zS6wCtm7qnnnrKe972 7du97fwdZdUZWvLt7+uQVxLvv/lQ/bv+HwRNuuFwx+8/Djf96Ec/8r6pAgAAQOLzWeL9dbyu lTlM4nUxj72ARxlSsVixYgl/aMo/3KF+MCmRxKv0plSpUtk64OaHxPslJ1FLvPoIBJXT+M+x bjjyWuKdlOVnOY3KJlzfgNhyKI0U5J6nEW7Y9rttE+FasytXruyNWON///xlbv7Oov5W+7yS eP9Nqn6wKiq64VCfmAYNGng3JZo2btzIJzcAACDx+S3xBw4c8ObVwdWPv7XNSbzquDUqhxvF xY24otp4lbUkwj/EpIav9Nffq6XeP8SkOtYlknixevXqyOOpO9TpLl6ruJN4tSj6a+LVYdc9 Z+rUqXGlaeDAgYEdW1Uy4x8b34/q+1WSoHOdW4mvXbt24Pj6eSnxQjLpbpqOHj3qLVdHXfe8 t99+m21928bDjTUv+f3Lv/xL+3jMmDHeen+Z2y9/+Utv+aZNmyJLvErS3EhOfvx9XSTx+nbB 3QirJd4/7KTQza4bSlOCrjp5Tf4RptzITJo0Zj4AAAASn88SL6pWrZpFDObPn29bnP2ta07i /UPh9e3bN0vLdq9evRK+tl7P/2NPOpZx48ZZmVbHTrdcNcB+wY8n8ULHmxOJd7+oqkklQZJ6 1dj7Jd61SOo8aKhAJ1m6aXE3KkHnUUM5xhtiMnZ0Gu3bL316nBuJV9206qVj5UnjlGskHslg Xkn8//7v/3rrdeOgMqHHH3/cE8D//M//9HKzbeIfe1IfiNgb0A8//NBb7+/AqqFZ33nnHftL sPpRL7dcoxsl+n/t/1VZSffChQvt6E7+/9dO2Hv37u0t0//RZ5991o6gpN9zcCPp6P9kZmam t52+QTh48KC9AdcNiFuumn8AAAAk/iZIvAQhaJx4f+dVSbzGpXZjravlXbWxurC78aUlB34R CULrVd8br/OcxDp2SMREEq+WULWcR5V4ZXbS6yaV8fglPt448f7OimE/9hR7nJIltYjGGyfe DV2ZU4nX6wT92JOTsthft/0+Eq9vJ/ydGv2T/n5UdsS2WbdNhP/m+b/+67+yrNP/K9dROt7/ SbWoJ/p71DCjQcfoRqLxS7yeo9KeeP8v/d8G+Gv1YyeVuIX1jwEAAEDi80jihb7+V6uiRn3R cHcaN/qJJ57IIvHp6enevP+rf3+NvOpjw9C40uqYqlZFCYWkukaNGnbcaw13F0siiRcqcYkq 8S6rBEo3Imo1Vc26X+I15rXKHVTDLynTv/qBG/+3A/HOo2txDyopUKulvr1wv9iqFs9BgwbZ 85EbqRZ6naAfHnISn9MSm7DX0zCiKovSjw3pF0t1A6UhR/03EGwbjV//+tdx+6MIjfai5T/7 2c/s/8uaNWvav103HKVe8+rVqwn/HtXRVO+lymT++7//29aw+4dM9ZfO6P+ejkn/L7W9hlrV TaBa8GNR+YxeUz80pv/D+vvTyDqxvyQLAACAxENS4Mp11Oqe30Puaf/umxGNMuRHP1YVNFIO AAAAACDxEEDXrl2tQGv89vxErfquNtmPWmdd6Y4rFQIAAAAAJB4SoBbyatWqWYlWJ8j8QB0P tX+VPpw8eTLLOv3wjuugqE6HAAAAAIDEQwT08/QqZVmzZk2+7F+10Wrxd0P/+Xn33XftTcSq Vat4IwAAAACQeAAAAAAAQOIBAAAAAJB4AAAAAABA4gEAAAAAAIkHAAAAAEDiAQAAAAAAiQcA AAAAACQeAAAAAACJBwAAAAAAJB4AAAAAAJB4AAAAAAAkHgAAAAAAkHgAAAAAAEDiAQAAAACQ eAAAAAAAQOIBAAAAigBXrxozbpwxGRnh05w5RfMcHThwwBQrVsw0adIk7jYNGjSw2xw5coQ/ KiQ+mA8++MB07tzZlCtXzlSvXt0MGjTIHDx40Ft/4sQJM3jwYJOWlmangQMHmmPHjkVeDwAA AEWH0aO/FasfRJ9WrEi8P0msZNZNpUqVMvXq1TNjxoyxDpIISbKec+jQoZt6DtatW2c6depk vahatWpm5MiRWWQ8LyR+8eLFpk2bNtbf6tata0aNGpXvwl9Q5xOJD0Cyrje/ZMmSVsS7detm 35zGjRubGzdu2G369u1rl3Xt2tVb36tXL28fYesBAACg6NCnT84kfsaMaBIveR8yZIhtLJS0 apm8o7BJ5xtvvGGKFy9u3apDhw6ejNesWdMcP348TyR+5syZdp0cTuegWbNmdr5+/frm7Nmz SHxRYNOmTfY/xCuvvOIta9iwoX2DJPhffPGFfaw/Dif1rVq1ssv2798fuh4AAACQ+LyQ+IoV K3rLTp48aZdJlK+qficAbe9vwZ8zZ47ZsmWLfdyvXz/To0cPU7t2bW9/Q4cOtc+RbKuV/9y5 c1leL9F6x5UrV0yVKlXsa6xatcouu379uhk2bJhdpufFk/jMzEzTtGlTU6FCBfPAAw+YOnXq BEr8xYsXbQu/bhS2bt3qLdfxafvnnnsu1znnz59vWrRoYcqUKWNff9y4cfb4453PnJwbJD4f kYTv2LHD/mFUrVrV/pFs3LjRvlH643Po6xotW716deh6AAAAQOLzUuKvXbtmVq5caZep4TEe aq1WKYu2k4zu3r3bk1s3SVS1v7Zt29r5u+++2/Ts2dM+ViOne71E6/289957XuOmn507d9rl KlsOkvgLFy548t+7d2/TsmVL7xhjJX79+vV2uUpp/Gzfvt2MHz/eLFu2LFc5VV6teX3Lof24 bWf83xsUdD5zcm6Q+HzC/WfQpDvAbdu22eVLly61yyTmjvT0dLtMd2th6wEAAACJzwuJj50q VapkGx8TEVv+4eRWLdOu/59rkOzfv7/3vObNm9tlkuuw9X7mzZtnl6vU2I+2c8d96dKlbBK/ cOFCO3/vvffa+cuXL5saNWoESvzrr7+e7XhiyU3OWN59912vNT/e+czpPpH4fGDPnj3mySef NPfcc4898frqRV+f5JfEHz582N7xMTExMTGl7rT7+efN2apVs1nbmVtvNTtee41zVEgmXZOT QeLLli1rpk+fbidXnqKac/mKSlH8gi8XSSTxajF2aH9BNwmadu3aFbrez9y5c3Ml8c8884yd nzJliveceDXxKmOJKvE5yeluJlq3bm2rMtw6f7+D2POZk3ODxN8EXOdU/YfYsGFDtq9FXLnM 2rVrQ9cDAEAR5lsRiGtu34oC0BKf25p4oUE4tFx14eqHJ3F306JFiyJL/OTJk+2yPt8e+JIl S7JMZ86cCV0f1Hqt2nY/ElotVzmKiJX4SZMm2XlJcZjEy6+0vF27dlmWq7xFz9fIOLnJuXnz Zltnr5Z0PdY5DJP4nJwbJD6P0VcyqmV66aWXAiXedVzVH2Oijq3x1gMAQBEmzN4Aic+lxKsD qUpFtFz15vFwo7Y4JwmSW/Xhc/X1aiUX+/bts7XnUdb7URlM5cqVs3RslR9piEkte/DBBwMl XsNFal4j77h88cppNPqMRqUpUaJEltZuNahq+6lTp+Yqp7uRePrpp+28bgZiJT72fObk3CDx eYxqyTRkU+nSpc19991nunfv7r0Z6tgqVAvlhpB06/1DSIatBwAAJB6JR+LzYojJ4cOHm/vv v9+TSTUixhud5rtj6WO30+/hSKqD5FadM1VC4jqkjhgxwtbbu9b0sPWxLFiwwBtiUmPFazs9 V4OGOCGPlXg5l+vYqrp493rxhph0LeAqe1FHWFeHrvHzT58+naucK1as8OroMzIy7EgzrmQp 3vnM6blB4vMYlcR07NjR/iHork93col+7GnAgAHm6NGjkdcDAAASj8Qj8XnZsbVWrVrZfCUI DdTRqFEjU758eTNr1qxAuRUaJlGt5WpF17aS1b1790ZeH8uaNWu8H3uSnMcea6IhJvUc/fBm +/btE/7Y0+zZs604qyFWI8ro+Fz/htzm1KgzutnQ+Z04caK9GdG8G2Yy9nzm5twg8QAAAEg8 FELGjo0u8D/8oRoTOWeAxAMAACDxUOBMnWpMRkb4tGIF5wqQeAAAACQeAJB4AAAAQOIBAIkH AABA4pF4AEDiAQAAkHgAQOIBAAAAiQcAJB4AAACJR+IBAIkHAABA4gEAiQcAAAAkHgCQeAAA ACQeiQcAJB4AAACJBwBA4gEAAJB4AEDiAQAAAIkHACQeAAAAiQcAQOIBAACQeABA4gEAAACJ h6tXjRk3zpiMjPBpzpwieYoOHDhgihUrZpo0aRJ3mwYNGthtjhw5wt8UEg8AAIDEQz4zenT4 e++fVqxIuDtJrGTWTaVKlTL16tUzY8aMMSdOnEj4XEmynnPo0KGbegrWrVtnOnXqZNLS0ky1 atXMyJEjs8j495X4kiVL2nVff/11gbzFBXVekXgAAAAkHvKLPn1yJvEzZkSSeMn7kCFDzMCB A03dunXtsm7duhU62XzjjTdM8eLFrWh36NDBk/GaNWua48ePI/FIPAAAABIPRUfiK1as6C07 efKkXSaZvarynQC0vb8Ff86cOWbLli32cb9+/UyPHj1M7dq1vf0NHTrUPkeyrVb+c+fOZXm9 ROsdV65cMVWqVLGvsWrVKrvs+vXrZtiwYXaZnhdP4jMzM03Tpk1NhQoVzAMPPGDq1KkTSeLX r19vHw8YMMDcd9999hgbNWpkNm3a5G2vY2nZsqUpV66cqV+/vpkyZUqkbEHnK+i8IvEAAABI PCDxCSX+2rVrZuXKlXZZw4YN4z5v5syZtpRF240bN87s3r3bk1I3SZS1v7Zt29r5u+++2/Ts 2dM+Vqu/e71E6/289957dl2zZs2yLN+5c6ddXr169UCJv3Dhgif/vXv3tsLtjjGqxGvq3r27 6dKlS5Zz8+mnn9rtb731VjN58mTTunVru3727Nmh2YLOV9B5ReIBAACQeEDiAyU+dqpUqZLZ sWNHwufGln04KVWL8sGDB+2yjRs32mX9+/f3nte8eXO7THIdtt7PvHnz7PK+fftmWa7t3HFf unQpm8QvXLjQzt977712/vLly6ZGjRo5knhXWiQxr1y5sl2mFvWlS5faxyNGjLDr9+zZYyZN mmTWrFkTmi3ofAWdVyQeAAAAiQckPlDiy5Yta6ZPn24nV56imnOVq6gUxS/46enpCSVeLc4O 7S/oJkHTrl27Qtf7mTt3bq4k/plnnrHz/jKXqDXxTuL9Iq5Wd/dcdf6tVauWnW/cuLF5/PHH zfbt2yNlDzpfSDwAAAASD0h8rmrihYRUy7du3Wr2799vxd1NixYtiizxKjHRsj7fHveSJUuy TGfOnAld7+fdd9+126q23Y+EWMtVhiJiJV4t45qXVOe1xItTp06ZCRMmmDZt2tjlJUqUsC3x YdmQeAAAACQeiUfi80zi1YFUJR5arnrzeKg2XdtI8uNJ/OrVq70acrWSi3379lk5jrLej8pg XCmL69h648YNO8Sklj344IOBEr948WI7r5F3XL6cltPEk3iV0+jGxpUevfbaa3bd8OHDQ7PF k/jY84rEAwAAIPGAxAdKvIaYlHjef//9nkSqxTve6DTfHUofu13nzp2tVAdJqWrIXWdP7Ve1 46q3d63pYetjWbBggTfEpMaK13Z6btWqVT0hj5X4ixcveh1bVRfvXi8vJF5j1uuxat1ffPFF 06tXLzv/wgsvhGaLJ/Gx5xWJBwAAQOIBiQ+UeP+kGm+NoOLvbBnEtm3b7HCL5cuXN7NmzYor pRpmUa3lakXXtpLUvXv3Rl4fi0pV3I89Sc5jjzXREJN6zqBBg0z79u3zrJxm/vz5VtJLly5t 16m0Rn0JwrLFO1+x5xWJBwCAosGGDSp4zS4zrVsb8/HHSDwkN2PHRhf4H/7wu/8PAEg8AAAU etLS4kuNRB6Jh2Rn6lRjMjLCpxUrOFeAxAMAAHJLTgBA4gEAAJBbcgIAEg8AAIDEI/EAgMQD AAByS04AQOIBAACQW3ICABIPAACAxCPxAIDEAwCkIIyfjsQDACDxAABJBuOnI/EAAEg8AADS R05yAgASDwAASB85yQkASDwAACC35AQAQOIBAJA+cpITAJB4AABA+shJTgBA4gEAALklJwAA Eg8AgPSRk5xQ4Fy/asz/N86YDzLCp31zOF+AxAMAIH3kJCcUOJtHGzPtB9GnQysS7u7IkSOm WLFi3lSqVClTr149M2bMGHPixImEz23SpIl9zqFDh25KdP+xbt682Vv+9ddf22UlS5bM92NY vHixadOmjSlXrpypW7euGTVqlD2u/ORmn2ckHgAA6SMnOSGvWdcnZxL/yYxIYix5HzJkiBk4 cKCVUy3r1q1boZX45s2bm2vXrt1UiZ85c6Z9HQm8zk2zZs3sfP369c3Zs2eReAAAQPrISU64 uRJfsWJFb9nJkyc9Kb569Wrg87S9vwV/zpw5ZsuWLfZxv379TI8ePUzt2rW9/Q0dOtQ+p2bN mraV/9y5c1leL9H6IInX9Nxzz8WV+ET71PFp+507d9r5Pn36mLS0NC9rpUqV7HT9+nVvfxcv XrTbFC9e3GzdutVbrtdwx5Lb/PPnzzctWrQwZcqUMXXq1DHjxo3zXjvoPOfknCHxAABIHznJ CUVA4tW6vXLlSrusYcOGcZ+nVulq1arZ7SSdu3fv9iTWTRJS7a9t27Z2/u677zY9e/a0j9Xq 714v0fqgYy1btqypXLmyleqvvvoqm8SH7XPatGl2ft68eebKlSt2P5p///33zcGDB+3je+65 J8trr1+/3i5XKY2f7du3m/Hjx5tly5blKv8HH3xg5/Xth/bjtp0xY0bc85yTc4bEAwAgfeQk J6SwxMdOaonesWNHwufGlnk4iVULtGRYbNy40S7r37+/9zyVwmjZhQsXQtfHu+F45ZVX7OP7 7rsvm8SH7fOjjz6yjx999FGTmZnpZZ4wYYJZsWKFfTx58uQsr/36669n22csuckfy7vvvuu1 5sc7zzndJxIPZsMGYxo0yH6daN3amI8/Jic5yVnoc6aA9JGzCOaMstGRb7dZ0iC7wL757TYn v9tm0+HNpvXCO82PJv8ky9Rl2V1m58ldRV7i1bo9ffp0Ow0bNswu69Chgy3r8IuupvT09IQS r5Zhh/YXdJOgadeuXaHr40m8jqtdu3Z2Xq3gfokP26fKZlTX3qVLF9v6rZZ41bh36tTJzrtW eT8qY4kq8TnJLxYuXPjtn3Nr7xuB2P4Isec5J+cMiQfLt39bca8V+iwlJznJWchzpoD0kbMI 5oyy0dy0+BL75nfb1J7TIJvA+0W+qEu8vyZeNG7c2C5X/ff+/futuLtp0aJFkSVeLdpaprrz JUuWZJnOnDkTuj7RsX787U1ciRIlbMu3X+Kj7FOSfMstt5j27dvbVm/VtKtzr5aXLl3aXLp0 Kctrr1271u5TNw5+VN4iqV63bl2u8muUHdXZqyVdj3VuwyQ+J+cMiYdUuV6Qk5xFO2cKnAxy kjNwozCR/ZZ4Au8mJP7/l3jViTsxdp0/g3Cjs0jy40n86tWrvfp6J8b79u2zNeZR1ocd68MP P+y1QjuJj7JP1+Ku6eWXXzZ79uzx5jt27JjttTX6jFrvddPgb+1WHbqeM3Xq1FzlnzRpkl3/ 9NNPf/f2fnszECvxsec5J+cMiQdkiJzkRPrISU4kPoUlXq3Qw4cPN/fff78njU2bNo07Oo1Q S7C269y5s1m1alWgxKoTpkpFtFz7HTFihK23176jrA+TeNXDV69ePVvH1rB9uo6qmj7//HO7 TB1RNT927NjAvK4FXGUvvXv39urQNa7+6dOnc5Xf1eDrpikjI8OONONKmeKd55ycMyT+e6A7 I/Vw1htepUoVW0vlOjsI/ZDC4MGD7XpNGp/12LFjkdcjQ+QkJzmRPnIi8Uh8XnZsrVWrlm1h 9vtKENu2bTONGjUy5cuXN7NmzQqUWKHhEEeOHGlHlNG2ktK9e/dGXp9I4sWCBQsCh5hMtM/z 58/b7f0j8IwePdruRy3d8Zg9e7YVZ5XcaEQZvcbhw4ftutzm16gzVatWted94sSJtrxG826Y ydjznJNzhsTnEt2VubtD1Vvp6xk9vv32271t+vbta5d17drVfnWix7169Yq8HhkiJznJifSR E4kvQhK/dWx0gX/uh991+gVA4nPGq6++aqVbX3MIff3hasx0N/nFF194X4XcuHHDbtOqVSuv 7ilsPTJETnKSE+kjJzmLmMSLnVON+SAjfDq0AgsFJD43fPnll/arFfc1iyS+Ro0a9usb1XC5 cT41lJNj1KhR3lc5YeuRIXKSM49ypsA4lEgfOZH4IiTxAEj8zUV1ThJwdRwRS5cutfMSc4eG btIy/QRv2HpkiJzkzKOcKTAOJdJHTiQeiQdA4vMBDeSvjgr169e3tfL5KfFq+dfP+Ob1FPY5 qm0ufpsx3gZnbr01X46LnOT8vjnDNiInOclZuHOGSby2CZP4/Mrovo0HQOKTkJUrV9oSGg0b 9Nlnn3nLN2zYYIVcPcAdrlxGPyoQtp6WIXKSk5zkJCc5aYkHQOLzgXfeeceUKVPGDhWkHxLw 4zqualzPRB1b463nokJOcpKTnOQkJxIPgMTnMZ988okdu1PS3aVLlyw/WbxmzRq7jYaedENI du/ePdsQkmHruaiQk5zkJCc5kXgkHgCJz0OWL1+e7QcU3DRhwgS7TeyPOQ0YMMAcPXrU20fY ei4q5CQnOclJTiQeiQdA4oGLCjnJSU5ykhOJBwAkHonn4klOcpKTnORE4gGQeOCiQk5ykpOc 5CQnEg+AxAMXFXKSk5zkJCcSDwBIPBLPxZOc5CQnOcmJxAMg8cBFhZzkJCc5yUlOJB4AiQcu KuQkJznJSU4knos8ABKPxHNRISc5yUlOciLx+cPV61fNxG1TzNgt40Kn+XsXIi+AxAMXFXKS k5zkJCcSX9BkbHoyNIt/Wn1wXcL9HTlyJMuPUZYqVcrUq1fPjBkzxv7gZCKaNGlin3Po0KGb kt1/rJs3b/aWf/3113ZZyZIl8/X1tX+9jl6vILjZ5xuJR+K5eJKTnOQkJzmR+Dxi0NphOZL4 WbtfiyTGkvchQ4aYgQMHmrp169pl3bp1K7QS37x5c3Pt2jUkHokHLirkJCc5yUlOJL7oSnzF ihW9ZSdPnvSk+OrVq4HP0/b+Fvw5c+aYLVu22Mf9+vUzPXr0MLVr1/b2N3ToUPucmjVr2lb+ c+fOZXm9ROuDJF7Tc889F1fiE+1Tx6ftd+7caef79Olj0tLSvKyVKlWy0/Xr1+NK/Pr16+3j AQMGmPvuu8++TqNGjcymTZu87VetWmVatmxpypUrZ+rXr2+mTJkS6fiCzmPQ+UbigYsKOclJ TnKSE4lH4u28WrdXrlxplzVs2DDu82bOnGmqVatmtxs3bpzZvXu3J59uqlOnjt1f27Zt7fzd d99tevbsaR+r1d+9XqL1QcdatmxZU7lyZSveX331VTaJD9vntGnT7Py8efPMlStX7H40//77 75uDBw/ax/fcc0+21w+SeE3du3c3Xbp0yXLOPv30U7v9rbfeaiZPnmxat25t18+ePTv0+ILO Y9D5RuKBiwo5yUlOcpITiS/iEh87qSV6x44dCZ8bW97h5FMtx5JhsXHjRrusf//+3vNUCqNl Fy5cCF0f74bjlVdesY/VCh4r8WH7/Oijj+zjRx991GRmZnqZJ0yYYFasWGEfS7yjSLwrOZKY 68ZCy9SivnTpUvt4xIgRdv2ePXvMpEmTzJo1a0KPL+g8Bp1vJB64qJCTnOQkJzmR+CIu8Wrd nj59up2GDRtml3Xo0MGWlPhFV1N6enpCiVfLskP7C7pJ0LRr167Q9fEkXsfVrl07O79s2bIs Eh+2T5XNqMRFrefjx4+3LfGS8U6dOtl51yofReL9Iq5Wdy3TcapTcK1atex848aNzeOPP262 b98e6fiCziMSD1xUyElOcpKTnEg8Eh8oxn4knlq+detWs3//fivublq0aFFkiVeLtpap7nzJ kiVZpjNnzoSuT3SsH3/8sSlRooRtsfZLfJR9StpvueUW0759e1t7rvp6de7V8tKlS5tLly59 L4kXp06dsq37bdq0sct1rGqJDzs+JB64qJCTnOQkJzmReCQ+xxKvOnEnxq7zZxDNmjWz20jy 40n86tWrvVpxJ8b79u2zEhxlfdixPvzww14rtpP4KPt0Le6aXn75ZVvu4uY7duwYmDcnEq9y Gt3wuJKk1157za4bPnx46PHFk/jY843EAxcVcpKTnOQkJxJfxCVerdASzPvvv9+TxaZNm8Yd nUaoJVnbde7c2Y7EEiSfqhV3nTq1X9WIq95e+46yPkziJdTVq1fP1rE1bJ/+jqmff/65XaYO pJofO3bs95b4devWeUNhvvjii6ZXr152/oUXXgg9vngSH3u+kXjgokJOcpKTnORE4ou4xPsn 1XJrpBR/p8ogtm3bZodVLF++vJk1a1Zc+dRwiiNHjrQdP7WtZHTv3r2R1yeSeLFgwYLAISYT 7fP8+fN2e/8IPKNHj7b7UUv595V4MX/+fCvpKs/ROpXWuGErEx1fvPMYe76ReOCiQk5ykpOc 5ETik4SnP5oYWeB/PPWnZtPhzQgMIPFIPBcVcpKTnOQkJxJf0Ly44yUzdsu40Gn1wXXICxRe iVetlobjOXv2rLfsww8/tIPiv/TSS3YsUOCiQk5ykpOc5ETiU0XiAZJe4vUrXfoZW9UNVahQ wdYQqUNGbG2XfrI29gcDgIsKOclJTnKSE4lH4gEKQOJ/+ctfZpF193O0mqpWrWrF3s0/+eST vBNcVMhJTnKSk5xIPBIPUNAS73oB60cHNHyPHquXrxuT88aNG97P8mpb4KJCTnKSk5zkROKR eIAClniNaarWdnHx4kUr6z//+c+zbVelSpUsww4BFxVykpOc5CQnEo/EAxSQxEvaa9SokWVe 45rG4n51DLiokJOc5CQnOZF4JB6gEEi8Bvx/44037KT5Dh06ePNuUokNEs9FhZzkJCc5yYnE I/EAhUTiczIBFxVykpOc5CQnEo/EAxSwxKvOPScTcFEhJznJSU5yIvFIPEABSzxwUSEnOclJ TnKSE4kHQOKBiwo5yUlOcpITiQcAQzkNEs/Fk5zkJCc5yYnEAyDxDjq2clEhJznJSU5ykhOJ B0hiia9fv7557LHHzLp168yGDRvMqlWrzOLFi7MMNQlcVMhJTnKSk5xIPBIPUMAS/+6775r0 9HRTrVo1T+ZLly5t+vfvb5YsWWIuXLjA2eeiQk5ykpOc5ETikXiAwiTxjmvXrlmhHzNmTBah L1++vP0F15UrV5rLly/zTnBRISc5yUlOciLxSDxAYZH4WKHfuHFjNqHXL7sCFxVykpOc5CQn Eo/EAxRSiX/vvfeyldmkpaXxTnBRISc5yUlOciLxSDxAYZH469evm8zMTPPwww+b6tWre+Je rlw5M2jQILN8+XJz6dIl3gkuKuQkJznJSU4kHokHKGiJ37x5s3nkkUdMzZo1s3Rs7du3r1m4 cCEdW7mokJOc5CQnOZF4JB6gsEl87BCTjz76qB1iUjXxDDHJRYWc5CQnOcmJxCPxAIVc4vmx Jy4q5CQnOclJTiQeiQdIAokvWbJkjibgokJOcpKTnORE4pF4gAKWeOCiQk5ykpOc5CQnEg+A xAMXFXKSk5zkJCcSDwBIPBLPxZOc5CQnOcmJxAMg8cBFhZzkJCc5yUlOJB4AiYfCdlHZdHiz ab3wzmwfsl2W3WV2ntzFxZOc5CQnOcmJxAMg8VDYLiq15zSI+0ErkefiSU5ykpOc5ETiAVJc 4qtUqWKKFy9ufxBq/Pjx5vz587wrhfyiUpAftlw8yUlOcpITiQeAQiDxzZo1MzVq1DClSpWy P/rUoUMH3hUknosnOclJTnIi8Ug8QGGWeMe1a9fM6tWrzYIFC3hXkHgunuQkJznJicQj8QCF ReJv3Lhhjh07ZrZt22YOHTrkLSsoTpw4YZYvX24yMjJMq1atzPTp07OtHzx4sElLS7PTwIED 7fFHXY/Ec/EkJznJSU4kHokHSGqJf+2110ydOnVsyYymX//612bfvn1Wng8cOFAg4Rs0aOAd j6YpU6ZkWd+3b1+7vGvXrqZbt272ca9evSKvR+K5eJKTnOQkZ5EfDQyJB0heiZ85c6YnyurE 6iT+rbfeso+HDRtWIOF1XJmZmeapp57KJvFffPGFXaaaffdtgW44tGz//v2h65F4JIGc5CQn ORkNDIkHSGqJ18gzJUqUMIsXLzaXL1/2JF5UrlzZVK1atUBPwoQJE7JJ/MaNG7PdYIwaNcou U+1+2HokHkkgJznJSU4+b5F4gKSW+NKlS5t69ep5836Jr127tilTpkyhk/ilS5faZRJzR3p6 ul02f/780PVcVJAEcpKTnOTk8xaJB0hqiW/cuLEto5k9e7YdhcZJ/Lx58+zjli1bFhmJP3z4 sPnggw/yfAr7HNU2YRtFfa2wD9v8yFcQOQtyIic5yUnOVPm8DZP4gsypazIAEp+AGTNmeDXx 5cqVs/+q9d0tU6fXwibxGzZssMuGDBniLXPlMmvXrg1dT8sQLX3kJCc5ycnnLS3xAEkt8UK/ xlqyZMkso8Fofty4cQV+EoIk3nVcbdq0acKOrfHWc1FBEshJTnKSk89bJB4g6SVenDx50ixb tsyOCqMfdSosX2MFSbzo16+fN4Rk9+7dsw0hGbaeiwqSQE5ykpOcSDwSD5C0Ei851nCSQUyc ONHWkhdGiY/9MacBAwaYo0ePRl7PRQVJICc5yUlOJB6JB0haiXflM4MGDTKnTp3Ksu7222+3 64CLCpJATnKSk5xIPBIPUAglXlONGjWyjKOOxHNRKaw5U+KXEvm7JSc5+bxF4gGQ+O8j8dWr VzcNGzb0ZP7BBx8058+fR+K5qBTanCnxS4lF5e/2yAZjljTILgdvtjbm5MfILTmT9u8WiUfi AQpc4iXrFy5cMA899JAn8rfddpv9tVYknosKOQsuZ0p84zA3Lb4gKCtyS84k/btF4pF4gEIh 8Y7169fbX2r1l9kAFxVyFkzOlPjGIYIkUB6FxCO35ARA4r+nxIszZ86YoUOHIvF82JKTnDcl J+VRSDz/P8kJgMTnkDVr1pjNmzcHrnv77bftuPHAhy05yUlO5JbPW/5/IvEABSzx69atM/v2 7bOPMzMzQyfgw5ac5CQnchuVlCiP4v8nEg9Q2CR+06ZNtkSmZs2adt5f+x5vAj5syUlOciLx USkqfTn4/4nEA9xUid+9e7cpXbq0adOmDRKPxJOTnORktCGGuuX/JxIPkAwSL06fPm2uXLli H1+7di10Aj5syUlOcjLaEBLP/08kHqCAJd5x6tQp8/nnn2dZ9s0335g//OEPZu/evbwDfNiS k5zkJCcSz98tEg9QWCT+xo0bZty4cbasZvTo0d7ytWvXej/wpKlPnz7m0qVLvBN82JKTnOQk JxLP3y0SD1DQEv/66697ou4k/sCBA6Zs2bLZ6uGnT5/OO8GHLTnJSU5yIvH83SLxAAUt8Xfc cYcV9PHjx9uSGvHAAw/YZVr36aefmrlz59r5Fi1a8E7wYUtOcpKTnN9tE6EDL+8nOQGQ+Hyi fPnypmLFirasRly4cMGkpaVZaff/8FONGjXscuDDlpzkJCc5LRE68PJ+khMAic8nJOa33HKL uX79up135TWNGjXytpHga5tKlSrxTvBhS05ykpOc5CQnEg9Q0BLfsWNHK+2PPfaYWbFihW1x 1/y0adO8bWbOnGmXde/enXeCD1tykpOc5CQnOZF4gIKW+IULF2brwHrbbbeZ8+fP2/Xt2rXz li9dupR3gg9bcpKTnOQkJzmReICClngxadIkWxsvUW/durXZt2+ft+7222+3yzMyMngX+LAl JznJSU5ykhOJBygsEi/0a6xnzpzJtnz58uVm165dvAN82JKTnOQkJznJicQDFDaJBySenOQk JznJSU4kHgCJBy4q5CQnOclJTnICIPGAxHNRISc5yUlOciLxAEg8IPHkJCc5yUlOciLxAEg8 8GFLTnKSk5zkJCcAIPFIPBcVcpKTnOQkJxIPgMQDEs9FhZzkJCc5yYnEAyDxwIctOclJTnKS k5wAgMQj8VxUyElOcpKTnOQEQOIBieeiQk5ykpOc5ETiAZB44MOWnOQkJznJSU4kHgCJR+K5 qJCTnOQkJznJCYDEAxLPRYWc5CQnOcmJxAMg8cCHLTnJSU5ykpOcSDwAEo/Ec1EhJznJSU5y khMAiQcknosKOclJTnKSE4kHQOKBD1tykpOc5CQnOZF4ACQeieeiQk5ykpOc5CQnABIPSDwX FXKSk5zkJCcSD4DEAx+25CQnOclJTnIi8QBIPBLPRYWc5CQnOclJTgAkHpB4LirkJCc5yUlO JB4AiQc+bMlJTnKSk5zkROIBkHjeSC4q5CQnOclJTnICIPGAxHNRISc5yUlOciLxAEg88GFL TnKSk5zkJCcSD4DEAxcVcpKTnOQkJzkBkHhA4rmokJOc5CQnOZF4ACQekHhykpOc5CQnOZF4 ACQeuKiQk5zkJCc5yQmAxAMSz0WFnOQkJznJicQDIPGAxJOTnOQkJznJicQDIPGFjRMnTpjB gwebtLQ0Ow0cONAcO3YMiScnOclJTnKSE4kHQOILK3379jXFihUzXbt2Nd26dbOPe/XqhcST k5zkJCc5yYnEAyDxhZEvvvjCSnuzZs3MjRs37LJWrVrZZfv370fiyUlOcpKTnORE4gGQ+MLG xo0brbAPGzbMWzZq1Ci7bPXq1Ug8OclJTnKSk5xIPAASX9hYunSpFXaJuyM9Pd0umz9/PhJP TnKSk5zkJCcSD4DEp4rET5s2zVStWpWJiYmJiYmpgCddkwGQ+CLGhg0brLAPGTLEW+bKadau XcsJAgAAAAAkvrDhOrY2bdq0UHRsBQAAAAAkHiLQr18/b4jJ7t27F+gQkwAAAACAxEMEYn/s acCAAebo0aOcGAAAAABA4gEAAAAAAIkHAAAAAEDiAQAAAAAAiQcAAAAAACQeAAAAAACJBwAA AAAAJB4KimeeecZs2rQppTNev37dTJkyxdSvX980aNDAjB8/3ly8eJGcZCUnOclJTgAkHpKP vXv3mlKlSpny5cuntMhnZGTYH+WqVq2aKV26tH2sX9o9duwYOclKTnKSk5wASDwkF/rF2ZIl S9oP2FQV+YMHD5rixYubHj16mKtXr5ovv/zStG7d2mZu1qyZOX78ODnJSk5ykpOcAEg8JAdv vvmm/VCdMWOGeeyxx1JW5DMzM222kSNHesvOnj1r2rdvb5fr4nLp0iVykpWc5CQnOQGQeCj8 nD592gwbNsxcu3bNzqeqyJ8/f95UqFDBfuPwzjvvZLmouNahiRMnkpOs5CQnOckJgMRDcpKq Ij9z5szAXJ999pkpUaKEvbCQk6zkJCc5yQmAxAMiX4AEjbjzxBNPeLnWrVtnl6nFqGzZsvZr 3mQj3ugPRSVnqr2n5CQnOQEAiYc8E/lnn3026Y490Yg77qKilqABAwaYFi1a2PnFixcnXc5E oz8UlZyp9J6Sk5zkBAAkHvKE9evXJ+Vxh4248+qrr5rKlSvb9eXKlbMde5ONKKM/FJWcqfCe kpOc5AQAJB6KNFFH3Ll8+bLZs2eP/Wo3GYk6+kNRyZns7yk5yUlOAEDioUjDiDuMckFOcpKT nABIPEAKkKoddVNt9Id4HeTISc5kzPr888+Tk1FoAJB4gKIs8lE66qbC6A9ROuqSk5zJlDU9 PZ2cjEIDgMQD5JXIJ9uIO2EddVNh9IcoHeTISc5kzOoEl5wAgMQDfA+SbcSdqB11k330h6gd 5MhJzmTMqhIicgIAEg9QhMhJR91kHv0hJx3kyEnOZMxKTgBA4gGKOKk64g4/R09OspITAJB4 AES+kBM04k6qdXiMN0ILOVMrZ6r97RaVnABIPAAUqMgnW0ddEWXEnVToIBdlhBZypkbOVPrb LSo5AZB4ACgwkq2jriNsxJ1U6PAYZYQWcqZWzlT42y0qOQGQeACAHBJ1xJ1k7yAXdYQWcqZW zmT/2y0qOQGQeACAHJKTEXeSmaLyk/TkJCcAIPEAUERhxB1ykpOcAIDEAwAif9MJGm1HMGoJ OckJAEg8ABQJkU+2EXcSjbbjFyJGLSEnOQEAiQeAlCQZR9wJG21HMGoJOckJAEg8AEAhIepo O4JRS8hJTgBA4gEACgGMtsPoLOQEACQeACAFSAWRD+qom4qjlgR17nz++efJySg0AEg8AAAi n1win6ijbqqNWhKvc2d6ejo5GYUGAIkHACjKIp9so+2EddRNlVFLwjp3OsElJwAg8QAARYxk G20nakfdVBi1JErnTpUQkRMAkHgAACjU5KSjbrKPWhK1cyc5AQCJBwCApCNVR9wRqdhZtyjn BEDiAQAAUkzkg0bcEanUWTdoFJqLFy+mXE4AJB4AACCHIp9sHXVFohF3/IKb7J07441Cc+zY sZTKCYDEAwAA5IBk66jrCBtxRyR7Z92wUWiOHz+eEjkBkHgAAIAiQNQRd0Qyd+6MMgrNpUuX kj4nABIPAABQBMjJiDvJTNRRaAAAiQcAAEhKUlXkGYUGAIkHAABA5AsxRWG0HQBA4gEAAOKK fLKNuFNURtsBACQeAAAgkGQccacojLYDAEg8AABAylBURtsBACQeAAAgZSgqo+0AABIPAACQ 0iDyAEg8AAAAIPIAgMQDAADAzRT5ZBttBwCQeAAAgCJNMo62AwBIPAAAAAAAEg8AAAAAAEg8 AAAAAAAg8QAAAAAASDwAAAAAACDxAAAAAACAxAMAAAAAIPEAAAAAAIDEAwAAAAAAEg8AAAAA gMQDAAAAAAASDwAAAAAASDwAAAAAABIPAAAAAABIPAAAAAAAIPEAAAAAAIDEAwAAAAAg8QAA AAAAgMQDAAAAAAASDwAAAACAxAMAAAAAABIPAAAAAABIPAAAAAAAEg8AAAAAAEg8ACQJu3bt Mps3by7wfQDnFAAAiQcACODTTz81xYoVs9PJkyfNmTNnTOnSpe38hx9+mKt95sU+CgO33Xab zbB48eICP5a8Oqex73dh+JsDAAAkHgByyIIFC6xMVa9e3c5fuXLFtG3b1tSrV88cOXIk0j5a tWpl9zFr1qxc7yM3r5OfXLhwwRQvXty+3u7duwv8fcqrcxr7fheGvzkAAEDiASCHZGRkWKHq 2bNnrp5/7do1U6ZMGbuPrVu35ttx3qzXceg19FqlSpWyAs37nVrHAACAxAPATeOBBx4wJUqU ML/5zW9M3759Tbly5UzLli1trXQUbty4YSZNmmRq165tqlSpYvfTrl07K1SPPfaY3Wby5Ml2 vnv37nb+m2++MePHj7elJeXLlzetW7c2K1assOsWLlzolUW46YUXXsi2j6jHPX/+fNOsWTNb NtK0aVMzd+7chK8Tjz/84Q92G72m5F989NFH3rIDBw7YZdq/WvfT0tJMo0aNzMyZM719zJkz x25/++232/lHH33Uzo8YMcLb5uc//7ldplyOTZs2mS5duth91qxZ00ycONFbl+hchpGbcxrl /U50zNevX7ct/9p++fLldtm0adPsfNWqVc2JEydCM0c9BgAAQOIBUpY77rjDyk/JkiWtEEni NC+BisLTTz/tSXCNGjW8chFNklYhSdX8r371Kzs/dOhQOy/xHDhwoBVsva46WErsnJBVqlTJ DBkyxHz88cfZ9hHluF999VVPsiWO7tjefvvtuK8TD38pzFdffeVJr+aVQUyfPt3OS34lxjo2 zb/11lt2vQRT83ot0bt3bzv/7LPPeq/TpEkTu8zdbKxevdrbj6RVrfh6/NJLL4WeyzByc06j vN9hx6ybDs3rhmXfvn2mbNmyWaQ+7PlRjgEAAJB4gJRFLZpq6ZT8PPPMM3aZRErzWh7G6dOn vXIUJ1gSMCdUrkSlTZs23jaSYSdox44ds+t/97vf2RbkF1980c7rWLT+nnvu8V7Lv48ox63O jRUqVLDLdEzCtTzfd999cV8nEa4Fedu2bebcuXPeMahFXtStW9fOz5s3z85L1jX/0EMP2XmV emhercj+7V3L+eXLl71zo3Onkhu1QvtbmJcuXWrn9e1ClHOZiJye0yjvd9gxi88//9yKt/al mnytGzZsmF0X9vyof3MAAIDEA6Qshw4d8uTn6NGjdtl7773ntU6HoVIVbSu5lQQKV2IiSZNk +uVQJRIqRalYsaKdf/DBB01mZqZXnuKQ0Gn9k08+me1mQ/uIctyLFi2y8xJah1rQ1VK7Zs2a wNcJo0+fPnb7lStXmpdfftk+7tixo7deOVQu4hg9erTd5pFHHrHz6nSp+VWrVmVp2d+7d69d r7IVl0s3CU5Olf38+fNeBtdaHuVcRrmBi3pOo7zfYcfs6Nq1q/d6knbJuV/I4z0/yjEAAAAS D5DSrFu3zspP5cqVvWWvvPKKXaZSkzBceYhr2Rau7lvlHbE3CsePH7fL1q9fb6pVq+Ytl5BJ QB0Sby2fPXt24D6iHLerN1fJSzxiXyeMJ554wmsBds91pTLuxkFyqmwqRXGSrrr4U6dOeRnU Eq3SHSemV69etc/XsJNaVqdOHTuvFvvYun03qf49yrmMcgMX9ZxGeb+jHLNwpTyadEPkCHt+ lGMAAAAkHiClcTXcnTp18pa5UT5GjhwZ+vwxY8bYbdPT07OJfb9+/eLeKAiVjqhFWx0o3dCA aln1txBv2bIlcB9RjtvNS+Ydhw8ftjXYauENep0wJPva/q677rL/NmzY0Gt5d8eklvEJEybY EpBbbrnFLpNoq7XbtTDrtZ2wqwbe4WrFe/XqZedVGqN5dZD97W9/m2WaOnVq6LnMyQ1clHMa 5f2OcswbNmzIIueq63eEPT/KMQAAABIPkNL84he/sPIjMXJIILVM9eNhuJryO++808rsl19+ 6f2Y0VNPPRUoh/pXnSbff/99O69SEtf5VPXQKqtwcufKTGL3EeW41frtyl10bCrJUFmIlmmk maDXCUOy75dPtVQ7XH25jlW4lnZNavWeMWNGllZtN665zpeOTy31LVq0yFIL7mrS1TLvyk0+ +eQTr2Y97Fzm5AYuyjmN8n6HHfPZs2e9vgCuz4A6tuqHp6I8P8oxAAAAEg+Q0rRv397Kz+9/ /3tvmeTJ1X2HoRpuVzKi1l/XyVKTSkuEG8HFyaEbTrBWrVp2NBWNLqL5wYMH2/UqLXEdUtVK rPrx2H1EOW7JogTXjXCiUgw9Vl17vNcJwy/+Gg5Rwzs6VN7h6sc7dOjg/RKqzolk07Ugu/Ie /y+M6ty57f3lPTpGJ/Y6/gYNGtjz7Ya0DDuXicjNOY3yfocd86hRo+y65s2b2xsNNyKOG4oz 7PlRjgEAAJB4gJTGSazKG4Q6BTohUtlJFCSc6pgoqdUoLCqD0PPd2OISWs270VJU5vH888/b 7TR0oGq4VSpx6dIlb5/qvCghlYSr02LsPqIe9/bt203nzp3taCYSeY0n7u/4GPs6UXCdUzXM oR+19N97771WPOvXr28zumPSa7oMWu5QHp07ib8617rhJf3lPRplZ/jw4fZGQ/vWcI8ud5Rz GY/cntOw9zvRMbtOqxJvfRsi3Dcm/g7IiTJHPQYAAEDiAYosbqi/2EmtolFEkazkAQAAJB4A biJqiVUrtmqmY6co5RpkJQ8AACDxAAAAAACAxAMAAAAAIPEAAAAAAIDEAwAAAAAAEg8AAAAA gMQDAAAAAAASDwAAAAAASDwAAAAAABIPAAAAAABIPAAAAAAAIPEAAAAAAEg8pwAAAAAAAIkH AAAAAAAkHgAAAAAAkHgAAAAAACQeAAAAAACQeAAAAAAAQOIBAAAAAJB4AAAAAABA4gEAAAAA AIkHAAAAAEgZ/h+1pW8K6e3QWwAAAABJRU5ErkJggg== --------------B094494E4371AEA342B2A256--