On Mon, Aug 15, 2022 at 12:39 PM Masahiko Sawada <sawada.m...@gmail.com> wrote: > > On Fri, Jul 22, 2022 at 10:43 AM Masahiko Sawada <sawada.m...@gmail.com> > wrote: > > > > On Tue, Jul 19, 2022 at 1:30 PM John Naylor > > <john.nay...@enterprisedb.com> wrote: > > > > > > > > > > > > On Tue, Jul 19, 2022 at 9:11 AM Masahiko Sawada <sawada.m...@gmail.com> > > > wrote: > > > > > > > I’d like to keep the first version simple. We can improve it and add > > > > more optimizations later. Using radix tree for vacuum TID storage > > > > would still be a big win comparing to using a flat array, even without > > > > all these optimizations. In terms of single-value leaves method, I'm > > > > also concerned about an extra pointer traversal and extra memory > > > > allocation. It's most flexible but multi-value leaves method is also > > > > flexible enough for many use cases. Using the single-value method > > > > seems to be too much as the first step for me. > > > > > > > > Overall, using 64-bit keys and 64-bit values would be a reasonable > > > > choice for me as the first step . It can cover wider use cases > > > > including vacuum TID use cases. And possibly it can cover use cases by > > > > combining a hash table or using tree of tree, for example. > > > > > > These two aspects would also bring it closer to Andres' prototype, which > > > 1) makes review easier and 2) easier to preserve optimization work > > > already done, so +1 from me. > > > > Thanks. > > > > I've updated the patch. It now implements 64-bit keys, 64-bit values, > > and the multi-value leaves method. I've tried to remove duplicated > > codes but we might find a better way to do that. > > > > With the recent changes related to simd, I'm going to split the patch > into at least two parts: introduce other simd optimized functions used > by the radix tree and the radix tree implementation. Particularly we > need two functions for radix tree: a function like pg_lfind32 but for > 8 bits integers and return the index, and a function that returns the > index of the first element that is >= key.
I recommend looking at https://www.postgresql.org/message-id/CAFBsxsESLUyJ5spfOSyPrOvKUEYYNqsBosue9SV1j8ecgNXSKA%40mail.gmail.com since I did the work just now for searching bytes and returning a bool, buth = and <=. Should be pretty close. Also, i believe if you left this for last as a possible refactoring, it might save some work. In any case, I'll take a look at the latest patch next month. -- John Naylor EDB: http://www.enterprisedb.com
