Horton
Menu

Thread

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Add missing inequality searches to rbtree

  2. Use C99 designator in the rbtree sentinel definition

  1. Add red-black tree missing comparison searches

    Steve Chavez <steve@supabase.io> — 2022-06-30T16:51:22Z

    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:

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.

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/

  2. Re: Add red-black tree missing comparison searches

    Greg Stark <stark@mit.edu> — 2022-06-30T17:09:02Z

    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.

  3. Re: Add red-black tree missing comparison searches

    Steve Chavez <steve@supabase.io> — 2022-06-30T17:15:41Z

    Yes, I've already added it here: https://commitfest.postgresql.org/38/3742/

Thanks!

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.
>

  4. Re: Add red-black tree missing comparison searches

    Alexander Korotkov <aekorotkov@gmail.com> — 2022-06-30T19:34:38Z

    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

  5. Re: Add red-black tree missing comparison searches

    Steve Chavez <steve@supabase.io> — 2022-07-02T19:38:41Z

    Hey Alexander,

> 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!

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
>

  6. Re: Add red-black tree missing comparison searches

    Alexander Korotkov <aekorotkov@gmail.com> — 2022-07-06T18:53:41Z

    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

  7. Fwd: Add red-black tree missing comparison searches

    Steve Chavez <steve@supabase.io> — 2022-07-06T23:15:45Z

    ---------- 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>


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.
+ */

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
>

  8. Re: Add red-black tree missing comparison searches

    Alexander Korotkov <aekorotkov@gmail.com> — 2022-07-07T10:43:55Z

    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

  9. Re: Add red-black tree missing comparison searches

    Alexander Korotkov <aekorotkov@gmail.com> — 2022-07-08T19:01:24Z

    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