A case for GIST supporting ORDER BY

Started by Michał Kłeczekabout 2 years ago5 messages
#1Michał Kłeczek
michal@kleczek.org
1 attachment(s)

Hi,

Some time ago I’ve provided some details with the issues we face when trying to use GIST and partitioning at the same time in the postgresql-general mailing list:
/messages/by-id/3FA1E0A9-8393-41F6-88BD-62EEEA1EC21F@kleczek.org%EF%BF%BC
GIST index and ORDER BY
postgresql.org

We decided to go with the solution to partition our table by:

RANGE (‘2100-01-01' <-> operation_date).

While it (somewhat) solves partition pruning issues described above there is another problem:
It is impossible to create a unique constraint on the partitioned table.

So now we cannot use INSERT … ON CONFLICT (…) DO UPDATE

My question to hackers:
Would it be feasible to implement ORDER BY column GIST index (only) scan for types with total order and sensible greatest and least values?

Thanks,
Michal

Attachments:

elephant.pngimage/png; name=elephant.png; x-unix-mode=0666Download
�PNG


IHDR��es�	pHYs��tEXtCommentCreated with The GIMP�d%n IDATx���_Hi�?�g��������cOj
�$7���E���.�t���zv����=����e���U6B��F!���3�2��iR�8X�SIw2���x�����"V����U��V���N���Lbw}�}�����7o�g�7�b���k]�{K��_~!�0>��b�H�aL�u]���E���t����4m�����(J�������@��B�e���}�+
un9������������Gw ��{�e�Z��#���^!�-�����zzz�_�l�����$B�
��>],/�|��)Y�e��O{���eTU��(����7�� #B����t]��C�a��b���k����:�����(���UE�u��6�Y��g�0����v��N_
PU5�(
�����i3�������j�v��i{��0?���(qUU����J����2���}P1UUKC"�M�����������4M�A�S�"B�2����O x���03�]�e�t]�����O���iqD�B�=�K$����DDv��R���������J�~�����s�J~]s7��a|�������u]>����Qb
RB O���a��b�����X,��,��`i�^��YQ���u}Z����X��o�@�B4m����h4�4� B�������eY��w���j!|�D���9p�)
�===D���I�kQ�`:�F�SU5�����C
�|�4��:{���s<q�aR�]��?���3���o �'�=�)���a�F�t��N�2�g����P�y�����(������������	(	;�^O��r1G��eY!�0��a��� x����~P��jAQ��(�5&�N�caa!�N���
�������B8�!�4Jw~���]8n�iZ��}h�Ux�|x�}lyy�A>e?���������@`��D(��!���]i�{��)Z�Kd�'�n��Am@Cg!��U(	�;,��j��EQ��9k`3��t:}�}v8DC�
!8
%a�I����(���N�����T<�@������)�}��pT�P�b�H���caa!��:�>a{G��,�`z��x��}��HH��x?�B��l��M���e�8�(?]������������R(!g�����qM���S�qI�0�o����t:�RP�SU5>88�]C�!�`���?�A��I���)����3�3�������	��@ p!����!��@;C`F�JQ; ���A�e�����d2�PC4M�b| �*�&pjj
g��4M�o���i��2�����LMM���4M����eYx��Q���GFFPNZ�kH�X�t:�&�L"�/�g{zz�`YV(�L>K�R(�EQ���Q  UU��^{{{!<(��?(����"���L��z������{�������V���=�5 �J�A9(�"EQ��H����\:��G2��1�<TU�R������3CD��z[���d�H��z�>}J�b����cb�X|dd�f�7k
�O�C ��E�G����A,��J���l �v���iD�>�i����WA�������kF�2:/�����qn��}%�Gc��~��W�y��,+4::����iZ�.�<~�8)�2��'�aW-�����r���/���i�����W�N�>�@gh�����H�4��B�u}zjj�7�J���A�@�����vigOO���g��p�AQ�u�(V���=���c�?�����./�u}ztt���SU5��*�_��u}faa��0�����@0�B���BGGG���H��CA��h�WU����Q�	;X���aY{'���C0�B�(�t���7�de����r�E8:��p{{;��z��;xBet]�1�waa�t]���.�h4>>>����@(9��_4�w]{3D(��(qUU����TU����0�����F@�	�*�	�PRvD�oQU5����Xi�a�

�F�a�
�MUU���aT,?��v�|��V�>�W2og���aW���%���_�v�7�����%� �������#�C�T��I�3�������	g��b�x���X,^X^^����:m����]����S�F�����_:�.����fZ�?��@����H��k�~#�Z�`��(�4::����5��!EQ����9�����r�V�����7���;�������GJ��}�����jMu���eY�O�>�_[|�3�===��D_�����SSS���<
EQ����h<#1B��,�y��
��������y [S����,�/%��}������w�������h���4�T�����l�`w�<~�x���j��+��������@ pA������F�(�I�Rt��}J�����A�����$�J�P ��U�>�c����_��~q�u}�hg���#����p�=���n�b?���YPU���vX\XX��wE�}��@���+4���R��pdd$���rA @������^���.��4��?�QU��K`���tD+�� r0��eY�g���`)����^-�CEQ�������`o��,�



=���r��,�}iaa��>��n�4�>��u�=����h�h�Y@���R)����}�R������D�g���;Jw����F(:B��aW
�����@�<#T���/�����R)_?��'	t#��e�t�CCCA?�����]
vU�&.PE��PZ{��taaa!h}��Wt��5������LMM���i_�@7Rq]R,i``�M-������`��u}������e2���.�A�T��,�JQ2�����k���GFF�t����C}���Z�C��:�@�0���d���v
������4���@� ��B���#�k�6n�b�e}���3�$zB ��n��A�d�Wg
��h|rr��.C t��wUU����� ��0�����^^^&]�}���eh
��t��L&�~y���B�!V����vD)(��N�v���~�d�(J|pp�eY�����R��/�;�[��*���l�eW7�����,,,�n���rW^�X,�����@��GW��q�����D��
�Ez��'.�@�B,k���G9(x�]f�����X!EQ��X�����0��FGG���H��@xD�a|s����^?��iZ���g��w���j|pp�5 k��������[���J�htt��g�UU�ONN^UU�o��������o���<��c�bj�]b�3��i�AY(�������][�h������y���x�|uj���pKp���B���|��������Pp��
���p||<~������/C ,����c��t:]XXX��!z�g�R�X,>22�B���j����_��^�|��f^��qknj���w�G;8b�]^�h8S�C������m/�8F����� v�a�B�����K��_�|��|��vG��-2s���I���w���������$��sR�


y��0\�w��c4�9:�x��(n�*�������{��{��f���������<i����������p575R��F�>��X9/7��'	���>�����Q���| ��Jw�V.� �3W�z��j����]��?��I�>�x���>kjXok	���b�FGG)�Hx�=���Y�{�����L��x��` �p���������k�t�p���������@��d���j��4s/�����;��w��:��B��c3�z�����{EQ����C�2 ��,+t���g^)�v�Z|||\�e��0�NMM�����dP/nj*41��Vs2�w���475R8����t:���]���>3::���������X,�� n3��s����j�Q ���H��������a �022�z��5�e|)k�oe'�DoKM;�-�{�bG�X,���D(�!y�y��i���IAI��p�k��o��pO"5G����)
�}�;D_��v�PU����q�p5S�������2���R�9��F������UUUo;�=a'�cd��6_ou���Gz
��i���sW��!��#}y
�B��M��n!Mm��3��e}100��+e��@������
w��@({'Q���G*��d2YqY)^��5�����t����������I��_�nky���-���c���`���5�{�N�CCCA����\�N5���-i��Y�e���v�*� z#������Ur�0��������yZ�8{��A�-�����-�n��v7�+�B0�r�CA�t���p844D7n���������B��@(sDy�s���v�H�6��M��YS��_�7zDD�55�775&�$����/�����R�=�+�/D�������n��`��:�-�P_Gm�����v8�����H�z�"�'k�1�aWn����0�h4>99Y��
k.��D������\!�m�.AsS#5k���_�-Dy���,R��z�X|��1o�����<��n��d����
���r�p��s8::J7n�X��i#���P ,�t���72zUU5>99�&��������207���t[�����I��ZyR�E�a���Afqe=���5k��s�(
RsS#������xD���V/�P�p(H}���H��V���&�4���f35��"�;w���[����t7��}v�jiX�� pB���E1:���2a\T"�}���Jo��A���R�����
�h��D_7�BY� v���e����\����@ ��p��RT��S�\�K_^_zh����u�[�t[�[�����Z�7gI7�D_xLsS#E�<E�K������bR��s��IW&Z�g����j�����Mg����HtcmF7�{1���� �~;�q�����y���Tb��/��0�~dd$�H$j&�:��@�d+�&:�;�����H�P������d� �u������D�q+�`��M��{^�]#/t"�W����P�0�iZ�����/�u�	Bb�1s���yc	?�@���ig��4����3����P���:��OP"vQ��8J����X,>>>�������A�7��,����z+�K�a�����������s�p�p(H�������<����T�3�B�F���=4�N6em8Sc)|���������%����L"� yK��f��c7�P	{X�������(�f~���<J��T�o�+��;G�����=�*�R�7R�E�cQ�@�`�"v�}��79?�y(p�]
����{��B��QF
Uinj�x��/�3en8��P��@(S�F��{����G��BWf�����
��@�Rg�s:n��R3���<"�����(�}�"�'k�gc*�	~	����\�|���%����������(9���$_B�0�9w�����/#%2�+���F+�Y@6��p�	D��J���}),�f~0��Kb����`���A2v!
>|�_���M��8������PGG�.C�d)�2��.h�5v�JL��5����F; ���:���c���s.�����]H�
=��"�;w����^o���'����i�D�OQ����nFc�
]#SsK��'x=�R)Z�a����B���������i�ap�/������j�=(��[�g��k�:�������� ���YO>L1�����o[�%�n�_B�g��%��IAj�K?�3��~�5���%�g�S:�-41��������)�
=e�(��j���'"/��v
���>Y��ip^���g
�[N�t��D����8���J�R��\ ������ � �����~���9�P����|�/�})��n!8�������x��:�J������
=��"utt�Y?��0�r0���G[hj�ov�\����<Z��$��H�)�;���
�H�i�M���]�T����
����~������{*�n"��0�7�lw-��T^����6r�S7�A'Rp������.������lFU������P��@�H$����"B7�f��<�E9�;�tF	��>�n���'=�3\��;�hz^���/���6��k���P���s��m�Z�+a�
��P_G�����g#p0��f+�5���7g�h8N
��4�Q��;����I�8�R^
��B����-����n��$��z�zP?C<7|��L�&�:�n�������HE��=��/�A4���_������H�e��xi������U^*��'''��R�7n��.<y�DS�����&|d�f��5|sv	g���n���5��w�����}��m,���P�@hYV���C�J�d��m������|d�x8�?t%E	)��+ge�����k��I
�
�oDuz��a��i�
��� ~c�]�vP=��3�B�_������������T�����e�U899��b��B)���P"�>��K�.Jy��E�OQ"vQ�eT�����sw	��4/<01���s��S�P����'�:JI
�����C���k������E,}������1�d
�x� NC}����~Wd?�*74��Q�����4Dr����i}-6���R�h4�w���B�(����y 9475����R�����-����
�����(�*�*�q�v���

������������n�����;�Z���&{��B�L���	��e�~���~�����%p^@�p(H3�KU���� kU�A0���P_G�W�Jy��H�P(�8
i��s������;([GQ��!c�,��'RsR���N^8G��+��ZqC$W(��a"4JE
�O$����e��0 ���1_����uq7T&�[d|�j�)�G!<�E��o�����iZ�����K�������O�0��3�����R�H�4����w�;�-I����,�Pt�Q��p``�M*�b����J���0 �l�%�I�?�� ���Y)o���3��&��om2�BQ�G�B]����;����,��� �l�P6�O^j:�f3�&��wm�����$�mO>`/E���� J3���\� ��575R"v�3��xM����kK�R400���d7�G��T*���?�,��j��#}�w�/��x�/��<3�E�y���B�&3B��F2��������]O<�+��� ����F���4�CA(�����H�P�����\Mf>�Xd�7n��>�922�*:n��#4|�,����0P�^l�����K��E_�������o�|�E����2�+����T,�X,}��nX�b�!�,+�����{�5e1�n���t�a��=O������������/c��������v�q�t�}�ptt�u�.\�����s����n� �2�a�3s���J�����>�:1��`C}��K����9������$i�&t�P���7n��{��C(b����x���k�K~7��rn��M=Ac�]}�Cnp�L�<������P�ch=k <w��]�����P*��?�d)E���
g
�M����Z�e������[9�����l%���Os�A""�����n���R����]�����3����d�'
.����p((�R���f�z�O���>|�_�@����
��H$��������^������Utb�1�4�P_'E�U"5GY3/�2�C��<�����/�@3��!�+�\A�P����������L&�-�
���Y!����(�����>�k3�2�Vz����.
�����J��E�8If��%�Z��Pn�-F�������&3�b�����+�],�phh�uwp||\X]��+t%��X�}�C}�;�3�"t�gfqea�a�������"[(�v������O���8�}]o*�J������ IDATL#4�����2z
��63|s��12v`,�{ p�l�:EvU%��O?9�`�����)���Ad#4��C"vQh�(*�
���vKv�N!�E���'O���&3�e9�`��@�}v���k���4@�F������E;vp�=�>k�����B!�E�P(��h2�\/��}?W!gg�@ pa||�k��\�k���V!��;�P����������b���k�|�E���IY�"�[d
����r�_,��q��]B����Aa�ldj���(����S"5��H����=!�[d
��XLX�'w	]����"�LL�>�
 ���wP86�e� Bfq��cwE_��
�-2����I�4�=:�K�J �,+��;(*f�� �
����H�W�
[����9���Y3ow��n^!B!�E�P���C!Mf��%t%����5vQ%�����!������Ut��,��Pf�@�����P���h����� "�����5��%t<�EJ�R�����#$��'�v�9������-i��#�[tc�d8K�F��h��t4�LV���x t���aD���B����u`���:���������n�	[`/��\���)����������{����b�A*��*9�H���;825��0	�1�=nF����H���f�����:��>�Y\!v�E��H&�+�r4�R�7�b����s?�v�����(��� ����>�
��d�5�m����B(7$Rs��Ca,c�:j����w�q4V�N�B��	��W�
k$�s����i:1����B!�e���V���FFFf������x��o��q���a�ttt��o)�����8��!��#�/�}���B��������lsV�i��>�����+t�^�F�8����&���.���/_�L�t���&�?���o�������d2y���u��Y3?�0 ^C}��0HD���C��g���9)�����|��l����c||��5��tE;}��b�H�t��:\qv���<��A	�<7�K�����P
gF�O�"��\��cw���(��X,�z����{��t:��L���k��{2�+�h$ ^sS������O(k���
����[R�B�����f^hc����]B�0&,�
��	�~o&3�y�B�C��aO��P
�B�P8|�,E�O���!��(Ey�=�>�N?;��T-�
��r`�{����M �	��n�H�)!gP*
~#c(L�.Rg�E�e�%Rs�Y3/�;��� k�����#M��0�L9�Vjpp�*�Z���'�K�����B�RQ�+;��{���LM�PP�e�
���D��^UU�6�*)�:�R)�-XM�����u2%z�;�]�:�-�n�B�RQ����[4|s�W�0�R3��f��6_o	��98��L��e�U�t:��f2�������A9L-d����x(5!��k�)bp=����4���b.p�w��������Y��E���� �D5����X�6�2��p(�4|�����Y\!e��h���a�b����8�EJ�R\�d�I`w@�����y��Ps��VY�F�O�~���
�Hbj��=�������(C�+�GY�Z����3<�; Q���.�,15�+K����3G��>;����i����5�YXX(�s+������K�D����(l�L��; ���:a���2KB���l#)���<
���5�E�F��J��e�\W��"��i�rQ�f2���u���w�C�����B���l��G�
�2�Y;�������+�������(r��
i&�y,d�5��P_G�Kg������xK�P8��_Kq�Y3��K���m��Q]���WQ �*���C��f����;�F2;�
���R"v�G�Q���.��ilk�{������\�������A�D�����6_o������#��Z�d��=b����*p���zYP���EE�k���P* ��~B��h&�?3W�����/���d�7v��Z�h��/o��������]x���9��`o":���y�Q3��)��8)������iR�#�d���v������]U��A�����4�����:2�k�����Q5�s�����~��a:��G�X|P��IQ����eu�qFM�A���,76^�Y\����3���rV�e�O��:�Q�����i���s�@����R��].:=o`��`"v�f~��L�2�+41�X�eP���T1g��_8�9���qh3���V~5G�].j�����>"_�d/��H�'�2K�Y\>b��K���(�2��6_o��$d>Gx�����eY!��\7�].��U��n��pk8���At�N"5��y����.	�����l�"��r-E�q�h��a:�~V����\�{�|����:s���N�9�=�>
.�<!T���===l%�O�>=����\�&8�����Q����H�z�{�(v��z��o�
\���P-�cd��vr�uXc����^..pk��&{�G���?�� ��^l��bF!�B����*��R}ID����9��@x�AD�D�Q�n��= VC}E�O���cw���(�yB���{�v_��X����~�Wn d�I����X�����b� �X"FM`w�=2����K�F�	�2��9�X����~��@�u~0���C�rQp7�� ��dG�t�:�-"/<��������:������X,Zw�UU��L�P.
 ������1v�Q�����_SC}��K�����|]������wh �u��^�>8�M�\@���*��*�����h��"�X#���\����il�U|
�`��������rQ�����g��#v��xE���B�ASO��8��f�^���U�C�q~0\�L�(��<�!j[fq�}M�Z�5�4v���kH�.b�j��!W�Q�0�=XN����5Mck��5��(��|�z2�A�U��O�7�I�.�So�l,�i�]�!��A�q�(HD�v��d�3���~	PM���2c�lwX d)��4�*�:D��E�C�/O�>�=�h23|�,�C,�1��:����@���������v}�m~���d���p.�x����o�
������Xe���Y�WXk���w�������E���:�f2���u���n�	}P��� ��j��a�@hYV�X,>p�T��Q7���'|��������y���yD"��/�A�(j���PQ�?�,DDO�>����B]���v5%8�I1�@M=��^���D@N���td�(
K�""�,k���9�q�4s��Z���M��$��"������(����F����0���HD����$
��5�����`y�c��	��>O��Q��p�=��T2��@z���Y�9�Z����[.���� �<�������pt"�n�a��0{B�0�q�r����a;�SK����;�������_����V����p��_�����B�����vr�����475R8d{���������*����y$l��+g���Q������U,?�����k =WW�����n���U��M�?!�Xcm>Vj��Yak�����sB�0�wl�B�/FUU��`f�%�R�K��$k�(��xSbjN�=M=���@��=;�8I�4��x�������h&�]���(>vW��c�]���:a���A �,+�_'����5��y"1"�'Y��,���8+k������x��!>��S�u��W ���\
eD���:��mf��e���3�K&f[��|f�;\�J�����0>(�� ���R���P���D�	��P3�?�y��.�lB�����>}����4-��"�~X��A��E�L�/D��v�[���SB�a��Q�UU��5lf%d"p�����f�����Gd�
���m��E4����W�����?~��%��M"?�rQ�����9a��`j��@hYV�cQ���Y3�p�1�rB�(�?�����Q4���kdR��@��aT�4���Y�y�c�Ikoe+��,��>7��u
fj[�����jC��@ p��5l�hA�����u�n��r��DvE��;�^mH���*��[��z�h���������u
f�m\��DD�����\�EQ\_��!��4�������C��z?0�����rBQm�jYC}u�[����\�vl������B��_:C�M�B�p��3����hoog��{��
���i�(�����K�����3�J_z�FN������K����s�7K�����;����E�O�b�Qi ����/�P�[��[	'�Ej���W��b�Qi ���	t��������VfIH���pK�3���,��J���q����y�����1��@�(���Gl3oK���Y4.��2n�] |�������1��V�7���s��������0
.aX}m��T?��.�Q��{���5���f�����(
�=���Q.
Dcw	y@��]�,@�zzz>���@�1���O?u}
"���[��`�9nB7�f6_o����|�%��v	�/�B�����l�b�/�qY�9~���[!G	)�X3g���>:�S���x�M�\v����n��!�8�#""]��9��A��+p,�?n#e`����C"~�v	����C�+v��f��4=��m-��Dj.)b]���}D�3�^U���k�L�����*9k>�Z
<���+!�K�_��xz��,����/�����'����� DT�Q�B5���y����V2��\#'�p���5�C[@~��P`��BU�J)?""Z^^�X��5��6�:������	(��1�%/v�#"���\^l�b�0P�8��`����K�����.��|���6gY$���O?��e��76����:���h��,�C�]Binjd�\���� ��	�RU�|���`fq�&���sne����.!TB�@�'/^bh5�������G"jX=v	Af�����g��0���!���8?G'j���3�����m{M~����������Xxp����D��[�>��$x�aB��|dY�_D^��~��#��������A����G�c����K���E�J����!!��:q~<���+!5���� ��y\TU���q�@�(����7�C�����A��D�1�����*fc{X�'<�b-���e!��� �G�a����(��K����.������K�nIrV��7�p|��b�(�#��0@-
��K��h�$b�0��I�����m����2_x��A�9{#�'����S�����{,�b��ioo���,�p�4
��������%�=�r/	��O��e��O���s��~���QU� �E��[��+p-5@�.a��j��iP�i}w���2�����|� ���8n���G�]B�#(`o�YLU�=�������W�"�'�Y�y�m1�Y3�������3��r"C�O_BpW��oH�*�E�%�2��:b��3*����>�@e�l(������A���a
���ZKQ��^g	��~�)�2�2��2���������������S�h.�
�����@��F���2Hn�,����>��&����l�;�����������5v���T����@zp]"5��������Ae���o����������*4�pgC�Vq~��/�����2��Jo��!�E��q6�1�x���|�E��OX�Ds�q
����_8�!"����}���YS������<�`p"4�����eq,s(B(K[K��c4�N/6^���h�'8�IqBM���;�@e	��K���p���;�ED��$�D(�B��g�Ch(��5y�{:�-I�����AhY�PzUU���B �Cq�i����m-���G��i*�Fe�u�cY�,mC�Q�J��B�{P=f��k�eYaY�JO�@e�c9l�5�8SBl�����
�H�#P�{����AH�@ehnjdi���+������l�\/�}�s9(CC}K��O�r,CDD�����p(���������L�����p\3
�o����~z��#��8�Yp~D�n.��Qyp6�+�lk��Z8���@�/��Ofv��5������48GN���6r"<8���@�FD{���tc������������<� $B �C|����q
F@����2
.aH�>kj`YG�u�D�2
U��0�5���(HA_�-��z9���,�9GNh�v�B"��9.�������-�e�#�� 5|RW���y������3	#��X�Pt�?����`o\�<�#'�$B �4�W�F\����
�����(�������"z;����u3N������W�?ol��x�><��zk����h�	����:�Z����~!��~��`�� 
RsS#�����a�w��J���{�}t�[�m[��p�Z�#'E9�s`_���Q2
�=�M��n�p�����{?!���4��P �{�0�FN(�rhB�W�1����4���;�>��|^������
���1�*�aY�9A��@�
��
���-�f������-�`���*m�������k�?�����#<�����J,@�
���>I��-]�P�~=bi�RK8�P��:���r���LD��^�VsMe8`��� �z 4�/k���3�B�M��|����5D�[��~���0s�������V�d�(�"z������]��}��s��p���e�
�#'�=��X�a���q,�zq|���Uv7��m-n96����,y�nz�&
.�CA�����z%����]}��5��I�!�M��{^��������t���J�e��UNC"��E�[�����_~���o����t��:�����>�SM"����Z7s����Rf�G21��4���W�j���j�N�]�
�`[����e}�����&U��p#'��z�:����������h�L�?!�C�k���H�)�r����������/hc����0��jYo��:C�i���|�����z���{��n���w��cwQfq�~�VC}����Q&���h0����e�����G9��@{�zZf�
]$i���Xz��On��r���������D�q�J���H��475��(��p����0������<_B�]8������[R��h�	�����k�>�3��r�t��D�����2}�@���FUU-��(S ,�������55�C���\Ax��!a��r	����+g�,��=8���a��o��2�������D������{Bt�'f����1��<a��M�lkqf�����?����G�
��=�Xg��[e8�H�I��b�t�����b��p(H������<�F��W���DD�;�j�����Gvk�H�I� 	21�5���Lbj�����;�a���k@�:���4��u}��5J��a��ggQ#�=?�t��3�B�/O����I M=���'�[����:J�_�=�����%"���:���!� �8�ZP��p�ZN6�c�2JB%31�5M�>�[�s'�CA����M�|����!���O�>e[�(F��>.^����)9�Q�t�:����M���r�z����$�2�a�����FUU=����*k=��8w6����Y��V������z0��B���pK'�* IDATR���1��D�O!T������l��G���K�����P��c|%��t����A��g�=n��>�B�#��ygl7�q�aW9��i�v����p�@u�2�������tQ�� n�|f��>�t�}��0���2�9�����w���x�n�t=���n�A$����[��C��r��7��Q��{�2��}��Y\|%�Bp�&���2�Z�@��Q{�|��Tfyy��&�_?��e|���N�B{GP��`�H�.b�`���qC�#�T`;��-d.	�[�>�vk["v�6�"�X})�������gC����#��DogUl�
t���422��DD��I�c��9�Z�6��%��>M�jM8��n�f�����V�oh<���D�n(�vs�����<?&"��,�p(�i�a�E)�6�}E�8�y\P��������5������������[�*F~�x��������em� 5��m�m�I�����P�m�PU���~
[ 4c��X��5��x6	�)�������RW��.��j��w�<&k�Ws������+��/��h����f~��=�����ZP��#����(���Q��c"���vJ���_U�b������.�-���e�|���2(8\8\�rv=��cy� �o#]���������<��j�����C)�~2k�}�t�.��do(C��T���/Ey��:��?]�'��yD�O����4=�D���	���
��O(k>��Ay:����c�\�l(��jE_g7�a9�oY�_Eq}��P����f~���?O�x��L�gl���
K���osS#5k���_�-��n�������G��	^978=��2�?���e�k+x_��K�n(���^���g8z5��,��A�DD�55��~��SP>��6c�_������))u�(�������I����t[�[��h�	���j��_���>��a�{2�f��`��?&3�+�/���z���Wp������P�j%_g���-G�hO�>u{	""jnjL~�*��x��������|iS�0f�����K��<-�}���wp_N�������.��A&�
��R�fW�3��5k�qo���x~������Gn(C�<v��P�W���?2�+�����Y3o�wJ�g�
4�+���G�n���'���i�"~�=4�j�D
j�����jw(k������W��T������4�Q%nY��[��b��o �n����zoI��
���a���G�w�C��5���_E�OI�@;>v��#~�=o�k![�hOOO�_[��,'�g_��;�-=���B������/6_o���M�?�*�C��H�)�&��D���K "����(����6�2Cp��]�g8��U�$tG t�,B4����3�1s�����K��������P"vQ�N���E�����/"��D_�^����6Y��
�_c�������B/�6����k?�������\�!��2c��\�k��#��q�z�O/M�?����(>v79v���K!"���@�D�����6���|m������/��8����lk����*��w;�\�����u0z�Q2c�S%����f�F�/v�CAa�m���P��+{�c��������Dj����p(H�M��
���Jtp�^�<�/_�j� 4����:�������r,4M�����@�5�pyy9�F]_�'��2�+�����k�/Ejf�@�������(t�a<rf=���
x����Dj�2�+��i�	j�3��~e�����_����d�3[&��J�����=�0���bQ�����B�Y�n7���p��a��#�,����-��2m���������Ea#*"��Z'2��K���'����^
�u��� Mm�����{�H��V{Wu���K���]��y�EY�k�V��������\������M�<L���o�w����/O�#"xV��$[�Z��%����=�����LM��O��ls��7�Y[_ �HO�nc�b��B�4�;�r������&fS����H�!:$��k�,������_:����I�M�l�k�2�+����pM=81�5�zd�;�A�W���Gm����t�}��>��PFU�x�{;!�.���	�4
Do;�&Rs��m�ne�Pb��Dj����D�-�)@%D��nwM�8�575��w�f&���j���|���8:���{�^X���eY��&����������t���0���h���S1<5�mY3?x+�8�5���)����I575R���}?o�����(f��z	}��.���su��_9K��O�����]�����J_4��}w�H@�k9"_�\��yWn�Qq�}�M��W:�0�,��Z�������#r�'"�,����jS��@_��k�	�Nm�`����f~����A3��u5Wp�!���-��>M3�Wu��"�z�������mb�q��O��S�g%�����,|�S��Y�UU�Z���Y��?}��c���}���������<�-����z����W���nIvu���n��d�����Vu9��+���c�_b��MDD����k��s���>��f�����v��'Ll�����YC����Gp�WU��j���@�5z�0����� �P_G�KgvAWi��^M=A�W���+te\��Q����Y"���up}��T���G�,
�p:����[��575z&n��r��I/6^
����l~d��	G����������"^��6cw�C��p(H��ug������%}�w��]\�����y�^������P���F�|X�5������#g�t�D�|��q��#H��yc��5e�y~0�N�v�v ����`=���9������������~�Dowg��c�Q<L��Tk�O4�������f�<q���;�z~����A�����K�E��8
?�!F��;8����Y�V;���A �j,cF� �qP>�ID����9K���I�������B�z�7���6r��5�y�z3��d���,���6)��k�^2�+�n>��I�������A""M����A <~����P�b��:\��~�����Z��<��o��x
�[g��M�������}]�����w	qLd�9�~z�����Mn>|�a��������u����cU�BUUYO,,,0����&��Y\Y�����9s}�U��j�C������M��%��}8*����JU_�k��<M�>��;�A8gb(��8+�t]g�yqb��m����p�����x��+t���R"5���s�;N�>�x��q�z��%��l'~�tc]��'3W��t�F�P��m�y����8���������A�Q����c��>�Tg_�l��bY�
��
�]Bt9�C��������2�+��t)
��u�$��E�����:�����	8?�oN}�!����w�����o0s�����P�*�o���i4c�
��������8��P�������#SsR� ����Z*j�c	�A����l��j��q�{B�N��e}���9/�Y�{W��Pl��uF�5T*~��K�,��vS�=�@:\}
�<�g�
�H�9���H�WIC}�kf:��� ��AM��~{B������p���D��D����]�RY����_���[ms����K�����w��!���i{%Rs��'\!��K����9���s�zzz
�Bw�i������6���������4�)��|����g�A6��*��g7v�M�>v��w�������9/�$�?��i�����P��&f����^�w-��q[�e9���&.���*���YV>�{}�51���{�}@F�B�ax�� �>��������4��C
������vF�(~X-����k,��a�rpu�t��Sfq�z�O�5�YI��`	G���m�����	�DD����i�3M�nC��K���)�����Wl��8*�����e�j�0��f�@�����.!�9+�����#'���m�����N��'�0�r���B��8����� ��6s����<��#g�9��475�<���Vy+�D�?NRfq��{�����
�������4��	����`[+�N��E���A�aOO��k����?s���B����f� �i�QM�G:�5��u)h�Q�An4�9���W�H��jC��;�*�>f���H��6�W��Y������#'�������/,����A"����
�����`4u}��'k���"����[��p��T��f�����p�#��-�-p ��UQAj��M�?���'���H�z���c��M������f~p5WH����5��b���*$�������������-�q~���@���U"r}X���422��2D��|������Ss�M�]�PP�������7������X����K���i?K0����+{na+��:!��G��s��p�����C����e�q�� �%������w��4��!����[4|sV� �H�U�������������e���pg�M:�f�Q���A�!��:U7-�Yw�����6_o�t�D�����xE��Yr��U;:������@%0���8_�
��Z,p����A�C!�9B]�g8��\*�������]����E_���A"�U��������pu���	gi*_]�o�-F��$:$�����p)�8Z��J�Qx��+��Pf�3
��D��Q��1����p����Y�9�M�}v�������""��5Mc��[^^�X�����8e���^�^�n� D��iG�������%���������QsS#��q]����E�QW�^2��.��X&��2R@	����yD�7gY������JG��j��r���2pT��9����t:���i��}]�97�q&l4�8����k�
����f���K�7g{�x�m�^:�=���[p��&��j��7�baa�u�������` $r?������N���_/B���6_o���E�8I��G����BW"5G�����"��X��}<x�k�s��<n�k)""�F����C���n���eY�X��/��^l��Dj�U��=������O���4�^�^r���~������5�M����'���,���y�@�����?>��?����,//��(�Z ��:g��eW(����P_G��j)�rl���n������Y:�d5WH�����/��5���B�A"��7(�v5��/6^!:�3�9�Z�t��BM�\��qh TU���R�u�X��?{����~�����9��"D'��X*����l�`6�����(�%x�h_�;�����:�URNkx�	RB�jK����m��C�� v��d{'E��%V������+�.�8���������H���^�m\��o��Z��F�d+Q�}����G�X{�B\����C���7_j�I�V���x�@Q��������+�����k��y!��������%"���U���C��ylWm�	BA��=BR��C��Xs�[y�����\�n�������cB("bYV����[��Q�E�DD�!��_�6����@����Ey�	��	������JM���c�s]���E�DD�!�.�3��v�r����#�vr���
�n��mH�]%��O���s�����d(��UBM���!�
~��BHWS]}�G��hoo����*!�m�E�y"��pQ1�v��`/j��o����q�E?W�M���a�����<�
r�����8� ���!j�"���}�h;k?�8��(���9e�"�	@0��[������1�l������'�X""��T|�K��B�0�0��~d���2DD�!���3����	�������_��]e������E����vX�]%�""�eANq9X��(:����z�T��`�y��"�������l�.*"��.�]���&Jv���T�!�^�'�������:�%���#L<�~���g[��n�l6�
%""�iB�M���B9��`"�P'���K"��U|Q&"]|�����m�`w�P�DD�qh��$���|��!Ru�M$"���v�5��C��/`v���|���V]���r��#�u%�NQeK�!"���!*/��S����&""���V���-X@���(�uB("b�6d�)�E���K�I��<�B("k���~pap�v��b-,,@�B!�M��)!�,�R��3��q�QD _�9i���Wb�UY���A��r9h���.h<�=&��O���s���&�E_�I%Te���D�'� <�x�IX,��� ������
[7Q��
��J=�F,C
���!���?��2�H%�g�$�'�]tvv�X0�,�n�d�	���z��8X�H-�4���*�m���&��g�T��"��Q�=(@H�
��?
��"{LE8X�������/����M��e�����{�8���0����X���<�.�8��M{NQ�e`�e8���H-��9?�I�2rN��;�_��$l O.��KD�4�$��M{NQ�e��9���H��
.!�g>��\��;�E{���&
u���}jj
JDDl����h?��
�9s��F��TB�P���TB
P�`
d����]���K����$��,��sDD��^��fBH��&�������V�v�l6�
���8�������P$|�el�8��)�Z��n]
�K�2����I�"Lr���-���|a�K���.:;;�
%""��@r���+!�`���Z��PW��	)��t&�+1�Y���Y��D�v�\.�nE���}%���2��B�����H�'�cn���TBi���
�����`�B�`X[�	&�D�����p����H��m�Wbv����
{��m�I�0�1�����S�0.��a�T,o����qDDZcG8����<�����z�/�����-�w��t)�-B��������PD��,��h���qX� "R�z5@�h3����X�GHA�vQH�k;�N�����[ZXX�m���H-T+��H%�#$�t����*���X��4M�
���T!�=��'��@D�j�=�h3����GHA�4^.���%���C���A��r>�V\������8��TDD
=(�B�����Ts����;�(���p[:r��j�X�("�mCu�d�	�i��`�� �Y'�{q��hs��o�8�EH�-���U�:�C9���D�Ad���B����,�Sd���;!���'�T�mDDD���v��Uu�h_`�r��P�D�}�ao;	��nun[J��e qDDb�GHD�j�(rH�f��}Zc��<�����^og,��v���>-�EE���
�G�9s�����T��/K!�{��i��Rp�]��-��;w��������H��y+���b�{��GA��iA^��,t�N��"L
��4��z����9E��z"""Bp���X��S��D���yU��^�vQ�&�""�m��1v���;E�xf""u��+�N���ZD�-��������O��������]T�	������;��z""*�����zs��a�q���D�a[��v�\.�vQ�2$��eAZ9]���p����H����l���p�G��8����yPX�|��3a{5�UlU�-���2�b����G�����(�b�o�&<me	��P�m�[�����ag����p����a\��]T�	���m���2� �pA=�:�]�5�U�EH��=�7+��Q��m5C�����DB��NeI-�*�/��/��G����Ty\�M��{k�>k<��E�
u�b[�aC$�.���$���2��B��pA=Q�q���`�h���.������E���_:N-)W�(�n���w�Q�D���U��{����v#�vV��}�(2��s�hIYB�4�a\(���.�'�<��%�����t0}{+y�,,���u5�d��XS����a��s�d.�F�����)!�mrI���*u�6_X�]R������	|��9�����Z6�v455��s��HcC�9 IDAT�0.�?�=B�JZ����I)#]��Op��������;2=���v��+g�0|�cG����H�~"]�-����pI=�=Lfjj�h@��]T��	!lA��y��T��["""�6�{�Q��N(8���%�j��K�r9d8��EE����X�YP�y,��hf"���g<���B���;�'�p��5�Uo;;q]w��}�����	�m���������#��3""�<}imx�	!��6�|���a�������to)sB��2���a���h�wO���J��n��q'!;~��iA���r9hU��,��EE�_!���3�F��'"""t��m5s���LEd=1F��f�R,o�������!��[YB���\.Yk���=U5��'"R�6j[�{X�Z���X=�4���,4����8�b�A�5!�.��-��=B������{bD[�5���i�6��u��X��W��r9�0����i�1���	a{{{��M!��/.Qe��m���%�5�U�v%��B��]>�����/ �����?�����w�B��P�aY~k�Hp�D���(��m�""1~K~�{������vgLMM!�����8��A��-���"��Dq�D������o{���N�;	A�^h����:K�=���H)"�8N�0d�){B("b�6dA����������%_���{-�v�9���O��.B������O�E����@*�Zfj���L):����I1�b7�A�������>��g�;��l�Nc��D"�vQ�
%�����c-�ua�Q/�S�4��B��xKD�����C����S��;�r��*z���8��W���w*����X,��<�
"V�Os�*uKDDO�>�|a������Fy��R3�X$��F����V�����?�}}}�[gT���0�,r��u]X_p�?$����~|���>���m���e0b��{�����x�)h��{�4�$r�f�T$!��#\XX��9��2DD��D�r���$�p��U����,��%�a\P�;�0�~�jBD����/�;	�S u��_������B�U�����A�B��!�!��O������B�V���v2��W�6;�H��=��:k��XS=��Y��A����i�1��b	�i��0.T����u�oqDx������c��r�IIT�/�W���Gmz=�n���8|�`__:d�T,!�mr��{�DDDf#��@��vZ�&Ce�h�|8R�vnT��u��u]H�#�����0��\;\����4��Bc����jl������d�YQ�{0i2dYU�B��{�D����EDtO�>�{=����L��p��0����@E�hBhY���GHD�Y���Y��@D$s�_A�{;["�@9�,
���a2��u]:L�0������YnMED,�������0"�{�nQl""
t����O5�������l+&+�$	���J�xB�{�D���6&!�ho�N��D��.�N\����JC�`
�A����>��J�xBh�6$yB��=B��C���`�5bZ�x���fn�><�mE�J���:�U]]��r����wZ��)2f% ��J�(��r���(�}S4��[���`x���f���[�m����"�3���g�������W# ���SSS��� ����	���m�ID�����RX�h���?Q��}��
�5�8������A~�jC�z�������\Z	���� 	!���P�����f)�owFQ���� q���0��I�������a2��=��B�{�D�/("������F�����N5�}J�����0�T��f��p""�������B�#$"""*�K�
��{��1U���q�rog4��a2�i&��{p#HB(�>�����a)��Q�Z_���i��������t67�B�De��%��.�98XBh�6$��������E��� ����c���Q%D	[��^Q�p��Qt�J�%�����VN�#$�������D���� {�����C�������p�,�W �Q�_(�%*��8��4M���[I�
!������uR���%"
����P#
UBv�]C]-|0��a2���K
��=B"������(�T��@/W�=�;��d�,t�D6��0�0.�e��F��P$��m�94��P�<}��7��0�$Uz�������!PT�����B��D"���M�x��;�(Lb�oC��|�t-��<
�Y#E6�x}W
����Ht���G]����0�t�0��[�6J!QS]?e&R�U
�����Zc��|�������q�0��C7L��"��������"������AH���9
z'�������V	��r�ja�*A��@6���W	�����	�H8���Q0}\@MTIk�_���}�K2����n�B��@6��b�x3��dJ�	!������C�|[c��a[,J��<�������	B
���{�����t"jER��!U���7��u�L��
!������b��Q�!O(yo����S��y���Jh[�{����Z�W>�WM��;�Y�a2%����FDDZcG`��*!�'�DD�n���d����U�e���U����y�L	<!	�=�3�F�RX�rC�P�Zp(�P��,R�����x���0V	���� qP+��
�jBD$�����a&S�$!�=�XS�]VX(��������Rz�I���{�$B�x����*���1w����	�j"��@����L��
a(�����B����zH������w�j /�K�o�F���_�|a���*!j�T�[U�%�e��:��a2%JB�0��m�>BDi=q$t�c�)a(C;i��e�Ft@��=x�)�UB�XS}�*���N�WM���a2�$!ioo��q]����XKD
\9A�CN����T�[���*!r9}������&�����DD�q���)Q���
�@[,oy�wK����\�?�\N��B
�t�&<&�������N�g�y��uU���	�����u�OP�l��)x�;�N���Q��J5oc0aC]-�#n||�_b�f�q����%�"�G�G���mA^�K���	���v3LUB�����{\5FJB�=�\.�A������D�Z��/V�	'���U�`�g_Mu�$/���T�jBDdpp0��&6R]!�U�\���j�5�B�j)���*�G���������E���2q�� ,UB��VvYGh�D�0x\�T'���a\@�ZXX�U���`BH��Z�����C�����	�������a��{�'�E��VM���E�����PD��m���\.�#""��f�2X��B-���Gx��P����GQ�*��P�:���:8>�?��,+�|��	!���y��XS�� ���J��������	�UU� �S�jw.�Sg�z;-h��u���{��@4o(Om�����r�}"�GH�K������}�5�^�~|�E�UU��_>�7�����h�5������C
���H$"5L�DyBhY���{������
�jf����Xi;�){y��?�NTT	[c��<$����~\���&���U�jb``�_Q'�B�q ��"�����v�r��vbMoC���U���HRU%D'��h_��W7�jaw�K����A�+I$GU���	!�����������7OTN�O;9�X�����3�,Rd�J�7O@	��T�f�����$M�,���B����mX���.���L@?���T@���W���M!����[
u������1)���1ED���ZiZ$��iL�L"b���"���Hk�H��(P{3���`�m	Y=@M
$���*�m��������1U��0M3��&6�"!q�u]X������Veh;(C���J8��%x� ������Jz;[�1U-�F���6	a{{;��X,�r]V��i��PeDx'�HDM�PD������xt2("255��Ui����*����R�;�
EDX�{*Q|�#���*a:q�����J���Bc��;��.WM(�MBh�X��G���aDD�	Q��TW�b=(��/�i�UB��}��6>>��ZI�WMl�MB("�����y�����(h��f���a��t��J�<��AWq}�?������D"�Ui���
�����`St�$LD�dk�R~�(TU	�A�'��L&�d}__���[B�k�D���Y�H;�j����a+I8P���TU	����J�:�T���f����m��_5��V	���m������"���Om���
���e�6��J�\�����&�*&�g2xL���>%qu�]B���������yW ��m�DD�A~6.���@�M�=!��Mx���-�b;y��Y$�z;-�����1����4�\5�s�%���������	*�mq�-�����x���D[�[��$n2~���wO�B��k��X#��lllL���-dL���H��{�]Bh�f�4M�����YD��i"�� ?9P�h{*����S��&�X����Yx�4>�o��"��i�����
��^���""�gb��
\CT�����|�%�TT������b�D�a����2!������@��PqY��HW���/�+��5DA��J�k��uTTU
��"�Mh����*����O�5v��'��^A~&.��E�"
����J&����yV�PQ��r����\D�-B�0��m�=�\.�#"\?A��n]��������D����=���XS�]K�w���;��P1��N�������\�m-B��	��a�c���nP��j9��^C~.�W�����#
�����*�����q��>�w�j%�v
:A�u����E��e}���&������\.�
*�m5�JBD���,��A��SQ%��n�(��J���L&��[nxx�����mBhY���a\@�B��@���}G����,��A��[����=��D'/����*tX-<(��*�z�wEEu�4��m����A�mB("�8����};����>S�1��@�$���kw�Ts����)*�������c���(Z'��{�"��g8Z�4��	!���N�b��p�����dn�><q��l���
RQ�}�h6�UR�"��i�:������Y��NF�A�"�{�Hd�e��q�3�L��Sr�EE+*��������OE���:!4C,����p]FD�G+G�?���/���� �.J,O�>����q�m��u9D��(U
��088���.h���tuuA���?�yl��}��'Hk?��\�8sB�/wR�����L����Mtp������?�u[Y���SF�Th6CE���>!D��p]v����y������3��n����� O��/�E�"
���/�T	[c��Q������Q�A�A�D"�3t�'���SSS�0""b[�y������5�DX�����_�����xDa�������.)�F�����""�H$��i� �B��	���'Q:�"�=��V�{�w�e�"�?m'��t����*���r���TU����fup�"�Od�YX���X,�� �Yq�R4�TWA_FT�y"
����J��EyY}�����[����] B�����T(��u���Wp��X#v�$�=Hkn�+h<����kw����ZV�JD��+�R��`__�t�Q B���\.��E�`'�����O6+���h����U��U�R~����VT-�?���(Um�N�����t�HEp�'���-�ua'�GH�@}��[W�e��PW+��zXU���D����Tr|����V~V+�{�����phF*)0	!r����,l�}���I��*��H��N���D����3�[�����=�!/��#����������*�hV�'0	�eY����jE��XS�]-DoB���`��A��f�(Q�M��Sr��e�����kT��LUup``�����PD��mH��'|������	��V`��2��vo;��vQ"�'O�)[V��\A�KzP��,�����i�I�q�A�
�@%�]]]��?��}���;�~gR9i�+W�#��I���m�(�T��!q����kT��W��AaC#P	�m���jj
Jl�xO�?t(��Fc��;
u���|a�r�&Q��=�e��5IK��v�D�:�H$`+��(P	�a�8���y�8%�]D�q���ju���.A�=�|n�+%����ln�����e�A���� �U�B���vX�l6��z�G��r���a��y�0�j���eU��E]r�35q+����mLBX��O��^.!t6�evv���I��2���C�C�q��3��g"�IX���VN�s��mgu��,p	�i��� m���B�9m�T+����$��.����[�
>Z��~�����nY=*�*����.����5V�/p	�n�D�X����`�Y1! OycM��������c�O���P-�G�,��	tgF���`__����������
*���,�������*����U�PB�_��A"=�iY=���\��Q�86RU4���� ��e�����O
������."�k���jK�oa����\?2�U"�=H�����]%<|���B���R�'�;U�����f�0T��@&�""��@N�|���<V����D�"���.�T7�c�is�UK���$��������e��Pe�����TW��m��:&�M���`w����>A�Ru�C��a�=5w�������+%�,�hs*�����������A
V������*V.�C����z����]�=R��������3�x�,���*�:�{X�����j���|��R)VC$�	�a�8d���������m�T��~B�� a�~)QqW��v�_����"n9��g���:aTE2�������	x`au�R���tuu�b�r�oP��6J�����^�vZ\�p*���}�� ��T-�/G��5v�b�
�t���
u�J�3���x#V+'�	�m������*���bB�!�I��N5�TW��Q�vZ�������8L�Ho��M%w|z@e[�{��(�:h[-z���zu0���:2�NM�,X�i�<�6�lW ���=��Os'aP��%�Tm���+�m%������,�?H��K���E~e�����F%��Y�@'�""}}}�X���x�I�g#���'D�&*�"�|a��A���g��%�7����q������E���:f�Om���\XX@��~6��d7�T�����b��mO��
"����/���o��L�v8�����X#�sWD�������
|BhY���iB�Fs��T���BGj��F9\&xT�a��	�`Q��~��Q
u��������z��O�3�ug\�eu0����8����fa��6J���F�m��Y���j�(xT-������V�<��o����""�L2h�M�b�"!����������B�m���O�����E�\5AH**�������G!��|�����������+V�/	�eY��q�m�5�i��Kg�+(����&��ME�p�m��v���T��:�J�:r�HED�����m��D�4GU_z�{*���o{\5A`s�����w��y�/�����VMu�Nd����<%����QVAB�vuu��b�m��}o�UB������+��c��*���{����9d�|�$���p��y%C�2����b�f2�H�:���q�w�6JT*�m�J�/���/�DT~K�x�p��z����-��5�+YB��f��}%����aa#+4	��F�*���g�zg�1Y%�Wo��YQ��LD����g�6w����~����y�z�T*��*�� ^����vX,.����[�
~��UB�4���m��,�DAD���J�U�;z}�^'w�ZB��d�X,�B�auP�P%����Nr����m��z'��z���!z�"z"*]���i���^�M�XB/"266��`��*!4C�I"b��[�\6��m����kw�1U$ �9.�'�rY��H��
}���J��iA���r�����d����UGGG9=L�P%�""]]]�X����[�������sfE IDATK�DoRQ����jV1��~	}�."2}{��0�o{��%���X#t���=�Y{�bW�lMut�i���G����A2�m'�yGE��]B���x�Id8�_X{�B���/�g�\�Us��������G�!��������;	}�s�G���b���H*��FI`�,�u�K��6�����<f���.��RQ�����E�D!��-���E�j�-��M��j�����;�^�Vb�v���^�)�	�Hx�FE��r������=OI+����9`F!�I���'O�!C�*��&/���������|o�����d2�i�%�����m�D���r���u*��L�������CF��������g��5�\n�u]%�A�qXT,�	�ab�6�m���ms��_�\����B�J�V�q=QtL��B����4Uk&R���������b��P&�"��QX,5wy����J8����=�N��A"R'_X�/�G��=IU��ccc�����`"�H��YP�~���q�i�.�.�fTU	ED�}�:
���2�E��E�(��'�j���H&�Q�^9<<���B���Y�,�6*"�lE��!���*�m�A�1FUo�}Q�"z�hZ����J��YC��+I�R���%�����j"�	��H__,�m���HJ�������&�E�DQ�*���W;��5�+9��}������VQ�0.��@��B���m����6JZP�+.�w��+]��"z�hc���������y%��U.�h6CUxzC�����r�����g���bM�w���<��j������A"�^���#�������N)Y3�r	�i�IV���P$�m���6JzP��o;������PW���/���VQ��HSa��4 ���J�������T*�r	��:���'�!o��E�������T��	�}O��&��$U���d�xUk&���x���:�H$X�L�Bt����*�������ZX<���-��|aU����?�r?a����_�|����a)�"��0���;��h����������T*������d��\�*�	��mtjj
K��FI/�z���*�������2@W[9L���4r�������[��h�U��E%m��LF��	����m���M��DB�,M{�7��>�M5�v�/�������5"2S.����xs��a2D�3O�>����o��q%�d|�?�N���������^Q�����0q�6���`c|cM�wyw�t2r�����x��ft�c����,�W���(TM�>����5�U2��%��D���D"��,�SU�i{�HED���`�����>��|���=!C�P���-�za�nC�a�=���
:��:�j���5""�����9���$�����F}���<VW��B��{�|lx:q�I�>��NB/��4x���-Hm�;UcM�*��\3�4M��*>�,2	!�mtjj�T,�!���7��
gR�75�U�����pf��DD���T?���T����JJ������0����/2	��m4���b���V3i�V�<}�t7a	���C�>����N$"� �����,�p��N)$#"��d��#7s	��"���Fs��**^��T3w��n��k�%��pw�S���.JD�������v��k��$��|���R)ek&L�L�:�J�m��������i���~t�gR����Z�5���H�\OBD�������d�]���
z�wellL� .��H%�""}}}��].�����vZ�IH�Y{�B��L
���iA�M���{���d�����e��n�Mk�Q���T*�g���K�B�q�1�"V�X���f�Dd}'aC]-,�n-�W���N\�d�M�O������^��|`�FC���:������g�Yq]�K�iW"���8�;����E��)?�n�\�#���U����%�����WZc��x��}����Um��.�W\����yog��L&�"��p	}E2!���B��N��[����l��J�7o;�<���c��w�o�ED�����jq��]����V�.�G>�k�LF|�W�fbtt��d&�	��8���	.����A��NB�����d����5�:�3����E��:�v
�5���DT�S7�0vl��5t����*��M���ZE�f"�"���8��555�%"o;��N�-�{�M�������?���&u�>@��A"*�|aUy�y���M?Cm����q%�u����"�F�i&��4�������v����	��`�l�x��Hg���b?�FC�G��������_�]���C���#\�X�O[�j��d��KJ�%���*$�ia�����O�m�SSS����O�KO�����FC��K���TWA�E��?�n�^��7�O��]<W��P�sPD$�JA�_od�v�q�wT���9���K��������T*9I1��?����zU�g$���je�O��cS���d)���1**�vJ����xC��@"*;�:��*W2�x���m�y��jV�e2Qywpyy�^X'�z���b��ze]�X��y�/�o��_w>�q+H��N}�o:v��Q�&''��DNz>���/�^��^T}��d��=�xN������������R�����:�<�JKK������`2��E=��������y����!��I�X����`���4CN�>-�m�X������H'�""---/����q���_G�����t�f$?)X�����V�
O�������*qG�7}{Y�"
���*�����T��S���C�z�0.<~���n	�f^%y����|����y^����2M3i�������8�T��E>!�f�/���a?�?��4M�(;���;;:'�"������@D��s�I�d�YA���itt4988�eu�u�i��z��<e�w���d__�$	%�a��b�(����_T8Igo���}X<���|^�I�a�[�vQ"
#����������-�-�J.//+O7V����K����8�����[E��|B("����2��A~pL�L>~�JD���z>�OY�B/�@\�����;=A^���1nR{���D�� |��C*����1e����|�m���l)��<oc������L�LK"��x���PDr������]�{�v2�V-
��|�O��'����������I	r�LD�������ttt����j.FE��TO�u{JC^�����2!|����Q?h�D"999�%".C���PDd�������1v
�{�."R!��	[ZZ�
D1�����m�fa?��R���~������_�����l�g���������DU�	�+�T�%���b'!��P))	��]d�h��e"
�V������hofxx8�N�_W�\�����{��S,ED��/�����jj�8�����,��&��x����N�����)hI������Ss���JAV���miiq��>I���099YS��3���HX���eYIT��q���(M��pIgo6�-���9�"y������������V���L��$,V��z�� �4r��,�Wpm�J��a2H�b�Vww��T*U���
���`�<���<�
,��������&�I��Hog�������A������X�9T����xw������x��
����\.����O�0666��������_L7@�u�h||�d��{'�BMT���l��qO�c��m����,}<��j�PW+��{����hKk�_�����P�R�z��@��<o���c=���~
&��!����Fs�4A���j���B�$*����J:{S�cH�j8���s��-���%�vQ"�I��*C�P���J�8���T,outt�a�I���N���H����������������#�4[-�B�����C��+�xD��_Y�������/1��r u�����{������"W�����J�������IT�����������E��.�__#B����� �
��ug>���E��Az��_�����s�����������{��)��8v��K�)�m����yD��Z�b�U�������P�0/�W�����`��8�u=NK��
�GD�[��u��~��R�s���0�����bY������et���b��;���QX@Y��Cd���GaMEDZc���Kgeb�}Y�x@f��{.������EZc�����X��	�A"�Uz�fOP��d2&��'�ie�p��7;v���x������QT8Y��$G>��4�[�VJi��R��q���	�H��+������v��������[��(���?#"�z'�~p� �eY����]-�gB��������BNd����?@_��,����`0}t�F�H{��SZ�i�����(����i;nQ`���;	����l6�'"����


���a2\EDA0�x_t�q;66�d��u��t:�c��	��9d�T��ql'WPP���N���`��+k�_�~"�]�v�Y����LF�D��'��L�t��	�^�$�U#<���<�
*���K6��to���+�g$"
��www�
R9uwwR,����nc``�����������5��d0`�yw��&_X��u4����r9��RY��?166�e�(�������%j����2��M�[��I�+A�G������h��X��r��~@d}��f�l��zn��gV��{�&
��HD5�Ub�>.����N���?bu�*������Yx��gB��l6����vR3::�D��

���h[��,����r�!�U���vI`Iww��:H����Q&�;(�r�������4��?F�z���i�t�6�je�O���42}{Y�����KC]�$�g�^[���LGG������X��4C,���.���O������������ZDD\�����}-�������v���p���_f�Y���?(���H�.j��d�w���5�ku����/������u�|(�dJD;i�5��������u���V�����2�eYV��,1MS���gL���M����v.�[]XX���r�$��U	����y�iii9���8N�����p"�E���A������&��5�s����D�M�LF���x��J��������d&���������_ryy��eY���5�]B�y}��,��1q��|<��pRg���Li��QI��^~�|`�711<����e���kx���ugR�T2�xS"�HNNN��2!�%�p�������(*�����g)�N\��n�o���L����0�������������Q*"�������L tfYV�4MyU�[�,�YT����1I�R��L�������Lw	=\F�
��kwd��22$�V���yWR��'�����$��}tC\�B$���X�L���1 |�?���������l�~=�������i�7���;�����+PQ���L&�C"L�=\��*����^
E����9I^�]����c�^_��m;��0�\��Lz�f��D���w���3=����y�h-�����W����:�EG��B������L�
=\F�

.�'�x�)I'.�~��ZZZ6m�ab\������(�j��d��K��+X.���<o��/����@�D�0��e5����)�i�N�DD���*),��2!�#�p�

V	����nd�frxxX�U{:�"
���Z�������yW�����������bQ<�����qG���,�a��*vQ��F��z���<U�J�5���{w�Av�nd���������J>�w���n�D��J�dll�g���2!���������WP,�W�#��LHe���y��^p"�H�����4���s���.��n�D�r��aX����i��"X�$	�Is&��^�m�5����!)t�2?h2("��f':::��;&�LF|�?Z�����5�������j��T?
��n�D�4::
�3|���}���}�}����cD�S���UB*���*�������(G2����}}}�k�)V
���� E�J8??_�
�>��Yp'��W,oe2T8Y�6��BcR8��f2��%�""��N���O:th���[���X9�+�D�QS]%����T?��8�B���=L�i```f��|��,2���$�g��R��|pi@�d0��J:��]���r�Tj���clii�T*%��B?;��bM�w�}��@��t��]�?�����VQ����k��8�c���,-�FP��>������3hL
�t���x�)-�;f�YAN��al�nnoo��8�FN%�W���:t��b�v�	��WPX��\^^F��0�����r����n���=�m;iY���������,��D�3EA:{S���~"����p�-�bBx�bQ�;]A�bQ=���W:-��<�JGG��O�����i�b���>}z�0�[�&�_����/��s�hK�~"�:::�u]H��	��R�����m'���Q�D�UB�&��m'EDJ	����~�+�,���8�0n���3N%�[E��1!�

��zV	iwtj��}�hKK��dp�T ���e�vG�cEZC]����_�ci�r���WP����p�(�L�dPD�����('�""�e�~����l��X��� �� �k,�W�����6b��\�����XC�d��t���nKK�x���DQU�I^���-�������eb�}���+��p����_>|�ya[�e��K��������m��4MV	)�j��d��K�,f2�>1�����v��~�H�?��$�|a����eI�|&�W�e��=s��vx�z%�����_������X��	z�a~����V	i���*�����tY���/�l6���a���mtA��s�K�+"�����h��������E�.����QT���0!,���CWP������0*��p�(��N���[^^���d��kw�AaU��+"��bk��j���g#~�a��]2q���}~���B
u���������3��hL�(�N��d2�R$����d$�NG>���L&	������;2}{y����k�&G>{��Q��r=��)s��������j��@k�q���8������$������!d�b�x+�� C���z;�./��l����$	m�����@��'w�����Igo6��yR&n�����������$��)��'n�����IED��+��l��!?WhWr�,�a��[�Kd��������l6+�����,+���������nYS]%�Kg�xa�����>V�#�����n��V�q[c���V��R�������Q�����AV�mxx�(2^�X���f�!ED$���S��5�k�z�w����!2�CD�[��q�n���vG�>�Q�����{'�
ATA��z%q���s�����WK#�����O��+���%��)=N�W�?�j\u{���8t(���kV+����e.�������|��1*�k<=����y�w����Q_</���J��Q�s�n���|�	PJu�7k��x�I�]a�zg�+��<(�J������.P�~�|�����aBX*��&��_H�|�K�PS]%��oU?����R����L�"S�d�DeR8}{���D��]�N���������5j��)H��+
���������].t��bH���/�2!����������J8��
q��������A.�_�H$������0�L
[������T����pZT���WMu����K��m&�,�W���8�_�������������JF>���Xtu���C�0jV]����}"����#\��R��|pi@�/!&��,��"�[��h����j��*C���.!��L��TE+�DQt&��7q�^��A����s��EED�nMu������F�5�=c[�{?b�l���WVK����xn8���E6�J	����m���:v��K��C_%�t���K��Hww� ������4M���7�j�?'�Kg�1]����G7B��E������������k���*9�T/���<j��U>e+�����_�Y�;."�����}�����.�K<�������r����w;���
�f�/�SU�)
�mT�x��J� ���l~~���m������I~�������{����.p����HC]�4�]��?+%�����:�����_��eE IDAT�=!6Tc7T����������9�.����U��~��*�D�J��0���,�J����AM�~��7�je�O����� *��A�����]���vw1U��m;9??HD�{+l`;A��]BhL�����PW��?H�k�5j�f�Y&��$	-������ax���L����z�w�	������GL���Ef��+�%���]Q���tuu����VX"�8d�d�L&��Z2~�/Lk�����U?���'�\<�N�!2��Mm�2L�^������(�bMo���>��w#���V&���|^��l���[�a�q���&�f�@?�|��P���N5����Q��TWi�x>�J��A��������f&n���er��IgoBc����������vk��(�l�����_t����!�ke9��4M�P��L�U���1%/�W�g�[f��J�U?��z2����.�_�(z���+��cn��#����L����>�x���j����5E�����d�LI__���}�����[*������x�)x\:�v
vww�dp�����X����Dd}�(j��~ ��!��!�
,=�V��.����qG+:�h�f�J'����t����B�(U	���RS]�"4�C:q��.�---��'t399�T���}tC�z����W%<�X�GO5Q��L��q��*O���%:�G�l�%BUU�T*��Zog����7��-�������"��qA�>�7�0Qt'O�>�|a���K�(��B]�`Q��TW���9��
���;�:4�B"�8�����HQ�p����;����5����]N�T����0������C2��D���-~K���Ft0�W�R~�3
B����;�[I^:��Qv�y����n�:00�l�/�}&�@*��""�L�tL�t�"?�5k��f�`*�R�K��������m�s���4Qt'_�r�2����[����3���T�=T��1�2,�0�������0!�SQ%�f����'r���bM�������u�t:���,�i*9��H�!2�AV2cMo�b����zH�����@}���j��$���(��%�$�""����VE�����R)%U��KMu�d�.j�^B�������\^^�7<<��Q^�}��VP�a��Y":�iy����	����f��nd�Yiii9�C2h�fr���%LPQ%t]w�u�d�� �vG����?��`��/�7M3999����ZDK�#�i?Df+
��8-&"� l�/��N���F�zONNn�0!T@U����_�N������@:q��.��.�h�D���������F���%�]�r���S�D�Ai�#��m�d��m��E&��*t'i���w��*��J������2�kC�+�K����i�f��������$���ktLED\�����e��q O�fe��*#�\Q�DPd}jz:��&|��j�V�&��(�8��M�j\��k�o;�M�EKKKdv
Z��M�|�2y��u�m[I�~'������M-�m/���JDu5�U����DPd}��nS�����$�B�TT	U.�O^:+��z%��J������O-�J&����-//�����G�����@�y�WKC]��a1��E�������h�O�q��Vk&���P!UUBU��ED�	�Q��z���~�N��������h����.//����V�b�3����,���	6����Gs����i�r��jGG�t;��m�h���������?D������f~~RDDbM�w�����s�g���������l��A�4��mKWW���8��;�b��q������"���J�m�$�v�4�\����d$�N_W���~�������0!T�T%�d2����N�r��7^h!������04�	��^B����QJ��������i&_�G�-I�-�4}{9�_�����H��>y��{��v���K����m/�UW�nR����'m��uuPD����/+�<���{��>��4������!_�V��|8����0Q4��%6IU��IX��-}���&n�c������^�vj���5�(�����H�y�w�����;�n9���~����AV�1<<,�������Od2����04��z�����2r�<v��v�h�^"H��m�I�����}����
@�����$_X=����B����q��@DY
u�b[��5vdc%P��H��j=+"Z&��e%�rop#&��H$����_�/����=����UTAz;[��qWP���Ni3����A�>0M�,%bY��� �%d	���>����o���G��""�����#r&����J�Wm����������"*�z�������	�FFGGg:::�1���-UfD�����0��"��^B�]��a\�m��U�f�'�/���|8�]}��z-��DDaUS]%��z9s�QZcGZc��qC�u�Q.�[���wu<��h~~�_,��t��}�!�LGG�K'��_W2`FD���}t#R/��TS]%��oU?���]/aYV��m9}�t(��D�����41���/'���;�D��C��_Hgo��� ���j�5�(�����FJww��r9�A����d"��W�h	B�x������R�fD�G�O�^V?�j����(�J�dll��YJ����\�@�9�?�a����`P	a��Te�9����PW+��z9�T�Y�/�^U��0���B-����TQeL��������J������ �K�q�q���N���0��j�5������L��n4q�^d�^��>O4���u5r�����&�RI$�"�&&��}�����Uq21??_��]+�'��������E�c���3k���M�L:�#]]]���m�9T�&����`T&������_h\������f��-g[�(������F����^Tk�|�%
��3Lv����=�f�r
�g����������1�]f��8P�G7�A�e��?�Z2�9�M����5��������?�~�4i��}Z��|��<���_��m�u�OkOS��r43 ���u��z����7k4R*����+(l��L,�����z�R�4������?�h�x����z�+���"���������8333����� �Sg�D�_����GF��Vf0>���\:?,����k�[�z�u������6�����{���g����c����h���g��g�~W�V:��,�0(�al��m�f������T*�Hfv���2�}�xc*�e�������=�8N���k����x\W�����7���4���w���^TG��jms��w���""����<`}��������;�udN/�?�P��A��+�� (N!�Z����^�����|���Em����T<�uT�c���	���B�����K���b�\�N�uCc�+��G>^�x����5�"����l6�J�R_�.GV�AE0��|��8�7���+
��A��?�(VGK����1����.F��g�%���|qcc��z�.���[���8������8��p8��z	�b�����r211�D|�0����bu��Q�a�m����?���r��b\�K�.A08w?[������ij������bsL�<�RI���n$��`G�^5�c�q��|>�.a�RY�ZOGQ�c����"�P��������5��*�Z�^���uvo����������:���z��^�K�Z��'O��������	�0j�Z�eY�Q����hf��a���HvI��������E������i��j���at��U��O��~W�#.;�����	���F�!CCCR�T�2Jb7���[�V��0(B L���\.G�pt�Q�OV������hf ��v�K\8�?��*���|1;;������_�S�r��/�^�1q�$��y�CCCR(�vO����b�����8��J�e4A���v]#���"��K����\�QI/�s:�%u��O�������h��*���q�]F����Pz���y��ju2�ww��^�cY����&H�V���d�P��-���Y�r�|��0�������l6{�0X�T�G������.����.�����\.'�\�����|>I!&J�
f|�_������*����I/Q����r9�%�����3��d�����"���^����^����:��"i
�"�z-���H���0q�l0�l6�F�_��P����&�j���%*�J1����������\�?�R����n�#��8��w	�@�YLZ�`�y������1��OQ��u��J�H��J�u����R�v�|hL���8��F�!�J��w���������aO�Rb�0x�F�!�j��WX�L)U\ZZ:c��f�k��LB�r������t����������J���k�0����f��(���8#���O,Sf�^���T8���\��GnV�.�������'�Fc=��#^'��wN�E�a�0��������Q��Z/
�X4
�i<��P�0����\.����~����i�t�8��~�"�^����~��%��D�h4r���<����fGP���Z�6lj��~����r�\�V����4�����X��r��p��3���|��pd��z�r,��������v�}�������R*�fGq�����y��_����?�^Nl�?&��������+Y�c����^��;�#�<�[�s��d��L�n`�R�X����R��^��82�pQ�&YYY�"���k�[�w��pms+���K����LLLH��<���eY��|�M�>������Gk���WO9J�Oq�?�����^�H�23���i�����s��l��n�^fgg��r96GD_�a��j��\.Y����[���-3��p���\����;Zqk�Q(ED��|���= p`�����A�����/�^��R� );�2�����z����:"�2vS�T*m���E��8N��jEU~O�~!�v?��7��@��hH�P8������'�m?	zMq�9��������������`�8�G�6��f��u����4������<a
��m�f��Qn����X4��mms����~�0.���O���?�(V��v�~w�6��E�=��jsk����ems�;������"�C �Z�i��n��wO�0+����8�u82��eI�^���h���td���uAn���r��h����Y���������zzbb��r������"��6�.~�t����_������gH��"�Y������u����x���n�S�U�)���X�<vS$���""�V��q��u[�������M7�������cy�>���Q��k�*��zq��_'���SY{�%I�H�D�z_n�����(v�������D����E�����5�@_e�]�w�^�aS��nK.�����eY��V�Wq�<�2O�x�w��(`�[��r�#��������������??Z{��O����B��v��A���Fk�hyy�Ok��G@�$Iw_�@�2Z��e��Q����b\:������\��?��p�;���NH���X.
�h4��=n�pms������C��D+�;B��>�rQ�������3��=q�L���Ak=������*Zk�Z����m�����8��!vH��T*�Q
��HJ��N�����G:B������.:��X�<JG����Y��_/zz}�[��#��=~L*�.��g�����U����(�V�R�TD�}qG����\���v�h��}���VWW���������t�r�\���M���n����r�Qo�'%v�mn]�V����������=f8��s�}2�y/1��������R��:�����_s4&��8�88SC�w����]tGFFFD)���;���y�b��_]]�k���	~i��6�yaJ��?��f�����8����=}�+;��a�Ck=���~��CT���o?Om�.�����{!�xc�H����	i6��<�e�+���RbY����lY�� �a���3���FDDk=����v���?_l�.�j���6�ya�5����#ti�It���h����t�X�(��s�F ��� ���	�;,J������bu���_���v��cY�����p�����@�r�Ba;�"GE(����'C�eSS�b��$4M
�88S�phh�������b�\N����� � \�Z�G)y7�F��P(�^F��f���a�������p����]�J��z��Q-�k�f���?Z����tspp&����k1��z�����0�,��z�>mY�x�k!�u���o��~���������`h�CG�p���p�'3�"Ii��a��]l�Z��V�'
�$���^����]��n�!��_��h���""���}���Yb��\:?|��yY���x�3��1����\����3�8#	���
����y^ ���}l�.��e���=Q�%*�.���{���cq��P.aPD��lJ�V���d�V��E������uO���t�\:/�N���{�X�K�D�a���=Z��8�$&Ok=](n�������y^o\�swv
ED�������<�h�)�wq������Mbb���\���]����t����
��[:����,--���|B�g�Pk����q�k�����sg�q�%ew8�����m�U�- ��:!����w�$&��Is1�Y�����s��m���������0v�y�w7��}�::�R�z�>����Z��������Q�����Ol�~E��x��������WOe��Vj��?&����'d��6�sD���N����
}3a�����.�J���iY�����q=~W�FC
�B�_G�u�KKKQ.!����������C�6��^��f��`�dO����Jc���+�@��\L!p0IJ��#�����eh�n�Z�8;;�2�T*���\,�~KKK���i%�GkOg���������?}�TD���b����������>!���fz�:�E�������J��N�,k��o�1r��@�_��c����H-����q���������D��� v�l6�&3���y���A�����@w���������gz���N�{�h�����IDD���T*���w��^���������u�i43 �b�VOOOl���,�w]wxfffZ)u;��$
Me�\����f��qz��i6�����ZOOLL����KD��n?���H������F3{�=�f��	�c�v�QL0~�-��diii���������z!��^����z)�177'�l�B��`G��\���0h������@�|pn��bAc(}w�,k<��WVV�����a|��!J���V�WQ�c/�Ri!�����g�^KT|�?���$NM�^�T*-4��������k���z��p��[����o����z������!"�Ba�^7����<�[�f�^7�>�|��t_�M
����z:�u �&&&�"��2�������vES�n�+~����C��p�\>���k(l��J������������Q�<�\.��n�:!�fs������������~���9.!^���{��|,C��?�
����j�*CCC7��+��v�� ��^��(�T*����R_�x�������(��t��C �����X�B�g�HO�<�^�V�^J`��������/��O�B�������l6����b3[�Tqvv��j�z;w	��a��T��{D$v��wk��*��������������t(�FC��jj�V*��5#)�J;�$�R����g��Ek�n������8r���-�q��,����� ���
E^��|~xff��m�O�^��T�Ui4�
��5������b�^_tg2�� ����Z��s<H�w
B~���R������1q��m��#����z��z[k���n��������
�u���k[�������zz~~�V�������/�r9����Z��r!��K��d~�8S;�;
�.)�Wr�866&J)v�@�7j�Z=�\.����l.4�M�,k�u���W�F���w����l6���"����077��l6�-�B���� IDAT���)�JO���w��?@���6wf~g�D�Y�SJ����(��w��@�7�,+��P���a���F�!�e�;�3�s|aZ)u+���fskyy�����n���R��q�GS(��h�~���/o���:��O
�WBaY��Rj���~B�K'�J���)|�v����lJ���`Y��Rj�q9{�����h��/N<�[l������}Zk�Zw����4�������YIjS �^�Z�����;"
t�s�}3"������]"�v���~[�YTJM���{�o�e%���~������<����m�E������1���G��n�xA�n�o��D��M�I�N��m[��=+J�-��8�3��=!,M��u|�_�_4�����3�j�I76M���`�Cu���?���Hg���m�m{���;�<�W"�P��z����v�TJu(�y�������r�;�1�y���;w&�#��v��s�R�Z�������X^^~���8-td{�L���qw�1�{��6;;�cY�v�P� ��!�
�qdff&vcD�]�����y�Z�5�s��c��jvgY�8�3e8t����A�@�����V��kY�x�kAzy��011�444$�R�3w
�ZO
9y��z�PXHZ�a��T�K�!����j�Z�RJ�^���������l6{!��������&�u����g���dhhH����F���A���93;���-���:���4��#"J���V��qBa��\DO��Lk�P*����ntv��p�m:!0�������R���H�B)��S�LgV���l"F�QJWVV�V����P���9��r����,�r9�V���<o�T*�9
��2����]^^����eq
]��2\�V��K�P��ce������Z��3t��j�

}�����y��K.8�STJ�����Rj����h��=�����,�����m��8�����Hha����S�����(�'&&���/�z����{v�w;�����r�LK(�����DDnX����vGFFF�&$z������/@�F3�&��z�8��7C{83B���������R��=77����)���z}Z)�g[��{���P�[��~�y��7dg'qg�����-����$E����������I��Ek��5;?���m��"B��V��\�z�n�P��)E4fgg��r���W��P��=
���T��,QJ�eY222�eY���(�nE��E�����~+Zki����
7D�������px����iG ���L���L
��f���TC,�����������~�
��-��>���a��I��\��]��!�q�=�u��Y�m����v{|uuu�OQ�k��/{�T�k 6z�:���M/O��!���dii���<v
p]�X����+���Px;��m
�����������,��D��F�h����K�������X �;�vvO����V�wii�Pa��3F�u]�N�}�?m&���q#��.@ D$,��Z���������S.��+++=��L����n�\�k��g�s"�d���]7QGk���@�����=�z������8Nqcc��J�r�]�W�T*=KKK�e�F�Vc	����'�~�mh����
�����{666z��r���J�b���m�Z=a�Lr]�����]����I�Z����iG D�T*������	��g�v�^�z<t�u7[�GH�j��Q/H
!b��,��+t����FO>���(��U*�����/�RC����0*�l�`[��a��1t��j�z���)�n����[�w�B�!"�,�z~�piii�[� X�5������Z-�GCb'���B�n�����}���B@� "Q\�}gii�gcc��Z���]C�q:�B�����7�	B�n����D�&�7;7�g�����1R�B$�m�����==+++_���&:*���Z��n`>�e|D�\�}�n������6R��}f�����z
@`|�l6�O�����l��~�eY���_�zU\�Md�{�v�-sss������v�A��A�mooy!4�1���WY���c'���T*�����7�|��/�B D�y�w������U�</�`b�vQ)%ccc�8��R�v���&��-�����{v�B� �F#�@����qX���@����������<o�������h�*�e�+��m���g���8�J�)�4.!�G�6c�N.����@@���NX����7�8RJmY��@D���_$��K\4��j�J��.dY��m��Z�@��B Z����W�W#����B�������^�mo�����i���{���x�ww~~~2��=�TqffF��|O�R��ZG�$���0*�B ht�q�:cD��r�;���:�4WVV�XYY����=Q�	@8�A$�@�l���p��j�z��<c+��Y���D	�Vi�A��It#����q�������l6�r����f�I#��SJ�]�&����m��7@�15���n���RX��m;�G�E [������t����r_����HLt������.������t	!�D���Z�&��6��'�������F������^����/L�i��&�]�@ ql���������������v";�RJ�����-�u��#�@�q��j�&������@�)�n+�n��yy�����h�����Ek�.�>)��J)�q��F�:���C��@ u,�z~�����A��#B�?X�5���	�J�)�����{��|���z@���A������X��b�@�+���i��!��n�����z��������Sy�T)U�m[FFF�q�E�����?���R�V�u2}�h�i�e�D1�C xB]����c.^�kZ�����q��&ED���;�},w;�}"��p[�%J�N�������N+z05����E#��.C �=�S��WXyv�3 ���I�����Nx�mg7��;��m��������~[D�y����;�"���@�"�!�A���=C�!�z'@��i�eYa�b�Q/������@7!��,+vw03�d#����	 �A$�����@�"�P�6�P)d�0 �8��� ��(���bj����F
]�@�C��A����(t%! ������:�0QHS3}���R�z ����[]]5���s�f���D�"��m�7�@���:a���@t+!�8���^�#z�l d!!�����gL�3Q�!����@�#��.E ���{�w�Df�"���O��7Q��B����B@�p`��#�Pkm��X���H! f��Sf��b�k�M���z	@��=v���@��*����
�]f��X-������m��D n����=�A�[���j��F�r���i�7B�9C;�Z�i#��.F ���7�C�n��M��,�H ��8S
���Ff*��M���@�1�`��o�5Q�jB����:��H!�8�q=nfjN������1���xZ����t�����Z����
��@�}3�a�$��V�k�B ����A�y��N�""�e=0U�!��_��g#uL� ���vn�o�D���U3[�"�8���Z@��%��W�Oa������@�#p�c�@W�Z�c�v�H! ���T0���V��N�����:�G�#`_�5�A@ ���9���#�Ddll�T) ���HpoHSM�|����B��hpoH���i#wu���&���(��L���@HSC�?87`�K���=4Q��o�5QFDD,�z`�CB@*�b
t+S3M���m���1D @��Jo����b@��!�,�s��=�32r��,#G��8#"q������Lu5I)5���8S]��15���<c?c�e�*���
��P�������z�M�1�1XDddd�T) ���T0���F��N�0j�c0;���A�bj����&����R�#��zB@$
`/&!��!bj������2""Zk#wED�R�M���@H�"�n������v���3�g��H���� �g�C$��>8gf(���� �!"a��f�k�?���?G�������X p@�������`���:����&����={�T) ��Pf�\�
 L5S29O��7�3B@dl�.�<���Okm�#'�g���p��?�#'L� tg�X1 ��x%�#'|�_0Q���?8 S-��80�����6RH9�F DF)��Lv(�����v������ "���oG�o��	 ��x�4��p����! 2�eE��C��gd��&���A DF)�[z���|���:rB)u�X1 ���SGN(��&�IA ��z�:�E�kLH��	:�/""�8�T��3��"3���H! b���]7Q������S��D RCkm���-�O�0�a���	����Z@��4���m��0VH! RIm�0�1s�
�&GN�ax���g�lN����Zk#w��
��*&�Si����Z�v���x���2@���z	�r���n 
���B�����g��*$��*�v{���
D!3p�HP3���8���	$��������u���	�?�J�@g�i@ DJ)��7��vQ��=4Q�T�Q����~���*�����=�`����:J�a#���!"e��/�|��yf@Z�k0z��`�NRXa#"e��f�k8���;�H����A���#�DD)�e��$B@��:~���;�����D����Z@��s�����F��if����z�D����z��C��9V�f�H����M����B@��R�>���$ mLv5���2���{���}��{I����(e������]E�q9�0�@��m�Q/�P�
�E� p�:������&�(��L���@��m����7��H#SF=�3�kg�v��,��D""�p�o��6���Rf�4���:�:���o����8&��E D.�v��f�?��H!���u1RH*! ,��Y�:�����1x/��<#u��6RH(! �D����@h���eY�J��a���@�� ;��je/��	�K�is#'Lt�E�fB@,�={6�g�je/"�1���m4����:�:�2�x3! ��E����@tS�bM��a =�fB@,=�������W19����2�:�:��@z�
��XPJ����n������^�q�b�E� b���@����j����;W@�2�����<o!����@�� ���N�����&�h����� �?B@l�K�pz�`2�}M��Z�
��eY����@�������er��Y�H�����H�����p����>��p���(u0�Ig�[���{��G �F��'L�?u"�%Gb�9���2������A���<�H��?M D���k�g����R�v�u�� b����:���?��^'3p:�;������Z��&�	��*B@�y������=�u�O���(��������k\�zu+�"@��d3S�'L������?(b�g�q�wB/��+A��=���(����1c/4|�?��~�
e�)9��B@��i�D7�:�"�������<�I�5�^�v	 u��X	���)��!D��{o�T-�]�=z e���QJ�i���	:�"��\:?l���y�>����m���R�@��T`�2��^D�Q�����	�]�
��@j�322��L��y��H
G�4r���k�a���@��T`�/M���p��1�a�X�{����|����R�C-��;A6��Zk�ar�7p���x��������;��!b)��2�v����F:�XIq�����<o��n?����W��|>�fB@,9���|��M`{
� )
�����q�u�	��fB@,�Xfyy�XP3}8(G�F/��	��GC ���8��4�X�������r����6��Fk��	��GC ��m���mr�0����f��!b���1�G���f��&l�.r\8! ��Po������d!�����F���s'��3�8:! ����{�������;Z�~]�������(����#b�u��v�VWW�z�]��g���t3�F���m�.2�8:! ��G�c�e430����z�~L}���������33�w�@ �ZP��>�������!3�'���p�.&��y��fB@�y�0�#l���
�����X�]������[�m{3�@� b�u�����������tGG`/��N��K��o�����WC}>�M��X�,K�R��#l6�FwI�>TM��R�r�����z:����e�����^��@���v������
���=��*|O�������|~>�7��H;! �\�
l���{�&�z�~\��������	'~ff�f2@����SJ�j�D���1�v���aFP 
������FC�������8�d�����n ��}��ln��}��#������\0>�/�����]��@7"���k��s�N_P����G���1�%���\:ot��H��dl�.�L��]�}��=$���������l�n��d��A $FP�FED�������?�`��X�k���i4��������;��@H� ��6���o�G�F3��F���%��-�
���z����^�644���~ ;KKK���O8���k]�"����W��Hj�<yr=�����];��D��	�q�����0(�.!�s��?�d�e�Ze��`��������A=og���}B��?�������H�+��G�HF$���V���8�TX��;��D�m{S)H�Q�j�j4��q���EM��p�d��f�i��s	�����z�����������333���	��n`3����j����-��^H���������Q�{w���������|������FPg���A�T�����dT���,��a>�! ��^���|�_�"����8����*W.��+��GU�P(��;���D@ $����
�yv������<c(pPQv�ZO7�@f��
���9��$V�C�E���7~�1������H.���B�J����
���!��u�@�W�V#��E��G�`���
3���j��0��E�Kk��l6{!�gF�KX��{y���tY$D��H�C��)�Z-v��!$�R��m��u�n�p��O�M�=}|�b,�`�T
����H�\fw0�@H���`uz���y^$J+�.�a/��/�?
t�P<�[�����h>�/:�3f
���Q@���?844t#�g�[���Vi�A��e$�������������lhhH�l������Ol�����c��hA�y�K�l6��|�~U������-3�'^�_%.a�T*���r�0D�@H�k����R�Y*�^�|����i���,����IGE-������! ���|�&}�_h4A?v_2�}�O�]z����?����G��LLL�~��V�
[�v��B@*LLLl7��@w2,����o��|�A��lEn���Q��!�z_n������=a�a��R�����?��n?�V��?w��>���K�#��p�?&7��b�`�Z
=���j���kx=v�q�����������I���/:�����Y�����f��5���7IDAT11�v����b�Vcw�;��������,
��A:���hf@oL]�k�ZO
����c�v�\.�`��Z��e��P�`,--M��i*�����mF2
G���\�����d�ky�l6+Z�����Z�^���@ �J.�����m������{`���x�����}�?uB�W.�_�t>��D�e����������%v����( U��I(�lE�T
��q���h&�O��J����_$	a�P(	��e���u� #�R'��2"���E~�����(w?[�zxI�v;
��4�����������`����T*��j5��q9:*"r��/�o���������^J�s��2�����G���h4R(���|>_dw�! u|����w�����Y���x���>����G�K�:�����K�c;>�ML�A���+++=�e�(���T*
�a��C���h6c�hf@�����:�2�aP���@���
�g�1����XO�X���I�����	����R�(�o)cL��r�\�T*b�@H��FPt8�Sl�Za=���-F��������^��=�z=A�V�R�T������ cB@jy�w7��}f�J�R,��a�8�GkOg*�?�s��`�;Lvy������>��x#R-�]B���'��N�o���+�~(dR;L�A�
IA ���]B���[����R���s�~!�������������2z��D7���l6+Zk�a�V�ggg9*
$��z&v	�R����������w?��k�[Q/�����d43 ���R��2������-����A�
�B ���]B��6�������������������wk4R*������u�R�V���A A���`b�P���H�e���=�>��p���s}2z���s}S�w+�J277gtWP�&2@R]��.�H|;������3���<��������Q/�{:�/3xZ�
���f��^S\��fbb�����"/���m�6��!�����v��4�a�^�����R�z��t������������?������$3�'��NH���8����|����N���*
��>"������A �����������
S��
��h����������6��u���:F3��<�Ov�cbbBL���aH6!���J�m����
��wEDfgg��Z�0$��U���

}m�C4�A�zWP��@Z� �`�eYR���#/
�F�dI������<yr�0 (����1��S���<o�Z�N����aHv]�V�M��Y(
����H0���
��r���@�JJ���r�h�n�� b_���d�Y��hDE�@Zqd�����v���R����e��jU�������2� �^��Z�^7~tTDDk�044$Z�H�#~����<yr�R�,��!��U*��j��`���#bq��`� �~B$���;�0Q��a����s����A��/*�@��������s����z}�q�����pi�����o��Q�����BD���M��_���B.���Z�F����hH6��l6{!�a�������/�@�`��]
��v>��[�|�������h4b{,t7�Tqii��m��Q��9B^�}���[�<�FC���%.�C���n�^��X��RF �%q�O��eY������r9��������;w���fbB`G�\.V*��]�@���?�f��^�n�m���0�"�����{����f"�������z�����;Q�@t��B���.
���!F��h����$5vp_@���(�J�sss��"C|�?�l6����X~���F �
��y�U:w�]�v���'Q�'�������r_����c�u?(�����}��r����>��[�v�����}Q�%)��������y�$�k|������"
�{��C���\.�qobY�����333�J�[Q�'N<�[�ZO.//��y���&�e�������Y�����}JZ(��m�������u����y�����i����8�z�N��E ��
;,�wgxllL�I����zZk}kyyY������k��p>�gW�8�����:Q)%ccc���LF����<o������U�Zw�������b�V�� �}#pi
�/�m�h��8�#g����#���-��,//O��m�Z�������T�V�-:�3�Z$��#��H��)���e�eY��z�����lY�u��,��O>~����{�'"��v�v8
���Q��B�C�\.���r<��@���.
�B�.����2�C�@@@<��;11q!�s�� �0����O�����@@�����J%��H�L �F��]*��9B���,k|fff8��A  D!�~��],����.]C���@��������S.��Q����n��j�nll���y� ��!����
��-v��m��k��	�B���������*w�L>�/^�zu�u�w�^t������j�	�H��q���k�� ��D�����ju��<�aJ(�:!�#�b�@@4��j�*��� ����09\�-^�z����@@�������266Fc�A  ����_�����ch�eY������q@jH������o5�M�U��q����W�q�i�����a#� �v[�������0��hv�*����zM`����}��l>�s��pl�.:�####��!)�	�����>�8Nqg�o�q�w�
�G  e���x������>���b�����RJ������ �r�����[^^�u��8�S�m[FFFD)����b��@@�}Pk�Hk�����	���ITJ-����={V�R��m���,!x��n�������y�""�?����=��at�������DDd'�-����f���r���b�IEND�B`�
#2Michał Kłeczek
michal@kleczek.org
In reply to: Michał Kłeczek (#1)
1 attachment(s)
DRAFT GIST support for ORDER BY

Hi All,

Attached is a first attempt to implement GIST index (only) scans for ORDER BY column clauses.

The idea is that it order by column for some datatypes is a special case of ordering by distance:

ORDER BY a == ORDER BY a <-> MIN_VALUE
and
ORDER BY a DESC == ORDER BY a <-> MAX_VALUE

This allows implementing GIST ordered scans for btree_gist datatypes.

This in turn makes using GIST with partitioning feasible (I have described issues with such usage in my previous e-mails - see below).

The solution is not ideal as it requires registering “<“ and “>” operators as ordering operators in opfamily
(which in turn makes it possible to issue somewhat meaningless “ORDER BY a < ‘constant’)

The problem is though that right now handling of ORDER BY column clauses is tightly coupled to BTree.
It would be good to refactor the code so that semantics of ORDER BY column could be more flexible.

It would be great if someone could take a look at it.

Thanks,
Michal

Show quoted text

On 24 Oct 2023, at 13:22, Michał Kłeczek <michal@kleczek.org> wrote:

Hi,

Some time ago I’ve provided some details with the issues we face when trying to use GIST and partitioning at the same time in the postgresql-general mailing list:
/messages/by-id/3FA1E0A9-8393-41F6-88BD-62EEEA1EC21F@kleczek.org
We decided to go with the solution to partition our table by:

RANGE (‘2100-01-01' <-> operation_date).

While it (somewhat) solves partition pruning issues described above there is another problem:
It is impossible to create a unique constraint on the partitioned table.

So now we cannot use INSERT … ON CONFLICT (…) DO UPDATE

My question to hackers:
Would it be feasible to implement ORDER BY column GIST index (only) scan for types with total order and sensible greatest and least values?

Thanks,
Michal

Attachments:

DRAFT-gist-orderby.patchapplication/octet-stream; name=DRAFT-gist-orderby.patch; x-unix-mode=0644Download
diff --git a/contrib/btree_gist/btree_date.c b/contrib/btree_gist/btree_date.c
index 68a4107dbf..1941459025 100644
--- a/contrib/btree_gist/btree_date.c
+++ b/contrib/btree_gist/btree_date.c
@@ -178,6 +178,21 @@ gbt_date_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	DateADT		query = PG_GETARG_DATEADT(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = DATEVAL_NOBEGIN;
+			break;
+
+		case RTGreaterStrategyNumber:
+			query = DATEVAL_NOEND;
+			break;
+		
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	dateKEY    *kkk = (dateKEY *) DatumGetPointer(entry->key);
diff --git a/contrib/btree_gist/btree_gist--1.6--1.7.sql b/contrib/btree_gist/btree_gist--1.6--1.7.sql
index 1085216501..e1cc256e01 100644
--- a/contrib/btree_gist/btree_gist--1.6--1.7.sql
+++ b/contrib/btree_gist/btree_gist--1.6--1.7.sql
@@ -75,3 +75,29 @@ AS
 	FUNCTION	7	gbt_bool_same (gbtreekey2, gbtreekey2, internal),
 	FUNCTION	9   gbt_bool_fetch (internal),
 	STORAGE		gbtreekey2;
+
+
+-- Add ORDER BY support for int2, int4, int8, date, ts, time
+ALTER OPERATOR FAMILY gist_int2_ops USING gist ADD
+	OPERATOR	20	< (int2, int2) FOR ORDER BY pg_catalog.integer_ops,
+	OPERATOR	22	> (int2, int2) FOR ORDER BY pg_catalog.integer_ops;
+
+ALTER OPERATOR FAMILY gist_int4_ops USING gist ADD
+	OPERATOR	20	< (int4, int4) FOR ORDER BY pg_catalog.integer_ops,
+	OPERATOR	22	> (int4, int4) FOR ORDER BY pg_catalog.integer_ops;
+
+ALTER OPERATOR FAMILY gist_int8_ops USING gist ADD
+	OPERATOR	20	< (int8, int8) FOR ORDER BY pg_catalog.integer_ops,
+	OPERATOR	22	> (int8, int8) FOR ORDER BY pg_catalog.integer_ops;
+
+ALTER OPERATOR FAMILY gist_date_ops USING gist ADD
+	OPERATOR	20	< (date, date) FOR ORDER BY pg_catalog.integer_ops,
+	OPERATOR	22	> (date, date) FOR ORDER BY pg_catalog.integer_ops;
+
+ALTER OPERATOR FAMILY gist_timestamp_ops USING gist ADD
+	OPERATOR	20	< (timestamp, timestamp) FOR ORDER BY pg_catalog.interval_ops,
+	OPERATOR	22	> (timestamp, timestamp) FOR ORDER BY pg_catalog.interval_ops;
+
+ALTER OPERATOR FAMILY gist_timestamptz_ops USING gist ADD
+	OPERATOR	20	< (timestamptz, timestamptz) FOR ORDER BY pg_catalog.interval_ops,
+	OPERATOR	22	> (timestamptz, timestamptz) FOR ORDER BY pg_catalog.interval_ops;
diff --git a/contrib/btree_gist/btree_int2.c b/contrib/btree_gist/btree_int2.c
index fdbf156586..760a83ca4d 100644
--- a/contrib/btree_gist/btree_int2.c
+++ b/contrib/btree_gist/btree_int2.c
@@ -160,6 +160,19 @@ gbt_int2_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	int16		query = PG_GETARG_INT16(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = PG_INT16_MIN;
+			break;
+		case RTGreaterStrategyNumber:
+			query = PG_INT16_MAX;
+			break;
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	int16KEY   *kkk = (int16KEY *) DatumGetPointer(entry->key);
diff --git a/contrib/btree_gist/btree_int4.c b/contrib/btree_gist/btree_int4.c
index 8915fb5d08..8f072e55c0 100644
--- a/contrib/btree_gist/btree_int4.c
+++ b/contrib/btree_gist/btree_int4.c
@@ -161,6 +161,19 @@ gbt_int4_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	int32		query = PG_GETARG_INT32(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = PG_INT32_MIN;
+			break;
+		case RTGreaterStrategyNumber:
+			query = PG_INT32_MAX;
+			break;
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	int32KEY   *kkk = (int32KEY *) DatumGetPointer(entry->key);
diff --git a/contrib/btree_gist/btree_int8.c b/contrib/btree_gist/btree_int8.c
index 7c63a5b6dc..ac2c35f059 100644
--- a/contrib/btree_gist/btree_int8.c
+++ b/contrib/btree_gist/btree_int8.c
@@ -161,6 +161,21 @@ gbt_int8_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	int64		query = PG_GETARG_INT64(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = PG_INT64_MIN;
+			break;
+
+		case RTGreaterStrategyNumber:
+			query = PG_INT64_MAX;
+			break;
+		
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	int64KEY   *kkk = (int64KEY *) DatumGetPointer(entry->key);
diff --git a/contrib/btree_gist/btree_time.c b/contrib/btree_gist/btree_time.c
index d89401c0f5..e06efc0ceb 100644
--- a/contrib/btree_gist/btree_time.c
+++ b/contrib/btree_gist/btree_time.c
@@ -225,6 +225,21 @@ gbt_time_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	TimeADT		query = PG_GETARG_TIMEADT(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = PG_INT64_MIN;
+			break;
+
+		case RTGreaterStrategyNumber:
+			query = PG_INT64_MAX;
+			break;
+
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	timeKEY    *kkk = (timeKEY *) DatumGetPointer(entry->key);
diff --git a/contrib/btree_gist/btree_ts.c b/contrib/btree_gist/btree_ts.c
index 3f5ba91891..b2b019a35c 100644
--- a/contrib/btree_gist/btree_ts.c
+++ b/contrib/btree_gist/btree_ts.c
@@ -274,6 +274,21 @@ gbt_ts_distance(PG_FUNCTION_ARGS)
 {
 	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 	Timestamp	query = PG_GETARG_TIMESTAMP(1);
+	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+
+	switch (strategy)
+	{
+		case RTLessStrategyNumber:
+			query = TIMESTAMP_MINUS_INFINITY;
+			break;
+
+		case RTGreaterStrategyNumber:
+			query = TIMESTAMP_INFINITY;
+			break;
+
+		default:
+			break;
+	}
 
 	/* Oid		subtype = PG_GETARG_OID(3); */
 	tsKEY	   *kkk = (tsKEY *) DatumGetPointer(entry->key);
diff --git a/src/backend/executor/nodeBitmapIndexscan.c b/src/backend/executor/nodeBitmapIndexscan.c
index 7cf8532bc9..9db905f36e 100644
--- a/src/backend/executor/nodeBitmapIndexscan.c
+++ b/src/backend/executor/nodeBitmapIndexscan.c
@@ -269,7 +269,7 @@ ExecInitBitmapIndexScan(BitmapIndexScan *node, EState *estate, int eflags)
 	ExecIndexBuildScanKeys((PlanState *) indexstate,
 						   indexstate->biss_RelationDesc,
 						   node->indexqual,
-						   false,
+						   NULL,
 						   &indexstate->biss_ScanKeys,
 						   &indexstate->biss_NumScanKeys,
 						   &indexstate->biss_RuntimeKeys,
diff --git a/src/backend/executor/nodeIndexonlyscan.c b/src/backend/executor/nodeIndexonlyscan.c
index f1db35665c..7ba350c3fa 100644
--- a/src/backend/executor/nodeIndexonlyscan.c
+++ b/src/backend/executor/nodeIndexonlyscan.c
@@ -563,7 +563,7 @@ ExecInitIndexOnlyScan(IndexOnlyScan *node, EState *estate, int eflags)
 	ExecIndexBuildScanKeys((PlanState *) indexstate,
 						   indexstate->ioss_RelationDesc,
 						   node->indexqual,
-						   false,
+						   NULL,
 						   &indexstate->ioss_ScanKeys,
 						   &indexstate->ioss_NumScanKeys,
 						   &indexstate->ioss_RuntimeKeys,
@@ -577,7 +577,7 @@ ExecInitIndexOnlyScan(IndexOnlyScan *node, EState *estate, int eflags)
 	ExecIndexBuildScanKeys((PlanState *) indexstate,
 						   indexstate->ioss_RelationDesc,
 						   node->indexorderby,
-						   true,
+						   node->indexorderbyops,
 						   &indexstate->ioss_OrderByKeys,
 						   &indexstate->ioss_NumOrderByKeys,
 						   &indexstate->ioss_RuntimeKeys,
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c
index 14b9c00217..fb8057c446 100644
--- a/src/backend/executor/nodeIndexscan.c
+++ b/src/backend/executor/nodeIndexscan.c
@@ -968,7 +968,7 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
 	ExecIndexBuildScanKeys((PlanState *) indexstate,
 						   indexstate->iss_RelationDesc,
 						   node->indexqual,
-						   false,
+						   NULL,
 						   &indexstate->iss_ScanKeys,
 						   &indexstate->iss_NumScanKeys,
 						   &indexstate->iss_RuntimeKeys,
@@ -982,7 +982,7 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
 	ExecIndexBuildScanKeys((PlanState *) indexstate,
 						   indexstate->iss_RelationDesc,
 						   node->indexorderby,
-						   true,
+						   node->indexorderbyops,
 						   &indexstate->iss_OrderByKeys,
 						   &indexstate->iss_NumOrderByKeys,
 						   &indexstate->iss_RuntimeKeys,
@@ -1134,12 +1134,13 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
  */
 void
 ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
-					   List *quals, bool isorderby,
+					   List *quals, List* orderbyops,
 					   ScanKey *scanKeys, int *numScanKeys,
 					   IndexRuntimeKeyInfo **runtimeKeys, int *numRuntimeKeys,
 					   IndexArrayKeyInfo **arrayKeys, int *numArrayKeys)
 {
 	ListCell   *qual_cell;
+	ListCell   *orderbyop_cell;
 	ScanKey		scan_keys;
 	IndexRuntimeKeyInfo *runtime_keys;
 	IndexArrayKeyInfo *array_keys;
@@ -1148,6 +1149,7 @@ ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
 	int			max_runtime_keys;
 	int			n_array_keys;
 	int			j;
+	bool		isorderby	= (orderbyops != NULL);
 
 	/* Allocate array for ScanKey structs: one per qual */
 	n_scan_keys = list_length(quals);
@@ -1168,12 +1170,19 @@ ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
 		palloc0(n_scan_keys * sizeof(IndexArrayKeyInfo));
 	n_array_keys = 0;
 
+	/*
+	 * Make sure forboth below works in all cases
+	 */
+	if (!isorderby)
+	{
+		orderbyops = quals;
+	}
 	/*
 	 * for each opclause in the given qual, convert the opclause into a single
 	 * scan key
 	 */
 	j = 0;
-	foreach(qual_cell, quals)
+	forboth(qual_cell, quals, orderbyop_cell, orderbyops)
 	{
 		Expr	   *clause = (Expr *) lfirst(qual_cell);
 		ScanKey		this_scan_key = &scan_keys[j++];
@@ -1596,8 +1605,30 @@ ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
 								   InvalidOid,	/* no reg proc for this */
 								   (Datum) 0);	/* constant */
 		}
+		else if (isorderby && IsA(clause, Var))
+		{
+			Var	*var	= (Var *) clause;
+			int	flags	= SK_ORDER_BY;
+			varattno	= var->varattno;
+			opfamily	= index->rd_opfamily[varattno - 1];
+			opno		= lfirst(orderbyop_cell);
+			
+			get_op_opfamily_properties(opno, opfamily, isorderby,
+									   &op_strategy,
+									   &op_lefttype,
+									   &op_righttype);
+
+			ScanKeyEntryInitialize(this_scan_key,
+								   flags,
+								   varattno,	/* attribute number to scan */
+								   op_strategy, /* op's strategy */
+								   InvalidOid,	/* strategy subtype */
+								   var->varcollid,	/* collation */
+								   get_opcode(opno),	/* reg proc to use */
+								   (Datum) 0);	/* constant */
+		}
 		else
-			elog(ERROR, "unsupported indexqual type: %d",
+			elog(ERROR, "nodeIndexscan unsupported indexqual type: %d",
 				 (int) nodeTag(clause));
 	}
 
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 03a5fbdc6d..0855f917ea 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -188,7 +188,8 @@ static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 									List **orderby_clauses_p,
 									List **clause_columns_p);
 static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
-										 int indexcol, Expr *clause, Oid pk_opfamily);
+										 int indexcol, Expr *clause,
+										 Oid pk_opfamily, int pk_strategy);
 static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
 									   EquivalenceClass *ec, EquivalenceMember *em,
 									   void *arg);
@@ -3092,8 +3093,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 
 
 		/* Pathkey must request default sort order for the target opfamily */
-		if (pathkey->pk_strategy != BTLessStrategyNumber ||
-			pathkey->pk_nulls_first)
+		/* Fixme !!! */
+		if (!(pathkey->pk_strategy == BTLessStrategyNumber && !pathkey->pk_nulls_first || pathkey->pk_strategy == BTGreaterStrategyNumber && pathkey->pk_nulls_first))
 			return;
 
 		/* If eclass is volatile, no hope of using an indexscan */
@@ -3132,7 +3133,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
 				expr = match_clause_to_ordering_op(index,
 												   indexcol,
 												   member->em_expr,
-												   pathkey->pk_opfamily);
+												   pathkey->pk_opfamily,
+												   pathkey->pk_strategy);
 				if (expr)
 				{
 					*orderby_clauses_p = lappend(*orderby_clauses_p, expr);
@@ -3184,7 +3186,8 @@ static Expr *
 match_clause_to_ordering_op(IndexOptInfo *index,
 							int indexcol,
 							Expr *clause,
-							Oid pk_opfamily)
+							Oid pk_opfamily,
+							int pk_strategy)
 {
 	Oid			opfamily;
 	Oid			idxcollation;
@@ -3200,6 +3203,46 @@ match_clause_to_ordering_op(IndexOptInfo *index,
 	opfamily = index->opfamily[indexcol];
 	idxcollation = index->indexcollations[indexcol];
 
+	/*
+	 * If clause is a Var and matches the index then
+	 * try to find an ordering operator
+	 * registered as ordering operator in index operator family
+	 */
+	if (clause && IsA(clause, Var) && match_index_to_operand(clause, indexcol, index))
+	{
+		Var	*var = (Var *) clause;
+		/*
+		 * Copied from createplan.c - find ordering operator
+		 * There is an opportunity for refactoring
+		 * to avoid double cache lookup here and in creatplan
+		 */
+		Oid sortop = get_opfamily_member(pk_opfamily,
+										 var->vartype,
+										 var->vartype,
+										 pk_strategy);
+		/*
+		 * This should not happen???
+		 * For now just return no-match
+		 * Alternative is to err
+		 */
+		if (sortop == InvalidOid)
+			return NULL;
+
+		/*
+		 * Make sure
+		 * 1) ordering operator is registered in pg_amop for index am
+		 * 2) sort family is the same as requested ordering op family (BTree)
+		 */
+		Oid sortfamily = get_op_opfamily_sortfamily(sortop, opfamily);
+		if (sortfamily == pk_opfamily)
+			return clause;
+
+		/*
+		 * No match
+		 */
+		return NULL;
+	}
+
 	/*
 	 * Clause must be a binary opclause.
 	 */
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 34ca6d4ac2..b364419d08 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -189,6 +189,7 @@ static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
 										 Index scanrelid, Oid indexid,
 										 List *indexqual, List *recheckqual,
 										 List *indexorderby,
+										 List *indexorderbyops,
 										 List *indextlist,
 										 ScanDirection indexscandir);
 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
@@ -3170,6 +3171,7 @@ create_indexscan_plan(PlannerInfo *root,
 												fixed_indexquals,
 												stripped_indexquals,
 												fixed_indexorderbys,
+												indexorderbyops,
 												indexinfo->indextlist,
 												best_path->indexscandir);
 	else
@@ -5114,6 +5116,10 @@ fix_indexqual_clause(PlannerInfo *root, IndexOptInfo *index, int indexcol,
 												 index,
 												 indexcol);
 	}
+	else if (IsA(clause, Var))
+	{
+		clause = fix_indexqual_operand(clause, index, indexcol);
+	}
 	else
 		elog(ERROR, "unsupported indexqual type: %d",
 			 (int) nodeTag(clause));
@@ -5551,6 +5557,7 @@ make_indexonlyscan(List *qptlist,
 				   List *indexqual,
 				   List *recheckqual,
 				   List *indexorderby,
+				   List *indexorderbyops,
 				   List *indextlist,
 				   ScanDirection indexscandir)
 {
@@ -5566,6 +5573,7 @@ make_indexonlyscan(List *qptlist,
 	node->indexqual = indexqual;
 	node->recheckqual = recheckqual;
 	node->indexorderby = indexorderby;
+	node->indexorderbyops = indexorderbyops;
 	node->indextlist = indextlist;
 	node->indexorderdir = indexscandir;
 
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c4fcd0076e..2233a213c1 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6414,6 +6414,10 @@ index_other_operands_eval_cost(PlannerInfo *root, List *indexquals)
 		{
 			other_operand = NULL;
 		}
+		else if (IsA(clause, Var))
+		{
+			other_operand = (Node *) clause;
+		}
 		else
 		{
 			elog(ERROR, "unsupported indexqual type: %d",
diff --git a/src/include/executor/nodeIndexscan.h b/src/include/executor/nodeIndexscan.h
index 8ee7969792..de6d77f1c3 100644
--- a/src/include/executor/nodeIndexscan.h
+++ b/src/include/executor/nodeIndexscan.h
@@ -34,7 +34,8 @@ extern void ExecIndexScanInitializeWorker(IndexScanState *node,
  * nodeBitmapIndexscan.c
  */
 extern void ExecIndexBuildScanKeys(PlanState *planstate, Relation index,
-								   List *quals, bool isorderby,
+								   List *quals,
+								   List *orderbyops,
 								   ScanKey *scanKeys, int *numScanKeys,
 								   IndexRuntimeKeyInfo **runtimeKeys, int *numRuntimeKeys,
 								   IndexArrayKeyInfo **arrayKeys, int *numArrayKeys);
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 24d46c76dc..350dede16e 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -495,6 +495,7 @@ typedef struct IndexOnlyScan
 	List	   *indexqual;		/* list of index quals (usually OpExprs) */
 	List	   *recheckqual;	/* index quals in recheckable form */
 	List	   *indexorderby;	/* list of index ORDER BY exprs */
+	List	   *indexorderbyops;/* OIDs of sort ops for ORDER BY exprs */
 	List	   *indextlist;		/* TargetEntry list describing index's cols */
 	ScanDirection indexorderdir;	/* forward or backward or don't care */
 } IndexOnlyScan;
#3Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: Michał Kłeczek (#2)
Re: DRAFT GIST support for ORDER BY

On Mon, 30 Oct 2023 at 09:04, Michał Kłeczek <michal@kleczek.org> wrote:

Hi All,

Attached is a first attempt to implement GIST index (only) scans for ORDER BY column clauses.

Cool!

The solution is not ideal as it requires registering “<“ and “>” operators as ordering operators in opfamily
(which in turn makes it possible to issue somewhat meaningless “ORDER BY a < ‘constant’)

I don't quite understand why we need to register new "<" and ">"
operators. Can't we update the current ones?

The problem is though that right now handling of ORDER BY column clauses is tightly coupled to BTree.
It would be good to refactor the code so that semantics of ORDER BY column could be more flexible.

The existence of a BTREE operator class for the type is the indicator
that (and how) the type can be ordered - that is where PostgreSQL gets
its methods for ordering most types. Although I agree that it's a
quirk, I don't mind it that much as an indicator of how a type is
ordered.
I do agree, though, that operator classes by themselves should be able
to say "hey, we support full ordered retrieval as well". Right now,
that seems to be limited to btrees, but indeed a GiST index with
btree_gist columns should be able to support the same.

It would be great if someone could take a look at it.

I've not looked in detail at the patch, but here's some comments:

--- a/contrib/btree_gist/btree_gist--1.6--1.7.sql
+++ b/contrib/btree_gist/btree_gist--1.6--1.7.sql

You seem to be modifying an existing migration of a released version
of the btree_bist extension. I suggest you instead add a migration
from 1.7 to a new version 1.8, and update the control file's default
installed version.

ORDER BY a == ORDER BY a <-> MIN_VALUE
and
ORDER BY a DESC == ORDER BY a <-> MAX_VALUE

This allows implementing GIST ordered scans for btree_gist datatypes.

This in turn makes using GIST with partitioning feasible (I have described issues with such usage in my previous e-mails - see below).

Did you take into account that GiST's internal distance function uses
floating point, and is thus only an approximation for values that
require more than 2^54 significant bits in their distance function?
For example, GiST wouldn't be guaranteed to yield correct ordering of
int8/bigint when you use `my_column <-> UINT64_MAX` because as far as
the floating point math is concerned, 0 is about as far away from
INT64_MAX as (say) 20 and -21.

Kind regards,

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

#4Michał Kłeczek
michal@kleczek.org
In reply to: Matthias van de Meent (#3)
Re: DRAFT GIST support for ORDER BY

On 30 Oct 2023, at 13:31, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

The solution is not ideal as it requires registering “<“ and “>” operators as ordering operators in opfamily
(which in turn makes it possible to issue somewhat meaningless “ORDER BY a < ‘constant’)

I don't quite understand why we need to register new "<" and ">"
operators. Can't we update the current ones?

I wasn’t precise: what is needed is adding pg_amop entries with amoppurpose = ‘o’ for existing “<" and “>" operators.

The problem is though that right now handling of ORDER BY column clauses is tightly coupled to BTree.
It would be good to refactor the code so that semantics of ORDER BY column could be more flexible.

The existence of a BTREE operator class for the type is the indicator
that (and how) the type can be ordered - that is where PostgreSQL gets
its methods for ordering most types. Although I agree that it's a
quirk, I don't mind it that much as an indicator of how a type is
ordered.
I do agree, though, that operator classes by themselves should be able
to say "hey, we support full ordered retrieval as well". Right now,
that seems to be limited to btrees, but indeed a GiST index with
btree_gist columns should be able to support the same.

Right now opfamily and strategy are set in PathKey before creating index scan paths.

The patch actually copies existing code from create_indexscan_plan
that finds an operator OID for (pk_opfamily, pk_strategy).
The operator is supposed to be binary with specific operand types.

To create a path:
1) do the operator OID lookup as above
2) look for sortfamily of pg_amop entry for (operator did, index opfamily)
If the sort family is the same as pk_opfamily we can create a path.

The side effect is that it is possible to “ORDER BY column < ‘constant’” as we have more ordering operators in pg_amop.

Ideally we could look up _unary_ operator in pg_amop instead - that would make sense we are actually measuring some “absolute distance”.
But this would require more changes - createplan.c would need to decide when to lookup unary and when - binary operator.

It would be great if someone could take a look at it.

I've not looked in detail at the patch, but here's some comments:

--- a/contrib/btree_gist/btree_gist--1.6--1.7.sql
+++ b/contrib/btree_gist/btree_gist--1.6--1.7.sql

You seem to be modifying an existing migration of a released version
of the btree_bist extension. I suggest you instead add a migration
from 1.7 to a new version 1.8, and update the control file's default
installed version.

Thanks. I didn’t know how to register a new migration so did it that way.
Will try to fix that.

ORDER BY a == ORDER BY a <-> MIN_VALUE
and
ORDER BY a DESC == ORDER BY a <-> MAX_VALUE

This allows implementing GIST ordered scans for btree_gist datatypes.

This in turn makes using GIST with partitioning feasible (I have described issues with such usage in my previous e-mails - see below).

Did you take into account that GiST's internal distance function uses
floating point, and is thus only an approximation for values that
require more than 2^54 significant bits in their distance function?
For example, GiST wouldn't be guaranteed to yield correct ordering of
int8/bigint when you use `my_column <-> UINT64_MAX` because as far as
the floating point math is concerned, 0 is about as far away from
INT64_MAX as (say) 20 and -21.

Hmm… Good point but it means ORDER BY <-> is broken for these types then?
The patch assumes it works correctly and just uses it for ordered scans.


Michal

#5Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: Michał Kłeczek (#4)
Re: DRAFT GIST support for ORDER BY

On Mon, 30 Oct 2023 at 14:39, Michał Kłeczek <michal@kleczek.org> wrote:

On 30 Oct 2023, at 13:31, Matthias van de Meent <boekewurm+postgres@gmail.com> wrote:

The problem is though that right now handling of ORDER BY column clauses is tightly coupled to BTree.
It would be good to refactor the code so that semantics of ORDER BY column could be more flexible.

The existence of a BTREE operator class for the type is the indicator
that (and how) the type can be ordered - that is where PostgreSQL gets
its methods for ordering most types. Although I agree that it's a
quirk, I don't mind it that much as an indicator of how a type is
ordered.
I do agree, though, that operator classes by themselves should be able
to say "hey, we support full ordered retrieval as well". Right now,
that seems to be limited to btrees, but indeed a GiST index with
btree_gist columns should be able to support the same.

Right now opfamily and strategy are set in PathKey before creating index scan paths.

The patch actually copies existing code from create_indexscan_plan
that finds an operator OID for (pk_opfamily, pk_strategy).
The operator is supposed to be binary with specific operand types.

To create a path:
1) do the operator OID lookup as above
2) look for sortfamily of pg_amop entry for (operator did, index opfamily)
If the sort family is the same as pk_opfamily we can create a path.

The side effect is that it is possible to “ORDER BY column < ‘constant’” as we have more ordering operators in pg_amop.

Ideally we could look up _unary_ operator in pg_amop instead - that would make sense we are actually measuring some “absolute distance”.
But this would require more changes - createplan.c would need to decide when to lookup unary and when - binary operator.

After researching this a bit more, I'm confused: If I register an opclass

CREATE OPERATOR CLASS gist_mytype_btree
DEFUALT FOR mytype USING gist
AS
OPERATOR 1 < (mytype, mytype) FOR ORDER BY mytype_ops, -- operator
<(mytype, mytype) returns bool
...
OPERATOR 15 <-> (mytype, mytype) FOR ORDER BY mytype_ops. --
operator <->(mytype, mytype) returns mytype
...

Then which order of values does the system expect the index to return
tuples in when either of these operators is applied?
Is that
ORDER BY (index_column opr constant); but bool isn't the type
supported by the FOR ORDER BY opclass, or
ORDER BY (index_column); but this makes no sense for distance operators.

After looking at get_relation_info() in optimizer/util/plancat.c, I
guess the difference is the difference between amhandler->amcanorder
vs amhandler->amcanorderbyop? But still it's not quite clear what the
implication for this is. Does it mean an index AM can either provide
natural ordering, or operator ordering, but not both?

ORDER BY a == ORDER BY a <-> MIN_VALUE
and
ORDER BY a DESC == ORDER BY a <-> MAX_VALUE

This allows implementing GIST ordered scans for btree_gist datatypes.

This in turn makes using GIST with partitioning feasible (I have described issues with such usage in my previous e-mails - see below).

Did you take into account that GiST's internal distance function uses
floating point, and is thus only an approximation for values that
require more than 2^54 significant bits in their distance function?
For example, GiST wouldn't be guaranteed to yield correct ordering of
int8/bigint when you use `my_column <-> UINT64_MAX` because as far as
the floating point math is concerned, 0 is about as far away from
INT64_MAX as (say) 20 and -21.

Hmm… Good point but it means ORDER BY <-> is broken for these types then?
The patch assumes it works correctly and just uses it for ordered scans.

Huh, I didn't know this before, but apparently values are pushed onto
a reorderqueue/pairingheap if the index scan is marked
xs_recheckorderby (i.e. when the tuple order is not exact), which
would be used in this case.

So it seems like this wouldn't be much of an issue for the patch,
apart from the potential issue where this could use the pairingheap
much more than the usual ordered scan operations, which could result
in larger-than-normal memory usage. E.g. float btree ops wouldn't work
effectively at all because every reasonable value is extremely distant
from its max value.

Kind regards,

Matthias van de Meent