Обсуждение: Add red-black tree missing comparison searches
Hello hackers,
Currently the red-black tree implementation only has an equality search. Other extensions might need other comparison searches, like less-or-equal or greater-or-equal. For example OrioleDB defines a greater-or-equal search on its postgres fork:
So I thought this might be valuable to have in core. I've added less-or-equal and greater-or-equal searches functions plus tests in the test_rbtree module. I can add the remaining less/great searches if this is deemed worth it.
Also I refactored the sentinel used in the rbtree.c to use C99 designators.
Thanks in advance for any feedback!
--
Steve Chavez
Engineering at https://supabase.com/
Вложения
Please add this to the commitfest at https://commitfest.postgresql.org/38/ so it doesn't get missed. The commitfest starts imminently so best add it today.
On Thu, 30 Jun 2022 at 12:09, Greg Stark <stark@mit.edu> wrote:
Please add this to the commitfest at
https://commitfest.postgresql.org/38/ so it doesn't get missed. The
commitfest starts imminently so best add it today.
Hi, Steve! Thank you for working on this. On Thu, Jun 30, 2022 at 7:51 PM Steve Chavez <steve@supabase.io> wrote: > Currently the red-black tree implementation only has an equality search. Other extensions might need other comparison searches,like less-or-equal or greater-or-equal. For example OrioleDB defines a greater-or-equal search on its postgres fork: > > https://github.com/orioledb/postgres/blob/4c18ae94c20e3e95c374b9947f1ace7d1d6497a1/src/backend/lib/rbtree.c#L164-L186 > > So I thought this might be valuable to have in core. I've added less-or-equal and greater-or-equal searches functions plustests in the test_rbtree module. I can add the remaining less/great searches if this is deemed worth it. Looks good. But I think we can support strict inequalities too (e.g. less and greater without equals). Could you please make it a bool argument equal_matches? > Also I refactored the sentinel used in the rbtree.c to use C99 designators. Could you please extract this change as a separate patch. ------ Regards, Alexander Korotkov
Hey Alexander,
argument equal_matches?
> But I think we can support strict inequalities too (e.g.
less and greater without equals). Could you please make it a boolargument equal_matches?
Sure, an argument is a good idea to keep the code shorter.
> Could you please extract this change as a separate patch.
Done!
On Thu, 30 Jun 2022 at 14:34, Alexander Korotkov <aekorotkov@gmail.com> wrote:
Hi, Steve!
Thank you for working on this.
On Thu, Jun 30, 2022 at 7:51 PM Steve Chavez <steve@supabase.io> wrote:
> Currently the red-black tree implementation only has an equality search. Other extensions might need other comparison searches, like less-or-equal or greater-or-equal. For example OrioleDB defines a greater-or-equal search on its postgres fork:
>
> https://github.com/orioledb/postgres/blob/4c18ae94c20e3e95c374b9947f1ace7d1d6497a1/src/backend/lib/rbtree.c#L164-L186
>
> So I thought this might be valuable to have in core. I've added less-or-equal and greater-or-equal searches functions plus tests in the test_rbtree module. I can add the remaining less/great searches if this is deemed worth it.
Looks good. But I think we can support strict inequalities too (e.g.
less and greater without equals). Could you please make it a bool
argument equal_matches?
> Also I refactored the sentinel used in the rbtree.c to use C99 designators.
Could you please extract this change as a separate patch.
------
Regards,
Alexander Korotkov
Вложения
Hi, Steve! On Sat, Jul 2, 2022 at 10:38 PM Steve Chavez <steve@supabase.io> wrote: > > But I think we can support strict inequalities too (e.g. > less and greater without equals). Could you please make it a bool > argument equal_matches? > > Sure, an argument is a good idea to keep the code shorter. > > > Could you please extract this change as a separate patch. > > Done! Thank you! I did some improvements to the test suite, run pgindent and wrote commit messages. I think this is quite straightforward and low-risk patch. I'm going to push it if no objections. ------ Regards, Alexander Korotkov
Вложения
---------- Forwarded message ---------
From: Steve Chavez <steve@supabase.io>
Date: Wed, 6 Jul 2022 at 18:14
Subject: Re: Add red-black tree missing comparison searches
To: Alexander Korotkov <aekorotkov@gmail.com>
From: Steve Chavez <steve@supabase.io>
Date: Wed, 6 Jul 2022 at 18:14
Subject: Re: Add red-black tree missing comparison searches
To: Alexander Korotkov <aekorotkov@gmail.com>
Thanks Alexander!
wrt to the new patch. I think the following comment is misleading since keyDeleted can be true or false:
+ /* switch equal_match to false so we only find greater matches now */
+ node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode,
+ keyDeleted);
+ /* switch equal_match to false so we only find greater matches now */
+ node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode,
+ keyDeleted);
Maybe it should be the same used for searching lesser keys:
+ /*
+ * Find the next key. If the current key is deleted, we can pass
+ * equal_match == true and still find the next one.
+ */
+ * Find the next key. If the current key is deleted, we can pass
+ * equal_match == true and still find the next one.
+ */
On Wed, 6 Jul 2022 at 13:53, Alexander Korotkov <aekorotkov@gmail.com> wrote:
Hi, Steve!
On Sat, Jul 2, 2022 at 10:38 PM Steve Chavez <steve@supabase.io> wrote:
> > But I think we can support strict inequalities too (e.g.
> less and greater without equals). Could you please make it a bool
> argument equal_matches?
>
> Sure, an argument is a good idea to keep the code shorter.
>
> > Could you please extract this change as a separate patch.
>
> Done!
Thank you!
I did some improvements to the test suite, run pgindent and wrote
commit messages.
I think this is quite straightforward and low-risk patch. I'm going
to push it if no objections.
------
Regards,
Alexander Korotkov
On Thu, Jul 7, 2022 at 2:16 AM Steve Chavez <steve@supabase.io> wrote: > Thanks Alexander! > > wrt to the new patch. I think the following comment is misleading since keyDeleted can be true or false: > > + /* switch equal_match to false so we only find greater matches now */ > + node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode, > + keyDeleted); > > Maybe it should be the same used for searching lesser keys: > > + /* > + * Find the next key. If the current key is deleted, we can pass > + * equal_match == true and still find the next one. > + */ Thank you for catching this. The revised version of patch is attached! ------ Regards, Alexander Korotkov
Вложения
On Thu, Jul 7, 2022 at 1:43 PM Alexander Korotkov <aekorotkov@gmail.com> wrote: > On Thu, Jul 7, 2022 at 2:16 AM Steve Chavez <steve@supabase.io> wrote: > > Thanks Alexander! > > > > wrt to the new patch. I think the following comment is misleading since keyDeleted can be true or false: > > > > + /* switch equal_match to false so we only find greater matches now */ > > + node = (IntRBTreeNode *) rbt_find_great(tree, (RBTNode *) &searchNode, > > + keyDeleted); > > > > Maybe it should be the same used for searching lesser keys: > > > > + /* > > + * Find the next key. If the current key is deleted, we can pass > > + * equal_match == true and still find the next one. > > + */ > > Thank you for catching this. > The revised version of patch is attached! Pushed! ------ Regards, Alexander Korotkov