plan time of MASSIVE partitioning ...
hello everybody,
we came across an issue which turned out to be more serious than previously expected.
imagine a system with, say, 1000 partitions (heavily indexed) or so. the time taken by the planner is already fairly heavy in this case.
i tried this one with 5000 unindexed tables (just one col):
test=# \timing
Timing is on.
test=# prepare x(int4) AS select * from t_data order by id desc;
PREPARE
Time: 361.552 ms
you will see similar or higher runtimes in case of 500 partitions and a handful of indexes.
does anybody see a potential way to do a shortcut through the planner?
a prepared query is no solution here as constraint exclusion would be dead in this case (making the entire thing an even bigger drama).
did anybody think of a solution to this problem.
or more precisely: can there be a solution to this problem?
many thanks,
hans
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
* PostgreSQL - Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
did anybody think of a solution to this problem.
or more precisely: can there be a solution to this problem?
Please post to the correct list (-performance) and provide information
like PG version, postgresql.conf, the actual table definition, the
resulting query plan, etc, etc...
Thanks,
Stephen
On Sep 3, 2010, at 2:04 PM, Stephen Frost wrote:
* PostgreSQL - Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
did anybody think of a solution to this problem.
or more precisely: can there be a solution to this problem?Please post to the correct list (-performance) and provide information
like PG version, postgresql.conf, the actual table definition, the
resulting query plan, etc, etc...Thanks,
Stephen
hello stephen,
this seems like more a developer question to me than a pre performance one.
it is not related to the table structure at all - it is basically an issue with incredibly large inheritance lists.
it applies to postgres 9 and most likely to everything before.
postgresql.conf is not relevant at all at this point.
the plan is pretty fine.
the question is rather: does anybody see a chance to handle such lists more efficiently inside postgres?
also, it is not the point if my data structure is sane or not. it is really more generic - namely a shortcut for this case inside the planing process.
many thanks,
hans
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
* PostgreSQL - Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
this seems like more a developer question to me than a pre performance one.
it is not related to the table structure at all - it is basically an issue with incredibly large inheritance lists.
it applies to postgres 9 and most likely to everything before.
postgresql.conf is not relevant at all at this point.
Really? What's constraint_exclusion set to? Is GEQO getting used?
What are the GEQO parameters set to? Do you have any CHECK constraints
on the tables?
If you want someone else to build a test case and start looking into it,
it's best to not make them have to guess at what you've done.
the plan is pretty fine.
the question is rather: does anybody see a chance to handle such lists more efficiently inside postgres?
also, it is not the point if my data structure is sane or not. it is really more generic - namely a shortcut for this case inside the planing process.
Coming up with cases where PG doesn't perform well in a completely
contrived unrealistic environment isn't likely to impress anyone to
do anything.
A small (but complete..) test case which mimics a real world environment
and real world problem would go alot farther. I can certainly believe
that people out there have partitions set up with lots of tables and
that it will likely grow- but they probably also have CHECK constraints,
have tweaked what constraint_exclusion is set to, have adjusted their
work_mem and related settings, maybe tweaked some planner GUCs, etc,
etc.
This is an area I'm actually interested in and curious about, I'd rather
work together on it than be told that the questions I'm asking aren't
relevant.
Thanks,
Stephen
2010/9/3 PostgreSQL - Hans-Jürgen Schönig <postgres@cybertec.at>:
i tried this one with 5000 unindexed tables (just one col):
test=# \timing
Timing is on.
test=# prepare x(int4) AS select * from t_data order by id desc;
PREPARE
Time: 361.552 msyou will see similar or higher runtimes in case of 500 partitions and a handful of indexes.
I'd like to see (1) a script to reproduce your test environment (as
Stephen also requested) and (2) gprof or oprofile results.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company
=?iso-8859-1?Q?PostgreSQL_-_Hans-J=FCrgen_Sch=F6nig?= <postgres@cybertec.at> writes:
imagine a system with, say, 1000 partitions (heavily indexed) or so. the time taken by the planner is already fairly heavy in this case.
As the fine manual points out, the current scheme for managing
partitioned tables isn't intended to scale past a few dozen partitions.
I think we'll be able to do better when we have an explicit
representation of partitioning, since then the planner won't
have to expend large amounts of effort reverse-engineering knowledge
about how an inheritance tree is partitioned. Before that happens,
it's not really worth the trouble to worry about such cases.
regards, tom lane
On Sep 3, 2010, at 4:40 PM, Tom Lane wrote:
=?iso-8859-1?Q?PostgreSQL_-_Hans-J=FCrgen_Sch=F6nig?= <postgres@cybertec.at> writes:
imagine a system with, say, 1000 partitions (heavily indexed) or so. the time taken by the planner is already fairly heavy in this case.
As the fine manual points out, the current scheme for managing
partitioned tables isn't intended to scale past a few dozen partitions.I think we'll be able to do better when we have an explicit
representation of partitioning, since then the planner won't
have to expend large amounts of effort reverse-engineering knowledge
about how an inheritance tree is partitioned. Before that happens,
it's not really worth the trouble to worry about such cases.regards, tom lane
thank you ... - the manual is clear here but we wanted to see if there is some reasonably low hanging fruit to get around this.
it is no solution but at least a clear statement ...
many thanks,
hans
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
On Tue, Sep 7, 2010 at 2:14 PM, Boszormenyi Zoltan <zb@cybertec.at> wrote:
Hi,
Robert Haas írta:
2010/9/3 PostgreSQL - Hans-Jürgen Schönig <postgres@cybertec.at>:
i tried this one with 5000 unindexed tables (just one col):
test=# \timing
Timing is on.
test=# prepare x(int4) AS select * from t_data order by id desc;
PREPARE
Time: 361.552 msyou will see similar or higher runtimes in case of 500 partitions and a handful of indexes.
I'd like to see (1) a script to reproduce your test environment (as
Stephen also requested) and (2) gprof or oprofile results.attached are the test scripts, create_tables.sql and childtables.sql.
The following query takes 4.7 seconds according to psql with \timing on:
EXPLAIN SELECT * FROM qdrs
WHERE streamstart BETWEEN '2010-04-06' AND '2010-06-25'
ORDER BY streamhash;
Neat. Have you checked what effect this has on memory consumption?
Also, don't forget to add it to
https://commitfest.postgresql.org/action/commitfest_view/open
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company
Import Notes
Reply to msg id not found: 4C868118.8020708@cybertec.at
hello ...
no, we have not checked memory consumption.
there is still some stuff left to optimize away - it seems we are going close to O(n^2) somewhere.
"equal" is called really often in our sample case as well:
ach sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
18.87 0.80 0.80 4812 0.00 0.00 make_canonical_pathkey
15.33 1.45 0.65 4811 0.00 0.00
get_eclass_for_sort_expr
14.15 2.05 0.60 8342410 0.00 0.00 equal
6.13 2.31 0.26 229172 0.00 0.00 SearchCatCache
3.66 2.47 0.16 5788835 0.00 0.00 _equalList
3.07 2.60 0.13 1450043 0.00 0.00
hash_search_with_hash_value
2.36 2.70 0.10 2272545 0.00 0.00 AllocSetAlloc
2.12 2.79 0.09 811460 0.00 0.00 hash_any
1.89 2.87 0.08 3014983 0.00 0.00 list_head
1.89 2.95 0.08 574526 0.00 0.00 _bt_compare
1.77 3.02 0.08 11577670 0.00 0.00 list_head
1.42 3.08 0.06 1136 0.00 0.00 tzload
0.94 3.12 0.04 2992373 0.00 0.00 AllocSetFreeIndex
look at the number of calls ...
"equal" is scary ...
make_canonical_pathkey is fixed it seems.
get_eclass_for_sort_expr seems a little more complex to fix.
great you like it ...
regards,
hans
On Sep 8, 2010, at 3:54 PM, Robert Haas wrote:
On Tue, Sep 7, 2010 at 2:14 PM, Boszormenyi Zoltan <zb@cybertec.at> wrote:
Hi,
Robert Haas írta:
2010/9/3 PostgreSQL - Hans-Jürgen Schönig <postgres@cybertec.at>:
i tried this one with 5000 unindexed tables (just one col):
test=# \timing
Timing is on.
test=# prepare x(int4) AS select * from t_data order by id desc;
PREPARE
Time: 361.552 msyou will see similar or higher runtimes in case of 500 partitions and a handful of indexes.
I'd like to see (1) a script to reproduce your test environment (as
Stephen also requested) and (2) gprof or oprofile results.attached are the test scripts, create_tables.sql and childtables.sql.
The following query takes 4.7 seconds according to psql with \timing on:
EXPLAIN SELECT * FROM qdrs
WHERE streamstart BETWEEN '2010-04-06' AND '2010-06-25'
ORDER BY streamhash;Neat. Have you checked what effect this has on memory consumption?
Also, don't forget to add it to
https://commitfest.postgresql.org/action/commitfest_view/open--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de
* Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
no, we have not checked memory consumption.
there is still some stuff left to optimize away - it seems we are going close to O(n^2) somewhere.
"equal" is called really often in our sample case as well:
Did the mail with the scripts, etc, get hung up due to size or
something..? I didn't see it on the mailing list nor in the archives..
If so, could you post them somewhere so others could look..?
Thanks,
Stephen
here is the patch again.
we accidentally attached a wrong test file to the original posting so it grew to big. we had to revoke it from the moderator (this happens if you code from 8am to 10pm).
here is just the patch - it is nice and small.
you can easily test it by making yourself a nice parent table, many subtables (hundreds or thousands) and a decent number of indexes per partition.
then run PREPARE with \timing to see what happens.
you should get scary planning times. the more potential indexes and tables the more scary it will be.
using this wonderful RB tree the time for this function call goes down to basically zero.
i hope this is something which is useful to some folks out there.
many thanks,
hans
Attachments:
canon-pathkeys-as-rbtree-3-ctxdiff.patchapplication/octet-stream; name=canon-pathkeys-as-rbtree-3-ctxdiff.patchDownload
diff -dcrpN postgresql-9.0rc1.orig/src/backend/nodes/Makefile postgresql-9.0rc1/src/backend/nodes/Makefile
*** postgresql-9.0rc1.orig/src/backend/nodes/Makefile 2008-02-19 11:30:07.000000000 +0100
--- postgresql-9.0rc1/src/backend/nodes/Makefile 2010-09-07 10:20:24.000000000 +0200
*************** subdir = src/backend/nodes
*** 12,18 ****
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
! OBJS = nodeFuncs.o nodes.o list.o bitmapset.o tidbitmap.o \
copyfuncs.o equalfuncs.o makefuncs.o \
outfuncs.o readfuncs.o print.o read.o params.o value.o
--- 12,18 ----
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
! OBJS = nodeFuncs.o nodes.o list.o tree.o bitmapset.o tidbitmap.o \
copyfuncs.o equalfuncs.o makefuncs.o \
outfuncs.o readfuncs.o print.o read.o params.o value.o
diff -dcrpN postgresql-9.0rc1.orig/src/backend/nodes/outfuncs.c postgresql-9.0rc1/src/backend/nodes/outfuncs.c
*** postgresql-9.0rc1.orig/src/backend/nodes/outfuncs.c 2010-08-18 17:22:00.000000000 +0200
--- postgresql-9.0rc1/src/backend/nodes/outfuncs.c 2010-09-07 10:18:00.000000000 +0200
*************** _outList(StringInfo str, List *node)
*** 175,180 ****
--- 175,198 ----
appendStringInfoChar(str, ')');
}
+ static void
+ _outTree(StringInfo str, Tree *node)
+ {
+ TreeCell *element;
+
+ appendStringInfoChar(str, '(');
+
+ rb_begin_iterate(node->tree, LeftRightWalk);
+ element = (TreeCell *)rb_iterate(node->tree);
+ while (element)
+ {
+ _outNode(str, element->node);
+ element = (TreeCell *)rb_iterate(node->tree);
+ }
+
+ appendStringInfoChar(str, ')');
+ }
+
/*
* _outBitmapset -
* converts a bitmap set of integers
*************** _outPlannerInfo(StringInfo str, PlannerI
*** 1545,1551 ****
WRITE_NODE_FIELD(init_plans);
WRITE_NODE_FIELD(cte_plan_ids);
WRITE_NODE_FIELD(eq_classes);
! WRITE_NODE_FIELD(canon_pathkeys);
WRITE_NODE_FIELD(left_join_clauses);
WRITE_NODE_FIELD(right_join_clauses);
WRITE_NODE_FIELD(full_join_clauses);
--- 1563,1569 ----
WRITE_NODE_FIELD(init_plans);
WRITE_NODE_FIELD(cte_plan_ids);
WRITE_NODE_FIELD(eq_classes);
! WRITE_NODE_FIELD(rb_canon_pathkeys);
WRITE_NODE_FIELD(left_join_clauses);
WRITE_NODE_FIELD(right_join_clauses);
WRITE_NODE_FIELD(full_join_clauses);
*************** _outNode(StringInfo str, void *obj)
*** 2451,2456 ****
--- 2469,2476 ----
appendStringInfo(str, "<>");
else if (IsA(obj, List) ||IsA(obj, IntList) || IsA(obj, OidList))
_outList(str, obj);
+ else if (IsA(obj, Tree))
+ _outTree(str, obj);
else if (IsA(obj, Integer) ||
IsA(obj, Float) ||
IsA(obj, String) ||
diff -dcrpN postgresql-9.0rc1.orig/src/backend/nodes/tree.c postgresql-9.0rc1/src/backend/nodes/tree.c
*** postgresql-9.0rc1.orig/src/backend/nodes/tree.c 1970-01-01 01:00:00.000000000 +0100
--- postgresql-9.0rc1/src/backend/nodes/tree.c 2010-09-07 14:06:42.000000000 +0200
***************
*** 0 ****
--- 1,65 ----
+ /*-------------------------------------------------------------------------
+ *
+ * tree.c
+ * implementation for PostgreSQL generic rbtree package
+ *
+ *
+ * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.74 2010/02/13 02:34:11 tgl Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+ #include "postgres.h"
+
+ #include "nodes/pg_tree.h"
+ #include "utils/rbtree.h"
+
+ RBNode *tree_allocfunc(void *arg)
+ {
+ return (RBNode *)palloc(sizeof(TreeCell));
+ }
+
+ /*
+ * Return a freshly allocated Tree.
+ */
+ Tree *
+ new_tree(rb_comparator comparator, rb_allocfunc allocfunc, void *arg)
+ {
+ Tree *tree = makeNode(Tree);
+
+ tree->tree = rb_create(sizeof(TreeCell), comparator, NULL, allocfunc, NULL, arg);
+
+ return tree;
+ }
+
+ Node *
+ tree_find(Tree *tree, Node *node)
+ {
+ TreeCell *cell = palloc(sizeof(TreeCell));
+ TreeCell *result;
+
+ cell->node = node;
+
+ result = (TreeCell *)rb_find(tree->tree, (RBNode *)cell);
+
+ pfree(cell);
+
+ if (result == NULL)
+ return NULL;
+
+ return result->node;
+ }
+
+ void
+ tree_add(Tree *tree, Node *node)
+ {
+ TreeCell *rbnode = palloc(sizeof(TreeCell));
+ bool isNew;
+
+ rbnode->node = node;
+ rb_insert(tree->tree, (RBNode *)rbnode, &isNew);
+ }
diff -dcrpN postgresql-9.0rc1.orig/src/backend/optimizer/path/pathkeys.c postgresql-9.0rc1/src/backend/optimizer/path/pathkeys.c
*** postgresql-9.0rc1.orig/src/backend/optimizer/path/pathkeys.c 2010-02-26 03:00:45.000000000 +0100
--- postgresql-9.0rc1/src/backend/optimizer/path/pathkeys.c 2010-09-07 15:41:49.000000000 +0200
*************** makePathKey(EquivalenceClass *eclass, Oi
*** 71,76 ****
--- 71,137 ----
return pk;
}
+ RBNode *
+ pathkeys_allocfunc(void *arg)
+ {
+ PlannerInfo *root = arg;
+ MemoryContext oldcontext;
+ RBNode *node;
+
+ oldcontext = MemoryContextSwitchTo(root->planner_cxt);
+
+ node = palloc(sizeof(TreeCell));
+
+ MemoryContextSwitchTo(oldcontext);
+
+ return node;
+ }
+
+ int
+ pathkeys_comparator(const RBNode *a, const RBNode *b, void *arg)
+ {
+ TreeCell *left = (TreeCell *)a;
+ TreeCell *right = (TreeCell *)b;
+ PathKey *pk_left = (PathKey *)left->node;
+ PathKey *pk_right = (PathKey *)right->node;
+ long val1, val2;
+
+ Assert((pk_left != NULL));
+ Assert((pk_right != NULL));
+
+ val1 = (long)pk_left->pk_eclass;
+ val2 = (long)pk_right->pk_eclass;
+
+ if (val1 < val2)
+ return -1;
+ else if (val1 > val2)
+ return 1;
+
+ if (pk_left->pk_opfamily < pk_right->pk_opfamily)
+ return -1;
+ else if (pk_left->pk_opfamily > pk_right->pk_opfamily)
+ return 1;
+
+ if (pk_left->pk_strategy < pk_right->pk_strategy)
+ return -1;
+ else if (pk_left->pk_strategy > pk_right->pk_strategy)
+ return 1;
+
+ if (pk_left->pk_nulls_first < pk_right->pk_nulls_first)
+ return -1;
+ else if (pk_left->pk_nulls_first > pk_right->pk_nulls_first)
+ return 1;
+
+ if (pk_left == NULL)
+ elog(ERROR, "pk_left NULL");
+ if (pk_right == NULL)
+ elog(ERROR, "pk_right NULL");
+
+ return 0;
+ }
+
+
+
/*
* make_canonical_pathkey
* Given the parameters for a PathKey, find any pre-existing matching
*************** make_canonical_pathkey(PlannerInfo *root
*** 85,119 ****
EquivalenceClass *eclass, Oid opfamily,
int strategy, bool nulls_first)
{
! PathKey *pk;
! ListCell *lc;
MemoryContext oldcontext;
/* The passed eclass might be non-canonical, so chase up to the top */
while (eclass->ec_merged)
eclass = eclass->ec_merged;
- foreach(lc, root->canon_pathkeys)
- {
- pk = (PathKey *) lfirst(lc);
- if (eclass == pk->pk_eclass &&
- opfamily == pk->pk_opfamily &&
- strategy == pk->pk_strategy &&
- nulls_first == pk->pk_nulls_first)
- return pk;
- }
-
/*
* Be sure canonical pathkeys are allocated in the main planning context.
* Not an issue in normal planning, but it is for GEQO.
*/
oldcontext = MemoryContextSwitchTo(root->planner_cxt);
! pk = makePathKey(eclass, opfamily, strategy, nulls_first);
! root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
MemoryContextSwitchTo(oldcontext);
return pk;
}
--- 146,178 ----
EquivalenceClass *eclass, Oid opfamily,
int strategy, bool nulls_first)
{
! PathKey *pk, *pk_new;
MemoryContext oldcontext;
/* The passed eclass might be non-canonical, so chase up to the top */
while (eclass->ec_merged)
eclass = eclass->ec_merged;
/*
* Be sure canonical pathkeys are allocated in the main planning context.
* Not an issue in normal planning, but it is for GEQO.
*/
oldcontext = MemoryContextSwitchTo(root->planner_cxt);
! pk_new = makePathKey(eclass, opfamily, strategy, nulls_first);
MemoryContextSwitchTo(oldcontext);
+ pk = (PathKey *) tree_find(root->rb_canon_pathkeys, (Node *)pk_new);
+
+ if (pk)
+ pfree(pk_new);
+ else
+ {
+ tree_add(root->rb_canon_pathkeys, (Node *)pk_new);
+ pk = pk_new;
+ }
+
return pk;
}
diff -dcrpN postgresql-9.0rc1.orig/src/backend/optimizer/plan/planmain.c postgresql-9.0rc1/src/backend/optimizer/plan/planmain.c
*** postgresql-9.0rc1.orig/src/backend/optimizer/plan/planmain.c 2010-07-06 21:18:56.000000000 +0200
--- postgresql-9.0rc1/src/backend/optimizer/plan/planmain.c 2010-09-07 14:29:40.000000000 +0200
***************
*** 20,31 ****
--- 20,33 ----
*/
#include "postgres.h"
+ #include "nodes/pg_tree.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
+ #include "utils/rbtree.h"
#include "utils/selfuncs.h"
*************** query_planner(PlannerInfo *root, List *t
*** 116,122 ****
* We still are required to canonicalize any pathkeys, in case it's
* something like "SELECT 2+2 ORDER BY 1".
*/
! root->canon_pathkeys = NIL;
root->query_pathkeys = canonicalize_pathkeys(root,
root->query_pathkeys);
root->group_pathkeys = canonicalize_pathkeys(root,
--- 118,124 ----
* We still are required to canonicalize any pathkeys, in case it's
* something like "SELECT 2+2 ORDER BY 1".
*/
! root->rb_canon_pathkeys = new_tree(pathkeys_comparator, pathkeys_allocfunc, root);
root->query_pathkeys = canonicalize_pathkeys(root,
root->query_pathkeys);
root->group_pathkeys = canonicalize_pathkeys(root,
*************** query_planner(PlannerInfo *root, List *t
*** 144,150 ****
root->join_rel_hash = NULL;
root->join_rel_level = NULL;
root->join_cur_level = 0;
! root->canon_pathkeys = NIL;
root->left_join_clauses = NIL;
root->right_join_clauses = NIL;
root->full_join_clauses = NIL;
--- 146,152 ----
root->join_rel_hash = NULL;
root->join_rel_level = NULL;
root->join_cur_level = 0;
! root->rb_canon_pathkeys = new_tree(pathkeys_comparator, pathkeys_allocfunc, root);
root->left_join_clauses = NIL;
root->right_join_clauses = NIL;
root->full_join_clauses = NIL;
diff -dcrpN postgresql-9.0rc1.orig/src/backend/optimizer/plan/planner.c postgresql-9.0rc1/src/backend/optimizer/plan/planner.c
*** postgresql-9.0rc1.orig/src/backend/optimizer/plan/planner.c 2010-03-30 23:58:10.000000000 +0200
--- postgresql-9.0rc1/src/backend/optimizer/plan/planner.c 2010-09-07 14:12:39.000000000 +0200
*************** subquery_planner(PlannerGlobal *glob, Qu
*** 305,310 ****
--- 305,311 ----
root->init_plans = NIL;
root->cte_plan_ids = NIL;
root->eq_classes = NIL;
+ root->rb_canon_pathkeys = new_tree(pathkeys_comparator, pathkeys_allocfunc, root);
root->append_rel_list = NIL;
root->rowMarks = NIL;
root->hasInheritedTarget = false;
diff -dcrpN postgresql-9.0rc1.orig/src/include/nodes/nodes.h postgresql-9.0rc1/src/include/nodes/nodes.h
*** postgresql-9.0rc1.orig/src/include/nodes/nodes.h 2010-03-29 00:59:33.000000000 +0200
--- postgresql-9.0rc1/src/include/nodes/nodes.h 2010-09-06 13:11:47.000000000 +0200
*************** typedef enum NodeTag
*** 252,257 ****
--- 252,262 ----
T_OidList,
/*
+ * TAGS FOR TREE NODES (pg_tree.h)
+ */
+ T_Tree,
+
+ /*
* TAGS FOR STATEMENT NODES (mostly in parsenodes.h)
*/
T_Query = 700,
diff -dcrpN postgresql-9.0rc1.orig/src/include/nodes/pg_tree.h postgresql-9.0rc1/src/include/nodes/pg_tree.h
*** postgresql-9.0rc1.orig/src/include/nodes/pg_tree.h 1970-01-01 01:00:00.000000000 +0100
--- postgresql-9.0rc1/src/include/nodes/pg_tree.h 2010-09-07 14:06:09.000000000 +0200
***************
*** 0 ****
--- 1,50 ----
+ /*-------------------------------------------------------------------------
+ *
+ * pg_tree.h
+ * interface for PostgreSQL generic rbtree package
+ *
+ * This package implements rbtree of Node * elements of the same type.
+ * It is a replacement of List for dealing with O(n^2) behaviour
+ * found with long lists.
+ *
+ * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * $PostgreSQL$
+ *
+ *-------------------------------------------------------------------------
+ */
+ #ifndef PG_TREE_H
+ #define PG_TREE_H
+
+ #include "nodes/nodes.h"
+ #include "utils/rbtree.h"
+
+ typedef struct TreeCell
+ {
+ RBNode treenode;
+ Node *node;
+ } TreeCell;
+
+
+ typedef struct Tree
+ {
+ NodeTag type; /* T_Tree */
+ RBTree *tree;
+ } Tree;
+
+ extern RBNode *tree_allocfunc(void *arg);
+
+ extern Tree *new_tree(rb_comparator comparator, rb_allocfunc allocfunc, void *arg);
+ extern Node *tree_find(Tree *tree, Node *node);
+ extern void tree_add(Tree *tree, Node *node);
+
+ /*
+ * tforeach -
+ * a convenience macro which loops through the tree elements
+ * in "inorder" walk to make it look like a list
+ */
+ #define tforeach(cell, t) \
+ for (rb_begin_iterate(t, LeftRightWalk) , (cell) = (TreeCell *)rb_iterate(t); (cell) != NULL; (cell) = (TreeCell *)rb_iterate(t))
+
+ #endif /* PG_TREE_H */
diff -dcrpN postgresql-9.0rc1.orig/src/include/nodes/primnodes.h postgresql-9.0rc1/src/include/nodes/primnodes.h
*** postgresql-9.0rc1.orig/src/include/nodes/primnodes.h 2010-02-26 03:01:25.000000000 +0100
--- postgresql-9.0rc1/src/include/nodes/primnodes.h 2010-09-07 10:16:45.000000000 +0200
***************
*** 19,24 ****
--- 19,25 ----
#include "access/attnum.h"
#include "nodes/pg_list.h"
+ #include "nodes/pg_tree.h"
/* ----------------------------------------------------------------
diff -dcrpN postgresql-9.0rc1.orig/src/include/nodes/relation.h postgresql-9.0rc1/src/include/nodes/relation.h
*** postgresql-9.0rc1.orig/src/include/nodes/relation.h 2010-07-06 21:19:00.000000000 +0200
--- postgresql-9.0rc1/src/include/nodes/relation.h 2010-09-07 14:31:16.000000000 +0200
*************** typedef struct PlannerInfo
*** 160,166 ****
List *eq_classes; /* list of active EquivalenceClasses */
! List *canon_pathkeys; /* list of "canonical" PathKeys */
List *left_join_clauses; /* list of RestrictInfos for
* mergejoinable outer join clauses
--- 160,166 ----
List *eq_classes; /* list of active EquivalenceClasses */
! Tree *rb_canon_pathkeys; /* tree of "canonical" PathKeys */
List *left_join_clauses; /* list of RestrictInfos for
* mergejoinable outer join clauses
diff -dcrpN postgresql-9.0rc1.orig/src/include/optimizer/paths.h postgresql-9.0rc1/src/include/optimizer/paths.h
*** postgresql-9.0rc1.orig/src/include/optimizer/paths.h 2010-01-02 17:58:07.000000000 +0100
--- postgresql-9.0rc1/src/include/optimizer/paths.h 2010-09-07 14:11:28.000000000 +0200
***************
*** 15,20 ****
--- 15,21 ----
#define PATHS_H
#include "nodes/relation.h"
+ #include "utils/rbtree.h"
/*
*************** typedef enum
*** 152,157 ****
--- 153,161 ----
PATHKEYS_DIFFERENT /* neither pathkey includes the other */
} PathKeysComparison;
+ extern RBNode *pathkeys_allocfunc(void *arg);
+ extern int pathkeys_comparator(const RBNode *a, const RBNode *b, void *arg);
+
extern List *canonicalize_pathkeys(PlannerInfo *root, List *pathkeys);
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
Binary files postgresql-9.0rc1.orig/src/timezone/gmon.out and postgresql-9.0rc1/src/timezone/gmon.out differ
* Robert Haas (robertmhaas@gmail.com) wrote:
Neat. Have you checked what effect this has on memory consumption?
Also, don't forget to add it to
https://commitfest.postgresql.org/action/commitfest_view/open
Would be good to have the patch updated to be against HEAD before
posting to the commitfest.
Thanks,
Stephen
On Sep 8, 2010, at 4:57 PM, Stephen Frost wrote:
* Robert Haas (robertmhaas@gmail.com) wrote:
Neat. Have you checked what effect this has on memory consumption?
Also, don't forget to add it to
https://commitfest.postgresql.org/action/commitfest_view/openWould be good to have the patch updated to be against HEAD before
posting to the commitfest.Thanks,
Stephen
we will definitely provide something which is for HEAD.
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.
regards,
hans
--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de
* Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.
An 18% increase is certainly nice, provided it doesn't slow down or
break other things.. I'm looking through the patch now actually and
I'm not really happy with the naming, comments, or some of the code
flow, but I think the concept looks reasonable.
Thanks,
Stephen
2010/9/8 Hans-Jürgen Schönig <postgres@cybertec.at>:
On Sep 8, 2010, at 4:57 PM, Stephen Frost wrote:
* Robert Haas (robertmhaas@gmail.com) wrote:
Neat. Have you checked what effect this has on memory consumption?
Also, don't forget to add it to
https://commitfest.postgresql.org/action/commitfest_view/openWould be good to have the patch updated to be against HEAD before
posting to the commitfest.we will definitely provide something which is for HEAD.
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.
Just remember that four small patches (say) are apt to get committed
faster than one big one.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company
* Robert Haas (robertmhaas@gmail.com) wrote:
2010/9/8 Hans-Jürgen Schönig <postgres@cybertec.at>:
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.Just remember that four small patches (say) are apt to get committed
faster than one big one.
Indeed, but code like this makes me wonder if this is really working the
way it's supposed to:
+ val1 = (long)pk_left->pk_eclass;
+ val2 = (long)pk_right->pk_eclass;
+
+ if (val1 < val2)
+ return -1;
+ else if (val1 > val2)
+ return 1;
Have you compared how big the tree gets to the size of the list it's
supposed to be replacing..?
Thanks,
Stephen
Excerpts from Stephen Frost's message of mié sep 08 11:26:55 -0400 2010:
* Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.An 18% increase is certainly nice, provided it doesn't slow down or
break other things.. I'm looking through the patch now actually and
I'm not really happy with the naming, comments, or some of the code
flow, but I think the concept looks reasonable.
I don't understand the layering between pg_tree and rbtree. Why does it
exist at all? At first I thought this was another implementation of
rbtrees, but then I noticed it sits on top of it. Is this really
necessary?
--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support
=?iso-8859-1?Q?Hans-J=FCrgen_Sch=F6nig?= <postgres@cybertec.at> writes:
here is the patch again.
This patch seems remarkably documentation-free. What is it trying to
accomplish and what is it doing to the planner data structures?
(Which do have documentation BTW.) Also, what will it do to runtime
in normal cases where the pathkeys list isn't that long?
regards, tom lane
Stephen Frost �rta:
* Robert Haas (robertmhaas@gmail.com) wrote:
2010/9/8 Hans-J�rgen Sch�nig <postgres@cybertec.at>:
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.Just remember that four small patches (say) are apt to get committed
faster than one big one.Indeed, but code like this makes me wonder if this is really working the
way it's supposed to:+ val1 = (long)pk_left->pk_eclass; + val2 = (long)pk_right->pk_eclass; + + if (val1 < val2) + return -1; + else if (val1 > val2) + return 1;
The original code checked for pointers being equal among
other conditions. This was an (almost) straight conversion
to a comparison function for rbtree. Do you mean casting
the pointer to long? Yes, e.g. on 64-bit Windows it wouldn't
work. Back to plain pointer comparison.
Have you compared how big the tree gets to the size of the list it's
supposed to be replacing..?
No, but I think it's obvious. Now we have one TreeCell
where we had one ListCell.
Best regards,
Zolt�n B�sz�rm�nyi
--
----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
Gr�hrm�hlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Alvaro Herrera írta:
Excerpts from Stephen Frost's message of mié sep 08 11:26:55 -0400 2010:
* Hans-Jürgen Schönig (postgres@cybertec.at) wrote:
but, it seems the problem we are looking is not sufficiently fixed yet.
in our case we shaved off some 18% of planning time or so - looking at the other top 2 functions i got the feeling that more can be done to reduce this. i guess we have to attack this as well.An 18% increase is certainly nice, provided it doesn't slow down or
break other things.. I'm looking through the patch now actually and
I'm not really happy with the naming, comments, or some of the code
flow, but I think the concept looks reasonable.I don't understand the layering between pg_tree and rbtree. Why does it
exist at all? At first I thought this was another implementation of
rbtrees, but then I noticed it sits on top of it. Is this really
necessary?
No, if it's acceptable to omit PlannerInfo from outfuncs.c.
Or at least its canon_pathkeys member. Otherwise yes, it's
necessary. We need to store (Node *) in a fast searchable way.
This applies to anything else that may need to be converted
from list to tree to decrease planning time. Like ec_members
in EquivalenceClass.
Best regards,
Zoltán Böszörményi
--
----------------------------------
Zoltán Böszörményi
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Stephen Frost <sfrost@snowman.net> writes:
Indeed, but code like this makes me wonder if this is really working the
way it's supposed to:
+ val1 = (long)pk_left->pk_eclass;
+ val2 = (long)pk_right->pk_eclass;
Ugh. Casting a pointer to long? We do have portable ways to do what
this is trying to do, but that is not one. (For example, this is
guaranteed to misbehave on 64-bit Windows.)
Offhand I think PointerGetDatum might be the best way.
regards, tom lane
Boszormenyi Zoltan <zb@cybertec.at> writes:
This applies to anything else that may need to be converted
from list to tree to decrease planning time. Like ec_members
in EquivalenceClass.
AFAIR, canonical pathkeys are the *only* thing in the planner where pure
pointer equality is interesting. So I doubt this hack is of any use for
EquivalenceClass, even if the lists were likely to be long which they
aren't.
regards, tom lane
Stephen Frost <sfrost@snowman.net> writes:
I'm not really happy with the naming, comments, or some of the code
flow, but I think the concept looks reasonable.
There seems to be a lot of unnecessary palloc/pfree traffic in this
implementation. Getting rid of that might help the speed.
regards, tom lane
Tom Lane �rta:
Boszormenyi Zoltan <zb@cybertec.at> writes:
This applies to anything else that may need to be converted
from list to tree to decrease planning time. Like ec_members
in EquivalenceClass.AFAIR, canonical pathkeys are the *only* thing in the planner where pure
pointer equality is interesting. So I doubt this hack is of any use for
EquivalenceClass, even if the lists were likely to be long which they
aren't.regards, tom lane
No, for EquivalanceClass->ec_member, I need to do something
funnier, like implement compare(Node *, Node *) and use that
instead of equal(Node *, Node *)... Something like nodeToString()
on both Node * and strcmp() the resulting strings.
--
----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
Gr�hrm�hlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Tom Lane �rta:
Stephen Frost <sfrost@snowman.net> writes:
I'm not really happy with the naming, comments, or some of the code
flow, but I think the concept looks reasonable.There seems to be a lot of unnecessary palloc/pfree traffic in this
implementation. Getting rid of that might help the speed.regards, tom lane
This was a first WIP implementation, I will look into it, thanks.
--
----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
Gr�hrm�hlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Boszormenyi Zoltan <zb@cybertec.at> writes:
Tom Lane �rta:
AFAIR, canonical pathkeys are the *only* thing in the planner where pure
pointer equality is interesting. So I doubt this hack is of any use for
EquivalenceClass, even if the lists were likely to be long which they
aren't.
No, for EquivalanceClass->ec_member, I need to do something
funnier, like implement compare(Node *, Node *) and use that
instead of equal(Node *, Node *)... Something like nodeToString()
on both Node * and strcmp() the resulting strings.
Well, (a) that doesn't work (hint: there are fields in nodes that are
intentionally ignored by equal()), and (b) I still don't believe that
there's an actual bottleneck there. ECs generally aren't very big.
regards, tom lane
Tom Lane �rta:
Boszormenyi Zoltan <zb@cybertec.at> writes:
Tom Lane �rta:
AFAIR, canonical pathkeys are the *only* thing in the planner where pure
pointer equality is interesting. So I doubt this hack is of any use for
EquivalenceClass, even if the lists were likely to be long which they
aren't.No, for EquivalanceClass->ec_member, I need to do something
funnier, like implement compare(Node *, Node *) and use that
instead of equal(Node *, Node *)... Something like nodeToString()
on both Node * and strcmp() the resulting strings.Well, (a) that doesn't work (hint: there are fields in nodes that are
intentionally ignored by equal()),
Then this compare() needs to work like equal(), which can
ignore the fields that are ignored by equal(), too.
nodeToString would need more space anyway and comparing
non-equal Nodes can return the !0 result faster.
and (b) I still don't believe that
there's an actual bottleneck there. ECs generally aren't very big.
Actually, PlannerInfo->eq_classes needs to be a Tree somehow,
the comparator function is not yet final in my head.
equal() is called over 8 million times with or without our patch:
without
% cumulative self self total
time seconds seconds calls s/call s/call name
18.87 0.80 0.80 4812 0.00 0.00 make_canonical_pathkey
15.33 1.45 0.65 4811 0.00 0.00
get_eclass_for_sort_expr
14.15 2.05 0.60 8342410 0.00 0.00 equal
6.13 2.31 0.26 229172 0.00 0.00 SearchCatCache
3.66 2.47 0.16 5788835 0.00 0.00 _equalList
3.07 2.60 0.13 1450043 0.00 0.00
hash_search_with_hash_value
2.36 2.70 0.10 2272545 0.00 0.00 AllocSetAlloc
2.12 2.79 0.09 811460 0.00 0.00 hash_any
1.89 2.87 0.08 3014983 0.00 0.00 list_head
1.89 2.95 0.08 574526 0.00 0.00 _bt_compare
1.77 3.02 0.08 11577670 0.00 0.00 list_head
1.42 3.08 0.06 1136 0.00 0.00 tzload
0.94 3.12 0.04 2992373 0.00 0.00 AllocSetFreeIndex
0.94 3.16 0.04 91427 0.00 0.00 _bt_checkkeys
...
with
% cumulative self self total
time seconds seconds calls s/call s/call name
24.51 0.88 0.88 4811 0.00 0.00
get_eclass_for_sort_expr
14.21 1.39 0.51 8342410 0.00 0.00 equal
8.22 1.69 0.30 5788835 0.00 0.00 _equalList
5.29 1.88 0.19 229172 0.00 0.00 SearchCatCache
2.51 1.97 0.09 1136 0.00 0.00 tzload
2.23 2.05 0.08 3014983 0.00 0.00 list_head
2.23 2.13 0.08 2283130 0.00 0.00 AllocSetAlloc
2.09 2.20 0.08 811547 0.00 0.00 hash_any
2.09 2.28 0.08 11577670 0.00 0.00 list_head
1.95 2.35 0.07 1450180 0.00 0.00
hash_search_with_hash_value
1.39 2.40 0.05 640690 0.00 0.00 _bt_compare
1.39 2.45 0.05 157944 0.00 0.00 LockAcquireExtended
1.39 2.50 0.05 11164 0.00 0.00 AllocSetCheck
1.11 2.54 0.04 3010547 0.00 0.00 AllocSetFreeIndex
1.11 2.58 0.04 874975 0.00 0.00 AllocSetFree
1.11 2.62 0.04 66211 0.00 0.00 heap_form_tuple
0.84 2.65 0.03 888128 0.00 0.00 LWLockRelease
...
The number of calls are the same for equal and _equalList
in both cases as you can see.
And if you compare the number of AllocSetAlloc calls,
it's actually smaller with our patch, so it's not that the
conversion to Tree caused this.
Best regards,
Zolt�n B�sz�rm�nyi
--
----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
Gr�hrm�hlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Boszormenyi Zoltan <zb@cybertec.at> writes:
equal() is called over 8 million times with or without our patch:
From where, though? You've provided not a shred of evidence that
searching large ec_member lists is the problem.
Also, did the test case you're using ever make it to the list?
regards, tom lane
Tom Lane �rta:
Boszormenyi Zoltan <zb@cybertec.at> writes:
equal() is called over 8 million times with or without our patch:
From where, though? You've provided not a shred of evidence that
searching large ec_member lists is the problem.
Indeed. I have put elog(NOTICE) calls in there to see which
lists is how long. It turned out that the length of ec_members is either 0
or 1, mostly 1, but the length of eq_classes is constantly growing.
This is what I need to attack then.
Also, did the test case you're using ever make it to the list?
No, because it was too large and because of the test case
accidentally contained confidential information, we asked
Bruce to delete it from the moderator queue.
Attached is a shortened test case that does the same and
also shows the same problem. The create_table.sql
creates the parent table, the table_generator.sql produces
the list of constraint excluded child tables and their indexes.
The gprof output of this is only slightly modified, the
number of equal() calls is still over 8 million, it is also
attached.
Best regards,
Zolt�n B�sz�rm�nyi
--
----------------------------------
Zolt�n B�sz�rm�nyi
Cybertec Sch�nig & Sch�nig GmbH
Gr�hrm�hlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de
http://www.postgresql.at/
Attachments:
gmon.log1.gzapplication/x-tar; name=gmon.log1.gzDownload
�8��L gmon.log1 ��[w������+�r^s���[�$3^;�x�����AKf��4�D����Y��T��������n�|*�vU�j����������&���X�UW��*iV�[�^5"���y�f����j�v�d�G�4���&_���U�'���������M>���(���?�|(%���v��,�mL?x�m?���;��"-�������J���j�feGo����o�� ��_�\��|���]R@G��z�(������FQ���l��?�M ��g�����G�m?��� ���"�@�}��|p���q�0�H�V&e�� ��[�:���|7Z;%��(��V���3�S�������)�}����Hdz����X��1)��V��V�k?���7m�V�:���h�&;���|.���<�Q����w��������Rcb�u�c��o��o��KN��O?I!�k��r�uD�+��{�><�C�:��?
\�����M���w"�]h�� d���V��s@0x0�B
���{Q�q�(���~���S��ul�������]�������e&������Hr�&!��@UW�_�ggB��O�N�VR���~W�P�Aa �8�����vQ�^u|O���w"�r��k���H�&n�eC�������rl��,r����sB0!��: �C��l]��NNhE�rK�s��Tr�3 '�7���g}��J�^HN�"�k��3i�:�����wq���z8��'���5�o8��ns.�L�]'$��FV)N�?���`��c� �s}�!�w��dS�3�|M��T|�Y
����Gy+�G���x�u^����`������O�$�
�������lT��������Nv�:w:M]{�Q���e�|�:���Dk���A���9o�3����p�&����c���u��yR���`��.��9t:�����������f��E����3��6�@���L8�v����gc�Lg1hd�\S��W���*s2���Q� l{.=�q���T��D~:}m[�\F#�
��9c:�W��%��Vi��Cs���� h:�W�C�C`E�� �ZgI��
�9l:�W�c�{��I�H����-|sFr�g$�Y���<�O]��%����N'8�����:�1� ���3�����~�s(�n�qU���w�=c�9��o0��-Y�;��|)��4i���t"��gM��g��>�)��#5���/�����Md���� wL��
Q�=iP^H��d�i�|����v���_PT���,�q�.���C-���`Fi�:�8�f9����������]����;����X����W�pU���ut"� 7��5�1� ����"7�q�_%E��3��m�i���1?�zKd��w�xs���A��b`C�\R��N#���M+-����Q��{��sCa�A*��1�k���O��]�9Y����N�{��� B{C�}[3%w*�1/���"W���b����1�yR��s��#���{V�&��L�-�&+���<��!~0�v@w��E=�������������q�]�I{M� pE��j{���C�����"{�2?OWa��m�co���9�����{�(�UhYi�<W���zW��R0L�S�������O�CHs��kRy����3 ��gW`��N�W�����w~��Y�����_���N���"hD| ������\+���V��^����;=yX��!���T����$��0wM��R�T���}z1��6&������������^���IM�� ���@\+$�n��me^��S��O����k�D����(f�5C9�7},�D��
�&��a���X'���~`wo�4�F����1��%$�FW����z]�.��p��`����p�P_:�96�0�4��w5QvTom�q*��c�4�����F����n����@x�q.��d=e� ����~�.����z�K{�O-c VH��`'����]���TXsh��e��K�,N��c�Kp�#�E5\F������]��v(�B�C� �Kv������}M��f�**�S8�u���\��w�f������QZ�Z�P�)�YdS���4iE��=�-�4(�z�)��uy#��y,�N
��G�Mv�Y�9���!�R�>���bk�O.��w��=���v��+��'