Use generation memory context for tuplestore.c

Started by David Rowleyover 1 year ago16 messages
#1David Rowley
dgrowleyml@gmail.com
4 attachment(s)

(40af10b57 did this for tuplesort.c, this is the same, but for tuplestore.c)

I was looking at the tuplestore.c code a few days ago and noticed that
it allocates tuples in the memory context that tuplestore_begin_heap()
is called in, which for nodeMaterial.c, is ExecutorState.

I didn't think this was great because:
1. Allocating many chunks in ExecutorState can bloat the context with
many blocks worth of free'd chunks, stored on freelists that might
never be reused for anything.
2. To clean up the memory, pfree must be meticulously called on each
allocated tuple
3. ExecutorState is an aset.c context which isn't the most efficient
allocator for this purpose.

I've attached 2 patches:

0001: Adds memory tracking to Materialize nodes, which looks like:

-> Materialize (actual time=0.033..9.157 rows=10000 loops=2)
Storage: Memory Maximum Storage: 10441kB

0002: Creates a Generation MemoryContext for storing tuples in tuplestore.

Using generation has the following advantages:

1. It does not round allocations up to the next power of 2. Using
generation will save an average of 25% memory for tuplestores or allow
an average of 25% more tuples before going to disk.
2. Allocation patterns in tuplestore.c are FIFO, which is exactly what
generation was designed to handle best.
3. Generation is faster to palloc/pfree than aset. (See [1]/messages/by-id/CAApHDvqUWhOMkUjYXzq95idAwpiPdJLCxxRbf8kV6PYcW5y=Cg@mail.gmail.com. Compare
the 4-bit times between aset_palloc_pfree.png and
generation_palloc_pfree.png)
4. tuplestore_clear() and tuplestore_end() can reset or delete the
tuple context instead of pfreeing every tuple one by one.
5. Higher likelihood of neighbouring tuples being stored consecutively
in memory, resulting in better CPU memory prefetching.
6. Generation has a page-level freelist, so is able to reuse pages
instead of freeing and mallocing another if tuplestore_trim() is used
to continually remove no longer needed tuples. aset.c can only
efficiently do this if the tuples are all in the same size class.

The attached bench.sh.txt tests the performance of this change and
result_chart.png shows the results I got when running on an AMD 3990x
master @ 8f0a97dff vs patched.
The script runs benchmarks for various tuple counts stored in the
tuplestore -- 1 to 8192 in power-2 increments.

The script does output the memory consumed by the tuplestore for each
query. Here are the results for the 8192 tuple test:

master @ 8f0a97dff
Storage: Memory Maximum Storage: 16577kB

patched:
Storage: Memory Maximum Storage: 8577kB

Which is roughly half, but I did pad the tuple to just over 1024
bytes, so the alloc set allocations would have rounded up to 2048
bytes.

Some things I've *not* done:

1. Gone over other executor nodes which use tuplestore to add the same
additional EXPLAIN output. CTE Scan, Recursive Union, Window Agg
could get similar treatment.
2. Given much consideration for the block sizes to use for
GenerationContextCreate(). (Maybe using ALLOCSET_SMALL_INITSIZE for
the start size is a good idea.)
3. A great deal of testing.

I'll park this here until we branch for v18.

David

[1]: /messages/by-id/CAApHDvqUWhOMkUjYXzq95idAwpiPdJLCxxRbf8kV6PYcW5y=Cg@mail.gmail.com

Attachments:

bench.sh.txttext/plain; charset=US-ASCII; name=bench.sh.txtDownload
result_chart.pngimage/png; name=result_chart.pngDownload
�PNG


IHDR|4T���sRGB���gAMA���a	pHYs�����e��IDATx^���\e�8��IH�_�AZ�K�"�@P��Oi�� V@@�'�(R�"�"R)�(�HW���*H'$����y�	�ew���&;���~���sg�����3s�=��0�]@��V��:%�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s
��U��.���1�x�������������~;&L�P����[,�����������k��F�����G}������n(�K,�D|��_��_��ffy,���?���z���n��b��!e�z��G���/.��{���>8V\q�r���K.��z�L���J����,[kV�L�81~��_���?_n��i�}�)�,���,�����������D�?���8������O��o�=^{���������;�����e�]���w��K/���GW��+������_�����y�d�����<���m+�'�������5	���#G����/�|F�B[dB�����Gq�m���t
���j�u�Y����6F�U�]_^H��_�:�9��x��W*s���w��f��n����2eJ��Y�������[�=/��be�{���-��"<��6lXw�q��o~3v�m�Xy��K�nU�#�/�K���i��U�2����W_}u�����9P?�;�O<Q�|�3���Kq�������+s��>tI/��B��W����n�%��������>SR����6�Y�.0j?�6�p��}���{���9�m�M�^t�>��7�q������.�`Fw����_����e�����
�������L��UVY%���o�k��j�'���/8���e�]�G���Q�x�i`~"�@�s�]w�
����m�����^�2g�b�M6�O~��e:e�n7�xc�����]�;������*���g��w�>}�T��]&z��f�Xk��*s"F����?*�`�`�����/�������O|���OzF���h���K/�zhI&���~�y�������t.{����+�Xn�$+����xz��Wc��qe�B-������[�T'-��"e~K�~�����o�����^f�e���{�y����|�����������Z��_�b,������� ���zk�^j����C��[��n��>�[�t�����ej�`������o���~z�����o4�l�����)���m�6����3���8p`��.��;j��Gm[H�m�]2�LW5�^r[O�2�tw����-o�{����j�5��fW�~���466�m�m,�Y�Cv���}(6�`����?��c����|���
d�}���k����K��-i�q�c��w��\>����"e����]Zf��sX{��Y�����=�XiS�N-��6����[��g�]fS�����t}�y����f���{[�M�����{J{��|��2����m!�a�^�������������;��G}������<.�_�f�Yk����,�7�k>��b�-��u�Y�����Z�U������v�}����|)�W>�FmT�[[�Y��_|��������B^\����A��|�l�����6����Z��{���J|��g�:�v�����UW]���\���ms��#�H9n�31�Ws���������-r��������{���9n�E]T�����{��k��~�-�Zj��=�-���I�&����	��3���R�������T�����>kj��y���^yL�v�m�s����}���|��n��v�:��Rg����t?�]�i����_��1bD���g�:th��D�������5jT��?����\���@�8N�#7I�c5��7�(?�S.����I���q�?��=��x����T����;��2i�����
-�(��B�������A�L��c�����A��1���}�d�y�u��gBcVr,��
o��1�v�r���s�=�>�l�V��n���d`c��7�@��v��1�� ���a5HY5y��x��W����/����[���}��_��l���U��r����,mr��Wo�=t��m����2A�m�V����:����s}����\>�WN2���9������TSd�u��KA��V�!�O�nn�����~�mZ���9�r����e������][����f�L���m4�MM�{��cn�j0�v_�t�D�@i�����|��\z��q��W�n23�Y����r[�1��O��A<g%��-��R����o���?�q��l��}Z�m���c\v�e%��I���v�`c����`l������as���o�gAn���)_���������������o�=~��_�SO=U_]��?�G��\���{�Wm`V��1Y��;��5�\S^'o�>_����y��m���	���7�[^���/��V�|��u����)���M�b����mS����\�<�^xa>��C���m0������K/�T�MK���>��G?Zw�����0�Y��<��s�-�u����,[����J�{�d@�{�c(/<�M�t�~���r]��5�^��!����Y%1��k��|�������S�������s7��-i������M�{�k���r�k�[>�N��L8��\���t�w�|\G���^��
�.#
���*QY�?�3�Q�?��G���?6�J�����32���y�e������5�����9y�o^Y�WMV���GKr[�U�)�p��r�^u�U����#�9�m���?��Fg2���>�`C����n����-�l���~U�-�����4�YK�ve4�y�wk2������l��������v2`^�jI.��+u����fg�}v	��e�eP��s�)���d{�v���-�����gp�9p��_X[��Uy|eb��C9�g��}3>������A^���|�|��<_�����7�<�:�
��yyL�{�6��������[���9����w�,�OU~&f��o�[��aV2����mY�|�|�����Y��m&�[�L���{T&�j����Q��Y��o�>��uk����~H�\y��E,���\.��ym���2���c7U�;�5m}��t�y�*�Py|g"iV��|������T>Gg|W���2�3]��ed`!���&!���}��w���Ld�+��?�{�Yu�����Br���t��E�����|��K�%����g�}��y�n���e��w����y�um7^)�OV�d7x�
F��B%^������Z[��\�+��2����r����%�s?������U�Ln����+g��~�r�f���7��k��)���=t���w�a�R���&�[��"��������V��������-��K�l'���-�5�����?^t�2 �m�Z���
`s���|��i��^y�n���)�7�S&&r:�9FW5��WLg[������l_M�m[����f�L[�{��?��rEsZr�%K��n��W���v��z�r�7��,��6P��n�m�-��\�����@^�#��<����l�_5��WeW��������~2���/|a������a^Q^����(�U������������
�����r�V�������m3��� �+�yn�����Vn�l�M�z�&?�m7��\��F������.W5��@[u�c2�#�B5!�����|�����/���y��v����������Y��-�:�6�u�uh�8h�|���
����5��vs�+�w^T��)�q���:�1���V�}V��%�<�u������%+��#/���w�w�����L�$�������!tP|��.�u�~h���y��*�<��q��7�?���MF�����>�����g��</�9��Y�g�4�������;��[U�}�ZW�}^��^U+�O����>��"�W&��9�����1�:��Rg��������� {��m�E�@����A5p��j����t��������q�%H�?��n��Q�<����h��$m������n3
�C7�*�+|��x50��zVW�g���
���w5�Q[2��9��r;����3�3��A����vX	�V:��v�u�L�������ss�v�\��^���W������1��*�7�K�2`R����
���A�Le"�vr�eP)�Y���:��y_�
�cKT�o�-����yj�q��]vU0�
�g����������3�����V�v��Z5����d[��������m��/�en��)��u�]7���*��^�r�L�f�i�9����X=���4������dO��<v2�\
�W�s�]v)���@H�>3y�Z�H�v��fw=�~x���m��{n��|�+����v���^)�/�6��v����f��@~���.�����nsb^��jy��6�	��y9�6�n��n+30��Z��U����y�c��\�T{�_u~>6��s"���&r���&��T���5�����|�33�������>��o-���Hn�M7�������������PM�6'�/���}39P5��C��� �y���g��Y�������6���<F����d���|�l����w&�sn�������nY�5�:���T.���<��<Zm������MJ�t�w�w��:/@=��������?�:B�0�}��4�3���!Z
�e�2�hI�k^�[
8dP +lZ���������[�@N���Z7��^������+���'>��f�gP'�����!���0j�sd���}Y��jn������v�i��\�lG������jP��d5Gmp�V�2HS+N�[������mgP�+�mSY=���e��2 ��g`7���&�s��5�yL�v^��s��j�5�j1)�iV���)�7��@]sr�d��v�f������A�����^3����b ��j@<���`eu�Z������A�����fU&�j�,���o�S��T�&j����������nsjn�M�V�3)Pm������`u�|l�sh�N��-�N2���:VeUF~Ff������E��������*���!��x)Y�S�����;M�zf%C57��3�����hU�k�jk�������<w����sW�n^�QM.g�j�3:�oV�|?�H�M|4����[[��\b�=�;sz^nN.��-����S;�M�����;��Rg����I��e�����@a�rg�Ack�Z� JK�Z,��A�����������95
�d ��U�U�}��t5������]E��K�Te��6h�	�����[
���;Z�gvG�����:�2.k����������.K��zmM�<mMv}���~7�>��ff����2��W��\��dn����oz�y�Wv3T��~����d:�W&�s�lo��nv�Y
��L�������!�U9nH���%�ph-�������y���2�n�L��6hM��L�f���:�
��yqL�������9'�o[�S.[{�od����y�Ck	�<^������������Z�����Rm���SoI���V����4��T&�fu,�W��|�4�j�<��>�a&tZ2/�CSY5�ZW�)?k���>�3y����N�~��4+y.�����;'{t�y�9y��U2�61���iR���+���2�	����:�-��^k���	������l��WQW�I�X�>�[�����U�����\�H��@B�s&S��6�]���+��d �6@�������J���;Z s{�&���V:C���U�-�}�\����n*O�����+���$k��.�M�W�2�Z�����+�����Zm>�z���l�9^H[�z^M���|�p�j�L��L�T����m��sPm�<���>-U���vV=�������@������tV	��lsj^�������F�?���-i{��U��5�z�&�rl��%��j-����deLU~�T����>�MxeB��I[?��#_�:Oj���w����G���M���G>��Y���?��<�}F�w��:����+]��*����~s�
:���T�M�gs�~�j���+u�y���]F��ruL���?�k�/V��L�������K�U�m���kXM�8o�����4
����M��L96Du~>w[���R����h��M��������l������RmWA��*��������J��'�����g9�FUV_��3a����_��c�9f��r=j��2T
:g���n�f%���=��	�f�69�4[+����<�v�=^�z��g������TW?&3���"�O&
�&yje�*�9���l�Y�����4���o��g�Y�����*�#��������Xs�^��<fk�6fUY9�J����,�f�&<�x��f/J�`{&nR>&�)M/�����L.���R.W[�3���y�f�^&��;���������rs:���Y��:���L��.#~M�x��?�^����4��yN��j�����!^{%r���%�U��s������P�[����'�%���g]M&;r����*2���3����,��z����������<n;�*$�����y�;�Z���|��We���1���d�g��8vr}k�G{������#����
�d~�������?���q���~��6lX�J�m�Pm9���U9�~����������^��rJ�����o�q�I�����#d���`�*���v���%�xm*+��r�[��l^����S
����Zb9�y(�����%�\R��l�Y����$n�������������Y��:���L��.#��^)������yd����
���9vJ�__�2&���.Yj�k���I���.���su������������R�a�ye���__�>2(Z�4�hy^�`l���M��:2��������������m`n��u&���e�'��9���O>Y�qm{l���a��w�}����o���:9��s����~���N���J�dDm'/���2�^;�OV��p��CK���Yg�U�;��~I�d�2�������|^�,���:�����]F
�Yf����~����������Zd�aV�v��"�+_�J��sv�r\���W��H��i�M3�R��2���/4�+�_�O&�3 ���<�T��4A���k��������^����+�;[�k��s�{����iWU�3�@���p����j�
��"��Fk��v�N����f��jIvs����:*�=���~��c���k1����]Ne���l��v�gm���7��l�����
V�qv�V�Y&:�����G�i���4]a?���m-�AYm�]�����-&��B����6��/�C�v��r[u�w��q^�z$�@��?�2�S
d"<��_��]hd� U9�C&1Z�c(tDw,����+]�]�y�����g�-�x�M��.������>�yp�5�����;N8���x�o���q���Zy^���[*��{lV�U5��fN�����:��]M��ulOC�����L��n��\Y���?��
���(#������*�����K|��(����O.�c���J����*�8��'?Y��������!C����j�YMt�u��{�U�qX��Uh�!/����S��������'���=)����^Ukn�������J��.T{�l�\�DTv�V=w�zg�<;_��J�t?���X\�zhy��:���#������+���2�	���>�v ��~�T��&��s�9�����������
�j<�|��$�fU������ui:V��T�������:����������u����!
�D����_*?2^��W^q_M~d"�6(������������s2��A��%��\<���i�<?����F�O��Q[m����3"��s�mO�G���<�H�V����GY��6�l��H�mP�Hsz1H���s0�98�����8p`�����[e�9��7m��"��Y�S�����������OUV��v�������aKdM�y������V:����o�}F�(|�]]5q��e��Sm���=��Y���rg���J���]��]J�@�O5��?`s���q����/�����W����,?�3�S��qk���S4���������#��+�L�t�`������dNvI2z��r�n����z�60����������5�\g�yf�`hnP�ZyexV6�����9��uV
J�1�]$Ue��������3�������������������2���|3m]�<��kW�:�����uj��������)�mIG��z�I�j�H��m��v�s������wV_t�Eq�I'�y��7��X~�e7c���l��~gG&?�^z���(R��96O5��m-�G�eo)����j�n���M��\����)�|���i�w�|������Tm�zK�\X��9������Y��:���N��.g�
7,���1��_���+���{m�'�^~��q�i�����?~����C������f#���M����������j^��
+�P��^����G�~��y��1l��rf;�
�5�XcF '�o��}�g�"��m�
U����/][&V3����Ljg�C5��V��FSv�U��-�a&�3H;+$���~T�������������=�y5uk���s�=3��<^�A�L��^������M����~�_���������`m@7����9y�����V�/��6Poj+�s�����d�8	���v��;Awg�Jdv�H��������	������W�r����{��^�$��tdUH{��U�NVM��v����VZ��*�y��s����2)��c�U�9_���ix&�f������v�E!}^�,��]����P�$|�r���=��s� ^v������t��4����� ��H��S���jw�c0����-�ncj����:Z
�dr�������|�-��r�lo��fk?H3�p�
7���+0s=j�[G�
��������2[��Jgh4�7]}���e�v�<������L2�^��=�])���V�y�w��]���lW^ye���%�	�L"dqU�P�sh��I������D|���n��$h�����U� ��**_3�-=_��������Ll��Vs-��	��qJ2�������|z�]wU�4�3�@�i:���>�j�#���_<�+�3�R=7�E!9���o��������������Y�Q���g�H�>s2)�m<y�e�m~6t��/���������p�&]���^U��9sc?�G���&�k�w��sf�{~�����W{;�Gk���N���w�qGeN������rg�����J�q^�z'�@��?��?����*!���o����~�9����d` ��|s��L\d!�%r��+%38��_��\MX���?��*��O?�$���fuUg^����[�X.�f0!��2`U}�|yU�%�\R�g�j)�����tuiGi�������Y)�A����S��+�3���6�mKA���+�_��<>�����e��`o���*��v2���������]U�NB7�d�m/�s����3%�3Q��yEu����W�;����8��3f��2����m*�y���s`�k�7�9�}���7�8#�����if�_y��+���<'T���3�	�.�`��7�]w�2V����1;�����e�]V�r]����s�s��tF�7�j�z��v����=2���h�	����U�H�myd�@�*����<�L�}��%�T�	��*jT������K�2��T�)�p;���L�-�����\^����6�[��'?�)���*�������s����}�_��\������0'2����|��>�dB��~�����PU�����jZY�����L�T�/�}���B%+�o���������&��k��w��f����>/w������e�w
�~��|I�c����K�
��W&�>��O�G?�������C�-?3q�UEy�`&,2t���t�vU���+�3���������O|�tEW��?��L�k�\�,��2��c�8���A4S�z���s	�6���s��\�Z3e�+��LT������n]��L�Lhe��@�o��Z��j��3�����:c��G[������d�A����?�������=.��[�������K������}\�LK�m[����i�������� \[duK&�����������_�� i�<Op�3��P+����20�V�=g����6�=+�~s[���n3U!U�e�6���#�Q^=��?��M���28\��jn����
�d�����/��������1���va���g"������������<����}��W\qE���v�i��b�-*����+r��dP[�E(���^x1;��#�>���[+����%y���u�~h�����������������\a��[�-�\����X]-?Y]�����b&�=����r:�����;���Ug}W���2�3>ti�������o����N���+����8���yumi�W������Y���v!j��lM�@�}��c�=���j���r���g�S���%f%�K^A[+���/�|�V����?>S�AU��7�|�r��t��K���������S��������@�_��WK�����)��e;���=)�<��r�uK��ZY�q�!����P��e���5y��q��^{5���l��2�� ��� qVx���:�9���6P/r�3q������l3y���j�����]��>����T�P��������l��:���Fj+�jU���{�W���6wK����C&*;��vN����|�����-��3������]w��T�����2������=)����g��������o|�e�V?�����=������DS������>/w����������P������4tI�C.���DA&d��Z���	���|��o��%��We�@,�DF��B�z�a�����4M"�ke_��`b^=����A��\>���5�)���}�������������?��1���U�y&_2����|�\������N��[
B�J������=s[��s�J&����y5}����M����>���A����i0�-������K��kf{j�����8�[KA��������0��%���13���UsA�����W�V�(Z��U���Y��m���}\�LK�m[����i���6�m���}�W���vv�e�r����Nk����@Y
�9����4��c�X	\V�{�����x�|�F�}U�7��4hPi����eZ��,��n�a	��z6}�<�g�=����n���e�6���#�Sn���D�+�s}��(��h��b���.��]XU���n��U���n�f�* �s��j�D���gCvW���<������a���l'M?��Mg��DM�}��q����wM��Z�|>W>Gv�V[���,�C��{~?����!�r]�q�*�<Fr�g�+���F-��������8�{^<�rd]�=����C[5=��������w�<~s��l;�D�}��qV��\�M7���Su��90���5�/�l��l�O�K��1���Y���C�yS>W��FG���{|��|����Y��:���J�n,�e�����?��v�� ��^xa	@e�*�����>T���dr��vv�P�f]��������|���,W���|�=�{��'f\���
+|`P\�6	(Y��]u����'���v��]�dw*�?�C�`9��
7�#G�,��Yf����?\��>�y������n*>�q�q�g�<P��q7�|�Y�@�#���c���7��]vY��O�7�x�rO�j��V�6��H��d����Z�r�}K/�t������@�'����Z*VXa����G���o��b�-�+_�J,���e��a��*��!>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|�\��wU���=~z��������9c�e��W�](��l��������w�1���*s:F�A��_;*�W����K�`>���'�}�M���X[�'���r����|5&?pO�V�����X��Vn�]�t��L����Iw<9�2�`�<yr\}�����W��{�N������c���'V��[=�Pl�������2�k������dO�t��������/��~��9j?�>�l�����O�=�2w�����b�������'�9m�x��I��f=�W&P��w^|�+_�I�&U��{��_���n�8 z����}����v�)�9��x��7*s�
={V�����?_������we����@=���6�6����fG�2c�����W_�2w����{�������w�����w]n����7S�.��{U�'������3��z��r������_>>��O��W^O=�Te.tM�'�>�u�16���#G�)���l�I����|&����hll,���_���o������>;��[y����<�@��e�\>�v�}�r�~s���x�]w]����1h�����Or�i���y�}.��_+���~��:th�?��7���x���K@�V�9s��'�x">����|���~{e��e5���^[���?�����t��m��>����!���rK��M544�'>��2��?�YUB;���W^y%N8������t�A������������ef;������~�����O��s���/��o��Xe�U>0������U�c$�r:����{�W�v����<�lK��\���[]����#���#�(m1��>����f��	��A�w<�P���5N���]S*�:^�n�m1���d�#��_a���?�y3c�UW��_<��������c��W��o��q?����+������q����?�����Gy���{��q�a��������.������w_��o+	�|�"�,R��������~��?��Xi����^�k����i����F��}c��1��c�� k�7�`���m�QY����C=��{�����n���o,�]t�X{������]s�����	&�����[���7���w�9P�kI���������t?���7�������=�Yg�Xb�%������c���
7��U9���>>�`	~���S�������r��5�������[����2��_��$r�_�~%����O�>�V�S�A�<���l���W�O�L��u�]w�M7�T�X���	�<�~��Xz��K��J�L,��1bDI�db(�e&%r���Yi���f�mV��=g���?���~z,��b%A���y���}d;��������ZY��/�����K���2eJ��m5�C��LzT������r��},���R��<7�|�r���	���
��f���Z��%��T=������w\	�f�:��������?��o���L�������3����������?���^Z��e3�:|�����t�������{��g�5�9/����r�3�������fQ>^���:��O,����G%(������!����r���j�LPe�9������������"-����I��g�:�q���������_��k�����|&�h�����
7�P�w���_��s_d[�z�����?�i��
��~����;�G^z��rLL�4�<����|�Z��D;������L$���s�9����l����	�l�]tQi�2����������S�t�����z���K%O�vT]�|�e�]V�����:S���d;�$I>��u2����=O�/$|�g2����|�T���V�r�-��YQ��/})�[o�W�g06�<�v��])ep4�s20���Zm��������+��7�x�j3�������tVOd�CV��Jz����0�c�=JeO���mV
,���%�������s���U�U��m��e�Y�T��#�o�s����
��u[c�5J�Uy_&���)l��j�l��{lI8��O���:��r;���Sn�L�duX&oj�S��l��X�
��m�9���DS&K���jJY}���~5>����DSm'~������:T��|�<�������LDee�'?�������%�h��j7f���������1�:y~�S�*��������o�0�U�������S^_
nVeWGyU��3`��Y���7���[�j�%���
�����k�Y*!���L��&���G)�c�m���mS�|�L��U��h��]A-��R�[m����r��pv��������Tv�����d��v������l�L44g�e�-���g�V�]&n�]�����	f����^+��v������p���r?�U>w&*��b���`���GV�|��(��*�����6���LRT���Q�Je�8�Q5QR+���y�e��o���{L���X7m�x`~!��<�W��`�<�1I����ri��ae����'+�{��v��\�����8��L������k�Ul�{��?������O��r�ke�8���Q���s���������a�J�����_*>2���e7_���X&�y��T���������LB��6�4��s�����W_-c�d���x�����
����4��iIK�9�@���	�LX=��3�*��c'����%�KV����c(�G�UG��2�=O�/$|�{���`vv=��y�}Q>��2NOs�����?�����Z!��n�������g zV���L0��9VJ&�����>�z=���K.��l������.����MX����T+��V@�9�lc�������6�q�+��W_�T�da�^~��Um]E���"�v�������_�n�Bh����[��*����@g����e�lx������:�C=4c����R"��.�r ��>�}��������2FIk�" �'������J`���������
�|�9h}&����:gI�oL��U����d�K���/�eX�'���<&2�����������<v��f���e�;^�7�xc���dNV��v
W�Ot	�Zvm�����|��q�����3��];eL�
g�Ux�n����3���n��<>+sZ<�j��+c���M�k�e�=��(�����_n�|������)������x&�MV�5��n�2	�I���O�\sM��s��\��0�����K��0�B�
�=	�jwi��Ys�f"t�}�-c�d����J�LBU�kk�|L&K�b��xXU9.N�p<��$|�k�d�n�2p������3�$njM�4)N=��20zV�4��_�2^G[����t��]0��ok�����)��8�������x��O�8�Lw���D_���K��Vn�D�C�Pe�M�0���L�57
-{���M">��#q�}����39�m���`���8��	��n0��i�u�]�<w��\�[>W�C��<fG>�NV�d�^s�����O~2�<�����oy�q��1����x`~!�@]��LV�T���	�Tg�H��*s��]Ie��������:�TKTe9��\v����7U[A�A�m���t%��_�2.����^� �O��r�����`�s*�:2����������	�� ����f
�O�<9�����m?h��f���&�V^y�v�I����kN?��4�6��/�Or|��?�s&
R&;j�v��u�UW����d�7n\�V�dRV5]������;����?�����g���������o�&�/�3�T����SO��O>�d�����X�=�r�����Z����/~�����x`~!�@]� p����}���`���.��
6������Ne5AvU
�n���e���k��7.���r��{�Y����X��U�1P������f�:}��.]he���O�m��&��k��u�]c����+��2v�q�2����k�{��|v#��+�T�v�Ng7ak��V�r�)�������o�-�,��}�������������������d;���V[mU��N;�T*��~������%e$/�����o�yY>�r
6���l�Y%S[YRM�f�(�+�T�}��5��%�\2c�M�:dR4�N��������e�\>��!C�z�{���m���\���Ly�w�qe:�e�}e{��3���f��������B����A���-����vV�d�8���������2>F��������*�'�tR�>�����e�I���*��W��)�?����RV>dBu��M7�4����8��c��@���J�P����:�����q&��J�'�x�2���80����K�!+�����*�l>��2�T�A��~eP?��On��?,���6�U=9FO&r����*����0�}f[�����������k��v9���rL�#�8"��b�x��GK�[u<�l�g�qF9F>�������C/9VV&.j�av������l��.�q��5�MyLe�5�|�L��1��7���WZi���:���Rm�x`~�0�i����)�"�?��n�:Z������PW����7;�����~���xW��#}���/��T��	�'O�7?�E�V�k��3>��;+�f_V�}��_-������9�����:��Y����WW��O7�tS,���e=���O�$|�eWX����b�e��n�aF�r]��/�\�����V]u��\��O�$|�#u�����c�t���v�s�~Y�p�����__��*2X�c'����H�U����nK����x�>�te�z�x��I��g�T��T�jh����������C���/����8qbe���������qFP��5,��oU�:��H��S�A�r<P����2
�|b���W�j����-�uW�C��>qBL{������c����G���'�P�t�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�&&M�W^ye2$b���]v�%�S�N�,�v�����>U�������{�-�������>�����#�<2�Xc��l�A�|��1b����i�����o��qq��G��g�}�����[����c��11l�����"�������SO=5�?���7e���������N:)=�����G��������sO4(VXa�x�����^����.~����j��VYX����q����d�;�P�.��~{����{K�������n�����]}��q�i���{��G�s���/���Zk��~������<��������.� }����������|�;q�
7��g�&L�<X�I�Td�m���,�L��Yy��+�D�V���FY&.'N������G����Xt�E��
8�����6�h���5jTY&+�������(:��c�}��Q��UEGqD�������L $	����'�o�K/�t,�������DP&�^~��6U�<��s���h�5���}�����l�I�����k��y�w�yg��q��W�^e�*�<xp����q�]wU�:	���^8VZi�x���J�������i�>�<�LI���Y��T�[e�UJo/��R��c=��S���k�q{���IO>��n��B���O�>���~�t����~7������S�_v��]��}���[����������+����n����[n������?_���wJWp}��-�7�C�P�����1�����d>5��j�����J����x,��B�o�������k���7���t���[��.��*��*�L�4W�	����z�{����g�%��m��&��r����������/�Q�FU��$|*F��vX���q�G����������~{<���q�!��)������K@W�0�]��Zv����|�_�3�8#Yd��=���u������W_]�\��y��w^z���b(�E�9������/�C���g��?���O���K.�e�]�L�z��'���/�|\|����_��=m��T���m�
7�Lu,>�=�X��-��@�'-��be\�1c���?\���%�X������Fs9�	&��/�\�3y����S^{���%���7�|3z������{W�2>�j��.�(������U�vN:��8��c+s���4����C������e�Z�j���'���^,�����J��
7��n�me��U����O��?�2X����Xw�u��7�|s��59���{���G>R�o��+��n�i�t�M��OT����G-I��}�c1`��2�g����(����I�&����:,��2����W�:	���6�,v�e���o~S�gj�>9����=��#��r��=-��u��s�;vl|�{����{���������T-���e��^�z��R>w���~����o;#�3n�����N;��k�]������O>tP�u�]���K����1sF�U�j.���4hP��r����m���q��w�Ty�I���-��K���[/�L�w�}w����{�=zT������/}��n��
+�O?�t�����v���~��Xm��*K:	�&2�s�e���������Jbf��7.�89��"�,RY�=�%|RV�d�l\pAI$-��B1x������'>��5_d�����Yg��]w]ID�����b(RK-�Te)	��g�:'�P�$|���@����s
��U����	���K&��o4V��l�������}�4T���/N��eR���v�h����=+��w��S��?O��6l�~�	��d�����c�����o����5c�w�#>��2wf?�qr������cE����Z}����r3w������K'��#1���
�#

K�m�e�u����Q�1qJ�v��dr�7iz,��!>�n��[h�_�dO&�.�����8����`�s�����L����������#�u����Qc����64��[��^��<15v�x�����OW ����3-�~�1����T5g���1v��x��������'���~2>����R�S5yj�/o�k,�-�\��j!�.	��e�f��SK�k���rZ�����wo�%i��m�P�c�Xf��8k��������"���)����q�V=c!Y�.�����F4��/N�O~�G,�������?��w���}b��-���#��[��P������U��������)1��=b�R]����[�=�Gl�z��_[�oC,��[�3=�L���sr���{m�Pe	������L��7�L�o^:1�Y�[��^����1|����
��&7���'������z������5�V��P�ww�[�{es�����p�����)��=z�GWh=s�s�������gl��{���M��/�o�w�o���9�O��I'];)>�\��w��H1���
�C�'O��=65V�--��d��/7��/��wZ�����b�%���'�mOL-c��q��x�����z=���O������������gCXB�g^�������/�����#j��g�;���k��������{6��{�����'�iR|��	������^�� ���N�nuN�@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s
��U�������=%�}fZ���9��E{E|l���M�U�1��$|`>�����fbL�:wR�z4��������ly��de��J��|�|M�	��d7ns���N�L1/H��|����i��I�	�		�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�SM�41����1j����]��'������c�c��G%�>�xe������x�k���6-9��T>@��>vL�}��c�.�>�����8z�6�ro3c��w��/�o}�1���c���j5��Z������~?�u�����{L4�YYj�"�t���c��?���o�?=?�����>`�h��Pe�������W^59����3��������X��#���k����d����zh>$�t��7�����������r����1p�X����b�~/�/�Ben3�/������	�SL���1}��w�&F��}��q�:`����{+K|P��GC�>�[�[h��F�~�c�5���������yy��H�����,��M����{�q���KK�����S�}��T�u[�,v�b����7w���M��c��	���D>@�h�F4,�h,�����m=>�j�=����h��t���R�7}����E��V)I�~g�&�-�/����r��H��4����?�VnEt[l����������9�7�����W_�E����D��������yy��H����_1b���>ibeN������}�e�[�%+s�L���O>^��`��:E��V�h�S�We��7�y+���B��������6�=:�O�P�1}��h|���>�[�$|�N�c���r�w�Y�����y&��vbL�0!zm�mY&��}��1��'������O��z�����yO?�T��x��R	�s44�"�~#z�����N��_�7�y;�8�ge��8jdLy��h�f��=VY-?����g�!�����yy���a��*��|`�I�*Ss����L1����s>uN���I��9	�:'�P�$|���@����s>uN���I��9	�:'�P�$|���@����s>u�a��*��|`�I�*Ss����L�o�3O���S��+�����X
�����4�k��������
�Sd�����n����=i��1�5���5D>@������&Unu�|�|����)���m��wW�,>@���n�Z���-�$|���@����s>ML�>=z��8���c��V����Xc�5����~���+���n��Iq��W��>��Xl��������{�-�������>�����#�<��v��l'�|r�1���{$|jd����.�-��2.���Xr�%c��!1q���������k<����g-�=��zj����q�]w�z�����z\q����;��g�S�N�,��|0��k�8�����\�Q�F������o<���e>@���q�����a�b��W�;��3x����������|�;q�=����q�*�h��W_��vZ�����#���������{o���Z����<g��������?�x\p�������7�pC�y��1a���#���OE&q~��_�J�L�l����+���"�������e�]��g���_��o��������},���q��������|��6��$u��r������;J���,�<=z�(�s�8�����Kq�@H>���n�������f�U���_�~q�UW�*������{.�������k�Y�����_?6�d��������^+�&O�\*���;��z�*�U9������W_-�
��(�3v��2���7�\������y���X���c�d"�o�������g�)��Le�OS9o�UV)]����Ke^V=��S���k�
+�P�5��IO>��n����	�w�y'.���R����L����������9o��.��l>������	�L��s�9�����.�6�`�8�������.���+��R�_|��gt
W�O�>��r���������)������7�C�P�����1�����dmN��92N;�����?���O��Yr�%c�m���;,N>���w��yy_.�����:����<GW5u�����#b�]w�c�9&z��Y��/�Gyd�����
�-��)-�������8qbI6e���� ��4LWe�Y��������$<��[����ll���1`�������Q>��_�[o�5.������;b��A����$TZz�����|�%]��w�I'�J+�Tng��N(�����q�Yg��tZs��'������oK��9M������|�l�K.�$���_Y�}mY�5<�@e
�������L�]��we�=+�������S��Lu=n�ae�c��u�1b���o����n�>�l\{�����{���.�j�&�8p`|�s�+I�Gy�<��?����]i��\�^�z���7�|�dOZj���;��N���Nq��7���=s���Z���.��"g���+��47M{�Ke�$+Z�8��vW�t�j����[��w�^��=�����w�_kU;U��w^z��q����!�R�;��k^~���j'���>oV�dR��j����/_|q����r�g�I�*Ss����L�g���+Ss�R7�[�Zp�Z��	�3�8#6�`�9N��|�5�\3~��t�dO�����O�${R���+�\�5kK,�D���W_-��������_.���I���,�HI����;e^So��f<��C�1�{���d�H��������e���I5��I�������s�=W�{��Q�o�����,�Ly���c+s�7z��R����|F�'�=���z��.�?j���>Z����2A�����1c��K/�c�9&^������G?��2dH�~�����OW��/�[���B)���L m���q�M7�O<Q���L�<�����},P����3��b�2��?�9&M�T�������{I$�XC�]	���'�o������.���t�s�=Kr������|FWl#F�(c��r�-��.����Y��u�����{������|������������n���z�*��-������~��2VP5�3n��8����7��M���N���k���J�d�"�O=�T�5�2w��c�����q�	'�
7���GJwk���'c�5����??��c�����6S�n9����o_�]wU�������_�j\w�u��z��V[mU�s��7.	�a������Zj��p�
��>8�]w��v�m��d�i����#�<Rwn��J�d%�GQ�{=��2�Ov���?��L�|����[o�5��o��������_?.���Ru�?��?��g-���J�?����|�<g&����?�a���x@�m�Y\s�5e[��n�%�������g��V+�R��j�em0z��8�����3w�}wen��Z�%�����:����U�����-R�z��!W����n��2��hW�Occc����mN�������*���-���������<�J����Q�g��qq�}���^��{n�;6�M�O?�tL�4���i�>&L�3�8#V\q��x������k���$y&O�?���c��v�����G�Y����d��a���#�(�����n�N'N�Q�F�
7��vX�����{��N�d"'�p�o������k��66�t��������.�(N8�����[������@ghW�'�k����b��W���;.P�gf}����:(��r�x���b����{�h�J��3&���h��b�V��m^���c����_|�t@�hw�n�{�����P������Ov���=Y�3r��������k������qt�v%|^x��t�M��;���/�8&M�T�gf���i����sOY>@�hw�n;��S���.1l���y��������_=�N��������.�v�!�9��r��;�Xy$��a��*�m��/���W_}ue�m��v����,V[m��`n|�����u��E*S�1d������M�V����I��.�,n�������[n�e����t�v�������k����f����T���i���c��s�-�=�'O��m^������G������+�3i���U�m����M��m^�������?�����t�V�t���#�<o��V�=f����~�,�L|�K_��={�������?��Oc��6*�>�/�x��3��m���m�c���������${f�O~������


�9@g������q�����_o��fL�0!~�����K.�o�},��B��>�{�����},6�l����We.��$|$|Z5r���g�}b��V�3�8#���S��*$|��O���m��_�������SN���{W��l������oGccce�]	���G�g?��8��cb��������������g>���8:G�>�1y��;vl����1|�L�R������g�~����o����j�E�n-��^x��x��'��C1��E��Y���i5��~���k����'���i�A��/~���j��*s��&�#��y�;��S�N-c�z�����+��'��{��,�AY���@=z����	�/�3�1|b������������r�����_�~�${��YV��E��
�6kll,���}��q�����������������W_}��$�i�>#F�(	���Z+���/����x��K(�����kb�m�������@�iw�'�x2���_�2��r���w�C����^���K.���J|�[����z�r���	����*����8��b���q�QG�J+�T�7b�E����q�Yg�C=T�U��y����0aB�w�}������>}�T��Y�n�b�v�����T��;�r�]	�������?_�����en�Yd�8p`���1y���\:Z��tK��M�e7my.@�jW�'�vVYe�����/�X���g�y&�����|>�����O���c������{.~����#*����^�a���O<�.��s��K�!C��~����~l��Fq������>o��V\q�q����l�]w]v�a1t���#�
�g5O3��'�|r�u�Ye�9��9��c�%������'��L�]7�y��C6�L�]K�toej�1[	��{�����[o->>�`���Z1h�������/


����E�G��s>^���c��7n\�w�}q���)���^zi���<yre	:�l%|2�s�g��+�o�q|����o}+��g�X��c�u�)I�I�&U@giw�n��9���������}����o����g��1f�����;���n+��|��q��GF�=�m�����>���;Y���.���~��Xy��+��'���'���?<�����_;��s�^��I���U�������;�]w�����dOjhh���Z+N;��X~�����kL�0�r/�]	�L�����������{Z�����������(�s�+��c���=��M+]��E.o������b�-[l�E�x������W�6��^����/6�l��8:G�>9>��{�[m�U|��%����X��=Y����3���o�J+����Oy��az+}��=:�>�����[���w�y'����2=h��8p`�N#F����_e:����G?��zj�����:����U�����-R�z��!W����n��2��h5�3r��R�3|�����:th\r�%�����3I�H��$�k{���?�m[{t��-_|��?��$|$|�:'���%|���9	�:'�P�$|���@����s>u�C>���N�u�]q�w�o�Q�@g�����/�GqD~��1q��2��������*��b����k��_~yL�>��@�hw�������~��q�g�K/��&M�q����g�=�Pl��&���;�e���o�<P���N�\}�����o~��q��g���/�>�l���6���W^�������*�_{��1m��2
@�kW�g���������!CJ�n�,�L����=�����������
6��t���O���c�<:^�>&L(�����*��K�y�'O��{�Lg��{��e�G������1cb���e��]�5���o�����Xw�uc��A����O/]�e��[�9~Z��L�"�,R�{�[��#G�y=�P�z���������/_��g�y���3p�����Oe.�]	���{������;���>8�?��8��c�}[l�EI566��w�GuT�'����9������Cc��a1|��8��K��a�{��W���q��_�"n���2?���4L��v�)�x�~��2v�������N�'��=g�uV���
���;F�^��|`�|�����u��E*S�1d������M�V�����.	�/���.��ZZM��92��~������


m��>�������:�Occc����ez��/�����V��u+�����g�o�V>@���Y�>�n���@����s>uN���I���v'|������?�����9�K�J��3&.���8��c���_��`^jW�g�����o�*��K,�De.�R�>�.�h4(�z��5jTe.�R�>�z��#�8�T�z��e<���-+�7���=zt|����W_}5���?��>��0`@I5444��������#+�@GkW����1^|������+s����������m���m����qt�v%|�z�(�3n��������/�s�=7����M���~:&M�TY
��4[	�	&�g�+��bl���q���5�\S�<�'O������N;������#�,�N�d�g��aq�G��C��u�]�L��'��Q���n��;,^~���=t�v'|2��]����~��c����^�n�i���~���E]'�pB�r�-q��WW��3�+�����v�m���+�q���3�>}��A[n�e<��C1~���=t�v%|���?�xl��F��
+T�6�����Zk��/�X���s��K���{�hhh��`^jW�'�j�����9rden�^{��x�����8:G�>/�pl���q�w��_�&M��3������N�{���,���s��K��v�)v�e�6lX����q�UW����S�N����q�E�;���sN��w�<���0�]��6{����������2����n����~���Ze07>i\ej��y�"�����qej�Z��{+S�vW����e�]��rK|�k_�-��2���[�o;��b���q�5�H���U�t]*|T��j�����~������?�x��y��]��1"�9����G>���j����[o�q��M�`A�����K.�\rI���.�>c�����:+��f�Xf�eb�]v��/�<F�]y�m����<yr<��#q��7�UW]��sO������n������c�V�n��]L�c�,xc��Q��V>����^�w��_��]w]�5*�Z�����_Y�L>^��C�n�N�/��B��o����>n��������V���	����;��#�w�uW���'>�������n����G��{����G�n�=ztr�!q�WT��g�%�,����d�Mb��A��O�����$��K�V566�;��S��^z������>�l�����}I���z�=sQ�>�z��
7�0o��F�x��%����������$}���<yrei����'+}^{�����������[o�5^x��r_��}c��7��v�)��z�Xe�U�g���>�����>������������)4t�����K����6��$|��3[�u��.�l����q����G���Z�^:�%|�8h���q�u�����j������������~5�
�/�x�t�vw�6a��x��Gb���%�s�=�T���d�Mb�]w�w�1V_}����G�`n���1|Z��<���OI���}�����c�=��O~���?��?���P��
	c��R���KWm��rK����q��W��{�����U����_�ns4���T���iUV�T�=S�N����+�
C�����o����4iRY����
���_~9?�����+*s>h�]v�3�8#X��
*|T����#�>���h������.��T��v���}2)���y������kK2�K_�R�|�������z�_��\��n�<�������	�����M6�$�:�����o������?�����'N��@GkW�g��������z����m^���=���1n���+`A��.��Z���Yd�Eb�UV�|0^{��������\.���s�+���w�<xp�s�=���0F�U�gf9?���6�`��8:G��wU��d���q�!��W\k��v��������B-S�L��������#����;�����_��@g|��[��a3��5b�����k����L-8���I�]�q����/+s>����|��?�T�s����O�566���?��_���G�?>^x��l������t���Z��[�z�:����P�$|����:�j���������������9����+���������:�
]��d�����>�����+s�o���q�%�D���+s��$�#�3����x�������[�n��������'�#��9	�/��j�MV�L�:�r���s�I��k5�3z��8�������I�&U���L��x���9���s�&|r���7�<����y�����o����	&���'?���k���s�s0�ZM����#���/�D�B-C��UW]5����/����R���@9o���q�
7�����Xs�5c�w,I���9��C�s0��7��iFv�v�M7�)��w�qGe�{6�t�Xl����;��w�}w���r�-����vl��6=���4�25w�<l���{F��25w-u����G�>U�����������K7mO>�d���
4(��c���g>k��Vt��j1�A$|$|�%�=�F��^x!�w����c�%��E]��07I�,x	�9*�ihh(��d�g���.]�-����=s�~����@����s>uN���I��9	�:��	�w�y'�������;��7����3�V���_�#�8"?���8qb�w�}��V[m[l�E��5���/�<�O�^��s�;������g?��8��3���^�I�&��q�������z(6�d��q���������(�t�v'|�����m�7���8��3c���g�}���f�m��+��?��Oq�UW�������6mZ���u�>�}�J��?>��2dH�g�e�)�s����~:6�t�0`@�����|�x��;vl�@�kW�g��	���/�*��K,�D�7y��x����t&|�w�^�{��/�p�3&�N�Z�����K�7�|3��������
����>}z�'?���9���+��"������m���e�C=��zk���������y��g�����+}�������+���w�<xp�q�q������{l�o�-�(	�������;����*�����8:G��Z:th6,�'�xb��9���b���*��7.~��_�
7�P���t���9�N;e��O?]��Y}��c�u�)c��������VX!v�q����W���OW���n�He�=#�l\����������c�>@�%���%|���]K�>�G����>:����V����+���zj����2�L*|t�6��#G�>������i��C��%�\�����:���.�f�U9�]vY����3�]~����j�����s�L�=��#��o~3������o\p��{:Q�>�����J��q�W>=z�����|�Lz��q�g�AT��zw�S���[&�K��{C��e������/���1����L�g�h����*�>������}��W��?M�G6�B�#�^�G|uh�X���/B���Q���I�&�����`�
b��wo6���S��T2$n���3fL���3n��������^<�����m����+�,�c��+]�����q�-�Dcc�'�������Gk��F����O>��1bDe	�����O�S�4)~�!�?�O����1vb����o��`}��������Lg}�OX�!�X�[I��gDc|��o��3��_��g������_&G��`�������cK�c�������=�Z���ro��FL�<�2��d�RvIw���W��O&{N=������L����q�W��;�g�}vL�:����|���k�����O/�3q6j��8��cK7yO?�t�0���_S��"
����Y�[�7�{|���c���/M�,�������6��������A�Dl��{�ypjYv�N�c�����-�n�P<���x���/�����OV���<���8qben��z��x��g��-Uuu��~{��nv]}��q�i��;�P�6��������{o���Z������T++x�������?^�M�>�h�x����c��w��������3��	&T0�|u����}zG��g�f��qzL������2-��G��:+v��,����n�,�-��}�y�^�{dq��#$|`V���Yt�Ec�5���n�)�����$������7e��6��teVo^����Yi��b�m���m���G���r���1p��2?�g�h��JR'�vr������;J�(�G�j�j�l�E�#�8"����E\&����������I��==~w��X���x���7�������5��uz�x��,�p��|2��]	�����g?��R�r�a���DV�drd�������I�o}�[��������Z��$VYE�]�
6�t��^�=�\�}���;�L�5�����&�l�����ke^v}w��w��w�1z��U��2q6x��x��WKq���o��O��||�3!�;��.c��J��3����l��Xg��C�+�����#��?`��������c�|�R�>)�Y����+�*��C����C�P�?o_v�e��v��.��B��d��Yg��w\IZ��g�y�$fr;e�OS9o�UV)]����Ke��q��������^;VXa�2��|L���t��+�o�P\��>q�n��x���rb�5��dMK�3�1~qZ|�#=b���'�>�f��09��k'��/7��?�nR�&n�%�����v'|Rv��&���k��b��Ae~��������k��5�X���'O<�D���?,�k����n�fk�+��R�_|����p���O,��re����/����;�+��(�oN&��]w������W��]Y��l�n���������������U�m�-�O���#�X}���?�|�8��=c�;���M���1%v�p�Xb��X������e3��c�dR$�>����K7����~U�{ZJXteYa�����L~���=���c����^z��[L�8��C&|��
���;�c���&�<�=[��"��z�ko���;����=,��$�Vk�����p�<l��������J��P6,0�g�����.��<��8��s�XEY����e�'�����~7��iVN<��8�������m���>��3k�Lv����|�t�w�%�D���+K��-�����L�Z�-���+�1�3�|��c�����}z��������w��_��g]������666�ta����9%~�G���
�����G���Vv�����
q�n�c�w���_~��x��7+K�������N����{V<�K�������S��z6�p��T����h&G^{�����;�����SN9���L�T�]��K�?�A|��_��v���n�4�d���a�O��#�{�1~���e<�_�g�49�^�!6��{I��^�G^65xvb�'�����������}o�i����)Sf�1����*���=%���	����q�6=K�'e���0/���'�;�����?�i�3�2�eC���J�����_�C9���s���['�n��y���zhIx�s7�Z�s��������Z
��l�e�-���>�/�|Y�~��U��?{�E��q��IH!	-��@AA���`9P�l���==�+�rz�(�^��Y�rz��'��S���� H�����~��B6�n��]�y����>3����g����<�=�(�7����[f+7,�g���_�O���Un�����R���4��wU�������.�j��S�5O�Z
��J��J�Y�n�v��T7���l�7���_u��xS����Y�T�u�G���C��qf���ot�%'{��0��m����1if��a�~���a�u�����8�����v��P I��?��;�0[�v��u�Y���?�K/�d{��y����� �}����c%b���z��o����?�|����4���Q��O5���~����Yc�z�r�K.��N>�do����'�x�
0�y� �.��������y�����9r��L�2��9�o�MB-����^��F���|������-Z��|�V3��H�<yr���[�
��]���O>��
�������M�6������n2g�:���S�N.-55ucK�7�|�JKK�t����XC�o��k Q|4pVJJ��n����n[��3�p��=�~��G��U�~���G���z�������I�~�l������O���BA���V=jYu�I'�>�����
��i����[�p��[��Km����\ �v��:��K��/���z�-��Ga�z��������������:v�hW_}�k!4l�0�o��\�n{����|��v�����#�lU�'99��<�L����g�yf�.�PSff�k�����u���W_�������O��_�����!�b����]u�U���������v�m���������Pc����~�z�����.���;��'��u�v��[����t���w�n�@��[�M5���2��*��xS����Y�T�U�G��
2�&O���4l���6q�D����R@,�!�S������Z�D�m��6t�P����R@,�!����I���������3f��Q��8=��>���{VZZ�-	�XjT�n����]y�����/{)�<x��w�}��K/4�t�K�������_��=t�=�������n|����������@�D�y��7\0���/��������:j��z���2e��&b!��Oqq�}���v����W_m���������Z���>���o�ZT���"[�h�����:u������Zn���VX�e�
h	���
�%��Off�u������+[�b����k9-���@�7�W_}�N=�T;������o�:xs6Y�f��9��|�I7n��w�y�@�[��o�f����VTUs������bg�me�u���h��e�Z�>�f��}����q�,o���:��v�Z������_�}���N?�t�����j�����m���n�7�|��=�����}{om@"S�g��+��M�����=xv:A�(�!�u�v�u��SO=��l�����z����S'/����Vj����>5��z����K�>!|�D������s������?������u��v�!��o�[����%%q����w�����{��G0V|4�������,55�����K �#���>�j�SXXh<���3�*++�T���b>|�q�6m�4�
�u�G��k��������?���r)))��K��|`�s��u�]VQ��}9�4Q|^x�{��G��3���n������9f����7�x�>��S;��c��[o������\�BTu��`����9]�v5��������dx����n�;�����@lD�Q�m�-�^�zY�N�����t�bt���;�����T4���t���J�����'99���X�*����i��us��-Y��K
o����W_���b#��Ozz�����f�����QP'���\������O>�C=�����������B���k��G�:���o{���7�l������o��K.�����NZ��V���Bo�yME=s4�%�r����W�i����#����Y��r�����R7���v��l�$>|��j�*�9s���7�K1�s�=�O�>��v�����R[>����D�'1�iy�$��Q+Z�~�}��W��Oii�K+**r���F|�~�M�6��<�Hk�������n��&+((���1b�]q�n��V����
{��G��SN�>�����m�m�����,Y��z�!����l�����B��O>�����n�w�}]7n��/���{s���oo������:�^~�e{����9���>�����[o������>�`KJ��+:u�d�]w����~��G�V?���>6l������8��������;�lt�-\��
�T4��>~������ukKII�R���|����}@�D�IMM�m���/^�`��u����=Z^� 6�
�deeY�^���w�q�@ ���I����o��Ms�k=�FTu�v�)��a�f�\r�]s�5�`�+++s�����?����#G��l'�x�[����L���]|��6{�l/es=z��'�x��8�/�������X�>*��B$�%�r����W�i����#�>!�r�M�:����n���:z��cS�L!�����6�����o���������6��I����O����X���	�l�
���~�7o����;VYY������n���k�������%K��y���>���v���[��=��W^���R�y�����=k��q����~�.��r[�r��&b!����i�����=z�`����t�R{��7�K�.6e�[�j��x�������t�NT���2{���m��v��^z�.��"KKK�����G}d�
��?�:v�h�]v��<s�L+**��M-����sSp�����v����1c������edd����L��G���44��>~��***\7n>���m������[�~����tih>Q|RSSm�m����<���,X�����o��\���u�����m��w���M/��OVV�����&O����Y�t���������n�rrr�r�����3���i�l�=�$�CQ|����'�h={��.��������n|��z��n���������5��k�P�ohzQ|d��w��_~����*;�������'�|������4�����p�	��c���;�@�7�d���,==�����'�X����T��>*��B$�%�r����W�i����#&���[�h&���)((�	&���C��w}�8=�j���[7++�K$*Z�$Z���>�|���l��!nz����]�'O���#1p�@�nNN��HT|>5��P��@���u"������O���E� �������A����k�K��{��Hp�|rrr��w��@ ������ 6h����$8_@�������&L�`����R���m[:t�eeey)�D�l�7��������x���}����q�,o���7����gC����'{)�8p�M�8�q|`+@�'1�!�SCii�}���VRR��D/==�z��miii^
 Q�I|�P'>���O��$y�HP���)((�	&���C��w}^�~���D��m��YYY^
 Q��'1���.�j����!C����'�w}�<y��������999^
 Q�I|��@@u|>���Ob ���>I�;T�>�v�Z7�O}/-����������������w�m���C���6���:��3]���>'N��C���.]�����nIIu��:w�lw�y��o��K$*��I�������*����o�^z�M�6�{�1;���
