Parallel bitmap heap scan
Hi Hackers,
I would like to propose parallel bitmap heap scan feature. After
running TPCH benchmark, It was observed that many of TPCH queries are
using bitmap scan (@TPCH_plan.tar.gz attached below). Keeping this
point in mind we thought that many query will get benefited with
parallel bitmap scan.
Robert has also pointed out the same thing in his blog related to parallel query
http://rhaas.blogspot.in/2016/04/postgresql-96-with-parallel-query-vs.html
Currently Bitmap heap plan look like this :
------------------------------------------------------
Bitmap Heap Scan
-> Bitmap Index Scan
After this patch :
---------------------
Parallel Bitmap Heap Scan
-> Bitmap Index Scan
As part of this work I have implemented parallel processing in
BitmapHeapScan node. BitmapIndexScan is still non parallel.
Brief design idea:
-----------------------
#1. Shared TIDBitmap creation and initialization
First worker to see the state as parallel bitmap info as PBM_INITIAL
become leader and set the state to PBM_INPROGRESS All other workers
see the state as PBM_INPROGRESS will wait for leader to complete the
TIDBitmap.
#2 At this level TIDBitmap is ready and all workers are awake.
#3. Bitmap processing (Iterate and process the pages).
In this phase each worker will iterate over page and chunk array and
select heap pages one by one. If prefetch is enable then there will be
two iterator. Since multiple worker are iterating over same page and
chunk array we need to have a shared iterator, so we grab a spin lock
and iterate within a lock, so that each worker get and different page
to process.
Note: For more detail on design, please refer comment of
BitmapHeapNext API in "parallel-bitmap-heap-scan-v1.patch" file.
Attached patch details:
------------------------------
1. parallel-bitmap-heap-scan-v1.patch: This is the main patch to make
bitmap heap scan node parallel aware.
2. dht-return-dsa-v1.patch: This patch will provide new API, where we
can scan full DHT[1], and get the dsa_pointers (a relative pointer).
The dsa_pointer values can be shared with other processes. We need
this because, after TIDBitmap is created, only one worker will process
whole TIDBitmap and convert it to a page and chunk array. So we need
to store the generic pointer, so that later on each worker can convert
those to their local pointer before start processing.
My patch depends on following patches.
------------------------------------------------------
1. conditional_variable
/messages/by-id/CAEepm=0zshYwB6wDeJCkrRJeoBM=jPYBe+-k_VtKRU_8zMLEfA@mail.gmail.com
2. dsa_area
/messages/by-id/CAEepm=024p-MeAsDmG=R3+tR4EGhuGJs_+rjFKF0eRoSTmMJnA@mail.gmail.com
3. Creating a DSA area to provide work space for parallel execution
/messages/by-id/CAEepm=0HmRefi1+xDJ99Gj5APHr8Qr05KZtAxrMj8b+ay3o6sA@mail.gmail.com
4. Hash table in dynamic shared memory (DHT) [1]
/messages/by-id/CAEepm=0VrMt3s_REDhQv6z1pHL7FETOD7Rt9V2MQ3r-2ss2ccA@mail.gmail.com
Order in which patches should be applied:
--------------------------------------------------------
1. conditional_variable
2. dsa_area
3. Creating a DSA area to provide work space for parallel execution
4. Hash table in dynamic shared memory.
5. dht-return-dsa-v1.patch
6. parallel-bitmap-heap-scan-v1.patch
Performance Results:
-----------------------------
Summary :
1. After this patch, I observed currently 4 queries are getting
significant improvement (Q4, Q6, Q14, Q15).
- Q4, is converting from parallel seqscan to parallel bitmap heap scan.
- Other queries are converted from a regular bitmap heap scan to a
parallel bitmap heap scan.
2. Benefit is more visible at lower workers (upto 4), after that some
of the queries are selecting ParallelSeqScan over ParallelBitmapScan.
And, I think this is expected, because so far we have only made
BitmapHeap node as parallel whereas ParallelSeqScan is completely
parallel so at higher worker count ParallelSeqScan is better choice.
3. Detailed result is attached @TPCH_PBMS.pdf
4. Explain analyse output is attached @TPCH_plan.tar.gz (for all
changed queries at worker 2)
TPCH query plan changed example (TPCH Q6):
----------------------------------------------------------------
On Head:
-------------
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1558475.95..1558475.96 rows=1 width=32) (actual
time=40921.437..40921.438 rows=1 loops=1)
-> Aggregate (cost=1558475.95..1558475.96 rows=1 width=32)
(actual time=40921.435..40921.435 rows=1 loops=1)
-> Bitmap Heap Scan on lineitem (cost=291783.32..1552956.39
rows=1103911 width=12) (actual time=7032.075..38997.369 rows=1140434
loops=1)
Recheck Cond: ((l_shipdate >= '1994-01-01'::date) AND
(l_shipdate < '1995-01-01 00:00:00'::timestamp without time zone) AND
(l_discount >= 0.01) AND (l_discount <= 0.03) AND (l_quantity <
'24'::numeric))
Rows Removed by Index Recheck: 25284232
Heap Blocks: exact=134904 lossy=530579
-> Bitmap Index Scan on idx_lineitem_shipdate
(cost=0.00..291507.35 rows=1103911 width=0) (actual
time=6951.408..6951.408 rows=1140434 loops=1)
Index Cond: ((l_shipdate >= '1994-01-01'::date)
AND (l_shipdate < '1995-01-01 00:00:00'::timestamp without time zone)
AND (l_discount >= 0.01) AND (l_discount <= 0.03) AND (l_quantity <
'24'::numeric))
Planning time: 1.126 ms
Execution time: 40922.569 ms
(10 rows)
After Patch:
----------------
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1541767.60..1541767.61 rows=1 width=32) (actual
time=21895.008..21895.009 rows=1 loops=1)
-> Finalize Aggregate (cost=1541767.60..1541767.61 rows=1
width=32) (actual time=21895.006..21895.006 rows=1 loops=1)
-> Gather (cost=1541767.38..1541767.59 rows=2 width=32)
(actual time=21894.341..21894.970 rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (cost=1540767.38..1540767.39
rows=1 width=32) (actual time=21890.990..21890.990 rows=1 loops=3)
-> Parallel Bitmap Heap Scan on lineitem
(cost=291783.32..1538467.56 rows=459963 width=12) (actual
time=8517.126..21215.469 rows=380145 loops=3)
Recheck Cond: ((l_shipdate >=
'1994-01-01'::date) AND (l_shipdate < '1995-01-01 00:00:00'::timestamp
without time zone) AND (l_discount >= 0.01) AND (l_discount <= 0.03)
AND (l_quantity < '24'::numeric))
Rows Removed by Index Recheck: 8427921
Heap Blocks: exact=47761 lossy=187096
-> Bitmap Index Scan on
idx_lineitem_shipdate (cost=0.00..291507.35 rows=1103911 width=0)
(actual time=8307.291..8307.291 rows=1140434 loops=1)
Index Cond: ((l_shipdate >=
'1994-01-01'::date) AND (l_shipdate < '1995-01-01 00:00:00'::timestamp
without time zone) AND (l_discount >= 0.01) AND (l_discount <= 0.03)
AND (l_quantity < '24'::numeric))
Planning time: 1.173 ms
Execution time: 21915.931 ms
(14 rows)
* Thanks to Robert Haas and Amit Kapila, for helping in design review
(off list) and many valuable inputs.
* Thanks to Thomas Munro for DSA and DHT work on which my patch is based on.
* Thanks to Rafia sabih for helping with performance test.
--
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com
Attachments:
dht-return-dsa-v1.patchapplication/octet-stream; name=dht-return-dsa-v1.patchDownload
diff --git a/src/backend/storage/ipc/dht.c b/src/backend/storage/ipc/dht.c
index 0916a3f..6974b91 100644
--- a/src/backend/storage/ipc/dht.c
+++ b/src/backend/storage/ipc/dht.c
@@ -51,21 +51,6 @@
#include "storage/spin.h"
#include "utils/memutils.h"
-/*
- * An item in the hash table. This wraps the user's entry object in an
- * envelop that holds a pointer back to the bucket and a pointer to the next
- * item in the bucket.
- */
-struct dht_hash_table_item
-{
- /* The hashed key, to avoid having to recompute it. */
- dht_hash hash;
- /* The next item in the same bucket. */
- dsa_pointer next;
- /* The user's entry object follows here. */
- char entry[FLEXIBLE_ARRAY_MEMBER];
-};
-
/* The number of partitions for locking purposes. */
#define DHT_NUM_PARTITIONS_LOG2 7
#define DHT_NUM_PARTITIONS (1 << DHT_NUM_PARTITIONS_LOG2)
@@ -699,6 +684,30 @@ dht_iterate_next(dht_iterator *iterator)
{
dsa_pointer item_pointer;
+ item_pointer = dht_iterate_next_dsa(iterator);
+
+ if (DsaPointerIsValid(item_pointer))
+ {
+ iterator->item = dsa_get_address(iterator->hash_table->area,
+ item_pointer);
+ return &(iterator->item->entry);
+ }
+
+ return NULL;
+}
+
+/*
+ * dht_iterate_next_dsa
+ *
+ * Move to the next item in the hash table. Returns a dsa_pointer to
+ * next item, or InvalidDsaPointer if the end of the hash table has
+ * been reached.
+ */
+dsa_pointer
+dht_iterate_next_dsa(dht_iterator *iterator)
+{
+ dsa_pointer item_pointer;
+
Assert(iterator->hash_table->control->magic == DHT_MAGIC);
while (iterator->partition < DHT_NUM_PARTITIONS)
@@ -716,9 +725,8 @@ dht_iterate_next(dht_iterator *iterator)
{
/* Remember this item, so that we can step over it next time. */
iterator->last_item_pointer = item_pointer;
- iterator->item = dsa_get_address(iterator->hash_table->area,
- item_pointer);
- return &(iterator->item->entry);
+
+ return item_pointer;
}
/* We have reached the end of the bucket. */
@@ -751,7 +759,7 @@ dht_iterate_next(dht_iterator *iterator)
}
}
iterator->item = NULL;
- return NULL;
+ return InvalidDsaPointer;
}
/*
diff --git a/src/include/storage/dht.h b/src/include/storage/dht.h
index ccf9d17..8655f55 100644
--- a/src/include/storage/dht.h
+++ b/src/include/storage/dht.h
@@ -61,11 +61,25 @@ typedef struct
/* Forward declaration of private types for use only by dht.c. */
struct dht_hash_table_bucket;
-struct dht_hash_table_item;
-typedef struct dht_hash_table_item dht_hash_table_item;
+
typedef struct dht_hash_table_bucket dht_hash_table_bucket;
/*
+ * An item in the hash table. This wraps the user's entry object in an
+ * envelop that holds a pointer back to the bucket and a pointer to the next
+ * item in the bucket.
+ */
+typedef struct dht_hash_table_item
+{
+ /* The hashed key, to avoid having to recompute it. */
+ dht_hash hash;
+ /* The next item in the same bucket. */
+ dsa_pointer next;
+ /* The user's entry object follows here. */
+ char entry[FLEXIBLE_ARRAY_MEMBER];
+}dht_hash_table_item;
+
+/*
* The state used to track a walk over all entries in a hash table. The
* members of this struct are only for use by code in dht.c, but it is
* included in the header because it's useful to be able to create objects of
@@ -101,6 +115,7 @@ extern void *dht_iterate_next(dht_iterator *iterator);
extern void dht_iterate_delete(dht_iterator *iterator);
extern void dht_iterate_release(dht_iterator *iterator);
extern void dht_iterate_end(dht_iterator *iterator);
+extern dsa_pointer dht_iterate_next_dsa(dht_iterator *iterator);
/* Finding, creating, deleting entries. */
extern void *dht_find(dht_hash_table *hash_table,
parallel-bitmap-heap-scan-v1.patchapplication/octet-stream; name=parallel-bitmap-heap-scan-v1.patchDownload
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index 9ed9fd2..c8034d0 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -362,7 +362,7 @@ restartScanEntry:
if (entry->matchBitmap && !tbm_is_empty(entry->matchBitmap))
{
- entry->matchIterator = tbm_begin_iterate(entry->matchBitmap);
+ entry->matchIterator = tbm_begin_iterate(entry->matchBitmap, NULL);
entry->isFinished = FALSE;
}
}
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index b019bc1..1dfd492 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -1753,6 +1753,22 @@ retry:
}
/* ----------------
+ * heap_bm_update_snapshot
+ *
+ * Update snpashot info in heap scan descriptor.
+ * ----------------
+ */
+void
+heap_bm_update_snapshot(HeapScanDesc scan, Snapshot snapshot)
+{
+ Assert(IsMVCCSnapshot(snapshot));
+
+ RegisterSnapshot(snapshot);
+ scan->rs_snapshot = snapshot;
+ scan->rs_temp_snap = true;
+}
+
+/* ----------------
* heap_getnext - retrieve next tuple in scan
*
* Fix to work with index relations.
diff --git a/src/backend/executor/execParallel.c b/src/backend/executor/execParallel.c
index 72bacd5..1e34f26 100644
--- a/src/backend/executor/execParallel.c
+++ b/src/backend/executor/execParallel.c
@@ -29,6 +29,7 @@
#include "executor/nodeForeignscan.h"
#include "executor/nodeSeqscan.h"
#include "executor/tqueue.h"
+#include "executor/nodeBitmapHeapscan.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
@@ -203,6 +204,10 @@ ExecParallelEstimate(PlanState *planstate, ExecParallelEstimateContext *e)
ExecCustomScanEstimate((CustomScanState *) planstate,
e->pcxt);
break;
+ case T_BitmapHeapScanState:
+ ExecBitmapHeapEstimate((BitmapHeapScanState *) planstate,
+ e->pcxt);
+ break;
default:
break;
}
@@ -255,6 +260,11 @@ ExecParallelInitializeDSM(PlanState *planstate,
ExecCustomScanInitializeDSM((CustomScanState *) planstate,
d->pcxt);
break;
+ case T_BitmapHeapScanState:
+ ExecBitmapHeapInitializeDSM((BitmapHeapScanState *) planstate,
+ d->pcxt);
+ break;
+
default:
break;
}
@@ -724,6 +734,10 @@ ExecParallelInitializeWorker(PlanState *planstate, shm_toc *toc)
ExecCustomScanInitializeWorker((CustomScanState *) planstate,
toc);
break;
+ case T_BitmapHeapScanState:
+ ExecBitmapHeapInitializeWorker(
+ (BitmapHeapScanState *) planstate, toc);
+ break;
default:
break;
}
diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c
index 449aacb..c3ad77b 100644
--- a/src/backend/executor/nodeBitmapHeapscan.c
+++ b/src/backend/executor/nodeBitmapHeapscan.c
@@ -47,16 +47,63 @@
#include "utils/spccache.h"
#include "utils/snapmgr.h"
#include "utils/tqual.h"
-
+#include "miscadmin.h"
+#include "pgstat.h"
static TupleTableSlot *BitmapHeapNext(BitmapHeapScanState *node);
static void bitgetpage(HeapScanDesc scan, TBMIterateResult *tbmres);
-
+static bool pbms_is_leader(ParallelBitmapInfo *pbminfo);
+static void pbms_set_parallel(PlanState *node);
+static TBMIterateResult *pbms_parallel_iterate(TBMIterator *iterator,
+ ParallelIterator *parallel_iterator,
+ bool is_parallel);
+static void prefetch_pages(int *prefetch_pages, int prefetch_target,
+ BitmapHeapScanState *node, HeapScanDesc scan);
+static void update_prefetch_target(int *prefetch_target, int prefetch_maximum);
/* ----------------------------------------------------------------
* BitmapHeapNext
*
* Retrieve next tuple from the BitmapHeapScan node's currentRelation
+ *
+ *
+ * [PARALLEL BITMAP HEAP SCAN ALGORITHM]
+ *
+ * #1. Shared TIDBitmap creation and initialization
+ * a) First worker to see the state as parallel bitmap info as
+ * PBM_INITIAL become leader and set the state to PBM_INPROGRESS
+ * All other workers see the state as PBM_INPROGRESS will wait for
+ * leader to complete the TIDBitmap.
+ *
+ * Leader Worker Processing:
+ * (Leader is responsible for creating shared TIDBitmap and create
+ * shared page and chunk array from TIDBitmap.)
+ * 1) Create TIDBitmap using DHT.
+ * 2) Begin Iterate: convert hash table into shared page and chunk
+ * array.
+ * 3) Restore local TIDBitmap variable information into
+ * ParallelBitmapInfo so that other worker can see those.
+ * 4) set state to PBM_FINISHED.
+ * 5) Wake up other workers.
+ *
+ * Other Worker Processing:
+ * 1) Wait until leader create shared TIDBitmap and shared page
+ * and chunk array.
+ * 2) Attach to shared page table, copy TIDBitmap from
+ * ParallelBitmapInfo to local TIDBitmap, we copy this to local
+ * TIDBitmap so that next level processing can read information
+ * same as in non parallel case and we can avoid extra changes
+ * in code.
+ *
+ * # At this level TIDBitmap is ready and all workers are awake #
+ *
+ * #2. Bitmap processing (Iterate and process the pages).
+ * . In this phase each worker will iterate over page and chunk array and
+ * select heap pages one by one. If prefetch is enable then there will
+ * be two iterator.
+ * . Since multiple worker are iterating over same page and chunk array
+ * we need to have a shared iterator, so we grab a spin lock and iterate
+ * within a lock.
* ----------------------------------------------------------------
*/
static TupleTableSlot *
@@ -67,12 +114,19 @@ BitmapHeapNext(BitmapHeapScanState *node)
TIDBitmap *tbm;
TBMIterator *tbmiterator;
TBMIterateResult *tbmres;
-
+ ParallelBitmapInfo *pbminfo = node->parallel_bitmap;
+ bool is_parallel = node->parallel_bitmap ? true : false;
#ifdef USE_PREFETCH
TBMIterator *prefetch_iterator;
#endif
OffsetNumber targoffset;
TupleTableSlot *slot;
+ ParallelTIDBitmap *parallel_tbm = NULL;
+
+ /* Get the parallel TBM address in shared memory using offset */
+ if (is_parallel)
+ parallel_tbm = (ParallelTIDBitmap*)((char *)pbminfo +
+ pbminfo->ptbm_offset);
/*
* extract necessary information from index scan node
@@ -101,36 +155,106 @@ BitmapHeapNext(BitmapHeapScanState *node)
*/
if (tbm == NULL)
{
- tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
+ /*
+ * Process the lower level node only if either we are running
+ * in non parallel mode or we are leader worker.
+ *
+ * In parallel mode leader worker will immediately come out
+ * of the function, but all other worker will be blocked
+ * until leader worker wake them up.
+ */
+ if (!is_parallel || pbms_is_leader(pbminfo))
+ {
+ /*
+ * If we are in parallel mode recursively process the outer
+ * node and set parallel flag in lower level bitmap index scan.
+ * Later bitmap index node will use this flag to indicate
+ * tidbitmap that it needs to create an shared page table.
+ */
+ if (is_parallel)
+ {
+ node->is_leader = true;
+ pbms_set_parallel(outerPlanState(node));
+ }
+
+ tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
+ }
+ else
+ {
+ /*
+ * By this time leader has already created the shared TBM.
+ * Here we need to create a local TBM and copy information from
+ * shared location. We also need to attach to shared page table
+ * using hash table handle stored in parallel_tbm(shared memory).
+ */
+ tbm = tbm_create(work_mem * 1024L);
+ tbm_set_parallel(tbm, node->ss.ps.state->es_query_area);
+ tbm_attach_to_pagetable(tbm, parallel_tbm);
+ }
if (!tbm || !IsA(tbm, TIDBitmap))
elog(ERROR, "unrecognized result from subplan");
node->tbm = tbm;
- node->tbmiterator = tbmiterator = tbm_begin_iterate(tbm);
+ node->tbmiterator = tbmiterator
+ = tbm_begin_iterate(tbm, parallel_tbm);
node->tbmres = tbmres = NULL;
#ifdef USE_PREFETCH
if (node->prefetch_maximum > 0)
{
- node->prefetch_iterator = prefetch_iterator = tbm_begin_iterate(tbm);
- node->prefetch_pages = 0;
- node->prefetch_target = -1;
+ node->prefetch_iterator = prefetch_iterator =
+ tbm_begin_iterate(tbm, parallel_tbm);
+
+ /* These variable are used only in case of non parallel mode */
+ if (!is_parallel)
+ {
+ node->prefetch_pages = 0;
+ node->prefetch_target = -1;
+ }
}
#endif /* USE_PREFETCH */
+
+ /*
+ * If we are in parallel mode and we are leader worker then
+ * copy the local TBM information to shared location, and wake
+ * up other workers.
+ */
+ if (node->is_leader)
+ {
+ /*
+ * copy TBM local information in shared memory before waking
+ * up other workers. Other workers will create there own
+ * TBM and copy information from shared memory, they will
+ * also use hash table handle from shared memory for attaching
+ * to shared memory hash table.
+ */
+ tbm_update_shared_members(tbm, parallel_tbm);
+
+ /* Change the state under a lock */
+ SpinLockAcquire(&pbminfo->state_mutex);
+ pbminfo->state = PBM_FINISHED;
+ SpinLockRelease(&pbminfo->state_mutex);
+
+ /* Wake up all other workers. */
+ ConditionVariableBroadcast(&pbminfo->cv);
+ }
}
for (;;)
{
Page dp;
ItemId lp;
+ bool need_prefetch = false;
/*
* Get next page of results if needed
*/
if (tbmres == NULL)
{
- node->tbmres = tbmres = tbm_iterate(tbmiterator);
+ node->tbmres = tbmres = pbms_parallel_iterate(tbmiterator,
+ &pbminfo->tbmiterator,
+ is_parallel);
if (tbmres == NULL)
{
/* no more entries in the bitmap */
@@ -138,17 +262,44 @@ BitmapHeapNext(BitmapHeapScanState *node)
}
#ifdef USE_PREFETCH
- if (node->prefetch_pages > 0)
+ if (is_parallel)
+ {
+ /*
+ * If we are in parallel mode then acquire prefetch_mutex and
+ * check prefetch_pages from shared location.
+ */
+ SpinLockAcquire(&pbminfo->prefetch_mutex);
+ if (pbminfo->prefetch_pages > 0)
+ pbminfo->prefetch_pages --;
+ else
+ need_prefetch = true;
+ SpinLockRelease(&pbminfo->prefetch_mutex);
+ }
+ else if (node->prefetch_pages > 0)
{
/* The main iterator has closed the distance by one page */
node->prefetch_pages--;
}
- else if (prefetch_iterator)
+ else
+ need_prefetch = true;
+
+ if (prefetch_iterator && need_prefetch)
{
- /* Do not let the prefetch iterator get behind the main one */
- TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator);
+ TBMIterateResult *tbmpre;
- if (tbmpre == NULL || tbmpre->blockno != tbmres->blockno)
+ /* Do not let the prefetch iterator get behind the main one */
+ tbmpre = pbms_parallel_iterate(prefetch_iterator,
+ &pbminfo->prefetch_iterator,
+ is_parallel);
+ /*
+ * In case of parallel mode we can only ensure that prefetch
+ * iterator is not behind main iterator, but we can not
+ * ensure that current blockno in main iterator and prefetch
+ * iterator is same. It's possible that whatever blockno we
+ * are prefetching is getting processed by some other worker.
+ */
+ if (!is_parallel &&
+ (tbmpre == NULL || tbmpre->blockno != tbmres->blockno))
elog(ERROR, "prefetch and main iterators are out of sync");
}
#endif /* USE_PREFETCH */
@@ -182,20 +333,25 @@ BitmapHeapNext(BitmapHeapScanState *node)
#ifdef USE_PREFETCH
- /*
- * Increase prefetch target if it's not yet at the max. Note that
- * we will increase it to zero after fetching the very first
- * page/tuple, then to one after the second tuple is fetched, then
- * it doubles as later pages are fetched.
- */
- if (node->prefetch_target >= node->prefetch_maximum)
- /* don't increase any further */ ;
- else if (node->prefetch_target >= node->prefetch_maximum / 2)
- node->prefetch_target = node->prefetch_maximum;
- else if (node->prefetch_target > 0)
- node->prefetch_target *= 2;
- else
- node->prefetch_target++;
+ /* Increase prefetch target if it's not yet at the max. */
+ if (node->prefetch_target < node->prefetch_maximum)
+ {
+ if (!is_parallel)
+ update_prefetch_target(&node->prefetch_target,
+ node->prefetch_maximum);
+ else
+ {
+ /*
+ * If we are in parallel mode then grab prefetch_mutex
+ * before updating prefetch target.
+ */
+ SpinLockAcquire(&pbminfo->prefetch_mutex);
+ update_prefetch_target(&pbminfo->prefetch_target,
+ node->prefetch_maximum);
+ SpinLockRelease(&pbminfo->prefetch_mutex);
+ }
+ }
+
#endif /* USE_PREFETCH */
}
else
@@ -211,8 +367,22 @@ BitmapHeapNext(BitmapHeapScanState *node)
* Try to prefetch at least a few pages even before we get to the
* second page if we don't stop reading after the first tuple.
*/
- if (node->prefetch_target < node->prefetch_maximum)
- node->prefetch_target++;
+ if (!is_parallel)
+ {
+ if (node->prefetch_target < node->prefetch_maximum)
+ node->prefetch_target++;
+ }
+ else
+ {
+ /*
+ * If we are in parallel mode then grab prefetch_mutex
+ * before updating prefetch target.
+ */
+ SpinLockAcquire(&pbminfo->prefetch_mutex);
+ if (pbminfo->prefetch_target < node->prefetch_maximum)
+ pbminfo->prefetch_target++;
+ SpinLockRelease(&pbminfo->prefetch_mutex);
+ }
#endif /* USE_PREFETCH */
}
@@ -236,21 +406,29 @@ BitmapHeapNext(BitmapHeapScanState *node)
*/
if (prefetch_iterator)
{
- while (node->prefetch_pages < node->prefetch_target)
+ if (pbminfo == NULL)
{
- TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator);
+ prefetch_pages(&node->prefetch_pages,
+ node->prefetch_target, node, scan);
+ }
+ else if(node->prefetch_pages < node->prefetch_target)
+ {
+ /*
+ * If we are in parallel mode then grab prefetch_mutex
+ * before going for prefetch.
+ */
+ SpinLockAcquire(&pbminfo->prefetch_mutex);
- if (tbmpre == NULL)
- {
- /* No more pages to prefetch */
- tbm_end_iterate(prefetch_iterator);
- node->prefetch_iterator = prefetch_iterator = NULL;
- break;
- }
- node->prefetch_pages++;
- PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno);
+ prefetch_pages(&pbminfo->prefetch_pages,
+ pbminfo->prefetch_target, node, scan);
+
+ SpinLockRelease(&pbminfo->prefetch_mutex);
}
+
+ /* Restore the prefetch_iterator */
+ prefetch_iterator = node->prefetch_iterator;
}
+
#endif /* USE_PREFETCH */
/*
@@ -465,6 +643,22 @@ ExecReScanBitmapHeapScan(BitmapHeapScanState *node)
node->tbmres = NULL;
node->prefetch_iterator = NULL;
+ /* reset parallel bitmap scan info, if present */
+ if (node->parallel_bitmap)
+ {
+ ParallelBitmapInfo *pbminfo = node->parallel_bitmap;
+
+ pbminfo->state = PBM_INITIAL;
+ pbminfo->tbmiterator.schunkbit = 0;
+ pbminfo->tbmiterator.spageptr = 0;
+ pbminfo->tbmiterator.schunkptr = 0;
+ pbminfo->prefetch_iterator.schunkbit = 0;
+ pbminfo->prefetch_iterator.spageptr = 0;
+ pbminfo->prefetch_iterator.schunkptr = 0;
+ pbminfo->prefetch_pages = 0;
+ pbminfo->prefetch_target = -1;
+ }
+
ExecScanReScan(&node->ss);
/*
@@ -567,6 +761,8 @@ ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags)
scanstate->prefetch_target = 0;
/* may be updated below */
scanstate->prefetch_maximum = target_prefetch_pages;
+ scanstate->is_leader = false;
+ scanstate->parallel_bitmap = NULL;
/*
* Miscellaneous initialization
@@ -653,3 +849,311 @@ ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags)
*/
return scanstate;
}
+
+/*----------------
+ * pbms_is_leader
+ *
+ * Check if we are the first one to come here, if yes then
+ * we become leader, otherwise we need to wait until leader
+ * create the shared TID bitmap and wake us up.
+ * ---------------
+ */
+static bool
+pbms_is_leader(ParallelBitmapInfo *pbminfo)
+{
+ bool needWait = false;
+ bool queuedSelf = false;
+ bool leader = false;
+
+ for(;;)
+ {
+ SpinLockAcquire(&pbminfo->state_mutex);
+
+ /*
+ * if state is initial then we are the first one to come here
+ * set the state to in progress and mark ourself as leader
+ */
+ if (pbminfo->state == PBM_INITIAL)
+ {
+ pbminfo->state = PBM_INPROGRESS;
+ leader = true;
+ }
+
+ /* bitmap create is in progress so we need to wait */
+ else if (pbminfo->state == PBM_INPROGRESS)
+ needWait = true;
+
+ SpinLockRelease(&pbminfo->state_mutex);
+
+ /*
+ * If we are a leader or else leader has already created a
+ * tid bitmap.
+ */
+ if (leader || !needWait)
+ break;
+
+ /* We need to queue */
+ if (queuedSelf)
+ {
+ /* Sleep until leader send wake up signal */
+ ConditionVariableSleep(WAIT_EVENT_PARALLEL_BITMAP_SCAN);
+ queuedSelf = false;
+ needWait = false;
+ }
+ else if (needWait)
+ {
+ /* Add ourself to wait queue */
+ ConditionVariablePrepareToSleep(&pbminfo->cv);
+ queuedSelf = true;
+ }
+ }
+
+ /* Cancel the sleep before return */
+ ConditionVariableCancelSleep();
+
+ return leader;
+}
+
+/* ----------------
+ * pbms_iterator_init - initialize parallel bitmap scan iterator
+ *
+ * ----------------
+ */
+static void
+pbms_iterator_init(ParallelIterator *target)
+{
+ SpinLockInit(&target->mutex);
+
+ target->schunkbit = 0;
+ target->schunkptr = 0;
+ target->spageptr = 0;
+}
+
+/*-------------------
+ * pbms_set_parallel
+ *
+ * Parallel bitmap heap scan set below index scan node as parallel
+ * so that it can create shared TIDBitmap.
+ * -----------------
+ */
+static void
+pbms_set_parallel(PlanState *node)
+{
+ /*
+ * In case of BitmapOr or BitmapAnd set first bitmap index scan node
+ * as parallel, because only first node will create the main bitmap
+ * other bitmaps will be merged to the first bitmap so no need to
+ * create them in shared memory.
+ */
+ switch(node->type)
+ {
+ case T_BitmapIndexScanState:
+ ((BitmapIndexScanState*)node)->biss_Parallel = true;
+ break;
+ case T_BitmapOrState:
+ pbms_set_parallel(((BitmapOrState*)node)->bitmapplans[0]);
+ break;
+ case T_BitmapAndState:
+ pbms_set_parallel(((BitmapAndState*)node)->bitmapplans[0]);
+ break;
+ default:
+ break;
+ }
+}
+
+/*
+ * prefetch_pages
+ *
+ * Prefetch pages before going for actual processing of the page.
+ */
+static void
+prefetch_pages(int *prefetch_pages, int prefetch_target,
+ BitmapHeapScanState *node, HeapScanDesc scan)
+{
+ TBMIterator *iterator = node->prefetch_iterator;
+ ParallelIterator *parallel_iteartor;
+
+ /*
+ * If parallel bitmap info available means we are running
+ * in parallel mode. So use parallel iterator for prefetching.
+ */
+ if (node->parallel_bitmap)
+ parallel_iteartor = &node->parallel_bitmap->prefetch_iterator;
+
+ while (*prefetch_pages < prefetch_target)
+ {
+ TBMIterateResult *tbmpre = pbms_parallel_iterate(iterator,
+ parallel_iteartor,
+ node->parallel_bitmap ? true:false);
+ if (tbmpre == NULL)
+ {
+ /* No more pages to prefetch */
+ tbm_end_iterate(iterator);
+ node->prefetch_iterator = NULL;
+ break;
+ }
+
+ (*prefetch_pages)++;
+ PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno);
+ }
+}
+
+/*
+ * update_prefetch_target
+ *
+ * Update the value of prefetch target
+ */
+static void
+update_prefetch_target(int *prefetch_target, int prefetch_maximum)
+{
+ /*
+ * Increase prefetch target if it's not yet at the max. Note that
+ * we will increase it to zero after fetching the very first
+ * page/tuple, then to one after the second tuple is fetched, then
+ * it doubles as later pages are fetched.
+ */
+ if (*prefetch_target >= prefetch_maximum)
+ /* don't increase any further */ ;
+ else if (*prefetch_target >= prefetch_maximum / 2)
+ *prefetch_target = prefetch_maximum;
+ else if (*prefetch_target > 0)
+ *prefetch_target *= 2;
+ else
+ (*prefetch_target)++;
+}
+
+/*
+ * pbms_parallel_iterate
+ *
+ * Acquire a iterator lock.
+ * copy iterator state from shared iterator to local iterator.
+ * Call tbm_iterate and restore the state back to shared iterator.
+ */
+static TBMIterateResult *
+pbms_parallel_iterate(TBMIterator *iterator,
+ ParallelIterator *parallel_iterator,
+ bool is_parallel)
+{
+ TBMIterateResult *output;
+
+ /* If not running in parallel mode then directly call tbm_iterate. */
+ if (!is_parallel)
+ return tbm_iterate(iterator);
+
+ /*
+ * We are in parallel mode so grab parallel iterator mutex
+ * before calling iterator.
+ */
+ SpinLockAcquire(¶llel_iterator->mutex);
+
+ /*
+ * Now we have got lock on iterator so copy information from
+ * shared location to our local iterator.
+ */
+ iterator->spageptr = parallel_iterator->spageptr;
+ iterator->schunkptr = parallel_iterator->schunkptr;
+ iterator->schunkbit = parallel_iterator->schunkbit;
+
+ output = tbm_iterate(iterator);
+
+ /*
+ * tbm_iterate would have changed the iterator value
+ * in local iterator so copy them back to shared location
+ * before releasing the lock.
+ */
+ parallel_iterator->spageptr = iterator->spageptr;
+ parallel_iterator->schunkptr = iterator->schunkptr;
+ parallel_iterator->schunkbit = iterator->schunkbit;
+
+ SpinLockRelease(¶llel_iterator->mutex);
+
+ return output;
+}
+
+/* ----------------------------------------------------------------
+ * ExecBitmapHeapEstimate
+ *
+ * estimates the space required to serialize bitmap scan node.
+ * ----------------------------------------------------------------
+ */
+void
+ExecBitmapHeapEstimate(BitmapHeapScanState *node,
+ ParallelContext *pcxt)
+{
+ EState *estate = node->ss.ps.state;
+ Size offset = add_size(offsetof(ParallelBitmapInfo,
+ phs_snapshot_data),
+ EstimateSnapshotSpace(estate->es_snapshot));
+
+ /* Estimate the size for sharing parallel TBM info. */
+ node->pscan_len = tbm_estimate_parallel_tidbitmap(offset);
+
+ shm_toc_estimate_chunk(&pcxt->estimator, node->pscan_len);
+ shm_toc_estimate_keys(&pcxt->estimator, 1);
+}
+
+/* ----------------------------------------------------------------
+ * ExecBitmapHeapInitializeDSM
+ *
+ * Set up a parallel bitmap heap scan descriptor.
+ * ----------------------------------------------------------------
+ */
+void
+ExecBitmapHeapInitializeDSM(BitmapHeapScanState *node,
+ ParallelContext *pcxt)
+{
+ ParallelBitmapInfo *pbminfo;
+ EState *estate = node->ss.ps.state;
+ Snapshot snapshot;
+ Size offset = add_size(offsetof(ParallelBitmapInfo,
+ phs_snapshot_data),
+ EstimateSnapshotSpace(estate->es_snapshot));
+
+ pbminfo = shm_toc_allocate(pcxt->toc, node->pscan_len);
+
+ /* Offset to parallel TBM info. */
+ pbminfo->ptbm_offset = offset;
+
+ /* Initialize shared tbmiterator and prefetch_iterator */
+ pbms_iterator_init(&pbminfo->tbmiterator);
+ pbms_iterator_init(&pbminfo->prefetch_iterator);
+
+ /* Initialize mutex to protect prefetch pages and target */
+ SpinLockInit(&pbminfo->prefetch_mutex);
+ pbminfo->prefetch_pages = 0;
+ pbminfo->prefetch_target = -1;
+
+ /* Initialize mutex to protect current state */
+ SpinLockInit(&pbminfo->state_mutex);
+ pbminfo->state = PBM_INITIAL;
+
+ ConditionVariableInit(&pbminfo->cv);
+
+ SerializeSnapshot(estate->es_snapshot, pbminfo->phs_snapshot_data);
+
+ shm_toc_insert(pcxt->toc, node->ss.ps.plan->plan_node_id, pbminfo);
+
+ node->parallel_bitmap = pbminfo;
+ snapshot = RestoreSnapshot(pbminfo->phs_snapshot_data);
+
+ heap_bm_update_snapshot(node->ss.ss_currentScanDesc, snapshot);
+}
+
+/* ----------------------------------------------------------------
+ * ExecBitmapHeapInitializeWorker
+ *
+ * Copy relevant information from TOC into planstate.
+ * ----------------------------------------------------------------
+ */
+void
+ExecBitmapHeapInitializeWorker(BitmapHeapScanState *node, shm_toc *toc)
+{
+ ParallelBitmapInfo *pbminfo;
+ Snapshot snapshot;
+
+ pbminfo = shm_toc_lookup(toc, node->ss.ps.plan->plan_node_id);
+ node->parallel_bitmap = pbminfo;
+
+ snapshot = RestoreSnapshot(pbminfo->phs_snapshot_data);
+ heap_bm_update_snapshot(node->ss.ss_currentScanDesc, snapshot);
+}
diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c
index a364098..9cc5088 100644
--- a/src/backend/executor/nodeBitmapIndexscan.c
+++ b/src/backend/executor/nodeBitmapIndexscan.c
@@ -82,6 +82,13 @@ MultiExecBitmapIndexScan(BitmapIndexScanState *node)
}
/*
+ * If parallel flag is set then set flag in TIDBitmap to indicate
+ * that we need a shared page table.
+ */
+ if (node->biss_Parallel)
+ tbm_set_parallel(tbm, node->ss.ps.state->es_query_area);
+
+ /*
* Get TIDs from index and insert into bitmap
*/
while (doscan)
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index dfeb7d5..9207741 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -44,6 +44,11 @@
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "utils/hsearch.h"
+#include "storage/condition_variable.h"
+#include "storage/lwlock.h"
+#include "storage/shmem.h"
+#include "storage/dht.h"
+#include "storage/dsa.h"
/*
* The maximum number of tuples per page is not large (typically 256 with
@@ -80,6 +85,8 @@
/* number of active words for a lossy chunk: */
#define WORDS_PER_CHUNK ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
+#define TBM_IS_SHARED(tbm) (tbm)->shared
+
/*
* The hashtable entries are represented by this data structure. For
* an exact page, blockno is the page number and bit k of the bitmap
@@ -138,24 +145,28 @@ struct TIDBitmap
/* these are valid when iterating is true: */
PagetableEntry **spages; /* sorted exact-page list, or NULL */
PagetableEntry **schunks; /* sorted lossy-chunk list, or NULL */
+ bool shared; /* need to build shared tbm if set*/
+ dht_hash_table_handle hash_handle; /* shared hash table handle */
+ dht_hash_table *shared_pagetable; /* dynamic hash table */
+ dsa_area *area; /* reference to per-query shared memory area */
};
/*
- * When iterating over a bitmap in sorted order, a TBMIterator is used to
- * track our progress. There can be several iterators scanning the same
- * bitmap concurrently. Note that the bitmap becomes read-only as soon as
- * any iterator is created.
+ * Holds shared members of TIDBitmap for parallel bitmap scan.
*/
-struct TBMIterator
+struct ParallelTIDBitmap
{
- TIDBitmap *tbm; /* TIDBitmap we're iterating over */
- int spageptr; /* next spages index */
- int schunkptr; /* next schunks index */
- int schunkbit; /* next bit to check in current schunk */
- TBMIterateResult output; /* MUST BE LAST (because variable-size) */
+ dht_hash_table_handle hash_handle; /* shared hash table handle */
+ dsa_pointer dsa_pages; /* dsa pointers for all kind of pages */
+ int nentries; /* number of entries in pagetable */
+ int maxentries; /* limit on same to meet maxbytes */
+ int npages; /* number of exact entries in pagetable */
+ int nchunks; /* number of lossy entries in pagetable */
+ int item_count; /* total item in dsa_pages */
+ bool inited; /* set true after leader converts page */
+ /* table to dsa_pointer's array. */
};
-
/* Local function prototypes */
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage);
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage,
@@ -167,8 +178,11 @@ static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
static void tbm_lossify(TIDBitmap *tbm);
static int tbm_comparator(const void *left, const void *right);
-
-
+static bool tbm_delete_entry(TIDBitmap *tbm, BlockNumber pageno);
+static PagetableEntry* tbm_find_or_insert(TIDBitmap *tbm, BlockNumber pageno,
+ bool *found);
+static PagetableEntry* tbm_find(const TIDBitmap *tbm, BlockNumber pageno);
+static void* tbm_seq_search(TIDBitmap *tbm, void *iterator);
/*
* tbm_create - create an initially-empty bitmap
*
@@ -244,6 +258,33 @@ tbm_create_pagetable(TIDBitmap *tbm)
}
/*
+ * tbm_create_shared_pagetable
+ *
+ * Creates shared hash table using DHT for parallel bitmap scan.
+ */
+static void
+tbm_create_shared_pagetable(TIDBitmap *tbm)
+{
+ dht_parameters params = {0};
+
+ params.key_size = sizeof(BlockNumber);
+ params.entry_size = sizeof(PagetableEntry);
+ params.compare_function = memcmp;
+ params.hash_function = tag_hash;
+
+ params.tranche_id = LWLockNewTrancheId();
+
+ /* Create a dynamic hash table */
+ tbm->shared_pagetable = dht_create(tbm->area, ¶ms);
+ if (tbm->shared_pagetable == NULL)
+ elog(ERROR, "could not create hash table");
+
+ /* Get the handle so that other backend can attach using this handle */
+ tbm->hash_handle = dht_get_hash_table_handle(tbm->shared_pagetable);
+ tbm->status = TBM_HASH;
+}
+
+/*
* tbm_free - free a TIDBitmap
*/
void
@@ -255,6 +296,11 @@ tbm_free(TIDBitmap *tbm)
pfree(tbm->spages);
if (tbm->schunks)
pfree(tbm->schunks);
+
+ /* If we have shared page table then detach from it */
+ if (tbm->shared_pagetable)
+ dht_detach(tbm->shared_pagetable);
+
pfree(tbm);
}
@@ -431,6 +477,14 @@ void
tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
{
Assert(!a->iterating);
+
+ /*
+ * In case of BitmapAnd, only first node will create shared TBM
+ * and all other node will have local TBM which will be merged
+ * with first shared TBM.
+ */
+ Assert(!TBM_IS_SHARED(b));
+
/* Nothing to do if a is empty */
if (a->nentries == 0)
return;
@@ -449,12 +503,34 @@ tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
}
else
{
+ void *iterator;
+ dht_iterator dhtiterator;
HASH_SEQ_STATUS status;
PagetableEntry *apage;
Assert(a->status == TBM_HASH);
- hash_seq_init(&status, a->pagetable);
- while ((apage = (PagetableEntry *) hash_seq_search(&status)) != NULL)
+
+ /*
+ * If we are using shared page table then use DHT iterator.
+ */
+ if (TBM_IS_SHARED(a))
+ {
+ iterator = &dhtiterator;
+ dht_iterate_begin(a->shared_pagetable, &dhtiterator, false);
+ }
+ else
+ {
+ iterator = &status;
+ hash_seq_init(&status, a->pagetable);
+ }
+
+ /*
+ * scan complete hash table using unified tbm_seq_search function this
+ * function will take care to scan DHT if it's shared page table
+ * otherwise dynahash.
+ */
+ while ((apage =
+ (PagetableEntry *) tbm_seq_search(a, iterator)) != NULL)
{
if (tbm_intersect_page(a, apage, b))
{
@@ -464,12 +540,21 @@ tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
else
a->npages--;
a->nentries--;
- if (hash_search(a->pagetable,
- (void *) &apage->blockno,
- HASH_REMOVE, NULL) == NULL)
+
+ /*
+ * If we are using shared hash then we need to
+ * release the lock on element.
+ */
+ if (TBM_IS_SHARED(a))
+ dht_iterate_release(&dhtiterator);
+
+ if (!tbm_delete_entry(a, apage->blockno))
elog(ERROR, "hash table corrupted");
}
}
+
+ if (TBM_IS_SHARED(a))
+ dht_iterate_end(&dhtiterator);
}
}
@@ -579,7 +664,7 @@ tbm_is_empty(const TIDBitmap *tbm)
* contents repeatedly, including parallel scans.
*/
TBMIterator *
-tbm_begin_iterate(TIDBitmap *tbm)
+tbm_begin_iterate(TIDBitmap *tbm, ParallelTIDBitmap *parallel_info)
{
TBMIterator *iterator;
@@ -592,11 +677,16 @@ tbm_begin_iterate(TIDBitmap *tbm)
iterator->tbm = tbm;
/*
- * Initialize iteration pointers.
+ * Initialize iteration pointers, only if it's not shared tbm.
+ * In case of shared tbm, we will copy these values from
+ * shared iterator before calling tbm_iterate.
*/
- iterator->spageptr = 0;
- iterator->schunkptr = 0;
- iterator->schunkbit = 0;
+ if (!TBM_IS_SHARED(tbm))
+ {
+ iterator->spageptr = 0;
+ iterator->schunkptr = 0;
+ iterator->schunkbit = 0;
+ }
/*
* If we have a hashtable, create and fill the sorted page lists, unless
@@ -606,7 +696,6 @@ tbm_begin_iterate(TIDBitmap *tbm)
*/
if (tbm->status == TBM_HASH && !tbm->iterating)
{
- HASH_SEQ_STATUS status;
PagetableEntry *page;
int npages;
int nchunks;
@@ -620,15 +709,84 @@ tbm_begin_iterate(TIDBitmap *tbm)
MemoryContextAlloc(tbm->mcxt,
tbm->nchunks * sizeof(PagetableEntry *));
- hash_seq_init(&status, tbm->pagetable);
- npages = nchunks = 0;
- while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL)
+ /*
+ * If we have shared TBM means we are running in parallel mode.
+ * So iterate over DHT and construct page and chunk array.
+ *
+ * First leader worker will create array of dsa pointers which
+ * will holds dsa pointers for both pages and chunks, later
+ * while converting to local pointers we will identify them
+ * and copy in their respective array.
+ */
+ if (TBM_IS_SHARED(tbm))
{
- if (page->ischunk)
- tbm->schunks[nchunks++] = page;
- else
- tbm->spages[npages++] = page;
+ dsa_pointer *dsa_spages;
+ dht_hash_table_item *item;
+ int ncount = 0;
+ int i;
+
+ /*
+ * Iterate over DHT and create array of dsa_pointers.
+ * Only leader will perform this step after that inited
+ * flag will be set.
+ */
+ if (!(parallel_info->inited) &&
+ (tbm->npages > 0 || tbm->nchunks > 0))
+ {
+ dht_iterator dhtiterator;
+ dsa_pointer dsa_page;
+
+ parallel_info->dsa_pages = dsa_allocate(tbm->area,
+ (tbm->nchunks + tbm->npages) * sizeof(dsa_pointer));
+
+ dsa_spages =
+ dsa_get_address(tbm->area, parallel_info->dsa_pages);
+
+ dht_iterate_begin(tbm->shared_pagetable, &dhtiterator, false);
+ while ((dsa_page = dht_iterate_next_dsa(&dhtiterator)) !=
+ InvalidDsaPointer)
+ dsa_spages[ncount++] = dsa_page;
+
+ parallel_info->inited = true;
+ parallel_info->item_count = ncount;
+ }
+
+ /*
+ * This step will be done by all the workers including leader.
+ * Here we need to convert array of dsa pointers to local
+ * page and chunk array.
+ */
+ dsa_spages = dsa_get_address(tbm->area, parallel_info->dsa_pages);
+ npages = nchunks = 0;
+ for (i = 0; i < parallel_info->item_count; i++)
+ {
+ item = dsa_get_address(tbm->area, dsa_spages[i]);
+ page = (PagetableEntry*)&(item->entry);
+
+ if (page->ischunk)
+ tbm->schunks[nchunks++] = page;
+ else
+ tbm->spages[npages++] = page;
+ }
+ }
+ else
+ {
+ HASH_SEQ_STATUS status;
+
+ /* Process local hash table, if we are not in parallel mode */
+ npages = nchunks = 0;
+
+ hash_seq_init(&status, tbm->pagetable);
+ while ((page =
+ (PagetableEntry *) hash_seq_search(&status)) != NULL)
+ {
+ if (page->ischunk)
+ tbm->schunks[nchunks++] = page;
+ else
+ tbm->spages[npages++] = page;
+ }
}
+
Assert(npages == tbm->npages);
Assert(nchunks == tbm->nchunks);
if (npages > 1)
@@ -791,11 +949,18 @@ tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
return page;
}
- page = (PagetableEntry *) hash_search(tbm->pagetable,
- (void *) &pageno,
- HASH_FIND, NULL);
+ page = (PagetableEntry *) tbm_find(tbm, pageno);
if (page == NULL)
return NULL;
+
+ /*
+ * If it's from shared hash table then release the entry.
+ * Only one worker is building hash table so it's okay to
+ * release it here.
+ */
+ if (TBM_IS_SHARED(tbm))
+ dht_release(tbm->shared_pagetable, (void*)page);
+
if (page->ischunk)
return NULL; /* don't want a lossy chunk header */
return page;
@@ -815,7 +980,11 @@ tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
PagetableEntry *page;
bool found;
- if (tbm->status == TBM_EMPTY)
+ /*
+ * Use fixed slot only if it's local tidbitmap, If shared bitmap
+ * then directly insert into shared hash table.
+ */
+ if ((tbm->status == TBM_EMPTY) && !TBM_IS_SHARED(tbm))
{
/* Use the fixed slot */
page = &tbm->entry1;
@@ -824,6 +993,7 @@ tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
}
else
{
+ /* In case of shared TBM, status will never be TBM_ONE_PAGE */
if (tbm->status == TBM_ONE_PAGE)
{
page = &tbm->entry1;
@@ -833,10 +1003,17 @@ tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
tbm_create_pagetable(tbm);
}
+ /*
+ * In case of parallel bitmap scan, we don't switch from TBM_EMPTY
+ * to TBM_ONE_PAGE. So even if we are here we may not have hash
+ * table ready, so if tbm->status is not yet TBM_HASH then create
+ * shared page table.
+ */
+ if (tbm->status != TBM_HASH && TBM_IS_SHARED(tbm))
+ tbm_create_shared_pagetable(tbm);
+
/* Look up or create an entry */
- page = (PagetableEntry *) hash_search(tbm->pagetable,
- (void *) &pageno,
- HASH_ENTER, &found);
+ page = tbm_find_or_insert(tbm, pageno, &found);
}
/* Initialize it if not present before */
@@ -849,6 +1026,10 @@ tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
tbm->npages++;
}
+ /* Release the entry lock if it's from shared hash table */
+ if (page && TBM_IS_SHARED(tbm))
+ dht_release(tbm->shared_pagetable, (void*)page);
+
return page;
}
@@ -869,9 +1050,17 @@ tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
bitno = pageno % PAGES_PER_CHUNK;
chunk_pageno = pageno - bitno;
- page = (PagetableEntry *) hash_search(tbm->pagetable,
- (void *) &chunk_pageno,
- HASH_FIND, NULL);
+
+ page = tbm_find(tbm, chunk_pageno);
+
+ /*
+ * If entry is from shared page table then release the entry.
+ * Currently only one worker is building the bitmap so it's
+ * fine to release it here.
+ */
+ if (page && TBM_IS_SHARED(tbm))
+ dht_release(tbm->shared_pagetable, (void*)page);
+
if (page != NULL && page->ischunk)
{
int wordnum = WORDNUM(bitno);
@@ -901,7 +1090,13 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
/* We force the bitmap into hashtable mode whenever it's lossy */
if (tbm->status != TBM_HASH)
- tbm_create_pagetable(tbm);
+ {
+ /* Create shared page table if we are in parallel mode. */
+ if (TBM_IS_SHARED(tbm))
+ tbm_create_shared_pagetable(tbm);
+ else
+ tbm_create_pagetable(tbm);
+ }
bitno = pageno % PAGES_PER_CHUNK;
chunk_pageno = pageno - bitno;
@@ -912,20 +1107,16 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
*/
if (bitno != 0)
{
- if (hash_search(tbm->pagetable,
- (void *) &pageno,
- HASH_REMOVE, NULL) != NULL)
+ if (tbm_delete_entry(tbm, pageno))
{
- /* It was present, so adjust counts */
- tbm->nentries--;
- tbm->npages--; /* assume it must have been non-lossy */
+ /* It was present, so adjust counts */
+ tbm->nentries--;
+ tbm->npages--; /* assume it must have been non-lossy */
}
}
/* Look up or create entry for chunk-header page */
- page = (PagetableEntry *) hash_search(tbm->pagetable,
- (void *) &chunk_pageno,
- HASH_ENTER, &found);
+ page = (PagetableEntry *)tbm_find_or_insert(tbm, chunk_pageno, &found);
/* Initialize it if not present before */
if (!found)
@@ -954,6 +1145,10 @@ tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
wordnum = WORDNUM(bitno);
bitnum = BITNUM(bitno);
page->words[wordnum] |= ((bitmapword) 1 << bitnum);
+
+ /* Unlock an entry which was locked by dht_find_or_insert. */
+ if (TBM_IS_SHARED(tbm))
+ dht_release(tbm->shared_pagetable, (void*)page);
}
/*
@@ -964,21 +1159,28 @@ tbm_lossify(TIDBitmap *tbm)
{
HASH_SEQ_STATUS status;
PagetableEntry *page;
+ dht_iterator dhtiterator;
+ void *iterator;
- /*
- * XXX Really stupid implementation: this just lossifies pages in
- * essentially random order. We should be paying some attention to the
- * number of bits set in each page, instead.
- *
- * Since we are called as soon as nentries exceeds maxentries, we should
- * push nentries down to significantly less than maxentries, or else we'll
- * just end up doing this again very soon. We shoot for maxentries/2.
- */
Assert(!tbm->iterating);
Assert(tbm->status == TBM_HASH);
- hash_seq_init(&status, tbm->pagetable);
- while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL)
+ /*
+ * If we are using shared page table then use DHT iterator otherwise
+ * dyna hash iterator
+ */
+ if (TBM_IS_SHARED(tbm))
+ {
+ iterator = &dhtiterator;
+ dht_iterate_begin(tbm->shared_pagetable, &dhtiterator, false);
+ }
+ else
+ {
+ iterator = &status;
+ hash_seq_init(&status, tbm->pagetable);
+ }
+
+ while ((page = (PagetableEntry *) tbm_seq_search(tbm, iterator)) != NULL)
{
if (page->ischunk)
continue; /* already a chunk header */
@@ -990,21 +1192,23 @@ tbm_lossify(TIDBitmap *tbm)
if ((page->blockno % PAGES_PER_CHUNK) == 0)
continue;
+ /* If we are using shared hash then release the lock on element. */
+ if (TBM_IS_SHARED(tbm))
+ dht_iterate_release(&dhtiterator);
+
/* This does the dirty work ... */
tbm_mark_page_lossy(tbm, page->blockno);
if (tbm->nentries <= tbm->maxentries / 2)
{
/* we have done enough */
- hash_seq_term(&status);
+ if (TBM_IS_SHARED(tbm))
+ dht_iterate_end(&dhtiterator);
+ else
+ hash_seq_term(&status);
+
break;
}
-
- /*
- * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
- * hashtable. We can continue the same seq_search scan since we do
- * not care whether we visit lossy chunks or not.
- */
}
/*
@@ -1036,3 +1240,171 @@ tbm_comparator(const void *left, const void *right)
return 1;
return 0;
}
+
+/*
+ * tbm_attach_to_pagetable
+ *
+ * Attach worker to shared TID bitmap created by leader worker.
+ */
+void
+tbm_attach_to_pagetable(TIDBitmap *tbm, ParallelTIDBitmap *stbm)
+{
+ dht_parameters params = {0};
+
+ params.key_size = sizeof(BlockNumber);
+ params.entry_size = sizeof(PagetableEntry);
+ params.compare_function = memcmp;
+ params.hash_function = tag_hash;
+
+ tbm->shared_pagetable = dht_attach(tbm->area, ¶ms, stbm->hash_handle);
+
+ tbm->status = TBM_HASH;
+ tbm->nchunks = stbm->nchunks;
+ tbm->nentries = stbm->nentries;
+ tbm->npages = stbm->npages;
+ tbm->maxentries = stbm->maxentries;
+ tbm->shared = true;
+}
+
+/*
+ * tbm_update_shared_members
+ *
+ * Restore leaders private tbm state to shared location. This must
+ * be called before waking up the other worker.
+ */
+void
+tbm_update_shared_members(TIDBitmap *tbm, ParallelTIDBitmap *parallel_tbm)
+{
+ /*
+ * Copy private information to shared location before
+ * waking up the other workers.
+ */
+ parallel_tbm->maxentries = tbm->maxentries;
+ parallel_tbm->nchunks = tbm->nchunks;
+ parallel_tbm->nentries = tbm->nentries;
+ parallel_tbm->npages = tbm->npages;
+ parallel_tbm->hash_handle = tbm->hash_handle;
+}
+
+/*
+ * tbm_delete_entry
+ *
+ * Unified function to delete an entry from tbm page table
+ * if tbm is shared then it will operate on from shared hash
+ * table otherwise on local hash table.
+ */
+static bool
+tbm_delete_entry(TIDBitmap *tbm, BlockNumber pageno)
+{
+ bool result = false;
+ if (TBM_IS_SHARED(tbm))
+ {
+ /* Look up or create an entry */
+ if (dht_delete_key(tbm->shared_pagetable, (void *) &pageno))
+ result = true;
+ }
+ else
+ {
+ if (hash_search(tbm->pagetable,
+ (void *) &pageno,
+ HASH_REMOVE, NULL) != NULL)
+ result = true;
+ }
+
+ return result;
+}
+
+/*
+ * tbm_find_or_insert
+ *
+ * Unified function to find or insert an entry in page table.
+ * If tbm is shared then it will operate on from shared hash
+ * table otherwise on local hash table.
+ */
+static PagetableEntry*
+tbm_find_or_insert(TIDBitmap *tbm, BlockNumber chunk_pageno, bool *found)
+{
+ PagetableEntry *page;
+
+ if (TBM_IS_SHARED(tbm))
+ page = (PagetableEntry *) dht_find_or_insert(tbm->shared_pagetable,
+ (void *) &chunk_pageno,
+ found);
+ else
+ page = (PagetableEntry *) hash_search(tbm->pagetable,
+ (void *) &chunk_pageno,
+ HASH_ENTER, found);
+
+ return page;
+}
+
+/*
+ * tbm_find
+ *
+ * Unified function to find an entry from tbm page table
+ * if tbm is shared then it will operate on shared hash
+ * table otherwise on local hash table.
+ */
+static PagetableEntry*
+tbm_find(const TIDBitmap *tbm, BlockNumber pageno)
+{
+ PagetableEntry *page;
+
+ if (TBM_IS_SHARED(tbm))
+ page = (PagetableEntry *) dht_find(tbm->shared_pagetable,
+ (void *) &pageno,
+ false);
+ else
+ page = (PagetableEntry *) hash_search(tbm->pagetable,
+ (void *) &pageno,
+ HASH_FIND, NULL);
+ return page;
+}
+
+/*
+ * tbm_set_parallel
+ *
+ * Mark tidbitmap as shared and also store DSA area in it.
+ * marking tidbitmap as shared is indication that this tidbitmap
+ * should be created in shared memory. DSA area will be used for
+ * creating bitmap using dynamic shared memory hash table.
+ */
+void
+tbm_set_parallel(TIDBitmap *tbm, void *area)
+{
+ tbm->shared = true;
+ tbm->area = (dsa_area*)area;
+}
+
+/*
+ * tbm_seq_search
+ *
+ * Unified function to scan full tbm page table
+ * if tbm is shared then it will operate on shared hash
+ * table otherwise on local hash table.
+ */
+static void*
+tbm_seq_search(TIDBitmap *tbm, void *iterator)
+{
+ if (TBM_IS_SHARED(tbm))
+ {
+ dht_iterator *dhtiterator = (dht_iterator*)iterator;
+
+ return dht_iterate_next(dhtiterator);
+ }
+ else
+ {
+ HASH_SEQ_STATUS *status = (HASH_SEQ_STATUS*)iterator;
+
+ return hash_seq_search(status);
+ }
+}
+
+/*
+ * tbm_estimate_parallel_tidbitmap
+ * Estimate size of shared TIDBitmap related info.
+ */
+Size tbm_estimate_parallel_tidbitmap(Size size)
+{
+ return add_size(size, sizeof(ParallelTIDBitmap));
+}
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index e42ef98..058e55a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -126,6 +126,7 @@ static void subquery_push_qual(Query *subquery,
static void recurse_push_qual(Node *setOp, Query *topquery,
RangeTblEntry *rte, Index rti, Node *qual);
static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
+static int compute_parallel_worker(RelOptInfo *rel, BlockNumber pages);
/*
@@ -678,49 +679,7 @@ create_plain_partial_paths(PlannerInfo *root, RelOptInfo *rel)
{
int parallel_workers;
- /*
- * If the user has set the parallel_workers reloption, use that; otherwise
- * select a default number of workers.
- */
- if (rel->rel_parallel_workers != -1)
- parallel_workers = rel->rel_parallel_workers;
- else
- {
- int parallel_threshold;
-
- /*
- * If this relation is too small to be worth a parallel scan, just
- * return without doing anything ... unless it's an inheritance child.
- * In that case, we want to generate a parallel path here anyway. It
- * might not be worthwhile just for this relation, but when combined
- * with all of its inheritance siblings it may well pay off.
- */
- if (rel->pages < (BlockNumber) min_parallel_relation_size &&
- rel->reloptkind == RELOPT_BASEREL)
- return;
-
- /*
- * Select the number of workers based on the log of the size of the
- * relation. This probably needs to be a good deal more
- * sophisticated, but we need something here for now. Note that the
- * upper limit of the min_parallel_relation_size GUC is chosen to
- * prevent overflow here.
- */
- parallel_workers = 1;
- parallel_threshold = Max(min_parallel_relation_size, 1);
- while (rel->pages >= (BlockNumber) (parallel_threshold * 3))
- {
- parallel_workers++;
- parallel_threshold *= 3;
- if (parallel_threshold > INT_MAX / 3)
- break; /* avoid overflow */
- }
- }
-
- /*
- * In no case use more than max_parallel_workers_per_gather workers.
- */
- parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);
+ parallel_workers = compute_parallel_worker(rel, rel->pages);
/* If any limit was set to zero, the user doesn't want a parallel scan. */
if (parallel_workers <= 0)
@@ -2866,6 +2825,84 @@ remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel)
}
}
+/*
+ * create_partial_bitmap_paths
+ * Build partial access paths for parallel scan of a plain relation
+ */
+void
+create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
+ Path *bitmapqual)
+{
+ int parallel_workers;
+ double pages_fetched;
+
+ /* Compute heap pages for bitmap heap scan */
+ pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
+ NULL, NULL);
+
+ parallel_workers = compute_parallel_worker(rel, pages_fetched);
+
+ /* If any limit was set to zero, the user doesn't want a parallel scan. */
+ if (parallel_workers <= 0)
+ return;
+
+ add_partial_path(rel, (Path*)create_bitmap_heap_path(root, rel,
+ bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
+}
+
+static int
+compute_parallel_worker(RelOptInfo *rel, BlockNumber pages)
+{
+ int parallel_workers;
+
+ /*
+ * If the user has set the parallel_workers reloption, use that; otherwise
+ * select a default number of workers.
+ */
+ if (rel->rel_parallel_workers != -1)
+ parallel_workers = rel->rel_parallel_workers;
+ else
+ {
+ int parallel_threshold;
+
+ /*
+ * If this relation is too small to be worth a parallel scan, just
+ * return without doing anything ... unless it's an inheritance child.
+ * In that case, we want to generate a parallel path here anyway. It
+ * might not be worthwhile just for this relation, but when combined
+ * with all of its inheritance siblings it may well pay off.
+ */
+ if (pages < (BlockNumber) min_parallel_relation_size &&
+ rel->reloptkind == RELOPT_BASEREL)
+ return 0;
+
+ /*
+ * Select the number of workers based on the log of the size of the
+ * relation. This probably needs to be a good deal more
+ * sophisticated, but we need something here for now. Note that the
+ * upper limit of the min_parallel_relation_size GUC is chosen to
+ * prevent overflow here.
+ */
+ parallel_workers = 1;
+ parallel_threshold = Max(min_parallel_relation_size, 1);
+ while (pages >= (BlockNumber) (parallel_threshold * 3))
+ {
+ parallel_workers++;
+ parallel_threshold *= 3;
+ if (parallel_threshold > INT_MAX / 3)
+ break; /* avoid overflow */
+ }
+ }
+
+ /*
+ * In no case use more than max_parallel_workers_per_gather workers.
+ */
+ parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);
+
+ return parallel_workers;
+}
+
+
/*****************************************************************************
* DEBUG SUPPORT
*****************************************************************************/
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 2a49639..c08997a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -161,7 +161,7 @@ static Selectivity get_foreign_key_join_selectivity(PlannerInfo *root,
static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
static double relation_byte_size(double tuples, int width);
static double page_size(double tuples, int width);
-
+static Cost adjust_cost_for_parallelism(Path *path, Cost cpu_run_cost);
/*
* clamp_row_est
@@ -237,44 +237,7 @@ cost_seqscan(Path *path, PlannerInfo *root,
/* Adjust costing for parallelism, if used. */
if (path->parallel_workers > 0)
- {
- double parallel_divisor = path->parallel_workers;
- double leader_contribution;
-
- /*
- * Early experience with parallel query suggests that when there is
- * only one worker, the leader often makes a very substantial
- * contribution to executing the parallel portion of the plan, but as
- * more workers are added, it does less and less, because it's busy
- * reading tuples from the workers and doing whatever non-parallel
- * post-processing is needed. By the time we reach 4 workers, the
- * leader no longer makes a meaningful contribution. Thus, for now,
- * estimate that the leader spends 30% of its time servicing each
- * worker, and the remainder executing the parallel plan.
- */
- leader_contribution = 1.0 - (0.3 * path->parallel_workers);
- if (leader_contribution > 0)
- parallel_divisor += leader_contribution;
-
- /*
- * In the case of a parallel plan, the row count needs to represent
- * the number of tuples processed per worker. Otherwise, higher-level
- * plan nodes that appear below the gather will be costed incorrectly,
- * because they'll anticipate receiving more rows than any given copy
- * will actually get.
- */
- path->rows = clamp_row_est(path->rows / parallel_divisor);
-
- /* The CPU cost is divided among all the workers. */
- cpu_run_cost /= parallel_divisor;
-
- /*
- * It may be possible to amortize some of the I/O cost, but probably
- * not very much, because most operating systems already do aggressive
- * prefetching. For now, we assume that the disk run cost can't be
- * amortized at all.
- */
- }
+ cpu_run_cost = adjust_cost_for_parallelism(path, cpu_run_cost);
path->startup_cost = startup_cost;
path->total_cost = startup_cost + cpu_run_cost + disk_run_cost;
@@ -831,10 +794,10 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
Cost startup_cost = 0;
Cost run_cost = 0;
Cost indexTotalCost;
- Selectivity indexSelectivity;
QualCost qpqual_cost;
Cost cpu_per_tuple;
Cost cost_per_page;
+ Cost cpu_run_cost;
double tuples_fetched;
double pages_fetched;
double spc_seq_page_cost,
@@ -855,13 +818,12 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
if (!enable_bitmapscan)
startup_cost += disable_cost;
- /*
- * Fetch total cost of obtaining the bitmap, as well as its total
- * selectivity.
- */
- cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
+ pages_fetched = compute_bitmap_pages(root, baserel, bitmapqual,
+ loop_count, &indexTotalCost,
+ &tuples_fetched);
startup_cost += indexTotalCost;
+ T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
/* Fetch estimated page costs for tablespace containing table. */
get_tablespace_page_costs(baserel->reltablespace,
@@ -869,41 +831,6 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
&spc_seq_page_cost);
/*
- * Estimate number of main-table pages fetched.
- */
- tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
-
- T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
-
- if (loop_count > 1)
- {
- /*
- * For repeated bitmap scans, scale up the number of tuples fetched in
- * the Mackert and Lohman formula by the number of scans, so that we
- * estimate the number of pages fetched by all the scans. Then
- * pro-rate for one scan.
- */
- pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
- baserel->pages,
- get_indexpath_pages(bitmapqual),
- root);
- pages_fetched /= loop_count;
- }
- else
- {
- /*
- * For a single scan, the number of heap pages that need to be fetched
- * is the same as the Mackert and Lohman formula for the case T <= b
- * (ie, no re-reads needed).
- */
- pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
- }
- if (pages_fetched >= T)
- pages_fetched = T;
- else
- pages_fetched = ceil(pages_fetched);
-
- /*
* For small numbers of pages we should charge spc_random_page_cost
* apiece, while if nearly all the table's pages are being read, it's more
* appropriate to charge spc_seq_page_cost apiece. The effect is
@@ -932,8 +859,13 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
startup_cost += qpqual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
+ cpu_run_cost = cpu_per_tuple * tuples_fetched;
- run_cost += cpu_per_tuple * tuples_fetched;
+ /* Adjust costing for parallelism, if used. */
+ if (path->parallel_workers > 0)
+ cpu_run_cost = adjust_cost_for_parallelism(path, cpu_run_cost);
+
+ run_cost += cpu_run_cost;
/* tlist eval costs are paid per output row, not per tuple scanned */
startup_cost += path->pathtarget->cost.startup;
@@ -944,6 +876,56 @@ cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
}
/*
+ * adjust_cost_for_parallelism
+ *
+ * Adjust the cpu cost based on number of parallel workers, also update
+ * the number of rows processed at each worker.
+ */
+static Cost
+adjust_cost_for_parallelism(Path *path, Cost cpu_run_cost)
+{
+ double parallel_divisor = path->parallel_workers;
+ double leader_contribution;
+ Cost cpu_cost = cpu_run_cost;
+
+ /*
+ * Early experience with parallel query suggests that when there is
+ * only one worker, the leader often makes a very substantial
+ * contribution to executing the parallel portion of the plan, but as
+ * more workers are added, it does less and less, because it's busy
+ * reading tuples from the workers and doing whatever non-parallel
+ * post-processing is needed. By the time we reach 4 workers, the
+ * leader no longer makes a meaningful contribution. Thus, for now,
+ * estimate that the leader spends 30% of its time servicing each
+ * worker, and the remainder executing the parallel plan.
+ */
+ leader_contribution = 1.0 - (0.3 * path->parallel_workers);
+ if (leader_contribution > 0)
+ parallel_divisor += leader_contribution;
+
+ /*
+ * In the case of a parallel plan, the row count needs to represent
+ * the number of tuples processed per worker. Otherwise, higher-level
+ * plan nodes that appear below the gather will be costed incorrectly,
+ * because they'll anticipate receiving more rows than any given copy
+ * will actually get.
+ */
+ path->rows = clamp_row_est(path->rows / parallel_divisor);
+
+ /* The CPU cost is divided among all the workers. */
+ cpu_cost /= parallel_divisor;
+
+ /*
+ * It may be possible to amortize some of the I/O cost, but probably
+ * not very much, because most operating systems already do aggressive
+ * prefetching. For now, we assume that the disk run cost can't be
+ * amortized at all.
+ */
+
+ return cpu_cost;
+}
+
+/*
* cost_bitmap_tree_node
* Extract cost and selectivity from a bitmap tree node (index/and/or)
*/
@@ -4765,3 +4747,69 @@ page_size(double tuples, int width)
{
return ceil(relation_byte_size(tuples, width) / BLCKSZ);
}
+
+/*
+ * compute_bitmap_pages
+ *
+ * compute number of pages fetched from heap in bitmap heap scan.
+ */
+double
+compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual,
+ int loop_count, Cost *cost, double *tuple)
+{
+ Cost indexTotalCost;
+ Selectivity indexSelectivity;
+ double T;
+ double pages_fetched;
+ double tuples_fetched;
+
+ /*
+ * Fetch total cost of obtaining the bitmap, as well as its total
+ * selectivity.
+ */
+ cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
+
+ /*
+ * Estimate number of main-table pages fetched.
+ */
+ tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
+
+ T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
+
+ if (loop_count > 1)
+ {
+ /*
+ * For repeated bitmap scans, scale up the number of tuples fetched in
+ * the Mackert and Lohman formula by the number of scans, so that we
+ * estimate the number of pages fetched by all the scans. Then
+ * pro-rate for one scan.
+ */
+ pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
+ baserel->pages,
+ get_indexpath_pages(bitmapqual),
+ root);
+ pages_fetched /= loop_count;
+ }
+ else
+ {
+ /*
+ * For a single scan, the number of heap pages that need to be fetched
+ * is the same as the Mackert and Lohman formula for the case T <= b
+ * (ie, no re-reads needed).
+ */
+ pages_fetched =
+ (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
+ }
+
+ if (pages_fetched >= T)
+ pages_fetched = T;
+ else
+ pages_fetched = ceil(pages_fetched);
+
+ if (cost)
+ *cost = indexTotalCost;
+ if (tuple)
+ *tuple = tuples_fetched;
+
+ return pages_fetched;
+}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 2952bfb..1a7bde0 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -337,8 +337,12 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
bpath = create_bitmap_heap_path(root, rel, bitmapqual,
- rel->lateral_relids, 1.0);
+ rel->lateral_relids, 1.0, 0);
add_path(rel, (Path *) bpath);
+
+ /* create a partial bitmap heap path */
+ if (rel->consider_parallel && rel->lateral_relids == NULL)
+ create_partial_bitmap_paths(root, rel, bitmapqual);
}
/*
@@ -410,7 +414,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
required_outer = get_bitmap_tree_required_outer(bitmapqual);
loop_count = get_loop_count(root, rel->relid, required_outer);
bpath = create_bitmap_heap_path(root, rel, bitmapqual,
- required_outer, loop_count);
+ required_outer, loop_count, 0);
add_path(rel, (Path *) bpath);
}
}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 47158f6..4ffcf87 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2803,7 +2803,7 @@ create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
plan->plan_rows =
clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
plan->plan_width = 0; /* meaningless */
- plan->parallel_aware = false;
+ plan->parallel_aware = bitmapqual->parallel_aware;
*qual = get_actual_clauses(ipath->indexclauses);
*indexqual = get_actual_clauses(ipath->indexquals);
foreach(l, ipath->indexinfo->indpred)
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index abb7507..0801b6e 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -47,7 +47,6 @@ typedef enum
static List *translate_sub_tlist(List *tlist, int relid);
-
/*****************************************************************************
* MISC. PATH UTILITIES
*****************************************************************************/
@@ -1071,7 +1070,8 @@ create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
Relids required_outer,
- double loop_count)
+ double loop_count,
+ int parallel_degree)
{
BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
@@ -1080,11 +1080,10 @@ create_bitmap_heap_path(PlannerInfo *root,
pathnode->path.pathtarget = rel->reltarget;
pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
required_outer);
- pathnode->path.parallel_aware = false;
+ pathnode->path.parallel_aware = parallel_degree > 0 ? true : false;
pathnode->path.parallel_safe = rel->consider_parallel;
- pathnode->path.parallel_workers = 0;
+ pathnode->path.parallel_workers = parallel_degree;
pathnode->path.pathkeys = NIL; /* always unordered */
-
pathnode->bitmapqual = bitmapqual;
cost_bitmap_heap_scan(&pathnode->path, root, rel,
@@ -3192,7 +3191,7 @@ reparameterize_path(PlannerInfo *root, Path *path,
rel,
bpath->bitmapqual,
required_outer,
- loop_count);
+ loop_count, 0);
}
case T_SubqueryScan:
{
diff --git a/src/backend/postmaster/pgstat.c b/src/backend/postmaster/pgstat.c
index 5c6cb6b..3e48afe 100644
--- a/src/backend/postmaster/pgstat.c
+++ b/src/backend/postmaster/pgstat.c
@@ -3382,6 +3382,9 @@ pgstat_get_wait_ipc(WaitEventIPC w)
case WAIT_EVENT_PARALLEL_FINISH:
event_name = "ParallelFinish";
break;
+ case WAIT_EVENT_PARALLEL_BITMAP_SCAN:
+ event_name = "ParallelBitmapScan";
+ break;
case WAIT_EVENT_SAFE_SNAPSHOT:
event_name = "SafeSnapshot";
break;
diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 0d12bbb..7cf0a3c 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -23,7 +23,6 @@
#include "utils/relcache.h"
#include "utils/snapshot.h"
-
/* "options" flag bits for heap_insert */
#define HEAP_INSERT_SKIP_WAL 0x0001
#define HEAP_INSERT_SKIP_FSM 0x0002
@@ -178,6 +177,7 @@ extern void simple_heap_update(Relation relation, ItemPointer otid,
HeapTuple tup);
extern void heap_sync(Relation relation);
+extern void heap_bm_update_snapshot(HeapScanDesc scan, Snapshot snapshot);
/* in heap/pruneheap.c */
extern void heap_page_prune_opt(Relation relation, Buffer buffer);
diff --git a/src/include/executor/nodeBitmapHeapscan.h b/src/include/executor/nodeBitmapHeapscan.h
index 0ed9c78..8afecb7 100644
--- a/src/include/executor/nodeBitmapHeapscan.h
+++ b/src/include/executor/nodeBitmapHeapscan.h
@@ -15,10 +15,17 @@
#define NODEBITMAPHEAPSCAN_H
#include "nodes/execnodes.h"
+#include "access/parallel.h"
extern BitmapHeapScanState *ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags);
extern TupleTableSlot *ExecBitmapHeapScan(BitmapHeapScanState *node);
extern void ExecEndBitmapHeapScan(BitmapHeapScanState *node);
extern void ExecReScanBitmapHeapScan(BitmapHeapScanState *node);
+extern void ExecBitmapHeapEstimate(BitmapHeapScanState *node,
+ ParallelContext *pcxt);
+extern void ExecBitmapHeapInitializeDSM(BitmapHeapScanState *node,
+ ParallelContext *pcxt);
+extern void ExecBitmapHeapInitializeWorker(BitmapHeapScanState *node,
+ shm_toc *toc);
#endif /* NODEBITMAPHEAPSCAN_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index bb1f56a..78f1ac8 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -26,6 +26,8 @@
#include "utils/sortsupport.h"
#include "utils/tuplestore.h"
#include "utils/tuplesort.h"
+#include "nodes/tidbitmap.h"
+#include "storage/condition_variable.h"
/* ----------------
@@ -1393,6 +1395,72 @@ typedef struct IndexOnlyScanState
long ioss_HeapFetches;
} IndexOnlyScanState;
+/*
+ * Stores the information about current position of the
+ * shared iterator used for parallel bitmap heap scan.
+ */
+typedef struct
+{
+ slock_t mutex; /* mutual exclusion for below three fields */
+ int spageptr; /* next spages index */
+ int schunkptr; /* next schunks index */
+ int schunkbit; /* next bit to check in current schunk */
+} ParallelIterator;
+
+/* ----------------
+ * PBMState information : Current status of the TIDBitmap creation during
+ * parallel bitmap heap scan.
+ *
+ * PBM_INITIAL TIDBitmap creation is not yet started, so
+ * first worker to see this state will become
+ * leader and will create TIDbitmap. This will
+ * also set the state to PBM_INPROGRESS.
+ * PBM_INPROGRESS TIDBitmap creation is already in progress,
+ * so workers need to sleep until leader set the
+ * state to PBM_FINISHED and wake us up.
+ * PBM_FINISHED TIDBitmap creation is done, so now all worker
+ * can proceed to iterate over TIDBitmap.
+ * ----------------
+ */
+typedef enum
+{
+ PBM_INITIAL,
+ PBM_INPROGRESS,
+ PBM_FINISHED
+}PBMState;
+
+/* ----------------
+ * ParallelBitmapInfo information
+ * relid OID of relation to scan
+ * tbmiterator main iterator
+ * prefetch_mutex mutual exclusion for prefetch members
+ * (prefetch_iterator, prefetch_pages and
+ * prefetch_target)
+ * prefetch_iterator iterator for scanning ahead of current pages
+ * prefetch_pages # pages prefetch iterator is ahead of current
+ * prefetch_target current target prefetch distance
+ * state_mutex mutual exclusion for state field
+ * cv conditional wait variable
+ * state current state of the TIDBitmap
+ * ptbm_offset offset in bytes of ParallelTIDBitmap.
+ * phs_snapshot_data snapshot data shared to worker
+ * ----------------
+ */
+typedef struct ParallelBitmapInfo
+{
+ Oid relid;
+ ParallelIterator tbmiterator;
+ ParallelIterator prefetch_iterator;
+ slock_t prefetch_mutex;
+ int prefetch_pages;
+ int prefetch_target;
+ slock_t state_mutex;
+ ConditionVariable cv;
+ PBMState state;
+ Size ptbm_offset;
+ char phs_snapshot_data[FLEXIBLE_ARRAY_MEMBER];
+}ParallelBitmapInfo;
+
/* ----------------
* BitmapIndexScanState information
*
@@ -1407,6 +1475,8 @@ typedef struct IndexOnlyScanState
* RuntimeContext expr context for evaling runtime Skeys
* RelationDesc index relation descriptor
* ScanDesc index scan descriptor
+ * Parallel Under parallel Bitmap heap so need to create shared
+ * TIDBitmap
* ----------------
*/
typedef struct BitmapIndexScanState
@@ -1423,6 +1493,7 @@ typedef struct BitmapIndexScanState
ExprContext *biss_RuntimeContext;
Relation biss_RelationDesc;
IndexScanDesc biss_ScanDesc;
+ bool biss_Parallel;
} BitmapIndexScanState;
/* ----------------
@@ -1438,7 +1509,11 @@ typedef struct BitmapIndexScanState
* prefetch_pages # pages prefetch iterator is ahead of current
* prefetch_target current target prefetch distance
* prefetch_maximum maximum value for prefetch_target
- * ----------------
+ * pscan_len size of the shared memory for parallel bitmap
+ * is_leader is_leader is set true, if this worker become
+ * leader for parallel bitmap heap scan.
+ * parallel_bitmap shared memory for parallel bitmap scan
+ *----------------
*/
typedef struct BitmapHeapScanState
{
@@ -1453,6 +1528,9 @@ typedef struct BitmapHeapScanState
int prefetch_pages;
int prefetch_target;
int prefetch_maximum;
+ Size pscan_len;
+ bool is_leader;
+ ParallelBitmapInfo *parallel_bitmap;
} BitmapHeapScanState;
/* ----------------
diff --git a/src/include/nodes/tidbitmap.h b/src/include/nodes/tidbitmap.h
index 9303299..e215256 100644
--- a/src/include/nodes/tidbitmap.h
+++ b/src/include/nodes/tidbitmap.h
@@ -31,9 +31,6 @@
*/
typedef struct TIDBitmap TIDBitmap;
-/* Likewise, TBMIterator is private */
-typedef struct TBMIterator TBMIterator;
-
/* Result structure for tbm_iterate */
typedef struct
{
@@ -44,6 +41,26 @@ typedef struct
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER];
} TBMIterateResult;
+/*
+ * When iterating over a bitmap in sorted order, a TBMIterator is used to
+ * track our progress. There can be several iterators scanning the same
+ * bitmap concurrently. Note that the bitmap becomes read-only as soon as
+ * any iterator is created.
+ */
+typedef struct
+{
+ TIDBitmap *tbm; /* TIDBitmap we're iterating over */
+ int spageptr; /* next spages index */
+ int schunkptr; /* next schunks index */
+ int schunkbit; /* next bit to check in current schunk */
+ TBMIterateResult output; /* MUST BE LAST (because variable-size) */
+}TBMIterator;
+
+/*
+ * Holds shared members of TIDBitmap for parallel bitmap scan.
+ */
+typedef struct ParallelTIDBitmap ParallelTIDBitmap;
+
/* function prototypes in nodes/tidbitmap.c */
extern TIDBitmap *tbm_create(long maxbytes);
@@ -58,9 +75,14 @@ extern void tbm_union(TIDBitmap *a, const TIDBitmap *b);
extern void tbm_intersect(TIDBitmap *a, const TIDBitmap *b);
extern bool tbm_is_empty(const TIDBitmap *tbm);
-
-extern TBMIterator *tbm_begin_iterate(TIDBitmap *tbm);
+extern TBMIterator * tbm_begin_iterate(TIDBitmap *tbm,
+ ParallelTIDBitmap *parallel_info);
extern TBMIterateResult *tbm_iterate(TBMIterator *iterator);
extern void tbm_end_iterate(TBMIterator *iterator);
+extern void tbm_attach_to_pagetable(TIDBitmap *tbm, ParallelTIDBitmap *stbm);
+extern void tbm_update_shared_members(TIDBitmap *tbm,
+ ParallelTIDBitmap *parallel_tbm);
+void tbm_set_parallel(TIDBitmap *tbm, void *area);
+extern Size tbm_estimate_parallel_tidbitmap(Size size);
#endif /* TIDBITMAP_H */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 2a4df2f..e1baacc 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -183,6 +183,8 @@ extern void set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel,
double cte_rows);
extern void set_foreign_size_estimates(PlannerInfo *root, RelOptInfo *rel);
extern PathTarget *set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target);
+extern double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel,
+ Path *bitmapqual, int loop_count, Cost *cost, double *tuple);
/*
* prototypes for clausesel.c
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 71d9154..397d266 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -52,7 +52,8 @@ extern BitmapHeapPath *create_bitmap_heap_path(PlannerInfo *root,
RelOptInfo *rel,
Path *bitmapqual,
Relids required_outer,
- double loop_count);
+ double loop_count,
+ int parallel_degree);
extern BitmapAndPath *create_bitmap_and_path(PlannerInfo *root,
RelOptInfo *rel,
List *bitmapquals);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 44abe83..3264f44 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -53,6 +53,8 @@ extern RelOptInfo *standard_join_search(PlannerInfo *root, int levels_needed,
List *initial_rels);
extern void generate_gather_paths(PlannerInfo *root, RelOptInfo *rel);
+extern void create_partial_bitmap_paths(PlannerInfo *root, RelOptInfo *rel,
+ Path *bitmapqual);
#ifdef OPTIMIZER_DEBUG
extern void debug_print_rel(PlannerInfo *root, RelOptInfo *rel);
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 27be549..7f7992a 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -784,6 +784,7 @@ typedef enum
WAIT_EVENT_MQ_RECEIVE,
WAIT_EVENT_MQ_SEND,
WAIT_EVENT_PARALLEL_FINISH,
+ WAIT_EVENT_PARALLEL_BITMAP_SCAN,
WAIT_EVENT_SAFE_SNAPSHOT,
WAIT_EVENT_SYNC_REP
} WaitEventIPC;
TPCH_PBMS.pdfapplication/pdf; name=TPCH_PBMS.pdfDownload
%PDF-1.4
%��������
2 0 obj
<</Length 3 0 R/Filter/FlateDecode>>
stream
x��YK��6����90�*=-��3���4���d!�����#�d��r{����2�q�R=�*U�����/s�`,��~�����������������G5�t;���
_?.���������9J�_:*����0 n������?=�g&��&���?3&������0�H��������Q��i/� B�I6��G�v4*B^����
�Ie���Q#NL�e��N2�G{ ���
��On.�Z����Q�w��Ko?n7�q,����m����@�{I2��e���h�i
;��M���+�^OO�{���L�(�� N����Us��������� �����4�0��y�`0�����U11P�3"��u������L�2J'����+L�si;�g\1E~W"�g2B��E|a��i�]�f��8/D�`w�.�9�6���T�H�R�r�- ��3i�=�SW��ZD�1��b]4
�=�� #�zQ0��<�8��H��V����aPl�%�����s9cJ���l���Q�F��e�P������� ����%���
e�(5��@�B���KJ)^��)I5�����h���J'V�pbk�!
[2�$\|{����?F%�F�����n��\Rg���.�:(B���:��':T���F�FF�b��?3*53������T�����L@C�MM~e�n�)��Lx�����f[�if��J)Xsj� ���1�e
F ���p�lN��������R�,|�����q����Cqy>��L��;k�PT��q&V<�;��o*����n�C�����/8c�R�d������5���zK�!���}�^CU�}���J����t����u����oG��]
��Pw[��UD�cT�Q���J��mJ��#m�Na|��_)�~Q��
������;&���}��Te����3+�J�({��e��^�A+1�g������F�~!�S���z`�����a��-��C����>uCjTR�.��
��4���6d�kVA�����W����<?3�"}�m�C���6�x�K���mzTP|��-N���Hy%3]H�=��UC������h����c���}<�H���RXSW��T���~�y���5��f,�8e�)i|i��f?�bq�j���=�������w��F=�=z`r��Gv,��pn���r���'+���=i���P���T��]]��G��}�M��f�I��=�����������F�!��V�Z&��T�@6k�H�����S�YGAH�<���z.�C���|�����|<�K��uJ/�]�p�����������N����8��c�����d���~��P��Q�Dn 8''L���(y,���L&�������� Xf\�.aESd�4�}��S�����:��- z]���s\���o>�"S�����b��^�O@
�,C�l��_XV I��6]��'��0m��x����)�� ����f K�[������d� �T�����$��9������P'���I|�����������W�!�V�&��c��;�T���&�E����G�U��'|/�7j4��.!����>]rH��C�����7�����1�m��4 �����;��?D�sVD_{+�,U�$1���(4MQ�y��C Pb03W-A�l?Rm%P�"��mD���?�`)$��=G�u�X�0�l�b%�!�^e���:ZZ]e����6
0�O��J�C�V�5
�j�"C#���C��peU/gQ�� �'+0UR��<�|x��g5|�g�p�*�������d8�
endstream
endobj
3 0 obj
1793
endobj
4 0 obj
<</Type/XObject
/Subtype/Form
/BBox[ -79 395 692 395.1 ]
/Group<</S/Transparency/CS/DeviceRGB/K true>>
/Length 25
/Filter/FlateDecode
>>
stream
x�+T0P0��t.�.��@. )�
endstream
endobj
5 0 obj
<</CA 0.5
/ca 0.5
>>
endobj
7 0 obj
<</Length 8 0 R/Filter/FlateDecode/Length1 24296>>
stream
x���xS��0:k����%Y[�%[�mI�������-{�,����6���6~@x$��$8 %���6$
y!!�I���$�M��6�i~���I��6NO�����-�W�����~���+i�=�5kf��Y�����B4�$�\�1�P���B�!���G��j��J�������Y�sA��;BJ�g����g�R�"��]�m���-$����$�?u��E $���v��+�����I������W��#�8����v�5X��aH|����k�
�>"�0B*ip`xd?��F��2��,\��-H�~A��|�GC�
��)�*>F������g2�'X�I�)6�#���������r�z���<_~Aa����{�{��mC&�Q���aKQ����'4v�>����V�"���Mt�%k���_�%��z^D~���s��>t ��O�V���#���v��=Nj>��M%|�����s��_�
�~�A��G���~�p�f�W�^����1���h7��!�C{ |;:-h9I�|��.4p�q4��F��,����M�7�^�6i�n�g?�C�n*�,|N����%����m&SdV�S_{�DF=���I;df�*NG����/ZZ0��uw�k�Us���*+��e�%�E��D�'�������Lu����.V���UJ�2���h��3��l�3��qgI��)�=l'I�[a��v�~+�D �o��"��uH���<�m�v��?�r�OC��F~���d_����0�!G�$�p�����*{����������*���:f�snWL��Q�����Y����Ur gU��H���������phacu���h�u��c�Ur�+�+���2J{m:�c?�����V��4����e�a���g�����]�lgU8{�G ��]a���:��X�]���F����}�o�t�y��[S:�)�t�o������=0�>�qzzl��.8��k4�����(�HJ����k8�@SXh���hg�����-�a���v���t:��}�L��e#BBBS��v|�i � �����H��VXO ��j
�v�39�cj�9c39���;�h�-n�����jB�=����V��p
������Ao/�6��v����>{�� d!�n.@8��H�g��E+� Co��8 ���Y����M ���p�����TERGt����^R���Q_�<|a�s0��s}<i���7�E���qs��}e�T�[]Ek�W��WE�@q96��|�����/�P>j�������2��;���vk'�i��F�#,5�nr6v5QF#��@�s�5���������������D2(:6��64�Fk
a��*]eo�V��
$� ��rr+�U���T��s���`E3���l{uWU��oA�Qv�����Q�gn��hrD>�nL����I %jp&�I'���a�FN��L�<ootv9�����j�}����%�L��X����X�L�A�g"�����z3q�5r�z4x[v�L�}\��[<N�;�iymQ���Vy����t�ILf�<���K���t��;k;����eh"A��n�uP����ua6��v-<.������ D��U�x��>��x�k|�N�
9�T�H#v����J���&!4&��r�_y����I��4�� 3i����4IN�2J ���D~W�;��li�oo�<���"�apV�8+�Vh�1��9a�sM�����tMW� 3��7����%����*r����D�����'���b�q���&At���M>�T�W�O M���t��Q��Si��T/������SE�N�����*�����PU����B�>���P;�����mJ>����a��c`q��K���L�^9����Y
�8{�oVI�1�R�7#�`�l��f���]�]���L��OO_��$iC�����3��`���m9��u9����46����E<T��sFT�kmm�(�[/JJZ[]����}^��D������g���@�����N{ZfQ
��������
�+�//�+=�35��H8�c�^=qn���S�+������t7<�]R9�d{�������o
����y�o�,��x�����5�fo[�s�v4�_�?�RzQ������9�K�3�Z��t��@��e9��6��Pa��|��raa�AG2���1y��L!��}
��'�4�:�H!
�Lk��9������Nv� :'�9�y� ���������E�����NeID� B��*/�U�*)��]�s��[7DI�.����I����� A��PM ��@}gE��y�������S�u�$&���h^^|q��������j�����k�r�M���S����w)��v>JB�h��iv�r���U)���"�[��������9��jlz�����g3�L�5c����B���=d�P�����0������u���y����������-,��%c����N�L�*!�Y;}�����}`��+wnw�zu������+�KY����=%����-�^H���������6%�?���;�����6}�pndF���Y���1vw,���>�F�n-����k�k�-��,Kb���y��5Z3#x�^'pvN�X%7� :EHS1��b�����w1Z���|������]�@f���u���Wzg���g����83�<��n(��������U&�JV���?�����Z��J�B6�����+-��v~��<�����^��U0�D������9X��s�C4m��XF�P�J�0����Efg����m.�
�8�\A:L�'�g��0�Xz�-���~%���/������%��Qi�Q���A�y�0�L�p�&]�����I �8e3R *I��m�8o������q�.����8F'��`\����3J��y�EgP�!|#�:qFrD���L ae~ ;�
�?�7��8��^x�w�TL92��{� ���C�U��q���������\��a��yh6��������7jvk0�"��%r��@��%��pzzJ@���[��3�s��jL���LIA����� #��������|'���0�\���}mq������t�D��!�<D2����yRy�0
�'3�2/��2U\�.�m.5�J�J(�
e&� fS��L����t�2�D��A������SG�����N*]Z�__��x#���`�{?�)��������zEr��Q��m
9�2gCsA[��W��������K����>��z����S��B�T��E�����W�)hbA��\��N��dj)s��C�P5�P
n�5>�W�T��
h�tips��R��28� ���-��w���ds�����,�
Hy�b,l�=�ck��ua|R���kt��h��j��5�j�55�6t�&k`A
�����o
>[s��@��K-
�������
�� ���<�h�������T�
�����::�����`Qb��O&���0��W�xy�� ����-��
��Z'���W�;���W�0�y����880|������p�=+�SX�r��&��*�Y�7�4�fEyb��������]W�������}x^_���(��]���W��?~������������C+r<�OF�H��'�a�S����{w�`���/J�\�)�!�YK��L��I3��M�>
^��*��M�� 6k�h�DD_L�2��p����6l������1/cj9�� lG�#5:�.�Bj*���m�8Q-�������Kt���?Y&Z�\'���(��J��Q��nS�������J���^t$�2pO�qP�x�[��S���������s���.~`����������OL}v� ��4����Y�y^a~C�#�����??���[�4ux*Q\:'c�@#�L��?3�<����`�� �Q;�����0��#oJO�z��M�t5��f����
p� �
�
{�!I�/i���x���R�����8�����BR0J�!�mk$%e[��Lv��0����X"kV3�*����<Db�����$��&�)�0�Xf�H��S�Co�^{���css��6��������������}��e�BSO�p���<xp�cmnn[f������.��y�3�bj�����w�./O�b�;)�Zi�e ;o�����x�0.��tX�Nf�����9!� �ZwX��
����J�� J*��U����8��=3d'R��[JF�22�2��cH4`�v8A �����XB �����k�F����������WP��*\e�)�S���o[�V�VZ�v�Wy��3����#��}
����]���o}��-[v-)o����7�����U��bby���������{!D�'��e�A)������%�n���m�M�}��5�}�S�5�V�F�n%^��d�}J�/M�&+J�XJ?UD,�:�s���BW���=K�IhQ���BDV*��J��6 �:��8��s�����'Wu�~��Y���Y���`��fh����??�����_@�3s�>3��_<{~GQ������o�/+���d��\Q`2W��-i���l� A
�Q^&������$mL+���#��I�F�����^&)��$��4M2���4�{YN�G�{�A�Y*�����y�]�����?��|�=���O=p�oy LA�{�x�v�{@���x�2-���#s�������< ��4&X.P�<x��=0HKWy:=L��H5�
����4���#�{(�~.�X�a�<�=��-����C!h�[$-�H�-���NRp��ha\G@����D�0F�\��<������)�e(IJ��$�IVf��)��K�Mc������R]Q��H�Am�t�\'��t�l�.��g��g(����������k9�G����'�i�W�C�_XTX�P����a232��) =���W0E��sK0�L�Nk�M��9�W����z�����+�Ag�1�`�S����|��>������*1���\o|AIq��'�j=���7�rN� ����c~������C��I��J���?�?�?���y������n�-#�/o��g<���=�x-����|������p��lR��8�sV<X�l��(���#A���p���<�X���yxl5����?�������+�y����h;���e|a�x��$`��tn+x��c�=���y�a���g/�p�?��tv��6$l�WI �C$��D<]�aLj�'��<3�C�/$�,�x��a���c�����i.�p�"l'��l%v�Jb��B3��2vPyXV2v��+)��~��c��m��
�<"��#���y�>�k������u�[a����(�M�%�!
&|��SI�N��W����x"2��DW�H�t&zQZ@MF<���������U�%��4�*
V%A���I^��w�CN��x��L*�a�\K(�=K<����@T��T�v6G�
B�=8��Dm6�u�nP7�����)t��6�E��z�������Z��������U���:TQ�X�31 w�v�T����E��]�x"c��3����~qI�1@G�<5��Uu�f�Q��w�_={��]�%T:$+K���Z9O��mH�z�du�����c�<b�vL�������^��Z���X}P�4#V`%�Q��-��������R*y�axb��x��^�H�l��z8Q[d���\l�5��3�g�����m�^�����:������#���M ,�
��2�&�a�KZ!�� B��TCX7t���>��?8w.�7�a�7������)mBc����T� �Tj�n�k���K :���
����A�)>%�!��q���r����$���l����1\�������}�����=A���O�K�{��|���������V���\��<ka7��YV�4+���R�k�D���1{��?��V �0Yp� [L���TJ�x4d���t��Q3(2�d����!�[uH���a
��3
S�����|$���������WRE{u�����;V��K��z�!pa���7����3��.>&],H����=�������py����������-��F���+�a%����
�29���`t�m������v�nO��A��������.�v9:I�*�d���uf������Vz���u $1:o�e�v �Pd_�R���m�S|y����'��f7���<�#i_����#Yqj��*z�h�nY^�������w7�������m^��y"�?vL����Ki�}KZ�&nK�qLo�&CW*,U@�,h���\Xc�b|��$��81�9��
n�X�\�U�`�k���<�j���H�tH/�����b�tV�[��c�8�����qfcL��L�J�1[es���?�%%��bFEm61B���{�G�������'�o���NSA�b_���2k�XG����C�e'�;�,p���`��76���������y���e�����wF
Rs�U�������������,��������g��f,�%>�i�%��H��Q_V��:8��]
�!|M��H0�z�N�~3c�$�)���������` ^a�0�/`Lo"� �"K���l�B� ���IM���-8�#��V"�[�Eh�Z#KQf|&�e��r0�����w�����L���8c\��
�S����SW�|���%��k�}�J�&*I_��]a���w��������yZ����=�8�;��}�}���d�}��l��[�ne6'�I<��4g���M�c!!F,TA:��+�x���#��(%c��)�����o�=��,��3�������������*c�������u����B�N��a���[�3�Xd �Z)�=,E7�W�h�j���~���A�IZj76��T�����������
���o�����
f:��y=��o�������������x��Y��[�6�y���c����<
��j65�R�#:A�l�R�g���I=��}d�W(PH����u=CdGjGc�CH3�Up 3��:*H���2 (b��������jV��y#��d�55�{�[S������N�j(��"��&2��d���-Dg���Y;���c��&�H��I;��h���)~<o2��&
lR���&��ob�<�w`�P�U����p��U�q~�)���K�-0��f��#SWa���
o��
f�*���s3M7w��d�w4Q9o4ju�n�K{]������K�["\.���M�J�G���rD�d��)�an���ilb���-[^�P�]�UX�Z�(|f����BGe���{���������I���PCO���T5�d�@��Z�h�*v7?�_Q����yw--���������oeI���w��Z���1K��w4V:���9�A�'�x�)_[mn���W�����V�)Dod-�yxL0�&��7)����Y�lb�z��q���9�d�S;SGR�����#��E�K���DHO,H�NMd��`��#��M?��'"�:�_����:R2�1�9�v{~���t��M:e~��k��&2�n����t�'���������"�/L=K��s�Oo�W�����==��_H������sg�nb��jZpU`V�B_V��9�{���U���,?p�
H�n{�����ea`��hi���`������W�9������Mt�-"4M�~����D����ep� �\].�����3NO�Jj"*�IE�X����i�a��
���8���6xM�Lx�0�g,����������+%q8+KHq(��a�}j���uQ&��)9�d&�����N���um���D��?�hC�����M���4e����M��y}���CscO������=�9��s��]�2�k�Y���}�����U�����MSV]��U�i����BRz������i�[�5?��e�W��n�����x����G�;��fS�x:n�����l $\�����j3!���2��2`���LK���?k%��k<dd&�b�S�_���2��(<��2�dl�`b23p�s�����a�z�zX���yY)]#�:/un�F����z$��qq������V�R��� B�g��&w�,TXK�����{y�����u��;v�����^��o)�q��G5��C��lZ��_jp`~�=��aG��}E�W���/���s�����������4�:��[��k^��%��5F���.��dA�R�hlN�����/����*��2a��n&�1�f���uL�B�
��Hl���l�F�������ugT�����Zu�����~���\��'���J����O��+����G��������+��}@y'�t�����oJj&�����jc�n�JL� +Xp���������&�M>���%W����3���/%+��HG��diIg0Y�t��br{2sLb�d�,����.dQ��D�(j���^�r�#V<���S�>�>�rY�r�f�`L��D��;���������D}�!����9���Z���6�u����g�.�����y�%����t�Q���@�#�Q�`,������g��W}H=�f��c8�v)
�4!ML���������p��L<� �� o�k��A�"d3M���-�������?#B|2{�~�~�����d�Ci|~C���O��� 3�I�X�*�|o}&[zm��U���
w/��W_L��+*9wIY����d���.�S:���VA�H
H�L`�Y��H$�1�B��>�A����!�1�8�/s@��9kjzp���I�,w�# @�Q����F����M:5~�{���%����:T������������fH/�+��Av��S�)8���DA���x�x�����dL]#YR�11� �?L����<V%��%3'XYB �\v���`�NK��!�]=��cD�9��]����������w]�u��]oBp�Qh
);�{U���T��S}��g8?1V���,
���~�����-^�j�lq�[3���PW� ������;mK
���Y�96�>��{�������)q���s�d&j��;�1b+�����.NE��iiC�����]�\��^k��|��<X`#�V�����N������>������a��R1~�P��x�8\����d1,(�����XW�-�g�/���V���
)����[���p��MN��W��.��yDwQe���& n�?���L����,�[���1w�'V.�!�n����d��#P�j�'���I ����/�d�;�������d_��x\��p{�����k���;��k�.z���1���I%����IH!��4!t�����Lv2t�0�����E���
ZQ{A{Y���TF�����(��s?����P~��0&��a ���� ~iF
\{�Y|�x���7�#T�"}�%\2"�m�������I�Z�x�a���<���&N�����j��a����H:����i�&�Hq������U\(FH����&��u_��!b�/S0����u'6������h���uk���g���UT���)SM�������b���=p����+�l���Y�+�����I�W��������J���H$�Z@H� |����Oy!�����e^x�{��K��^v��{��
��p
����|[
�Y[��X��+~���C����~8��=~��o��?����/�����g?|��w���
��?�����������}������?�s${�
�Z�^��~ 5��[�����,���~|���I�V�-�j?|}�������c�A?�J������i2(��:�A�k�w����-��6?� m���?�����#U�z�O��u�\��+Wh�K����B��"m*C��)-�����!�V�!_.��C��$���9��Z$�7&R�����4y��%�����'����~��.���$��J-e �����GyB�9���f���Y�ns}a����m�m�d��5{�hDx�_O��T��
�`��}�!A��^T�l���""���C��7�I(uJ�6��vb������7DG�U��kR���'�O��i���hI��t��a�LP:����Vh�K<t��W��q�c���l��r,�L���.�FlZK��u��S����e�nD�U���p|�G������_���K�_�C|z����7�8��k(��������HLm�Cc�
TD{��T��e4�o�:Y������z�|������&�C��b`���P�9KmS*�%2�5sJ���*J�*Z�����W�r��k�QY��<���)���e�D��+����� SB�eU|d��<a~���x�g
m���e9���z���{���5����d<�VwC��Gv2|�D���gb�v���������q�-��v��R�$���]*�nt��6�=�b�l���6���������f����klKm=6��\h�]��9��&@�0"��9@@9 �}A�G��)D�@,l��������L��[%6'�4��c����*k��ZF�*�q������R���)�����<���
l���>�a[�2r����9`Q
�@�1���?(ss&�����Y���43������\�Q����=�����x��<p�{=��h������c�#Y��v���:�N���)�m���*]��.�.����:�F'I����n����o"S(�%"/f�X!B��#n�-�*�#�A�Q�!�R���!������g��"�'B�X,6�����������*�"���(������� �?���"|;���.�;�Nn�����8�-"����"~W�������="��[�KD���#��"�I��G"�a�x@<J�i��b��d��(�F��k"|"�oDxOi�M�� �-"�a�u"���!I�WE�������x��[EX+B��D���"NA'���\��"��D��{)��"n���D��*�V��+"\��?�u^���f}��"��9�9�������H��!7�n���r��"�6p��U<$������W)��X�����LIg�l�C����k@��F��Gp�e�������������������r��C-���M���QA�Q��IuS�|��.C|���%�^�#�u��� �����\�5��d<���)�a��3�@�9����)2�C"t3�������jK�F�����}4���5�M�U�e�N����S�t�JABB���w�������"�;��6n��m�[f��W�M�(/�g�^}4���"in��wc>�5j_���jtE���a�
�+a �������|b� �������/�����Q���Q����Dj�^=���f�����G�O�t�����S��J&����lgm�J-��6����i#��Z�D+-^l��i�[��yj�D�l�:����J���1�J�!"���2��0T�s=$�[{]t8�}dE+��
�K����������^=�x`��G��< �~>U?�������w�k����m����7��������8ot��J����)��am��Z���;a?`���$��"��`/���d����U�PY _��N%�1q������P�����*2�����H��tR/����}3
�B���[��;l�����|�,e�%����)+���y}��v����S���ieb������`&{q�)��d1�6O}2�;y�����F�\��&��ZJ��y(��}��W����l��;����4J#�J����k�MJ���O����El���YI� A.�J�Ce9�O�c[9L��d��r���
f���*q�7����!�"���/zY�G^�p�L�A����"-��<���fB��;�O�V��,�n>���������&N�,���4_ib~��z���:�XS��~�~zX�����Jb���"�HE��� �(��N��R�:�u��6�v�����_c��a60�3D� �K7i*H�h5<� �K�,`V�����za��OxK�@P��F��
�
�LQL�q�9Xm��[�����p�����A5m���al7�3�vT�
�n �g��\�@h&T�h��J3����P<I��F����_l�L�l��
�P�Vc$=R��2R����&(*
�u����3q� ^����:�����W�����+����_~��wc�� 4��^���g$��w�#�a���O�:����'�>����
�Q��
�1����[zM2WVU�L�s*���_�|f��&���4F��,",��{��� �0�Yzj���`��#sq���
\>���0������_��[�,^� n�����-�����}�^2��W>mEMc����������o����3h�`�u��?=�}1�h����>��U���K��C�������.s*;7A��\���\Q~�"�����zt���6�=�/���g�m��]��R�*��
�/�=�������7� ����������%�7R E �1�N#a����1 c�1�d (AE���p�;m�d��
,6 &��f���z��G�#��v�w�t<�8�x����3��z��0O���[��x��E����a&Y���4#��~�S\p��?s��8��{�8���0�����`w v�#��,�q�t`��1��2`�#���n � 2������� ���
�/����!���a��}��t�*G�����8�����o9>p���+"���A� E��|�A���c� ����: 9V��F��N����8Q.�Ux����������~9����fDFk+�Dd$x�����Ou��8��=�t��n$�2��k~j��(�����O~c�%`&>9%������@�$���m.���s��� ��Z��W!<����Q�@<���� !��R��0i��6 &�I2�J�)�2a�������E��/�g-,x/}�/d�:��B7��-�����B+�����J�1�������I�YSiY@����Y� �gi{-x���b��������-@1�-��B��2~�TP�����-,m���ErfI{IH�f�Z/X8��:!�[g�#�R�`�j,%�������q9��6����
T�"��
W}T�)�n��}�O�
[�����i��YI1�Gs����,��q���i*�NO���sH�������������~������c�
�4!MX�Lhk��f�fd5T�k����j������w]�*W�)��B�� ��q�q�sg5�{�`i�������>��k�}���a�Ki�����;�������g3B��Gz��)L$�B�p�e�L����$\�IT���%D�x��Bm@��9|$&+T �Plm,��}0VkNNRrf9�� f��I�#�9B�]�7/X��9������9��#9�?6�@aN �;�����9p�fm�����s����H��F�*G��J�k�Q�����������9���n���n7����pc�>u��nx�
��p�
;�0"���!����
7��sZ���"b��Ey���I���������fH -��Gn���o�a��x�
���Un�:{�37|��37>��g���
�i;�x�;��Y7���W7��
o���������gz�Fa��}�~�� ��o���r��q�L�}�Q���L���v� �a�(���?�]�������1�C���*�[�������w�]�v��4RS|������nvL&k��(Y�������H������L�w)�����O��J7�n��UJj�d���s����T%(�������s O�O3������W\�.��B0���N��/�_"�o����Kn��+/��
�3��,���!y�E"��o+������ ��qS����UzU�����g�~z�Ue�R�R�*A����T
$�R)u�3a�k(���ug,�]�����������4�d��fI����$����<�a��~��!j�K)��N����Up��^� Y����(fCN��M,Y`�.����_���Q�b@��</����q<�3H-d�K��U����?S3o�a���)5�]
u�:��V�T��� ����WlA5�o/Kj��)apC��4r����Z���-Ti�PiZ0k��z��I-���v�>�-�����Li��ZxK��p�n�K�;����h���R����OX~���W'��)�n�z-C�eh�� z�h�3�S�6���V�i���N-ss�_�w�\'�����[���hM�-����K��K�V�-���&�e�����{�r��s�%ZH���}�?�t�/s0'�0����2#Zh�B=}���`��\4��<�%���i�Z��aY%0X��!�����G'�����Q��h�}1���e�i��\d�#M~�B�s���������m�n.����SuY9�~3u���m��w 4?�zv�SU��c�Z��k�^�Yd���O�lb#Y�.�/�����1���T���Y�!�a#&�
�^�!�1c�OzI�I�Y�+k��K#�N���k�8f/w���G��B�%gT0�6$���o��s5�7d�!��w48������D��9��egJ��,^�H�w[�[\�}?g�]���k�]���L���|���A����o���
�"����sg��_�*�;�VI�����B����h������������%��F�k).A6�|��=K��ZB����D�z�R<G���<�;��\���I��/aZJ�;H�K�vr����\��ZD���2�$��A��L�\v��O�������V>�x3N�����������$��;�?!���;��H<��A_�w������y�.�kf��|��=�HP<����~���KLq������j�4�i�cU�'t!!V��S�L�0��Wc����^����>���Lby���2������HYb3��8�r���(���"��G<
��f"���&I�$Xr},��� �A��
D�JD��a��LD��E��a �
+�&�z4�BqP
�(j�a5i��������hX����p,���X��&��hP
c���a�3��0K`��a%1D�
~6V�O���a�bOG�<Jb/D�jT�^��5h�
k�o��h8mQ���8���;b�Z�m��"���N{�c�m��_���^��.�������wuz�w���^4��v�|{����>2�����ch�}����w�������/��^��3��ch�������!{��6���K���ix�G,�����
�����=}�#]C$�����Y���:F��G������tw����Wv
�t���^��U�C}��}+im�����;048m�H��.�������������R�w��
��(�J�Y9���Uy#�:���z�I�=�#k��I�?L>*�HZs3��d`�D`����.;E?L�wwu��
��Z9���n�[���������@C�D��?+Md� D��C=�� ;�B+Q6y�!�|�Hh�B��D�MB���@yHh6ZC���0��.��"��rY
y')5Ul�Q= /@�Ij��A��A`��Z�B�I� �����$�W����>�Or�X?�K���Q�>�o6IYIR��:�\��������K������H�(�<�v_V�����Q"B����;�'�n �e��\�RaD��_������IyJ��+e�#$�<@��Qz�"��[�)����0������7D�o�6������'����D�z�� *%+�m��s+��Q�9��@�?-7Bf��L�.y�{ld�=2������R�_�wJ������?�������5���#K���L��������Pm����dj{����}d�H����������������/�f�:_&����s���J��k����C0y
�]t
b\��[(���@���9�������KXwi���K{/����Q��?~��~��f��_���p����t�W�H������~��<0
�f�m�_�~�����k����������2lo|7�6��N�;�����������W�:���W�z�U����'�'� �x����P�^�|����Xx"������0�=Vy~1�"�|�����B����0�������{�b����g�Ne�8�f���pf?�$���/��u��}���a�a<�0���'�����{���x��������e��
������DHh���>�AA��N����,0����5��1�����yL� :����N/�������0=+��T����$8k�u, ��x, �<S�t
B��j 6��R����cu:�n�n@�Ww^7�SV��K:���cf��4L�_�r��VN/�+C-a�N_L�����bW54�4x�i���9�u���������p' H40FB�q3��42<2*�-Dh���!�?�"r\�$��
����(v
���0��#$}����0MR�\��z�� ^N��H��0�&�������r�
endstream
endobj
8 0 obj
16520
endobj
9 0 obj
<</Type/FontDescriptor/FontName/BAAAAA+LiberationSans
/Flags 4
/FontBBox[-203 -303 1049 910]/ItalicAngle 0
/Ascent 905
/Descent -211
/CapHeight 910
/StemV 80
/FontFile2 7 0 R
>>
endobj
10 0 obj
<</Length 464/Filter/FlateDecode>>
stream
x�]�M��0���>n��vb�J��E�������J�p�����n+� z����<���;��R~�Sw�:c�m��.�S�c����n�+����\�)���-�z��jU������i�O���(��>�a����cZ���+\����X�U����v��^C)Y��>}��sJ�����2��T��>����/�XU�Z���u���oM��������ShU5v����%7�Z���F�j�cn������
�����F6�-k
�����x����+��Y������y��v`�;������gM+1���`�[8k�[9��V�g�Jg����&��
�=�
��L�\C7��q/���`�;�����}�{�����.��
�b�����wO���{q���$��78����������H<�
�h���`���OK���G�_'�/���X��c B�L�0��s:O3���%���
endstream
endobj
11 0 obj
<</Type/Font/Subtype/TrueType/BaseFont/BAAAAA+LiberationSans
/FirstChar 0
/LastChar 55
/Widths[365 666 556 556 277 556 666 556 556 277 777 666 556 556 833 610
722 722 277 610 556 500 777 556 556 556 556 556 556 556 722 277
556 222 500 556 556 556 833 777 333 222 943 500 556 556 500 277
333 277 500 222 277 722 500 722 ]
/FontDescriptor 9 0 R
/ToUnicode 10 0 R
>>
endobj
12 0 obj
<</Length 13 0 R/Filter/FlateDecode/Length1 9252>>
stream
x��X{T[������2��������]���g, ��A�l�dI~''q��v��C���I�����/N��4���g�H�v7M�=��n��������d����o��_M���9��^43���7�|����;�hx���)� ~h�*L�� ��Fk��E���?T }!b �Nm�!I
Br�����?���DH� ����;|6�UB�/���1�z�Q9�_46��1�Z� �p<8���*Wo>o��#d��H�x6����\(�?����P0������=6��f���@� 2�������HerER���|�oK����AYh�X��HjP&������������Bo^F�F��S�}4��@��i��G_ �7��,:�����
�:�9���5�5�Fg�)t���<�M�(��>��P
���= ��YA1�C�`.�64�~3?>}�.�]�L�����?D����P�
�cTJ��b�
���=0�aE�A�Sq��x ��`f��G>������g���+�����E��~�/�N#?�r����F�0:X;B���=�r��|��ks�B��������,���(�5���M���a�,M��xG�������c������-�UNGsSco���]YS����bY��Rj6.1q�z]Nf�Z���LNR�eR C02;8��Ab�\�R�s^xoxD��u�#���k��9r�&��ohb5[�jK���c�w�9v�w��>������H���� 2����0�u��5�����m,��4��er��K.5��d%�J�#���z,����!H�J��b�wX��t;��z}_��EH���.�$�dM�\4����� ;c>;8�F=��an�{�[`�06�8b�}B�I(����]���}��kv&j����<�7����X����,���r�������#J:�X�����'�������j.6��9 a���Q����
��}��3�k�uv�
�n�;�1/H�g��+��������F ����t�fy�a���Y�Q{�VS�@<���BOV/��Z��1��A4[��1AR�2�9 �^aj#��&
N-�}��s1M:[m�uY��e��
R��n �B���"��I�����t
[��j��9<����0����)���7�{1r��Ya��!�7���\H��o�����w��!�aBf��<C�Q���Lgf1Os�j��t��l��g����lh9�k���M�WG�=<"�<�a�i#�[��>p����D�J.�tzqF�4��[����~���#�jNR�������@� �b�&Z�� `�@p��P�b5 .Ji�6��n�E���P�:|� =��fTJ����`MFY����������L��ML#T�BS'��E������q}�+�n�6
��r�D�zn�n`Bz�^`(�����\a���`]wt�,t�1������A����0�"]+�~��9�61�hq?�fx���1�mc\�p��v���p����E���V���Xj���q���;gx�������V�{�g&M����"�s��"��RB�TH�2�R0
Q_�����+"?4��(S,�0�%q�zAF@&��xQF�R�`�������o,���9���as��W?��,EH�|���k�r;���r��!3p6.5�����9���5C5,��[�Yf0����K2��gd����a�h��b)���2?�=�����O/���� {���>&������w����\g��F���")�������<���K�}�����Lj@�����i�4�U��d�������n��
�4���ee�8M*�*�H��J/����O���}�p�����������������~���sx5����O����_�l�N�|dCw�
Q�6���60���X��n�2��s�D�{���!�X<l�C���J��X5�� ��[��s�9l���[./ Y�2���a��B*����z)SN\����y���&?�<��S�x�[��]Id�
m�'���W��6���S��/������~������X}��o���W�z��P��?��r��_�=����o��
u@U�;e�J2����p����&p�Ve�w��k��Q�8��x���y���_\Jv����*����>-�O��N����D���R��Hf����&���W��]3C��\���� g2���� ��s�%7��'e�r�fcDr) �$uIJB���\O.����e�H6��m�@����j���m�f�~S�mV�� ���)��d�( 1�`�\��361i�FbIU���29��1��k��3*�����u�bo�����#��������L
,+q�<.�{N^oP�y�
���������w�2;y��_�p����cP%�7*}-��t;���v�h%���n���b�
b���-����*^UFT*��W�����\��LS�0ANh��<� �Z����d�40Yz�������xn�+�O����u������#Y�ei
��U�� �8p H�T��|PS��S'���L�C��M����L��`�f�8����Y@��v^r��x���{�j\�S�o�����g�Mc�+��y�y]���������y�C]�;K
~�cG���� �#e�{����+%������gv:�Gtyc�+S%�GG��V\�����n�����k�����*��/*������XB�y�#8za��i>�-9~K�����$xWJ,��bq6�/����P��HQ�6KK�$k���������d]2 &O&N�O�$'/m5>0�� �����y>`����
�� j�F�����!��D�+�C�n�X�c�B���&1=Gh�� P���U��Ru��L���������O�w}ea]�m�+���t���H��D�����8��H~�?9xl������m��������������=�{|�3���$��2�W/�S�~���Z[A���,��hS��"�����������|4E��fgeg3��9�*��*��kkIY%_I�����j�4%?"'A�����������O�t��k�k�p]]�������;�S�#f)%<@\6��,3�
�Tx�*�"*UJ$��/��� [�#`�\�����Y9��a� ��@y��t�E����?�00�*RY���zEa~uW�����`�����y�����������F���N�u�ZV�Z�,m�����*����yuE��`���X�&;�L�_���=�{��������2��jKI����]������ ��������n����7�{2f��j+�����zF���J�t��rR^.��d����ZcPZ�^*��@]@
J�#�(#D�5U^A�7NOM�����r�s.��Q����{���RS�)d��,���,E�����'�C�o�V���7G�w�2���\s ��������H�k������`���wY��*w�3]{��������ot����E�n����P1t���N�����;-u���D�w?(��
�� ��d���gH7KH��f%�+�[�S�����R(�R���d�w�(Sfq�Z*��J��u>��%���\kNJR ,���c���e&Q*�Pd��R�2`C��2�9���n��E��r���lV��v�������y�����-�:��m������ee�5Ez3\��
����zfM����"Z����7_�v
���������7?m{�q^s����+-b���C�g���������$�@O*�+)��y�����I�aiN.���&���I�a#c4���NWP�)�1U��jCU�JRU��E�X���sK#�������`���p������g!El0LS%C��7_U��}������m��������J�<Y^<�����z��r�
t��T6T�v�-+��ky���UiJ��������[~�����BX���V���O�m?�������/�wk6�2V�>��{x}�ssK��T����������BF�
���B�LB�Y%v � F���$9
2�&�H�MF��vI���I5�0,��\����E6�Z&��:�����*���e�I] ����}Ru<C��m������b��W��������}����X.������D��]���S�|��U��H�����u-|�����dA
(��v����AM7��
��%TJ��fI�J�F�Z���*C�cN�<fBW�?M������C�������(��;O�?5��~����� ��,�w%�N#�I���
8�%C�� =���%(M'h)JC/$h���-G����@��%A'�4H�8�6��Bn��t*
�Wt�'E0;�$w�lL�p�2� ���O�jd������-f^O�2��y?A��G���(�(A'���� Z�VHW$�t�4��S�/ �8����=���G���q��-/+�b�|���5�-�!�0>��
6�����|����������v
���^6��&���lp���m����7��no �����"C���/���w��q�����G�h����R~S��������1X��?��A����n����Q�f{n\;2����!_8��`t���5�����l��55��`���o��m�F��H00��j�����[� �!��'��/�3��E��X�e,:1�"��VqF��V�� k<�cf#>K�G���o\���|CQK0<j�����������f���<�h83���w�0��Q4������*��N�2TT����"���� -P
h��[,DD���m�X�����5����y��(���m/����a�dA4�7�o���yh����
\ ������A��!��3�A�T��o�go�����K����Z�R,-��g�Y�R�_���C,�Q�JT�����{A�[��GR���lQ��3f\3����n�m���-�K � ������8nam����q�9�,
���n�8g�(��9G��D.�j�-eE��?��ny(a�"R��?�q��1�x�-�� �g[���/(B[oYc���G���w��mvhdiK�.xI�?"�G-up��h[D���F?��������&dwz�����������"(K���9��������i,����s������wurut�t�W��J�W�W'���z��]Q_��t\ ]��"K����_���S�
��rf�~y��;w���K�����y������K���cz/a�����N�V�7��?���?���}��a�y���N�e�Y�lh��_�f5�N���W�,��y���b��J�N�����/1I!$�#�S� 0S/y�<���"�|?�����
�"�SkO=y��)���'M:���t'z������!�( P��r
3�c��_z�H����t<�O��t�N�.N_�&��u�����G������_:.Q��<~���q���ju��E�N�XR�Suo8����G��zt���?�����a�09�������9ue��Cd���)���_R�%i�N6V#{p��L��� �[/m�����G#v]@�H����ag�n>d0;�PY��@��9����^�������O�� <��o�����h �+�cPc�b�K�*��,V��K����uw;�� �~h3�5�R����
2X��2�����]�h$_�*]��h��H�v�w��b���,6:/t`vM���X�+t&���W�����������8��������:O�=�FZ�U�'�s�bVA9����W�d�����z���W]��%�b�u:�]�A5���TV�ZUPuXuI5���AvU��
|*K�,>2��m2�����Zy��������;��~���g0~�o��C�1�U(�v���Va�S@��g�Qc_4�j���1�D2jIA���N�G��).�RY$.�@D�����?*�P� ������5���(��U�:.�����.J�#�6�����������Fr����
endstream
endobj
13 0 obj
5990
endobj
14 0 obj
<</Type/FontDescriptor/FontName/DAAAAA+LiberationSans-Italic
/Flags 68
/FontBBox[-271 -303 1061 1014]/ItalicAngle -30
/Ascent 905
/Descent -211
/CapHeight 1014
/StemV 80
/FontFile2 12 0 R
>>
endobj
15 0 obj
<</Length 270/Filter/FlateDecode>>
stream
x�]��n� �;O�q{�����1�n�������0Z�
�����&=h�qf�0f�����g���<���&3;��Ai�T*��(���-�Bo�L�F���H�r�w�\����d/N�Sz���k�v��F��2R�TB�y�������m#CZ�eZ�
���q�FF�d� �� �b����V��_._[�^|rJ�P�Xy���d�.��G�.}����'�!�@�K�)��>'����3�>9�C�������5P1;V����V~��5���
'���
endstream
endobj
16 0 obj
<</Type/Font/Subtype/TrueType/BaseFont/DAAAAA+LiberationSans-Italic
/FirstChar 0
/LastChar 11
/Widths[365 556 556 277 556 556 556 556 556 556 556 556 ]
/FontDescriptor 14 0 R
/ToUnicode 15 0 R
>>
endobj
17 0 obj
<</Length 18 0 R/Filter/FlateDecode/Length1 14380>>
stream
x��zt���9gf$�d�lK�[#���<��� �0��m�
F6���c��!HpR��@~�Ch/�k�J�)i�����i�O.m�
m��8p�Hoo��3��I����}k����3��>����>g���
m��4�$�l��~h�B�-�pl��aa���3��Y�:�fC�����y)�5����~}��i������{��O�"��x��"�W ����6o�f|m'���������7��nC����
��I��OCY���{`��w��B���?8�k�;�P�@�C��q���CYB��p����� �r
��Wkb�:��o2'$&%[f��Z�����������A&�E~�v��(����g�t�^�W
���I8}�>�V�C��>
�s��q����c�et
��u\��/����]�S�������~��`������� �<��h/���`:�
rm!��a�+xU� t �{]B��t�2IP��S�4sy� 2/&{7�~���.\������ �����A�[� t�-,�r�5��*2N���^�5�����FW��x?�dV��9}}�RY��%�r�(<�����? ����/
���?��9�H���������G�Jt�������5�?��T���������a������������3[��UUYQ^6������,������H������F�^���y�R���(����B�]!6�^W�O��n@tOCt�@yn� ]2�p;����D)E(�)Jl*Qe~�PkBo���1�����{���E2�f�-l6h!�&��!�%��<��Fk�j��1�z�}�O�����5 j
e��p�,,$���A*-�6�d�v����jk,6[{~����^#W��2��bnH)����h�p,����1Z������v�h1��v���2:B9��P���a��P���6��\��L�S�K�2va����v;�;�Qd�@��zGG=v�3�5�=61��.���bbF��a����&�����i��pyt��%�����m!������v�L���>I��u�� ��lt���$�
����HY@�,���t��H�9;Ycj�5#�5S���0���m�!6c~��t��;4�
��Z:vCH�W��>k���2� R���B\&�ZMo +�65��_#�qt�i���������vE�7�%!?/T��L}K[H�@���Q�1�Ztw�����r��x�����b��7��M��B�sC��'�*����=��]5(/{S�)���t�H�|���P{
%6��u�Y;���:d�������,����no���������CdnK[}�����mfT�He�f�~����aK.��P m����� ��Jx��*�
�pK���J�
[�$5��j}5Q:Z��)G����In
Z>s�,�v[���#P-D;�*����*&<���QT��t�mv����'���6:6�Y�Qe�:��U�m�i�5!TO�2C�e�rC���T��K��'��Q���y�2�G"�|~�%,�4Zd���l�t��E��<zL��-�Q�����7�U���A���I��E���eN~8�9�����c~�������-m� &s���K���S�2�P,E��@��(�dz�) ����r�g#���a�3F"8�$� ���$G/���>�1��Z���������v���4�8���@;�Y�0Q���v����>���)�:�WP�V6���;G
��/���IP
<z�V�����F���J6m\<��~[y�! �cEs}\����<�)�m�3lF[
����p���j��ip�*&>��T�6�����-�����#vXs�O���5z�U�����jN'r�����t���A��0.��!
�����A�8���ee��9n��BN@�]��{Z��He�bIq�\q�,�SIW��i:b�8���G����_=�5�����-K����Wn���6���w�����b�0��{���d����9�nZ]���� T��Z�t..�.�._��������E��y��������T����t���e���b��B4kE��7qI�T�Ej�%�*Ox�~�a �������b��f���06q�{��u�-�T1u �(�7Y
��U�������pt����C�;A��ga:p��B;�6#�I����x����������+m�?�$�
�j[@
<�vs YY�_���������:avY�6�v*'>cG���V��W���:6qU��iV��fy
ZX"j<igs�����4�n�`�<y9������y��5�q�K���V������������������Z�E���[���������4��"�������]���#Vf�b"J�iw��&cO����p�R����nq)��o]Z0w���OL�����$.|!F�����@�2�>CHM���O]�S+f�������y%mUi���;w����������W���m\�{�{��2+sL�'j���OXi�����UnX�G�0��R��SH?�� ^���zf�1u&�u������b��k=jebR<��Yt9���B��kP�!7���v�O.��A#(�.7]Y�T���1'��9(L�}�!��eXSnYcER��R������/�W������*:g�y��
���vs��#�>�*�B
�&y��3<*MV������i����s�p��y�qIz���Dm07!CNJ����\�xdBAV��tVa�N�"��l�'����1�P[&6���i�;�z�����K�V-X������t���|D5_�����_y���;U5[��$�-+c��T�z�����X��NW��k�2<m�&�rm��R��wVw^G\:������8Ca��e=���?x���A�S^���V�}��E�E����� x�
t�1 �1l��;W?��,\����U-5�c�� ���g7;J��R~��2'G�STb�_�r��-[�y��\P�Vg�%Ix�u�ak����l���������HZ�2���3�"�F���`�[����D����@�B�+���37�^�h�.Q���D�M�'�Kd�$��D{�W����X�7����������]1��e�.�
���V�P�b\�)�K���)4�pk�>���f5������^�^�[�������-ZS��������{�;���j��o�����6��eY���� >�>��H��v:�l9��R��@�(^���F�R��?�p ��P���J��+ii$Mv�`CiI��s�)�aqV��+��*�\��F��:�0�������/�/�R����a�a��/���@k&[~�������K��[��)�$�������q���^��hA�N!5�)t(gR�H
�X�z��'aQ��� ^��qu$�)v��$N�#K�%�?�v��?:;����h/vGg�
����&�A��g�M��s��3#6?.���Kf�����g�/�S+^a9�P(��NuN K�
k�E�s
�`�7RY�D�t�����G���A�6d�'�g��o$A.���4��9���2(\f��\b��6��b<e$O?0��F��I�q����v�8D�$�OD�������.�9��1/���/�e�E�E��i5��LZ���.��!~"��"�M�V��r������"~R<%h~���rW�
"I�F���������"��Et��"��:<!��"�'�a�6k�"���uj�9M�h%�F�0T@S�����Wd������R���7��F�J�?�Oh�D/�-����mh��"~T�00����N����D��,a��\$.GvU���,�a*�_�'2}Q�!q@�z��WdT9��D�S0BK����!�����Azy�"W9U34uM'��\9��N�����������ne�LwlB�����GBz�`� gef)`�W2���Rq�9��tS&R�PPX��:��x
��Z�s���~;B�dM�Z�S��Z�e���"&&��[���{;g�jWiE��Dwa^��w�{n\���-��J����7c+��S=�fV��,c�x�����~ ]����2�2$y�:�Ao�6pf���N {�x��N�d8p���G��H��;�v�|�g���>��}U��{��v��dV��4�������<z��-ohiy��;�r�L����c�d����=(��@8�e�5j���Z��X��3Q ��������=xQ�F��b%�9�b6�������qIuD��X�T�9���n�&��vtNF/4v��v��X�<�6���Xl�13'|q
[��� �?��gKx-������p���0��6�G-�@v5�xU���T�����4!�u���
��f� ���z�zq��8e;��"bj�����`�L��V�����S�P�����G�k�H�i�C$������Q�D��K���@/�����P��-����.�z�t���,"~F#���"K�w�H;�.�"=���LMw�4�T$�fB����T*�t�qV�j�?M�@Q!F4@�q]TF�+�N�DD��K��L�JS�&��Z�sUv��#^v�� Q�RHHY!��RI�"!3!�����eW�&�jh"N������qn�4�;��
����2����bl��s�����4�W�LN�����|�6'c�,$Y�8U����"��c�x3�6�w���:A��ie��7��Y�^�_,6�K�*��n|���UJ���g��f�x��g�����"�)/7S�$�};���g!�(C�=��'�����.�V��<i�=����������W\�`+*����*��
g&�
H�q��|��
�P��� P��AZA�����Zj�q`�Z��1�������Z���� ��)q�$
����9�r����JV0�R��Y���������p�r�����=��H������u�=� %��u� �;������L�_�[�s;J���)B�h�{����'�/||�����J&�N�b�:kX����d�
ka��������BF��^`9�T�5[��S�:����Mr�|J�kH=YNv79M���!���$E���,?����#� ���T���n��'-<���<y�*���/��4�w���Gxf�' �yr���'!�,O�������<�D��x�(����������O]��N���T�X�c�.���:�/��� 9�c*��� ���'�R���<~������U_����k{�''x������h��O��<9������,������l�w�y��4�&��y��+�z�a)I=0��� L<&��s�E�A���� �*�����"��7j�+o7��-�������r���������N�w�D��?�.M@���p��e���3�{�g._��|��`]�PZ|
��>���"�rdqY�,����Zp��CP�TD��:�q������+��<��G�X��#�rL�`r�E�/��Uw��~�d> [v�qou����>���x�S�/��Eah��#}��i����rdnw ���K�&��4�m�R��"9�[�p�8c���!Z1��5Y,&V�\�.�0w�������8$����y 8$Y ���; 'M��i������GO����;�����"ck��s{N��mm}+���{�gF����}��uO�8�����\�U����@����C�������}K��7KY�#����� E��
�B�In����m��K�2#��Z��J�uuJ��.VbK��J��h�+�d��<��~M���k��T��EV��������H!����7p����L4"�%*XI%X�Z^ �I��<�����U���f�Yg�X~d/w�K�]����rN(�ZN��]��X-���X��h,��9�,�����z�r����� ��)��|�Z����Y��F��5�r�~:lr����m�%5�)���d���`�|�����|�/���WV��+�{���`_Qq�S��O�\�g{�OnI*���������<������G�YZ�Z�����7R+��������X
�el��4N>��8�:���X}u�q(�2�
��1��P��0#��J�=-���)���F���3�-M��O��J����p��7f���?]�����XS�j��\
y],����J�W����e8�C@.�>�����H.rw����^��^4��$b���w�T�����6�-z�b[n�G��40K�{.����{����b�}�U��S+&sjH�?��r-W(�Z��`����<�� 0JV�`�a`E��~X�t���4TWpah��������_���!-�J5��*N�D�swY�3���&:!�r�PO�X(�m�y�,�������� ��HC�u�E���7��_�=�����?�Bx���7'�����n���;0n��B>$�R)����-��xF�y��6���-��z�H�I������N#g�
z�&$�%��pD�������4_�cLW�`���kq�z���~{���Z8�{�B]s����G}���]�� [����!n&�-����11^p��j���50^��0���Ww����kP�*{����2�"n?���e��R��m��uI�I���m���x[���+��s���cw�"w��~���z��e�1�KB������� �`�C�(p@�/*������|�'�y��c+���x����y���� 5cD������:8(R�����$�x�7������������V�2�O!k���\�_��W��Ay^���,Q;�mCK� ~�F�B� �K�6�>X�Q"�p�G�[�a������� ��}�?+��=q
����#��"vwU.�k�'�J��$ u�����9�."� ,����*TE�*����Z4q���_��@.��:sInn���$��_���W.�#8��w������n�1������R��g���.fj�+����|�bX��m'�k�sW���crg5����
[��kv�I��/�����d�ez�'��7�~MU�C���r��e���������j��0#��������[mi���X���N��+3�RLz��~������o��J6I��jp�D�Y�j�A������9�_j"� ���Xs��Ux A1B��� g�Z_GHbb�U���
N����V��Zc1��),R�48�������6a�I)�f����vs;i����gb��8�%E>��������=f�
���Yciy�^��,0��t=����`N���'%��uz��B�
��t�`�R�D���I��g��������gq��!��7�x�����F��+�wx��g_�<�<k���� � �����[����������W?�����M��������Z��=g|t�I\#Gs!�l�p����ig��VN�o��qy[������"��s�6�^�6J��Y����0+��09�Q��Q����t�:uIR09����y(�df��yJC�4]��&�9������~�y
�=i������2�e�~KH��.�5L;���]���#K�K�$J�����Oo���*�*l3�J}������V�.��uw.[�
�9������v|�$}���e#K����'��y��'�������^�����[_����-���.g���Z�Z�g�m~Y7p?5}����W~�����{���[?O/S������L� !���b4��O����6��pKQ���Q%��v���-�����] o'�#�r/"