PoC: prefetching index leaf pages (for inserts)

Started by Tomas Vondraabout 2 years ago6 messages
#1Tomas Vondra
tomas.vondra@enterprisedb.com
1 attachment(s)

Hi,

Some time ago I started a thread about prefetching heap pages during
index scans [1]https://commitfest.postgresql.org/45/4351/. That however only helps when reading rows, not when
inserting them.

Imagine inserting a row into a table with many indexes - we insert the
row into the table, and then into the indexes one by one, synchronously.
We walk the index, determine the appropriate leaf page, read it from
disk into memory, insert the index tuple, and then do the same thing for
the next index.

If there are many indexes, and there's not much correlation with the
table, this may easily results in I/O happening synchronously with queue
depth 1. Hard to make it even slower ...

This can be a problem even with a modest number of indexes - imagine
bulk-loading data into a table using COPY (say, in 100-row batches).
Inserting the rows into heap happens in a bulk, but the indexes are
still modified in a loop, as if for single-row inserts. Not great.

The with multiple connections the concurrent I/O may be generated that
way, but for low-concurrency workloads (e.g. batch jobs) that may not
really work.

I had an idea what we might do about this - we can walk the index,
almost as if we're inserting the index tuple, but only the "inner"
non-leaf pages. And instead of descending to the leaf page, we just
prefetch it. The non-leaf pages are typically <1% of the index, and hot,
so likely already cached, so not worth prefetching those.

The attached patch does a PoC of this. It adds a new AM function
"amprefetch", with an implementation for btree indexes, mimicking the
index lookup, except that it only prefetches the leaf page as explained
a bit earlier.

In the executor, this is wrapped in ExecInsertPrefetchIndexes() which
gets called in various places right before ExecInsertPrefetchIndexes().
I thought about doing that in ExecInsertPrefetchIndexes() directly, but
that would not work for COPY, where we want to issue the prefetches for
the whole batch, not for individual tuples.

This may need various improvements - the prefetch duplicates a couple
steps that could be expensive (e.g. evaluation of index predicates,
forming index tuples, and so on). Would be nice to improve this, but
good enough for PoC I think.

Another gap is lack of incremental prefetch (ramp-up). We just prefetch
all the indexes, for all tuples. But I think that's OK. We know we'll
need those pages, and the number is fairly limited.

There's a GUC enable_insert_prefetch, that can be used to enable this
insert prefetching.

I did a simple test on two machines - one with SATA SSD RAID, one with
NVMe SSD. In both cases the data (table+indexes) are an order of
magnitude larger than RAM. The indexes are on UUID, so pretty random and
there's no correlation. Then batches of 100, 1000 and 10000 rows are
inserted, with/without the prefetching.

With 5 indexes, the results look like this:

SATA SSD RAID
-------------

rows no prefetch prefetch
100 176.872 ms 70.910 ms
1000 1035.056 ms 590.495 ms
10000 8494.836 ms 3216.206 ms

NVMe
----

rows no prefetch prefetch
100 133.365 ms 72.899 ms
1000 1572.379 ms 829.298 ms
10000 11889.143 ms 3621.981 ms

Not bad, I guess. Cutting the time to ~30% is nice.

The fewer the indexes, the smaller the difference (with 1 index there is
almost no difference), of course.

regards

[1]: https://commitfest.postgresql.org/45/4351/

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Attachments:

index-insert-prefetch-20231022.patchtext/x-patch; charset=UTF-8; name=index-insert-prefetch-20231022.patchDownload
diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.c
index af392bc032..dc3197401c 100644
--- a/src/backend/access/brin/brin.c
+++ b/src/backend/access/brin/brin.c
@@ -117,6 +117,7 @@ brinhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = brinbuild;
 	amroutine->ambuildempty = brinbuildempty;
 	amroutine->aminsert = brininsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = brinbulkdelete;
 	amroutine->amvacuumcleanup = brinvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index 7a4cd93f30..666d58a750 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -64,6 +64,7 @@ ginhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = ginbuild;
 	amroutine->ambuildempty = ginbuildempty;
 	amroutine->aminsert = gininsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = ginbulkdelete;
 	amroutine->amvacuumcleanup = ginvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 8ef5fa0329..3ed72cce44 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -86,6 +86,7 @@ gisthandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = gistbuild;
 	amroutine->ambuildempty = gistbuildempty;
 	amroutine->aminsert = gistinsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = gistbulkdelete;
 	amroutine->amvacuumcleanup = gistvacuumcleanup;
 	amroutine->amcanreturn = gistcanreturn;
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c
index fc5d97f606..442a963125 100644
--- a/src/backend/access/hash/hash.c
+++ b/src/backend/access/hash/hash.c
@@ -83,6 +83,7 @@ hashhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = hashbuild;
 	amroutine->ambuildempty = hashbuildempty;
 	amroutine->aminsert = hashinsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = hashbulkdelete;
 	amroutine->amvacuumcleanup = hashvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index b25b03f7ab..025b56ba4c 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -63,6 +63,7 @@
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
 
+bool              enable_insert_prefetch = true;
 
 /* ----------------------------------------------------------------
  *					macros used in index_ routines
@@ -196,6 +197,27 @@ index_insert(Relation indexRelation,
 											 indexInfo);
 }
 
+/* ----------------
+ *		index_prefetch - prefetch index pages for insert
+ * ----------------
+ */
+void
+index_prefetch(Relation indexRelation,
+			   Datum *values,
+			   bool *isnull,
+			   Relation heapRelation,
+			   IndexInfo *indexInfo)
+{
+	RELATION_CHECKS;
+	CHECK_REL_PROCEDURE(amprefetch);
+
+	if (indexRelation->rd_indam->amprefetch == NULL)
+		return;
+
+	indexRelation->rd_indam->amprefetch(indexRelation, values, isnull,
+									    heapRelation, indexInfo);
+}
+
 /*
  * index_beginscan - start a scan of an index with amgettuple
  *
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index 9cff4f2931..7eda2258ee 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -275,6 +275,49 @@ search:
 	return is_unique;
 }
 
+/* XXX simplified version of _bt_doinsert */
+void
+_bt_doprefetch(Relation rel, IndexTuple itup, Relation heapRel)
+{
+	BTInsertStateData insertstate;
+	BTScanInsert itup_key;
+
+	/* we need an insertion scan key to do our search, so build one */
+	itup_key = _bt_mkscankey(rel, itup);
+
+	/*
+	 * Fill in the BTInsertState working area, to track the current page and
+	 * position within the page to insert on.
+	 *
+	 * Note that itemsz is passed down to lower level code that deals with
+	 * inserting the item.  It must be MAXALIGN()'d.  This ensures that space
+	 * accounting code consistently considers the alignment overhead that we
+	 * expect PageAddItem() will add later.  (Actually, index_form_tuple() is
+	 * already conservative about alignment, but we don't rely on that from
+	 * this distance.  Besides, preserving the "true" tuple size in index
+	 * tuple headers for the benefit of nbtsplitloc.c might happen someday.
+	 * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
+	 */
+	insertstate.itup = itup;
+	insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
+	insertstate.itup_key = itup_key;
+	insertstate.bounds_valid = false;
+	insertstate.buf = InvalidBuffer;
+	insertstate.postingoff = 0;
+
+	/*
+	 * Find and lock the leaf page that the tuple should be added to by
+	 * searching from the root page.  insertstate.buf will hold a buffer that
+	 * is locked in exclusive mode afterwards.
+	 *
+	 * XXX Same as _bt_search, but just prefetches the leaf page and then
+	 * releases it. We don't need the stack.
+	 */
+	_bt_prefetch(rel, heapRel, &insertstate);
+
+	pfree(itup_key);
+}
+
 /*
  *	_bt_search_insert() -- _bt_search() wrapper for inserts
  *
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 92950b3776..e12f85a177 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -122,6 +122,7 @@ bthandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = btbuild;
 	amroutine->ambuildempty = btbuildempty;
 	amroutine->aminsert = btinsert;
+	amroutine->amprefetch = btprefetch;
 	amroutine->ambulkdelete = btbulkdelete;
 	amroutine->amvacuumcleanup = btvacuumcleanup;
 	amroutine->amcanreturn = btcanreturn;
@@ -207,6 +208,26 @@ btinsert(Relation rel, Datum *values, bool *isnull,
 	return result;
 }
 
+/*
+ *	btprefetch() -- prefetch pages for insert into the index
+ *
+ *		Descend the tree recursively, find the appropriate location for our
+ *		new tuple, and prefetch the page(s).
+ */
+void
+btprefetch(Relation rel, Datum *values, bool *isnull, Relation heapRel,
+		   IndexInfo *indexInfo)
+{
+	IndexTuple	itup;
+
+	/* generate an index tuple */
+	itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
+
+	_bt_doprefetch(rel, itup, heapRel);
+
+	pfree(itup);
+}
+
 /*
  *	btgettuple() -- Get the next tuple in the scan.
  */
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index efc5284e5b..eb215c3b24 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -200,6 +200,101 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
 	return stack_in;
 }
 
+void
+_bt_prefetch(Relation rel, Relation heaprel, BTInsertState insertstate)
+{
+	Buffer		buffer;
+	BTStack		stack_in = NULL;
+	int			access = BT_READ;
+	BTScanInsert	key = insertstate->itup_key;
+
+	/* Get the root page to start with */
+	buffer = _bt_getroot(rel, heaprel, access);
+
+	/* If index is empty, no root page is created. */
+	if (!BufferIsValid(buffer))
+		return;
+
+	/* Loop iterates once per level descended in the tree */
+	for (;;)
+	{
+		Page		page;
+		BTPageOpaque opaque;
+		OffsetNumber offnum;
+		ItemId		itemid;
+		IndexTuple	itup;
+		BlockNumber child;
+		BTStack		new_stack;
+
+		/*
+		 * Race -- the page we just grabbed may have split since we read its
+		 * downlink in its parent page (or the metapage).  If it has, we may
+		 * need to move right to its new sibling.  Do that.
+		 *
+		 * In write-mode, allow _bt_moveright to finish any incomplete splits
+		 * along the way.  Strictly speaking, we'd only need to finish an
+		 * incomplete split on the leaf page we're about to insert to, not on
+		 * any of the upper levels (internal pages with incomplete splits are
+		 * also taken care of in _bt_getstackbuf).  But this is a good
+		 * opportunity to finish splits of internal pages too.
+		 */
+		buffer = _bt_moveright(rel, heaprel, key, buffer,
+							   (access == BT_WRITE), stack_in, access);
+
+		/* if this is a leaf page, we're done */
+		page = BufferGetPage(buffer);
+		opaque = BTPageGetOpaque(page);
+
+		/* we should never see a leaf page here, we only prefetch it */
+		Assert(!P_ISLEAF(opaque));
+
+		/*
+		 * Find the appropriate pivot tuple on this page.  Its downlink points
+		 * to the child page that we're about to descend to.
+		 */
+		offnum = _bt_binsrch(rel, key, buffer);
+		itemid = PageGetItemId(page, offnum);
+		itup = (IndexTuple) PageGetItem(page, itemid);
+		Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace);
+		child = BTreeTupleGetDownLink(itup);
+
+		/* we should never actually visit a leaf page during prefetching */
+		Assert(!P_ISLEAF(opaque));
+
+		/*
+		 * Page level 1 is lowest non-leaf page level prior to leaves.  So, if
+		 * we're on the level 1 and asked to lock leaf page in write mode,
+		 * then lock next page in write mode, because it must be a leaf.
+		 */
+		if (opaque->btpo_level == 1)
+		{
+			PrefetchBuffer(rel, MAIN_FORKNUM, child);
+			break;
+		}
+
+		/*
+		 * We need to save the location of the pivot tuple we chose in a new
+		 * stack entry for this page/level.  If caller ends up splitting a
+		 * page one level down, it usually ends up inserting a new pivot
+		 * tuple/downlink immediately after the location recorded here.
+		 */
+		new_stack = (BTStack) palloc(sizeof(BTStackData));
+		new_stack->bts_blkno = BufferGetBlockNumber(buffer);
+		new_stack->bts_offset = offnum;
+		new_stack->bts_parent = stack_in;
+
+		/* drop the read lock on the page, then acquire one on its child */
+		buffer = _bt_relandgetbuf(rel, buffer, child, access);
+
+		/* okay, all set to move down a level */
+		stack_in = new_stack;
+	}
+
+	_bt_relbuf(rel, buffer);
+
+	_bt_freestack(stack_in);
+}
+
 /*
  *	_bt_moveright() -- move right in the btree if necessary.
  *
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c
index c112e1e5dd..5dba71c6e4 100644
--- a/src/backend/access/spgist/spgutils.c
+++ b/src/backend/access/spgist/spgutils.c
@@ -70,6 +70,7 @@ spghandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = spgbuild;
 	amroutine->ambuildempty = spgbuildempty;
 	amroutine->aminsert = spginsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = spgbulkdelete;
 	amroutine->amvacuumcleanup = spgvacuumcleanup;
 	amroutine->amcanreturn = spgcanreturn;
diff --git a/src/backend/commands/copyfrom.c b/src/backend/commands/copyfrom.c
index cec80bacea..0309377869 100644
--- a/src/backend/commands/copyfrom.c
+++ b/src/backend/commands/copyfrom.c
@@ -421,6 +421,16 @@ CopyMultiInsertBufferFlush(CopyMultiInsertInfo *miinfo,
 						   buffer->bistate);
 		MemoryContextSwitchTo(oldcontext);
 
+		for (i = 0; i < nused; i++)
+		{
+			if (resultRelInfo->ri_NumIndices > 0)
+			{
+				ExecInsertPrefetchIndexes(resultRelInfo,
+										  buffer->slots[i], estate, false,
+										  false, NULL, NIL, false);
+			}
+		}
+
 		for (i = 0; i < nused; i++)
 		{
 			/*
@@ -1242,6 +1252,16 @@ CopyFrom(CopyFromState cstate)
 										   myslot, mycid, ti_options, bistate);
 
 						if (resultRelInfo->ri_NumIndices > 0)
+						{
+							ExecInsertPrefetchIndexes(resultRelInfo,
+													  myslot,
+													  estate,
+													  false,
+													  false,
+													  NULL,
+													  NIL,
+													  false);
+
 							recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 																   myslot,
 																   estate,
@@ -1250,6 +1270,7 @@ CopyFrom(CopyFromState cstate)
 																   NULL,
 																   NIL,
 																   false);
+						}
 					}
 
 					/* AFTER ROW INSERT Triggers */
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index 3c6730632d..52c31c17bd 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -113,6 +113,7 @@
 #include "catalog/index.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
+#include "optimizer/cost.h"
 #include "storage/lmgr.h"
 #include "utils/snapmgr.h"
 
@@ -252,6 +253,111 @@ ExecCloseIndices(ResultRelInfo *resultRelInfo)
 	 */
 }
 
+void
+ExecInsertPrefetchIndexes(ResultRelInfo *resultRelInfo,
+						  TupleTableSlot *slot,
+						  EState *estate,
+						  bool update,
+						  bool noDupErr,
+						  bool *specConflict,
+						  List *arbiterIndexes,
+						  bool onlySummarizing)
+{
+	int			i;
+	int			numIndices;
+	RelationPtr relationDescs;
+	Relation	heapRelation;
+	IndexInfo **indexInfoArray;
+	ExprContext *econtext;
+	Datum		values[INDEX_MAX_KEYS];
+	bool		isnull[INDEX_MAX_KEYS];
+
+	if (!enable_insert_prefetch)
+		return;
+
+	/*
+	 * Get information from the result relation info structure.
+	 */
+	numIndices = resultRelInfo->ri_NumIndices;
+	relationDescs = resultRelInfo->ri_IndexRelationDescs;
+	indexInfoArray = resultRelInfo->ri_IndexRelationInfo;
+	heapRelation = resultRelInfo->ri_RelationDesc;
+
+	/* Sanity check: slot must belong to the same rel as the resultRelInfo. */
+	Assert(slot->tts_tableOid == RelationGetRelid(heapRelation));
+
+	/*
+	 * We will use the EState's per-tuple context for evaluating predicates
+	 * and index expressions (creating it if it's not already there).
+	 */
+	econtext = GetPerTupleExprContext(estate);
+
+	/* Arrange for econtext's scan tuple to be the tuple under test */
+	econtext->ecxt_scantuple = slot;
+
+	/*
+	 * for each index, form and insert the index tuple
+	 */
+	for (i = 0; i < numIndices; i++)
+	{
+		Relation	indexRelation = relationDescs[i];
+		IndexInfo  *indexInfo;
+
+		if (indexRelation == NULL)
+			continue;
+
+		indexInfo = indexInfoArray[i];
+
+		/* If the index is marked as read-only, ignore it */
+		if (!indexInfo->ii_ReadyForInserts)
+			continue;
+
+		/*
+		 * Skip processing of non-summarizing indexes if we only update
+		 * summarizing indexes
+		 */
+		if (onlySummarizing && !indexInfo->ii_Summarizing)
+			continue;
+
+		/* Check for partial index */
+		if (indexInfo->ii_Predicate != NIL)
+		{
+			ExprState  *predicate;
+
+			/*
+			 * If predicate state not set up yet, create it (in the estate's
+			 * per-query context)
+			 */
+			predicate = indexInfo->ii_PredicateState;
+			if (predicate == NULL)
+			{
+				predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate);
+				indexInfo->ii_PredicateState = predicate;
+			}
+
+			/* Skip this index-update if the predicate isn't satisfied */
+			if (!ExecQual(predicate, econtext))
+				continue;
+		}
+
+		/*
+		 * FormIndexDatum fills in its values and isnull parameters with the
+		 * appropriate values for the column(s) of the index.
+		 */
+		FormIndexDatum(indexInfo,
+					   slot,
+					   estate,
+					   values,
+					   isnull);
+
+		index_prefetch(indexRelation,
+					   values,
+					   isnull,
+					   heapRelation,
+					   indexInfo);
+	}
+}
+
 /* ----------------------------------------------------------------
  *		ExecInsertIndexTuples
  *
diff --git a/src/backend/executor/execReplication.c b/src/backend/executor/execReplication.c
index 81f27042bc..ad371e4ec9 100644
--- a/src/backend/executor/execReplication.c
+++ b/src/backend/executor/execReplication.c
@@ -532,9 +532,14 @@ ExecSimpleRelationInsert(ResultRelInfo *resultRelInfo,
 		simple_table_tuple_insert(resultRelInfo->ri_RelationDesc, slot);
 
 		if (resultRelInfo->ri_NumIndices > 0)
+		{
+			ExecInsertPrefetchIndexes(resultRelInfo,
+									  slot, estate, false, false,
+									  NULL, NIL, false);
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, false, false,
 												   NULL, NIL, false);
+		}
 
 		/* AFTER ROW INSERT Triggers */
 		ExecARInsertTriggers(estate, resultRelInfo, slot,
@@ -600,10 +605,17 @@ ExecSimpleRelationUpdate(ResultRelInfo *resultRelInfo,
 								  &update_indexes);
 
 		if (resultRelInfo->ri_NumIndices > 0 && (update_indexes != TU_None))
+		{
+			ExecInsertIndexTuples(resultRelInfo,
+								  slot, estate, true, false,
+								  NULL, NIL,
+								  (update_indexes == TU_Summarizing));
+
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, true, false,
 												   NULL, NIL,
 												   (update_indexes == TU_Summarizing));
+		}
 
 		/* AFTER ROW UPDATE Triggers */
 		ExecARUpdateTriggers(estate, resultRelInfo,
diff --git a/src/backend/executor/nodeModifyTable.c b/src/backend/executor/nodeModifyTable.c
index f62d28ac60..2acbf67300 100644
--- a/src/backend/executor/nodeModifyTable.c
+++ b/src/backend/executor/nodeModifyTable.c
@@ -1094,6 +1094,13 @@ ExecInsert(ModifyTableContext *context,
 										   NULL,
 										   specToken);
 
+			/* prefetch index leafs before inserting index tuples */
+			ExecInsertPrefetchIndexes(resultRelInfo,
+									  slot, estate, false, true,
+									  &specConflict,
+									  arbiterIndexes,
+									  false);
+
 			/* insert index entries for tuple */
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, false, true,
@@ -1136,10 +1143,17 @@ ExecInsert(ModifyTableContext *context,
 
 			/* insert index entries for tuple */
 			if (resultRelInfo->ri_NumIndices > 0)
+			{
+				ExecInsertPrefetchIndexes(resultRelInfo,
+										  slot, estate, false,
+										  false, NULL, NIL,
+										  false);
+
 				recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 													   slot, estate, false,
 													   false, NULL, NIL,
 													   false);
+			}
 		}
 	}
 