��.|����*ZSVVf�V����?�@� D�IMM�m���������y����
�dee�`3g�����K��U�G�z�j�z��k���~���b ��/�����9s�����/������](##��[S�����;�����{)�D�l�7��������x���}����q�,o��������1�N8�����|���l��)a_K�,1����@��*�SVVf����-^��.��b���Ol�����&M�D���*���<s���������j}������z_
�$%E���*��MJJ�m��������`K�*����i��ww]�n��PST���T;��s\���'����Ro�_ ��n��������|`���N�:��l�]w�n��yK����z��miii^
 Q��ez�>*��B$�%�r����W�i����#��O^^�
2�&O���4l���6q�D����R���Ob �C��^6a���'Rm����C�ZVV��HT|>���Ob ���>I�;�G� ��Hp|�G� ��Hp�@�71��r�J���l���6�|o����mkC����,/����-�����Q��"/��;��7��:N��M�Q|
���o�x�������
8�&N�h999^
 Q�I|�4H�����������Ad���������|>�*..�+����x�
?~���|>o.`kG�'1�iy�$�="EEE�h�"0`�|��{�@T���$KII���[�wlyQ|��ic����-\����[��`K�*����lg�y�����3�<c����l)�@�7� ��o����3f�e�]f�;w�c�9��u�f;����TM�����woKKK�R����Bo�yM��M!��O��xS����Y�T�U�'//��b�'O�R6p�@�8q����x)�DE�'1�!�S����0a�k���m����C-++�K$*>����D�'1�iy�$�	��������k����C�5�O������z>
��y���
�hz�m���Z�A�n	����W����T��>*��B$�%�r����W�i�����>	��@�#����R���m���X��}�k����r�O����:�m������f����*�-��Vi��[@�)��k�0�ZK���u7��=0��������M��TM���Z�[w�0���:�0��p�u(�w�4�{�x@��pJ���%m��e]:��;�j����M�W�����xK�T�����q;��p�%o���t����]f���b�|�Lc��|	%P^f�]v��A'�/+�K5K��c����J/���a�Z����j�H �|������>���k�j��<�2N:�K�R����dK����R�/��%�k���������g-e��j����@<ht������y���G�s�=��?�|[�v�����[o�e��/�� ����Y��'-��~��K7/5����Y��>�w�q�_���\7�|�3��5E�������Onn������.��R{��gl��%.TQQa����}����;�X ����*�����-P\�Z��Z��%��3-�����]��n�6�r�
����D����u�G�x�y����_�~v��7�����U-:t�`��-��#G���U]��+~a����������������Z�$m��Z�>���e?-��/fys=��^`K�:�������/�l7�t�M�<����j�e�]��fYYYv�m��C=d�g�v�����+�����Ek3�nk�����0�����@�/�Jr�����i���R���^ ND�)..�O?����9���,##��SSRR���6h� �������@�(}w��<��.QP���;l���(-�R�*sWZ��������D��@<�*�STTd�-rc����x��effZ�.]l��UVVV�������<|���[k�Oo�����Z����QWm����*|���I;�����>��U.��*�g��c�;u�V{����(�.����2�O��Sk�����1���[�k/Y��'X�����p�5(.2��<+�3��y��:i�~cmn�������Sm��Yr�6���;,�m;�L$��#_ �vJJJl��6c�{���G����+������8q���?_�������>����KOOw����l�7��������x���}����q�,o�������6�{�����.�������i���6j�(�7o�����`@E���������'�|�:� ���km��9�n�:{������.������z�-���Kl���������t�����o��z�!7��=c���:x)�DG�n��.�Z^�n�
��V[�r����{���W_}e={�t������v��|>��4`k@�'1�!�@��$>-/��>�/�j����?�/�`��������K
�s��v��wZ����@���Ob��]�5���?�!C�������o���6q�D����R���Ob �C�n�*++s�{�>�l���m��U�z��:_�&M�u@E������s��I'�dw�u�v�a��cG�z����=II+QEb�III���������TlIQ|233�{������/[RT���T;��s��������VQQ�����y�����l��a��[7�������^��O8�����woKKK�R����Bo�yM���K>���M5���fyS-G����\9r�=��S^J�h'N���/���$>|��E���>1b�u����?�x���>m����C�ZVV��HT|>�Z�~�����~�I�&��{����|���I��#RQQa�����o_�e�]�TlIQ��)**�+���JKK��G���lo�%��>����[���/*�R��/+�R�k��p�����K�����O�Z�nm�����3g�_|�����Yw�0+}oj��=(�w����o�*����x��v�����^h���?l���VPP�� ���'PZ�}�=��~�WQ|��]k��_���?���\6l������k7���5h� ������_O��5���fzS@��*����m��%������5k�T�W,�q���w�UT���{��w,D���Z��>�/|�/�~���v�Z���k���w�������v������[�}��^
 Q�[�M5���2��*��xS����Y�T|#�#��R�-|�~�-Y���4�<e���_�u���)--�/���M������sII���Dzz�[7--�K$*Z����>���So���$��������[m��c���I�����K
O���g]t��U�G]����k����[ee������g�h�"����z>
�|��W��{���G}d�����+W�|�1=�K-��y��������������_���:����������6|�p��|^
 Q16c���|�r��/�`�W����b{����C�6h� k������������C9�����T@"#�@��>����`�����<2d����.v�}�YFF�7�H �S�i��w����oo�&M�;�������TlIQ|���\��m����'�
� ��Hp|j�����~��:�(�m�^�����n���rUZZj����w�q��M����3�8��}�]����R�[�h��1���c�7����v���[nn��@>�|���v��'���_n�|��}�����K.��N9�������`��w�i��v���1�z��e��w��_~�����>j���|��W��?�����^�y���f����km���Q�
`�G���a�;v���x�����?���_����������)S��=��c����Z�����ew�u���.h�����>��#�5k��������n���O��������m���6n�8�3g�M�:����[�w�ox��#���/��OAA�}���[e�A�fX<x�]q������1��������@���Y�v����K���e7�p�u�����{��:�u�jG��%P�|�E��{�k��������\u�Uv��g�.�@��>
L�|�����{������$KDK�.uA���{[�����M:t���cS�'??�K���?�h3g�t��i{���9������>�+V����2�����	'�`iiin:Dc�����/_�Z"HT 8�7}�}�����k�����f��E��D�1u�z�����RjR`���������L��]]+�����[7����MRXXh����}���v�yg�V���7D�n@�
�(Hq�������S�c������o�]w���9�{���]wf[�y����i�\�q�l�2���m[��[m���;�i�D�i�egg���l��6��~��u�	@��WT����T;�����������&O�lg�y���5����F���hS�L�*Z��\�����Z��q���S'oN�4��l����=%%%���>�Z��4a?lj��.�^|�E{���l��5.�s�)�����g����%%5*��������#�����K.��u_��������1c��n�	&� X8��Q7m����]@i�������-�I$�����?�� z�L���j^w������o{S���;��M�7�)~�)4tNSk���!;vtA������x?�F��|��	3����/��{�?�|��$���~u���
���/m��I����� �(�s�y������g�{����3�<c'�x���W
L
>�f��a�_~��H]�E�����.��{�14
'����^p�v4�O�5�Z����n��P��v�����o�����?���j^�G�|?w@o�yu�6���o�Sb�SSjTy�������?�m���O�>�O~~�]z������������������x���---��k�x����S�������;���������=��];��q���4��/����������(//�6l���j[�z���=���������,������s���������Z��p�	���o��?�l?��v�a�������~����[�j����y�������5��s����������� U��~�������/u�w��:�z�����=��ww��%K���������{���DQ|���l���.P��_?�m���+�����w�q
�o� �����D�[��R��Z��k�K.��u��n�N;�4KJj�0G]�v��}���i�l��y^�&
�|���v��Z�N�\Zjj�~��n��7����R7�V?}��$)� QE3�8���m�����{��\`�n��7�a
Th�����)�����:�@�QGe>���=��s�g��=�G�v-}D��O?��uq���e��zj�D
�i����~�&L��1�SXXh��{��?�N:�$�g�}\:@T�6m���+\�m��lk� ��/�h�|����.���5c�oMs��4h�t9�����/���z�z��eGq���Mc��;�F��>W�PW_}�k!4l�0�
�1�c{����|��v�����#��
lU�G]�����W�������=���t���Z�����t]�}��W6�|;������_w������C��^{����*�Y�����m���Z�����.@|5o��Z��u�Y�k�x ����V����T��>�����xS����Y�T|#�#��RT-|��k���:u���9�u��-+�>~���Y��������]7e�f�������{K����n�{����4/��h9B���O[NT{�b�'O�R6p�@�8q����x)�DE ��O}��-'��OAA�M�0���_��4�m��6t�P����R��@���O[NT@�F ��O}��-'�{@�jt������y���G�s�=��?�|[�v�����[o�e��/�����o�OV�����*�����U�k�P����2o	��+����m�m�6��B>��~Z���@�jT�'77�xz��i�^z�=��3�d������^{��>�h{��w�'ez��J���s+�O���KlQ����d~
.����.�M�]~����=S�|���w�u��gO��;�L��������B�1$��>j�� �SO=e�����o�����j���C[�l��9��������}���x��v�I���m��6��4`m�}���R�w�����cU5��_VX�L�]1(�v��d��$���le��6gi�-� �E�y��W���_��n��&O�lW_}����.�\���,����������g�ei� R=vH��/��[�H��:D^��� `�|����RjRk����[��5���+��>@��*�S\\l�~��k�s�y�YFF�7����$;���m��A��OAA�7������i��6u).XAI��_����[���9��"���
7��uO�l����^�>`/�,��9I��krU"$��>EEE�h�"7vONN��^ff�u���V�Zeee�E����%'��]���tD+���4�����\j���|���e. 4��"�Plv�)�u�
�Du�nRYY�`7m��� �2�|��Y���6��V6h����t�&�go�����}x+{�����4W�y�+%���a)$��>j���[7����%K���,X`3f�p�k=hN��m��I��_��[�Z�(�_�>0���
��xx@b�*����n�{�����v�=�Xnn�7������Q�l��y�������Y�.`e5{o�H-|r���VK���,����\���)�.�`g�u�=���v�A���^ks���u����/�l]t�������[o�%�\b�����v��.z��>�aS�G������l�e����7K���J��lS�G�{J��v��Q�_@���,���n��v��g��5�����>���������w�
��3���4�������J�����b��S����g�O/���U�O�~���R[��o���bIIfG��b?�����)s��Z\i�N+�m����]���@�jT�:;;�n���?�M�4����:;��������q����?�l?��u���[�N��-XQ|�j��:�gcNO��;%���.�����m��in���~)����o�V���Tb�3}v��i�M��-�����W����T��>�foR��xS����Y�T|#�#��S$��Z���	l���^J���mkC����,/��h9B���O[NT���<2d�M�<�Ki���m���������>�!����>������_ZII��R��e�l���6u�T[�z����v�A�V>II���@���O[NT�H)0t�������nO?�������@"#�@��>����f7iiiv�9�Xvv�M�4�*++�9hj1�g�]�v��[7���/l��
^*�Z�>VTT���~��
���������Ol��i��.�X����9hj���3*((�	&�������������3m�����{�9;����4 ��[�M5���2��*��xS�������xG>%F>5��>yyy6d��<y��R���l������+����/��$�����D�)--�/���JJJ���Z�je={�����{)���>�!����>���@���O[N����.����n�{����4/�h9B���O[NT���<2d�M�<�Ki�����-''�K$	|�C>m9�j���w���1cl��uv���[��}�G��r�J7���_�������g������&m����C�ZVV��H���|�r�
�����s��v����>h]�v��l�f�9r�}������O��{���$2	|�C>m9I�{D*++m���VPP`w�uW�`�t���n��KMM�I�&��Q��Y�v��u�Y��N;�}��g�����W^iK�.���{���o����-X��I3�m��J+*�����e���-�����v����--Gh�S�i���,���������i(N������O{��/���V�,�#��~C����DU�'33��u�fS�N�o���K
��O?�i��Y����z	��)��]��6��~YT���t;���m��5v����)S\K������	��K.qc����t�	u���>[X��M�S��7������f��m�:�G�����v��q~rss���o�8�[�n����� �E�III�#F��o�m������|���\k������]�o�������yk ����>�w������n�:���/��w���s�������j���?��f���O�:m���^�z�QGe{���eeeys�~U�[�G��X���m�5�Y��s��4�N�����/X��}�k���.
�����[�g3m�Cl��[��s-L�W�
�m�-�Y����?��{�Ci�wh>��5���h�]w��a�z���d������r��t��t���4�4��� �a�t�j&�fm�m�;����/�u����M;K�~G/����"�2j!�a�Z�6_z��)2���/,��6m������N+
��4#��\o
��G��Q�6�)h:|�%ef��z��y)f��b������x)>��Rz�4��<�\��K1��e���-�[w/�C�������+�b��^J�Z����t�n�i���X������,�sW7��4�M����m���^J�|�3���n���ml��l�e�XRV���n����y����[�M5����D"^�'w@o�yu�6���o�Sb�SS��@�#����$8>	��@�#����$8>	��@�#����$8>	��@�#����$8>	��@�#����$8_ ���-���Bo�yM��MmR��{+za����a��"/�i���-�����g[�n=���/��;��7��:N��M�7�)1��)��-�O��v��bp[�{]�l�K'�8��U�i���i��������2;��";��"���Jo��=��f��M�Y�G��7�[�Mh>h1�l�k�V�7�����UXj.M�j�J����O��.���z�O������!��3|nY��s%���v��)�e�m���n�Z�J�;H3�o�7�1����|Q��������K�{iZi�W��g�1�g;�O��Z��o%�f�������	M-��E�wh���_���1�R�f#A���V��Lo
�C�-�w����n�y�M�b�V��E���l�7���^;V���e������N;�����*��E,�q���w����@�QX��4�e���4��H}�S����o�Mq-����~+���w���}�|����]E���k
6�'��m���C{���yS�����/����v�1�n���m|v��e6g��]�����)�o_/�����b�S7�
��Xz+�kNH�c�I��;&����-#�l�������"��-�w�VXj����S��M2R}�s�M�����N��l��_���H�@���������{	A��f����@M����}�}��5�:��8����*�f�e^���Z�=vH��b�W���E��.P�[������Wak����v��������M��h\����sUp����@���k�k����R���J�jq�=��2������������J���7o����o+�{�$��C�r���C�\��r{��r�c�(��
 ���@�����Q'�Y��>�b�����L3�~p��'���`Ee�}��;��TiK�v�>)�j�x������m���g��{����/����~�n�7�r���y����[�M5���2��*��xS����Y�T|"�;B��������	��@�#����$8>	��@�#����$8>	���T.[j��r����������S��-w@��^E����0+������l�=���>�0[�
~/ ���Y� �6�r�*�������?�|�K��-y��-{��Y�Qc6�R?����~�m}��t�n��b�����74����G�hf�s�1����u�K���{iZi�Wa�%��`iG������J�u77����-��v�y�pK�~���v��W,����2�����%��M;�	���4�.�����q[����Rj�v����AK���R�*+-PV�}l������i��|��^��i��%PZj��
V����w� 7vO�����
��e|�m,�]����}���������zX���si������N���f))��MG���/����,�KW���&+��so�*E���
�q�����6����U`�@�H�����������Zz�A�v���}�hK�q'+��k[�H��gZ�oY��5���
�\g��|o.`kD�hfj���}[�����Jy��Z��7Z�>���e?-��/fys[#>@3K��2���(+�R�%����u����1|�kV[���K�%p��i����;ng��L�\�����A�4��[��o�f����VT����4�����}[�n�6��l�G�������{��>�\Z�7_��FX�k�Xj�C]Zu��������kn��vi��m�5�Y�N;[���m�-�������r�����2Zo��+,��,��#]Z��?���j^�G��H� m	��wk,�'1Z��O-�U#-|�b(�3||��7�"f�)(5��-�fm����R�v���t����Y��XJ��n�����]i�w�S��|�n�ee�b��������?[�q�3KJ��������X�����{���w�b����^����Z��)�h�o�[���4�N���hI9���+��������lks�7O�k��|�l���v��b���c-�������m���Z�����Mw��z$��o���w��z4��Yr�7��Ij��-�:��Z��.�i��p����#jvq���]��C�D�|�K7`����Q�n��G������o�+�����������_i�<^����m��M�����[�p/��2|������~��*�fw�1��
K��i^8_,��;�]j]�����2��3���d�:Y�>�������5^�)�:���;$Yv���6���h�/�����]2 �zuIv/M+M��y��
k���+�����:>����3gi��|f�}�C����k�VRnv��)�7����@�n�����:o���E�J��p.?6���n�[�l�������PKy���o*l�������^*h��4����e��,����i��E�{��G-yd����8��:�$Y����9��Ti?����}S6�@��	�)?NO$�Zf����G�lC�������'���_W��}�og�u�&\lag����8�n:5�����J��+�<��S���^Ri��+�Z���lB��	t�j|F�yvh�d�z����i�lm�f�P��������lvx�/�
�&��������{	A��f����F����lm��<��-����\��Reup������&[�v��5�h{��d��f?���Y��o�ef�u
_s���v�K%VT�)���=���u����{�*\p��}h�6G��	���l;u���SK��+�������l�v>7O����+�+���4����=S\�������y�����l��>;`��uD��~[a�;%Y�6���h�g��i����F�Xb}��2������I��-XQ|�j����R�o'���K+��q���I%�>�g���f�do�����*mI^���'�ZE��\������=��{�9����|�����s6��n�yV��'o�&��+zi��r����������-�������������,{��\Z��w�������������+��k�p�_-������?����
�k��
kw��-�C�[N��>�\��%n��C�Y�6�����O��zS�k��Lo
���|����j^��������B>%F>5%Z�lE��~c���-����}����4/���bI�m��K�����s��uV�����<��������v<i�o��vH�`[3>[������M;K�~G/����4��@y�%w����X���Z��22�*+�g��UV��Lk=��5��>[a�%�ik��T/�������J��g�c'���T��e�YR�%���}��i��J��,��A���5��fe_��.s�G|�"����T�������OZ���,e�nUikV_yV��4���:k�����O����b�nD�b������,���\-�����~C�����F��r+|�~��?���t�*�efY����R�g)��f�W_���+}w�[�Sf�������/*�R�^� ���~��l��lE����M5B `�/���YY��7X����U�I�n�S��4V��]�r�r/�*
n�@i��)��[�M����	��U~�`\�
����.���5$0�da�]�L�}��j����_��a��W�JC�J��2���(+�R��AI���r�RR��0�;K�����_/Z��w[����fTqc�TTX���K��Q>k�7�|�>��M�F|�s�
6��R������t�*,5��y�T�}wn����"�b�-����VgI��nz�����W��_-���/�_J���_�g�K{)������/���n������;��^�hY���,�#��t5�WZ��_z)�����I�����H�����{7����q��E����K�Z�.���i�i^8_�x��v�I���m���4������j�������8��"���{?K���
���������Y��XJ��n�T����_w��1]����
�����������W�nz�[�Z�������m�O>d%S�v���[�Q���[��w����n�y�M���V����c�${�����t��C���>�oM�LA�����6���r�q����K���6��q���&����6�j����Y����^��3O��?�����k,P\�b�e^�K�������l�C�:��|����,>�����e��,�ZCM+�.��>k]�|��K���0��g����^�V��!q%m������u�2��4�����m^���|�����a�q����v<�1P�KK��a��6o�k�����<c�t�@\ �@�[S��t:����'��VB��������
���y�T.[j��r���������X���m�5�Y��s��M�gnk/>�r��k��;��_{Ed���-����=4��v������a�I�����v��W�|�p�u�(��?�^�PZ]����V��L[{�[w��V��\��Sh��k-�[w�0�k��?������@
|�s�b3���_������eP���1�zuI�kOJsi�W[��o��r�e]:�R���^�V����O��7Zr��\W`����%u��2/n���X���.3��eV�`���C�����o�+���������D�����v�U�wg����R+*�Me[��4����Z���l]Q�R~����_��������J�V��`����8�6�\P&D�J�M��t�j&�fm�m�;�����5���1f����*��J���h���k�k�V�7����������u�%���S��n�g�e��=xv��t�}8���y�LC����1b"Y�r�O���s���9�+���(-����=vH��b�����[q��n�k�sN�{K.�B�lm0�:���/,��6m�������VZ]|�[�/=���/��%�k��
<���Y��Z�n=�����4����>_Tiy��d@���K/M+M���d����pu��NJw]��rP+zX+���J��l�$�#&�u*��b�o��L�b�e�e��N}�
�?�����O�d�����Zj���W�+�������|n����oW<Wb_�>��9r�d4�F�[_�;�,���W���{������b���q�;����q�����6��1_�Lo.�C�`�-�[V�Y�m6�&jZi�N$�,��[�vI�S���}vN6�X�n���#&�uJ�������zK�u7K?���y��V���V�h�[&�eg�l��i����F�Xb}��2������I��-XQ|�<���N�v�iVTf6||�{iZi���2N=�r^x�����Yee��>�D�@��jl�X0�x��N��N����~�K��
u
V��[3�d[=�������I���J�YF+/!H�J�Kc��v��Z%W�jk�1��S��'K���%�BR����`/��K�o�~��?e��k3�K�J9r�{��L��w����o{U�;�k
T�^;%��a��W�J'i���Tl�5�~�U�-��QV��+�b�7�!����@B��96��B{dj���h�jl�������_V�	���CJ�};����UWa����^a��|�2N�����s��{onbXSy���H�Q@b�:���-d����\����1b��$e���%L�'$ef��z�m:J����k��y�)"����-���K���q;�ed�����~<W)�laL^'�S�~C�B�	+������{nFy��iD&Vc�h����������;4���/�v��d�u�9���0�!��x��y���OZ���[r���R��KV{���?/�{�*��
sc����1b"Y'���V�d��7��R�*W.�@a�YE��ADRz�4��<�-C*Yj��|K���K�^��w���#]K�����(.��n�{)�O���K�����a��-��~��!����>�gnk/=g�2����pO�h�j�0c~�����e���~y�����~-"�.>�r��k��;��Nh�{�M�	!
(��q�U��C����"����a~Y��o~���ne�vl��&V]��W���OgZ�!��\���U�>N$�h��~�����9Q��I��v�}����7+��#]K�����n�J��b���`��"K�����j��,�kw+x�N�ma������,�sW7O�}�_w�U,��}n��giGcs���'����T}�#��������{����VZ�@Om�-�&��A\����H���.�u����6��6x#��u7��=0��������M�[&Q�C>IL+����s����U��Y+����N�}��9v�����<���%�b������~[{>����S���a�+�|����7����(V���o��w�U�i}ZYF��+�����jl�?e�U������:�������o����*~Zh�������;}���ck�9-���n���v/�Vw�s������q��:G��b�.km�Ge��m�T��.�������:)�v��Qc\0a����g���3������/3�[

�;m�v�%�lc��fk/;������uc�<Qy_>g�k���~��67����5g����,9�mo����nw)��Z�a�X�l!-�@�:.���/k�������X�v������Z�=��Zf�J+�.q���|�U���Ss�U�u������M��'�A�/�M��
�����/���m��T�����q;��p�k���v��W,����2� ����U�=�~����~{�?.�T�X�
�c+�8`3���%����;����o�����O��*��f�+J��f�W]g��|��W����b��R�o�������j{,Z�w����)��cc��u�+���9�z�5�1c�D�N��}��3����f�w�#�;�����m;Y����Sf�����z����������R6Q`G�t}P��g���O�d���m�3���r�nI����.��
@� n�K�Z$�v���:��2K����:�|Y����C��22�*����Q��S�*���&��C,Z$h��9I��k����z����g�a���]���|��a�VU�U�'	�H-E�	�����d���9"�Z5p�L>m��2*���5'�����X��l�I���j6���{������i��X�!�,e��,����y�����R��O�\��:�N-��~����e��-�����<�<W<Wb_�\u>�dQuQ��^�Yn�>S��]vt�����F�#�1��A���'X���-9x]$�n]��/k�����*�Z�y�e�t��R����Q��P}��K>��b��j�����EBZ����Sm�a�R�ZR0K5�ym����5�����XR������M��^x�Rv��q��L�_������b���J�:��~�F2R}�s����`B�vI�j����Xu&
�$o���)������X���^J���������mk��|����|�e��]?8����
~[�����#��#
)�3��r�g�d{���:�]j�1��#jA\�b����
[;�<��X�?]Pg�! �4|�
4���X�QW�������OZ���,e�n^j���+@��&��K,[$T�:?`�Tn�wI�=w�|���OE��s����q�����1C"�E !��	�Yz������9�.�S�b56�Z���u�Xu����
�����l��$�5��k3�K�J9r�{��L
ihQ�`�����m�Ii��u��ac���d���{[{�P+|�������>[�! ��q{4�x�Xkz�����-P\�*�CO�&��RBEu������sx��J�vN�V[�4�������q�����[���G]�����G�$,_���*��U~;��"�?��~w_�-~V����*�y��o-+��O�f�N�.@��O�Zw�+��<�p�Xu��K�`aTi�_�>��:�NJ�]�D�1c�4���X����,���\�,`kQ�m0�u��b-�]}8���0��f}d�W���M(��N�S���k#Q�����l��~����������~-%�����o��@��j��&���Y����@�vm���s2���7��s������R����������jl=lp@pz��r��w�}��uC�1}j�UWaz� ���V��CV2�m��w�	�M��v�1n�5>�qS���>��Q4�)+����f���j�}����T�RQ]?����U�F�����2{gv������O��J�p8��o�����n����U�;ng��L�\����bHH�U��>��}���>�
�k��N��j4O>�/Vc�(�?��������\>���K�n�}z���"���Q]������b����<t���`���vw>����-A�k��;�(�-h,^����F(H��:�+��/k���CJ��bE/O��KG$d��l��!�?���*�Sl��k#y��r{��r;��V���p�����O�a�G��1�He�JZr������@B�������X�
�:��>x;���y����}�cT�p@,�
���[��Km�7���SgZ�G��d�s��(� u�{S�_T��6=u/���o�`���Nhf�R���>����
�����������d�k���Z���W�
��S���E��ZXi��+�������&���������f��w������s�LU���
�|�*��R��#�X�N]��T��&�X�S ��av�1�^JM� ��0�������o�7��U�]-����b-V]}�1��Z(~�%�;�����_n���?��%�bR�DE5��b�"��`��l��v�c�v��7���SPRs�p�����Oi�~cmn������S���g�����t�%�m��A��'@<)�5��j>e�������y���$�ow�Yj��U�0�@����i|���U��W���)���ydj��7�n�&�=C�7V�!2��O�U+,����N���e_5jc+e�bF_kmF���-KC�=7�
�}�M��'���v��J�xG>%F>`��l�7�����y���u���������D>��|���qT�i�!���X��>�St�'>��?�!�Z^����m$,>	�.�HV�m��r������bs+��fv`�;�o+����F��s���>�St�'�t����D�n �(�3||��7�"f�)(5��-�&��Z��V4_�-�&���qkn�-������b��[]���G�D�b������,���,w@���V����
�"C�DD�uW��������Kmz��|��-�>�!�SKii����+v�q�Y�6m,''��8�{��w���{KE����h�"1b�������l�����o��rss�%�i-X��1����wY���1y�|O��
�O��-��m.�-�&F��g���N;���l����W/��������v��'���>j��
k��}��W��?�����^�y���f����km�����?�th*
�_b����������
J���~��O�)�5��j>e����P>���_�������?�x���o����}��G6k�,�����}����'�xK7�1��<�G���s���q�l��96u�T���o��o�)S���>h������M�Yn�������o��1�+����E���a|<k����^z������n�.]��tu�v�A� �Z�h��iHc���>p��s�=���IIIq����v�UW��g����S	�����T��l��=0F�8�@�7��}���v��'���y������TQ��?���V��x���7p����+++��#G�}���Z�s�1����?����?������J/�oO)��_���0�N7�w+���T/�������)o����/����dY���K�_gK�>*����V7
�4�����6�w��)>�K��u���q�,o*��O�S}����O��O��Q}��-�>������k���UNmJ������m���^j��}���6�|�g�}l��wvi�i������
	A��}V�`�����-�fm
���R�tI���~K���0F�8|<��-s�m��u������a;����^�h�{�Oc�o��
�+8���p��f�o���:j��-\��s/rO�5���gK�o�V��[s�����x�����7�Z�4�is6F-{�[��w�)D�1b��!��)((p��n��{���}%%%���>�Z��[^+���������T���l�rD]PU.i����R>o����)�5G�������-H���M@l1��g��1v�
7��	l��!^jM�,���S7m�����S�N6q�D������$�e�s��zS�'�����]��HM�b�GV�����*Od'�����f�I��M�?-��'��.�S������O�k{���T�Z����T����2�Q��|���)�����8����|������>�S�>��3o�i�����Z�e�R-�U�vS��]�5��
�P$�����O�!8��C>E�|"��C>E�|��!�':��T�):��R8�Ot����'>1�����E]d�=��]x��^jM��/���.�i��i��PpH��v��MW
����N��s�Y����9���2m��P�v������-\����~��7�`KC�}���iyyy�aC���W�^m�g�v����{��%#���m��l������


��M��]�Z�z��|�}
�t������[�d�K�m��9��G�.@@����kW����M�6������n�@��������9
i�����������|�M+--u�!j���G�@�a��������Gc��q��5����]�Qwl�~��k'++�N=�TKKKs���������
<��~�i�0a���Oaa��{��6~�x;���l�}�q��@�fZ(U���^�����W/+//��3g��J����,%%�[��x;C����'��~X��Mc�O>��c�����X=��m��w�~��/^l�{�=�������{K����O-jQ�����g3f��V�ZY���]��#���������H���h�"{�������rc������:����c���R|c�$8>	��@�#����$8>	���REE�]w�u6h� ����R�����?o�w��i��|>�����v���[nn�����y��W�^v�EYqq���-�������k��x,
0�&M�Dma_������&N����������w;���\�)���'Ove���E�l����{D\��������GziZ���C���O����]u�U����{K4�2+�Ez���J�g���i�o��r�-[��[������?�a��m�vz����g[ ���D�����v���
W^������|jXee��5j�m\���1�k�������999v�g�kT�/�$��Z�_�Q�S�6��^y�+--����1�f8:�^p�����Md��v*cT����::t,�|�T���2ks�l��K��{��*�v_��<��S>���"){��<��7
W���=�P ;;;0p�������9��V�X8���uuy��_���]�tqi���_���>��F�X�f��|���EEE�l):�/:]����o���G�����|�YgV�Z�-��4�������a��	^��t><����r�7���1���_�3�����������zW�>�U�|��w��;�FU?���o4���{o�5A�|R��7�2+�Ez������3�E��|���;���������vz����v���g���~{�L]������L�8��oU���>80w�\oiT�n���i��Vc��~5tn��ZFy4i���eb�X�~-3j��@AA��F��y���"��3�l���=un}�M{l��<�����::�:hk��m�d��������yI��h��H�7e��"�v�9�������������P���z�Y�~_��<�z�w�{��]��dKC�qe��
��#Gn<�	���8u�U����5*�u2������N:)�r�Jo�4�[���g�a��i��D��f�r��|���?��#���?��Cw1:^��$�9��K.q���R�%����U��|���t�Rw�m��s�*++]zIII`��q.]��
��_�>p��g�<R�T��A���1����tt#�}_7�/��R�|����e�\z8�Y�/����^Wj��~��I���/���>�|�*�'Ov�������7�|��
�(�^��������{��R�4R���5�[����s��qnF�E�=�P�Q�'�\���=;���{�|R������e�[�%��~B�_�T�O�������A��k��Y[��Z�-!���m����.��m��n�i�uF�����7��]$��2+�H�]c���yM�t/���������\ze���Ws������~�q{W�G�]�T��������)S�:� w�o�����&�B7:�����^�&�+�������SN9%����Sy�����^��=�T�_|��J�TX5]���ose�^*�?uUr�v:���W��U����/���A�1|���7!��P�T����?�R7=���p�Q(��cM7��ut^����]>=��5n�D���Sy����Pf%�h��{]�����2d�f�����+���m�p�:fu�j��QtL��;v�|��*�T1�|PMm:'���'�Uq����j�����D{-����Z��9[B�k*cC��4���Be��
w��*��_���c��P��#�<�]����Oc��'�|R�5b���p������\$��1���{��1n����:���c�_��G�U���j��I���\��L�����aS�'["��A\�v���Z�`��U����e]�v��FG}�?������k�����>!�;�<[�d�����?������ZW��o�����}�y)���Q�;��Z�:}G�b������F?��������'^O����l�{��N�:y������v��M�Z����G�y�_O�����U���o_�o�N��=�y���+�������O?�;�0[�x��ZE����u�������~r�[}�~7X���S^��� ���4����/v��7���/���n�����>�>��s�a�\��eee^j�c��Z?������n6�v����
^�l�������G7��v����:v���1m��k�z�uk�cI��G����-�O�;����r�)5�����>�u��q�n?�~~���zs7WYYi��O���|:t��?��m�a��#�9q����������z�9r�>���v?�z����Tfi{k
�d�1�����9URRR��M�Q}Z�t�u����Y����R7����u���~���nCB�M�&h\�������S�zKm>�^��1��GHS�Y���W^)�t�W��XY�r�}���������:��<����
��ZS<�Y[��k�^�7��24��6�lv>����w��������M:_����^{y��h�x/�k��5ZII�;�����a�Y�Y�p���1�~����!���n�s�������5�^ok�2A���0#���ZF��|����|��.�k��+t���fo)�=��X��>��3W���M�4�3g�����5�������|�A������O��i	��t~Z�|�
8p�kD]W*]>���_��)�j�t�5�X�����������������?�t���suZ^(��4v_��<��g��G��-j����\���7����8O�T|RSSm���6g�Wi���_������4�	J'�(������N�:�\��VTT�NR���?��*����nW �.�U0|����U�NX������"*Lt!��>��������7�������������8���\ER<:��\!�����/uU�5f`e�W_}�M�2�m'm3�III�����w�e��u��G��%�\�.���E���>�������BB������`}�>(*��=�OTQ{�i���Y���t�z�����������Qq�T��
*m��n����v[oN�4�����������t����������~��]A/��E�*�T1���|������~�F�]�HOO��v��M�x��7.[����w�y����Mu,�\��]7B���N�
i]-S�.�u��cFx�r,i�����*�u~W����|;��C���z��qv�
7X�������F���y�����w�g��/��q_���,Uv���v���'���n��z����sOWir��'�����p���#Z��������s�����Pe��G

2d�����n"u�u�Y.0"MYf)�ms���n<+��g:�U���:7��^7����2����E{���J�*���C����C�?��PUa�}\�R���	wN�6�9*|����?�mu�<xp���uNR>�|��B�t���U�M�4�U|��D����.�k]��aU����k�y�1���$�����UF�2�]�v^�&�~�5�����������[��C�������Qc���/u�%�vG�*�u�W���h�7eVM�n��K���6����kQ�����5eV������'C��H���Tv����n:t}���+xa�����5���.�&x���������/\�{��5!��`O=���&�����Ov�
5�T���-��S��M��;��$	����	���	����K��2�������6Dy����YM6�,Y����{UoN�&����j����U^���n���Wy,�����[^/59
�o����S�K�{.�����i��;��� ��

:�f��:������%m�������y��g7��QG���_�97��A��g����m`����B���t���f����X�_�S���O?u}�V�f
���:W��_4��������T�g�k��D=���5��/vp��[��5����*p����c@�3�<�
h��)�{������S��z������nU��5����K/���#�B�TK(��_�k�N8������n��'^w���
NCB�P���a�6n7���!xc���)��:�$x3�ql.�:�����~N��>�oH�F��g����7�^x����{��n��?�����K�~�sP�szu���k���_����1��R�u��$4���@�k��9�IDAT�a�q������W?��{����wH�|���k��6���$Y��c`Hh�������Guy�4��r?��iZ���BW���}����s��<RWB:7i�Zo��E�u��Z�!:�)�����5h���J]����B���'u�!�{
�{��M������VKn����kxc����.tonF��)�6�f�5�X
����tN�>��2�YU�j_��<Y_�k�<��{����--|��RG�ZDO��������?��"���{�<�dQ�d=ip��w��/����NGO����`��"�!��{u���j6���z�8DO%(����^
��z�W�%������?��W�t}o"��fz"VO�i����u9��37�x���zi;�9h����n��F���
�{�Yy�e�$�������Q�S�m�'�W\q��<g��.�_=�,�7���0���s�V��������v������`!��J�ir�G}O�E���%��������!j9������A��'vB������'<�����XsOO���z?��#����Z&i_U����C�M�F�?m'u������[:rMu,��)�N�q�!z�_�<u�m��5����:���9N�X
G�}����P�k�g�JC��K�.�i���k�������u�h?��U�V�����vTK������rDO�������M�V_f��dm�>}����c�=�Zs����.���7�����u'U����s���Y��|���O�1�<�$��C��:���N]�i;KS�Y:�t��i;���}C��{o;��s�~��"VB����&�~�}W��t����>�V/��s�����Q�u��D��Sj���C���O=��K��pO�"�@ ��Mj����������s��W^�����'��j��k�����	����Z=����n�U��T�^#�I�
�>P����:?����u�Z�
t�����z�;NbE�����)��u=����\�����_��cS���d����#����t~R>�%�������M�U%�m��cI��s���>
�I��5���L�7(��4����[7�O*g�����o�W���Cu
ui�<��m�3�2��]����
UV�2 ��*RTaW�OPU�l���.M���qU��Y7��!R?���
�������;T����o��P��T���y��E�N�U�<�����c���W��*�t��M�N�#�H	��^���8��S���V���&�j���Q����/�p��>E��Y���P7b��P2��<����z!�������x��Ve����e�]�dcSK�K�Q��Ut���q��Z��nrCT��eU����>�|Re�.@X]�i�n��w�5������J�?����[V��y��g7�K"�����K�R���B��u��Y���T�s(0�D>����P��:W+��s_�
0��u>W�������i��h]+�}����t!�s��)����Z�,��
 ����x�w��P��T�����9-���������?�m)��j�c�s���:�u����L���5���x��(�t�S���'�x����j�+]x���8������Fhm[��/�����t�=z�������w"�Y\�5���+��|;~�xw��������Xr�s����vR�Ze��A���*Dc��\�cW��P�T�T]���Ge��[T���*�4.��vQ��T&��N�^u?��6A���O��L��z���9A���CC:'���=p��I]��B�k���|���s�����nB���]c4v{Sf5����:=x��)u���/o�(t�����(�6i�}U��_����2�^���l]W���D,���
l��T�n����J>���d�
7����P����
�*�u"��S�zBWQj�CO�j]UF��7:������*kT��_���?fU�T��I���\s��1W��d�t@�mW=�Q[��KO��������*DU�'1?�p����ET(��I�^���V%M(U�+��������'����o��]�T,�UD���
=���>�T��X�w�MS�8��#z�Y7��<�g��R��*@Cc��m����������#�j��P��B�������+��'�C��z�Fy�1nB�}D�)�%Q�Li:�i��6U+,}�Z(/����P�5��.C��D=���}.T��'����z����U�)\���T(PV�*�t>��v���m�Jc��[������Y:�+���o�X�~��0U�*������n8�
E�`�ij�C��Eu	du��xj�2K��������7��*��{����`M!T>h�Q�����i��jQ������~&�Rfm��R<���R����N�N��:�|��*ktl���B�T���E�����N�bU����pt�X����y��*Ce�������WC2:��p��
�	zZ9�=��z���sN���MA�dc��s�uo�)�f���4�H�M]��U�{]�OU"�v����M�������T��zB�]�.��<�{�u�$Q~�:L���Y�4��������'�5��Q�m
)0��*EK]��:��6|�ZT������BM75�Y�
�**�d�*�uC���
Ub��G�*�4_����=��.E�����[�zj@����:�P	�m�� T�v����J�P�FsQ���p�v=���hU���R���Sy��D���Z�T���T��<�:!*�5(��oz�WzBD��c]��ca���FJ�]���p��
yu��|QE��e�(���������P*/4/D]L(Hrn��TOt(/U�����*���lo.�$����HOUzS���Jy�~=	��K���q�m�|P A�Xy��T��TQ�V>�������V�K�	m+=���l����f#�2����K�gz"M�*�%�Y���?*p���ZO��2N�f�������s�;o4�� ���0�j�2K7�� �������O���\��+�[E��*,k����[��D)���k��
]W*��
	��U)�T�s�*m�9��d����j��g"���'u�����R7(�V���E��}Z�F�cH�Pk�����Y[{9MM��:t��Bg*'We�����hzm���P�W���K]�6�cS��1]���UX�t�l;���O�k�>Qy����no������=��}����:��|��t����o�@����+_(��4�������t����C�jM�:��C`��QmMu
��jQ�K�)�Pa����"V��*����*���*UTq�}U��I7=�����T���s��i�����NT�Y��N7����3����*�T�[�����<Pw>����@��@V��*�-Z���V>h� �M��I��*hByX�n`/��b�U���G�f��0��Vz<���0Q!�V�gC/5�Ve�*P����C(�K��%��� W��
l�-���q�B[�*8u����5U�W/����:�My��R��)������	&xK��_���I�pOo�"T���Qm�Xw,�K{�JN����P>�]���L�\(�K�c�>:�k��8���E���6V���%��P��U-��R������)D������G�{�#t��N�Iy$�����R�@}kk�Qu����L1���a�5B����*��?1)�Rf��ciK���R��Zh{k����yU>)?j�PE`j����:w�!]wh_�M�P���
.h~�sK��Q�3����U�!<]�U��>���NO���n]�kP��*�����1VW0!�]����"=6U��zZ�fu�����L��*CU�*M�[�H���7�G*�5fV8*;t-j����M���}��K��P���um�`�Z�kZ��u��(�����#P}��%t�r�UW��h�/H�z��|����'1uB���|u��U������*�u�S��NB*��$�
=����*hU!�yz�6���!��P��zW���������x��ZT�&@�Ow�*�B�j�[�pB���U���P�+z"Zr*@�/��b�Wm�P>�r�a8*8��A�x���������	]d�=���)�K�G��
M
���R����9�ta����%���u|��r]�)��cB/��.��|]Bu������h<��n���.pmW?�=�t���F��|����h_���^�s^�Cm�t,�G������\���n.�T����0Q�h�Wew�"�6U��0���Z��Pf�K��.��U���G���mm+�!J���*�D���Z��@]c�K�P���6�����S�����,�s�C�@��	����f��b�)(�����%u=���@B�D*�Z��_����R�gyy��	!�����s�=��P�3�g���W]z��L�V����s��)��%t���
w
�|��u�[*u���`=���T���P�����T0OO�+��s�Z�Rq�x*;T��W�j{���r����h�M]wT/3��Tf���yTe������,�m���r7=t��\���������2�����K�Q���[��g���N��U]��~Hy[�8��XG>hQt����U@h|�p��$V%d���u#�'qus�J��S��
g����T��H������z�UZ�i��T��{�'��i\���VM�/���&�8	�Q��P%Yuz:CO��*aBOK��XPw)�|Q�zrC��I�*Z_T���X���*k����
�PE\��S�zb8���'�t3j���o��/���o����]�����������C��@���P��!Z�7���{
��S?�`]��#]�j?����:=E��7D�](���XRwR
�������I��P��P���6����*TI���R}��j<"��Mk?���=��rB�@�����6���}BO�����1���~�������\��.���W�Jx��u��ZVi9
j��~:w(�n c����ym'm�zJ�6���Q��n��k�,���BV�����Rp��>+:�X���>�6�gt����O�2��_��J���zh@���w��(��ku{��*6����:���S����u�yI���2\y����'���2]�p��S��x�M�C��w���PE��:'�u��'�U�h�����P����T��FQO�GSq���xR��cB�-��%��k��G�2-�cS������Ke��N}��R����*�m'�^����M�k���aj�2����2���jc�%��Z��k��s��'E�r��Zz������:���X������}A���9O��X��w�}�p����L�0A5B���G{)5o��v�C����m����������~�~7x��4i�K���W^q��������9�������2e�7���i����>��
���o����w��%����z��c��U�����?X����Cy����V^�V^^5j������zs�
6�7(��o�n��5.=���{�7'(..\r�%��u�Y���7n����,^��K��?�O���(x�^hxs�_�x���EEE^j�by,�@�b�}���m��@ x�^ n���{��S%x�^���~��g���������z�����W����e�]�����?��_B4��'�p��H��XK�������z]y�����Ron 0v�����:���/����������w�����Y�ti����v��},tLUVV�|�M���q��#
�^����V�=���wD�/����=�t���5�Y�������_s������7�}��E/���&Y�~}����v�QeL�ci������<�������*((�s�9n����Z��u����#Fl<?�Jh?�v
�o�'��7�x��;�����eVK��k�����^W*oB�R����@��������KG������w���O�St\F"t�h��L3��u�?�K]����=�����~�1�����<]�T�~C��D��zY2o�<�=5Oy�<�OC��cI�h+V��RQ���k�cA���E�f�����������,O{l�Ee��N�����&��v�F�{1]�����M�9'�tR`���.�>
mo���5���=�$T��ut}R��(eV���W:O�8�/�>�����9�;��i��dKB�q)���4t����n�U�h9U�����wo�Y'�P���C���]��NUzj^������W��{���}�n���z(.��6��U��Eu�S�m]���
U�i�����U���Fi�(���w��1��]	��A�o�^����O���e�?���7�B� ��6u���9�rss�
r��]�CT���������_W�
U�?�~��x���O?}�6������v|�������cI����mUj���I�K
U���I]�������K�U�����=?*�wZ����p��<���K%e*�P�ir�����`����tyP��I��L
�B$���M�td2�Tc\K��*����$N����w�u�}�������y�}�Zk_��������w�s���S���}m�s��_�����g��?�������[�sD"���N�$�>�^S�U1�X����O�����������������D�I�����}C��W�K�sdw������t�*�t:�*f���S���F���(�����Yx�=�-�g3�������z������kj_���x�����M���4ve��"��T���/�Nu\{���Tw����/�����vzM�va������c����kz�%K��������sV�rRv�%�D�6l����	�{�(��M�Y����_������������w��G�'����XOv$|pF���"+�����Wy����lz��|��'�p��
��^�IK������0-�5kV��c���'�w��5���R#�s�YsrK��"3���6�����>}��d�	�E�v����o�N����4�H�HP/�D���qz��7��W_{����=����z,�XRO�~������z�oU`���L�����$�A?`�M��0��$~���_���r����)QU������*UJ�x�R�O"Q��S%`<���#2|a�������s�~z=���-���w��ca9g��=�������o���C��MNn������)�����?�������s�F����c��5i�$=zt�����~����_���]������d�����L^�W����Tv�,u<���[�,����+��T�Y���b&��7����I#,7���Np:�KQ����[�q���O��,X�u}*�}���9�S��T���/�r�]@u�������}��������9�y�������w��.���Zf9)o�Y����rK^����s��X�K�sV~��9=Nf������q2��?���W��iE� �H�D	��#�q$|"��@����8>G� �H��5h� W�H�p�B�����U�X�n}��u_|��m�[�~�{��\��Um{����-[lo������'��-I��G�k����k�0����#3�;v��{��7\��]�2el]��������g�}f�$_n���o��~���ooe��eK7w���V�<x�����'?������g7���K/�����r��/�t��z�k������OcKOP=�|���F������v�����n���n��aV7z��Ju���+��v�'O��jj��1c��Y���E��]���[c[9�wU���o��us�V�������������i��n6lp���o,N�O��TN��V�o���6m���cq��w,�}�>���������,��X����C�����N|*��;������wow�����+W�����D�X�w������;�T7�#���,l��=V�z~�X�>}�I������ G�������*W�\9w��W�dI�5j��W��5|iY�V��9z|�u��������*U��������������yjXS���]��������|�O�5�}�x�	��ysk,�^���oZZ�0`����~f��d�q�F��W/�n�:K�����]t�E����?��;���-[����S�1/^�:t��:u��������j�R-Y��^3L���H
�J���^��-]���p�
�:J���?u�����Q��Tgj�y����*�#���������y��ge�F���?�bD
^�7�}��W������>�5j�F�a��Kg�������3g�����T�R�h������������W�f�l�����k������g,i?Q#������\
�={�t�;w��@���Xu�P� |>�9S��}c��	�������>��O�����X���yJ,�$���m�6o���}�]���e�K	�W,U�P!KJ��)��c��O>q���Eu�h�"�%��X����@�}�Q��������;v�n������g�J�
�T����k���Gm���N���o��?�m������+HII	6l�`�D�����{���S�`�����A�j���R�JA�������`��5A�j��v����m�m�
{�1{�^�z���N������[�n�r���o������s����G���]�l������Z�~���Y���y��^
du��_�>�Q��m���9sbk����#A�~��y�o=0`�=~�������^�:�W���WK�.�--�RSS��6q��xy>|����k�.]�t0~������Wy��U�S�L���R���gO��uk�?�m�6��u�-����b�������rK�i�&[/*��}����8��X�:��sO����Z��������=
�35�����7��x]�^��\����7���� b��|y{Z��e�x==����5'���k�b)]~���������{�������i�`����5���em��	v��M,�#|9�^��u�)5t;��������#Z=?��mk�vE��=��?��zuN�:�Fr����tY�jU�������zO�k���t�Mn��Mn�����'z�j�J��u��������g�G4JE��x��s�����M#�i�����T�R�����{)^���������/�lu����K.����z;:�zUkz��T�V�zS���e�Q
������=^�f�����Q�^���������Fi
�������G?rw�}��V��d�}3+��~��Q7m�4�����c=��/��M�7|�p{�XRYK���ow������+f7��b)%%��F�����H6���y���my~��h�����s���5���k�^ZZZlM�w����C�ltI�J�l���Ot��Ia��������d�_���:���un�4���I������~:�����bIq�c�K'��XR�j���W��<��|`��?���#�4�Q��K�L,�^�7-���y5h�i��@��Jd�����A�6�YD
6��CS��AA��^
�!��j���m��SC��G?��NJ�(a��9�_{�5K>yj��5k��8qb��FaW�rew�e����5���E
��^zilM�+����]Sh�7����]�Z���_�@���{�Y}�^��:S����ZTGz5�h��3�<c��c�9��w�n�!�v�m�%�A
��*'L��*��jtS�e��Mc���I2b�`���?�A�Q:��?K�\sMli:M���_���^�h��w~����i]s�����7h�����GS$*y�,��XR�]������o�<���s2���OY��3��Z���S$������w��O�*1�zS�*a$����3��]D�����4��A�[�������UBH�C,�	@����0]�X?�u����.��Bk4V�M?����V��*���z��'�~���j��~�Vc����?t���/�QT#W�P���B�j,
'���3��z��D�F�d�7�)���/���������E|ow����O�1���_TW�[5��5�`��Ca�{������ofH,$��R�%L
k���bC	�D�p���+���o�n�����rMtL�	]�"Q����T��%%p�#�D��Q=�Z(J@�=t��^x!Cch29�b��.�:���}�Z����pb!Y�g,���Le�}^e��#z���l�H,?�C�5%��(��b�d�Kz-%vt�7_~�FY)����c%W�R)I��b)�H�
�;��)c�J>��@�k���x�~���}5����~���@�Q��oP#���a��a6�H�-�!N}���5��F�9��p��#�6�w�������j\Q]���H�Qj��:5����P�:�s<5��^���~�[5j��/��j�8p�=��X�
�����3�z�+>T�Gb2��X�+]�|�����^�����?lj#�������ZA��h*��������r���Vg�g%R5�)N-Q,)���P=)q��$*c%�hP=)��Q>�Uo�7�������}������t���U��/����UZ�K�C�P�����@�����To�a{��k��h���%�(�55�'����05*�af��y�`3{�l��gOk��4f��us����m����D�*j�]sA�����F�-[�X�g���QO]5�����W�7���49r����O�M�lJ,��
��x��x�	YS,������3��@�H���;�4��=��c�,)���+��N�:Y��Z'�3-G�
2��:JHh*��^K����Z
�J������Fv����B�'�T�J*h�����(��c�bN��cY��?�����QqJ�it�����nJv+��k%i�b���G,�	@�i
1�OE��\4�~��{A�!@?����5�h�/�6�vjd�tj��:�����H����5��Z���^���h��_>L#7�����^�_�\#�����=�SWe��I�������C5���;�nz��g��o_l���V*]�O�����S�@��Q�#�N�.?Q"�Z�G����%5�j4����4i�m�kl(a�������X�	�|�F�ZX�|���e�*�����bCq����R�jU�WBA�����#_O~kf�R��KJ�jZ7���J��/]�I��S�G������.���B,�	@��^���o�[�N�5��'����?����c_
�������������F��iC���������O�-I�^�jl@z�u��?��O�-��F�b��z��F��h�/5r��Q
<�'5R�w�Fqi��F"���w��������}"��^�j{���6��aK����:�t��^��%�$
�����q2�[=/��)�t�
5\+A��f}�(��?cI
���7w�{�>i���E��tc8!/������Y�p�}�����^��_����4"D�!�r./��s��Cq2�|��p=�k
�u�����t�G�X�=>�\S���o��~�kj.�p�x���	2d�k�T)���������������p#����F���]�%|ag�U����[�i��"�����U]�S��-���f���y�����~��Y��K�.v
�0����]�Ee������5���;y�d���������.����)S��\��^�j�Q�A�Aj�QCx2�����t�����7ri�^�x��l���=b��Q(���*n�#4%���C����FI��%�4ROS#��{�1�
�S}iZ*%����������3��`�����s/��b��3��Cu+�l�/��l�K�����c��	�<5rDT?z��}��g�dA�K9��X��(i�s��%:�)��s�����Vu�Kyp�r����>��� 555�$�o��6x�����?�m�Z�j�Z�
�T�b�K�.L�2%8v�X��6l�����v��w���bk�`���A��Mm]�
�-[�����mz�![~�����c}}.}����c����={���f�q�F+����Y�fA�F���v���;w��m�N�6h��x�.Z�(�����~���6r����t��-�����-[*T�e�L�l�@1���b*��K/�/���G������p�&����Gq��T�&�k���S�N��Qi����e
6L�����>[�.]���~�����?������K���/��W�:����;��
���%���n�����3'�����>[s��� ci���A�6ml;������x��+W.X�bElM:b)w��]���{����z�riiin��9����6-�m���N%L=85����ox���2QO^��
����=k�,�6L�
��j���]���������)�4�F�e5E��P��Q-Z����?�����L���p$sow���R�J��T�7o�Fid�F�i�`��/�a=z�h{o}6�(�������]�@���m]@\�t�>}�������\id���6m���(���j����={v����K�jJ#K�����ov7n�z�1W=���h�It�M6��X�v��Y,�NJ�.m�;ou���W�;����X��������4�)))��Fl���b)��K����Ga�F��;�hD���S��;E����
�b�@����8>G� �H�D	��#�q$|"��@����8>G� �H�D	��#�q$|"��@����8>G� �H�D	��#�q$|"��@����8>G� �H�D	��#�q$|"��@����8>G� �H�D	��#�q$|"��@����8>G� �H�D	��#��h����H�".55���1���Y��)S�u���m��5��s�}��<x��]��m_�bE��[7�j�*Al+�f��i��|����t}�����km���k�9��u[�lq<���Z�j��}��w��c�b[�>P^}�Uw�}����;�U�^�<x�������>}�k���0`�KKKs�Z�r�K�v�>��k���1b�;r���N�*U\JJ�{����W_}e�<%|� ��k�����~K���W���Q��-\��5m��A%K���-W���o�����	2$�D	(S�Nu�<��[�x�{�����I��E]�V�^����o�����[�f���n���n��E����v�
r��M��)_���U��������n�D����{/������gH}�����T�lYK8M�8����?��O��d�{�����cm��!��M�6�m���h�?��>�lw��QK�(9��O��sgw�9��zM���aC7|�p{���_|a#����o����4�G�z��k�n��&�i�&�w���Zg���?����[��{�����Cn���R�J6�G�'�o������;�3��J������naJ�h�5%]�*V�XlM:M�����}�]�y�f[V�N�zM��4%o�R�FI%x�m�f��������:)^��+U��[�t��,��sg|�6}�!C��H$%�D	(�F�D��G'(��{�nK]q���i4��W^i	�����2m�Q>���F����-�s�u��j���tnk���uz�;��O�
l�\�:v���:�,��o_K ������e�,I �H��D���Z?���s�����k��n�6�F�h�O�
,�s�5�XG����mJ��<Z�D���C�`�w��w�5{�@<x��*�\��3f�;|�plkQB�� i�G�\z��v����p�
���n��v����Z<�����r��W�D�����=��������{z����n��z���-��DR�=\jjjlkQB�N�2e��H]��O�������-[l;���4m��`�������h�*U��p������km����Z<Z��$��=���6h����|���������D	8M4U[��umt����nS�e����y�2\G.��bW�V-�n���s���;�#x��QrG�vf��a	m�����+W�������{�4m[��EmZ8�E�N�b���ut4Zg��n��I��Kn���6�F�t�bIOI�o��F�8�F��/_>��Y�H���5�J��5���.��r{<n�8���/�#G�����V�����o}�%J������FJ�<��3����,Q��uk�^M	M�6`�Ke���h{����t��4h��U�\���4E����k��)��=?���m�O����1c\�N��w�a��-$|�4R2�}����7�t���w%K�ts��q{��u={�to�������+^�x��4J�f�����~�����5{������-k��k����5��uS�GS��X�����6m�;v����Kb[��"��
@d1� �H�D	��#�q$|"��@����8>G� �H�D�s�8O��jRrIEND�B`�
v1-0001-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchapplication/octet-stream; name=v1-0001-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchDownload
From a46508514d5b7fbf7e526f41e89373e0244f85f4 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 20:17:39 +1200
Subject: [PATCH v1 1/2] Add memory/disk usage for Material in EXPLAIN ANALYZE

Up until now, there was no ability to easily determine if a Material
node caused the underlying tuplestore to spill to disk or even see how
much memory the tuplestore used if it didn't.

Here we add some new functions to tuplestore.c to query this information
and add some additional output in EXPLAIN ANALYZE to display this
information.
---
 src/backend/commands/explain.c                | 37 ++++++++++++
 src/backend/storage/file/buffile.c            |  2 +-
 src/backend/utils/sort/tuplestore.c           | 53 ++++++++++++++++
 src/include/utils/tuplestore.h                |  4 ++
 src/test/regress/expected/partition_prune.out | 60 +++++++++----------
 src/test/regress/sql/partition_prune.sql      |  5 ++
 6 files changed, 130 insertions(+), 31 deletions(-)

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index c0c73aa3c9..4f85b0af11 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -119,6 +119,7 @@ static void show_sort_info(SortState *sortstate, ExplainState *es);
 static void show_incremental_sort_info(IncrementalSortState *incrsortstate,
 									   ExplainState *es);
 static void show_hash_info(HashState *hashstate, ExplainState *es);
+static void show_material_info(MaterialState *mstate, ExplainState *es);
 static void show_memoize_info(MemoizeState *mstate, List *ancestors,
 							  ExplainState *es);
 static void show_hashagg_info(AggState *aggstate, ExplainState *es);
@@ -2242,6 +2243,9 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_Hash:
 			show_hash_info(castNode(HashState, planstate), es);
 			break;
+		case T_Material:
+			show_material_info(castNode(MaterialState, planstate), es);
+			break;
 		case T_Memoize:
 			show_memoize_info(castNode(MemoizeState, planstate), ancestors,
 							  es);
@@ -3313,6 +3317,39 @@ show_hash_info(HashState *hashstate, ExplainState *es)
 	}
 }
 
+/*
+ * Show information on material node, storage method and maximum memory/disk
+ * space used.
+ */
+static void
+show_material_info(MaterialState *mstate, ExplainState *es)
+{
+	Tuplestorestate *tupstore;
+	const char *storageType;
+	int64		spaceUsedKB;
+
+	if (!es->analyze)
+		return;
+
+	tupstore = mstate->tuplestorestate;
+	storageType = tuplestore_storage_type_name(tupstore);
+	spaceUsedKB = (tuplestore_space_used(tupstore) + 1023) / 1024;
+
+	if (es->format != EXPLAIN_FORMAT_TEXT)
+	{
+		ExplainPropertyText("Storage", storageType, es);
+		ExplainPropertyInteger("Maximum Storage", "kB", spaceUsedKB, es);
+	}
+	else
+	{
+		ExplainIndentText(es);
+		appendStringInfo(es->str,
+						 "Storage: %s  Maximum Storage: " INT64_FORMAT "kB\n",
+						 storageType,
+						 spaceUsedKB);
+	}
+}
+
 /*
  * Show information on memoize hits/misses/evictions and memory usage.
  */
diff --git a/src/backend/storage/file/buffile.c b/src/backend/storage/file/buffile.c
index a263875fd5..9255f7d464 100644
--- a/src/backend/storage/file/buffile.c
+++ b/src/backend/storage/file/buffile.c
@@ -867,7 +867,7 @@ BufFileSize(BufFile *file)
 {
 	int64		lastFileSize;
 
-	Assert(file->fileset != NULL);
+	Assert(file->files != NULL);
 
 	/* Get the size of the last physical file. */
 	lastFileSize = FileSize(file->files[file->numFiles - 1]);
diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 947a868e56..24bb49ca87 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -109,6 +109,7 @@ struct Tuplestorestate
 	bool		truncated;		/* tuplestore_trim has removed tuples? */
 	int64		availMem;		/* remaining memory available, in bytes */
 	int64		allowedMem;		/* total memory allowed, in bytes */
+	int64		maxSpace;		/* maximum space used in memory */
 	int64		tuples;			/* number of tuples added */
 	BufFile    *myfile;			/* underlying file, or NULL if none */
 	MemoryContext context;		/* memory context for holding tuples */
@@ -238,6 +239,7 @@ static Tuplestorestate *tuplestore_begin_common(int eflags,
 												int maxKBytes);
 static void tuplestore_puttuple_common(Tuplestorestate *state, void *tuple);
 static void dumptuples(Tuplestorestate *state);
+static void tuplestore_updatemax(Tuplestorestate *state);
 static unsigned int getlen(Tuplestorestate *state, bool eofOK);
 static void *copytup_heap(Tuplestorestate *state, void *tup);
 static void writetup_heap(Tuplestorestate *state, void *tup);
@@ -262,6 +264,7 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->truncated = false;
 	state->allowedMem = maxKBytes * 1024L;
 	state->availMem = state->allowedMem;
+	state->maxSpace = 0;
 	state->myfile = NULL;
 	state->context = CurrentMemoryContext;
 	state->resowner = CurrentResourceOwner;
@@ -420,6 +423,9 @@ tuplestore_clear(Tuplestorestate *state)
 	int			i;
 	TSReadPointer *readptr;
 
+	/* update the maxSpace before doing any USEMEM/FREEMEM adjustments */
+	tuplestore_updatemax(state);
+
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
@@ -1402,6 +1408,9 @@ tuplestore_trim(Tuplestorestate *state)
 	Assert(nremove >= state->memtupdeleted);
 	Assert(nremove <= state->memtupcount);
 
+	/* before freeing any memory, update maxSpace */
+	tuplestore_updatemax(state);
+
 	/* Release no-longer-needed tuples */
 	for (i = state->memtupdeleted; i < nremove; i++)
 	{
@@ -1444,6 +1453,49 @@ tuplestore_trim(Tuplestorestate *state)
 	}
 }
 
+/*
+ * tuplestore_updatemax
+ *		Update maxSpace field
+ */
+static void
+tuplestore_updatemax(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		state->maxSpace = Max(state->maxSpace,
+							  state->allowedMem - state->availMem);
+}
+
+/*
+ * tuplestore_storage_type_name
+ *		Return a string description of the storage method used to store the
+ *		tuples.
+ */
+const char *
+tuplestore_storage_type_name(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		return "Memory";
+	else
+		return "Disk";
+}
+
+/*
+ * tuplestore_space_used
+ *		Return the maximum space used in memory unless the tuplestore has spilled
+ *		to disk, in which case, return the disk space used.
+ */
+int64
+tuplestore_space_used(Tuplestorestate *state)
+{
+	/* First, update the maxSpace field */
+	tuplestore_updatemax(state);
+
+	if (state->status == TSS_INMEM)
+		return state->maxSpace;
+	else
+		return BufFileSize(state->myfile);
+}
+
 /*
  * tuplestore_in_memory
  *
@@ -1513,6 +1565,7 @@ writetup_heap(Tuplestorestate *state, void *tup)
 	if (state->backward)		/* need trailing length word? */
 		BufFileWrite(state->myfile, &tuplen, sizeof(tuplen));
 
+	/* no need to call tuplestore_updatemax() when not in TSS_INMEM */
 	FREEMEM(state, GetMemoryChunkSpace(tuple));
 	heap_free_minimal_tuple(tuple);
 }
diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h
index 419613c17b..3d8a90caaf 100644
--- a/src/include/utils/tuplestore.h
+++ b/src/include/utils/tuplestore.h
@@ -65,6 +65,10 @@ extern void tuplestore_copy_read_pointer(Tuplestorestate *state,
 
 extern void tuplestore_trim(Tuplestorestate *state);
 
+extern const char *tuplestore_storage_type_name(Tuplestorestate *state);
+
+extern int64 tuplestore_space_used(Tuplestorestate *state);
+
 extern bool tuplestore_in_memory(Tuplestorestate *state);
 
 extern bool tuplestore_gettupleslot(Tuplestorestate *state, bool forward,
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 46b78ba3c4..e6bc3f5c05 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -2886,12 +2886,13 @@ where c.relname like 'ab\_%' order by c.relname;
  ab_a3_b3_a_idx |        1 |         0 | t          |                  |                  
 (21 rows)
 
+set enable_material = 0;
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
-                                        QUERY PLAN                                         
--------------------------------------------------------------------------------------------
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
    Update on ab_a1_b2 ab_a1_2
@@ -2912,23 +2913,22 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
                      Heap Blocks: exact=1
                      ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
                            Index Cond: (a = 1)
-         ->  Materialize (actual rows=1 loops=1)
-               ->  Append (actual rows=1 loops=1)
-                     ->  Bitmap Heap Scan on ab_a1_b1 ab_1 (actual rows=0 loops=1)
-                           Recheck Cond: (a = 1)
-                           ->  Bitmap Index Scan on ab_a1_b1_a_idx (actual rows=0 loops=1)
-                                 Index Cond: (a = 1)
-                     ->  Bitmap Heap Scan on ab_a1_b2 ab_2 (actual rows=1 loops=1)
-                           Recheck Cond: (a = 1)
-                           Heap Blocks: exact=1
-                           ->  Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
-                                 Index Cond: (a = 1)
-                     ->  Bitmap Heap Scan on ab_a1_b3 ab_3 (actual rows=0 loops=1)
-                           Recheck Cond: (a = 1)
-                           Heap Blocks: exact=1
-                           ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
-                                 Index Cond: (a = 1)
-(36 rows)
+         ->  Append (actual rows=1 loops=1)
+               ->  Bitmap Heap Scan on ab_a1_b1 ab_1 (actual rows=0 loops=1)
+                     Recheck Cond: (a = 1)
+                     ->  Bitmap Index Scan on ab_a1_b1_a_idx (actual rows=0 loops=1)
+                           Index Cond: (a = 1)
+               ->  Bitmap Heap Scan on ab_a1_b2 ab_2 (actual rows=1 loops=1)
+                     Recheck Cond: (a = 1)
+                     Heap Blocks: exact=1
+                     ->  Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
+                           Index Cond: (a = 1)
+               ->  Bitmap Heap Scan on ab_a1_b3 ab_3 (actual rows=0 loops=1)
+                     Recheck Cond: (a = 1)
+                     Heap Blocks: exact=1
+                     ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
+                           Index Cond: (a = 1)
+(35 rows)
 
 table ab;
  a | b 
@@ -2941,8 +2941,8 @@ truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
-                                  QUERY PLAN                                  
-------------------------------------------------------------------------------
+                               QUERY PLAN                               
+------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
    Update on ab_a1_b2 ab_a1_2
@@ -2950,20 +2950,20 @@ update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
    InitPlan 1
      ->  Result (actual rows=1 loops=1)
    ->  Nested Loop (actual rows=3 loops=1)
+         ->  Append (actual rows=1 loops=1)
+               ->  Seq Scan on ab_a2_b1 ab_a2_1 (actual rows=1 loops=1)
+                     Filter: (b = (InitPlan 1).col1)
+               ->  Seq Scan on ab_a2_b2 ab_a2_2 (never executed)
+                     Filter: (b = (InitPlan 1).col1)
+               ->  Seq Scan on ab_a2_b3 ab_a2_3 (never executed)
+                     Filter: (b = (InitPlan 1).col1)
          ->  Append (actual rows=3 loops=1)
                ->  Seq Scan on ab_a1_b1 ab_a1_1 (actual rows=1 loops=1)
                ->  Seq Scan on ab_a1_b2 ab_a1_2 (actual rows=1 loops=1)
                ->  Seq Scan on ab_a1_b3 ab_a1_3 (actual rows=1 loops=1)
-         ->  Materialize (actual rows=1 loops=3)
-               ->  Append (actual rows=1 loops=1)
-                     ->  Seq Scan on ab_a2_b1 ab_a2_1 (actual rows=1 loops=1)
-                           Filter: (b = (InitPlan 1).col1)
-                     ->  Seq Scan on ab_a2_b2 ab_a2_2 (never executed)
-                           Filter: (b = (InitPlan 1).col1)
-                     ->  Seq Scan on ab_a2_b3 ab_a2_3 (never executed)
-                           Filter: (b = (InitPlan 1).col1)
-(19 rows)
+(18 rows)
 
+reset enable_material;
 select tableoid::regclass, * from ab;
  tableoid | a | b 
 ----------+---+---
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index dc71693861..2707a475b5 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -688,6 +688,8 @@ left join pg_stat_all_tables s on c.oid = s.relid
 left join pg_index i on c.oid = i.indexrelid
 where c.relname like 'ab\_%' order by c.relname;
 
+set enable_material = 0;
+
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
 explain (analyze, costs off, summary off, timing off)
@@ -699,6 +701,9 @@ truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
+
+reset enable_material;
+
 select tableoid::regclass, * from ab;
 
 drop table ab, lprt_a;
-- 
2.40.1

v1-0002-Don-t-use-ExecutorState-memory-context-for-tuples.patchapplication/octet-stream; name=v1-0002-Don-t-use-ExecutorState-memory-context-for-tuples.patchDownload
From 7da19dc9c76a7a0f08edcb6bbfd60aee959fabc5 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 21:15:01 +1200
Subject: [PATCH v1 2/2] Don't use ExecutorState memory context for tuplestores

Here we make tuplestore.c use a generation.c memory context rather than
allocating tuples into the ExecutorState memory context.  Doing that
could cause that context to become bloated when pfree'd chunks are not
reused by future tuples.

A generation.c memory context is much better suited for this job as it
works well with FIFO palloc/pfree patterns and consumes less space as
there is no rounding allocations up to the next power-of-2 value as
there is with the aset.c context used for ExecutorState.

This also allows us to more efficiently cleanup memory used by the
tuplestore as we can reset the generation context rather than looping
over all stored tuples and pfree'ing them.

Also, remove a badly placed USEMEM call in readtup_heap().  The tuple
wasn't being allocated in the Tuplestorestate's context, so no need to
adjust the memory consumed by the tuplestore there.
---
 src/backend/utils/sort/tuplestore.c | 52 ++++++++++++++++++++---------
 1 file changed, 37 insertions(+), 15 deletions(-)

diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 24bb49ca87..551f0f0a19 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -266,7 +266,11 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->availMem = state->allowedMem;
 	state->maxSpace = 0;
 	state->myfile = NULL;
-	state->context = CurrentMemoryContext;
+
+	/* palloc/pfree uses FIFO pattern, which is ideal for generation.c */
+	state->context = GenerationContextCreate(CurrentMemoryContext,
+											 "tuplestore tuples",
+											 ALLOCSET_DEFAULT_SIZES);
 	state->resowner = CurrentResourceOwner;
 
 	state->memtupdeleted = 0;
@@ -429,14 +433,38 @@ tuplestore_clear(Tuplestorestate *state)
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
-	if (state->memtuples)
+
+#ifdef USE_ASSERT_CHECKING
 	{
+		int64		availMem = state->availMem;
+
+		/*
+		 * Below, we reset the memory context for storing tuples.  To save
+		 * from having to always call GetMemoryChunkSpace() on all stored
+		 * tuples, we adjust the availMem to forget all the tuples and just
+		 * recall USEMEM for the space used by the memtuples array.  Here we
+		 * just Assert that's correct and the memory tracking hasn't gone
+		 * wrong anywhere.
+		 */
 		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-		{
-			FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i]));
-			pfree(state->memtuples[i]);
-		}
+			availMem += GetMemoryChunkSpace(state->memtuples[i]);
+
+		availMem += GetMemoryChunkSpace(state->memtuples);
+
+		Assert(availMem == state->allowedMem);
 	}
