Content-Type: multipart/alternative;
 boundary="------------IUGo6AL1IN9VbKBQDRUD7vna"
Message-ID: <b83dd728-3e3f-4efc-8086-b181f27dae86@postgrespro.ru>
Date: Fri, 28 Mar 2025 15:31:31 +0300
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: POC, WIP: OR-clause support for indexes
From: Alena Rybakina <a.rybakina@postgrespro.ru>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: Pavel Borisov <pashkin.elfe@gmail.com>,
 Andrei Lepikhov <lepihov@gmail.com>, Alexander Lakhin <exclusion@gmail.com>,
 pgsql-hackers@lists.postgresql.org
References: <567ED6CA.2040504@sigaev.ru>
 <CAPpHfdv+jtNwofg-p5z86jLYZUTt6tR17Wy00ta0dL=wHQN3ZA@mail.gmail.com>
 <ab8aedce-7a2f-4bb2-bfad-3f1ad91e7336@gmail.com>
 <41ba3d47-2a48-476c-88d4-6ebd889a7af2@gmail.com>
 <CAPpHfdvehQbCpQG9zYr739y2nXQkE=FYsat5VE-pDoB4RDPfBw@mail.gmail.com>
 <e40494ad-cad8-43e6-8372-d0c7b3411ad7@postgrespro.ru>
 <CAPpHfdtPz+J-n6=qAMBqx1p88Ut_cbS9JRbL+EKRpWY04tGcRg@mail.gmail.com>
 <036d64e6-4d47-485c-b047-6664d452b3e8@postgrespro.ru>
 <CAPpHfdumgFuUihGqrmDVR5FnzOLsAah-ZdZ269FgsUrOeNU6rw@mail.gmail.com>
 <1a4f1631-86c1-4185-a520-03b24a389449@postgrespro.ru>
 <CALT9ZEE94JN01za2o872foQErgyLHaX7OnOtoh70QbmXP7=S2A@mail.gmail.com>
 <3ac7c436-81e1-4191-9caf-b0dd70b51511@gmail.com>
 <CALT9ZEEyivV=CDE=CCf8JwT5dU2epBDmbiRyVg8fO7-m6rud7g@mail.gmail.com>
 <72eab2bf-7f94-4f58-84bc-2b80d74b6443@postgrespro.ru>
 <CAPpHfdu71LCrXfwaRot1u_xfx7r92VFvZNRLvQJS79B3XFmBhg@mail.gmail.com>
 <e90cb57e-98bb-41a4-ae6f-156eea91a711@postgrespro.ru>
Content-Language: en-US
In-Reply-To: <e90cb57e-98bb-41a4-ae6f-156eea91a711@postgrespro.ru>
Archived-At: 
 <https://www.postgresql.org/message-id/b83dd728-3e3f-4efc-8086-b181f27dae86%40postgrespro.ru>
Precedence: bulk

This is a multi-part message in MIME format.
--------------IUGo6AL1IN9VbKBQDRUD7vna
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

On 28.03.2025 15:23, Alena Rybakina wrote:
>
> I agree with your code in general, but to be honest, double qsort 
> confused me a little.
>
> I understood why it is needed - we need to sort the elements so that 
> they stand next to each other if they can be assigned to the same 
> group, and then sort the groups themselves according to the set 
> identifier.
>
> I may be missing something, but in the worst case we can get the 
> complexity of qsort O(n^2), right? And I saw the letter where you 
> mentioned this, but it is possible to use mergesort algorithm  instead 
> of qsort, which in the worst case gives n * O(n) complexity?
>
No, sorry, I was wrong here and it is impossible to rewrite it this way. 
I apologize, I agree with your code.

-- 
Regards,
Alena Rybakina
Postgres Professional

--------------IUGo6AL1IN9VbKBQDRUD7vna
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <div class="moz-cite-prefix">On 28.03.2025 15:23, Alena Rybakina
      wrote:<br>
    </div>
    <blockquote type="cite"
      cite="mid:e90cb57e-98bb-41a4-ae6f-156eea91a711@postgrespro.ru">
      <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
      <span style="white-space: pre-wrap">
</span>
      <p>I agree with your code in general, but to be honest, double
        qsort confused me a little. </p>
      <p>I understood why it is needed - we need to sort the elements so
        that they stand next to each other if they can be assigned to
        the same group, and then sort the groups themselves according to
        the set identifier. </p>
      <p>I may be missing something, but in the worst case we can get
        the complexity of qsort O(n^2), right? And I saw the letter
        where you mentioned this, but it is possible to use mergesort
        algorithm  instead of qsort, which in the worst case gives n *
        O(n) complexity?<span style="white-space: pre-wrap">
</span></p>
      <pre class="moz-signature" cols="72">
</pre>
    </blockquote>
    No, sorry, I was wrong here and it is impossible to rewrite it this
    way. I apologize, I agree with your code.<br>
    <pre class="moz-signature" cols="72">-- 
Regards,
Alena Rybakina
Postgres Professional</pre>
  </body>
</html>

--------------IUGo6AL1IN9VbKBQDRUD7vna--