@@ -2127,11 +2141,19 @@ ExecUpdateEpilogue(ModifyTableContext *context, UpdateContext *updateCxt,
 
 	/* insert index entries for tuple if necessary */
 	if (resultRelInfo->ri_NumIndices > 0 && (updateCxt->updateIndexes != TU_None))
+	{
+		ExecInsertPrefetchIndexes(resultRelInfo,
+								  slot, context->estate,
+								  true, false,
+								  NULL, NIL,
+								  (updateCxt->updateIndexes == TU_Summarizing));
+
 		recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 											   slot, context->estate,
 											   true, false,
 											   NULL, NIL,
 											   (updateCxt->updateIndexes == TU_Summarizing));
+	}
 
 	/* AFTER ROW UPDATE Triggers */
 	ExecARUpdateTriggers(context->estate, resultRelInfo,
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 4c58574166..2e7f9c1eec 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1027,6 +1027,16 @@ struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_insert_prefetch", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables the planner's use of index insert prefetching."),
+			NULL,
+			GUC_EXPLAIN
+		},
+		&enable_insert_prefetch,
+		false,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h
index 4476ff7fba..73128a8937 100644
--- a/src/include/access/amapi.h
+++ b/src/include/access/amapi.h
@@ -113,6 +113,13 @@ typedef bool (*aminsert_function) (Relation indexRelation,
 								   bool indexUnchanged,
 								   struct IndexInfo *indexInfo);
 
+/* prefetch pages for new tuple */
+typedef void (*amprefetch_function) (Relation indexRelation,
+									 Datum *values,
+									 bool *isnull,
+									 Relation heapRelation,
+									 struct IndexInfo *indexInfo);
+
 /* bulk delete */
 typedef IndexBulkDeleteResult *(*ambulkdelete_function) (IndexVacuumInfo *info,
 														 IndexBulkDeleteResult *stats,
@@ -261,6 +268,7 @@ typedef struct IndexAmRoutine
 	ambuild_function ambuild;
 	ambuildempty_function ambuildempty;
 	aminsert_function aminsert;
+	amprefetch_function amprefetch;
 	ambulkdelete_function ambulkdelete;
 	amvacuumcleanup_function amvacuumcleanup;
 	amcanreturn_function amcanreturn;	/* can be NULL */
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index 4e626c615e..91e7cfc4d0 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -149,6 +149,11 @@ extern bool index_insert(Relation indexRelation,
 						 bool indexUnchanged,
 						 struct IndexInfo *indexInfo);
 
+extern void index_prefetch(Relation indexRelation,
+						   Datum *values, bool *isnull,
+						   Relation heapRelation,
+						   struct IndexInfo *indexInfo);
+
 extern IndexScanDesc index_beginscan(Relation heapRelation,
 									 Relation indexRelation,
 									 Snapshot snapshot,
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 7bfbf3086c..3df531bb16 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1135,6 +1135,10 @@ extern bool btinsert(Relation rel, Datum *values, bool *isnull,
 					 IndexUniqueCheck checkUnique,
 					 bool indexUnchanged,
 					 struct IndexInfo *indexInfo);
+extern void btprefetch(Relation rel,
+					   Datum *values, bool *isnull,
+					   Relation heapRelation,
+					   struct IndexInfo *indexInfo);
 extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
 extern Size btestimateparallelscan(void);
 extern void btinitparallelscan(void *target);
@@ -1185,6 +1189,8 @@ extern IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting,
 extern bool _bt_doinsert(Relation rel, IndexTuple itup,
 						 IndexUniqueCheck checkUnique, bool indexUnchanged,
 						 Relation heapRel);
+extern void _bt_doprefetch(Relation rel, IndexTuple itup,
+						   Relation heapRel);
 extern void _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf,
 							 BTStack stack);
 extern Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack,
@@ -1237,6 +1243,8 @@ extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate);
  */
 extern BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key,
 						  Buffer *bufP, int access);
+extern void _bt_prefetch(Relation rel, Relation heaprel,
+						 BTInsertState insertstate);
 extern Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key,
 							Buffer buf, bool forupdate, BTStack stack,
 							int access);
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index e1eefb400b..f82505a86b 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -632,6 +632,12 @@ extern List *ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
 								   bool noDupErr,
 								   bool *specConflict, List *arbiterIndexes,
 								   bool onlySummarizing);