+#endif
+
+	/* clear the memory consumed by the memory tuples */
+	MemoryContextReset(state->context);
+
+	/*
+	 * Zero the used memory and re-consume the space for the memtuples array.
+	 * This saves having to FREEMEM for each stored tuple.
+	 */
+	state->availMem = state->allowedMem;
+	USEMEM(state, GetMemoryChunkSpace(state->memtuples));
+
 	state->status = TSS_INMEM;
 	state->truncated = false;
 	state->memtupdeleted = 0;
@@ -458,16 +486,11 @@ tuplestore_clear(Tuplestorestate *state)
 void
 tuplestore_end(Tuplestorestate *state)
 {
-	int			i;
-
 	if (state->myfile)
 		BufFileClose(state->myfile);
-	if (state->memtuples)
-	{
-		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-			pfree(state->memtuples[i]);
-		pfree(state->memtuples);
-	}
+
+	MemoryContextDelete(state->context);
+	pfree(state->memtuples);
 	pfree(state->readptrs);
 	pfree(state);
 }
@@ -1578,7 +1601,6 @@ readtup_heap(Tuplestorestate *state, unsigned int len)
 	MinimalTuple tuple = (MinimalTuple) palloc(tuplen);
 	char	   *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
 
-	USEMEM(state, GetMemoryChunkSpace(tuple));
 	/* read in the tuple proper */
 	tuple->t_len = tuplen;
 	BufFileReadExact(state->myfile, tupbody, tupbodylen);
