Join optimization for inheritance tables
Hi all,
We are working with Aster for the summer and we would like to bounce some ideas that we are having for some possible PostgreSQL extensions. In order to describe our ideas we will use the following example:
create table msg(
msg_id int,
msg text );
create table receiver(
msg_id int,
user_id int,
ts timestamp );
create table msg_100(
check ( 1 <= msg_id and msg_id < 100 )
) inherits (msg);
create table msg_200(
check ( 100 <= msg_id and msg_id < 200 )
) inherits (msg);
create table msg_300(
check ( 200 <= msg_id and msg_id < 300 )
) inherits (msg);
create table receiver_100(
check ( 1 <= msg_id and msg_id < 100 )
) inherits (receiver);
create table receiver_200(
check ( 100 <= msg_id and msg_id < 200 )
) inherits (receiver);
create table receiver_300(
check ( 200 <= msg_id and msg_id < 300 )
) inherits (receiver);
When we are issuing queries on one of the parent tables, like,
SELECT * FROM msg WHERE msg_id BETWEEN 50 AND 70;
PostgreSQL is smart enough to filter out child tables with check constraints that are refuted by the filter conditions. In this example, the optimizer will pick a plan that only considers the parent table 'msg' and one of the child tables 'msg_100':
Result
-> Append
-> Seq Scan on msg
Filter: ((msg_id >= 50) AND (msg_id <= 70))
-> Seq Scan on msg_100 msg
Filter: ((msg_id >= 50) AND (msg_id <= 70))
Plan costs are removed for simplicity of the presentation.
Now, if we issue a join query between the two parent tables, like,
SELECT * FROM msg m JOIN receiver r ON m.msg_id = r.msg_id;
the execution plan will be:
Merge Join
Merge Cond: (m.msg_id = r.msg_id)
-> Sort
Sort Key: m.msg_id
-> Append
-> Seq Scan on msg m
-> Seq Scan on msg_100 m
-> Seq Scan on msg_200 m
-> Seq Scan on msg_300 m
-> Sort
Sort Key: r.msg_id
-> Append
-> Seq Scan on receiver r
-> Seq Scan on receiver_100 r
-> Seq Scan on receiver_200 r
-> Seq Scan on receiver_300 r
During the planning phase, the optimizer treats an entire hierarchy as a single entity. Hence, it first considers the most efficient way to create the append paths for the two hierarchies, and then the best way to join them. However, there are some optimizations that are possible here, similar to the table filtering described above. In particular, instead of joining the two appends, we could "push down" the join to the child relations - that is, create pairwise joins between the children and then append the join results together.
Based on the check conditions of the children and the join predicate, it is possible to filter out joins that cannot produce any results. For example, joining 'msg_100' with 'receiver_300' is redundant since the check constraints of these two tables do not overlap. Tuples in 'msg_100' have 'msg_id' between 1 and 100, whereas tuples in 'receiver_300' have 'msg_id' between 200 and 300. Therefore, no tuples can be produce from this join.
A plan with such optimizations could be:
Result
-> Append
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg msg
-> Hash
-> Seq Scan on receiver receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg msg
-> Hash
-> Seq Scan on receiver_100 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg msg
-> Hash
-> Seq Scan on receiver_200 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg msg
-> Hash
-> Seq Scan on receiver_300 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_100 msg
-> Hash
-> Seq Scan on receiver receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_100 msg
-> Hash
-> Seq Scan on receiver_100 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_200 msg
-> Hash
-> Seq Scan on receiver receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_200 msg
-> Hash
-> Seq Scan on receiver_200 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_300 msg
-> Hash
-> Seq Scan on receiver receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_300 msg
-> Hash
-> Seq Scan on receiver_300 receiver
The parent tables don't have any check constraints in the above example and hence will need to join with all the child relations. However, based on usage and feedback among Aster's customers, we believe that it is common practice not to store any data in the parent tables. Therefore, we were thinking of creating an "Empty Check Constraint". This constraint will enforce that a particular table is empty and will prevent the insertion of any rows into it. If the parent tables have the empty check constraint, then the optimizer will be able to further eliminate some of the child joins.
A plan with all optimizations and features suggested could be:
Result
-> Append
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_100 msg
-> Hash
-> Seq Scan on receiver_100 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_200 msg
-> Hash
-> Seq Scan on receiver_200 receiver
-> Hash Join
Hash Cond: (msg.msg_id = receiver.msg_id)
-> Seq Scan on msg_300 msg
-> Hash
-> Seq Scan on receiver_300 receiver
In summary, we are making two suggestions:
1. Extend the optimizer to consider joins between child tables when hierarchies are joined together.
2. Add the "Empty Check Constraint", which would enforce that a particular table is to remain empty.
We've created some basic implementation, just to verify the benefits of these ideas. The initial results seem promising as we observed decreased execution time and for large data set the query execution time could be several times faster than before.
We would greatly appreciate your comments, thoughts or suggestions that you might have regarding these ideas.
Regards,
Nedyalko Borisov and Herodotos Herodotou
Nedyalko Borisov <nedyalko@asterdata.com> writes:
In summary, we are making two suggestions:
1. Extend the optimizer to consider joins between child tables when hierarchies are joined together.
We already handle this for the case where the join is nestloop with
inner index scan, and I'm not convinced that there's any real gain to be
had for other join types.
2. Add the "Empty Check Constraint", which would enforce that a particular table is to remain empty.
The trouble with that is that a constraint that doesn't propagate to its
child tables is a weird beast that I'd just as soon not invent.
We are currently thinking about inventing an explicit notion of
partitioned tables. If we had that, it would be reasonable to have
a special kind of "parent" table for a partitioned set and refuse to
allow any data in that relation. But I'm not excited about contorting
the general constraint mechanism in the way that would be necessary to
express this as a constraint.
regards, tom lane
Tom Lane wrote:
Nedyalko Borisov <nedyalko@asterdata.com> writes:
In summary, we are making two suggestions:
1. Extend the optimizer to consider joins between child tables when hierarchies are joined together.We already handle this for the case where the join is nestloop with
inner index scan, and I'm not convinced that there's any real gain to be
had for other join types.
From OLTP perspective this proposal won't introduce any benefits due to
the fact that queries operate on small parts of the data, so we can add
a flag that will disable/enable the inherited join.
However, the OLAP queries process significant amount of data and to
leverage this fact the DB admins partition the data. We think that the
optimizer should take advantage of this partitioning and consider plans
where the joins are performed on small parts of the data.
For example, typical observed scenario is: optimizer chooses Merge Join
for two partitioned tables like the plan below:
Merge Cond: (table1.id = table2.id)
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table1_part1
-> Seq Scan on table1_part2
-> ....
-> Seq Scan on table1_partN
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table2_part1
-> Seq Scan on table2_part2
-> ....
-> Seq Scan on table2_partM
This plan ignores the fact there are indexes on the table2 partitions
and that the pairwise partitions joins (index nested loop or hash join)
will be faster than scanning all the partitions and sorting them.
To see the effect of the pairwise joins we performed some experiments
with the initial implementation. The experiments consisted of joining
two partitioned tables where each of the tables have around 200 children
and the 2 int columns id and count. We generated data of different sizes
and measured the execution times and here are the results:
0.5 million records -> regular plan 0.69s -> modified plan 0.51
1 million records -> regular plan 2.9s -> modified plan 1
2.5 million records -> regular plan 4.17s -> modified plan 2.28
5 million records -> regular plan 11.25s -> modified plan 4.46
Increasing the data size or adding more columns will increase the
difference between the current plan that the database picks and the
proposed modification of the plans. Thus, we thing that it might be
useful if the optimizer considers plans with inherited joins.
2. Add the "Empty Check Constraint", which would enforce that a particular table is to remain empty.
The trouble with that is that a constraint that doesn't propagate to its
child tables is a weird beast that I'd just as soon not invent.We are currently thinking about inventing an explicit notion of
partitioned tables. If we had that, it would be reasonable to have
a special kind of "parent" table for a partitioned set and refuse to
allow any data in that relation. But I'm not excited about contorting
the general constraint mechanism in the way that would be necessary to
express this as a constraint.
OK, implementing a special "abstract"/"parent" table would make more
sense. In this line of thoughts could you elaborate on the explicit
notion of partitioned tables or give us some references.
Thanks,
Nedyalko Borisov and Herodotos Herodotou
Show quoted text
regards, tom lane
On Mon, Jul 6, 2009 at 10:23 PM, Nedyalko Borisov<nedyalko@asterdata.com> wrote:
For example, typical observed scenario is: optimizer chooses Merge Join for
two partitioned tables like the plan below:
Merge Cond: (table1.id = table2.id)
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table1_part1
-> Seq Scan on table1_part2
-> ....
-> Seq Scan on table1_partN
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table2_part1
-> Seq Scan on table2_part2
-> ....
-> Seq Scan on table2_partMThis plan ignores the fact there are indexes on the table2 partitions and
that the pairwise partitions joins (index nested loop or hash join) will be
faster than scanning all the partitions and sorting them.
To some degree my merge-append patch would mitigate this case. It
would allow the use of indexes on some or all the partitions to avoid
the sorts.
However it would still force all the partitions to be appended on each
side and then merged. If we could match up all the partitions then I
think this plan would be faster with the Append on top and separate
merge joins for each pair of partitions.
Aside from skipping the cpu cost of the merge-append I think it would
win for a few other reasons as well. Each join would be able to come
up with much better statistics which would enable it to pick a better
join when one is available. Even if the planner still picks a merge
join it would be much more likely to finish early and skip the
remainder of a partition on one side or the other.
OK, implementing a special "abstract"/"parent" table would make more sense.
I had in mind to tackle this in a bit of a roundabout way. If we mark
the parent table "read-only" then notice that all tuples (all 0 of
them) in the table are frozen then we can discard that table from the
plans. Since changing the "read-only" attribute would have to be
treated as a DDL operation which would invalidate any cached plans we
can trust that it won't change as long as the plan lives so no new
tuples can be inserted.
The reason I wanted to take such a roundabout route instead of having
an "abstract" or "empty" property is that a wanted to generalize this.
Once we know a table is read-only then there are lots of properties we
could find useful in planning aside from emptiness. We could have
statistics like the minimum and maximum value for a column which the
planner would be able to trust and exclude partitions without having
to explicitly declare constraints on every column.
This is all just my musings, not any kind of consensus. Does it make
sense to others or is it too baroque when a simple "abstract" flag
would do?
This patch extends the query optimizer to consider joins between child tables when hierarchies are joined together.
Short description: when the optimizer considers join paths between two tables with child tables, it only creates join paths over two append paths. In this patch we extend the optimizer to consider joins between the child tables from the two parent relations, based on the child table constraints. The idea is that only child tables with overlapping constraints need to be joined, and not the entire hierarchies with each other. This optimization can provide significant benefits in terms of execution time. A short motivation example as well as the overall algorithm description could be found in the attached presentation.
Herodotos & Nedyalko
________________________________________
From: gsstark@gmail.com [gsstark@gmail.com] On Behalf Of Greg Stark [gsstark@mit.edu]
Sent: Monday, July 06, 2009 3:14 PM
To: Nedyalko Borisov
Cc: Tom Lane; pgsql-hackers@postgresql.org; Herodotos Herodotou; Eric Friedman; John Cieslewicz; Dheeraj Pandey
Subject: Re: Join optimization for inheritance tables
On Mon, Jul 6, 2009 at 10:23 PM, Nedyalko Borisov<nedyalko@asterdata.com> wrote:
For example, typical observed scenario is: optimizer chooses Merge Join for
two partitioned tables like the plan below:
Merge Cond: (table1.id = table2.id)
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table1_part1
-> Seq Scan on table1_part2
-> ....
-> Seq Scan on table1_partN
-> Sort
Sort Key: id
-> Append
-> Seq Scan on table2_part1
-> Seq Scan on table2_part2
-> ....
-> Seq Scan on table2_partMThis plan ignores the fact there are indexes on the table2 partitions and
that the pairwise partitions joins (index nested loop or hash join) will be
faster than scanning all the partitions and sorting them.
To some degree my merge-append patch would mitigate this case. It
would allow the use of indexes on some or all the partitions to avoid
the sorts.
However it would still force all the partitions to be appended on each
side and then merged. If we could match up all the partitions then I
think this plan would be faster with the Append on top and separate
merge joins for each pair of partitions.
Aside from skipping the cpu cost of the merge-append I think it would
win for a few other reasons as well. Each join would be able to come
up with much better statistics which would enable it to pick a better
join when one is available. Even if the planner still picks a merge
join it would be much more likely to finish early and skip the
remainder of a partition on one side or the other.
OK, implementing a special "abstract"/"parent" table would make more sense.
I had in mind to tackle this in a bit of a roundabout way. If we mark
the parent table "read-only" then notice that all tuples (all 0 of
them) in the table are frozen then we can discard that table from the
plans. Since changing the "read-only" attribute would have to be
treated as a DDL operation which would invalidate any cached plans we
can trust that it won't change as long as the plan lives so no new
tuples can be inserted.
The reason I wanted to take such a roundabout route instead of having
an "abstract" or "empty" property is that a wanted to generalize this.
Once we know a table is read-only then there are lots of properties we
could find useful in planning aside from emptiness. We could have
statistics like the minimum and maximum value for a column which the
planner would be able to trust and exclude partitions without having
to explicitly declare constraints on every column.
This is all just my musings, not any kind of consensus. Does it make
sense to others or is it too baroque when a simple "abstract" flag
would do?
Attachments:
join_inheritance_presentation.pdfapplication/pdf; name=join_inheritance_presentation.pdfDownload
%PDF-1.3
%����
5 0 obj
<</Length 6 0 R/Filter /FlateDecode>>
stream
x��SKo�0�@1
�}��������+!qk��Th9t�v���lv7�l+PI}���agj��hC}����=&{��L
���.��%R0�g�&���Vd�{a~������������)���6�~��}7g����js(�I������1��`��W�i
��?���V6%L�O���-�����Y^)i=�$C0�Z����,�j�h�~�q�������7x\�N��N�A��d"����cm���>G�1���&������ $�v<EA����s(����:��������w�N���{�
��[m���J�c���Ra�������%�������cq'���0�8�iUX���K����Ha��sqO*��2�{�+��W(>hr^$�>����y#���g�k���D�W����^�A%kt ��m�A��{V� ���iP�_&@H*)zJ�z=v����h<?P!�1�I��?o
�1��=����e^t����+zH<�1��e�i88�3���R�����U�2#�
f�Z��|Z�8����_�1�|����$T���?�7H�%_endstream
endobj
6 0 obj
553
endobj
16 0 obj
<</Length 17 0 R/Filter /FlateDecode>>
stream
x��XK�5V6�f;�� !H��Ww`�_e����-�J���]���/��������&q`����*W�Wv�s��Z�j����Y�������9o������g�$8�����D^m����������i����������k)�?�/m�?n��~ �������q�����Z��t}��� ����?%�W�y2&����������{=>9k�9k�U�������*��������B{|���}�k��#g��������N����`������88�����d-���~e�M�wo
�����/c���&��U��Q���]����t!M����
�9�
ko�A��������c��W��6�-��%^��PR�r�`f��J���daA��=��~ T��dM:R���������j���BwKF)j+�9��f����������#�pL�����b �� #�]��)�� )9^�4��(���������(a�1aq���9����C��&�l,;�9U�!�&�9#b�Q�QwC�4�H���(��U�����h,<T����aq�������J��TF�yi^%4lI�V���Mtq�:��-_+��&�9�b����rV�HP&+%�Z�U)���'��v{����X���;�DJu��� %����R]�
�j l/��
�����~G��dy-� ���VE��hiC��N�?������e�&�b���Cn����r���c
_#voFc^&�{�.F�z�yca�p�P���r� ���Lk��RR��'G��vL�fmv��(��9���<+[E�!(6�S�3y�iy8����X�����b���J�p�c�s�������u7�3w�Oz/1W5��/8��&����H� 9z� &rtaH�C#��>��#��f+9������)@�Z���4!'��T
����g�N���a����YJNwI��e�/���pjK���YJN�I"��$>� ����<������L�^&D��l�x*K�h�1h�7�����
�[��d��_�����}�l[�NA��,{�e��/5�K����;o��4 ���E��EB�������k��L_>�1G��#�A�k�z��t��Q_��M&�5v3qI+Sq��\�ET\j�%��d� <0�<�Z�uz+R�W���������m�si�K�*�])l^z������o��{�]��YR�#������B~~$9_��*���d���,��9.��z��nm�P�d_^(X\ZA�#�
f�W_�+T��'0�����#~!`Y���m�^����p���|�A�)&���D�����%�?��{�h��}0b�h�{�SAQ�A$%����[�L�wtm���f�
������Y�P���:�A��6^��Ln����O�C�%+[rJ��\ [^e�%�k���)�9���c�)�=��}��@+��y�����y8��u_������D�OVsU�R�$��v�&(kmiNG=�W+�>��p4�R�C�f�
9��cir_a�+"���AMF3MH>/�Lp���7��G�endstream
endobj
17 0 obj
1546
endobj
28 0 obj
<</Length 29 0 R/Filter /FlateDecode>>
stream
x��Y��E���� � <�#����tWwWw���o�M|�N��[�����������u�S�������_U�GsQke����_����B�������)kl���(l�U���y��,��=�~�~x^�^�Z��{�%�����'���w�To�W/���0k���,f�
N]�,`�k�������X����{^v���nD�������{�>[�_�d7��|��M��m�����/��z��~l>Z��6!5G�%kSsm��*jf��������'��z��`����9��#�57��c)���bIJ��nc��{�]9�<���
��veS��Z3������?����]��S�8�T�U)�M��O�<�%� ����a1V�X�����'��QN3����Sd�
L:47�#yK�y�q������&: ��`b�: 4�4��-qO.!�h�m���-A����.��ezV�M�]�N�� ���Z{�1\�K�7�-�oE��'"�S4�y*K�_�yQZ��Q�v��$�,no�!jE�80y ���bCm�/���b�!�b��p�u�K�e�6��=���JMz��������1%��*x��"�ev��@qE�bqH� �9Ql$����A�{`����(�"L�k��UA��2��@�N�
�w�=�y��I����"f�`3���d� �2�7(vTk�i:f�.��;8x��r
��ED�$ �������?qh����%Dh���eS���;EZ���E�9�0��E�C�\��Z��=��R��E�4z9{6h
���� �t����
�������_��7!Z[�5F�=]@s/�������u�.W�}Qv(�8�N!��,���D�Q���~W.�R��7�[����N�Y�VQ�E����*�R%��X��M�w]BQ�W��$��6�}��1�]�.����dO��[u!�%dZD���sW��u�M���d�����u!����@�<Q����o���|
;����)�'p1��c��gZI�Jn��t�WT`�nw�4�T}������]�Jf��=h���x����&�����A�J<P�����-~���7i!�g��r����/��?�
z���^���Y5���Q�+(.8���)��Q� �|e��;e@d�����2������*N����>t�2-iW^�m�*���d�E�m���]F�E��R�.���!�:�[��!�d{1�j.��bYv���U����G��������x�A>��i��J��|8o�|��N����;L�4�7;=$p](��1�f��������Ds�Vh� B��J�j#uVdk��'��#� �z��M�7�Wl,�'Cu~�����`g�j1h�T=���T��l��oT+OA�u�����8�D��e��(G���$�e��Y�L���w�=�s���\^�(�����2�gi7?X:�)��j�����(��S���<��oe�Qw��)U`\<S������ =�c~�����tLT'������!`0z�6�{GC_����Q!JA�����"�~�]=&����Y�[,��5�� X�Kt����z�?J�\��������a�-�$�`Q����Z�F���$i~�*�}5��vG �k���H�%T��P�h��`�����:uJ��J��-wE&!nS�X�O$�����w�V�W��Q���xg0yT��"��CK��.��,��-n������X~9.�m� �WrCR�,�F�O�c����I ��@��y��)����bZ�{��BR��n���������{�k�[��'F��� �z��h����Oendstream
endobj
29 0 obj
1770
endobj
34 0 obj
<</Length 35 0 R/Filter /FlateDecode>>
stream
x��Y[o5--�6jB��
h��J� ��{|� ���H<�<��%E �_���>�m��"T)��>���|s�����T+�G���|�����2��F�z��h�8�Lt}X�mg)�a�W��~������<?%��[gj�����?�g���77@��;��cx�����$�$`�j���o;Pt��G�z�={���Q8�Bk���{�>8�\�nH�md����Ja�2�
�e�������Q��Q�%!��c����`�7�X�@�4WK��B���B�D�M0�������usTb��QJC�������B�9*K���&��$�P��e�#F�
.��.LD`��c�k��
��p�����5�6������*
���
6����=��rXXU���6�a��|��6o�K��RF>������P0����`�Jk�<9Y$zn�@��i/�8�:g�$�x&E���&L��[�����1Fi6$����#g�mIFhn �����t�"�
<�����p%qS�`��,R�)�[��5���R� ���_�:���N1xa���f�Y��������Q^'��Y�$������As��B��3(3d��)+���e�p��?cXl���;�l�XI��{�f$��""��`#�f�;#��>��u{�@R���A�7z��(�H��++�)y
����fo4���Wa��. ���>��
�r�t����v� d�Ee��~����&5n�������2a\�k��z�qE��T�����(���bPT�\�(��t��Qv��9�d��6z�5
���'�����l�i��7�����~t��Rl6������o!�������"�)��i�����+s����dd���'T�r+�(��2y���Y��3O�U!��z��R��A��?�q0{gw�@�J�15RrL�,G3��v���^oh�x�z�I�{��(�s���Q�g�^���0;oq�@�u`�'imt#��-N~;#����5�}}PM)�gQ�gp�-N��B�;����r8G�p��Xo�����������^�����S(J�\B���=>�����g�q�)�������#��82�FTq�@�/Q�t`������1�b��k��d4�,7F#m�O.�sQ���$��+�H���l��O
De��(�a0�y� �V����H�]FrI ��5>��� 1��.�{mg�C�c,]t20^c
�.�g<�l��R�����T42}:~��-������8A��U���2k�y;��_r��������:6�����U�;Y�\�M��
�b^����)�e��!�A����0f�N����!���$��n��@^K��3��+dC����*��:y�������rH���}Syz�+]� ���k��,:@l�O�@�&O�%/z�F3�!o��
3��m���l���[����@�����j��Z*�(&���t��6����N]�s�R.X��������uq!�#���A8�8jF��N�>vUr3Y��O��U�N5�bM� ��A�q�� �h;�oF����KfR4���tu���$K#�'3s��F
�Z�[���+{���
������#�k���0|��Y��UxJ�4�p%S7��|�5��d�
����XL����[Wl���:��`e�$)�8�0�����b��!�qkt9�tcZB����" b�c�~ZZ)�b�u^v�-�)�����o���T(�4D0
dR��4t�4HO������y�IE �M���Y}��Y�03T�V�NB
K�0���xZO�endstream
endobj
35 0 obj
1787
endobj
40 0 obj
<</Length 41 0 R/Filter /FlateDecode>>
stream
x��XKoE��xa���i�#3�m���WBB\��!�dH��l���W=���/N$�\S[]����j�B(�I(����y��� ���\4FYi�������22jq��sV�rF����������?�O7�Z���F���N\��<9i��V~�K��+�auA������E����(����z�3���XP�h�4��q���s���OCk��� �O�c�l*z�d��A;/�������R'e������I�~�P2zC*�oA�G��]���*��.�����
���=�)���u�S������Xz�z�$AZ�j(�%�(
8�P�����C�� ��������Z�@�����E��o����B�(��m��$u*��s��Sk��A�y�f��+���F�������\r����c�Hk�AH��$�>I�� �z��3�l��F��'�mo��9�O-��Y�U4ad�>�a!?b2�V�c��F�d��l��n��U�7
9�Av�"�����������0�t@�P"R��0%m@z �%�,u���q�m?�|.����TH-� ������,O��]4��HZ���O9�U (�vV"�(����cu�6� �epud��^4d�`�z�����UT}q�3������.��=@�E�tB����TA�p��sy_%X��� M d�Z�����T�3��0�n��4��tim�aA��a���a�:��o�#�ZXd�(��,���'��i����YO�N;I)��f�s������%F+^cN�$F?���f�s6� ���`=?OV�����lg�x�2!�����g\2��������n�s��:`�������~�w������Jz��w{��c�������~���e���-����0Cifg�Mnfgc�ZG����[2�<�Y��7^� ��6��u��:�%So+��A����7v@����E��`#|��D�^1&�������7H�8��`S�e�`�t���h��z �b�M�L~5Y�v��&������&*������Z�fj�_����u���up�n�
����������*�\GN��8M��
��b���p���zhR�V��+��6��"�����/j9W7�����u1W�7��k/<��27I�����r�P�K)���,��$�����FnB�Nz�gL ���;��<}vy�d�^��(�I`�Y�K���L��*�HB�Q�N����
� 1o���Y��������.n�<�����9�p�[N&(��0��<��t�[���B�0�0���-:lew0���\�)�;�U�+���*����Y���I�l�\u�m�I� =�!C��8�,��W�V�W��q�v<�B..�uX��X�~k����G{�I��������o����0�<� ��H�*IcC������2���+q��8&�A���C��J�p�|�z�&�<q����V`�Q �R�xu2���=�*�endstream
endobj
41 0 obj
1457
endobj
46 0 obj
<</Length 47 0 R/Filter /FlateDecode>>
stream
x��X[�E�,�� ������8�x��Uu���hL�/KN���
��b��W=��s�����=��S�������V�6����8<�>{���U'�U�������i���]��Qe�\�vg�=�~�~��_T�����+r���c[S��_�V=���� !V���x�Jih�CI�L�������P����<����(�T����p/�����s��T�E���?��fIU����;����q������������v�:��#���3XM��V�:o����K����Y����������dMX�)���N@�\�*0n������dT��e�c��0�\���`����Q�;eB�^P0�Bs���1 7q<�N�a>9�F<�'�jXZ,�O>2� tl�6��El�ng���+/@CV���������9/�����B�n+p�H�|:g9 ��;��q�}��o�����E
�AA0�����������q���X��/[��yg$�)��0�vQa�=2F��m�<"��[qb�xw16���GB�]�m�[qL��cs]\4�i��'��)N�8'�K)U��F����=��dA���H�:���5���B�!\r��ind���Z^>}���i��a����(6�@��N� ������O��m!h���0H���*�>��������Y�g@W�*��>�_p��;^�\��o'c�����`M�v�������A�}�w?JKY'�Zd@A�NO`prz
k�|�"-N�!�����$j��Lr��wgmb��P$���q���##K�U��R�N�������0)wP>�+��n�H^��>"*`w kZ��7��O�� ��r���i�MtR�~���:���PO����������z i%�t���g�H�CP�����z�h}���B^n-�v<��3A.9*����Z�}��pJH-�O�k�.��n��?���S#x�IKM
M�)�M��k�3�d��%dC��V|r���q�q�R�3[<���p�����jy�h�%�m���q��������Z�9Z���^���cy���������
;���� �%�WP<����
���x��H2�&�������s��~���c�/��Wu��kY7$cC����@?!���jN�R�!���Qg��<Y�
lB<����.M7V}f�dF1��2h���s2B�H�w�wa�L��|&c��)h��]�5�&c��-m_���M���F���t�`
���\"`cP��"%)��.lP�)�����c�R2U�:);��1i����3g1Uq����+hu��E_X}/Y�0�����!p�h�1��:P�s�5�h/v�Q�7��e�����1�A��m�Fi���e�'�� 3�:I9����`�\��F���"�����+.���#=��I:���[y!�&�-�Eg�a2�{���)����V����L��$�4���� ���UM"jwz_�S 9z�����%`�
|V���;�g@��&jN>-CH_}6�>S�4��H���>���jB���S��H�%�^��[����4�6��`QQ�"c�����1eF�}MA��qk0�\���� o S�Q�[R�X����U@y8R��pX�m����P�X������;���������{Uv��`�V�� ��U*F��J�
�"������ %�F����Z�S`+�+��r)^�\�&]nCgP�Q]�u�z�f?-�T�b�(/{6��T
�Gl7��#A#29F���c�����������4��IE &��w�^}��&K���E�*�H� A�%�ZW�(����endstream
endobj
47 0 obj
1839
endobj
52 0 obj
<</Length 53 0 R/Filter /FlateDecode>>
stream
x��X[o\5is;��B�(H�ST�sR�xl�/���xi�
O���(��K|�s���������xgg��?�=3���"Sk��������~�OuYY��%[�/F����H�ye����������'���j�\����\J����s}�G���z�� DY�� ]b�^k��c8;X��q�w)��Xoa��_���&.����e����E��R��5��!������"O�b��'�}���^4_��(ig���v�� ��kv��&��i�
&Y�����w:Ps$�����P����������+��O��-oeE����>�>BS�RPl�o�f�Mq0f��c��lX1�ZoU�������K0��T�7c0�����*��Iik�@#6���z�G�1��^��)�N{@�Zq�}Gf?>z���@����� v��.[�JUa0pH^����@�y�����*���S���]��oFQ��7:���nG�yl�.J�n��9�J������a����1(��&�0Kb���sc����i"��G��,��d�J�-�3X�~8����c9k�g2�G'��t�;��N�F��P���^Y�!VJ����=�<j��U2`\�1���5.8�X*����q��b���]�Z�Q6���jy��9m�����$�a8�[@���-����?�vP�i_L|�zb�h��u�G���b�fC�P=j��X��k�f�
� ;i���i�E��lxC\���2�-Ho_&��!6�������!m��9I%�J�ad\�8*���3�f7������ls��.n� �������7
w��|>i|�N1�g#ww��!,�F? �����vL���l�����S���� ��B��TH���*�CR�mB��������af���)CL(M2�^��5�+amH�7 ��������a���D
�����w�D�i�G����f�2�Ja��(�IW��L+aRd��p�>���W�u��� ��\�,�q��".���-��b�{�>�v��~���0_���'i7�
��)����dE�b�RN�h
�L�#~6��
5���q\N��t"�����i��P�0���hv�s����iV\�(��{�����?m���q�A�'��24�?�����x�N[Q;�����&o*�Q"y0Ga5����]���u��u�irG�����p���u���1RJ\p^����'�k��k$���YFF�8;�`�\B�����9�b./��VD3��L��=�
R�Z���K��������7A�!w���k�~��5��aq�������1M&$�i��/p����������X�F�J���Z���c�����I���<?` y3��N�j��� 0���X�)���v��7"��m%'Z{���)�'5@�� �/��|/�J[����pc�h���8����f���/Xi�K�K���y$���u/WK�c�Q�D���W������(��b��U�^�bc:"������J��y�)p��� ag����(K�;�Ba����:� )�\arO|��yU�d�X�UZ��i+��3@&��q�����Np9n�#F�mN��%����i��1��o�"IA�����'4��&
;�����C^z��$��BFV�����=i>�Px*6�72�{���/8� �<�T��<hb���2�rqE��6��endstream
endobj
53 0 obj
1694
endobj
58 0 obj
<</Length 59 0 R/Filter /FlateDecode>>
stream
x��Y[o5�BJ�)"U)�B����u};��"�%�J<4<Z�v�6������3�%$[ D���9s��������KU�������W����TZ�������c����zU)"�g9��������~S�:�^���kL����R}�k���:�;�(,�.HXl���u��������u����DX��9���}����\������\��,�6Vu<�s��U%��H[y�� k%w�l�\W/�i$7Jb�,7�y���H{���CHX��f�
Rj��K������H+k({ �5iv�d�'v�,����D�P�����NK8�.���S��-��^�P}��R�E���|j�y~��&�kb@u���*�%E� ;( <�� ��?Pu�q�#^�����
T�L�����Hf�����!��]�<w��z�c�<{���[�E�$����c���T ���fhe
���'��'M��M�
���<��������eO� 7�%�iI�)�4Y�>����>B5�cYF�.2��"F�L���{7�cv���;<o�~~ ����v��(v�FW*U"@m9x��2����^?��mK���|N��"�r��6*��kS)m iP&p%�0�����N�Nj��7��6�P�4���bm"��[�[0[J��DC�j����f�Kc���'9���;\��F#J�)'[�'�������|>�Y�g�P��j��<��Z���b��PZ�/.;LQ0�
���"�\1ZI�E��j���hS8F������x�t������k!�M�� OY�;4���n�s��7���T%9*��`���=��#[|F�i!�g��Up�e5��vq�N�v�G!�G�|Y�9�9��y�8c���K����8����n��##�]N���)���o����<^��lK�����A��|�zvtw����a�G��l�� �ggxy�O��Yq��>���a���r��}��������e.�q�WN�f{�����O���dQ��>��}��o��9�>m��A�{�����7@�����n)��$��5R��R������w6����� a��W��������7*l������J�,:$�� �Y����0foyy���!^�m�����F:i����b8 ���fA\' ����*^IYD� �l ��!�E%/�D1�*�V�C ��s�����h)��q�:ATP�a��J-�}�-�
Q��p��D�p���dd�@��+D�@�`Jp��������9D����!�������W�� 9������ :�r�JvQ�MZ�p�dg�4A��|��V�����hpY�Q�?(�� ��e�������H�3�FK��6Y �s�u�+����C����.$D�>��Hw��$�E5!gly��V��-endstream
endobj
59 0 obj
1392
endobj
64 0 obj
<</Length 65 0 R/Filter /FlateDecode>>
stream
x��X]o5mJ�m��& X*$vwk{<c[B!o�"�@�h����3�/��&$myk�C��3����gOj�YW����m��i�_�S�Td|G����v�����+���U��{\�Q��������^�<5��)uB5'�������G��7��F��t��1�n��<���������bc���
�5l�������*v�����h[���5t�C�_Tf��T���b�`Y��m�k�[�yG�n7��!DO�-G!gRs]��F�Z
����H��������������Y�Dnn�K���7��8�]�����<{����C]����q�!v]n�&��s�g���*�}5
���4��
l�(r�v������� !�t%�\��T;�R��XN k ��S����?�&'�@S��Yr9o-X��S0�� ,[Ho��C���8r����S��$t�U�%"�f��ZNy^�sJ�}bu}�).��&6�F��Z�0�� p.a]�*���� ����M�:P1 o��$1B��K�n�(��t<��v���#��Q-����+�]��>�������x���� \�p��zZ��4[��}2�|��E������r��7��8�R�i%����<�%#~�*&���=q�9b ���jI����������qc15�Ls�������w�p������J�8AP�l�|������9� z,���Oqb9{!�����L�qE����S��:Wbri��E��Q���-{�����I�(�_��!���$$�K*j��d��UK���r�Z�kmr�O�}��#Ev�(��H{ ���w��R2Z]�9�EQ��%�;�2�!���gN3���e��Z���N��Q���zU�H�{I �'
��X���-�j=I�O��E����x=av�-;�������-n7��;��%�"y��70]�����r�p��>�������k��l�����c���8���`O�uI&���>��N�l�s)�G�Rr|��w�z\E,�41�#����ZJ��$�+$>x��i��y����#�v<�2yd���S^<�#�����kON��ja |�dQj.yO~������
h]��9������a�y��k=p�nE��^���'{����k.� �c?�7vn�}�(�����g|fb�Gvg�E�O9��5.�����_���������D�_ybH1����"��:��d_'p����5�Zl&�����$�kP�\ �+E�i��Nn�sl��� ��&���U�Z���1�mB��5�6��~����`�]�UE���Ef�:$ K���WV� q|k��K���!\���UjB��Wfd���c kL@Z�j���������s�2'����3��g���W�� �1+���<C��FT�$�yV��<��5���'�r��<����k��m�9I����L��`R�i88+�sn�7[t�Nw�P�$���Q ��
"#'�����O�C����Q�?�
� �kCJEJ����endstream
endobj
65 0 obj
1509
endobj
70 0 obj
<</Length 71 0 R/Filter /FlateDecode>>
stream
x��X�k$E�\4��\��� �������xE_r,�`|�����l���_��N�~d�%9h�!55U]��uuu�,�V�
���p1�^����_��r�+g�X�����S��Ye����Y������N����]�����Up�2�����zuZ�� ����
�6�R;@��S��)&�o�dX7�9���}aaQ%����},_��7S���Qe�QL_UnM*E�`T4�t^�,��F�@)����*gu����Q.���v*[���0�]���w���F>�E���O e���{R�r�e�������a����8������ u�X��$����/��h=y8-xt�L������&��N�]YX���*[�B>��y�]���*$Cm���q�D��I-�>��A����~$=`~3h%y���]��n� J�k��j�� u�T�������%Le�kC���F�Vc6�#���{C��!Dp�f�sN�0}�xU���������"X��>i��d�0n<�$_���>�ur\��kT�<����q�G���������Q�������^�_��� �'u�x&)��\�l<�5���1sa?V���A�II��!�����F[I("�V�k�7&���6�Ee�G /���,a3(�hYS�6M���~��7m'N[46�j���M0!�?:��8;'�S5B��)��gR!v]��/�����;��Q�)�-�;8;��pv���9��s ����� k����sV���,��[l��K�c4����|
�������L������5�]���}�`�e�,�8����f�M��H���<DY>�k����qe`d���
g\2�S���]l4���F�*�j������{��������������/4�;���(�T�Q���1������}�[I�y�����1�5e������S�������\�_ER�)�����6��1���<�m����`��1#:{�p1Q}=�8`�������|^�����(��]�8��������!�qg����1%:+?�������`HE���>f�dPg\0B����
��\��G�o NQ�����UM0W8ETB��83����6���^�~�Z� �+�FK=X�aw M�cp#�G<�5�g�9L�2
}R��il�W�6�7����)H�:)��m��X���;�<mE�]���������*r�O4��g��h��3�����������"D�C����S�^���C�4������!���]H�
k���[b����f��Y���endstream
endobj
71 0 obj
1279
endobj
76 0 obj
<</Length 77 0 R/Filter /FlateDecode>>
stream
x��X[oEi+���!��������f��( $�K�#���)��pJ����6>'�����C����������t��F~&�����I�_�U�Wd|G�������P�m��\�[�L������������s���^���Hu`���������a��t���1VW��^�����E���\����gN����XP8�rG���]��g�������qH�^����zS9v!@6�.���Y��y���������L�"e����t�17�A er��*��bss�&�������}slM��v�H�e���o�s�[�����Gr���=5��"yh+6���7J;�����~����a
������xQ������;�r�����`�s��O�U@:����D�B�V��9�O!k(�o��mJ���G/� ����B�b�`���yJ�(H�q�j���B������uq�����C!�g���D���O.�����:}�|�N�P1�c������C����P+(Lk����i�D�zT����h�"��"��4(�����6�$'I9������������Y��y.��!k[�@���&-"( c#�s�6�A��$�[�2��)�j�h����P8�C<j��5
����X~�w9;fZ��x�@�p=(���A���.C���!����G�<����;n*�����Cz�;c�����X��_�Fg3�gP�8��X���X}�K;#2�#����#����z�3'%x�Y�L����L@L�:�3�����H���w�����j�����4�\�'+���3����i���,q�S�|�����]|��l�p��G+3";��^Bq#%�?����_n��gI�����?q�RV���g�Z�����w���5��Ufy({S�]�;�����j�7���u��g� I&@�W� ����$���|������%��'��s;�.g���K���� �AAHG�=�gi5G,�Xt\%�:������"W�� B��{�$�����oN�i�����+5�s5�g�;/6 �'��1e ]z8{�@'�OLiv�
��3��������S�?��C
G$W�3x�9�'�6�C�WO<��o�g���:���L���<�n�����D������ �X�L��,��o-Yew4���O.��������3%0�1:k�$����s��=���F��ic<x[<�
�+`S�����.�w���K�m�z �M����I���g��������~|��M�([����d��)�,�I�9;<�QQ�_���q�gS��G�b�IiR����q1�0��I��J���Q �R
r���'��V��
endstream
endobj
77 0 obj
1332
endobj
82 0 obj
<</Length 83 0 R/Filter /FlateDecode>>
stream
x��}y<Um��1eB��B�3)�!���S��R��$��$D�D2�n�22��1I%C�<�{*�w�s������|>����h�����{�u]�w]{]��!d�(�������>v���(��E#���������, sfCa���J����v�m���
�?v�/z1"Q��a���X�1;6{)6��{���g�Q 1�@O�A��2p?�����NA`$7���A�e���~��Q6�,����+�m]`*`k@+^����a�l���Q�,��C���X����TBQR!�A PD�#x��� ��$R������D��QD4�(�*)����X��O)/p+����%��+�A~�"��+� �H��? ����\�@�eQF����%c��_��T���YC�H�K���j��+U0�P�'�E!d�D���&�������~�bu]O������=��e(�{��������~�@�@��B���}�"����K� 8 O�V�6��x�x�t�e��
X����x���J�A���d �X4j��w����@# ��7��2�R$����<�c�?�[)_~:��S@Dc�0[V��$�(�'�H�����_�X������}@�#P+�T�x<q�
5,@��0������xt����� ���0"pF �E� v��&H<�;�w�a�Ga�XQF/0�P �v#����`b�H" �������1 �X4M��($%� x�;�,������g ��[�D06�G��$������`;`�D�P+��#� �a��qKj�k�Jc��{��F� ` c��>�'���(O [�p8�4� �@O�TL��q�,4
����`)��H� z�KWZ <