+extern void ExecInsertPrefetchIndexes(ResultRelInfo *resultRelInfo,
+									  TupleTableSlot *slot, EState *estate,
+									  bool update,
+									  bool noDupErr,
+									  bool *specConflict, List *arbiterIndexes,
+									  bool onlySummarizing);
 extern bool ExecCheckIndexConstraints(ResultRelInfo *resultRelInfo,
 									  TupleTableSlot *slot,
 									  EState *estate, ItemPointer conflictTid,
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index bee090ffc2..33e89b82bc 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -70,6 +70,7 @@ extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
 extern PGDLLIMPORT bool enable_presorted_aggregate;
 extern PGDLLIMPORT bool enable_async_append;
+extern PGDLLIMPORT bool enable_insert_prefetch;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
#2Tomas Vondra
tomas.vondra@enterprisedb.com
In reply to: Tomas Vondra (#1)
2 attachment(s)
Re: PoC: prefetching index leaf pages (for inserts)

Hi,

I had a chance to discuss this patch with Andres off-list a couple days
ago, and he suggested he tried sorting the (index) tuples before
inserting them, and that yielded significant benefits, possibly
comparable to the prefetching.

I've been somewhat skeptical the sorting might be very beneficial, but I
decided to do some more tests comparing the benefits.

The sorting only really works for bulk inserts (e.g. from COPY), when we
have multiple index tuples for each index. But I didn't have time to
rework the code like that, so I took a simpler approach - do the sort in
the INSERT, so that the insert tuples are sorted too. So, something like

WITH data AS (SELECT md5(random()::text)::uuid
FROM generate_series(1,100) ORDER BY 1)
INSERT INTO t SELECT * FROM data;

Obviously, this can only sort the rows in one way - if there are
multiple indexes, then only one of them will be sorted, limiting the
possible benefit of the optimization. In the COPY code we could do a
separate sort for each index, so the tuples would be sorted for all
indexes (which also has a cost, of course).

But as I said, I decided to do the simple SQL-level sort. There are
multiple indexes on the same column, so it's a bit as if we sorted the
tuples for each index independently.

Anyway, the test inserts batches of 100, ..., 100k rows into tables of
different sizes (10M - 1B rows), with/without prefetching, and possibly
sorts the batches before the insert. See the attached index.sql script.

The PDF shows the results, and also compares the different combinations.
For example the first 5 lines are results without and with prefetching,
followed by speedup, where green=faster and red=slower. For example 50%
means prefetching makes it 2x as fast.

Similarly, first column has timings without / with sorting, with speedup
right under it. Diagonally, we have speedup for enabling both sorting
and prefetch.

I did that with different table sizes, where 10M easily fits into RAM
while 1B certainly exceeds it. And I did that on the usual two machines
with different amounts of RAM and storage (SATA SSD vs. NVME).

The results are mostly similar on both, I think:

* On 10M tables (fits into RAM including indexes), prefetching doesn't
really help (assuming the data is not evicted from memory for other
reasons), and actually hurts a bit (~20%). Sorting does help, depending
on the number of indexes - can be 10-40% faster.

* On 1B tables (exceeds RAM), prefetching is a clear winner. Sorting
does not make any difference except for a couple rare "blips".

* On 100M tables it's a mix/transition of those two cases.

So maybe we should try doing both, perhaps with some heuristics to only
do the prefetching on sufficiently large/random indexes, and sorting
only on smaller ones?

Another option would be to make the prefetching smarter so that we don't
prefetch data that is already in memory (either in shared buffers or in
page cache). That would reduce the overhead/slowdown visible in results
on the 10M table.

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Attachments:

prefetch-benchmark.pdfapplication/pdf; name=prefetch-benchmark.pdfDownload
%PDF-1.4
%����
1 0 obj
<</Title (prefetch benchmark)
/Producer (Skia/PDF m120 Google Docs Renderer)>>
endobj
3 0 obj
<</ca 1
/BM /Normal>>
endobj
6 0 obj
<</CA 1
/ca 1
/LC 0
/LJ 0
/LW 1.33333337
/ML 10
/SA true
/BM /Normal>>
endobj
7 0 obj
<</CA 1
/ca 1
/LC 0
/LJ 0
/LW 2.6666667
/ML 10
/SA true
/BM /Normal>>
endobj
8 0 obj
<</Filter /FlateDecode
/Length 5319>> stream
x������������u���Y����u��=(���?P9#�Cq�Y���&����F�#����������J?\���~����\����P���?�p+������`n?��>WJ�[�����?���Gv��o�,S�vV�5-����D�nS���y[a}
�o��|������h&�K-���c�9Md'����ivR�Ig�S������`r��M.��hH��(9
��z�O-�j	x�$�_|�%��D~��t�h��������z�Z�%&����Z`���<E�c����~]�sb	�[P�6g�1��Z��p�I"�8[K�Y&����OuJH���u���d�n��S\�I���������I7hnk:l���o����L��{����H?g_t�0�.��/I�R�u7�l'���D�^&��rQl.f"H1���)���/�,3!��Q��h���c�V!��Q�xN��ZJ�������o�2d�Q����=���T��N��A��Z�S]�r��(6���E9�L��K�����,����*�D��9}�|���S���j�UH�������uj-�����E9}�(���bs���Z���D�9�:~j��>��$��q��U6�L-&��V�)}\��i����7+s!�ic��h����^Ot-�$���E9��('��bs���Z��D�9}���Q9�����TKX���h��+&�Dse�����vk������mN�:��"J2WO�V���d;����d&�$3$��bsAH2A��(6�g4�7iMr�:J9��V��`��r�?�uW!&�Q�D��s����FY�h�x�kI'�� Ht-���E9�L��D���h&���SRMmU�lq!��QV��%��g���NV!�z[�h��w!��+R�&,����jv���T���j&��s�kQN5���kV��H�*�Ts�Q$��n��9l��CWs��V��]
BJ5W�z1�����jv���T���j&��s�kQN5�����6��O!�2J4S�&����Y����K����a@�)��z��h�<�h3��1�l'���D�h&�DsQl.�f"H4���8F�Oym�EBLu�<E�f��k�U�;�XX
�BL^�\�1�:�de.�<����<��9"�IY��e�
����
��*�0)��2�����Tt_ h�I9�S�%�r�Z�\�P-\��%���0)����+O�y�VaR�����J�$��@5���M�RG�x���R��l�i�AH���zha!Wu��k��@�������j��Z9�Wt:�=7+s!U+W��B���!U+Spo�I-��Z����)#��5�\H���>�j�f���~���FH����R��Wrh�T��r{�u�#�K�\-c����2�\��h��P�w!��\�Z�
MR
���{kJ��j�)�r#�?���FH5�(���p1�R
3�:6Zo��=����Q$�F.�f��w�\�<���O��9�\H5��s�b;������n��Ci��T�\y�n��z��������+�M��2I+z���������R����`q!�4W���R���%�dX�LU�OoM�X��������e�eA�����F���(��`�B�ge.�Jn��X@5w���)Z��um�����(�
������
S��h�i�T��YZb������x���R�2���>{��5=.�:e��qt'���R�2e_n��A����)�o�����R��+g��7�4�"�6B�W��	ku!k=J�Ry���@��M��Ls.�F�!�j����&���/y?�g*�o�����o�`o���;�s�����G���8�A�3����N��>]���n��g���n��������t����~���W���\����WRz��VCf�2pB�O�l�@�{���>1��j�������
����C>���K9�3�}*��I�Y?�=eP���qri��F�\.�������mWVM�����W�K�L��U�d�O#�&����0�z�qTjJ��&HN���������qJ�SN���
��K
��������@�8;Y����e���)
�6��;6V%����Z�����B'B���2j����R7?}�s��=�o��$%p�*9W�
i7`�ve�`R����q�5a���A�q�z67B���'��78eY?����3�Tb�u��I!�E��8����8����#@QrVT^AO*����������������l�����ugLP':�}�(����C����\���l���s�((��N{M���new�;xV�ZAxd�R�����o�;����no��BE!��mMe�����$�,�H��C�w����@�+�	�u����z��|B��!H��1�N��&%\�#�ccT��I��1�������:���37�7�'�7����y��4�����q���1��	q�8����CF����0�|,u�0�+|F��S��H�xUBr���F`�P����#Y���A��F�Z��d���d�Uz
(}s��\�P:S��+C�!�pp���-��C���Sf#���y�{m/�Da�,�d��Z2L��v���v[7��f;��zK�������%������4<�������2eF$���N��ULc�v�i��-��WF,e�!t	�'�L�%'�/H[�x���U�Gy�e�d�^b0<�����y"!L9N$.�����}CP&G��MQ��w���U��������[��B����T�J+�f�b���)�"���B���i9�j��w�-��>jk����}�;]�����"���w;$!��CQ��"�~g!B�rD}��Y��A��_r�u�`�������-��x{��/]��v�A@.�:���A8<�A�P�����.{y	���~�|/#pQ�/)[3-��������)��v'T1Bh;"���o3��t	�����`�2�B���!_�N�<t��D����4������8K7�������}H���_���@��]��E��w�R��	^�+!����]_����7@�vA��0�O.���O�AH0:u(^V���� �g(e!@����I^B���R����{59o���O�S�v��?�,/�Y�\��<Y�n����[~M|���B����;tMt���e����4�[�x6�iX^�}��o�>dyY�����'�55�B�?����O�[������}���~:,/�>b��ax-����j�X�"A���p���!@��H�U?����,��	���A��!���f�n�%���)wdn;���vd����,7]���-�����N��B����;tM���|%�?��#X�����/'����G,���C��%�X�������v�B�?���,�l+),/��X���{B�� �/'����G,@�T����ot"�,����}}-����C��~�<y�i�eA d?7�U�� �������9V3�S:YRz�s���uES����)�^�����2%y��8%��NIN�����Chw�y`�!�n�pH�N0p������h!l�G��ep!��#N��}��B��t�����.���
d.�����y2�y��)���e���"�v�Y�,�8+8"��X�g��Y��C0Z8+2q�\%���6���X�%�����P{�#�b����j{���%�|��{o�v#5����w\,[�,t��y�K� @�W�D�fi�5��e
5�D�|@��Iy��^x�pZ�����������.t�p��^�N4���O�8-�%������{a��ia�	��e�U��q��!����� N_=�=���I��+e8mR����yU���������w�%8���W��"s��!��s������K���]z��c�w�K{�8�����-�q�Ezic���!��s�[�L�e����{���~����������d.{������%�,��0H�W��=2� �_$��Xzd��)��	_�h���jo|�Tl;����o�X0]B��-?�&���2:�d����>}�_�R�]�+!����]�� ���X����|�T�@b�s���\��B�����>���O�
}%��H�=y���ebya������E�c]�rB�����W{)�Dva������A d�zF���=��;ku���?A�4��������vD�sm�^L���P|]�	��[~�ol��:��������q{7��WB�|=��]@~E="������>�V]�]�@B�s��[����!���}]�F_s��.����"��d����Bva����!��dK�0��j�X�� �_4
����!@��zd/��X�"� ~"�a��H#LJ/���
/q2a9�����7�u���SB�kx:�<qFj��H���)����D�yJ<}
OG*���U�:�n__��WF���-J7��5xt�f�r�����st�B&yJH~�]=&��50q��~�������E�&��xD�-2��\�}��q_�FG=n;�iqZ
n�A��s
�Z��F�&(�-���d_�������zZ��*Y�a��W���}����������Ujxt'^!laf����h�cK=-�}�~��B�B_����(^ gK�A�o_;U��]�rD�#�p��Fbmi
l_�F���0������T��g'�m��A���n��-��x�\_w��2o=E�>��'���y[�+����W����"��H���.��e�%�����s�m�����F����2_��/���umi�o���Kz����o��r����� o_d,�p�j����WO��m�c���#���Y�z�����+�mY�������x[�)��E<���-��x�\_�����o������,�F�
�e)'�HyK6�H=E?��.��	���W���:��A\���i���z�7����@��A-|C� ~��~��0D��Gy%��[�9�&�p����)~v7���H�"O	�����Vu`m�������}�~�;x$m����=���m&_c ��S��e���
)[�n��S=�=���-��T?�/�(��S�kdT��D������U�x�,�����w��e��	�8�5'�?_#�wT��d�2�h���s��c�p�y18��p��&c����_Nn��I��!��C`o{9$k3O>X����S�H��x<�A\�g���>���Qj�yU��)� ��������d���l��E����3�Y����������(�4@H�[�������.�����7�Z��#j�����z�1g���������P�
endstream
endobj
10 0 obj
<</Filter /FlateDecode
/Length 5343>> stream
x��]]���q}�_��,�)��`w�������������*Vu�J�m��Z��w�3�*��>�S$�v�>����4�������Y���Bw��������������?���>w��)������?�`�0�|���z��^�<�x����K>F��Z�lco�n ����
����1,�`�9$s�0��Fon��iO���}��s)�b�o]��t��l#��	�R��,%h)!DF�l��i)!PF�������Ys�`)h7�R�����2��$�>`)!I�w�RSF9�)��|1�J�H�t�n��`�F�\��.%v)!�F�l[v)!�F�����S6�,H���q��w)dcL>�.{1���e���^f;z�,DGG5��n�x��)l�q���Y�������n�����&��d����l#"�y����A���s�(�n���c����4��x���+�>&�X��^��P��R&?vy��>�� +[�8z�\�J�������B��Jpu�!=�gwW/%W����K�z)bWQZ5��^���F�V�����C���I���P]�Rv^������P]m��>GRJ>_��0e+TW[�kF���~��m�����f�RRq���\����"v��U�����]lDiu�n`�L�0����	�J�.^*���(�:����hlH�i|^	�-Fq�<Y�,%����-K�e)b�QZ5�nY��-F�V���Tf�QZu��mZ���e�F�ml{Q6������mEi� ����V�V���PB��0
�Ge�[	��V���0���h`,��B$C�Q$�����l��m�t�w�B���2��!Z�-%����yK;o)b�QZ5��[��yF�V��O�A)���~���r!�<M4�<���P��2��LCZp��P�����rE	��l��j��:�q�RRq���\����"v��U�����]mDiu{��y��d�V��6�q�g����b��P]�j��C�-�,-����m�MI���P]m�W��a�FRq���\����"v��U�����]mDiu�v�����l���3������2��y�A�z0�'��z��T3�����w�:���;z�m5i$���eG9����V�V
����mEiu{��er��UG0�i���w���o
�ar�L������Vyo!na�.���2�f����0i�Y�}�Rn���T�X�8��}���H��E
�R�an�c�3}�8Y*r�Q���$���������P��*�e'v�t�!�Pc%��2G���stQ��Pc�*����sX��w-�X1�s|"�2)Z�F�m�m��X��[���x��Y���*��hy�VH!���*�S�����j�����"[fR��Pc�*�g%��x_��B��>�c�k���i s����5��rY�a��R+����O��F�L��:wj�jL[e&U3�w31g�52�i�a��d��S5+��^*�{�	�X
4�M�\Zj���F�P��*s�P�1����i,[�sS����B�e�\��i�_++�X�������������L#��rY%�Y���P#�(73
�>�0���xm)��������6��:����U����W5�](�e����3���eLS��JdY�f'Qde�{?�,�(AnD-��G�_-�Q7@~���2�V��]��3���j}V�D���!+�����{���Ir�z�Lc��&��Z*s�QZu�c`)�8�����w>M�S�/�c?�����bv�F������������u��&���s�s�������������?b����m��n�����[�s�b.`����o�a�4H�����o�B�^C�S����o��sS���wx����s�n���ME_�D��|�:���'����Y�M	�����=M��������Y��|��,?��xsC7�?6����_�3�������Q���\���/T~V{�i��?>����e�����%8:c��iz|*��������L����Y@�;uy|y��w.�E�����ps�}jhk�XH������w�P�����j�~zX�������w���92s��4��mG������f�@�d���a��X�q��77L_��;��7
8e�������dR���{��I&�Y��2����y���W���������;�X�Ge��<�Z�D���-��{B3����0�3��R�j����;����y[�����>7JJo��Z��c����� ���<AG�Z�%l�0�'f���A5�~�r<J�V�A����K�!��{M�+k
]r�IJ>���Ug����{^��#L=l����l�4d���0�k�.�2�q��q�V�]�����n2;?M���a$�b������a$�3l����b��p�D�����8NeI����8�WN����w�adtc��%����z�a��Q��:��F&Jd�:��
�_�0B5�<w�����)�)}�fG.y8_X�J�h��~0�wq�"� h��sM��@�.u��}��U"AZ%��ys��0o�����4=���;��I���{'U�T*8�Vp`=bR�?���A2F�r�>-��4��������;7�>4�%��a�y�TI�t���-%Z�I��a���"�W�:6f�V1`�i��>v����2C�O��yi)o�X���"F�cae*o@Hysu�fdk�b@B.U�E�P��S����>�;7���>�n�Z_1�G{^�������G��������I,�3�c�p��N)&Y
���
�?���[�f��s���&��9O���YW��"b� �B����*���r��cH����u8��h�;�uB��������2o��@h�ELPuws�B'�1�~�pV-���1e��	c����u��~�����bV���]H���]X���m���C���;
H��~@������.<��aU�~V�E�X�[�E(w�O����gJLa������}/���  !�W��m�aU
��k]<Pf����fx��+��������F�������&"@:d��CcK���E��aU�~w���o���uq���b�=��c����&^��h������;6���?0!\~?�C�����m �"���.Z��O������\#���j���(�������A���1*�?w����� ���Te|��4���1������*���z�O�?�}��0���%Mmt��|��J�/����2��
�?iu��<�U���X�
��R���o�=x����F��2[��eG�.�}���/vS-��E���X���J�26sy�p��iP�4T3v��cFP.����Y8s����H>��J�����j}���re��Z3�����f8���b�����^87�q#T����-$��B�� h��Z)$�X�B�"X�BD*���H���uH
	��b�}jm���Q����g~��w�fY�����~/�J�P��������K�tn���,������w�<�n@@R��4�����T�}��5R)b0�Z���ei�]�o���4��*`�i����'%	�@-I���N��H*�"��
Z�����j�q�#)����Uf���`a��	���\�u�~��1���{�R`\��&x��	�T�?��m����O	��)_7��W>���](��}�~���u�����!�a���( ����0[�Z�����*e?�[�f�����}J��4���cT�~���x
H(���W�|x�Pv�R�s�����s��Or*e�O)�~3�����c��c��\�"F����<h��1�Q����_��5�p�!����e���	C$�/|�{��'�}s�����?���h}Gqy��r�!l�Zo.��X����6Q��/�0[.�f�p������A
�?9����Q@����}U@�'X���X����}U���Xp��>�����]�������[�<����`��Y��=(�B��p�[��(;h��Ga�oG����"����F���^�>�����:7��>
�](��}������#�}��P���x�&
H(�~@i���U�<��V��`H���� ���[���������3��Pv��J�����Lo�2e	e?7��I��T�Pv�R�s���j����`�)e�o�+-������"F�_����A���	�36.�A������
�\>c�������l�����1a��������e4JH�B��C:d!���q^E*���o}�^���R`F��`��gq��O_�/�G3\��s3��;����\�������]\a�H��87��#g�/�)�f-=���������f��$	����e���Zz\k��U R�0.�{��U�s������9�����������4��}c��4o~?�L��|�	��������3�����uh��@9�n����������B������K��v�����a��/=g�@h�5P]�h����C&P
��z+U��e������P���k��������a��X�>d�����{m�s���]�)(��l���.�s�J������E��bS��M ���M�J�������~#����-`�z�����k�9��s�V���Z�f83�P�� mMd��V����ry0���_d���JU�<�r��1BuP����&B�o��0z�J��>������C��8�}�8}���<i]��a������l��oM���	
�?������/��*��*X[C[��X������o0�zV�UF���VvC�5A��Wqw+�B�A�B�����5�Pw4���_%���Q�������_�/�j����&(��*�:}�b�~����|J	;d���.����S�T��m���s��~��j���� m���j����D0�"������w6n^%.|s���s]�{��i5�Th�E���q�f��A����>�o��|�\��q��X��J���z�+(Q���/�;�bU�|.V�Q�M�<�]��a�9d�LY�kYVk�
w��*u>�1�N!���������o��*m��G�c��i�����Z��[)����2�����1�B�]8�CH�_)x~L`���b�w�+���2�k E�_	�)|���u�:!U6|*������\��B�T��#�?�A��S�������uCpC�n������������/��^��f�q
c,��r|����=����;7��/}���gi(�u�?�=����'���5�����C!���I�����vD����fm+b�Nd������o�U_�D��;'=���|x�����#;������t�>�<�
endstream
endobj
12 0 obj
<</Filter /FlateDecode
/Length 5388>> stream
x��]]���q}�_��,�)�������N�p�o���X5�*6�yF���k�g�UO}P�Hd�����o\�+����_���6,������n��?~+?��Oo���t�����s��t[R�����������CJat��5�K��aM����c�����5���?��7�v�7��n
~[�4�sN��4�������dN:�O��>��sk��oC\�t�?lc��	����l-hk!D����	��B��%�3��+G#������?[?
��B�Z(����)[�X�=����2�9,����TF@*�����6"���vk!�[�5�d�E`�k,��yH��4�+�5�X�-�{����OQ������}o�:$������Fe$�dQ
���)_����-z$�������yj�A9��D�5&��5����_c�[S�N?�����6��+����d�C�-����3��8WF��u�������i���2J��+OS�:.�g-_�%��Iu�i=���S��4Rm�ToM����SmL�� �zk�TS�N?L��%$�c��i��kc>����e�~�h��[�������Kem,�\�&J?�g�3_(����5�Hr������H�9���5qr�&N�1��������kL�:�0���pD�4+��w���3�T
��m��{]l���F��A�����5q��)U�`oMlcJ���`o�9�����p��U�`{g���<�=(��(��D���T]��mLlkJ���%�N��9,e6��l����Y����w�l��(�X�\�R�����We��H��hS��4Rm�ToM����SmL�� �zk�TS�N?�y%#�|����Mm]�H�~��B�aWc�4��|N��/nZ���5��������H��5j��3��\i&�[K#�� J���i��8����r��&N�1���C�������0k�D[gz�@�D]�sc�$[7��J<���re�$���a��ey���5j��3��u2l�XI6Q��&N���I6�T]���5q��)U������hL��\�4Zg,��m��6&
�1Q��)U�`��Ruz,����mM��^5�|���.���F��4g���M�t����L����_�B���l���sa�I����&����+����J�������Fr��V�IkU��1;sT����~������b��0=�u�9���s7������
��>s	ve�9���4����	Ae�9��2�E>��.��5��]9�5J^����i]���,s]?w&�H�{pU���udH<��1��5jU[g�KV�X��5jU7�������5m]K<d���Z��tu]���s��'���yy����|�������tX�JTF�i�K�Sf����5��v��}�����u��%T�1%f_k���:��r�$m
Z����<����f�FZo���������|:;������8�q�l��{3�
6�!i_3�����i���3(?�5��h��+r��S9k�������S�N1�Q+�������]JWF}]�g�
#�P��S�:?�F����;�_H�p�I����a��:���&8�|=�56�_�*���>�o��Q���.�E�cx����s�\�V�^���(�l�!k��Z�)U�����u�rEy���Rk�V�u.a4���5�#67q-�+�����N��F�&�,wr�>J�*�V�q�.E��������m�����3VM[g�&cJ8�����b���?��kFB������oo���,�g�q��n�(���02#�����7>.�s������n�/�z�����C�c���Q>p+�o���.fQ�^^���O%���>��^��c���Rk���u}y�XN����eJ��J���*�����?�g�z��%�!f����e�\��/��{�����]�����77
�gK#Ls�^�DV@;?��8�w��X ���>L�����5G0���2��.���A���e�uY����&�(�)!S�����" �]2��a�w8!m*�u	�����:��4"$-J}��4�{)5��vq-@?��M�v������+�-Cn���t������L
(��y�:��vK0�������<��*�M�M�@�?�y`�G
)b�=G���"����������+C�w������~p�����P����o�J�[(920�iqgB��U���6��)w^�a1��.�K`���/JN�Z���k�i������<S����h9?�
?#\�;,���������L�Q�XSM�Jy����U4����\�%�[�U�`�)���>
kG���Jw�e�r������L.�2�y��qq��v�q����7�3�Q���BB�p��<��#M!a^�d��SH���$�y��|
�����7�GmN������������\!�9�;�1X/1��#B4���I��������B�/;��v^�aZS� ����;���cv�c���C���S���D?�u�>t��QK� �����?���1t<n��/Oe#VZ*�C:���S���`%u"ux�#nMM�M�XT��!7��[���O����H����H���0�������H����h��x��x;���4�N��#m�p�G���5-���j4,��.��� �����H��;�H�����i�_Z����A+j�Uc�bmN���WXIt�HEt]$����E*
T"�.��%{,V�~�����?�����`nE�������hM'��j�;"@*�����:�f��\�1�CtBg���J����L��C4C��z�\�y*�NYT��"����	�h,�"���&�fV��
R �"���&�R����v6����-��l�����Ym���H�� m}�L�8�08g���j���C*��"m5pKd��N���d���q%�StA�"����cG����*�;&D���0�&�O���D*����h"�����,*�a� 4�[�~cD���*���&�2�X�r��vx��� �[�"�pn��H��
��+Q	XT&���/�=�AsN0��:�p
	��`U�P
X-�T8ks���JZD*b�"Y�}_"j��r�"X[�s[z!�!��%��^}����&w�^�;�D/�c�����^�S����CB�����^��^8)�&^�����}b^������	<M���=_u�v���s;����2�X�U/����[�'��P����p�7�*<�XT/���x�������J/��z��"������X-�^��^f�zD*z�"H{������/�U�B�����������N�v�����^�?v�M4o/�W�1!za?�CV�6�"�+{YH�!!q@���*��z�^�������}�	�hK���*$�m�&
3)!��\��u��x��+$@�"$������dw�����B���W�6��^��B�p	@���,
!���
��`�)�HEH��t�<!�aU!q���n�V�)�|M����q�'�N��k{�7��P�c���~���s�c����,�x�-``��P��s�s�Eg��@���@���������!,�������� 4���W=tn�c������H�7��?�..����t8�L��]����t8������J��z��"9b�s��w�CX-��Vd;7�T���Hwoq=��C����T/�8��/	�)7�������]������U�wL�^��s7u��������L�h���^���zay���/1�.�`��^8���O��,������:6��^��^8���H������ �^8���
�/���_/��z��"9bC0�����������T���H_�
��V���[���<?�������#"��������^8`��l�~�q���t�F������J�!�_�I�]oA��A8d�7���@D/�.z���%�E/�)�pr�����lFzEZ����#�]rV��'w8�_n�ZP�^@;\��Er�6�^fY�X�����]J�(������
b�p��_��z�~��4F��b�������
�]����#l�w����;&D/��t�F�&|�?E*z��Gl���������za��}�z$�ZK�������&�z�K���^8��_�]�� R��v8N�{�-z���s;�������}��U/P$���kA���X���O��T��E�b�A���V��M���B�1��n���.za����7��s�~t��VH�HEH�����M����"$� ����C6z�����JH���Bb|>������R�B����.��d!!"!qn��K_��
	,*$��p�����
!v�
���!��-JEH`��B�\��	��/�T��U��E��n���X�s�:�v�hW�;vZ�=_Y��}�g����/~�@�������-)�s�������%�ps(J������V��������0O�7�Ue��@���L�1����Na�R%�_��e�O�,_+�{���*U>iS!"_���|����!�J�������@,y
���\��4y����klt:�aU>|�!�
#����Y'�i��j�������cAPN|�t���TR|������E���\	�A�T)Qi0����^�",�����>����W�}.Z��4�6�Y����l�E�
����~��aU�}.V�{����0�!.�!��O^��{�J!�`���O�*�A�
Aa�����	�0t0��/��'���?D���o��[@��`-u�|-�JV��h
u�|z��B�� u? �������P���6��+���
u�
V�W�Hu?��_�[�;�U��U�������[�O)a+J��r���.:=�NYB�� (u? �x����P��!8w�Ea�Ve���� M��,D�/��W~
��2�|�"X{��j���� ����g����`�e���~U�|.��K�{�2���"X{�0{�
{������1���/���{��=O�0fly9<Kv�(w���`!P��;�N�L�1����N��Re�/��U6���c������%d������P�k�<�|B����F[c-����t�K���k ���I"�N��_�Pn�2�S����rY�F��������`�%-���r���
Sp��ny�����d��Cv���Ia���y	s,�r}�y��=���������n/t��P����yd{��r�xXj�]����a���o���o��#�����5qH
�h�����p5��|����}K><����Gq���q��qx���
endstream
endobj
14 0 obj
<</Filter /FlateDecode
/Length 5283>> stream
x��]����q}�_��,�7Q�3���v�plF&@���"�ZbQ�f��{���w�J�UjE��c��~�����~������$���B����#����~���������������}���_��;����u
��*����[���`�c
�98o-,�X�G�$
-�VF3AXK�^l)0���vR���:�N�;�����}�Y
&7�������+�f���z����R��$��S)PL���������t@)�w@�(%��R`����p�~�)�%D��������09 d���JA]F���[J,�>�-%�I?�Vk""e��B����e�6�a��;��,jz�m��X�%�:��r!����		�t7a�]�/	�R�n&9.?(F�� �L���P
f"1���O��~�K�����P����L�����O��}�0�-�sH�Q��3��� �6M����t)i��.E)��(��B5`
t)J�f�P�>V�����Fo��dB
4W����~��>������s)�T'XR��� ���]J�fA�KQ
t)J�f�P
�]�R��(T������B
4W��pN�	�]�(���$����,���
��z�R�3;�\�R�KQ
3�j��R���D�:=z'���+������������Yf�+.�@s�t�OG���\H���������P��Z�����I����Af"2A��(TB����E�:}?�� ��[�Z��Z��5n�(�ywb��Z�&g�oBt�,�q<���hv��@��h&
��)��(��Buz����G���)oB
5W�M��Jy��z�	)�\Y��h�P��F��A�R�B]�R��(T�P��j&
�����B��{�o
��r��V�Q5)���~
)�\Y��0��$�P�� ��(���P3Q�L�.E)�L��C�����+����PA���p�U{����h��h3�.�I����f"4A��(TB���E�:}��.��iU��1��r�Z��_O2�����pE�C�yb��r*�H�%dZ��Bu��28X�����2���$�=��A����������OaTNy���$�
���[��dQ5�7gq��4�.�7!(CfUFkMcX�o�,��<��
p��r�U����~�9��@5���."L����r�+��"�N=����r'�L9]��Wc �Z�~��d��<9r�:}����r����:�����;!�4W����/mU�RN3e�������UB�j����`����e���hHZj9��RVse���s%e.���F+j��8k%���#c�%;���B���(w�����r�����F<�+W�	���uI�)_�z4��s7�����+C!��Or!�+S��������2����	�TV�(S�j�(\���u'�L�^�)S9�t}X!$O.�e��|\�jB��*!�i�X�'�#�n�����g������*T
(��hi���5��LH�C�5��	������+w���&+S�9g�b�)�*!�r5r����Z�f2��
q/
I�x�r����`��S�c��&`�2!fs�=qPe6?������M�#w�g�Z7 ����&]'=8nr4?TB�_]->1�d�u,q�������L�\����)+���G��w�B*!�%7;-�4�.`m2�)/����.��8}%���#C����BN�JHy�GN���`G��e��L5�W�^]��3e$S\R�H�'��e��<����zE.�L-����������f�3�_��6?~�����C/���{|��xn���M�~���F�I�y��~������������~2zUF��5`�������'*}���~���Mz^�`^Z�t�	�y��U�	m�veZ����e�]�����.�q��-�����'q���;�B�A����l������x�R����<��`��V������3�= U�<���E��97�Vz��l�5�Q�I���x ��+�c
�9�}��a��SN/�?��B
����q*����0v��_����y����B�8�l��k
y�V�R��X��!�]��%G�aV[*5��VQ-@?l�+�'���Sf*?�2��3Sy�����,�h�Y��6+3d3��oi����&�<�<?��t��3�T�b�u��M.ny�Y8��������!�>/2Y~9=���~i�,����U*N�P�g�P�WwB������f��)wY�a.2�.��&�~����[��Ut�<mfv�����g�/�N�-�M��;��W����@?�M�4C������WT&�����W�D�ZR�~�/2�t%��<7���mX;��g���(�������O���o�
�1q�&A��\��[h�rO����,�^�eS��M�8Cl�w�����bD��S���'����?���&��{m	9���c5p�)dQK��%�;��CL!�F(uA��k�=�������p�%���N!�;��d����wq�5���>�r�C���7(X�}��y0NOn�n�v��K&#��c?�Q��;�eu��Z����	�������M���v������bk���� Qv����t��OU��=%C��GK�!Y����rv�%�0B�����d~h�[���C���{K�����W����~�<Z�L!����Y2�d�^��n��S�?3s6��S#1�~�u4B`#q�����T/����B�����Nh]_��5�y��2VF��}�D�[.E��3K-���^��f��0��[r}��DZ��k� ����?��2@����0�&�&#XI����C��3���� 5�Ef-�����)'�.���"��������p����#V���Nx/�h��8f��<@>����-s@���;���s��e.@>���;���1���;����fr^A��kp�*!�)�����-r���-���	?o�%��#�p! ���]�!���5PH�eX��_���[�M���v�KA�.�>"��>d��}��V�����R}M��n�!��a%
?H�5���kc-]Z}D��������A���r�h��N�����]�D~t����N *?�Z�E��[5�E�Ecu�.o
��d�i=�?�\^j;r�{m?�������������l"qy! �����M�Yb%.�����.F�����������N�������^����!������z��������`=�V�N�������y7�"/����8A��r���.@.?����2'��	�=qy�`qj)����\~��3�v����\^j;r����\~3}k$���?o��M4����K!�?H�&��g)�M��eX��_��
./�S�����#.���C./ q�A��='���r�{��	����o+�\^������'�i��t������n����8��{�9SvY�����z	Uk��m��)� .hf}o���]����8��4��y@Z}�lZ�s���8��[�c=��+jI6����Q��Ul;�$�[YjQKr��G���n�<��-!s���
	!Q�q�%���>U!,�#>Z2�G��D}���3�����.�[2��%����$�
�-��,���|g�a��?�v�=���BN]��N�<�*uv���w?
vBN�]� N8}C�Xsp�]uP����3���G\��#k���c���.Y�?o��sB:}/����x�^���yH�����f�����N���N��Dtz�Z:�b#�<�����k�����@Y�\���X?��B������G�����./�b��;�E������GwA�V+d�2'3�	W1sm������Mt�u���G_��gf~�����w���/��]��Jy}Q(������D��X��_���l������������2���(�w���P���T_�s���"���N��C./�>���a���0�����[
��K]����.�m�:��(Nx���~._j�E�]>b��
j|�Ul;r�{m?�����U�,���R@���z/�8��2���/�z���lqya���h�!�������������!���^l��\^���� ����=��������y7��e�@\~t'H��K]�\~t�nB./sq�A�����7����� v&F�,���f{���?�*����������%��v_�#��� �?
��,�pG�)Q��HB|�|5�V^VuD�o���W���G�}��;��.������/;VK�����u�����z����������v�{����5�< �>��7]�]�]�$�c8�E�wsv�����O{7����A���ab�+�Z�����eo<h}�����	H�eX���7��)�"U>���O���0�h��E���&����w��7��a�"K{����I�X��H�GwAo�#a�9�� 9�nb��
'j~A���
�Bn.9��A���#���]��|�����\�"��C��$���vZ��]_�B�}���A���o����uk���D��H����7����C�k����F��o`E�����ad���C$�{�����"i7�|[���� �U���z%�}����u���I1����e!'�}��x�������Q\�|[����8��;A�o�YO�/������A��3}/[�|[���X�����������U�L��X������f�^j�D|V�T>Jd�W�F��(X{�I �R�������^3bE"~3�&�eH����D����[��d�_���(W�K�� ���@��\�$����������a�{�xL��3_�.BJ,|��Eo!N��c�������)�[�6yv���'T�z� Q��(��EQ%�=���7��e8�b��S��D���u�;����)���XG�V"7���.�[���z�������E. b=F�xoj'�6�4k�l��F�y��e�;��V��eX�Z����n-D���^���z�0d�2�D��c}�D���D�7/��	y����,����*Z�"E�=R!��a%�=V)�+1�A��^�"�,Q�{�6_w#�7"E���^��&R��q!V"��\xO?�S`��6��l`1G�y��;����3����
Qx���D��/��_�j<d
tH����,�..k=��[���v����8�th9�&�6�U�_�9��#��Z��"iyt�'�Xl���t&7���p������E��\:s3v��X��]�C+��������>�?���q��p���R
endstream
endobj
16 0 obj
<</Filter /FlateDecode
/Length 5440>> stream
x��]Q���m~�_1��X�dY@Q���&�I��&��M�?P�"gF�uF\{���=�f�c��GR�(�s�����������_>��c
���Ihn������_������~����>�sc�r�������|�A�!�t�6���3p�i���-	nS���ykay�u��O����o�X!�[)��+�"��DqR���z+N��8�������Y
&?�����
�Wp[����N���p���GB����RN	I�g�WB���z��P��(%��Dy}��B�������\]H?��TB f���RP�8+�I��p����B����R�
I�gN�4+���O�MvV
���*m���YJ����R�t����a���a��'��t��+���9!�~�H�B�t7/��$���������AB"�����c!� KQ�N�����*^����B
s���	���.��PY
)��2b0����	�'!�6��mK�h�l�hI!Ez��}�v8��y��R��8B]�0��C-D�� ��a��(V���&$l�f����C])[8`M�tJ��T���sA`�JS���r�*���%�D���F��A�R��+E<!��1x��'D�:}�8��C���Ci>��'!�RN�L��pt\yB�Q�L>Nf	�,pr���"�[�a.%�0�� ���\�0�B�b�K�Y�bu�{����'d�J�w<�����[�W��t���,U)��wZX	9��Fw�����d?���f!�0�Y�buA�A��(V��	��)��=��!�R��u�����I)���2��V�	�C*&Ve�g���B])+B�x�R��8B]�0��C-D�� ��a��(V���+E,Z�1�f<�+!�0K�"�<G�!�0��f��s"�"���fq��a�K�Y�buAs)�0Q�N������Z#����C-���D��h�����c�"Zw!�Z(g
�-�����K!�Z^Y�m<ZH�A�K��a��(V�P�"������Ym�D5�����j�L�*�H��L�r��rne��G�V%�P7��P7�!�Z*��z�ew,$���%G�B-Dj)��!�B���X��i���'n�R�k����c��#XF�n\�Xr(P�B
t��9!�[)�R�V�rd��|R�1[f1a*�K��C��2DW*�.8a�n�1c���$������e�
�%U{�sp_��g��,�b�����+����b
Rwb`6�+u����E���"fh�\/*�����qvz��^����3{�9;+�L�m �����B�N����
wR\����S^��@bnJ���T��R��Q���`gee*F/'>\"+�����3S*bg��{V��T�U�:c�K�!�q��[�����4)�<���J
��	U
9��(�JXD_��%��g)�L��y!����B�y,U�RrX*���Px�$�<�yM0��hA�r�:R�N��"���Y*�n)�==*!���I�G;�=/��sz7�'_Y�B�j��y�B�������Z*�i$���^(����I������Q��#�����nd��Q�JU�>���	�n%�\�����2�Y��BH�*���A3�6�����2O�8�f!�,������������r�),��+�R��W�"X��W����������2��4��G@)�,��1�O��YR��j����B����6���^��'T��]	9��2��y��"�h��$���%����3Z��K?C{��R�-��[����(e������3��5�J�Y-�.����e������2��B������"��T���e$������f���?��{ff8S�������������:����;���&�&�`M|�������yMW��_��g���n���*dZ�f,\9����K)���"��x����'����V�~������u�v�p��9��t���l7���e�2��d��:�
�"������D��O��8Y?�'���AR���\��m�S&��1���_n�������:�����7H"�O��[�L��9m�4�y1w�	GcL�-�@v�n������A�b����v}|�3~���������5N��g�$���B����7Li�v�ey�a,R�u	��9?��k�B.Cg�0e�8�G*5��V1-�~z�
x��/��<Y� cf�����h�i������,
W�X�����I�;�������V.op�r��[	��3@���Z�H_q�f]��W����w���r��4�>�_�ey�_�N&��������y�[��m�JBF�������J�f~�p���n�0�;358t0������<m];O���,���Df���k�2v�~\��B��f};�r8B(Q��������������]k�Lk���T���g�|������������ ������K
��
^c���O�%�C�$���O���������
ff%j41��
!�z�3��q��4��uSC�|��B|BB� >�;��C�_CB-Nf�Gm�9�a��N8���3D�����p��C!�F�� ��9�|	P�Ztp
:��C���6-[\;W�w�i�]@������alf�W��_,�Pg{�o'��z:���K�Z����R��;�ew��-w~2���c�U�����!���;��I��vn:_�s����[.}k} n�n�3E����O�8q�4H����nH�uC'$���m���:9k�7�����S�mt�ros��&I���������N��g����`��
�$�5�u�y�mVt!�f���v�b������B^���jVF�`���z%���dtZ��������6{=J��=';'�VP�d��1s��������?���os��������k
��P�������=����������&3o� h/Qvm�e�����]@��W��1�)(���L�/���C�y�b�H���e���^O���[2e�VQ�`�~��{hj��Mc��+s���( 4C�Kd��k!�\~xz� sy%��G�9��4Z\>q�m	N��nS?2oI�������m�YND�R��y��p��q�O��!`�:w��v����I^�)S�����!�a��Dl#g��:&��V�����������k�_{����y�����t3w��u�2u������&3w]�1q?�)T�n%oW���K!x1m*>�e�:���@s���C�]S�1����������jf�\}w<?_4�gU��km'�~���� ��0]��~�r
�x���]������_L*���|e�~��g��fT�CJc�]Y}L����^jD�^Y������� �H�����,_$��D�u�2���,��v�^�=P&���dv�S�]s$�]�$z��������A�
�F1�A ��$���9�	 �u�M�Fy���T��7�r]~M�-��mL������v1����Y�?n��M���E��t�H�q�4l��N��
����|e���g������/�I�����_��J���,��k]j�I$+�|�CD�)��b> ����I��e��%M���O��e�$�8��s�b�
���&�����G���H�	����.b����$t�;������y���]����u��������;��<���vjb��vjbt��M�q�����!jb�u�wS�*:��W9��)���[e-qKrm-������;�Aji�A]�C�y\�x�-����u�r�q��o}P��y4�)��;��0�w���*u�\��ctT���P�1:�y@���wS�1:�m83���[��Q�^������	^������vb��5��[~
�[���3?��)l��M[I�u�2e?��3��m.p�xO�����\����@@���V��i���J���_[}�-��O�|e.m���7���Kw���\�8���|@����A��f�+���+! .?:��:���Bo�_��v^��y�%A�<�}�3�j�3��Z�3�2]��~���z@�P�'��6���
.��������<�~���}M\^[}��/��].� q�������y�e.q�������J_��_\}�l��/%��������{gl�4�\^���G�0�.�� s��!���G	q�3���d��h-�_����rw2}2�}�#�j���_k��w`>��X~?��SH�t	(��!���:�5 M�����W��'�zi��/��J��>���V�>e��)������V�CD������L�u�2e�����6W
�w��D�������`)�w�+C�������������sd�J����[���vh��u 03�����=U|�3�"�O������Wk9��K-���w�5���>�.��u�;���s�k=^���T]�)3����um��y?&���c���UG4]<f��V]3F�! �:w��_Zu��9�����<e�~i�5����D��������q��J*����p3;?��_D��\q��P.�� `f>8�o�	��R��9���0�Me������}x����W������n!SVzJTyO{WY�+�|e�<��������j�����}����W�a�B�{^�1�X����C�;{a����}tz�x��]9&0g?�!h�y].0������"�����@`J�k9�������u5����Z�������d��xAvJ��^�H��n��pJ{�K�=x8�Z4��_<I���B���  �xekg{������!����=����� ��;�q�,}��
��z���u!�.`��W�=���P0/6�vw:���/+�.��v�a5A������A!�eD�P�@]�( ��w��h!�]�(�����(A�.`?)F��
��'�p���(CN]����� �ZO3�������n���^�+q�Q|��_2���+q�Q��fr���(CN�~x4�j!��~���;�eN��8�( ~�9}��l��ja�%R�]R������ `B)z�{�����c��{���
&��!8��uon"�~wU���������A�]U���zzx����Ob�c��[��y�\}�:���DT]W�������O���Vn���C�����X����(���9�����/�4�%.��u��	�5��
%���d���>d�J�����I��S��:_�w��r+������k�}�Lm7��E��� �|x��r%D��
��}b��u�21���c����|����I���u!gr>H���\`�J��R��]�J_���k�Y������1:��/�_���
�<��]�p��L�K�o������T�/I5�E>5��>kp����R�����������qK\���B�sYlP]g��[��u�biyt�O2���B��o���lop��'x��I[�����������X��D��C���{���8b�����p�>�8���
endstream
endobj
18 0 obj
<</Filter /FlateDecode
/Length 5375>> stream
x��]����q}�����E�x$~v��|��r�� ,���Ujnq��������L�J�ZUE��.mnc��;��n���?���U�?�����o��������n����;�br�����??���m�`Rr���0G�o��
�!Y�i�k��!��'�����f�������4L�����N]P;�V��'���~�[w��0���C��[�2h���#<KZZ��$}|���(eIz����l���,
�,�����XZ�eI��D��B(K�{�)�.���VV�B@���;K�����&�]Z��B`�%�c����*K�{D��W`���G��B�������e�(f��\m$��b�>$���{���5b$��U���:�z�Oe��*ET����Se��jSZ�>������K\x�����6�g^����lW�����sS�J�yH��2r`W����y�4>�j����#����2����=�KK#�j#
��TB�4�+SZ��xi*!V����09�K-�<�N�WF	�rv���X�5Px�ye�Pkg?���yty;;U�WF	�v�"RR��Ou��&�V�H�s��Z^Z�VQ������Z����%�KS	�2����@+g��0�����EB��c�/�K������Q�nii�NmD�[�J���:eJ���-M%t��V�C�t.aQ��H![ ���*�k��F�le"�������: ��LD�6�����f����~�4���d���i.���N�U6���k�mF��)r���q��\C�p8O�����6�t���0O^�yii�YmDa^�J���feJ��0/M%���V�\iEbA���\%��hpV�6������BT|�Q�:.ESbX%��	tN���h�zi*�^�J��)�X�4�@+SZ��<W��G����a��2J�W��j,���suVF	�v.��63,m�@+W$���:YeiZmD�^�J���heJ��@/M%���V��t.�S��H![ {�2T��d��2��Dd+��Miu@"[��lmJ��cd+g"[��j D�>j*>�D�^
�6am��e���P�8V��2�3����1hr}r���\"��yk�%b���4)�]���2�3�����d�1;�,����(�,i\|�-��lY�RTj���+#9�d�ve
G���Q�J;�����U��O���s�2TzAS%�nG��UF����-[����h�6�f��`9�OkXw�d��I�E���M\%��sm$uT�Q�X;�����+����?\�+���X�EU�6Jkg�r/���Q2X9����I0)���2J+g_��j#�2yi��Q2X;���'OM�[��Q2Y;�e2���y���g������U��^��(Yg�sV��x�m�l���z����;#\�Y;�)���&��(��t����XW�^g�K�;��K6+g�<��}]�dxZ@^�$���s�<
����(����x��^E�s�,��2�E7XN��TgZ�~�s����+��<�w|��2rF���O����N����j��)R.~v��J�g�\.:j��{�Hxxe����Pfkg7Z-�
4U���F��O�r[9S����z�d��w�d����_rU�)�kA
��QrU9�����Es��I��\{��T�����
W}a�P}�E2�Wj�����h,�F�P��e�����2���MK��1����k��b�!�_7Z|�����r<��U������� ���v*|}�������1��~���?����O����ss��l,�~�����S�KS�t�o�����?�����8�i���];��a�{4;t��[�u(c��&cM����q���8%�C��'i��L�d28J���9.
>K�\�1��F����yqC�5�urC�����(!�:���;�|6e��c$B�4Vf0�uS����,|�)zo��A�3�7�����&��$�1>>p�]M��(���b��[���!�.��)�:���]>t+6r�:��J3��<R����i���m���SO>�
��Kf�8D�M#3M�r������5b��PnF[���h�����V-o�p�r����`�gSl�-L�Dq��f]������i��_r���<�>�Oa�6��������[#y��<�V�x������L��	��VR6�[����0�e=�����q�%���i���y���fa7'��2;��=���S��3����!�>h&���)Wf�E� �Y�\QM�Hy�y~�d���5 �:A��T�a�3�X�a�c��o��ABa
�=(���4����A�67�Ix�Ly:&A�|>�;Z�=���d�O�_l
���!.�;��)��� c���B|fN�����)���YK�	���Ts�0�k~�B�	%C �!�;����Bh�� ��1�����Qv"mp;_v
!�<��4���:��9�iw"�Osv�2����~@���X�ae���������:���%� �����?v���:�������X6b�%�q?��(��.vB
��vN��N���U�:��:<����&�7 M��H���\�)Sz.��>P����g�[����I����5p�tW�ou��H7)K���zz����

#A��}D����������g��
-v@��m��z�Xs�j���Z��b���1��G���dEi1��bW��u
DS��T,��NB�$����9�Lto����/��1�����zt����8`���h���/��	p��H�����w�1!��"����!��F�
���
���4&M�
��lL[Zz�����
oN�j���9K��+|R��@�V�qr�oh)�Wz� 	,=N�p���4�dGK��Yz�$��hNt��V�`.���
�����*���6��U������U��+�D/������SX�q�^����-ou��Y,�9�I4g�_^j�;"��~@H���G�\[�����~�@����@���	�)@z��"���t����U���S+�I��l�P�E"�Z����Z�)
�����n��{f5��>�(ypje��n���~C`�-�`��Us�.K`y ��T���Ne��dap*��G+{�B*��H���>���W�Do�O���"���Y�;�?lDJ+�&�*�~HH���<{���h)���=D)<��fu�� �`?	H�$�y����<�jvX�.��
�]Vf���\$�����l�U��"e�pn�7�6�������	�V8N~����
�p@��z�`Y)`� R�\����ky�����E��r��0�".���ZW����7{��!s4��)zA���:v���~���IZ�X��X���Z����Ta
Xa�KAs]
�OIe=+�Q�I@������]�ElQ�� 
c??�(�uW���\����0�=Ya����8����zC>k��� 
��
�I��#u��(��Ea�$@_�i(,Da\+�0@��0�E��aPa`XEa����`����F>���S��;RGrz�s���'
�������������?�C��x}��9J�!�+
I�HY����n<]��F����$������F;�"�!��EP�o{d������WB="e=t�������[�Xa$�:����J��������5t@��dT+j�QC��{�RQC RVC�"�x{I�E���`�U~���l������Dn?�)ot�����k�����*�!������jD�j��G���OM�^�T�F����$������qYe��
�pn�ww�U-`!�pn��}�~Z���������$m���j#A���~ 	������E/�$G�����s�X.�^8�1Oy�HY/\i��i�����`��*��)�����sL�)���'>�
������t�=t�O���@B�	�V�zE�A��l.�d}��DM@������@X/@�!�{�����YX���Y/�\���`�Y/�\����/��B�V�p��>���B$�@X/�\�8	�R�~]o�h��^8"I��W�`.�^8k3��{gQ�U/|5�U/�XY/\+���D_�<�|�#}03��������^�?�C��~���&����y���|���)�����7�����Z�F����$��7��X�.z��
���C.z��
��}fK�"e�pn����l��h��� z��
�I��P|}?Z��H�3�mg�������`E�GB��^�����X/`XE/\+�����4��	���3E���m����FG�ba���N�������j�;"���n@H�_�~�0�,������!������(����C����D�%
�l	�Vv�:{�P�E"�Z�x���{&@�,N�l��;��>�(ypje���������q�?A�x�{�,�"
NE�_�2�p�0�Z8Y@HE\i���[��\������i�s�N��>?��L����-O\�>���8F�4�W'�7J�R�}�o�n�1�S�:	�� ��h�~?
�~--7�X��[�jX�]�r�~���vp_�a����a�>�Wi��Z����J�}�����~Q5� ��_��>�i�/���WcJ�>�a�v�}RD:�9�3��E����0��1�C�:	���t� ��_���R�#A:��$�z��F�Z������"+�������V:t���/�^-�:�U:��`���@:t���C?�������t��b��w�l�A���_)��j V��/������o��>�q7f~,y]�D�{6��6H��G��������~������[I�~�N=Ms��Y��
�����6Y��/?�!�6JA���n���r�����~-d��OF{�7���~�d�_���o�Hk�}2R�����6�����`E�@�3�Mi���s�3x��.z�n4k�
Q ��~
��h�6_����V��9������(�F{7?c]�Y��V��,��d�F����b_#��������J����r�����b�x�����*���H�]��
�����V�1��X_i��$����a�S��ul�����57�V�������D��A��*����t���a���\��5�����C�m1Y���c��]��1)���"�[c������^Hs�t���=�+k��J|��K�Q��!_)�"cX�G>+�"d�u��L����q���N�ac���1�~%�3���4���[FC��k�%��M�$�z�L�.��1�!�X��x�����~=�)����@�s�l�c��[��u�K����x��n�-<��&����F0|�7�����P��Q����p%�&Q�Ycx��~$���.x���%z���o��O�����
endstream
endobj
2 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 8 0 R
/StructParents 0
/Parent 19 0 R>>
endobj
9 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 10 0 R
/StructParents 1
/Parent 19 0 R>>
endobj
11 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 12 0 R
/StructParents 2
/Parent 19 0 R>>
endobj
13 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 14 0 R
/StructParents 3
/Parent 19 0 R>>
endobj
15 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 16 0 R
/StructParents 4
/Parent 19 0 R>>
endobj
17 0 obj
<</Type /Page
/Resources <</ProcSet [/PDF /Text /ImageB /ImageC /ImageI]
/ExtGState <</G3 3 0 R
/G6 6 0 R
/G7 7 0 R>>
/Font <</F4 4 0 R
/F5 5 0 R>>>>
/MediaBox [0 0 842 596]
/Contents 18 0 R
/StructParents 5
/Parent 19 0 R>>
endobj
19 0 obj
<</Type /Pages
/Count 6
/Kids [2 0 R 9 0 R 11 0 R 13 0 R 15 0 R 17 0 R]>>
endobj
20 0 obj
<</h.8wjxpup23wkz [2 0 R /XYZ 72 524 0]
/h.qbh9ygvjk8eh [9 0 R /XYZ 72 524 0]
/h.yn2prqby1c1a [11 0 R /XYZ 72 524 0]
/h.89zc5wk356xl [13 0 R /XYZ 72 524 0]
/h.v4nh6p4vfucj [15 0 R /XYZ 72 524 0]
/h.bnc1b7mrxtvv [17 0 R /XYZ 72 524 0]>>
endobj
21 0 obj
<</Type /Catalog
/Pages 19 0 R
/Dests 20 0 R>>
endobj
22 0 obj
<</Length1 28852
/Filter /FlateDecode
/Length 16123>> stream
x���xE�?|�����3�s�L2��d�I�B "i ��_L�H"��\�(�\ETtWtE]/��2����*��(�.�^AEEwQ�EV2�S5�$+��~��|������S�>Uu�����S����"�4���L���+��1f��mzc�i��qL�� Q��STr�o���?�������������L��0�>.T`��_4y�"�q�_��/��N�?}�Kj7X�0~������#����2}��i�#��@�+zM�1e��<�r=6�4��0cj�����X9���f`���1��F��1w���W��a{��9�&7�c��a�����ZY������S����������k\+�uH�a��N��{t�>���?b��`�!�����
�-�1]�"��=��:���X+�"����6*����oRxJ�c"O1A7<u
�u���s@��p�lPgL�v!�s]j{���m�]��$[��O~���v}}d�?o�0]��Qc�Fv�4��i<	8����'�b<	\�'�+�$0
F#��''0��X� k��
�XLF�*�
�����fI���_�x���#@�z���iEz���f�uv{5���FD�B���J��S��U�K(�0��L�������E���`!�����/���Lx�D��G�����	��-k�I�;{�B����r�=���~q�\,�f`��_��~y�,:�3u�������������zZ�_���_;�����O��3��[����M��8���H���0�4�]��)XaF�P����G���%���(�����:%p*���3���Z���sY�<XK`>r�0�b�t.	�1�C{i*��TL��L�k����%XCw<Ul�^�/k���H3l��x��:�$���5����D���i#N�n�%�2y�3����!����I�0�1�cHO�
���a��Oe��_��]������]��;���c��w\�g��d�>+P�*;��^	�l���n�aH�=>1�3���p�]�f�N�|v�_�����	�'3�y�/��x��-�*�a���R�
�B���)w�8�F����_����(���a��
n���!��W�V��]+��(1#Qz�&W��GktL�������XM�����'�)�%��f���x�}��[�C������c�~�v���Pw	�E9� ��$6=�3� e�0j�08L���>�$^�T���.�@.?�}3`�&=����;��F,u=4�<[�x�����'c����y��?�$�����X����������Gx������u%:MwS�]���Q��g��/�?��x.��c����Xo���	I'EdO��y�Qa!Z�B��SP��D|>&����-�w���sRf���G$�<�'b�'UI#��%���t}�~*�F�,�Y��O}
Z�����O� ��(r5�A��U�>��&G�I��������a���8O�'�W������m5m��n�g�$�����[�<�O�����<�1+�*�"���x�J�&O�Md3i�Z��O�W�{�9G�xR�f�,��g�.�7���G�[x���?	iB�z
B�0[�JX��v�1]|K�a?����6�6�~�{QwZ���������](��q��������%�	�;>�)?��������h�B9���w����#Wb�L"��r#���dy���d/��_���f��6w�=�:�k�T������z��,��`�B�0D��
��%�:!*�!|$|*���MbP��bD"N����M����\2Is��R�������~�~��N�~��]C=J�K�vv����� a;�C{�>�&}�yL�Q�T���Ao!-4Gw����%�����>H7����0�T�10�v��&��g�R!�����lob�7J2��~+��L�=&/�bDx����8| �H9E�F�� ���@���AX@n��t�"�kP���g�.�%%�G=R:��L�~������� �"N�{�Y
_���]t�I���Fg�����7����A���I��A����3�[�	>����E� O�F����JX[��Z��g22r��h��
%b^��U��6mj�n���a��E���bZ�
x>�vBD	��:~Z�7�EK[a��J����~�m4L�=
�c����������R,q|��&���f�[�9�+u��[����t5}����:�/�v.���x�#���\-��@elM�/(��ha���p����k�\�=�������||�c0*�L,HL0#6F�^xJ��}�8J���{3L��c���m3���^����G�s�6p���Ze��*��)�]���GI���n]#]����9��,5��g���i����+6�E6����J�pPhp�
�G�p�����x�:$�GUL��'��s6�3������S�sj)N��P��PR���Bj+�0����B�j���qz-�-Hge�
� ��*5J��A���g�T_��m5��N5u-��&3�f��i��[IZ?�	�6��V��-��hz�jP��b-�
���DG��T���U��0JN]����-�Y` �&*
��y5�L�4p���p��5�
\[����4L��

��{�����t����kVu��V��TYt��Uj��Q5s���bx/�\�z0V�;�z�����5Q��T�����?��� �R?K�CB3V����I_��K�����]���>H]=�&����6T���`��%�|������p�b�w�V�-A�����T�8;��G�z�����@D��*��&��������zrod����]�)8"3������>,����*!u��:���)
�)W���$%j�����H�����~ �)�����Z����B�/�}0����OvV��Z5�#��Q5��
�f4�V���z��?���r��9���C(�-�wG
����x��f����=5�_=&T=jB�:hu}�o��v���{��T�9�F��	�f<�rb��Ej����?���V����upT��<���������iv����hf�O�s�o�x����l0N��c'�^m�����ph��ck���Q���������,�fD5�����/���vb�H��x0��Z8
����C�����ZcM��T%�z}���z�������v�����j��JAa���c�V��1fB�.@�clM3%t`����9�W�K�x*e�,�ET�j��L
�?c���sE����[	�4C2���VOS�i��x�����l���5���dmW>����z�����L��P�RG2I�>O�����@Jd1R����7���O)�?/�8cw�,f���"'�-�8�_�����v���#e�$�-��RG2���.Y�!Y>�K�bf,_�&�mm/��:.Rh{;:��o+����������Y��.)^���d�����S�E
moG���,����:��5��J"�������Lj����|0^�)=���5y��D�;�����d��^N{;:�d�V��&�k��������:�I��r�.Q>�����2�v�V�L�$����WR�E}��/�v������W��v�S�FG�H&�wd\�|{�|RfV[��Y��D~�W�����|K����J�;+�ir��d�����%�w%�gw��ev;��������:�I���K��x�awYYm�7t�����������4�����d��.�-k*)'�S�V�H&�w^�vt>/�Gv��uh���^�I���-�:�I9��t�D����c&R&y���4�������dR^{9E�(_M���r2i�����%����37u\��e�(��r}gwy�YK�,��;�?0��.H����r.�D����>v���j��\sE�D�)��n��"�t��/�Gv����� &�N��Nq��Hit��������d������&�kS����#���y�d���x�awe���;���B���7xd���c�B��Hfp��'d6�
j�Bh��]b��UP��*��"����>��{�$0]A\��	��0�������a���8�2�T��	>���N�MH�o1�0D,�0�$�b��A�|,e�e�a8�s4!���������e��9%<��N���mW����F��UC�l}�l�K�����y���#���]M����=���
��H���&�1�
QT�)����.��O�T 0���i��K��h�~�2���S�zj��^����S��a�~��'�XF��>G����>oa��D��y����`�A�J�0l������#D�~��i]����>��6�>R����i�4�����D�(AsDZF�pxJZ�������F��#dC?�!d7�v�
�����V��65|�1}���FT0�Fb��0���Q��B�����R��`P�!o`8
�4#1��f��������o�Wp�	���U~}��������^x=D6�������(xU�Z��:��m9�`������"a��0�$�b��>��<%��B��!� �������	h��Zx 
�� ��2�6��T�[�Q�{�G�A��5H1��)�9��b�2)�	��b1)�V�����`���D�o�7`/���t��
 ��	?��m7`�m�"]
�M�I�^�4�4=A����[I�r�TA��!M��'M����=�7vE�Z:E�5/i:D��'M��)L�rISiRI��J������A���?S:�^����fa�f��g�M�����i��f��}v��VP�w�S2����%��%����%������b%�I�c�C������{9��0Tb��a�o1H�9�b�0/��-�aE�F�`1���ED��2�Q.��[����<�>;�{+������Z���H����w�k�{�������{����A�(u��$�����{���������kI�<�fkw+�kG�'���W�V��I���_�V�4��)��|�g���V��
���V9�.����8�r�����]vo�	�������k1�������cyU�k�Z#��#X��&X�����,�&D�d6���W
�����Z�~��F?B�K_�/�g���L}��ep�� L�*�����j��"����?"a�0	��V(�����(zQ�PM�� ������Z5zvL���FM��BH�Q
�cD{G�[�����HuT?������S��QzG+��5�$��Vd���]@�}��������Z�zWz+�����.�	���Ntft]��������F�2k���f��������]�;v���%�#����~U����d<��|�|(1�q>N��TC ��!����#_� �Hs9_����D���6������y�Th�<�ijG�C�����y<Mp���41�h?���#K��YH:�9���s���,E	�;S,w�������X�'y,��'��SD"d[�����s}h�T�����F��U���k����k'�`����������P������dOd�}CU[a���5['jS���j}��j�
YZ���;Su���Ha#Ya���!e�.c�CX]e��2V�m������j��'�������Z��U;�������o�������ls�6*�D-XV��]��,�)�eeoY�[�fe�&�Y
&�C ������;hfU���&-��ux#��:0oPTk�j\�>t�`Lu�r����z=���G��I����Zc����0�K�#K�`iFc����}�:�iA���h�k�h�z,ES06���})6=4��6�iL��hv$�8�gN�E�'�D_,J\�w�-��.I��"�[��C��C'��������~4��Wj�60�1v��&���Q�D+GX�!���jGt��ND7�9\B�����E�|��t:����tD?�L�@�?���U�D�B��'�1��#�~�s!1��O\���!��8F /v����]9v��"� CW���?���b(B,������tG,����4�_P���D���z!^e���7b%���
� �����q �wP�!�~���2v���x9�G
��X
��*�a08�-�8� ���G���7��d8�@��S0�!��xG�����p$��Sp5�Bz"�A�����p��b�z��W!^��5L�Z�)0q*\�8
&����g@�L�&vfA=��9����p-�_��q�Sb_�����#6r\3b_��0q1�B��s�f#.���7�u�7s\
�o�������	X��	��"����{���v�+�����nD\K������c��jX�x��)k?���V�{`���q-�q�nC�~��k�=v~��X��V!>w`�C��`=���V�>���.�G`
�o9>
� n�{����#~O�}������_#>��}O���X��	D���Yx����9x�y��G��o��(�V���6"n��[���{�~�����Dl��w����9��M�{as���<��G�������9�?���/�_�-��p��/���_� �W��U�{^��C��u����D<��o�.��8���o�^�?��w��?���G���>���?�6�����E���%����?��?����+�#p��qx-�|�?��?�x�@�#~o"~	Gbo�I�_���_��c�����?8��w����7�[�+�i���������G<���0�:����	#��x~�c�?�q�s�	�y����k�'c�9������m�w��6����M��6��_������_����o��)����M��6�3n�?��M����O;��O�M����O;��O~a��s�~������6����l���k���������t?�?��_�O�_���6��6����t���!�F`�Ld��������W���5����
�C�F�;h���*�A��Lk}k��CzF{�b��\^��������G{�F0�� ���YH��������� �w��s���tD�%���m����X��qid/q�/�j�7���;u��r*O]8�T(����Q^���n�[�����h�I�.�Hz����k���,��4�$vRNR��AR��P��-�!+����CP�� �����"Ib9�s���Q�q��Pv�dKn��GI���a�� �y7<�n���+Wl%�k'�� d�����b�*����N'������~� yy��w7.�pO�������{��e�B,zx�"��^����8N��B��fW9m�}����B����
���
�&�$����l� n�	��B���n�^����}J�"7{��k�j|���b��})�u�q���6�b�ey�8�l6'��Njv�yY\�0�`�fF��0~F�X,��%�6��^a���#5Sz@��K�on���8Fh>�);�,<��(�4(��9�pE��T�����/K:�%I��/Z,N|���f���Pd�!KK�^f���k�t3U�D�����`�����*z���kV�Qo��A�+�W�f�uNtO������m��������XBo��o�����S^��O�JG���S�e�e=���-����Qs�NJk4jY��b#�b����"?�0�
�����,�n`��F���5oU�}��9��8�s���+w1������Bdd�N&:��-@���A0txq���TL�=�BQ��N���]	�������<��y��Y�<����vm^�t��[�^QG�!"���I��b�������C;�o���4�Af}3s%{vE�J�	���L��s4�'���Sp4��t����K���DbIG����2��0�^�LNk�x��� �����\��\��\�p�5���piI�u��:V����#�N�Q����T���WN`�����v�*+������'�%�KV�.I���z����Z��3��O��7�[���C����X����=j�
=�F��T(��^���hW,^�Sga2c�s���(H\���4������9�=m����djJKS���R5������C�H%�%L�h�B����B�h��d=�5��I�\,����E��2Y���{�b�1�d���xeZ������>i���k~�P�Vk�-O�����y�c�����3N����;�4C�+�J@���N����W#�pz��$��?������h?
�~�PZ���F����x��'��m��������jb�����1�^��d]�����d��J:�����Hw��������Mwf���U\��y�����da��[�����~��!������-Lhb�;+\����:�lI��+1#Iz����e4-�w������!��?������y�������_1y��>�6����v������<���;�3
�B���EH����|kB����6��<������%d���0���~1����b	Yd���CU����0/��E��.b'8�++��p�OT:�������,� �J�8�~�}q�0�3G������������ug�S�N���e�U����1e_��!�_�ZHO|���M�����:l���bGr�)[�h���S��e*�6����$�>��os�&V����NvWxmWo+���{��&�q>���S6zma+�?!�%���H]�,_8������%.+hYP:������8�<	WMqY�L�=C@�e|K�����<qK�+]sc��Y3��Z������fO�r����G�#���_�m���G���L�������Lo�2��n�������[HG���v������@���=���"q��&\�h��s�:n�%���i��7p��Q�'.�!��:��Q�Q�h��5�y��Y~M�])\i��(8P�A���d�8�X,��%�`*[D����aA�<��@���V:m�Ng�2�����a�{�����VR�Y�Zv�T���S��F�2�-�R�
U�@���$N�`����V����?����3L�+�/>m(g*�V���I����l6n�B���������G����\33+X�(���d�\.7�,��p����k�rn;jS^n�"�B�Iz�{�Cv�N������������d�S���W<��8��.�fv���Y��!@�kN'NG37�I13���hi�rr���Q�&�Dq&F9����h���fL|�;[�]@��-�{��j
��~���6Q�-Vz/N�����Xlra�i���he��������cu��������8_���d�N�� ]0����qB��(N���t��\V��j������!��1+�Zm��$��&�w�)��E����')��e�����F������W�Ro��x�����'���y����/f\���K'�RW|���Pg����*C��E��g��	��P���A#��rg	hh������������������o���wa�����O��>���������GTz�w��-��v��W�k>�,�0�/7�C�P@�]�~��}coMj��I"/)F��e��'�\�87��S1��$r���� �DpE��,�bA/&C�pYL�
��/O�@��d*��hi|y��XK~���rR��N)��lu��#Uz�]��R'8����)�)�Y�)�"��������w=v��6/n3$�08�1*�g�YF�R�X���r��b;3�;�wleSZ���M8�=7�E�I��MIVn��%K!����<������B�l�5g�ku��7��VR�eW�MJ���,ML���4��ivo���4���l��V�y�����Oj|2�nJ�_��
�h�p�A��<����l&s0O'�
v���k��A�s���Cg��?�Z����7���������](q���O>q�M��c����������m����S��j��l����T�lm��m��=��s�G�X`�f=`!"��A4���M1%�Q�4
e9��|M���(L��P��yd.�|��2W��-�v��p�,[-�u9����q���3�-� �C���a���S��l�����N����<��h;�����k��#l�gj��&
BP,���R=��a�7�;��l/��5��uI��p;;_�gsM����<�%�x]y��*�a�����dsK�O��y�K�����G]�3��v3�"CF��Xq�B�u���
H����`�88���Dl�F0��%���6��2�L.$���N9n���y�n��������l�r��<���7DJ6D�7����%'�D�,
��Z6Kd��;�|�q�'m�deX)J4 �Y)��!]<C=C�_�_������,���[nJ�V�5�J�r���J��io�:�h>��j:��j�tU������2� c3�F:�t���f$��7���}Fb�M�C$�I2ER�&�h�T�566�Fm��>�W����
��ocT B+���sxf����9���B\ukn�^������'4��q&5���gGy�D�Q%l
���.��u����p��~_�yLq�:������?��}���=w��mg�{���}���=c������g��1�7=��g��.�z��c�M{�K��;����������q��&M^u�����#�n���M��8����6T���7�|��k:����*{���x&��\7�8���$w��R��Q��}-��2���@Ov�t�i�s�kG��,�oo|���i-�	���%��7W�^{a���Y��V�ju�HB�B����q��G�l
��@����%|�P��6*l�����FD�F�{|Zw��\�/Qk�������i�}���h��=W��	s<s���nJ�%�&��������_{�P����<�z��}�L�h�C�[�,UR�#���k�gU�wF�����`R��I�	&wy��I9��f��,���6�����M\[�<-
].�\�r
�����#�f����Nz�3uB��r�35�- u��9���=K��,�W@�q��va�p%�������a�-#{�^{��8O��=u�M�=���������y�-��1�M�]��o�e������cD���Y��m_�m��>���Y�S5��p��
��v�7��@D������������P��v�43�z�|c��W�_��<�Q��<����Z��eL_v��@AA�.��PB���(_m�or���k�y���&T�/�\&���I�$1A��U7�����467YZG?���d���e?+M6�2d6g����BlO���*��T{�g�2p"���s���R|���w;�"}'zS;�u��t8��oH����+(�pez��76$�7�v={��:l<Xi�d�����!\s��19a�:��z���+����Ok�~M.[������=���{Mx��>cX���nw����<�#oo�������v��aC�u9��^�={��%|�!����i�l(0c�P��e�{��:�`������H��Vi>�d���d���f+��d�X�����}?�`\f��@��L����N�-��P��r��~�y�5'�v �#�W�Tp8�uq���b�9����Z���%��Q�	��� �}�Y59Jmt��j��P���J�/dP�x��"�B/�#9St�K@eEE�a��O��������\4� .�W��bW�C��6���k)��W��-7ZWYf�3�[zYG�jWI�a�V�Ct��N���IxF/9��j-�Q�NG
8��H����D#�F�'(�Ua�T�hrP�n�	���u���t�<��d�M&�
�j�231���3r�V��$�+#�(���
QZ�����^��t�t�6{�Zo���������t�r
c��'����={��:��S��[�U�X���.���:jS
��P���s(�G����W0�:*c^>��
��ZM,5�����rka��QVn-)����������.\P�����A�$��^e$����?Dr���_O\�������V��}���.��p������z��������b?pC&yTK����s���8�<U���g�j6����'|$���������=�����bwG_w�����Q����������������W�Y��Fz�=�=��o[�<��TE������>�v��q����p(8�?������^A��k;��5
;�C����F��9
L�-�(c^Ai�B,�8����.e���\�$�a��D��P�6�����gV%G������z!����o?U��`�0D?�]oe���s���f�/PZ���I]��cF��-�Dp��4�|R����\qaA�XI������$-�P�)�.}wTI_NK�5����U�����_���?ij^1y����(���;�n&��~�B�D 2�o���'E��{y`��O3I����h����3��r�8J�	��	�:����"��LF���!G���#�|�$$	]���/�Z*���%�z�$n�$�q�fF������������Q�~�1�i��A�|c�qc"��1f4��^��Q��t���J@�I�I���@�(>&F���qQ�/�)��xc��,(�V$~���V�D&���/���gr�Yd�	�Nq�a������h\X�7�+*OER�K��_���g�n���~GKK�����:����g��*t��@�����S'HN�IiU>�t��:%��	�fK��<������jpY]�_�'��b�Xek�'�&���� &k�Wc=������\�b=afo�|V�}b���N3���u
�����Ml��a�������U3���{����*�zO{�|�c��w�W�
�������5�������v{�'J���1��c"�Y���)�|j���*u`+N�6T`_�0<�{��#�Q��P0�SF�����������E�P\�y$��d0�M�����5��L���r�r���m��w<i7Zt�R��m_����?>R1�����1���A����r����nn�������qZ�<y���n�������'����������H��K����L��T�������T;�=��u���:G�g�w�n�q�2�1�3�{q%��ja�n��jy�0U7�4G6��E��o6���J.�\��q�s�d���\t��W�z/��J"�4�f8��0�o����'p���--��+z�t�np�c$�q�e�i+++k�V��q���\:�9g_ �L^��������}��mQ��n��3�����$���;���,�/4�\�^������]kqb�~��o�Bb���6E��w�������������je��������������~	�������B!^��q��k���DIH,�c�i�"Q2�
F����- ��/��1���U'q��N��?W���_S�UU�������I�s���}�?-��wL
���;��l��vB�;���H�R���j�����}�����+vZ����@�Y�D���W_�o�����b����y&oHe���b�+c'���3�Z����G��o%�D��&|��I�$��$��{��-�3]�+���
cU�����K��o�y�����1-��V\]x4M��+���w�a�q�i�y�<�2�0�8�4�<K�ei	�����9y9]z�L0������/
-�i�������(~��Y�]�����/�=�����$J9I"��R���CI��D��}���O0���&1]
�Es���V����+dC�U�F�&�����I6_�7�w�'}�����7��������+��W�B�(�2p��S�}A�j/%����9�4����������Er~�Bs21����t�������v{OfY|�825����|*�����||���6��c��^
���;���S�m��) �NvA�C���^����y��cVJA:oAz��%�KheIS	-anm��$�KR��O���X���Y�T.�j��[Eo�M�[�l�
��q�p��������c@*a�)_��Z�`X�%D����|����/z���Z����S�G<���^����p^���B:Wa��8�"H�5������pa4�����E6t1e��<�I��T2��>j��_|D�/_���3�����'���#��p^7���}F�'N}|�t����q�l��y��{������{�7��&��r����<�����=8~��[�z�\���pj�e!on�����,�F.�y�w���e!��������6^��c��b�I�pe�w]�3���d;9�^�%weuq��r���[�5s�����$%v�~�����{��!v$3�=����kJ�k���bb�|���#OG��DC*#��lJ�gy������I�?�������W}�t�?����~�����^�: %��x�G$�7����r<c�5�i���e�x�d�h��d3��"��8�N�h�&�I�_�`/Y+G+���<������3���]L�
���{��]��x�+&	��Z3�Jf^���vsJEI6:����A��F���P�)��~C�9��\}�!b-���>���*a������mC�W8���v��O1Lw,�n�/2��v�v8~�����|���Y�my�"Wo(s�`XixHxP~�l���O��a�����xTz�xR<i��qF���7K��2G��U��	��%��2LV���Ao���r��\�^�9�G�2�
Yh.)`�����)b+�6M���/�����&Q��#>0�]]���?�?WN�3nG������Jz��h2P�M���&�z�h�j�L6���]oP�v�#���t:��9�buY,V��������b[�E�_d�;D��.[-�y�,z=�Dr�lV+�\g����4YK+�~M��gZf��V:N3���y�evjg1��#�����#��vr�yv���ag���h!���������������lm��M���;G�/(�����U�`��,TG�cjZ,������8�k�H�T����7b����1|���V=�����1��|��;�U��S���]��8�`�h	�4��Y��������*<u_��;����*�����7Yc��p�C!T��N�U�\�F���|��]���Ez8�z�9HH�Hu����+��wm�y��-m-{6w�����	�!z���^?L��{�.�~�-���p]��j�������M#3��mO|I����)%*YP�m���E�l����is[��\b��H_��:q�a�u�m�n��_���h�<�������+=I�rr��P��J����k���L�w�V�U�!����_�o[>P>79�:j��a�y-���VF�$�0���7p�dE���4I���H�Q'
��fSpACl6�b&`�� +&�Fm&� 4R%�.�@--��+.YLF� P	}Y�q��*g�l
��V��J2vj�H�I�V:P����4{v�P����d�:\H��R>W������Z�������J�6�*�8��i@��"![-Vof����9�\�N+0�xsV��?w����r��/O�O-__��R�� �G�8-C
e����m�?�]7a�����G����>m_�|�����=����$W����Y?�m��
JR:���y��KB7GG�������-�8G|9���Q������Q�(��&�M0~��!�%����fMVB�+����=��S�����4����'6�[s������-&A�h8�j~q��@/���g���,��^����vs�#�y���Q��u�t�t�t/�[��or��^aYm_�X�����i�y��������K���O��?�]����mU��m���j~|%�H�
Z��&+h�M �\Ng�����MF��k6�B��t8d�,����i����[i�v���j�c5s�Cs�I�}�h%v�H6�0�,�[�*�#da������l�7��%C]��;����QZ���W9s���U��t�r�S���{Jt
(�x��O�������V������q���`��$m�+����rSvY9:c'����������e\P����"�<����m��C��e/s�-��<�������Q$;���mN�����K��oV�s2f�2����_�t1�}��-j�_��?j��Z
endstream
endobj
23 0 obj
<</Type /FontDescriptor
/FontName /AAAAAA+ArialMT
/Flags 4
/Ascent 905.27344
/Descent -211.91406
/StemV 45.898438
/CapHeight 715.82031
/ItalicAngle 0
/FontBBox [-664.55078 -324.70703 2000 1005.85938]
/FontFile2 22 0 R>>
endobj
24 0 obj
<</Type /Font
/FontDescriptor 23 0 R
/BaseFont /AAAAAA+ArialMT
/Subtype /CIDFontType2
/CIDToGIDMap /Identity
/CIDSystemInfo <</Registry (Adobe)
/Ordering (Identity)
/Supplement 0>>
/W [0 [750] 8 [889.16016] 18 [277.83203] 19 28 556.15234 37 [666.99219] 48 [833.00781] 72 [556.15234 0 0 0 222.16797] 81 82 556.15234 85 [333.00781] 90 [722.16797]]
/DW 500>>
endobj
25 0 obj
<</Filter /FlateDecode
/Length 291>> stream
x�]Q�n�0}�W��{���MBH]%v��>�&��4B��`3&-Rb�����>�F{��� ��i����$�o��$��_��o�����G�}m�A@���w3�Nj����^�B��
v�Up3Y��=�(KP��L��}i{��d�Z����>h��EH	'������ZsCQ���P\�)�/��������!��8�K�fAYJ�>ft&�1����b�HU�|�o���$%Z���B�<!�s���N.������N��k1N��n��6:99�F��q-���m��.���	��
endstream
endobj
4 0 obj
<</Type /Font
/Subtype /Type0
/BaseFont /AAAAAA+ArialMT
/Encoding /Identity-H
/DescendantFonts [24 0 R]
/ToUnicode 25 0 R>>
endobj
26 0 obj
<</Length1 20588
/Filter /FlateDecode
/Length 11691>> stream
x��|	|T�����{g��Y�l��d��L2�L6����NL�H �!�E�F\��j���Ke��N�Z��km]�-.�hQ�����3������{}��un��l�{��������I��A��1�UTC"���Uc&M�������tLo3u��=���$����Ss�����9(?���5u�6.>��`��i���z�����M�WyF|�^ ����X�l��e��{0}t���+�	2����,X�v��5w+��^�S�-[�������fa��y�7LF�P�p!f�/`z�S.[���.�v���[�ty�����;���������Y!l0M�c�s��e�����Q�0o���+WE���/e�+Z�W��jZ`��z�	�
f ���.g�7P
3@��
��t�5��+�DN�=������F�M�r��g>�q��xA�HboC�x�Mk[��kAk�p-l��
��sV]���m�3��f�J���kx����d��I��8�a��1��V��g����,?����A�2�L����*�8	�"N�Kg�L^���	��nU>$�������QQ�Z���T��y�S3q�D�kTo�]J����#����qn��n6 ���9���o��:-�{KGA%��	�V�*X���W�y5�����D"����/�D�q��L�w�����v�m������%��({!��er-��[Q}Xx
L�3"�c�����Hy0vE��P+���O��zN]-
�������Z��j]^/����.�~�e\{����li1����/bq����0�,�
cq�vb,����V��9��pNW��"�������+1�.G{
�h��(s�)�?<�$�c�Z��f^�K`���l��/��0~^�!���+e���B^�?�T��V�3����^g������`�|~����1d#\�8%Q%������6��s�`��f]XNK�����a���w���Jq%,�{1����P�+�0��/g�x�WFN�>>�i�	�����S�H/�P<���K���B�S�?ca������oy���������<��;a^��G�n��Y��p��B�c��`7��$O���6�-���K����(l �t������N���x��V�^���T��qm% �M���/��D�#TN��H�'~����o3���s�,�������}��*��](���{x3�/����^Aw/��G��`+����;���p%�����h��<K>��=}�����#������#�.|'��|����J\����>'�����U�*����������}���xea����jQ?�Q�3�'idK��Ed9C%Z�{�n�����*�
��������.���,�������	u��}n<�9.����t
\[q����^�	���.�����	�����������'K��9@� ��7i�C���
>a����
q��R|���������#�"_DzQ�n�yj4w�fly3�wa���>��
���W����Bl�AR�`�ErH!�D&�dYE��k��d���CB�{�y��G>#��7�T3�Qu��I�h6�@�-t}��O��:}����O?�_��`�+E�c�K�Y�ra��V�Zx�yD8.�8&1]�&> �_O�?�t��U��~��X����z�z�z������]I�&K�����������4�B��v��\1~
o�g�#�G��G�$� ��',~I�PU�
���H
��FV��`"��4<NE�G$��)\I���F4�K���^�J|S�	�C��`����q^FFbl��B���������2�����t,%������$�3)��m-���U����:�3��Z�K����U0_��5��N�����B{�&i	���	��|B�C
����&���Z���qa�0�Z���Dp�`?��Wa��"�"����`]�
O���~r��@X��\CEr��G�S+����/��g�^��}�r9�-R�������	��B11�r���z��~
E����}�=b<���p����t�Qp]�O��ci�oF{�#���������e�\1���
I:rj
,��$�� i<a+�rL��"?tGM��Q:|XIq�����!�9�Y�������i����������w:��6������N+k$�
g��J_U�'�o�~���Y,���s.�hy0��b�����y.�����F%��$��)���LO��z���	���0~S�������<a����Ox*�+<!���U�^�V�X��������fmV&�ku�a,���h'���G��rX;:��U������*XBBZ��y�I��*+�����)o��
�ot��"P��	��Co���
n��gj�V`nc@?�7o����0���a`�!����I��R^�����������mm[<�]��.,�2���:�Y�V��V�MocZt�`GX��P��j�U��������[���'���)k�.W�+r\���iu>o�,�W?�"��mS�v�=��de�+��6���XDo�0�|����8�UO9�N�z��f�4y�'u>H1��bhk*F1��|*4�aQH.olS��|�|H���<m�N�����s��r�i�����8������PF��'�8���fe��B�
���&��c��rP�^/���A������u���&t@0'P�������tV��l���}h���ji��~LJ��r�����7G�����'���T�5�t[=��T���\Y,���		4�	/EK�uN�%��!1
�����%
�"�!����86��Z�w��#��S<8�X���a����/J_�=}����z���6�EeU�;mmU>OU[c��pd�\�G��u��m+*��h8�}cB�j[=b!��Jat��l��$[����R���uZ]%��qt}{*��uy�<���e)KA5AK��^����KE���Ma<Os6�@S�F����,��i�O�?M H�v���to�b�ca���u�-yG�����A���[�\��x��[���tlg�{:f��s���M,_������Pk����h����vwV�a���y����!�tj6��NO�a�&������������'E�m���;]	y���~�����w����-�%���"rk��q#���8�p4�J?g�s<�q��e'r\��������$^�����$�&
nEn�$A7�BGQ�Q��%Lt��w�����w�g�;C7��3�����fT���2a/&\��&&�>������r��ud�w���0�Ys�x�������~���$Z}��}&+Lj;�?�������$hu��}����I���K�/e<��B��;�awXD�]a�H����=;w�����}��-�b�����3�uHo��oe��y�]��aBw�7�����y����C���l7o.3���h��Y��{6��[�tO7��h������=��������������\iG��# �H�v$I6�E�h��F��h�QC����#���f��^ j����q�y�_Q��x�	Y�jZ=u4�j�����wS}a�E�P�F������v���a)2%T�I�f��rs=���V\����$�emN`{s�j���X�|S}=��.s�YF�K�*�������>���v�,�uJ�&�brK�`IgR����u����Cy,I���6�3��H�VVt������K�$�UNa�BfE}}5N
�C���=����eL�4�p9�D�|\�.*����y.�K&�ar,@9�qH�r�����w�*+�}��uus��h]�R.�v����Ep�����P.Ru^$+&�}N$��$��2����sV��Z
��<:�\�leR]�F�����8e�H>����$t���I����E�O�
ee��RJr����$���p����n�^.��lC�(kT�(V��������9��M�&{cE
f�����j��g���s?+c�+b�*�eL�����.I��YU�c^��<��29����R�)����rL����L2�M������l�B
�Z�1�OTN�u�fo�$
{I�^C���Z����cD��z�<��5�j�Ka�����%V�N��h������~9V-�_�o�X�xa����d�
�~������#E���o�(�4bt��Q���?|tL����@#�"��r�z�~���_�_�/��JU����e��&�f���>�~���~��t*���Y���Z�Q#��nVP?Vi2��7���^���y�^��5e�!;m���}��@���?	�� ��`0�F��EAM&��P?�������0�L���g2�@6��ZQ�I���oEEZc�;��I�E�(�\Q��4�%�j���t�j�Np�'�X,����O��-�S�v�Rob���1�q����������[�~3����JKN@������������Z����l��AoEQ�4��@�����|��I�������@O�hG�q�J�����FE������I8\.�����w�\`r�h
�4/�?����TV-[c��I�'&Y����`�G�T���������eK7kP	����d�����d�$�� ������Uf�j����O"��Q<�����$�SV^�7������7[gP���DJZ�5-���(--
�RPtH
@�����}(d�`klDa��{F����G�B����#P@)���nEi����l�Q�����������Y5���h�k(�k��������w��3�����w6��g��Z=������]:uly������C��7E�E�V���J��S����]A��Dz�y���E��QzD�M`DT@A4#���n��A�� ���h������8D'�xp �������� !�$C"��=������nDxS���)���>�A����q0�E���# 1�c�|�����\�DY�y���9����XC� ��K8���04��R�8��H(B,�b� �|
�8����)�����������@q,�B��G#VC9�x�D��*�	'��I0q2��|	S8N�K"=0
���x�Z��|���:��X�gp�	�g�T���x��0=�94���s�q.�&������f��8f!.���e���q	��0q�E��"��r�+`^�Sh�f�V�����*X�x,B\
K����F>���q\����U�q��|WC�Fh���M��X�x-\�x�F���pe�/p=�A�k�r��#��U�?���q���j��ac�O�6!��x\�x+\9��f��9��G�� ��x~��.��nhC�%��xlC�������G��#����F�����~�q7����nG|�@�w">��a��#pW�}x�F�
�������^��
��c�����q?��x�G|���1D�]������ �S��ix�x� <��G��� >����X�8�"���!��;hG|:_�N��`?��p�<��
<y^�0�Q�B|������<y������6<y~��C���Gx�]x.���E|���<���;������p��qx�O�2����_8��W?�W#��'p4r>��?��Wx�sx#�*������o#~	�G�
�A<��k��7�.�����+p����>�w�A�|F^���G�?�1��8���O{���}���`��Oq��s��sz
�t�E��=�����!fr�����grN�����9='r9�a!2�i��!���O��8}�(�������5���9��9���S��OqN?5`N��s���������9��sz����=��{8�������~�s�I��'9��9�s���sN��s����?���9����-���s�b��K8�/���l���9}%��U��u���3��?����s������p�����pN?�9���#���pN?�9���#�q���p�i���9�����O���������9���9�m��oqN�s�[���0���9�
��opN����rN?�9�(������rN?����)���6_	.i��I�
j�hQ��0��/�Vb��5j+� ��Ny�3���]io��tiMo)�a\�	aH���5�!�?F��#�)���x�C�}�[�J��-aW�J�VS�F#�d�^Tk�z����T���SO���,�m���zQL�M(�L�@E�*k�*u�<4J�(
h������WN���Ta�i�WYi1;J�%%[�[6���lP���������QRJ�(����H��'x�����`���o����$)#�x5y�������tY���W��3���#4�uk��Gg.Hd6�-���&b�P���$!���!9i��x%�
��=^B�)��(�th\��)J�HA�	w'
U���&;9�����P�3A����"�'��J/��p��X��44�����H�vU�%�/-?���]�C���>�L�G�wN[�p���<}���}���u��?���1w������_�������{�,��K����q������j����ppD����4����:��-�A/�rl�j�'_A���djeo�4�s�&�0���J%��s�b<�$����dB���J/�UK�7	JI`��q�4`<'��F��8�>�?}��DTE�Q�����J������T��uFP[�W���H������Fa����b��>U��}���=��W�y/��p{PVTD&e*�
Gu�3
x���08�f/���M'TH
�� ������W�d���k���G��;/iC�
��
8���
hH.>�S�O��$��}G��������_'�	��t�B�H*��1��Jg�fZ�
��E�%�"�"�r�"�r�Z�F�
�fs��!�-�\	;]�\�]M������+G�Y���F�z�e4]b�=��� :h4������-���r����.0E�w=��"�@����	�JE��F���F�I1��V��n�s8���F��	G�;U�'L��S�HT�J��m��b�`�l��U�l���d�����8�6�AE��T6����$���[�f�N�Mg�����0����}����������)����y�J6�������`�Q)0��v��������c:A��*sQ��Z��zY��M��v�h���T�.���Tt���Q��F\$������o`��*���SZ�eZ��L%Zv(�`"�
��"��R`ub����T�l f(1B���Puab�x�_���z\0-
�hh�8Ga���ZhUK���S�A���=I���o��>{����������&�;�����'��W��c}�{�����F	�^���-?����Ck5��ZISp�*a�j�Q(1���7)�A�"�<�j�j�z�A���%�IQf�UQ���[mz�.Y+���*C�Dqs�8����4Co5(3h�A���7����K/S�����Y��^F���&�Jar}p0������j]��d��Np��5+9�=>������Cl	G�j]Mt^�:Vb��uy	�</��slZ�O������W�����
/����=�x��)��C�6'�C6�V�E��o�����������}���9��@��������p���e?V	�?����6����|&��#��-�-�$�����k�sA��F3���H�J^���Q�mq��r9��u�)�8UGRs����}F��uR�[�A���JN�<�?�TF�H��I���n|<]���!�������J�	6���������Z`I����K~�/E��a\~^��=Pqf�o��F����AV^�l��5uu�&�Y_x��K��I����onm�����[���^��|���n���G���88�l$?YP��xa�>lx�(�mI�%�}��R��� 9�����j�kU�H���^MFk/���&�M�C�[�LF��Mu�W�u�W�l�r�.�h
�����G����H����>@C���l��x3�)��]�\�
�@ZL��y>���8���K1�k����|i�Wk~��f���r3_�~��?�7j���ww{�92j�A:}���o������y������]�����g�C]x?������A�cZ�cZQ�����1^t��qQ	�?/��L���-.�,$�@��)	R���Q�$��d����4����P�E����-���l����1�0)��c������Q�D�#�n�o�mh9�w ��^
0Simi`��P���s�b�����oTYjaR�������_�k?�/���ohj���J���KV$�,�}������1;�xe�w���]G�%����WI����� ~\��H:�+��Y��TN��Z��{d,��83�A����l4���@����h$F�Ll4S��FDA�Z�*��JAV����*.�dq:9���aj����lCRZ�|s�e:��'�F��u�s"�LD�h��{Z��N��a)Q^�TJi)���Lk-��1���hZS�$�K>������s;�W6U^��5rh���r���
wo��e���_9�6�n�i>���}��?CJ�|�������y������!�!Tt������MCUi���4��f/�R�g�t8���tC�3>��u �;H*�v����7��m�3��Nw�jw����������-���A���&�kq����8�4m���(&��g��x�W�eZdz�-Hw(Z��@���z��
-���z>Vz��A�����(������m�xbA��:�Ak=������qn1*�5QO������F��|�+�(_0���Zm��-��=�	��6d���9���v���G���FK��w|�G6o����=yyE}h�-KF_����<r�9nz����=�v���~����CO/�qJ<����f�����_���e��V Mg�$��#�D�z�:i�q�Js��Es�,-��i��2?�y��u���t6���R����q�����X�j	=d0�E�������
Q9�Pf�hx� *�������k�!����]3�w�����)��0�}��6^&�p_68jG�w���Z��7\|z����J���<�l�|�]��W2F~Z���T��0�":FQ��}�������Y?��s��-Ic+�v4g��m����ol-���&z�����:_�+F���$��3$��>(�N�T�Ve�v��).�(o�_���#���������HT%!�J�O$6���t�V��tQ�Z���EY�ZCa:��M��"�:S�x��!bLq1�Z�9�|V�1X�]����ebpdOuV����Q^���#��%�F���h����6&�4��:��e}I����(FT{b-[4��v
���|�X�R������Gb�������3�1.G/srOQe&�AY[�3�I����/�>���w��{,e_��u��V3�x�e�qc�Z&)��PM��J��dc�hP
���fd0��~	0�����s{l��!n��d���6��e���jKs���z=�}u�;����&o
6�l��)`U��&K�w��\���V���r�@��:�����=���X��E�:z�7��"D�����9��(=�-��?��1��8z�����!�K����������5�lh�l����y�c��[��K'�m�-=p�2�����)�D����E��k��uHK�4�LmZA������W���s������Q	���
NJ��J�GS5��JSK/���k5k��"
��y�l�TT���sTJV���Q���
�1�&}A3��z�����(E�':�u
A$'r�����#����QG��;h�`n������A�
�83���4PV
x�sr��i�1MT��g������H��4���{�5�����>���w����e��]1|c����9CG���>��<��������5]`�]w*��	�A2iLY�B���-Y�����&������rY����w�K�/���������`VN����i�$H+S�������������
GfU�����
+b��Hz�O�����:y{�Ww^ud���������o�|�����6R���S�<�������r�/s��i��c��{^c�!O�-�������)��Z�2���j�}��R�1�����lS�^$��TJ8r*8��^�!�;�������w�:�����d�����x��L�$5�c���������6���`�=.p�vQW�z���6,�7���z��/CJ:{�)�##/p(H�ah�����S
��v$��f�����~LG��q�A �L��s� !�2���$�Aw�mS~����v�\����Z}��k+W7��[�z��9������	���]�=j��������ft
3Q�&8\/���in�E�!��G���W�GA���b1)�c�Zr�c;t�d:�
�qPS�	YUe�c_���we$6�e�D��a��pUE���
ov�����=K���o����Oxw�l��6��(��!��:�<�H����u��@����}�j���R���.�]YS��R8�����/�����_=ho��}=}�l���N@}e�7t&<9�#�tb(0�7#?7���'EX-���C�s��c�a�1�^&U��������=�JX���2���_�^��uB�T���7�
��v����=X��	�w��d���L�<�y"��T�����x MI�i�����������q$����g�K�%Ps���DF[{��Z����a��(!fv���ue	Gk?����O�X�oD��v4Lv�m�P���^S�fMjZ����+^���b�����f%ox��v�[��\C��&\^�8*'#c}���c���u��qEm^��U8�`��1s�L���Kz�j/�`k0��|�j��/�wY�C��?���B�7�E�i���,�L���t(�,���4��V'��4���J�M@cM��K�DcU��� ������N�������Q��u<b����YO���9�����E;HE���d��K���k�'m/zmrGr�zGZF�m����W�����������X�Ia1��M�����S��D:8~L�����M����Z7;7���o�T�L������3o��:�@1�f�^�3���3��r�����������a��NMZ-���&���nr�y���m~���p�,u�n�::�����������y�&fo���lB2�O�i3�-5��|��~�����7~Bes�'���/q���J�1���U���\�����������%sS
-������%{�e=�����$����\+�3�{��ih^���?<�.���}���>_������5�����/_�%������a{�\����[�=�����6�b��� S�<�<��V:nV����e
/P�q2*M��F���T���F����&��������QV���$A�j-n�&< �Wk�t�7�����	4MR7M5�u2_��)!�
,�-���
��-~�p�tZ":wQ����+�kR�J�6�FC�E��a�0c������|��:��|��]��:y<(����((�y�>B�qI�|B|����@��}����t��a�h�qqJ��0M����![{?���+��m�o����
endstream
endobj
27 0 obj
<</Type /FontDescriptor
/FontName /BAAAAA+Arial-ItalicMT
/Flags 68
/Ascent 905.27344
/Descent -211.91406
/StemV 129.882813
/CapHeight 715.82031
/ItalicAngle -12
/FontBBox [-517.08984 -324.70703 1358.88672 997.55859]
/FontFile2 26 0 R>>
endobj
28 0 obj
<</Type /Font
/FontDescriptor 27 0 R
/BaseFont /BAAAAA+Arial-ItalicMT
/Subtype /CIDFontType2
/CIDToGIDMap /Identity
/CIDSystemInfo <</Registry (Adobe)
/Ordering (Identity)
/Supplement 0>>
/W [0 [750] 36 [666.99219 0 0 722.16797 666.99219 0 0 0 277.83203 0 0 0 833.00781 722.16797] 71 72 556.15234 73 [277.83203 556.15234 556.15234 222.16797 0 0 0 833.00781] 81 83 556.15234 85 [333.00781] 87 [277.83203 0 0 722.16797]]
/DW 500>>
endobj
29 0 obj
<</Filter /FlateDecode
/Length 289>> stream
x�]Q�j�0��+t��$�����R����[��8�!_�J�P�
3��e):7�F+���D����yZ�@���4K8H%���-������uv86z�XUD�>;;���$��X�j%Z��p�<���1�8�v���������nD����H�Wn=z���c5<������tm�����G
���������\� �:��y��q�%u@gB����_��	^�'u�iP�y	dV��E���yJ$)��H*]r"OD>Y�mQ#���-�F'k�������A)��m��l������
endstream
endobj
5 0 obj
<</Type /Font
/Subtype /Type0
/BaseFont /BAAAAA+Arial-ItalicMT
/Encoding /Identity-H
/DescendantFonts [28 0 R]
/ToUnicode 29 0 R>>
endobj
xref
0 30
0000000000 65535 f 
0000000015 00000 n 
0000032896 00000 n 
0000000109 00000 n 
0000051925 00000 n 
0000064900 00000 n 
0000000146 00000 n 
0000000232 00000 n 
0000000317 00000 n 
0000033135 00000 n 
0000005707 00000 n 
0000033375 00000 n 
0000011122 00000 n 
0000033616 00000 n 
0000016582 00000 n 
0000033857 00000 n 
0000021937 00000 n 
0000034098 00000 n 
0000027449 00000 n 
0000034339 00000 n 
0000034429 00000 n 
0000034681 00000 n 
0000034744 00000 n 
0000050955 00000 n 
0000051191 00000 n 
0000051563 00000 n 
0000052064 00000 n 
0000063843 00000 n 
0000064095 00000 n 
0000064540 00000 n 
trailer
<</Size 30
/Root 21 0 R
/Info 1 0 R>>
startxref
65046
%%EOF
insert.sqlapplication/sql; name=insert.sqlDownload
#3Tomas Vondra
tomas.vondra@enterprisedb.com
In reply to: Tomas Vondra (#2)
1 attachment(s)
Re: PoC: prefetching index leaf pages (for inserts)

Seems cfbot was not entirely happy about the patch, for two reasons:

1) enable_insert_prefetching definition was inconsistent (different
boot/default values, missing in .conf and so on)

2) stupid bug in execReplication, inserting index entries twice

The attached v3 should fix all of that, I believe.

As for the path forward, I think the prefetching is demonstrably
beneficial. There are cases where it can't help or even harms
performance. I think the success depends on three areas:

(a) reducing the costs of the prefetching - For example right now we
build the index tuples twice (once for prefetch, once for the insert),
but maybe there's a way to do that only once? There are also predicate
indexes, and so on.

(b) being smarter about when to prefetch - For example if we only have
one "prefetchable" index, it's somewhat pointless to prefetch (for
single-row cases). And so on.

(c) not prefetching when already cached - This is somewhat related to
the previous case, but perhaps it'd be cheaper to first check if the
data is already cached. For shared buffers it should not be difficult,
for page cache we could use preadv2 with RWF_NOWAIT flag. The question
is if this is cheap enough to be cheaper than just doing posix_fadvise
(which however only deals with shared buffers).

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Attachments:

0001-insert-prefetch-v3.patchtext/x-patch; charset=UTF-8; name=0001-insert-prefetch-v3.patchDownload
From 5b2c18986422f5dda3cd0dfebd16e22443051d92 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Mon, 6 Nov 2023 17:42:48 +0100
Subject: [PATCH] v3

---
 src/backend/access/brin/brin.c                |   1 +
 src/backend/access/gin/ginutil.c              |   1 +
 src/backend/access/gist/gist.c                |   1 +
 src/backend/access/hash/hash.c                |   1 +
 src/backend/access/index/indexam.c            |  22 ++++
 src/backend/access/nbtree/nbtinsert.c         |  43 +++++++
 src/backend/access/nbtree/nbtree.c            |  21 ++++
 src/backend/access/nbtree/nbtsearch.c         |  95 ++++++++++++++++
 src/backend/access/spgist/spgutils.c          |   1 +
 src/backend/commands/copyfrom.c               |  21 ++++
 src/backend/executor/execIndexing.c           | 106 ++++++++++++++++++
 src/backend/executor/execReplication.c        |  12 ++
 src/backend/executor/nodeModifyTable.c        |  22 ++++
 src/backend/utils/misc/guc_tables.c           |  10 ++
 src/backend/utils/misc/postgresql.conf.sample |   1 +
 src/include/access/amapi.h                    |   8 ++
 src/include/access/genam.h                    |   5 +
 src/include/access/nbtree.h                   |   8 ++
 src/include/executor/executor.h               |   6 +
 src/include/optimizer/cost.h                  |   1 +
 src/test/regress/expected/sysviews.out        |   3 +-
 21 files changed, 388 insertions(+), 1 deletion(-)

diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.c
index 25338a90e29..3b9c22847a8 100644
--- a/src/backend/access/brin/brin.c
+++ b/src/backend/access/brin/brin.c
@@ -117,6 +117,7 @@ brinhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = brinbuild;
 	amroutine->ambuildempty = brinbuildempty;
 	amroutine->aminsert = brininsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = brinbulkdelete;
 	amroutine->amvacuumcleanup = brinvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c
index 7a4cd93f301..666d58a750f 100644
--- a/src/backend/access/gin/ginutil.c
+++ b/src/backend/access/gin/ginutil.c
@@ -64,6 +64,7 @@ ginhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = ginbuild;
 	amroutine->ambuildempty = ginbuildempty;
 	amroutine->aminsert = gininsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = ginbulkdelete;
 	amroutine->amvacuumcleanup = ginvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c
index 8ef5fa03290..3ed72cce448 100644
--- a/src/backend/access/gist/gist.c
+++ b/src/backend/access/gist/gist.c
@@ -86,6 +86,7 @@ gisthandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = gistbuild;
 	amroutine->ambuildempty = gistbuildempty;
 	amroutine->aminsert = gistinsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = gistbulkdelete;
 	amroutine->amvacuumcleanup = gistvacuumcleanup;
 	amroutine->amcanreturn = gistcanreturn;
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c
index 7a025f33cfe..4f92fb4e115 100644
--- a/src/backend/access/hash/hash.c
+++ b/src/backend/access/hash/hash.c
@@ -83,6 +83,7 @@ hashhandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = hashbuild;
 	amroutine->ambuildempty = hashbuildempty;
 	amroutine->aminsert = hashinsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = hashbulkdelete;
 	amroutine->amvacuumcleanup = hashvacuumcleanup;
 	amroutine->amcanreturn = NULL;
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.c
index b25b03f7abc..fac126da421 100644
--- a/src/backend/access/index/indexam.c
+++ b/src/backend/access/index/indexam.c
@@ -63,6 +63,7 @@
 #include "utils/snapmgr.h"
 #include "utils/syscache.h"
 
+bool              enable_insert_prefetch = false;
 
 /* ----------------------------------------------------------------
  *					macros used in index_ routines
@@ -196,6 +197,27 @@ index_insert(Relation indexRelation,
 											 indexInfo);
 }
 
+/* ----------------
+ *		index_prefetch - prefetch index pages for insert
+ * ----------------
+ */
+void
+index_prefetch(Relation indexRelation,
+			   Datum *values,
+			   bool *isnull,
+			   Relation heapRelation,
+			   IndexInfo *indexInfo)
+{
+	RELATION_CHECKS;
+	CHECK_REL_PROCEDURE(amprefetch);
+
+	if (indexRelation->rd_indam->amprefetch == NULL)
+		return;
+
+	indexRelation->rd_indam->amprefetch(indexRelation, values, isnull,
+										heapRelation, indexInfo);
+}
+
 /*
  * index_beginscan - start a scan of an index with amgettuple
  *
diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index 9cff4f29313..7eda2258eef 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -275,6 +275,49 @@ search:
 	return is_unique;
 }
 
+/* XXX simplified version of _bt_doinsert */
+void
+_bt_doprefetch(Relation rel, IndexTuple itup, Relation heapRel)
+{
+	BTInsertStateData insertstate;
+	BTScanInsert itup_key;
+
+	/* we need an insertion scan key to do our search, so build one */
+	itup_key = _bt_mkscankey(rel, itup);
+
+	/*
+	 * Fill in the BTInsertState working area, to track the current page and
+	 * position within the page to insert on.
+	 *
+	 * Note that itemsz is passed down to lower level code that deals with
+	 * inserting the item.  It must be MAXALIGN()'d.  This ensures that space
+	 * accounting code consistently considers the alignment overhead that we
+	 * expect PageAddItem() will add later.  (Actually, index_form_tuple() is
+	 * already conservative about alignment, but we don't rely on that from
+	 * this distance.  Besides, preserving the "true" tuple size in index
+	 * tuple headers for the benefit of nbtsplitloc.c might happen someday.
+	 * Note that heapam does not MAXALIGN() each heap tuple's lp_len field.)
+	 */
+	insertstate.itup = itup;
+	insertstate.itemsz = MAXALIGN(IndexTupleSize(itup));
+	insertstate.itup_key = itup_key;
+	insertstate.bounds_valid = false;
+	insertstate.buf = InvalidBuffer;
+	insertstate.postingoff = 0;
+
+	/*
+	 * Find and lock the leaf page that the tuple should be added to by
+	 * searching from the root page.  insertstate.buf will hold a buffer that
+	 * is locked in exclusive mode afterwards.
+	 *
+	 * XXX Same as _bt_search, but just prefetches the leaf page and then
+	 * releases it. We don't need the stack.
+	 */
+	_bt_prefetch(rel, heapRel, &insertstate);
+
+	pfree(itup_key);
+}
+
 /*
  *	_bt_search_insert() -- _bt_search() wrapper for inserts
  *
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index a88b36a589a..2594dc10f90 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -122,6 +122,7 @@ bthandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = btbuild;
 	amroutine->ambuildempty = btbuildempty;
 	amroutine->aminsert = btinsert;
+	amroutine->amprefetch = btprefetch;
 	amroutine->ambulkdelete = btbulkdelete;
 	amroutine->amvacuumcleanup = btvacuumcleanup;
 	amroutine->amcanreturn = btcanreturn;
@@ -207,6 +208,26 @@ btinsert(Relation rel, Datum *values, bool *isnull,
 	return result;
 }
 
+/*
+ *	btprefetch() -- prefetch pages for insert into the index
+ *
+ *		Descend the tree recursively, find the appropriate location for our
+ *		new tuple, and prefetch the page(s).
+ */
+void
+btprefetch(Relation rel, Datum *values, bool *isnull, Relation heapRel,
+		   IndexInfo *indexInfo)
+{
+	IndexTuple	itup;
+
+	/* generate an index tuple */
+	itup = index_form_tuple(RelationGetDescr(rel), values, isnull);
+
+	_bt_doprefetch(rel, itup, heapRel);
+
+	pfree(itup);
+}
+
 /*
  *	btgettuple() -- Get the next tuple in the scan.
  */
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index efc5284e5b1..eb215c3b246 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -200,6 +200,101 @@ _bt_search(Relation rel, Relation heaprel, BTScanInsert key, Buffer *bufP,
 	return stack_in;
 }
 
+void
+_bt_prefetch(Relation rel, Relation heaprel, BTInsertState insertstate)
+{
+	Buffer		buffer;
+	BTStack		stack_in = NULL;
+	int			access = BT_READ;
+	BTScanInsert	key = insertstate->itup_key;
+
+	/* Get the root page to start with */
+	buffer = _bt_getroot(rel, heaprel, access);
+
+	/* If index is empty, no root page is created. */
+	if (!BufferIsValid(buffer))
+		return;
+
+	/* Loop iterates once per level descended in the tree */
+	for (;;)
+	{
+		Page		page;
+		BTPageOpaque opaque;
+		OffsetNumber offnum;
+		ItemId		itemid;
+		IndexTuple	itup;
+		BlockNumber child;
+		BTStack		new_stack;
+
+		/*
+		 * Race -- the page we just grabbed may have split since we read its
+		 * downlink in its parent page (or the metapage).  If it has, we may
+		 * need to move right to its new sibling.  Do that.
+		 *
+		 * In write-mode, allow _bt_moveright to finish any incomplete splits
+		 * along the way.  Strictly speaking, we'd only need to finish an
+		 * incomplete split on the leaf page we're about to insert to, not on
+		 * any of the upper levels (internal pages with incomplete splits are
+		 * also taken care of in _bt_getstackbuf).  But this is a good
+		 * opportunity to finish splits of internal pages too.
+		 */
+		buffer = _bt_moveright(rel, heaprel, key, buffer,
+							   (access == BT_WRITE), stack_in, access);
+
+		/* if this is a leaf page, we're done */
+		page = BufferGetPage(buffer);
+		opaque = BTPageGetOpaque(page);
+
+		/* we should never see a leaf page here, we only prefetch it */
+		Assert(!P_ISLEAF(opaque));
+
+		/*
+		 * Find the appropriate pivot tuple on this page.  Its downlink points
+		 * to the child page that we're about to descend to.
+		 */
+		offnum = _bt_binsrch(rel, key, buffer);
+		itemid = PageGetItemId(page, offnum);
+		itup = (IndexTuple) PageGetItem(page, itemid);
+		Assert(BTreeTupleIsPivot(itup) || !key->heapkeyspace);
+		child = BTreeTupleGetDownLink(itup);
+
+		/* we should never actually visit a leaf page during prefetching */
+		Assert(!P_ISLEAF(opaque));
+
+		/*
+		 * Page level 1 is lowest non-leaf page level prior to leaves.  So, if
+		 * we're on the level 1 and asked to lock leaf page in write mode,
+		 * then lock next page in write mode, because it must be a leaf.
+		 */
+		if (opaque->btpo_level == 1)
+		{
+			PrefetchBuffer(rel, MAIN_FORKNUM, child);
+			break;
+		}
+
+		/*
+		 * We need to save the location of the pivot tuple we chose in a new
+		 * stack entry for this page/level.  If caller ends up splitting a
+		 * page one level down, it usually ends up inserting a new pivot
+		 * tuple/downlink immediately after the location recorded here.
+		 */
+		new_stack = (BTStack) palloc(sizeof(BTStackData));
+		new_stack->bts_blkno = BufferGetBlockNumber(buffer);
+		new_stack->bts_offset = offnum;
+		new_stack->bts_parent = stack_in;
+
+		/* drop the read lock on the page, then acquire one on its child */
+		buffer = _bt_relandgetbuf(rel, buffer, child, access);
+
+		/* okay, all set to move down a level */
+		stack_in = new_stack;
+	}
+
+	_bt_relbuf(rel, buffer);
+
+	_bt_freestack(stack_in);
+}
+
 /*
  *	_bt_moveright() -- move right in the btree if necessary.
  *
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c
index c112e1e5dd4..5dba71c6e42 100644
--- a/src/backend/access/spgist/spgutils.c
+++ b/src/backend/access/spgist/spgutils.c
@@ -70,6 +70,7 @@ spghandler(PG_FUNCTION_ARGS)
 	amroutine->ambuild = spgbuild;
 	amroutine->ambuildempty = spgbuildempty;
 	amroutine->aminsert = spginsert;
+	amroutine->amprefetch = NULL;
 	amroutine->ambulkdelete = spgbulkdelete;
 	amroutine->amvacuumcleanup = spgvacuumcleanup;
 	amroutine->amcanreturn = spgcanreturn;
diff --git a/src/backend/commands/copyfrom.c b/src/backend/commands/copyfrom.c
index cec80baceaf..03093778691 100644
--- a/src/backend/commands/copyfrom.c
+++ b/src/backend/commands/copyfrom.c
@@ -421,6 +421,16 @@ CopyMultiInsertBufferFlush(CopyMultiInsertInfo *miinfo,
 						   buffer->bistate);
 		MemoryContextSwitchTo(oldcontext);
 
+		for (i = 0; i < nused; i++)
+		{
+			if (resultRelInfo->ri_NumIndices > 0)
+			{
+				ExecInsertPrefetchIndexes(resultRelInfo,
+										  buffer->slots[i], estate, false,
+										  false, NULL, NIL, false);
+			}
+		}
+
 		for (i = 0; i < nused; i++)
 		{
 			/*
@@ -1242,6 +1252,16 @@ CopyFrom(CopyFromState cstate)
 										   myslot, mycid, ti_options, bistate);
 
 						if (resultRelInfo->ri_NumIndices > 0)
+						{
+							ExecInsertPrefetchIndexes(resultRelInfo,
+													  myslot,
+													  estate,
+													  false,
+													  false,
+													  NULL,
+													  NIL,
+													  false);
+
 							recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 																   myslot,
 																   estate,
@@ -1250,6 +1270,7 @@ CopyFrom(CopyFromState cstate)
 																   NULL,
 																   NIL,
 																   false);
+						}
 					}
 
 					/* AFTER ROW INSERT Triggers */
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index 384b39839a0..a83450c8dae 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -113,6 +113,7 @@
 #include "catalog/index.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
+#include "optimizer/cost.h"
 #include "storage/lmgr.h"
 #include "utils/snapmgr.h"
 
@@ -252,6 +253,111 @@ ExecCloseIndices(ResultRelInfo *resultRelInfo)
 	 */
 }
 
+void
+ExecInsertPrefetchIndexes(ResultRelInfo *resultRelInfo,
+						  TupleTableSlot *slot,
+						  EState *estate,
+						  bool update,
+						  bool noDupErr,
+						  bool *specConflict,
+						  List *arbiterIndexes,
+						  bool onlySummarizing)
+{
+	int			i;
+	int			numIndices;
+	RelationPtr relationDescs;
+	Relation	heapRelation;
+	IndexInfo **indexInfoArray;
+	ExprContext *econtext;
+	Datum		values[INDEX_MAX_KEYS];
+	bool		isnull[INDEX_MAX_KEYS];
+
+	if (!enable_insert_prefetch)
+		return;
+
+	/*
+	 * Get information from the result relation info structure.
+	 */
+	numIndices = resultRelInfo->ri_NumIndices;
+	relationDescs = resultRelInfo->ri_IndexRelationDescs;
+	indexInfoArray = resultRelInfo->ri_IndexRelationInfo;
+	heapRelation = resultRelInfo->ri_RelationDesc;
+
+	/* Sanity check: slot must belong to the same rel as the resultRelInfo. */
+	Assert(slot->tts_tableOid == RelationGetRelid(heapRelation));
+
+	/*
+	 * We will use the EState's per-tuple context for evaluating predicates
+	 * and index expressions (creating it if it's not already there).
+	 */
+	econtext = GetPerTupleExprContext(estate);
+
+	/* Arrange for econtext's scan tuple to be the tuple under test */
+	econtext->ecxt_scantuple = slot;
+
+	/*
+	 * for each index, form and insert the index tuple
+	 */
+	for (i = 0; i < numIndices; i++)
+	{
+		Relation	indexRelation = relationDescs[i];
+		IndexInfo  *indexInfo;
+
+		if (indexRelation == NULL)
+			continue;
+
+		indexInfo = indexInfoArray[i];
+
+		/* If the index is marked as read-only, ignore it */
+		if (!indexInfo->ii_ReadyForInserts)
+			continue;
+
+		/*
+		 * Skip processing of non-summarizing indexes if we only update
+		 * summarizing indexes
+		 */
+		if (onlySummarizing && !indexInfo->ii_Summarizing)
+			continue;
+
+		/* Check for partial index */
+		if (indexInfo->ii_Predicate != NIL)
+		{
+			ExprState  *predicate;
+
+			/*
+			 * If predicate state not set up yet, create it (in the estate's
+			 * per-query context)
+			 */
+			predicate = indexInfo->ii_PredicateState;
+			if (predicate == NULL)
+			{
+				predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate);
+				indexInfo->ii_PredicateState = predicate;
+			}
+
+			/* Skip this index-update if the predicate isn't satisfied */
+			if (!ExecQual(predicate, econtext))
+				continue;
+		}
+
+		/*
+		 * FormIndexDatum fills in its values and isnull parameters with the
+		 * appropriate values for the column(s) of the index.
+		 */
+		FormIndexDatum(indexInfo,
+					   slot,
+					   estate,
+					   values,
+					   isnull);
+
+		index_prefetch(indexRelation,
+					   values,
+					   isnull,
+					   heapRelation,
+					   indexInfo);
+	}
+}
+
 /* ----------------------------------------------------------------
  *		ExecInsertIndexTuples
  *
diff --git a/src/backend/executor/execReplication.c b/src/backend/executor/execReplication.c
index 81f27042bc4..080966b4e90 100644
--- a/src/backend/executor/execReplication.c
+++ b/src/backend/executor/execReplication.c
@@ -532,9 +532,14 @@ ExecSimpleRelationInsert(ResultRelInfo *resultRelInfo,
 		simple_table_tuple_insert(resultRelInfo->ri_RelationDesc, slot);
 
 		if (resultRelInfo->ri_NumIndices > 0)
+		{
+			ExecInsertPrefetchIndexes(resultRelInfo,
+									  slot, estate, false, false,
+									  NULL, NIL, false);
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, false, false,
 												   NULL, NIL, false);
+		}
 
 		/* AFTER ROW INSERT Triggers */
 		ExecARInsertTriggers(estate, resultRelInfo, slot,
@@ -600,10 +605,17 @@ ExecSimpleRelationUpdate(ResultRelInfo *resultRelInfo,
 								  &update_indexes);
 
 		if (resultRelInfo->ri_NumIndices > 0 && (update_indexes != TU_None))
+		{
+			ExecInsertPrefetchIndexes(resultRelInfo,
+									  slot, estate, true, false,
+									  NULL, NIL,
+									  (update_indexes == TU_Summarizing));
+
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, true, false,
 												   NULL, NIL,
 												   (update_indexes == TU_Summarizing));
+		}
 
 		/* AFTER ROW UPDATE Triggers */
 		ExecARUpdateTriggers(estate, resultRelInfo,
diff --git a/src/backend/executor/nodeModifyTable.c b/src/backend/executor/nodeModifyTable.c
index 299c2c75be8..5ac4b788e2f 100644
--- a/src/backend/executor/nodeModifyTable.c
+++ b/src/backend/executor/nodeModifyTable.c
@@ -1094,6 +1094,13 @@ ExecInsert(ModifyTableContext *context,
 										   NULL,
 										   specToken);
 
+			/* prefetch index leafs before inserting index tuples */
+			ExecInsertPrefetchIndexes(resultRelInfo,
+									  slot, estate, false, true,
+									  &specConflict,
+									  arbiterIndexes,
+									  false);
+
 			/* insert index entries for tuple */
 			recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 												   slot, estate, false, true,
@@ -1136,10 +1143,17 @@ ExecInsert(ModifyTableContext *context,
 
 			/* insert index entries for tuple */
 			if (resultRelInfo->ri_NumIndices > 0)
+			{
+				ExecInsertPrefetchIndexes(resultRelInfo,
+										  slot, estate, false,
+										  false, NULL, NIL,
+										  false);
+
 				recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 													   slot, estate, false,
 													   false, NULL, NIL,
 													   false);
+			}
 		}
 	}
 
@@ -2127,11 +2141,19 @@ ExecUpdateEpilogue(ModifyTableContext *context, UpdateContext *updateCxt,
 
 	/* insert index entries for tuple if necessary */
 	if (resultRelInfo->ri_NumIndices > 0 && (updateCxt->updateIndexes != TU_None))
+	{
+		ExecInsertPrefetchIndexes(resultRelInfo,
+								  slot, context->estate,
+								  true, false,
+								  NULL, NIL,
+								  (updateCxt->updateIndexes == TU_Summarizing));
+
 		recheckIndexes = ExecInsertIndexTuples(resultRelInfo,
 											   slot, context->estate,
 											   true, false,
 											   NULL, NIL,
 											   (updateCxt->updateIndexes == TU_Summarizing));
+	}
 
 	/* AFTER ROW UPDATE Triggers */
 	ExecARUpdateTriggers(context->estate, resultRelInfo,
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 7605eff9b9d..b58555c8b03 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1037,6 +1037,16 @@ struct config_bool ConfigureNamesBool[] =
 		true,
 		NULL, NULL, NULL
 	},
+	{
+		{"enable_insert_prefetch", PGC_USERSET, QUERY_TUNING_METHOD,
+			gettext_noop("Enables the planner's use of index insert prefetching."),
+			NULL,
+			GUC_EXPLAIN
+		},
+		&enable_insert_prefetch,
+		false,
+		NULL, NULL, NULL
+	},
 	{
 		{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
 			gettext_noop("Enables genetic query optimization."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index e48c066a5b1..bef650bb155 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -391,6 +391,7 @@
 #enable_seqscan = on
 #enable_sort = on
 #enable_tidscan = on
+#enable_insert_prefetch = off
 
 # - Planner Cost Constants -
 
diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h
index 995725502a6..e3445225f49 100644
--- a/src/include/access/amapi.h
+++ b/src/include/access/amapi.h
@@ -113,6 +113,13 @@ typedef bool (*aminsert_function) (Relation indexRelation,
 								   bool indexUnchanged,
 								   struct IndexInfo *indexInfo);
 
+/* prefetch pages for new tuple */
+typedef void (*amprefetch_function) (Relation indexRelation,
+									 Datum *values,
+									 bool *isnull,
+									 Relation heapRelation,
+									 struct IndexInfo *indexInfo);
+
 /* bulk delete */
 typedef IndexBulkDeleteResult *(*ambulkdelete_function) (IndexVacuumInfo *info,
 														 IndexBulkDeleteResult *stats,
@@ -261,6 +268,7 @@ typedef struct IndexAmRoutine
 	ambuild_function ambuild;
 	ambuildempty_function ambuildempty;
 	aminsert_function aminsert;
+	amprefetch_function amprefetch;
 	ambulkdelete_function ambulkdelete;
 	amvacuumcleanup_function amvacuumcleanup;
 	amcanreturn_function amcanreturn;	/* can be NULL */
diff --git a/src/include/access/genam.h b/src/include/access/genam.h
index f31dec6ee0f..3e5e377c64a 100644
--- a/src/include/access/genam.h
+++ b/src/include/access/genam.h
@@ -149,6 +149,11 @@ extern bool index_insert(Relation indexRelation,
 						 bool indexUnchanged,
 						 struct IndexInfo *indexInfo);
 
+extern void index_prefetch(Relation indexRelation,
+						   Datum *values, bool *isnull,
+						   Relation heapRelation,
+						   struct IndexInfo *indexInfo);
+
 extern IndexScanDesc index_beginscan(Relation heapRelation,
 									 Relation indexRelation,
 									 Snapshot snapshot,
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 7bfbf3086c8..3df531bb168 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1135,6 +1135,10 @@ extern bool btinsert(Relation rel, Datum *values, bool *isnull,
 					 IndexUniqueCheck checkUnique,
 					 bool indexUnchanged,
 					 struct IndexInfo *indexInfo);
+extern void btprefetch(Relation rel,
+					   Datum *values, bool *isnull,
+					   Relation heapRelation,
+					   struct IndexInfo *indexInfo);
 extern IndexScanDesc btbeginscan(Relation rel, int nkeys, int norderbys);
 extern Size btestimateparallelscan(void);
 extern void btinitparallelscan(void *target);
@@ -1185,6 +1189,8 @@ extern IndexTuple _bt_swap_posting(IndexTuple newitem, IndexTuple oposting,
 extern bool _bt_doinsert(Relation rel, IndexTuple itup,
 						 IndexUniqueCheck checkUnique, bool indexUnchanged,
 						 Relation heapRel);
+extern void _bt_doprefetch(Relation rel, IndexTuple itup,
+						   Relation heapRel);
 extern void _bt_finish_split(Relation rel, Relation heaprel, Buffer lbuf,
 							 BTStack stack);
 extern Buffer _bt_getstackbuf(Relation rel, Relation heaprel, BTStack stack,
@@ -1237,6 +1243,8 @@ extern void _bt_pendingfsm_finalize(Relation rel, BTVacState *vstate);
  */
 extern BTStack _bt_search(Relation rel, Relation heaprel, BTScanInsert key,
 						  Buffer *bufP, int access);
+extern void _bt_prefetch(Relation rel, Relation heaprel,
+						 BTInsertState insertstate);
 extern Buffer _bt_moveright(Relation rel, Relation heaprel, BTScanInsert key,
 							Buffer buf, bool forupdate, BTStack stack,
 							int access);
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index e1eefb400b0..f82505a86b1 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -632,6 +632,12 @@ extern List *ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
 								   bool noDupErr,
 								   bool *specConflict, List *arbiterIndexes,
 								   bool onlySummarizing);
+extern void ExecInsertPrefetchIndexes(ResultRelInfo *resultRelInfo,
+									  TupleTableSlot *slot, EState *estate,
+									  bool update,
+									  bool noDupErr,
+									  bool *specConflict, List *arbiterIndexes,
+									  bool onlySummarizing);
 extern bool ExecCheckIndexConstraints(ResultRelInfo *resultRelInfo,
 									  TupleTableSlot *slot,
 									  EState *estate, ItemPointer conflictTid,
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 6d50afbf74c..150bd3affb5 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -70,6 +70,7 @@ extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
 extern PGDLLIMPORT bool enable_presorted_aggregate;
 extern PGDLLIMPORT bool enable_async_append;
+extern PGDLLIMPORT bool enable_insert_prefetch;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 271313ebf86..344a0449d99 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -119,6 +119,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_incremental_sort        | on
  enable_indexonlyscan           | on
  enable_indexscan               | on
+ enable_insert_prefetch         | off
  enable_material                | on
  enable_memoize                 | on
  enable_mergejoin               | on
@@ -133,7 +134,7 @@ select name, setting from pg_settings where name like 'enable%';
  enable_seqscan                 | on
  enable_sort                    | on
  enable_tidscan                 | on
-(22 rows)
+(23 rows)
 
 -- There are always wait event descriptions for various types.
 select type, count(*) > 0 as ok FROM pg_wait_events
-- 
2.41.0

#4Heikki Linnakangas
hlinnaka@iki.fi
In reply to: Tomas Vondra (#3)
Re: PoC: prefetching index leaf pages (for inserts)

On 06/11/2023 19:05, Tomas Vondra wrote:

As for the path forward, I think the prefetching is demonstrably
beneficial. There are cases where it can't help or even harms
performance. I think the success depends on three areas:

(a) reducing the costs of the prefetching - For example right now we
build the index tuples twice (once for prefetch, once for the insert),
but maybe there's a way to do that only once? There are also predicate
indexes, and so on.

(b) being smarter about when to prefetch - For example if we only have
one "prefetchable" index, it's somewhat pointless to prefetch (for
single-row cases). And so on.

(c) not prefetching when already cached - This is somewhat related to
the previous case, but perhaps it'd be cheaper to first check if the
data is already cached. For shared buffers it should not be difficult,
for page cache we could use preadv2 with RWF_NOWAIT flag. The question
is if this is cheap enough to be cheaper than just doing posix_fadvise
(which however only deals with shared buffers).

I don't like this approach. It duplicates the tree-descend code, and it
also duplicates the work of descending the tree at runtime. And it only
addresses index insertion; there are a lot of places that could benefit
from prefetching or async execution like this.

I think we should think of this as async execution rather than
prefetching. We don't have the general infrastructure for writing async
code, but if we did, this would be much simpler. In an async programming
model, like you have in many other languages like Rust, python or
javascript, there would be no separate prefetching function. Instead,
aminsert() would return a future that can pause execution if it needs to
do I/O. Something like this:

aminsert_futures = NIL;
/* create a future for each index insert */
for (<all indexes>)
{
aminsert_futures = lappend(aminsert_futures, aminsert(...));
}
/* wait for all the futures to finish */
await aminsert_futures;

The async-aware aminsert function would run to completion quickly if all
the pages are already in cache. If you get a cache miss, it would start
an async I/O read for the page, and yield to the other insertions until
the I/O completes.

We already support async execution of FDWs now, with the
ForeignAsyncRequest() and ForeignAsyncConfigureWait() callbacks. Can we
generalize that?

--
Heikki Linnakangas
Neon (https://neon.tech)

#5Tomas Vondra
tomas.vondra@enterprisedb.com
In reply to: Heikki Linnakangas (#4)
Re: PoC: prefetching index leaf pages (for inserts)

On 11/23/23 14:26, Heikki Linnakangas wrote:

On 06/11/2023 19:05, Tomas Vondra wrote:

As for the path forward, I think the prefetching is demonstrably
beneficial. There are cases where it can't help or even harms
performance. I think the success depends on three areas:

(a) reducing the costs of the prefetching - For example right now we
build the index tuples twice (once for prefetch, once for the insert),
but maybe there's a way to do that only once? There are also predicate
indexes, and so on.

(b) being smarter about when to prefetch - For example if we only have
one "prefetchable" index, it's somewhat pointless to prefetch (for
single-row cases). And so on.

(c) not prefetching when already cached - This is somewhat related to
the previous case, but perhaps it'd be cheaper to first check if the
data is already cached. For shared buffers it should not be difficult,
for page cache we could use preadv2 with RWF_NOWAIT flag. The question
is if this is cheap enough to be cheaper than just doing posix_fadvise
(which however only deals with shared buffers).

I don't like this approach. It duplicates the tree-descend code, and it
also duplicates the work of descending the tree at runtime. And it only
addresses index insertion; there are a lot of places that could benefit
from prefetching or async execution like this.

Yeah, I think that's a fair assessment, although I think the amount of
duplicate code is pretty small (and perhaps it could be refactored to a
common function, which I chose not to do in the PoC patch).

I think we should think of this as async execution rather than
prefetching. We don't have the general infrastructure for writing async
code, but if we did, this would be much simpler. In an async programming
model, like you have in many other languages like Rust, python or
javascript, there would be no separate prefetching function. Instead,
aminsert() would return a future that can pause execution if it needs to
do I/O. Something like this:

aminsert_futures = NIL;
/* create a future for each index insert */
for (<all indexes>)
{
    aminsert_futures = lappend(aminsert_futures, aminsert(...));
}
/* wait for all the futures to finish */
await aminsert_futures;

The async-aware aminsert function would run to completion quickly if all
the pages are already in cache. If you get a cache miss, it would start
an async I/O read for the page, and yield to the other insertions until
the I/O completes.

We already support async execution of FDWs now, with the
ForeignAsyncRequest() and ForeignAsyncConfigureWait() callbacks. Can we
generalize that?

Interesting idea. I kinda like it in principle, however I'm not very
familiar with how our async execution works (and perhaps even with async
implementations in general), so I can't quite say how difficult would it
be to do something like that in an AM (instead of an executor).

Where exactly would be the boundary between who "creates" and "executes"
the requests, what would be the flow of execution? For the FDW it seems
fairly straightforward, because the boundary is local/remote, and the
async request is executed in a separate process.

But here everything would happen locally, so how would that work?

Imagine we're inserting a tuple into two indexes. There's a bunch of
index pages we may need to read for each index - first some internal
pages, then some leafs. Presumably we'd want to do each page read as
asynchronous, and allow transfer of control to the other index.

IIUC the async-aware aminsert() would execute an async request for the
first page it needs to read, with a callback that essentially does the
next step of index descent - reads the page, determines the next page to
read, and then do another async request. Then it'd sleep, which would
allow transfer of control to the aminsert() on the other index. And then
we'd do a similar thing for the leaf pages.

Or do I imagine things wrong?

The thing I like about this async approach is that it would allow
prefetching all index pages, while my PoC patch simply assumes all
internal pages are in cache and prefetches only the first leaf page.
That's much simpler in terms of control flow, but has clear limits.

I however wonder if there are concurrency issues. Imagine there's a
COPY, i.e. we're inserting a batch of tuples. Can you run the aminsert()
for all the tuples concurrently? Won't that have issues with the
different "async threads" modifying the index for the other threads?

If those concurrent "insert threads" would be an issue, maybe we could
make amprefetch() async-aware ...

regards

--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

#6vignesh C
vignesh21@gmail.com
In reply to: Tomas Vondra (#3)
Re: PoC: prefetching index leaf pages (for inserts)

On Mon, 6 Nov 2023 at 22:36, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:

Seems cfbot was not entirely happy about the patch, for two reasons:

1) enable_insert_prefetching definition was inconsistent (different
boot/default values, missing in .conf and so on)

2) stupid bug in execReplication, inserting index entries twice

The attached v3 should fix all of that, I believe.

As for the path forward, I think the prefetching is demonstrably
beneficial. There are cases where it can't help or even harms
performance. I think the success depends on three areas:

(a) reducing the costs of the prefetching - For example right now we
build the index tuples twice (once for prefetch, once for the insert),
but maybe there's a way to do that only once? There are also predicate
indexes, and so on.

(b) being smarter about when to prefetch - For example if we only have
one "prefetchable" index, it's somewhat pointless to prefetch (for
single-row cases). And so on.

(c) not prefetching when already cached - This is somewhat related to
the previous case, but perhaps it'd be cheaper to first check if the
data is already cached. For shared buffers it should not be difficult,
for page cache we could use preadv2 with RWF_NOWAIT flag. The question
is if this is cheap enough to be cheaper than just doing posix_fadvise
(which however only deals with shared buffers).

CFBot shows that the patch does not apply anymore as in [1]http://cfbot.cputube.org/patch_46_4622.log:
=== Applying patches on top of PostgreSQL commit ID
7014c9a4bba2d1b67d60687afb5b2091c1d07f73 ===
=== applying patch ./0001-insert-prefetch-v3.patch
patching file src/backend/access/brin/brin.c
Hunk #1 FAILED at 117.
1 out of 1 hunk FAILED -- saving rejects to file
src/backend/access/brin/brin.c.rej
patching file src/backend/access/gin/ginutil.c
Hunk #1 FAILED at 64.
1 out of 1 hunk FAILED -- saving rejects to file
src/backend/access/gin/ginutil.c.rej
patching file src/backend/access/gist/gist.c
Hunk #1 FAILED at 86.
1 out of 1 hunk FAILED -- saving rejects to file
src/backend/access/gist/gist.c.rej
patching file src/backend/access/hash/hash.c
Hunk #1 FAILED at 83.
1 out of 1 hunk FAILED -- saving rejects to file
src/backend/access/hash/hash.c.rej

Please post an updated version for the same.

[1]: http://cfbot.cputube.org/patch_46_4622.log

Regards,
Vignesh