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

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

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

Re: Sparse bit set data structure

2019-03-15 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

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

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

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

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