-- 
2.40.1

#2Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: David Rowley (#1)
Re: Use generation memory context for tuplestore.c

On Fri, 3 May 2024 at 15:55, David Rowley <dgrowleyml@gmail.com> wrote:

(40af10b57 did this for tuplesort.c, this is the same, but for tuplestore.c)

I was looking at the tuplestore.c code a few days ago and noticed that
it allocates tuples in the memory context that tuplestore_begin_heap()
is called in, which for nodeMaterial.c, is ExecutorState.

I didn't think this was great because:
1. Allocating many chunks in ExecutorState can bloat the context with
many blocks worth of free'd chunks, stored on freelists that might
never be reused for anything.
2. To clean up the memory, pfree must be meticulously called on each
allocated tuple
3. ExecutorState is an aset.c context which isn't the most efficient
allocator for this purpose.

Agreed on all counts.

I've attached 2 patches:

0001: Adds memory tracking to Materialize nodes, which looks like:

-> Materialize (actual time=0.033..9.157 rows=10000 loops=2)
Storage: Memory Maximum Storage: 10441kB

0002: Creates a Generation MemoryContext for storing tuples in tuplestore.

Using generation has the following advantages:

[...]

6. Generation has a page-level freelist, so is able to reuse pages
instead of freeing and mallocing another if tuplestore_trim() is used
to continually remove no longer needed tuples. aset.c can only
efficiently do this if the tuples are all in the same size class.

Was a bump context considered? If so, why didn't it make the cut?
If tuplestore_trim is the only reason why the type of context in patch
2 is a generation context, then couldn't we make the type of context
conditional on state->eflags & EXEC_FLAG_REWIND, and use a bump
context if we require rewind capabilities (i.e. where _trim is never
effectively executed)?

master @ 8f0a97dff
Storage: Memory Maximum Storage: 16577kB

patched:
Storage: Memory Maximum Storage: 8577kB

Those are some impressive numbers.

Kind regards,

Matthias van de Meent
Neon (https://neon.tech)

Show quoted text

On Fri, 3 May 2024 at 15:55, David Rowley <dgrowleyml@gmail.com> wrote:

(40af10b57 did this for tuplesort.c, this is the same, but for tuplestore.c)

I was looking at the tuplestore.c code a few days ago and noticed that
it allocates tuples in the memory context that tuplestore_begin_heap()
is called in, which for nodeMaterial.c, is ExecutorState.

I didn't think this was great because:
1. Allocating many chunks in ExecutorState can bloat the context with
many blocks worth of free'd chunks, stored on freelists that might
never be reused for anything.
2. To clean up the memory, pfree must be meticulously called on each
allocated tuple
3. ExecutorState is an aset.c context which isn't the most efficient
allocator for this purpose.

I've attached 2 patches:

0001: Adds memory tracking to Materialize nodes, which looks like:

-> Materialize (actual time=0.033..9.157 rows=10000 loops=2)
Storage: Memory Maximum Storage: 10441kB

0002: Creates a Generation MemoryContext for storing tuples in tuplestore.

Using generation has the following advantages:

1. It does not round allocations up to the next power of 2. Using
generation will save an average of 25% memory for tuplestores or allow
an average of 25% more tuples before going to disk.
2. Allocation patterns in tuplestore.c are FIFO, which is exactly what
generation was designed to handle best.
3. Generation is faster to palloc/pfree than aset. (See [1]. Compare
the 4-bit times between aset_palloc_pfree.png and
generation_palloc_pfree.png)
4. tuplestore_clear() and tuplestore_end() can reset or delete the
tuple context instead of pfreeing every tuple one by one.
5. Higher likelihood of neighbouring tuples being stored consecutively
in memory, resulting in better CPU memory prefetching.
6. Generation has a page-level freelist, so is able to reuse pages
instead of freeing and mallocing another if tuplestore_trim() is used
to continually remove no longer needed tuples. aset.c can only
efficiently do this if the tuples are all in the same size class.

The attached bench.sh.txt tests the performance of this change and
result_chart.png shows the results I got when running on an AMD 3990x
master @ 8f0a97dff vs patched.
The script runs benchmarks for various tuple counts stored in the
tuplestore -- 1 to 8192 in power-2 increments.

The script does output the memory consumed by the tuplestore for each
query. Here are the results for the 8192 tuple test:

master @ 8f0a97dff
Storage: Memory Maximum Storage: 16577kB

patched:
Storage: Memory Maximum Storage: 8577kB

Which is roughly half, but I did pad the tuple to just over 1024
bytes, so the alloc set allocations would have rounded up to 2048
bytes.

Some things I've *not* done:

1. Gone over other executor nodes which use tuplestore to add the same
additional EXPLAIN output. CTE Scan, Recursive Union, Window Agg
could get similar treatment.
2. Given much consideration for the block sizes to use for
GenerationContextCreate(). (Maybe using ALLOCSET_SMALL_INITSIZE for
the start size is a good idea.)
3. A great deal of testing.

I'll park this here until we branch for v18.

David

[1] /messages/by-id/CAApHDvqUWhOMkUjYXzq95idAwpiPdJLCxxRbf8kV6PYcW5y=Cg@mail.gmail.com

#3David Rowley
dgrowleyml@gmail.com
In reply to: Matthias van de Meent (#2)
Re: Use generation memory context for tuplestore.c

On Sat, 4 May 2024 at 03:51, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

Was a bump context considered? If so, why didn't it make the cut?
If tuplestore_trim is the only reason why the type of context in patch
2 is a generation context, then couldn't we make the type of context
conditional on state->eflags & EXEC_FLAG_REWIND, and use a bump
context if we require rewind capabilities (i.e. where _trim is never
effectively executed)?

I didn't really want to raise all this here, but to answer why I
didn't use bump...

There's a bit more that would need to be done to allow bump to work in
use-cases where no trim support is needed. Namely, if you look at
writetup_heap(), you'll see a heap_free_minimal_tuple(), which is
pfreeing the memory that was allocated for the tuple in either
tuplestore_puttupleslot(), tuplestore_puttuple() or
tuplestore_putvalues(). So basically, what happens if we're still
loading the tuplestore and we've spilled to disk, once the
tuplestore_put* function is called, we allocate memory for the tuple
that might get stored in RAM (we don't know yet), but then call
tuplestore_puttuple_common() which decides if the tuple goes to RAM or
disk, then because we're spilling to disk, the write function pfree's
the memory we allocate in the tuplestore_put function after the tuple
is safely written to the disk buffer.

This is a fairly inefficient design. While, we do need to still form
a tuple and store it somewhere for tuplestore_putvalues(), we don't
need to do that for a heap tuple. I think it should be possible to
write directly from the table's page.

Overall tuplestore.c seems quite confused as to how it's meant to
work. You have tuplestore_begin_heap() function, which is the *only*
external function to create a tuplestore. We then pretend we're
agnostic about how we store tuples that won't fit in memory by
providing callbacks for read/write/copy, but we only have 1 set of
functions for those and instead of having some other begin method we
use when not dealing with heap tuples, we use some other
tuplestore_put* function.

It seems like another pass is required to fix all this and I think
that should be:

1. Get rid of the function pointers and just hardcode which static
functions we call to read/write/copy.
2. Rename tuplestore_begin_heap() to tuplestore_begin().
3. See if we can rearrange the code so that the copying to the tuple
context is only done when we are in TSS_INMEM. I'm not sure what that
would look like, but it's required before we could use bump so we
don't pfree a bump allocated chunk.

Or maybe there's a way to fix this by adding other begin functions and
making it work more like tuplesort. I've not really looked into that.

I'd rather tackle these problems independently and I believe there are
much bigger wins to moving from aset to generation than generation to
bump, so that's where I've started.

Thanks for having a look at the patch.

David

#4Dmitry Dolgov
9erthalion6@gmail.com
In reply to: David Rowley (#1)
1 attachment(s)
Re: Use generation memory context for tuplestore.c

On Sat, May 04, 2024 at 01:55:22AM +1200, David Rowley wrote:
(40af10b57 did this for tuplesort.c, this is the same, but for tuplestore.c)

An interesting idea, thanks. I was able to reproduce the results of your
benchmark and get similar conclusions from the results.

Using generation has the following advantages:

[...]

2. Allocation patterns in tuplestore.c are FIFO, which is exactly what
generation was designed to handle best.

Do I understand correctly, that the efficiency of generation memory
context could be measured directly via counting number of malloc/free
calls? In those experiments I've conducted the numbers were indeed
visibly lower for the patched version (~30%), but I would like to
confirm my interpretation of this difference.

5. Higher likelihood of neighbouring tuples being stored consecutively
in memory, resulting in better CPU memory prefetching.

I guess this roughly translates into better CPU cache utilization.
Measuring cache hit ratio for unmodified vs patched versions in my case
indeed shows about 10% less cache misses.

The attached bench.sh.txt tests the performance of this change and
result_chart.png shows the results I got when running on an AMD 3990x
master @ 8f0a97dff vs patched.

The query you use in the benchmark, is it something like a "best-case"
scenario for generation memory context? I was experimenting with
different size of the b column, lower values seems to produce less
difference between generation and aset (although still generation
context is distinctly faster regarding final query latencies, see the
attached PDF estimation, ran for 8192 rows). I'm curious what could be a
"worst-case" workload type for this patch?

I've also noticed the first patch disables materialization in some tests.

    --- a/src/test/regress/sql/partition_prune.sql
    +++ b/src/test/regress/sql/partition_prune.sql
    +set enable_material = 0;
    +
     -- UPDATE on a partition subtree has been seen to have problems.
     insert into ab values (1,2);
     explain (analyze, costs off, summary off, timing off)

Is it due to the volatility of Maximum Storage values? If yes, could it
be covered with something similar to COSTS OFF instead?

Attachments:

pdf_latency.pngimage/pngDownload
�PNG


IHDR��5���9tEXtSoftwareMatplotlib version3.8.4, https://matplotlib.org/%#u	pHYsaa�?�iwIDATx���w|S����I�4��BXh"{J-E��� ���^Z*TPPd^���"\�p� ��� TpQA�"CdKi��^���4�I��I�2>��+��'''�I�����#	!�����k(�DDDDT������ ��a$"""�2�DDDD^�������0y@""""/�HDDD�e����� ��a$"""�2�DDDD^�������0y@""""/�HDDD�e����� ��a$"""�2�DDDD^�������0y@""""/�HDDD�e����� ��a$"""�2�DDDD^�������0y@""""/�HDDD�e����� ��:w�$I�����)F�����y���L<����$IX�xq�����y�����;�DT
@�j�W��$I�M�����o��	���)��{�n��|}}�;��o���\�R���oS�N��s\�v�����t��5�n��X�4i�o��i�����?���I^����f������)D^���@�
������X����e��u�V=z����~�?�<n��V��z\�r{�����3�h�"|��g����+=��N�:��9��]�G����-��l�EEEP�T�����t��=111�����c���`0��M����b����<yr���7+,,�����D�z�H`��������'�@XX-Z�/��#G����������Z<���#���{0|�p;vQQQ����*���!�IVVBCCk�x���P��P(\��E���b���5tS����_%�`���={��}�v����#;;���^��a���0`BBB����~�����~��'//'NDLL|}}�����8x� c%����������g��:[cG����@\�p�F`` �7o��K�~��7�}��@��-�v�Z��\�~�'OF������`8G�����{7n��V��1c�v��ak`AA^|�EDGG����������/!,��$	&L��M���S'����c����m[�����^��K��m29s�z�!4n����������W_Y�4L`��u�>}:�7o���V�����=z4BBB���d>|��s�l\����`0`������#4
"""0~�x��q�b���<��oG�^������������v�j�����Cbbb��cKii)f����={"$$�����k�.y�s���i�����g����Y��}N�8�|�7�F�A�^��y�f��2}�?��RRR��iS�����9L����F�~����`�z�������3�R�l>��'�Dhh(���z/�\	 �
�O��������>???|��7V����������|������;�����3g��7�@vv6���n���O�������e�0|�p�����<y2���p��q�����n���I�&�������W;P��c��������o����L�0�W�����W/,X�AAAHJJ��g����M�0x�`,Z�S�L�o���~��!==��}{��3��RS������B`��!x���1`�,Z������)S���b���?��g�y�<��|�Mc����v�Z��|�w���?�����'������o�3�<��_���2d����c��;_}�&O��7�xj����:t(>��c����?��O���_HNN����?~<�L�����oX�d	���5k� 11Z��b��'Ob��������%K��[�n5j~��W=z�b�_~������8����\������w��`��Y�r�
�1�M�6��e������?�������v�?��S�b�����a�l~�=��9��3g��������?L�0�b���Wc��A�~�:�M������[�n�F��N����[<�����9���t"�	"/�j�*@���S\�rE\�xQ�[�N���	???��_	!���k� 6l�P���v�*5jdul[����m[���(�����P����������������Vy�A���-[Zm?{�� V�Z%oKNN�o�!o�q������$�u����O�8!��3g������^��z___1g�y�/��b���m0o��M�����b�|PH�$���Oy�V�-�9rD�����kU����8q� ~��y[^^����111���~FZ�j%
�}-�y�����6�N'n��v���_�~�_�~V���^����X�f��~��m����eK@l���b���l��h��/�l�����"??�����V�N'JJJ,��q������?������+V?O&����;w����6�� ���#��m+o3��%$$X��L�4I(�J���-�cPP����EEE�e����xg�����k��*�"W�
 ���4m����x��G�/����7�����������t�R�����V������Sx��Gq��5�jXPP���������'I���b���ru��<�������h���������k���P�9sF����+�w����v���];�[�Q[�n�R����?o���_�_�������n�Z��K�.�h�����wo���W��'�|�����c�,�ONN�k���[������~Z��T*��s�9�N��aBBB���������gOZt�@ll�U�nHH��O?�T�b���X�~=�
������T*�*��`���������W/�~&�_��o��?�0����s�v�q��)\�t��9O>��E�����^����v�����<L�:���g����$���W��5k� ::���s�} r5�BcH�����������k��������

����wo�&��:u
��
���A�F����o"99������'���^$%%�U�V���F���c�������n������|l��`��%K������������c�v�Wt��y4k����m������-ZX�Q�FVc�y���8����o>����������@�����s����g'''���6��������&%%a������p�w`��������Q��j��~���������W��'�x�����k���'++��?k5j���)�U7���8q"��Y�3f ''[�l��I��~��
 ii�Z�����������[oY-�bb

?�0n��v|�����o��[oa����q#���+�J����o��^{�5<����;w.7n�B��'���.���.��,Z����6`��	��5kl�b�����������'�|�;���|�	"##����p�?���=��
��)S�R�y��YT�*c���<yr�P��ic�}m�4j�����������A�"@�Z�������������/�����7**
�<��y�dee�G�x����X����?�w�u>�������h�����#mj��%v�����<�*��'���R��-q��I��5}��-["55���U@[���Q#�]����[����;�����FAT�T��G�����`�l��	����4XU���?G�V��q�F��}����U�3a�f�T*��-����G�Z������0t�P���/X�f
�w���;�J;�����#G0q�D4j��>�l����gO�n��������o��iY
�^����������Y3��������+J�����a��1Z�qd������{��^��Zb�����$INW:�u���b��}HKK��`�����A��>�N��g�����w����u��8q����$G��Z����^����s������z�MF��7n`������w��e
��?{���x?��Wlcxx8���N����������ok����s�=

��y���r���;p�@4i�,�w�}��yV���?���X����O?a���		�_|������B����_8;v��1c��ys\�t	�v�Bpp0����!//7�t|�At�������s'~��,\�P>^��=�~�z�����[oE`` ���������c��93f�����~�
k������uk���b���

B@@���l�	����p�]w��W_��s���kW|��7���/1q�D�	ua������O1p�@<���h��1>��C�={�����"���w����a���8w�:t���7���?�8-Z���D�;YYYX�|9:v�h��`�~�0~�x��7��=���J�S�Na��
X�d��B�����;:u��
6�}������S�9x�`l����?
��g�b��������p�����C�_�7�|37n�N�:�S�NX�t)������;c��qh��233��������b�I{�����O<�[o��>�(5j�#G����~����J��#�<���{J��bax"��P���\�i��_~����LK|�n*�J4m�T�q����_YYYN�2�<������e��������B!JJJ��)SD��]EPP�]�v�����q������>*BCCy�����	�jK�~�D�����l�R4H����X����"**J�������o"--��2&_~����������hG��M�0.�2i�$��Y3�R�D��m�[o�e�d���q1�399�j{E�=���������B�����{�-[�X�c�RA]�vM�5J���1j�(q��!�K�|��'�U�VB�V�n�������|��b���g�����O���;��^zI�����T��ly��7���N���`0�7�xC�l�R��������-[��l��={D��=�Z��Z����"))IDFF
�J%�7o.,>��sy��~�L�M��[6o�,���#���Dpp��������O��i��}����{�~�\�$D=��&"�j�;w���X�jF���mY�d	&M��s����]�-�9�n�����>rz&4���@""�"��|�~��yu�����?��LB�	8���d��y3v����~�
_~�eC7�������c��b�
L�0��E��\ ��\��G}���x��W0d���nR�y�������{���g�n���*�$"""�2HDDD�e����� ���$�0HOOGPPP�^o�����'�@^^�5k���|�`
���#::���ADDDN�x�"n����nF�`���� �����n
�#77���������L������DDDn���oyg�7�c$"""�2�DDDD^�c���� ��N��^�o��PJ�>>>^=��:�DDD*--����QXX��M�J���#**
j���������`0p��Y(�J4k�j���&"�@ii)�\���g��m��^��sU���PZZ
�����h���7ts�???�T*�?����h4
�$��HLDD�V�\?����!"""�2�DDD��s��A�$>|���BN`$""��G��$Ix����{��g!IF�m�����q��et����[I�������DGGc��u(**��c���h�����Q*���������#@"r?~��\k����=z ::7n��m��-Z�@����m��mC��}���0<�O�����{�nH����T���������N�<Yo�F�c$"�RZ�L������[C���\a��AnB������c��U��+W���1c,�)((@JJ
������T(
���0U��W_�����~������w�}T�X�%"���Y�u���k��"�flo��>6'�j��9��?��i��������~�	��������}�n���+W�i��8v�X���^�u���0u�T4���\����HD���������k�k��)
���Wc��U4h�4ib���S�0r�H�j�
������\�p��cw��E�:**
���U�'@5�
 ��R��W��p� 2��R����{mg<����0a`���V��w�}h��%�����Y�f0���JKK�<�J���6]"��nc��D�^,`^�����$Iw�6�����$!1�2�^�v
'O�����~�����!�Iu��~Z��,�����T*q��q�ks�5BXXV�X���(\�pS�Nm�fR�@"r/���J9��&���l�]�P`��u8p�:u��I�&����j�R]a���+�DN[�zu��o��I�:!!���x�|���������N�%i�u���25T�X$"��1�DD5�HD��<j�*����*�HD��<���^����lc$"�b�t%
�""7�HD��<��K0'"r ������&"r �������DDc$"�R1�HD�0@"r/�� ����O�H��v��
I����]���$���%�@"r/'���Ld���GC�$H��Z�6m�`��9��t�>w���

��FR�������T���H��`��U())���[����B�Ra��i
�4�G��{�@����Edd$Z�l���~			��y3-Z���;#  ���x��g��o������1f������Y�fJJJ���/#::���h��
>����<p�z�����'O��x��/�D�=��h��U+��=��*y��)�q��h4���v��Q�o�`���K�._@rB���ym�? IN?�����]�B��;�����X�9s�<�^z�%�������/^�3f��-00������4���;���+��=��W�Z��������i��x����������~���HJJ�;����o��O���O>	�9s&x�DDD`����������>_2b$"�b� �m!�F��y�W�u��OB 55��o�s�=g�bbb���O=���}��j���@�$DFF����������c�$$$Z�je�Z���:����:u*
���bh4��=S�NErr����s����^���3�s�N�8q��oG�f����7����>g*�2]�K�.ELL4
����o��*���an��h4t��[�n��j�x����Rv�f�������t�c�����l�m���ur~DTKLPQ��WN!r��-[�F��b���5kv�������y��

��Q�p��5V^�<|�0�J��*��K����(@VV���#�3g���q�p��e��������������- �Hp���HII�������#11'O�Dxx���{�����#1o�<<k����a�p��At��	���8x� ^{�5t��7n��/��!C�`�����3g��'T��KD5`
��@�8�@r
*c%��^�w�u�-[�Z�f���������������O���_G������?b���(--�����������*���T�]m0����={6x���i4�����p��E7n��X�|9���+�\�S�N����%0`�L��;w.v�����{��/GHH�����{�{�����Ey{PP�E9��\����T�U��ir
�X���uo��a�w�Q�$��aB@@��ic����0X�p!
c��g�}f��Z��^�����sg|��wr��z����'OZ���}���x�"._�,W��g�^��5xpii)8`���P(������4��IKK��AKLL�t����k��?aaa���;�z�-��B"�d���^�}}o������wD�j��
�Z-�}�]�9s�1�/_n�OLL��������W����111HNN���?�M�6������{�Ux���3��Ga�������q��q�[���O$$$���oFrr2�9�~����j���7j�x��U��zDDDXl���@FF���ddd8�qq1^~�e�9������������]�0~�x���x���*mkII	rss-nDT�L]����'�w����S�����������kW,Z�,@�N��f���7�b�>}�������#��iS�����e�����3�<�[n����CAA�������-[���o�������n�
o��6Z�l	�X���/PTT���{��'�����^{'��\��.i�Z<���B`��e�����_w��j������y����ku�y��a���u�f"�����!�h��
�F���o'7�z��J�4i&M�d�m��Q�/[����R�F�E�a��EV����;!�����[7�m���HLL��m7�|3~���m�A�i��$M�4�R�Dff������J��EFF���)��?;v������N�s���||��i����o/^�����V��=����*��R�:������jO�@�Z��={"55U�f0���Z�4���x��`�������S��s�N���U����C�P��yWO��Q=2���)��e����A��E�u�DT{\�8%%������z��������@����������^x����.��A��n�:���+V�`>� <�-[�@����7n�Z���4���w�u�������I�&���5j�0oU�|�����6}���*�$"��K�#F���+�1c222��[7l��M��q��yZ:`��v�ZL�>���
��m�M�6�S�N�K�.a����c
����w�y'|}}�n�:��5%%%�����I�,���1�S��������A 9�% L�0&L��������=��Cx���l�S���=zp!"wc�������6/ ������~���4�@""����>�Be����
0����P�
`C�,T����j�D�>L��*@Y���E�b���{v7�e���F.5<��c~:*�2]�DD�����X��p%*~��0�J%BCC��������oK
O���Bdee!44J���'y!@"r����.`�
 �6����H�'44���������<P(��7u�Xt�$!**
����j��g�]�T*V���HD��`>	����-S�.`��T*4�-q��x?��WV+N������HD�Co��EW)�Y�,��=����}�/#w{O�b��T�HD�a$"�a������
`��
 9�����i��^	D���� 9������20^8PW�������HD�C�6���@��B�c��I�D�>�.`�Wv�HD�������_	DW6����������HD�C^�K'���/����]�.`"r ��1����o��j�
���x������}�/��]����_��X,�yO�%���HD���Rp^�l���U�LDNb$"�a>����YU��9�D�>,&�xa4p �@"r�4P��]�����
 � �/���@"�%�D�>LPR�w�������@�^@Q�S��lb$"�a1	�{+���|�����HD�C�_�'�+�~fP�n`"r ��y,�
`����p%�mDD�`$"�a>�� �5���u5*��6""G0��f��M@�k��1��S�(�TH����HD�C�b6�|��3���Q(�S� 9������@�Y�K�i�J)A�4��f����HD��|�$�����*���9����HD��| �uk�f���U9����HD��| �u�6��V*�*�u���D�>*�� h���trPy  9������(�����.�������1��&"g0��e�.��e]��Y�
��
  9����G�1�J����$��
 ����q�D�>������#�����|�Y��D�8@"r�@�,�� �e]�>�]�\����HD�C�]	0��@y!hvQ
