Re: Sparse bit set data structure

2019-04-08 Thread Heikki Linnakangas
On 09/04/2019 03:45, Alvaro Herrera wrote: On 2019-Apr-08, Bruce Momjian wrote: Uh, should this be applied? Yes, it's a pretty obvious typo methinks. Pushed, thanks, and sorry for the delay. - Heikki

Re: Sparse bit set data structure

2019-04-08 Thread Alvaro Herrera
On 2019-Apr-08, Bruce Momjian wrote: > Uh, should this be applied? Yes, it's a pretty obvious typo methinks. -- Álvaro Herrerahttps://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Re: Sparse bit set data structure

2019-04-08 Thread Bruce Momjian
Uh, should this be applied? --- On Thu, Mar 28, 2019 at 03:46:03PM +0100, Adrien NAYRAT wrote: > Hello, > > According to the draw and simple8b_mode struct comment, it seems there is a > typo: > > > * 20-bit integer

Re: Sparse bit set data structure

2019-03-28 Thread Adrien NAYRAT
Hello, According to the draw and simple8b_mode struct comment, it seems there is a typo: * 20-bit integer 20-bit integer 20-bit integer * 1101 00010010 00110010 00010100 * ^ * selector * * The selector 1101 is 13 in decimal. From the

Re: Sparse bit set data structure

2019-03-22 Thread Heikki Linnakangas
Committed, thanks for the review! I made one last-minute change: Instead of allocating a memory context in intset_create(), it is left to the caller. The GiST vacuum code created two integer sets, and it made more sense for it to use the same context for both. Also, the VACUUM tid list patch w

Re: Sparse bit set data structure

2019-03-20 Thread Julien Rouhaud
On Wed, Mar 20, 2019 at 5:20 PM Julien Rouhaud wrote: > > On Wed, Mar 20, 2019 at 2:10 AM Heikki Linnakangas wrote: > > > I'm now pretty satisfied with this. Barring objections, I'll commit this > > in the next few days. Please review, if you have a chance. > > You're defining SIMPLE8B_MAX_VALUE

Re: Sparse bit set data structure

2019-03-20 Thread Julien Rouhaud
On Wed, Mar 20, 2019 at 2:10 AM Heikki Linnakangas wrote: > > On 14/03/2019 17:37, Julien Rouhaud wrote: > > > + if (newitem <= sbs->last_item) > > + elog(ERROR, "cannot insert to sparse bitset out of order"); > > > > Is there any reason to disallow inserting duplicates? AFAICT no

Re: Sparse bit set data structure

2019-03-19 Thread Andrey Borodin
Hi! Great job! > 20 марта 2019 г., в 9:10, Heikki Linnakangas написал(а): > > Please review, if you have a chance. > > - Heikki > <0001-Add-IntegerSet-to-hold-large-sets-of-64-bit-ints-eff.patch> I'm looking into the code and have few questions: 1. I'm not sure it is the best interface for i

Re: Sparse bit set data structure

2019-03-19 Thread Heikki Linnakangas
On 14/03/2019 17:37, Julien Rouhaud wrote: On Wed, Mar 13, 2019 at 8:18 PM Heikki Linnakangas wrote: I started to consider rewriting the data structure into something more like B-tree. Then I remembered that I wrote a data structure pretty much like that last year already! We discussed that on

Re: Sparse bit set data structure

2019-03-14 Thread Julien Rouhaud
On Thu, Mar 14, 2019 at 4:37 PM Julien Rouhaud wrote: > > + if (newitem <= sbs->last_item) > + elog(ERROR, "cannot insert to sparse bitset out of order"); > > Is there any reason to disallow inserting duplicates? AFAICT nothing > prevents that in the current code. If that's inten

Re: Sparse bit set data structure

2019-03-14 Thread Julien Rouhaud
On Wed, Mar 13, 2019 at 8:18 PM Heikki Linnakangas wrote: > > I started to consider rewriting the data structure into something more > like B-tree. Then I remembered that I wrote a data structure pretty much > like that last year already! We discussed that on the "Vacuum: allow > usage of more tha

Re: Sparse bit set data structure

2019-03-14 Thread Heikki Linnakangas
On 14/03/2019 07:15, Andrey Borodin wrote: 14 марта 2019 г., в 0:18, Heikki Linnakangas написал(а): <0001-Add-SparseBitset-to-hold-a-large-set-of-64-bit-ints-.patch><0002-Andrey-Borodin-s-test_blockset-tool-adapted-for-Spar.patch> That is very interesting idea. Basically, B-tree and radix tree

Re: Sparse bit set data structure

2019-03-13 Thread Andrey Borodin
Hi! > 14 марта 2019 г., в 0:18, Heikki Linnakangas написал(а): > <0001-Add-SparseBitset-to-hold-a-large-set-of-64-bit-ints-.patch><0002-Andrey-Borodin-s-test_blockset-tool-adapted-for-Spar.patch> That is very interesting idea. Basically, B-tree and radix tree is a tradeoff between space and tim

Re: Sparse bit set data structure

2019-03-13 Thread Robert Haas
On Wed, Mar 13, 2019 at 3:18 PM Heikki Linnakangas wrote: > I started to consider rewriting the data structure into something more > like B-tree. Then I remembered that I wrote a data structure pretty much > like that last year already! We discussed that on the "Vacuum: allow > usage of more than

Sparse bit set data structure

2019-03-13 Thread Heikki Linnakangas
Hi, I was reviewing Andrey Borodin's patch for GiST VACUUM [1], which includes a new "block set" data structure, to track internal and empty pages while vacuuming a GiST. The blockset data structure was a pretty simple radix tree, that can hold a set of BlockNumbers. The memory usage of the