1��0T�����t)��e`8����HD���Rp@y�,#���`�����y)8"r �y��M1���(����@"r ���c����?TfcY$"g0����p�����VgVT�U��	�D�>LU0�1�^+TU�� �Qa!h/Z�|
@	�$���y)8"r ��.`��l� ��Y�v����}X]
�{���,���X�1�D�@"rV�zSp�
 ����\&.]�111�h4�����}�����
���[��h��sgl��U~L�����_F����f��!))	�����~�:{�1#44c��E~~~���������k�&{�**.CD5�p���HII���3q��At������������={0r�H�;���a�0l�0=zPXX�����^����q�F�<yC��8�c�=���;v���-[������'����%"'U:�*�ec�Lc�|\����p��E7n���:`���������+m��d�0S�LA���1w�\������ $$;v���?�v�����n�{����������c��m������8������.��[gU)$"Qq���r��X4uku���<������HHH��)
$$$ --��s���,�����J����H����P���������OBB
���[�3"�:c��y�:���McY$"'�4t�^�
�^�����8q����ddd��?##������x���1r�H��������7��8%%%())����������v��j�.c
z>�.`y!hV��q
^�kZ�?�0�X�lY��5o�<��������Zj%������h� 9��`�&M�T*���i�=33���6�i����w��y���C����Qq��N�����+}�i��!''G�]�x���$�Z`�������l��.`"r\�@�Z��={"55U�f0������x�������v��a��)��:u
;w�DXX��1���q��y���~�����8��������`�����z�20�.`��Y�DTs
>RRR����^�z�w��X�x1


0f�@RR�7o�y��^x����.��A��n�:���+V�`>� <�-[�@�����7n�Z����c��7n�/_�V�	&��GA�f��� ��	a}-`��.�Ra �$"g�D1b�\��3f ##��u��m���.\�BQ^������]������W^A��m�i�&t��	p��%l����[7����k���N��5k0a����
����;��S�'LD�fA�4P�M�x�TX^	�c��.`��	�0a���v��m�����C=ds���Q}�H����v�Z��ID
�|��N1-]�RpZ�$"'4�@""���</\P_q����
 9������UT��(������p09�����y��'��A/�l
�����*��r 9�����yW�U�������{�B���3��=�@	0�
��c}*T�9��������|��������B�DT�D�*^��k����'��HD5�HD���e���j��T�W�:�D�<@"r�+�XT��� lWy%"r �S�3�,��`�l�����q 9����C�c=��7]
N�"�mv]���� ��`=�8@"r �a�(/��]��J��09������lc�7t�-/��`����HD����V��E�3���A�D�l���k�_	��g[�$yF0g����=��E��T�WKu��c��=����z~���:��Rp-@"r ��LW�(���.��1�����&"'1�{�r@���x)8��&"�1�{�j�t����I ��c��=x��
��X$"�1�{0����.(�c=�Noy)8�c��y�D����m�<�
hk g����=[�l<��@]�����
`)+�D� @"r�@��gZ�����
��U�7:�$"1�{�9���q��[WUHDNb$"�`�X2���]��.�S�HDb$"�`k�$y�R0z^	��j ��������`��=P�"���@"r �[����h0@�y��k����HD�������K�f���I ��HDNb$"� /S���i)�_�X�3�6��r 9����������]�:�@T�09�����(��\����HD���1�e��=;���$"'1�{��zgPoc�HD�b$"�`k!h�k`Ucu�����=��0�5��@y@V��A�D�*���h���u��I�D�8@�K���A�BDb$"�P����,���1�	/��HD�a$"� �X������_	��1������=��@*���k[_
��&"g1�{��z_���^,'�p09����Ce��(Ue�{n��l�?�+��\����HD���
���qd��JV�����=��V2	����W-/�1�D�@"r�-������,*� �\���3gj�DDU��Rp�1�����������HD�Ql��
���.|��'(..��6Y��Rp^4P��y�l��c��A5
�D�.]������H�?���s�XK�.ELL4
����=��
p�-�@���s����u���7n�=�����0H����[��;��$I���z���Q��Rp�?�|��u��y5
���u��%K�����+W�������/:u��E����+vg���HII���3q��At������������={0r�H�;���a�0l�0=zT����}�����|�q���������7���
 ��#���e`��e����`-���je���x�l��,������'#::III�|�r��_�h���1c��C�X�|9����r�J��/Y���)S��}{��;=z��{��'�3j�(��1			U����?"##�[pp��o��J�z�B��1�> +�D��Z	�����3�<���(,Z��'O�����c����c����>����j
�			HKK�����4�`���X��UY�f
�4i�N�:a��i(,,�t������Z����x�@c�O����1�D���w���E��j�*�<y��{/>��#�{��P������W#&&��c\�zz��#""p��	�������FF�C���G��eK4k����+^~�e�<y7n����y�0{�l�^��jIuc��Mc�*�ek��9�Fp��ex���1z�hDEE��'<<|�AM^��<������;wFTT������O�u��V�O�6
)))�����������y�J���e`�1���6���jw���-Z�?!.^��-Z@�V#99��c4i�J�����333i�9����o���8���i3�������F�ADN��Vv%�
��j�j9��T�1��[����W��_�~���vC�V�g��HMM�����">>��s���-��a����eZ*��j&5�j�z�,`��Y�*^���T�
��������Fc�qRRR����^�z�w��X�x1


0f�@RR�7o�y��^x����.��A��n�:���+V���y��u\�p�����'O�<�����X�v-���^�����_��I�p�w�K�.N�DT�*(/���V��� ����
��qp�$a�����������w/�u�f��F��+W�`�����@�n��m�6y���,�������k�b���x��W��m[l��	�:u����y� ��G��9�f��Z����;������c�����%DT����wW>	D�B@��P4Qe�
��`����oP���cj�]�v����:��	0a�������j�C=��z����=�G������h|��w����)�y�:��1���1����>�Dd���]�c����%K�x2�=Q6���e`<`�
�i `\+P];K�����U�V�V;��������Rp�@""{9x��^����x�������������+�H�@�&"8CBB���!!!�� ""��
`e�@<���1��$A���7�&"�8��}�LD�F^��20^�\�@�X�Ju���j4b�����������������7���aDD�@o��d �\��W�8t�P|��G���l���.���C�l��Zi ���z�,`�?�>�09�F����������9"##q��y|��Gx��wj��DD���|�U6�����95
����

|��7x���P(p�m�������@""������cEc������j��i�M�6������};���@VV�&��#��B��7��lk +�D���3f`������A\\�������w��YT��
��`�i�����~Mkj9��P�+�<������/._���]�������������#"P��XW��?P_��J[�Td$"��(@dd$"##-�������%"*g��r����@_c�:�D�������?��������� �3g���qDD,�]ec=z��
���f$"'�(>������0j�(DEE���#"�U�@�u=���1�rd09�F�����W_}����o��""k�,�x��@���m�T��,a��P�Y��5B���k�-DD�����*V��1��uU,c��.`"rD����s1c����:�:�6:-�ap��3us09�F]�.��������T*��<X��0�*���.`SPQ�@V��5
���
��fUATQ4�BXw{���r"rF����3k�DD����m�Z1�=�����.��1��I �LD���@������_L�6
��_`���t�R�GD��1��3����,�
 9�F�U���_�������;w���C����q�F\�p}�Qm�����=c�����&�']A��9�F����=�N��FS�G��{����_���z�R]���^
���k�Rp�LD��Q���_0~�x����7GFFFMMDT�T�����,yl4�;/GD��F������V����4m��&�&"*g���d�O�$���/��6�#�$UW�$"rD���!C0g�h���uK��.���_����k��DD��J�-���=4��@l���20D����"??M�6EQQ����6m� ((���zm�����<�F0`V��.`�|%vQ���,������?���9���|���			��>"��g�@�g@���k����t4X�z56n��s��A�$���"22BH�?5�:��-���]��T�9��.`!��'�x�.]B�����cG�?�G�����_��$"oV�B���w��X�4	����#���^���=RSSq�]wY<����b��a�������T+�$"/���@tU\�c��NU?��S���+V����nL�:k���q����={��f3�3�
����+P����#G�n��+���\�@yv��
���_GDDD��GDD���N7������e`<���hk��=a���T������|��R��N�s�QDD����
���������$!F�
___�������QDD�|�=����N����j��`"�5^uzS��I HDp*�Z����ADT99z����h�?��F�&"��.��@}���M�|� Qu����{-`����HD�c$"�W�@�v
���f�U��^�D���w���b��R�fN!"{1���@�g�9���\�`��>��h�N_om""��HD������+~*c,��HD�a$"�W�:��������K��@"� ��j�zvpU����XT�HD�a$"���]��*f������@"� �>�'�x^4D�>*�l�.f$";1�����y]���w���.`"r����K�"&&�qqq��o_��o����r4
:w���[�Z<�q�F�s�=�$I8|���1�������",,���>|8233k����6x�$�Y�l�<�@"��K����#%%3g������kW$&&"++���{�����#1v�X:t��
��a�p��Qy������,��u'M�������a���;��������#��w��+��K�T[d$";�D\�h���1c��C�X�|9����r�J��/Y���)S��}{��;=z��{��'�3j�(��1			6�����>��-��w���={b��U��g~���:9O"r��@���T�1��&";5x,--��,��B�@BB���l>'--�*�%&&V��-�V��8�-���-ZTz������Z���x�,`���HDvj�x��U��zDDDXl���@FF���ddd8�e�P��

��8���CHH�|����������z�,���K�����J Dd���d��i����o/^l�&y�88/�\Y���@��q��5�?M�4�R���}������H�����th���QZZ���l�*`U����������AD������:�����q
^T�����'RSS�m������������x��`����oK��=�R�,�s��I\�p���Q=�;zb�������@��^
^���$''�W�^���7/^����3�������c��y�^x������1h� �[������+�c^�~.\@zz:c������H���`���HIIA������{��������� �*y�$���W��u
����A.G��+W�`�����@�n��m�6y����0�R�>}�v�ZL�>���
��m�M�6�S�N�>�7o�$<��#��3gb��Y���~
���GII	�������C�u�o!h�����$	!D���-���		ANN����9D���D�����O���Y?~��Nw@��^���CG/�`��?"*D��i�m�������{qKd�M���[H�~����$"�Vu]�>����~�S���l�S^�
 ����\�������iS=��M�j0�LD�b$"�W�@S]q�������,`"� �>{+�����+�T��Z�0�BDvb$"�g
�R%@��|&��@Gf��
����z�D��������^�Y�|���@!������c�
�e�i��}{��=@_Te����&�Q�`$"�'����q�:�Z
��Y��$!�������z�D�����
 i��C�e$";0���+���=t`���W�LDv`$"�gOT�U=,�� j�LD�c$"�W�B�@�Z��:��l
�%�:o�?@"r}vu�&�xV�w��8�@"� �>���=3����X(�f$"{0�k��
����n�q0'��=���	�K��3����o`�\�@"� �6�YE��Y��Z�/�HD�`$"�f��������9	���HD���
�����HD`$"�fZ��Y���Y��^
�]�Dd@"rm�P��O�����UU���\�J D�@"rm�K�HUT�<t�No�:���LD�c$"�f�����VWS�3v�����������\���Cg��*��,\ ��U@"� �6�@��%`�l_�R!!�l  U���\��,�(UU�g�z\��B���Qv! U���\���x_]4���Y��vV �O
�)*��6��c$"��/X]T�K��=��T���ZVd0U���\����.�K���=��4�WmG�4�]�DT@"rm���
2�k-�vsZ�Z�vT��N�D���h�U�w0�.`"� �6�����}|��
,��X�l�,`?@"� �6���z?I��q�ZG&����.�,`"� �6{���=��3���.`"� �6�P���]{��V��B��I �DT
@"rm�X�@�5@�YPk�*��Y�DT
@"rm���+���\6P�c���"-�u�."ro�D��v^	0�zPp�,`�����u��R�Y��j �6{gY,�\}�F����R���DT@"rm����e`L��UvL�$I�gQU���92��+�:S���-�� DT@"rm�������_(�	��`��*�D��Lc�Z����'��],�	LDT@"rmzf{�@�A����=������LDU`$"���:�r�3��M�?��Y��y0gQ�����c�X�/�x_�Sg��O���Y��Y���&�*0�k�����~_�F���u��zd�
`�g0U���\���
�&�x_t��K���,I���kHD�a$"���@SP_
h��M��t{���Y�DT=@"rm�\XP�\LQv�5������W���f$�*�L\�t)bbb��h�}��U���
p�-�@���s����u���B��1QQQ���CBBN�:e�OLL$I����?�����j��u%�|"���+�>T�.`�&���D\�~=RRR0s�L<x]�vEbb"���l��g��9c����C�0l�06G���y��7��;�`�����w/������b�c��3�/_�o�=�\��+9��1��GM1���s
@�|��R��,b""s.-Z�q��a��1����/_�\����K�,��0e��o�s��E�=��{�0V�/^����c������>��#���c��M�


Bdd�|���%"G�]�v��`qv�4�>��1��wi�+��&��4x,--����� oS(HHH@ZZ������Y������g��EFF��>!!!����:�������������N���S#���H0`9��������O�R!!Xc��	LD�����u�������������'N�|NFF���322��M�*���y����7��={0m�4\�|�-���%%%())�������,��i^�l�b�U@LB���-��HD�j���RRR���t��Z����c��y�������y�={v}6���hop���f������D"������4i�R���L��������������*�7�;rL����N���s�l>>m�4������/VynDT��Q@����
 �&��5xT�����'RSS�m������������x��`������������'77{�����p��a(
����|������7"�c������iO=2Mqd0����z.�������d����{�����QPP�1c������ys��7��/�_�~X�p!
�u��a���X�b@�$L�8���?��m[������^C�f�0l�0��${���]w���� ���a��I��?��F�5��@D6�M���������M{�����cy98"��K�#F���+�1c222��[7l��M��q��(����O�]���O�+����m�b��M������K/����<������F��}�m�6h4�j��u�0k�,��� 66�&M�HD.@��������M{��3����.`V��2.`��	�0a���v��m�����C=T��$I��9s0g������?���Sm%�z��������+u��z$w;�x=`"�Z��$"��i��c�M���A_7m�':���v������6@"rm�20���1����J��b��
 U���\�<����)�	������
���]�ec9	��*�HD��`DY7��c�X�d�$"� �.�Y�Q80g�4���+��NW�a9�H!D����� �.�Y��(_
��`��X��u�X��7���j�]D����u��f�:�l
����lP�R����A�-�D��t%�{I�`�l��O1���Q:�<I��8��op)"����\���x��q�y��Ut����@"��HD��T�q��0�v��;;��*��Dd �.g+��2P��@��x���l`$"�e������<e���.`�@@"����\WM���\J�����I DT@"r]�@+��a�����U�m�G�
�Z��,`hT��3�5@"r]�V
 0��u~F�������c����HD��Ttdh���}^f����9�4�e`��j�D���.`+�i�w�
 ��!�:�HD�K�vp �@y`
*��EZ�
�V�ED����\W�*�Q�{������o�t�@6�Q�D����A�_,*-�*���R�?c�Z�DT �.y!hg&���@!��&�h���&��1����U��?��+�Z�����4r)"����\���x��s���
`A`0�^��I�V/�L0��`��r�D��JkP Px�V�UJ��BTJ��c4)[
�j Yb$"�U�.`��xI8�-��*�~*%$��b�<��[\k�""��HD��&]�@�b�n8P�N,c\s�j�MD�9��ui�����/�����zdZ�����x9�@"��HD���������K���zT\v��T�B������"@"r]rtb �D��/�N{�Q���E�ML��B�\Q$"�����u;C�`�������Q9�g:X���
"��Dd���\���v�x��>���iO=*(�}}�>�$If�9���1����20�et�����`@
 D��K7�� �&!��|����n@�%@��ZkZ}��
 �61�wg���MD�9��5���j���1�* (����M�/��
`�����W�k�&"��D��J������e`�QK����5oS=*��.`S�3����1�k2@� ��K��Z���Y�6����,���6��x�Z!�z�IDu���\SI��^�d��IX���S5;N=��I ������.\/����`$"�d
����3	kk�w�
`~�):�4(�\�==���""��HD����`�(D��U��J��`�����������5>y@"rM�ck�Q )�K��e��Y��F�1���<�����5>y@"rMEeaER������&�d����QN�)�k|�^1�
���\�kk|<"r�D��L74����u7�_:X�c��R�A���*���j!����R����c$"�Tx�x�V�c5�i�Ow��]T
���Mm���N����]����{c$"�TP������A���Sh��
�SA����fu6^��Y�c70��c$"�T�]����
(���������|c�q-��3��,m�Q�5�����q��=1�k*(���U~@L_��'���xu,3��q�^m�$	c�X��,����Q�a$"�c0��������1�6��A�(��!����7!�_������Q�$�f�D�z
����}��
2��_�Kj��u$#�n��Z�������D���&�V�D�zr.���e���Ep�e���3��v�[.e�j9��w�B�@_��V��>_��'"��HD���Y�}h��=n��
p�`�+��ft�J> �I@�;��)�����8{���_��\ �������j���c�!�����8���s&%y����������t����*��8��6�������[�q[��(,�������:y"r].�.]���h4���a��}U��a��r�-�h4���3�n�j��3f�@TT�������S�NY�s��u<��cFhh(������Z?7"r��#������.C�>����������X=X|���K�*���o�>��Y���u���\�
!~*D���k(���f!��R������~��bmy����|�v�+�a�����_�`�	|��e\�^��)Q�$������GRR�/_���8,^�6l���'n���={p�w`��y<x0��]��������`���7o>��C������^�o���c��A�1��8p ._������j�3fn��V�]���v���"$$999��7����C��x�g �}������MO��k��,|J��4 ?����@d ��q�&7Q]uY�������-����[�y��?������CV$���9V���|<��~��b�V�(��Y08��UD#��"~�,������`�:����0��*]�C�������((�#@��d�{����z�u�*���@_��T�$r���E`\\n��V����k�`0 ::�=��N�j���#PPP�-[��s������[7,_�B4k�/��"&O����ADDV�^�Gy��G���/��W/��m����{��_��f���y� �:��r`��@����v'���������
��k]���`�9��6���@����%)�������`��5(
���x��h��1�
hB��e]��z$.���b��1�w-��4��l ?��0��:��/������gB���n�?�K��K�+�_1�rT�� ��gi#�
����J�"+���C�:��pY�g-q�8���8�'�X+�Q)��qn�
B����[���&��@I���-�@2��E7�����
Z�9�8w����J^	T
	*�J�z�\)��������l�� ����!*T���ji�(,���T��=��zyV�$~*%:4F��pkLc�����U]���W�?2��Gf�\��A��Ad�Q!~�W� ��0�:�!~�M�2J�hT��to��] ��������9�
&oONNFvv6���K���h�)))�8q��m�����i�9�3g��u��8t��u�&���_?t��
K�,���+���/�����:��6l����o��%%%())+�������Z�:��C��\�~R�?0�}���������_�>�������?��w�=�m�������lT��;^
�{<_C���>n<�
��5m���iwC>Z��F����]F����g�X�b�)E
��o@��/�V"��H
@����^��?z�����Y�)t��Z�g���eCWJ@R��+������pb��:�
2>__�q�z!!�(���M�6$H�-�P���U�t)E���J��M#J`��R���
�P�P�D	T�
 A��T��$�~N�q}�\!$���J���J������TJI�F����<EZ�E�t�����>P+�$�{h0���N/��P�7�Tg��������J)�G!ARH��y�$	
��d|L���R��#Q�����(;��{�)K�cKe�?��H��0��;����@��k�W�^�^�GDD������8q��s222l����!?n�V�>��}||��qcy��������g�yf�+�t��;��u�\����~�4tS*���V.7+e��HMpA$���'�[q]�3�r�X�C0
,�{�%�%�B�����fkB����c@,-0�tE��[P$�	h���1�H���
�}�q��`�x��*
�:�KT��'��~��N�i�)���F���A)	�������BB���R	�H9h���QgG��V�L_v3'���@������v���3ZW�9���;�6mRRR��M���������$�v�IU~[����CB����;�==}���jwa����a{{������C���%;�52�s��O��J�_���N�T��R�	UP�FhG��X,�~w��;�]���|���[�e7���%�*]>|�yP���(A�04�Bc�AoVb1�L�o��2�h����g#�e�1�_�����'�-�P�Q�Z�f}���M��*dI.P�k���b�@N�%Z=J
�4��SA�0�G����*��6���Pd_���:�U��T�@��C�B	�Z��R��Cc
�2@���IQ��J�����YY���0���^k��t���I�z�@v���:����+$	�~*k|�R:�NKt\/(�������a���R��>
�T
��}��V�G�@a�%�v�������'����!�t��Mo��$��Q���&�c*�sVJ��|���UQ^4���B�i�>�7T��M�4�R�Df�� ���LDFF�|Nddd����333e���K822YYY���t�~�z�����_����g��^��^���u����$�����F4e7�h�:��%���[m�Uv��_���S�/�V���gO�����RSSo�9������;��ccci�Onn.���+����l8P~I�o���qqq�v~DDDD���+�������d����{�����QPP�1c������ys��7��/�_�~X�p!
�u��a���X�bciz�����?���m����4k�L�h��}{0���������j1a�<��#v�&"""rW.G��+W�`�����@�n��m�6y���P�+�����k�b���x��W��m[l��I^^z�%��'�Dvv6����m���k��5k0a����
����;��S'NDDD�|w�i�DDD���~��@""""�_�DDDD^�������0y@""""/�HDDD�e����� ��a$"""�2.q)8we��Jnnn������e�w��/��Xyyy����n	9*//!!!
���k���`@zz:��� IR�;77����x��G^�����<�y~�������<!�����Y3(�9��P(������5���=������<�y~�������o���xg�%"""�b�DDDD^��E���b������m���	�����s���?O?G��'�yV����� ��a$"""�2�DDDD^�����a���h��%�����O���/��B��1QQQ���CBBN�:eq�������Cpp0BCC1v�X���[��������o�F�Att4�|��??�V��_~�;wF@@�5k���$���[#&&�$Y������W�9������?`��c��g���L���zK���>������w�5kI��i�&����wn��
���[��h��sgl��������s;v,bcc������[c���(--����g���?������X�W��{��J/M����n����s��� I>lu���b<���C`` ����L�}.\��A��������2e
t:��>�w�F�=����6m�`���5>?�"��<����C������N�3g��������B1�|"6m�$�9"�"bccEQQ�|���]����Y����M�6b�����999"""B<��c������O?~~~����w��_vv�HHH���'N�iii�w���g���h����3g��|��|���w�����"99Y0�����_�8��~�B���|��X�r��$I�>}Z>�+}�[�n������q� �������w���~J�R�������cb���B�R��~��A������G���o�O�_~��/���|��g�
b����iii�������XW�W�XRRb�{��O���Xa0���~��Gb����?��� :du���zJDGG���T��~q�m��>}����t:��S'��� :$�n�*�4i"�M�&�s�����/RRR��c�����+�J���m[����0����B�T*��-[,����C�����`0���H��[o��egg___����
!�8v�� ~��y����ZH�$.]�$������5%%%�>/���h��]]�^��g��}�q��yy[��-��o�]��4��	a�9&''��C�VzO��*���n�m��V���>�~�a1h� ���������7������o���X�{Sx����+�_m�<���	Q;�aii�h����3g���U?Cs��1;;[�T*�a�y�������&�0�L�B!222�}�-[&��������^;v�8��#Dbbb-��g`p��t����h4�������?�������@BB��XHH������HKKChh(z��%�����B��{����q�P���>���8y�$n���`�gKNN$IBhh������#,,��w�[o�eQ�o���?���w#<<�����O?�k��Y��S>���L|��W;v��c���������4��1�cz��:?[rrr��qc��C�Axx8������7[<���W����8?���p����v���c���}��8p��Z�E�n���h�����s�������ILLDnn.~��wyW<?W�XG�����s�"==z��|�	���p��eddd����{�c�x����7����1L���������b����9r��E���y�[��v�������o���^�o���;����>Bjj*,X�����^����)���~��� <���]�34W��s��S��k��U�����w������m���X�p!6l�����
}����a�,�+�_m�<6�����#��� 117�t���U?C{ddd@�V[
*��:���������Z�^|�����?���?����C�T�G�9r$8��M����V���?!�-[f�XJJ��u�.]�V�1~�x��7�%.�S�9>��#���;wF�.]��uk������o�f������+W�������gH�]�t	�C=�q�����4ib���z��HOO�[o��!C�4DS�M?����o���>��b���T?X�C�[��w�}���|\�x����V�E�V�	V3�233��"##���e��N�����-��u�cu���31�����c���?[������p��9
{~�}�h�U�Vh��	���O�����?���'O��'����������\e�����s~&���������O�X���c����?���r��3���cC��������V�BXX�]��>C{DFF�������+��:������Z�^�A@@���p��
l��C�Ell,"##���*������{�">>���l�j���~�����8y����Z�V�g��h��5j�`����S�Na�����X��B����\������������]CTT��M>�����]�v��X�����\||�����1�NC�`���y�����'V�Z���>,�L�}~9����8v�B�Z�
IIIP�T��>C{���*���m'O���,~O��7����
:t��q��s)
=��m��M|������3��o�]�vqqq�T�������P���_�_�U:�����w{��?���h��������"""B�5J=zT�[�N�����"U�_ii�2d���������-�"0����g�x������������'�|"�6m*���\���;���<1y�d���&��=+v��)z��!��m+����c��gh���#�����e����j�a^^�8t��8t�� -Z$:$�<�����~�I������_����b������FM�����m������������������k������������.
�X�r���_m�<�����9����S���z
W��]�&:$���+@�[�N:t��g����-Z��~��������������e`���q��a�m�6��iS���L�2E?~\,]����T�X���_/Z�j%�j�����>������7���^���W���_�<y����]#G����"88X�3F���Y�s����o_���+�7o.������g��o��k�.!�qqq"$$Dh4��}{��oX���<������P�s�=�i��B�R��-[�q��Y,M ��~�&���������v!\�3��k������d!D���}��g���oj�Zt��Q|��W
~~�V�����d����}�����_���{[,����W�?�uq~�q�&#G��X��+�����9S>FQQ�x��gD�F���������-�B�;wN8P����&M��_|Qh�Z��t��M��j��U+�j����'������DDDD��8������0y@""""/�HDDD�e����� ��a$"""�2�DDDD^�������1l�0���z�j����Z{��� ��a$"��h�"t������3�<���|����1f����@�$H��Y�fJJJ0y�d4o�����������*���oG����������r�Jt����������	�?�8l��V�Exx8>�������s�$	���eggC�$��7n��c�=��M����m����U�x���1�KS(x��w������?���~��^z	��O,^�����|�2._����'&L����4�[����+z�!0�N���]XX���_�������������`��ex��g���O���~������M�O<�m��Y�-[����#F�������p��1|���8~�8�-[�&M������K	"����,�j��6laaa���V�!!!��?^(�Jq��%�������M��@������K�.����5���j�m����X�`���}��'F�m���={V�����qC�v���9f���IDd���DDU��s'����'N 77:����(,,���������o�������-���� ,,L�����[������BVV ++�������m{��'�b�
���K�����_�o���&�k��������q��A�s�=6l���S��AD��]�D����;����K�.����?8pK�.���V����|(�J8p��o����%K��T*���$I����Wm����p�������O>All,n��v��O�0�	6�&`Ghn���8�<&M�$R�nj""g0��:p�.\��n�
7�|3���-�Q�������w��^���,�i���i�k!&&������a��a��UX�z5�����5m�,��O1�/99�|�	/^�+V8�:DD���\NN�U�	C�6m��j���������O?�����[����|����k�������7���{IIIX�p!�w��+W� 55]�t��A��j��Y���SO!<<D^^~��'<��s�>O<��^���d�������v������Xdeea������1={�D��QRR�-[��}�������HD�-99Y���;V!��E�DTT����������>��7�c<��S",,L3g�BQZZ*f��!bbb�J�QQQ������������/��BT���|�r��];��=�����A�l�R�{��V�f�hR�c�����x���'�u�&����I s�����~~~�q��b������3���DDU��0|BDD���G����j�*<�����9�}�����DD��]�DDN0�z�*.\���P2�j�������^����j�DDN�p�bccq�M7a�������s�o��hQ��LDDD�e���a$"""�2�DDDD^�������0y@""""/�HDDD�e����� ���������IEND�B`�
#5Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: David Rowley (#3)
Re: Use generation memory context for tuplestore.c

On Sat, 4 May 2024 at 04:02, David Rowley <dgrowleyml@gmail.com> wrote:

On Sat, 4 May 2024 at 03:51, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

Was a bump context considered? If so, why didn't it make the cut?
If tuplestore_trim is the only reason why the type of context in patch
2 is a generation context, then couldn't we make the type of context
conditional on state->eflags & EXEC_FLAG_REWIND, and use a bump
context if we require rewind capabilities (i.e. where _trim is never
effectively executed)?

I didn't really want to raise all this here, but to answer why I
didn't use bump...

There's a bit more that would need to be done to allow bump to work in
use-cases where no trim support is needed. Namely, if you look at
writetup_heap(), you'll see a heap_free_minimal_tuple(), which is
pfreeing the memory that was allocated for the tuple in either
tuplestore_puttupleslot(), tuplestore_puttuple() or
tuplestore_putvalues(). So basically, what happens if we're still
loading the tuplestore and we've spilled to disk, once the
tuplestore_put* function is called, we allocate memory for the tuple
that might get stored in RAM (we don't know yet), but then call
tuplestore_puttuple_common() which decides if the tuple goes to RAM or
disk, then because we're spilling to disk, the write function pfree's
the memory we allocate in the tuplestore_put function after the tuple
is safely written to the disk buffer.

Thanks, that's exactly the non-obvious issue I was looking for, but
couldn't find immediately.

This is a fairly inefficient design. While, we do need to still form
a tuple and store it somewhere for tuplestore_putvalues(), we don't
need to do that for a heap tuple. I think it should be possible to
write directly from the table's page.

[...]

I'd rather tackle these problems independently and I believe there are
much bigger wins to moving from aset to generation than generation to
bump, so that's where I've started.

That's entirely reasonable, and I wouldn't ask otherwise.

Thanks,

Matthias van de Meent

#6David Rowley
dgrowleyml@gmail.com
In reply to: Dmitry Dolgov (#4)
Re: Use generation memory context for tuplestore.c

Thanks for having a look at this.

On Sat, 11 May 2024 at 04:34, Dmitry Dolgov <9erthalion6@gmail.com> wrote:

Do I understand correctly, that the efficiency of generation memory
context could be measured directly via counting number of malloc/free
calls? In those experiments I've conducted the numbers were indeed
visibly lower for the patched version (~30%), but I would like to
confirm my interpretation of this difference.

For the test case I had in the script, I imagine the reduction in
malloc/free is just because of the elimination of the power-of-2
roundup. If the test case had resulted in tuplestore_trim() being
used, e.g if Material was used to allow mark and restore for a Merge
Join or WindowAgg, then the tuplestore_trim() would result in
pfree()ing of tuples and further reduce malloc of new blocks. This is
true because AllocSet records pfree'd non-large chunks in a freelist
element and makes no attempt to free() blocks.

In the tuplestore_trim() scenario with the patched version, the
pfree'ing of chunks is in a first-in-first-out order which allows an
entire block to become empty of palloc'd chunks which allows it to
become the freeblock and be reused rather than malloc'ing another
block when there's not enough space on the current block. If the
scenario is that tuplestore_trim() always manages to keep the number
of tuples down to something that can fit on one GenerationBlock, then
we'll only malloc() 2 blocks and the generation code will just
alternate between the two, reusing the empty one when it needs a new
block rather than calling malloc.

5. Higher likelihood of neighbouring tuples being stored consecutively
in memory, resulting in better CPU memory prefetching.

I guess this roughly translates into better CPU cache utilization.
Measuring cache hit ratio for unmodified vs patched versions in my case
indeed shows about 10% less cache misses.

Thanks for testing that. In simple test cases that's likely to come
from removing the power-of-2 round-up behaviour of AllocSet allowing
the allocations to be more dense. In more complex cases when
allocations are making occasional use of chunks from AllowSet's
freelist[], the access pattern will be more predictable and allow the
CPU to prefetch memory more efficiently, resulting in a better CPU
cache hit ratio.

The query you use in the benchmark, is it something like a "best-case"
scenario for generation memory context? I was experimenting with
different size of the b column, lower values seems to produce less
difference between generation and aset (although still generation
context is distinctly faster regarding final query latencies, see the
attached PDF estimation, ran for 8192 rows). I'm curious what could be a
"worst-case" workload type for this patch?

It's not purposefully "best-case". Likely there'd be more improvement
if I'd scanned the Material node more than twice. However, the tuple
size I picked is close to the best case as it's just over 1024 bytes.
Generation will just round the size up to the next 8-byte alignment
boundary, whereas AllocSet will round that up to 2048 bytes.

A case where the patched version would be even better would be where
the unpatched version spilled to disk but the patched version did not.
I imagine there's room for hundreds of percent speedup for that case.

I've also noticed the first patch disables materialization in some tests.

--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
+set enable_material = 0;
+
-- UPDATE on a partition subtree has been seen to have problems.
insert into ab values (1,2);
explain (analyze, costs off, summary off, timing off)

Is it due to the volatility of Maximum Storage values? If yes, could it
be covered with something similar to COSTS OFF instead?

I don't think not showing this with COSTS OFF is very consistent with
Sort and Memoize's memory stats output. I opted to disable the
Material node for that plan as it seemed like the easiest way to make
the output stable. There are other ways that could be done. See
explain_memoize() in memoize.sql. I thought about doing that, but it
seemed like overkill when there was a much more simple way to get what
I wanted. I'd certainly live to regret that if disabling Material put
the Nested Loop costs dangerously close to the costs of some other
join method and the plan became unstable on the buildfarm.

David

#7David Rowley
dgrowleyml@gmail.com
In reply to: Matthias van de Meent (#2)
2 attachment(s)
Re: Use generation memory context for tuplestore.c

On Sat, 4 May 2024 at 03:51, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

On Fri, 3 May 2024 at 15:55, David Rowley <dgrowleyml@gmail.com> wrote:

master @ 8f0a97dff
Storage: Memory Maximum Storage: 16577kB

patched:
Storage: Memory Maximum Storage: 8577kB

Those are some impressive numbers.

This patch needed to be rebased, so updated patches are attached.

I was also reflecting on what Bruce wrote in [1]/messages/by-id/Zk5r2XyI0BhXLF8h@momjian.us about having to parse
performance numbers from the commit messages, so I decided to adjust
the placeholder commit message I'd written to make performance numbers
more clear to Bruce, or whoever does the next major version release
notes. That caused me to experiment with finding the best case for
this patch. I could scale the improvement much further than I have,
but here's something I came up with that's easy to reproduce.

create table winagg (a int, b text);
insert into winagg select a,repeat('a', 1024) from generate_series(1,10000000)a;
set work_mem = '1MB';
set jit=0;
explain (analyze, timing off) select sum(l1),sum(l2) from (select
length(b) l1,length(lag(b, 800) over ()) as l2 from winagg limit
1600);

master:
Execution Time: 6585.685 ms

patched:
Execution Time: 4.159 ms

1583x faster.

I've effectively just exploited the spool_tuples() behaviour of what
it does when the tuplestore goes to disk to have it spool the entire
remainder of the partition, which is 10 million rows. I'm just taking
a tiny portion of those with the LIMIT 1600. I just set work_mem to
something that the patched version won't have the tuplestore spill to
disk so that spool_tuples() only spools what's needed in the patched
version. So, artificial is a word you could use, but certainly,
someone could find this performance cliff in the wild and be prevented
from falling off it by this patch.

David

[1]: /messages/by-id/Zk5r2XyI0BhXLF8h@momjian.us

Attachments:

v2-0001-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchapplication/octet-stream; name=v2-0001-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchDownload
From bf4f15355eb040b0c0410a5700df1ebcda5938e5 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 20:17:39 +1200
Subject: [PATCH v2 1/2] Add memory/disk usage for Material in EXPLAIN ANALYZE

Up until now, there was no ability to easily determine if a Material
node caused the underlying tuplestore to spill to disk or even see how
much memory the tuplestore used if it didn't.

Here we add some new functions to tuplestore.c to query this information
and add some additional output in EXPLAIN ANALYZE to display this
information.
---
 src/backend/commands/explain.c                | 37 ++++++++++++
 src/backend/storage/file/buffile.c            |  2 +-
 src/backend/utils/sort/tuplestore.c           | 53 ++++++++++++++++
 src/include/utils/tuplestore.h                |  4 ++
 src/test/regress/expected/partition_prune.out | 60 +++++++++----------
 src/test/regress/sql/partition_prune.sql      |  5 ++
 6 files changed, 130 insertions(+), 31 deletions(-)

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 94511a5a02..b284e93fed 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -125,6 +125,7 @@ static void show_sort_info(SortState *sortstate, ExplainState *es);
 static void show_incremental_sort_info(IncrementalSortState *incrsortstate,
 									   ExplainState *es);
 static void show_hash_info(HashState *hashstate, ExplainState *es);
+static void show_material_info(MaterialState *mstate, ExplainState *es);
 static void show_memoize_info(MemoizeState *mstate, List *ancestors,
 							  ExplainState *es);
 static void show_hashagg_info(AggState *aggstate, ExplainState *es);
@@ -2248,6 +2249,9 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_Hash:
 			show_hash_info(castNode(HashState, planstate), es);
 			break;
+		case T_Material:
+			show_material_info(castNode(MaterialState, planstate), es);
+			break;
 		case T_Memoize:
 			show_memoize_info(castNode(MemoizeState, planstate), ancestors,
 							  es);
@@ -3319,6 +3323,39 @@ show_hash_info(HashState *hashstate, ExplainState *es)
 	}
 }
 
+/*
+ * Show information on material node, storage method and maximum memory/disk
+ * space used.
+ */
+static void
+show_material_info(MaterialState *mstate, ExplainState *es)
+{
+	Tuplestorestate *tupstore;
+	const char *storageType;
+	int64		spaceUsedKB;
+
+	if (!es->analyze)
+		return;
+
+	tupstore = mstate->tuplestorestate;
+	storageType = tuplestore_storage_type_name(tupstore);
+	spaceUsedKB = (tuplestore_space_used(tupstore) + 1023) / 1024;
+
+	if (es->format != EXPLAIN_FORMAT_TEXT)
+	{
+		ExplainPropertyText("Storage", storageType, es);
+		ExplainPropertyInteger("Maximum Storage", "kB", spaceUsedKB, es);
+	}
+	else
+	{
+		ExplainIndentText(es);
+		appendStringInfo(es->str,
+						 "Storage: %s  Maximum Storage: " INT64_FORMAT "kB\n",
+						 storageType,
+						 spaceUsedKB);
+	}
+}
+
 /*
  * Show information on memoize hits/misses/evictions and memory usage.
  */
diff --git a/src/backend/storage/file/buffile.c b/src/backend/storage/file/buffile.c
index a263875fd5..9255f7d464 100644
--- a/src/backend/storage/file/buffile.c
+++ b/src/backend/storage/file/buffile.c
@@ -867,7 +867,7 @@ BufFileSize(BufFile *file)
 {
 	int64		lastFileSize;
 
-	Assert(file->fileset != NULL);
+	Assert(file->files != NULL);
 
 	/* Get the size of the last physical file. */
 	lastFileSize = FileSize(file->files[file->numFiles - 1]);
diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 947a868e56..24bb49ca87 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -109,6 +109,7 @@ struct Tuplestorestate
 	bool		truncated;		/* tuplestore_trim has removed tuples? */
 	int64		availMem;		/* remaining memory available, in bytes */
 	int64		allowedMem;		/* total memory allowed, in bytes */
+	int64		maxSpace;		/* maximum space used in memory */
 	int64		tuples;			/* number of tuples added */
 	BufFile    *myfile;			/* underlying file, or NULL if none */
 	MemoryContext context;		/* memory context for holding tuples */
@@ -238,6 +239,7 @@ static Tuplestorestate *tuplestore_begin_common(int eflags,
 												int maxKBytes);
 static void tuplestore_puttuple_common(Tuplestorestate *state, void *tuple);
 static void dumptuples(Tuplestorestate *state);
+static void tuplestore_updatemax(Tuplestorestate *state);
 static unsigned int getlen(Tuplestorestate *state, bool eofOK);
 static void *copytup_heap(Tuplestorestate *state, void *tup);
 static void writetup_heap(Tuplestorestate *state, void *tup);
@@ -262,6 +264,7 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->truncated = false;
 	state->allowedMem = maxKBytes * 1024L;
 	state->availMem = state->allowedMem;
+	state->maxSpace = 0;
 	state->myfile = NULL;
 	state->context = CurrentMemoryContext;
 	state->resowner = CurrentResourceOwner;
@@ -420,6 +423,9 @@ tuplestore_clear(Tuplestorestate *state)
 	int			i;
 	TSReadPointer *readptr;
 
+	/* update the maxSpace before doing any USEMEM/FREEMEM adjustments */
+	tuplestore_updatemax(state);
+
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
@@ -1402,6 +1408,9 @@ tuplestore_trim(Tuplestorestate *state)
 	Assert(nremove >= state->memtupdeleted);
 	Assert(nremove <= state->memtupcount);
 
+	/* before freeing any memory, update maxSpace */
+	tuplestore_updatemax(state);
+
 	/* Release no-longer-needed tuples */
 	for (i = state->memtupdeleted; i < nremove; i++)
 	{
@@ -1444,6 +1453,49 @@ tuplestore_trim(Tuplestorestate *state)
 	}
 }
 
+/*
+ * tuplestore_updatemax
+ *		Update maxSpace field
+ */
+static void
+tuplestore_updatemax(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		state->maxSpace = Max(state->maxSpace,
+							  state->allowedMem - state->availMem);
+}
+
+/*
+ * tuplestore_storage_type_name
+ *		Return a string description of the storage method used to store the
+ *		tuples.
+ */
+const char *
+tuplestore_storage_type_name(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		return "Memory";
+	else
+		return "Disk";
+}
+
+/*
+ * tuplestore_space_used
+ *		Return the maximum space used in memory unless the tuplestore has spilled
+ *		to disk, in which case, return the disk space used.
+ */
+int64
+tuplestore_space_used(Tuplestorestate *state)
+{
+	/* First, update the maxSpace field */
+	tuplestore_updatemax(state);
+
+	if (state->status == TSS_INMEM)
+		return state->maxSpace;
+	else
+		return BufFileSize(state->myfile);
+}
+
 /*
  * tuplestore_in_memory
  *
@@ -1513,6 +1565,7 @@ writetup_heap(Tuplestorestate *state, void *tup)
 	if (state->backward)		/* need trailing length word? */
 		BufFileWrite(state->myfile, &tuplen, sizeof(tuplen));
 
+	/* no need to call tuplestore_updatemax() when not in TSS_INMEM */
 	FREEMEM(state, GetMemoryChunkSpace(tuple));
 	heap_free_minimal_tuple(tuple);
 }
diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h
index 419613c17b..3d8a90caaf 100644
--- a/src/include/utils/tuplestore.h
+++ b/src/include/utils/tuplestore.h
@@ -65,6 +65,10 @@ extern void tuplestore_copy_read_pointer(Tuplestorestate *state,
 
 extern void tuplestore_trim(Tuplestorestate *state);
 
+extern const char *tuplestore_storage_type_name(Tuplestorestate *state);
+
+extern int64 tuplestore_space_used(Tuplestorestate *state);
+
 extern bool tuplestore_in_memory(Tuplestorestate *state);
 
 extern bool tuplestore_gettupleslot(Tuplestorestate *state, bool forward,
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 7ca98397ae..1a5d5fb06b 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -2824,12 +2824,13 @@ deallocate ab_q3;
 deallocate ab_q4;
 deallocate ab_q5;
 deallocate ab_q6;
+set enable_material = 0;
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
-                                        QUERY PLAN                                         
--------------------------------------------------------------------------------------------
+                                     QUERY PLAN                                      
+-------------------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
    Update on ab_a1_b2 ab_a1_2
@@ -2850,23 +2851,22 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
                      Heap Blocks: exact=1
                      ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
                            Index Cond: (a = 1)
-         ->  Materialize (actual rows=1 loops=1)
-               ->  Append (actual rows=1 loops=1)
-                     ->  Bitmap Heap Scan on ab_a1_b1 ab_1 (actual rows=0 loops=1)
-                           Recheck Cond: (a = 1)
-                           ->  Bitmap Index Scan on ab_a1_b1_a_idx (actual rows=0 loops=1)
-                                 Index Cond: (a = 1)
-                     ->  Bitmap Heap Scan on ab_a1_b2 ab_2 (actual rows=1 loops=1)
-                           Recheck Cond: (a = 1)
-                           Heap Blocks: exact=1
-                           ->  Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
-                                 Index Cond: (a = 1)
-                     ->  Bitmap Heap Scan on ab_a1_b3 ab_3 (actual rows=0 loops=1)
-                           Recheck Cond: (a = 1)
-                           Heap Blocks: exact=1
-                           ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
-                                 Index Cond: (a = 1)
-(36 rows)
+         ->  Append (actual rows=1 loops=1)
+               ->  Bitmap Heap Scan on ab_a1_b1 ab_1 (actual rows=0 loops=1)
+                     Recheck Cond: (a = 1)
+                     ->  Bitmap Index Scan on ab_a1_b1_a_idx (actual rows=0 loops=1)
+                           Index Cond: (a = 1)
+               ->  Bitmap Heap Scan on ab_a1_b2 ab_2 (actual rows=1 loops=1)
+                     Recheck Cond: (a = 1)
+                     Heap Blocks: exact=1
+                     ->  Bitmap Index Scan on ab_a1_b2_a_idx (actual rows=1 loops=1)
+                           Index Cond: (a = 1)
+               ->  Bitmap Heap Scan on ab_a1_b3 ab_3 (actual rows=0 loops=1)
+                     Recheck Cond: (a = 1)
+                     Heap Blocks: exact=1
+                     ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
+                           Index Cond: (a = 1)
+(35 rows)
 
 table ab;
  a | b 
@@ -2879,8 +2879,8 @@ truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
-                                  QUERY PLAN                                  
-------------------------------------------------------------------------------
+                               QUERY PLAN                               
+------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
    Update on ab_a1_b2 ab_a1_2
@@ -2888,20 +2888,20 @@ update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
    InitPlan 1
      ->  Result (actual rows=1 loops=1)
    ->  Nested Loop (actual rows=3 loops=1)
+         ->  Append (actual rows=1 loops=1)
+               ->  Seq Scan on ab_a2_b1 ab_a2_1 (actual rows=1 loops=1)
+                     Filter: (b = (InitPlan 1).col1)
+               ->  Seq Scan on ab_a2_b2 ab_a2_2 (never executed)
+                     Filter: (b = (InitPlan 1).col1)
+               ->  Seq Scan on ab_a2_b3 ab_a2_3 (never executed)
+                     Filter: (b = (InitPlan 1).col1)
          ->  Append (actual rows=3 loops=1)
                ->  Seq Scan on ab_a1_b1 ab_a1_1 (actual rows=1 loops=1)
                ->  Seq Scan on ab_a1_b2 ab_a1_2 (actual rows=1 loops=1)
                ->  Seq Scan on ab_a1_b3 ab_a1_3 (actual rows=1 loops=1)
-         ->  Materialize (actual rows=1 loops=3)
-               ->  Append (actual rows=1 loops=1)
-                     ->  Seq Scan on ab_a2_b1 ab_a2_1 (actual rows=1 loops=1)
-                           Filter: (b = (InitPlan 1).col1)
-                     ->  Seq Scan on ab_a2_b2 ab_a2_2 (never executed)
-                           Filter: (b = (InitPlan 1).col1)
-                     ->  Seq Scan on ab_a2_b3 ab_a2_3 (never executed)
-                           Filter: (b = (InitPlan 1).col1)
-(19 rows)
+(18 rows)
 
+reset enable_material;
 select tableoid::regclass, * from ab;
  tableoid | a | b 
 ----------+---+---
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index a09b27d820..3e13fcf1bb 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -674,6 +674,8 @@ deallocate ab_q4;
 deallocate ab_q5;
 deallocate ab_q6;
 
+set enable_material = 0;
+
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
 explain (analyze, costs off, summary off, timing off)
@@ -685,6 +687,9 @@ truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
 explain (analyze, costs off, summary off, timing off)
 update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
+
+reset enable_material;
+
 select tableoid::regclass, * from ab;
 
 drop table ab, lprt_a;
-- 
2.34.1

v2-0002-Optimize-memory-management-and-increase-performan.patchapplication/octet-stream; name=v2-0002-Optimize-memory-management-and-increase-performan.patchDownload
From 79d89769ddb518c998b932f4b93b949535939e5d Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 21:15:01 +1200
Subject: [PATCH v2 2/2] Optimize memory management and increase performance of
 Materialize

Here we make tuplestore.c use a generation.c memory context rather than
allocating tuples into the ExecutorState memory context.  Doing that
could cause that context to become bloated when pfree'd chunks are not
reused by future tuples.  This speeds up users of tuplestore.c such as
the Materialize, WindowAgg and CTE Scan executor nodes.  Some benchmarks
have shown up to a 22% performance increase in a query containing a
Materialize node, but much higher gains are possible if the memory
reduction prevents spilling to disk.  This is especially true for
WindowAgg nodes where improvements of several thousand times are
possible.

A generation.c memory context is much better suited for this job as it
works well with FIFO palloc/pfree patterns and consumes less space as
there is no rounding allocations up to the next power-of-2 value as
there is with the aset.c context used for ExecutorState.

This also allows us to more efficiently cleanup memory used by the
tuplestore as we can reset the generation context rather than looping
over all stored tuples and pfree'ing them.

Also, remove a badly placed USEMEM call in readtup_heap().  The tuple
wasn't being allocated in the Tuplestorestate's context, so no need to
adjust the memory consumed by the tuplestore there.

Discussion: https://postgr.es/m/CAApHDvp5Py9g4Rjq7_inL3-MCK1Co2CRt_YWFwTU2zfQix0p4A%40mail.gmail.com
---
 src/backend/utils/sort/tuplestore.c | 52 ++++++++++++++++++++---------
 1 file changed, 37 insertions(+), 15 deletions(-)

diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 24bb49ca87..551f0f0a19 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -266,7 +266,11 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->availMem = state->allowedMem;
 	state->maxSpace = 0;
 	state->myfile = NULL;
-	state->context = CurrentMemoryContext;
+
+	/* palloc/pfree uses FIFO pattern, which is ideal for generation.c */
+	state->context = GenerationContextCreate(CurrentMemoryContext,
+											 "tuplestore tuples",
+											 ALLOCSET_DEFAULT_SIZES);
 	state->resowner = CurrentResourceOwner;
 
 	state->memtupdeleted = 0;
@@ -429,14 +433,38 @@ tuplestore_clear(Tuplestorestate *state)
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
-	if (state->memtuples)
+
+#ifdef USE_ASSERT_CHECKING
 	{
+		int64		availMem = state->availMem;
+
+		/*
+		 * Below, we reset the memory context for storing tuples.  To save
+		 * from having to always call GetMemoryChunkSpace() on all stored
+		 * tuples, we adjust the availMem to forget all the tuples and just
+		 * recall USEMEM for the space used by the memtuples array.  Here we
+		 * just Assert that's correct and the memory tracking hasn't gone
+		 * wrong anywhere.
+		 */
 		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-		{
-			FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i]));
-			pfree(state->memtuples[i]);
-		}
+			availMem += GetMemoryChunkSpace(state->memtuples[i]);
+
+		availMem += GetMemoryChunkSpace(state->memtuples);
+
+		Assert(availMem == state->allowedMem);
 	}
+#endif
+
+	/* clear the memory consumed by the memory tuples */
+	MemoryContextReset(state->context);
+
+	/*
+	 * Zero the used memory and re-consume the space for the memtuples array.
+	 * This saves having to FREEMEM for each stored tuple.
+	 */
+	state->availMem = state->allowedMem;
+	USEMEM(state, GetMemoryChunkSpace(state->memtuples));
+
 	state->status = TSS_INMEM;
 	state->truncated = false;
 	state->memtupdeleted = 0;
@@ -458,16 +486,11 @@ tuplestore_clear(Tuplestorestate *state)
 void
 tuplestore_end(Tuplestorestate *state)
 {
-	int			i;
-
 	if (state->myfile)
 		BufFileClose(state->myfile);
-	if (state->memtuples)
-	{
-		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-			pfree(state->memtuples[i]);
-		pfree(state->memtuples);
-	}
+
+	MemoryContextDelete(state->context);
+	pfree(state->memtuples);
 	pfree(state->readptrs);
 	pfree(state);
 }
@@ -1578,7 +1601,6 @@ readtup_heap(Tuplestorestate *state, unsigned int len)
 	MinimalTuple tuple = (MinimalTuple) palloc(tuplen);
 	char	   *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
 
-	USEMEM(state, GetMemoryChunkSpace(tuple));
 	/* read in the tuple proper */
 	tuple->t_len = tuplen;
 	BufFileReadExact(state->myfile, tupbody, tupbodylen);
-- 
2.34.1

#8Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: David Rowley (#7)
Re: Use generation memory context for tuplestore.c

On Fri, 31 May 2024 at 05:26, David Rowley <dgrowleyml@gmail.com> wrote:

On Sat, 4 May 2024 at 03:51, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

On Fri, 3 May 2024 at 15:55, David Rowley <dgrowleyml@gmail.com> wrote:

master @ 8f0a97dff
Storage: Memory Maximum Storage: 16577kB

patched:
Storage: Memory Maximum Storage: 8577kB

Those are some impressive numbers.

This patch needed to be rebased, so updated patches are attached.

Here's a review for the V2 patch:

I noticed this change to buffile.c shows up in both v1 and v2 of the
patchset, but I can't trace the reasoning why it changed with this
patch (rather than a separate bugfix):

+++ b/src/backend/storage/file/buffile.c
@@ -867,7 +867,7 @@ BufFileSize(BufFile *file)
{
int64        lastFileSize;
-    Assert(file->fileset != NULL);
+    Assert(file->files != NULL);
+++ b/src/backend/commands/explain.c
[...]
+show_material_info(MaterialState *mstate, ExplainState *es)
+    spaceUsedKB = (tuplestore_space_used(tupstore) + 1023) / 1024;

I think this should use the BYTES_TO_KILOBYTES macro for consistency.

Lastly, I think this would benefit from a test in
regress/sql/explain.sql, as the test changes that were included
removed the only occurrance of a Materialize node from the regression
tests' EXPLAIN outputs.

Kind regards,

Matthias van de Meent

#9David Rowley
dgrowleyml@gmail.com
In reply to: Matthias van de Meent (#8)
3 attachment(s)
Re: Use generation memory context for tuplestore.c

Thank you for having another look at this.

On Wed, 3 Jul 2024 at 00:20, Matthias van de Meent
<boekewurm+postgres@gmail.com> wrote:

I noticed this change to buffile.c shows up in both v1 and v2 of the
patchset, but I can't trace the reasoning why it changed with this
patch (rather than a separate bugfix):

I didn't explain that very well here, did I. I took up the discussion
about that in [1]/messages/by-id/CAApHDvofgZT0VzydhyGH5MMb-XZzNDqqAbzf1eBZV5HDm3+osQ@mail.gmail.com. (Which you've now seen)

+show_material_info(MaterialState *mstate, ExplainState *es)
+    spaceUsedKB = (tuplestore_space_used(tupstore) + 1023) / 1024;

I think this should use the BYTES_TO_KILOBYTES macro for consistency.

Yes, that needs to be done. Thank you.

Lastly, I think this would benefit from a test in
regress/sql/explain.sql, as the test changes that were included
removed the only occurrance of a Materialize node from the regression
tests' EXPLAIN outputs.

I've modified the tests where the previous patch disabled
enable_material to enable it again and mask out the possibly unstable
part. Do you think that's an ok level of testing?

David

[1]: /messages/by-id/CAApHDvofgZT0VzydhyGH5MMb-XZzNDqqAbzf1eBZV5HDm3+osQ@mail.gmail.com

Attachments:

v3-0001-Remove-incorrect-Asserts-in-buffile.c.patchapplication/octet-stream; name=v3-0001-Remove-incorrect-Asserts-in-buffile.c.patchDownload
From 1dd647d53d38aaabcd4cef0ece4e556297d69729 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Wed, 3 Jul 2024 18:07:58 +1200
Subject: [PATCH v3 1/3] Remove incorrect Asserts in buffile.c

Both BufFileSize() and BufFileAppend() contained Asserts to ensure the
given BufFile(s) had a valid fileset.  A valid fileset isn't required in
either of these functions, so remove the Asserts.

Discussion: https://postgr.es/m/CAApHDvofgZT0VzydhyGH5MMb-XZzNDqqAbzf1eBZV5HDm3%2BosQ%40mail.gmail.com
---
 src/backend/storage/file/buffile.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

diff --git a/src/backend/storage/file/buffile.c b/src/backend/storage/file/buffile.c
index a263875fd5..5535e81214 100644
--- a/src/backend/storage/file/buffile.c
+++ b/src/backend/storage/file/buffile.c
@@ -857,9 +857,9 @@ BufFileSeekBlock(BufFile *file, int64 blknum)
 }
 
 /*
- * Return the current fileset based BufFile size.
+ * Returns the size if the given BufFile in bytes.
  *
- * Counts any holes left behind by BufFileAppend as part of the size.
+ * Returned value includes the size of any holes left behind by BufFileAppend.
  * ereport()s on failure.
  */
 int64
@@ -867,8 +867,6 @@ BufFileSize(BufFile *file)
 {
 	int64		lastFileSize;
 
-	Assert(file->fileset != NULL);
-
 	/* Get the size of the last physical file. */
 	lastFileSize = FileSize(file->files[file->numFiles - 1]);
 	if (lastFileSize < 0)
@@ -883,8 +881,7 @@ BufFileSize(BufFile *file)
 }
 
 /*
- * Append the contents of source file (managed within fileset) to
- * end of target file (managed within same fileset).
+ * Append the contents of source file to end of target file.
  *
  * Note that operation subsumes ownership of underlying resources from
  * "source".  Caller should never call BufFileClose against source having
@@ -908,10 +905,8 @@ BufFileAppend(BufFile *target, BufFile *source)
 	int			newNumFiles = target->numFiles + source->numFiles;
 	int			i;
 
-	Assert(target->fileset != NULL);
 	Assert(source->readOnly);
 	Assert(!source->dirty);
-	Assert(source->fileset != NULL);
 
 	if (target->resowner != source->resowner)
 		elog(ERROR, "could not append BufFile with non-matching resource owner");
-- 
2.34.1

v3-0002-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchapplication/octet-stream; name=v3-0002-Add-memory-disk-usage-for-Material-in-EXPLAIN-ANA.patchDownload
From 6d9beec81499e0dd8998e4bd9a8e88965b26ae56 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 20:17:39 +1200
Subject: [PATCH v3 2/3] Add memory/disk usage for Material in EXPLAIN ANALYZE

Up until now, there was no ability to easily determine if a Material
node caused the underlying tuplestore to spill to disk or even see how
much memory the tuplestore used if it didn't.

Here we add some new functions to tuplestore.c to query this information
and add some additional output in EXPLAIN ANALYZE to display this
information.
---
 src/backend/commands/explain.c                | 37 +++++++++++++
 src/backend/utils/sort/tuplestore.c           | 53 +++++++++++++++++++
 src/include/utils/tuplestore.h                |  4 ++
 src/test/regress/expected/partition_prune.out | 37 ++++++++++---
 src/test/regress/sql/partition_prune.sql      | 29 ++++++++--
 5 files changed, 148 insertions(+), 12 deletions(-)

diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 94511a5a02..abe1362ac6 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -125,6 +125,7 @@ static void show_sort_info(SortState *sortstate, ExplainState *es);
 static void show_incremental_sort_info(IncrementalSortState *incrsortstate,
 									   ExplainState *es);
 static void show_hash_info(HashState *hashstate, ExplainState *es);
+static void show_material_info(MaterialState *mstate, ExplainState *es);
 static void show_memoize_info(MemoizeState *mstate, List *ancestors,
 							  ExplainState *es);
 static void show_hashagg_info(AggState *aggstate, ExplainState *es);
@@ -2248,6 +2249,9 @@ ExplainNode(PlanState *planstate, List *ancestors,
 		case T_Hash:
 			show_hash_info(castNode(HashState, planstate), es);
 			break;
+		case T_Material:
+			show_material_info(castNode(MaterialState, planstate), es);
+			break;
 		case T_Memoize:
 			show_memoize_info(castNode(MemoizeState, planstate), ancestors,
 							  es);
@@ -3319,6 +3323,39 @@ show_hash_info(HashState *hashstate, ExplainState *es)
 	}
 }
 
+/*
+ * Show information on material node, storage method and maximum memory/disk
+ * space used.
+ */
+static void
+show_material_info(MaterialState *mstate, ExplainState *es)
+{
+	Tuplestorestate *tupstore;
+	const char *storageType;
+	int64		spaceUsedKB;
+
+	if (!es->analyze)
+		return;
+
+	tupstore = mstate->tuplestorestate;
+	storageType = tuplestore_storage_type_name(tupstore);
+	spaceUsedKB = BYTES_TO_KILOBYTES(tuplestore_space_used(tupstore));
+
+	if (es->format != EXPLAIN_FORMAT_TEXT)
+	{
+		ExplainPropertyText("Storage", storageType, es);
+		ExplainPropertyInteger("Maximum Storage", "kB", spaceUsedKB, es);
+	}
+	else
+	{
+		ExplainIndentText(es);
+		appendStringInfo(es->str,
+						 "Storage: %s  Maximum Storage: " INT64_FORMAT "kB\n",
+						 storageType,
+						 spaceUsedKB);
+	}
+}
+
 /*
  * Show information on memoize hits/misses/evictions and memory usage.
  */
diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 947a868e56..24bb49ca87 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -109,6 +109,7 @@ struct Tuplestorestate
 	bool		truncated;		/* tuplestore_trim has removed tuples? */
 	int64		availMem;		/* remaining memory available, in bytes */
 	int64		allowedMem;		/* total memory allowed, in bytes */
+	int64		maxSpace;		/* maximum space used in memory */
 	int64		tuples;			/* number of tuples added */
 	BufFile    *myfile;			/* underlying file, or NULL if none */
 	MemoryContext context;		/* memory context for holding tuples */
@@ -238,6 +239,7 @@ static Tuplestorestate *tuplestore_begin_common(int eflags,
 												int maxKBytes);
 static void tuplestore_puttuple_common(Tuplestorestate *state, void *tuple);
 static void dumptuples(Tuplestorestate *state);
+static void tuplestore_updatemax(Tuplestorestate *state);
 static unsigned int getlen(Tuplestorestate *state, bool eofOK);
 static void *copytup_heap(Tuplestorestate *state, void *tup);
 static void writetup_heap(Tuplestorestate *state, void *tup);
@@ -262,6 +264,7 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->truncated = false;
 	state->allowedMem = maxKBytes * 1024L;
 	state->availMem = state->allowedMem;
+	state->maxSpace = 0;
 	state->myfile = NULL;
 	state->context = CurrentMemoryContext;
 	state->resowner = CurrentResourceOwner;
@@ -420,6 +423,9 @@ tuplestore_clear(Tuplestorestate *state)
 	int			i;
 	TSReadPointer *readptr;
 
+	/* update the maxSpace before doing any USEMEM/FREEMEM adjustments */
+	tuplestore_updatemax(state);
+
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
@@ -1402,6 +1408,9 @@ tuplestore_trim(Tuplestorestate *state)
 	Assert(nremove >= state->memtupdeleted);
 	Assert(nremove <= state->memtupcount);
 
+	/* before freeing any memory, update maxSpace */
+	tuplestore_updatemax(state);
+
 	/* Release no-longer-needed tuples */
 	for (i = state->memtupdeleted; i < nremove; i++)
 	{
@@ -1444,6 +1453,49 @@ tuplestore_trim(Tuplestorestate *state)
 	}
 }
 
+/*
+ * tuplestore_updatemax
+ *		Update maxSpace field
+ */
+static void
+tuplestore_updatemax(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		state->maxSpace = Max(state->maxSpace,
+							  state->allowedMem - state->availMem);
+}
+
+/*
+ * tuplestore_storage_type_name
+ *		Return a string description of the storage method used to store the
+ *		tuples.
+ */
+const char *
+tuplestore_storage_type_name(Tuplestorestate *state)
+{
+	if (state->status == TSS_INMEM)
+		return "Memory";
+	else
+		return "Disk";
+}
+
+/*
+ * tuplestore_space_used
+ *		Return the maximum space used in memory unless the tuplestore has spilled
+ *		to disk, in which case, return the disk space used.
+ */
+int64
+tuplestore_space_used(Tuplestorestate *state)
+{
+	/* First, update the maxSpace field */
+	tuplestore_updatemax(state);
+
+	if (state->status == TSS_INMEM)
+		return state->maxSpace;
+	else
+		return BufFileSize(state->myfile);
+}
+
 /*
  * tuplestore_in_memory
  *
@@ -1513,6 +1565,7 @@ writetup_heap(Tuplestorestate *state, void *tup)
 	if (state->backward)		/* need trailing length word? */
 		BufFileWrite(state->myfile, &tuplen, sizeof(tuplen));
 
+	/* no need to call tuplestore_updatemax() when not in TSS_INMEM */
 	FREEMEM(state, GetMemoryChunkSpace(tuple));
 	heap_free_minimal_tuple(tuple);
 }
diff --git a/src/include/utils/tuplestore.h b/src/include/utils/tuplestore.h
index 419613c17b..3d8a90caaf 100644
--- a/src/include/utils/tuplestore.h
+++ b/src/include/utils/tuplestore.h
@@ -65,6 +65,10 @@ extern void tuplestore_copy_read_pointer(Tuplestorestate *state,
 
 extern void tuplestore_trim(Tuplestorestate *state);
 
+extern const char *tuplestore_storage_type_name(Tuplestorestate *state);
+
+extern int64 tuplestore_space_used(Tuplestorestate *state);
+
 extern bool tuplestore_in_memory(Tuplestorestate *state);
 
 extern bool tuplestore_gettupleslot(Tuplestorestate *state, bool forward,
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 7ca98397ae..7a03b4e360 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -1,6 +1,24 @@
 --
 -- Test partitioning planner code
 --
+-- Helper function which can be used for masking out portions of EXPLAIN
+-- ANALYZE which could contain information that's not consistent on all
+-- platforms.
+create function explain_analyze(query text) returns setof text
+language plpgsql as
+$$
+declare
+    ln text;
+begin
+    for ln in
+        execute format('explain (analyze, costs off, summary off, timing off) %s',
+            query)
+    loop
+        ln := regexp_replace(ln, 'Maximum Storage: \d+', 'Maximum Storage: N');
+        return next ln;
+    end loop;
+end;
+$$;
 -- Force generic plans to be used for all prepared statements in this file.
 set plan_cache_mode = force_generic_plan;
 create table lp (a char) partition by list (a);
@@ -2826,9 +2844,9 @@ deallocate ab_q5;
 deallocate ab_q6;
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
-explain (analyze, costs off, summary off, timing off)
-update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
-                                        QUERY PLAN                                         
+select explain_analyze('
+update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;');
+                                      explain_analyze                                      
 -------------------------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
@@ -2851,6 +2869,7 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
                      ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
                            Index Cond: (a = 1)
          ->  Materialize (actual rows=1 loops=1)
+               Storage: Memory  Maximum Storage: NkB
                ->  Append (actual rows=1 loops=1)
                      ->  Bitmap Heap Scan on ab_a1_b1 ab_1 (actual rows=0 loops=1)
                            Recheck Cond: (a = 1)
@@ -2866,7 +2885,7 @@ update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
                            Heap Blocks: exact=1
                            ->  Bitmap Index Scan on ab_a1_b3_a_idx (actual rows=1 loops=1)
                                  Index Cond: (a = 1)
-(36 rows)
+(37 rows)
 
 table ab;
  a | b 
@@ -2877,9 +2896,9 @@ table ab;
 -- Test UPDATE where source relation has run-time pruning enabled
 truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
-explain (analyze, costs off, summary off, timing off)
-update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
-                                  QUERY PLAN                                  
+select explain_analyze('
+update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);');
+                               explain_analyze                                
 ------------------------------------------------------------------------------
  Update on ab_a1 (actual rows=0 loops=1)
    Update on ab_a1_b1 ab_a1_1
@@ -2893,6 +2912,7 @@ update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
                ->  Seq Scan on ab_a1_b2 ab_a1_2 (actual rows=1 loops=1)
                ->  Seq Scan on ab_a1_b3 ab_a1_3 (actual rows=1 loops=1)
          ->  Materialize (actual rows=1 loops=3)
+               Storage: Memory  Maximum Storage: NkB
                ->  Append (actual rows=1 loops=1)
                      ->  Seq Scan on ab_a2_b1 ab_a2_1 (actual rows=1 loops=1)
                            Filter: (b = (InitPlan 1).col1)
@@ -2900,7 +2920,7 @@ update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
                            Filter: (b = (InitPlan 1).col1)
                      ->  Seq Scan on ab_a2_b3 ab_a2_3 (never executed)
                            Filter: (b = (InitPlan 1).col1)
-(19 rows)
+(20 rows)
 
 select tableoid::regclass, * from ab;
  tableoid | a | b 
@@ -4419,3 +4439,4 @@ explain (costs off) select * from hp_contradict_test where a === 1 and b === 1 a
 drop table hp_contradict_test;
 drop operator class part_test_int4_ops2 using hash;
 drop operator ===(int4, int4);
+drop function explain_analyze(text);
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index a09b27d820..442428d937 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -2,6 +2,25 @@
 -- Test partitioning planner code
 --
 
+-- Helper function which can be used for masking out portions of EXPLAIN
+-- ANALYZE which could contain information that's not consistent on all
+-- platforms.
+create function explain_analyze(query text) returns setof text
+language plpgsql as
+$$
+declare
+    ln text;
+begin
+    for ln in
+        execute format('explain (analyze, costs off, summary off, timing off) %s',
+            query)
+    loop
+        ln := regexp_replace(ln, 'Maximum Storage: \d+', 'Maximum Storage: N');
+        return next ln;
+    end loop;
+end;
+$$;
+
 -- Force generic plans to be used for all prepared statements in this file.
 set plan_cache_mode = force_generic_plan;
 
@@ -676,15 +695,15 @@ deallocate ab_q6;
 
 -- UPDATE on a partition subtree has been seen to have problems.
 insert into ab values (1,2);
-explain (analyze, costs off, summary off, timing off)
-update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;
+select explain_analyze('
+update ab_a1 set b = 3 from ab where ab.a = 1 and ab.a = ab_a1.a;');
 table ab;
 
 -- Test UPDATE where source relation has run-time pruning enabled
 truncate ab;
 insert into ab values (1, 1), (1, 2), (1, 3), (2, 1);
-explain (analyze, costs off, summary off, timing off)
-update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);
+select explain_analyze('
+update ab_a1 set b = 3 from ab_a2 where ab_a2.b = (select 1);');
 select tableoid::regclass, * from ab;
 
 drop table ab, lprt_a;
@@ -1318,3 +1337,5 @@ explain (costs off) select * from hp_contradict_test where a === 1 and b === 1 a
 drop table hp_contradict_test;
 drop operator class part_test_int4_ops2 using hash;
 drop operator ===(int4, int4);
+
+drop function explain_analyze(text);
-- 
2.34.1

v3-0003-Optimize-memory-management-and-increase-performan.patchapplication/octet-stream; name=v3-0003-Optimize-memory-management-and-increase-performan.patchDownload
From b4e51dde2670dac744371c3a5b37177a2c307a59 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Fri, 3 May 2024 21:15:01 +1200
Subject: [PATCH v3 3/3] Optimize memory management and increase performance of
 Materialize

Here we make tuplestore.c use a generation.c memory context rather than
allocating tuples into the ExecutorState memory context.  Doing that
could cause that context to become bloated when pfree'd chunks are not
reused by future tuples.  This speeds up users of tuplestore.c such as
the Materialize, WindowAgg and CTE Scan executor nodes.  Some benchmarks
have shown up to a 22% performance increase in a query containing a
Materialize node, but much higher gains are possible if the memory
reduction prevents spilling to disk.  This is especially true for
WindowAgg nodes where improvements of several thousand times are
possible.

A generation.c memory context is much better suited for this job as it
works well with FIFO palloc/pfree patterns and consumes less space as
there is no rounding allocations up to the next power-of-2 value as
there is with the aset.c context used for ExecutorState.

This also allows us to more efficiently cleanup memory used by the
tuplestore as we can reset the generation context rather than looping
over all stored tuples and pfree'ing them.

Also, remove a badly placed USEMEM call in readtup_heap().  The tuple
wasn't being allocated in the Tuplestorestate's context, so no need to
adjust the memory consumed by the tuplestore there.

Discussion: https://postgr.es/m/CAApHDvp5Py9g4Rjq7_inL3-MCK1Co2CRt_YWFwTU2zfQix0p4A%40mail.gmail.com
---
 src/backend/utils/sort/tuplestore.c | 52 ++++++++++++++++++++---------
 1 file changed, 37 insertions(+), 15 deletions(-)

diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c
index 24bb49ca87..551f0f0a19 100644
--- a/src/backend/utils/sort/tuplestore.c
+++ b/src/backend/utils/sort/tuplestore.c
@@ -266,7 +266,11 @@ tuplestore_begin_common(int eflags, bool interXact, int maxKBytes)
 	state->availMem = state->allowedMem;
 	state->maxSpace = 0;
 	state->myfile = NULL;
-	state->context = CurrentMemoryContext;
+
+	/* palloc/pfree uses FIFO pattern, which is ideal for generation.c */
+	state->context = GenerationContextCreate(CurrentMemoryContext,
+											 "tuplestore tuples",
+											 ALLOCSET_DEFAULT_SIZES);
 	state->resowner = CurrentResourceOwner;
 
 	state->memtupdeleted = 0;
@@ -429,14 +433,38 @@ tuplestore_clear(Tuplestorestate *state)
 	if (state->myfile)
 		BufFileClose(state->myfile);
 	state->myfile = NULL;
-	if (state->memtuples)
+
+#ifdef USE_ASSERT_CHECKING
 	{
+		int64		availMem = state->availMem;
+
+		/*
+		 * Below, we reset the memory context for storing tuples.  To save
+		 * from having to always call GetMemoryChunkSpace() on all stored
+		 * tuples, we adjust the availMem to forget all the tuples and just
+		 * recall USEMEM for the space used by the memtuples array.  Here we
+		 * just Assert that's correct and the memory tracking hasn't gone
+		 * wrong anywhere.
+		 */
 		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-		{
-			FREEMEM(state, GetMemoryChunkSpace(state->memtuples[i]));
-			pfree(state->memtuples[i]);
-		}
+			availMem += GetMemoryChunkSpace(state->memtuples[i]);
+
+		availMem += GetMemoryChunkSpace(state->memtuples);
+
+		Assert(availMem == state->allowedMem);
 	}
+#endif
+
+	/* clear the memory consumed by the memory tuples */
+	MemoryContextReset(state->context);
+
+	/*
+	 * Zero the used memory and re-consume the space for the memtuples array.
+	 * This saves having to FREEMEM for each stored tuple.
+	 */
+	state->availMem = state->allowedMem;
+	USEMEM(state, GetMemoryChunkSpace(state->memtuples));
+
 	state->status = TSS_INMEM;
 	state->truncated = false;
 	state->memtupdeleted = 0;
@@ -458,16 +486,11 @@ tuplestore_clear(Tuplestorestate *state)
 void
 tuplestore_end(Tuplestorestate *state)
 {
-	int			i;
-
 	if (state->myfile)
 		BufFileClose(state->myfile);
-	if (state->memtuples)
-	{
-		for (i = state->memtupdeleted; i < state->memtupcount; i++)
-			pfree(state->memtuples[i]);
-		pfree(state->memtuples);
-	}
+
+	MemoryContextDelete(state->context);
+	pfree(state->memtuples);
 	pfree(state->readptrs);
 	pfree(state);
 }
@@ -1578,7 +1601,6 @@ readtup_heap(Tuplestorestate *state, unsigned int len)
 	MinimalTuple tuple = (MinimalTuple) palloc(tuplen);
 	char	   *tupbody = (char *) tuple + MINIMAL_TUPLE_DATA_OFFSET;
 
-	USEMEM(state, GetMemoryChunkSpace(tuple));
 	/* read in the tuple proper */
 	tuple->t_len = tuplen;
 	BufFileReadExact(state->myfile, tupbody, tupbodylen);
-- 
2.34.1

#10Alexander Lakhin
exclusion@gmail.com
In reply to: David Rowley (#9)
Re: Use generation memory context for tuplestore.c

Hello David,

03.07.2024 13:41, David Rowley wrote:

Lastly, I think this would benefit from a test in
regress/sql/explain.sql, as the test changes that were included
removed the only occurrance of a Materialize node from the regression
tests' EXPLAIN outputs.

I've modified the tests where the previous patch disabled
enable_material to enable it again and mask out the possibly unstable
part. Do you think that's an ok level of testing?

Please look at a segfault crash introduced with 1eff8279d:
CREATE TABLE t1(i int);
CREATE TABLE t2(i int) PARTITION BY RANGE (i);
CREATE TABLE t2p PARTITION OF t2 FOR VALUES FROM (1) TO (2);

EXPLAIN ANALYZE SELECT * FROM t1 JOIN t2 ON t1.i > t2.i;

Leads to:
Core was generated by `postgres: law regression [local] EXPLAIN                                      '.
Program terminated with signal SIGSEGV, Segmentation fault.

#0  0x000055c36dbac2f7 in tuplestore_storage_type_name (state=0x0) at tuplestore.c:1476
1476            if (state->status == TSS_INMEM)

Best regards,
Alexander

#11David Rowley
dgrowleyml@gmail.com
In reply to: Alexander Lakhin (#10)
Re: Use generation memory context for tuplestore.c

On Fri, 5 Jul 2024 at 16:00, Alexander Lakhin <exclusion@gmail.com> wrote:

Please look at a segfault crash introduced with 1eff8279d:
CREATE TABLE t1(i int);
CREATE TABLE t2(i int) PARTITION BY RANGE (i);
CREATE TABLE t2p PARTITION OF t2 FOR VALUES FROM (1) TO (2);

EXPLAIN ANALYZE SELECT * FROM t1 JOIN t2 ON t1.i > t2.i;

Leads to:
Core was generated by `postgres: law regression [local] EXPLAIN '.
Program terminated with signal SIGSEGV, Segmentation fault.

#0 0x000055c36dbac2f7 in tuplestore_storage_type_name (state=0x0) at tuplestore.c:1476
1476 if (state->status == TSS_INMEM)

Thanks for the report. I've just pushed a fix in 53abb1e0e.

David

#12David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#9)
Re: Use generation memory context for tuplestore.c

On Wed, 3 Jul 2024 at 22:41, David Rowley <dgrowleyml@gmail.com> wrote:

On Wed, 3 Jul 2024 at 00:20, Matthias van de Meent

Lastly, I think this would benefit from a test in
regress/sql/explain.sql, as the test changes that were included
removed the only occurrance of a Materialize node from the regression
tests' EXPLAIN outputs.

I've modified the tests where the previous patch disabled
enable_material to enable it again and mask out the possibly unstable
part. Do you think that's an ok level of testing?

I spent quite a bit more time today looking at these patches. Mostly
that amounted to polishing comments more.

I've pushed them both now.

Thank you both of you for reviewing these.

David

#13Alexander Lakhin
exclusion@gmail.com
In reply to: David Rowley (#11)
Re: Use generation memory context for tuplestore.c

05.07.2024 07:57, David Rowley wrote:

Thanks for the report. I've just pushed a fix in 53abb1e0e.

Thank you, David!

Please look at another anomaly introduced with 590b045c3:
echo "
CREATE TABLE t(f int, t int);
INSERT INTO t VALUES (1, 1);

WITH RECURSIVE sg(f, t) AS (
SELECT * FROM t t1
UNION ALL
SELECT t2.* FROM t t2, sg WHERE t2.f = sg.t
) SEARCH DEPTH FIRST BY f, t SET seq
SELECT * FROM sg;
" | timeout 60 psql

triggers
TRAP: failed Assert("chunk->requested_size < oldsize"), File: "generation.c", Line: 842, PID: 830294

Best regards,
Alexander

#14David Rowley
dgrowleyml@gmail.com
In reply to: Alexander Lakhin (#13)
1 attachment(s)
Re: Use generation memory context for tuplestore.c

On Sat, 6 Jul 2024 at 02:00, Alexander Lakhin <exclusion@gmail.com> wrote:

CREATE TABLE t(f int, t int);
INSERT INTO t VALUES (1, 1);

WITH RECURSIVE sg(f, t) AS (
SELECT * FROM t t1
UNION ALL
SELECT t2.* FROM t t2, sg WHERE t2.f = sg.t
) SEARCH DEPTH FIRST BY f, t SET seq
SELECT * FROM sg;
" | timeout 60 psql

triggers
TRAP: failed Assert("chunk->requested_size < oldsize"), File: "generation.c", Line: 842, PID: 830294

This seems to be a bug in GenerationRealloc().

What's happening is when we palloc(4) for the files array in
makeBufFile(), that palloc uses GenerationAlloc() and since we have
MEMORY_CONTEXT_CHECKING, the code does:

/* ensure there's always space for the sentinel byte */
chunk_size = MAXALIGN(size + 1);

resulting in chunk_size == 8. When extendBufFile() effectively does
the repalloc(file->files, 8), we call GenerationRealloc() with those 8
bytes and go into the "if (oldsize >= size)" path thinking we have
enough space already. Here both values are 8, which would be fine on
non-MEMORY_CONTEXT_CHECKING builds, but there's no space for the
sentinel byte here. set_sentinel(pointer, size) stomps on some memory,
but no crash from that. It's only a problem when extendBufFile() asks
for 12 bytes that we come back into GenerationRealloc() and trigger
the Assert(chunk->requested_size < oldsize). Both of these values are
8. The oldsize should have been large enough to store the sentinel
byte, it isn't due to the problem caused during GenerationRealloc with
8 bytes.

I also had not intended that the buffile.c stuff would use the
generation context. I'll need to fix that too, but I think I'll fix
the GenerationRealloc() first.

The attached fixes the issue. I'll stare at it a bit more and try to
decide if that's the best way to fix it.

David

Attachments:

GenerationRealloc_fix.patchapplication/octet-stream; name=GenerationRealloc_fix.patchDownload
diff --git a/src/backend/utils/mmgr/generation.c b/src/backend/utils/mmgr/generation.c
index b858b8d0f7..a0217adbf5 100644
--- a/src/backend/utils/mmgr/generation.c
+++ b/src/backend/utils/mmgr/generation.c
@@ -855,7 +855,12 @@ GenerationRealloc(void *pointer, Size size, int flags)
 	 *
 	 * XXX Perhaps we should annotate this condition with unlikely()?
 	 */
+#ifdef MEMORY_CONTEXT_CHECKING
+	/* With MEMORY_CONTEXT_CHECKING we need an extra byte for the sentinel */
+	if (oldsize > size)
+#else
 	if (oldsize >= size)
+#endif
 	{
 #ifdef MEMORY_CONTEXT_CHECKING
 		Size		oldrequest = chunk->requested_size;
#15David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#14)
Re: Use generation memory context for tuplestore.c

On Sat, 6 Jul 2024 at 12:08, David Rowley <dgrowleyml@gmail.com> wrote:

The attached fixes the issue. I'll stare at it a bit more and try to
decide if that's the best way to fix it.

I did that staring work and thought about arranging the code to reduce
the number of #ifdefs. In the end, I decided it was better to keep the
two "if" checks close together so that it's easy to see that one does

and the other >=. Someone else's tastes may vary.

I adjusted the comment to remove the >= mention and pushed the
resulting patch and backpatched to 16, where I broke this in
0e480385e.

Thanks for the report.

David

David

#16David Rowley
dgrowleyml@gmail.com
In reply to: David Rowley (#14)
Re: Use generation memory context for tuplestore.c

On Sat, 6 Jul 2024 at 12:08, David Rowley <dgrowleyml@gmail.com> wrote:

I also had not intended that the buffile.c stuff would use the
generation context. I'll need to fix that too, but I think I'll fix
the GenerationRealloc() first.

I've pushed a fix for that now too.

David