Thread

1. Bitmap Indexes: request for feedback

   Gianni Ciolli <gianni.ciolli@2ndquadrant.it> — 2008-10-21T14:57:59Z

   Hi everybody,
   
   me and Gabriele Bartolini have been working on Bitmap Indexes (BMI) in
   the last weeks, with advice and guidance from Simon Riggs. We feel
   that we are about to approach the point where it is appropriate to ask
   for feedback from this list.
   
   Thank you,
   Dr. Gianni Ciolli - 2ndQuadrant Italia
   PostgreSQL Training, Services and Support
   gianni.ciolli@2ndquadrant.it | www.2ndquadrant.it
   
   ---8<------8<------8<------8<------8<------8<------8<------8<------8<---
   
   First of all, let us describe what we have done so far, what we found
   and how we think to proceed now.
   
   == 1. Bringing the patch up to date ==
   
   We started from Gavin Sherry's patch dating May 2007
   
     http://archives.postgresql.org/pgsql-patches/2007-05/msg00013.php
   
   As far as we could see, there has been no further activity on this
   subject.
   
   First, we brought the patch up to date. The latest version of the
   patch was anterior to the new Index Access Method Interface
   
     http://developer.postgresql.org/pgdocs/postgres/indexam.html
   
   so we adapted the patch to that interface.
   
   Then we added a few BMI page inspection functions to the pageinspect
   contrib module, and we used them to examine the code. In addition to
   finding and fixing a minor bug, we diagnosed an effect of HOT tuples
   on the BMI patch, described below in greater detail. This also helped
   us to produce extended descriptive documentation of how these indexes
   work, and suggested us how to produce some more tests to verify that
   (a newer version of) the BMI patch works; we are going to add some
   regression tests especially targeted to HOT tuples.
   
   After message 
   
     http://archives.postgresql.org/pgsql-hackers/2008-10/msg00855.php
   
   maybe it is appropriate to mention that backwards scan would not be
   supported at all by BMI indexes.
   
   == 2. The effect of HOT tuples on BMI creation ==
   
   The latest BMI patch mentioned above was also prior to the
   introduction of HOT tuples.
   
   Some parts of that patch rely on the assumption that
   IndexBuildHeapScan scans tuples in increasing TID order. It is easy to
   verify that this property is no longer valid after the introduction of
   HOT tuples; however, a similar but weaker property still holds (the
   scan is always done in non-decreasing block order).
   
   This breaks some low-level bitmap vector build routines, which have to
   be rewritten from scratch because they expect TIDs to came in
   increasing order; but it does not harm block-level locking used in
   that patch.
   
   == 3. What we would do after  ==
   
   We understand that BMI development was suspended because of lack of
   time from the last developer, during the improvement of the VACUUM
   phase. The main obstacle was that the physical size of a compressed
   bitmap vector can either grow or shrink, possibly creating new BMV
   pages, which can mean bad performance.
   
   The current VACUUM algorithm is unfinished; we are going to examine
   it, looking for some improvements, and to measure the current status
   with some ad-hoc benchmarks.
   
   == 4. Timeline ==
   
   Up to now, we spent many days to isolate, describe and partially fix
   the incompatibilies described above; now we feel that points 1. and
   2. can be cleared in a couple of days, bringing the patch up to date
   with current HEAD.
   
   As for the remaining part, we expect to finish the patch before the
   deadline for the latest CommitFest.
   
   We will re-post the patch as soon as the HOT tuples will be working;
   then we will post a new version the patch when also VACUUM will be
   done.
   
   Does anybody have any comments and/or additional requests?
   
   

2. Re: Bitmap Indexes: request for feedback

   Josh Berkus <josh@agliodbs.com> — 2008-10-21T21:26:44Z

   Gianni,
   
   > me and Gabriele Bartolini have been working on Bitmap Indexes (BMI) in
   > the last weeks, with advice and guidance from Simon Riggs. We feel
   > that we are about to approach the point where it is appropriate to ask
   > for feedback from this list.
   
   The other major issue with the Bitmap index patch as it stood in 2007 was 
   that performance just wasn't that much faster than a btree, except for 
   specific corner cases.  Otherwise, someone else would have been interested 
   enough to pick it up and finish it.
   
   So performance testing of the patch is absolutely essential.
   
   -- 
   --Josh
   
   Josh Berkus
   PostgreSQL
   San Francisco
   
   

3. Re: Bitmap Indexes: request for feedback

   Gregory Stark <stark@enterprisedb.com> — 2008-10-21T23:00:08Z

   Josh Berkus <josh@agliodbs.com> writes:
   
   > Gianni,
   >
   >> me and Gabriele Bartolini have been working on Bitmap Indexes (BMI) in
   >> the last weeks, with advice and guidance from Simon Riggs. We feel
   >> that we are about to approach the point where it is appropriate to ask
   >> for feedback from this list.
   >
   > The other major issue with the Bitmap index patch as it stood in 2007 was 
   > that performance just wasn't that much faster than a btree, except for 
   > specific corner cases.  Otherwise, someone else would have been interested 
   > enough to pick it up and finish it.
   
   Actually as I recall the immediate issue was that the patch was more complex
   than necessary. In particular it reimplemented parts of the executor
   internally rather than figuring out what api was necessary to integrate it
   fully into the executor.
   
   When we last left our heros they were proposing ways to refactor the index api
   to allow index ams to stream results to the executor in bitmap form. That
   would allow a scan of a bitmap index to return bitmap elements wholesale and
   have the executor apply bitmap operations to them along with the elements
   returned by a btree bitmap scan or other index ams.
   
   -- 
     Gregory Stark
     EnterpriseDB          http://www.enterprisedb.com
     Ask me about EnterpriseDB's On-Demand Production Tuning
   
   

4. Re: Bitmap Indexes: request for feedback

   Tom Lane <tgl@sss.pgh.pa.us> — 2008-10-22T02:48:12Z

   Gregory Stark <stark@enterprisedb.com> writes:
   > Josh Berkus <josh@agliodbs.com> writes:
   >> The other major issue with the Bitmap index patch as it stood in 2007 was 
   >> that performance just wasn't that much faster than a btree, except for 
   >> specific corner cases.  Otherwise, someone else would have been interested 
   >> enough to pick it up and finish it.
   
   > Actually as I recall the immediate issue was that the patch was more complex
   > than necessary.
   
   Well, yeah, but if the performance isn't there then who's going to spend
   time refactoring the code?
   
   			regards, tom lane
   
   

5. Re: Bitmap Indexes: request for feedback

   Simon Riggs <simon@2ndquadrant.com> — 2008-10-22T07:32:45Z

   On Wed, 2008-10-22 at 00:00 +0100, Gregory Stark wrote:
   
   > Actually as I recall the immediate issue was that the patch was more complex
   > than necessary. In particular it reimplemented parts of the executor
   > internally rather than figuring out what api was necessary to integrate it
   > fully into the executor.
   > 
   > When we last left our heros they were proposing ways to refactor the index api
   > to allow index ams to stream results to the executor in bitmap form. That
   > would allow a scan of a bitmap index to return bitmap elements wholesale and
   > have the executor apply bitmap operations to them along with the elements
   > returned by a btree bitmap scan or other index ams.
   
   The indexAM API has now been changed, so that is a simple matter now.
   
   amgetbitmap() was committed on 10 April 2008.
   
   -- 
    Simon Riggs           www.2ndQuadrant.com
    PostgreSQL Training, Services and Support
   
   
   

6. Re: Bitmap Indexes: request for feedback

   Simon Riggs <simon@2ndquadrant.com> — 2008-10-22T07:36:42Z

   On Tue, 2008-10-21 at 14:26 -0700, Josh Berkus wrote:
   > Gianni,
   > 
   > > me and Gabriele Bartolini have been working on Bitmap Indexes (BMI) in
   > > the last weeks, with advice and guidance from Simon Riggs. We feel
   > > that we are about to approach the point where it is appropriate to ask
   > > for feedback from this list.
   > 
   > The other major issue with the Bitmap index patch as it stood in 2007 was 
   > that performance just wasn't that much faster than a btree, except for 
   > specific corner cases.  Otherwise, someone else would have been interested 
   > enough to pick it up and finish it.
   
   That seems a strange comment - are you thinking of hash indexes? Do you
   have references to these poor performance tests?
   
   BMIs will be a win for indexes with high numbers of duplicate keys -
   where btrees don't operate very well. OTOH I expect btrees to continue
   to be very useful in places where many keys are unique or nearly unique.
   
   Index creation was much faster and produced much smaller indexes than
   btrees, when used in the right situations. Better use of memory and
   reduction of I/O alone are important factors. Significantly smaller
   indexes also allow more indexes to be built on a table, leading to
   overall gains in performance.
   
   -- 
    Simon Riggs           www.2ndQuadrant.com
    PostgreSQL Training, Services and Support
   
   
   

7. Re: Bitmap Indexes: request for feedback

   Mark Kirkwood <markir@paradise.net.nz> — 2008-10-22T09:50:44Z

   Josh Berkus wrote:
   >
   >
   > The other major issue with the Bitmap index patch as it stood in 2007 was 
   > that performance just wasn't that much faster than a btree, except for 
   > specific corner cases.  Otherwise, someone else would have been interested 
   > enough to pick it up and finish it.
   >
   > So performance testing of the patch is absolutely essential.
   >
   >   
   As Simon mentioned - index creation time and size was certainly improved 
   considerably.
   
   There were certainly cases when row retrieval performance was not 
   improved much (as compared to using a comparable btree index) - my 
   analysis was that these were typically when heap fetch time dominated 
   index scan time i.e it didn't matter how good your index access was, you 
   were mired in heap seeks. ISTM that this situation will change 
   dramatically when index only access (via dead space map? or similar) 
   arrives.
   
   Note that even if only for the on disk size savings, these are worth 
   having for data warehousing situations.
   
   regards
   
   Mark
   
   

8. Re: Bitmap Indexes: request for feedback

   Tom Lane <tgl@sss.pgh.pa.us> — 2008-10-22T12:31:43Z

   Simon Riggs <simon@2ndQuadrant.com> writes:
   > On Wed, 2008-10-22 at 00:00 +0100, Gregory Stark wrote:
   >> When we last left our heros they were proposing ways to refactor the index api
   >> to allow index ams to stream results to the executor in bitmap form.
   
   > The indexAM API has now been changed, so that is a simple matter now.
   
   No, that was merely one component of the problem.  The APIs for
   tidbitmaps need revision too.  You can't "stream" a bitmap yet.
   
   			regards, tom lane
   
   

9. Re: Bitmap Indexes: request for feedback

   Simon Riggs <simon@2ndquadrant.com> — 2008-10-22T12:43:52Z

   On Wed, 2008-10-22 at 08:31 -0400, Tom Lane wrote:
   > Simon Riggs <simon@2ndQuadrant.com> writes:
   > > On Wed, 2008-10-22 at 00:00 +0100, Gregory Stark wrote:
   > >> When we last left our heros they were proposing ways to refactor the index api
   > >> to allow index ams to stream results to the executor in bitmap form.
   > 
   > > The indexAM API has now been changed, so that is a simple matter now.
   > 
   > No, that was merely one component of the problem.  The APIs for
   > tidbitmaps need revision too.  You can't "stream" a bitmap yet.
   
   Please explain further.
   
   Which calls? Why do we need to stream them?
   
   -- 
    Simon Riggs           www.2ndQuadrant.com
    PostgreSQL Training, Services and Support
   
   
   

10. Re: Bitmap Indexes: request for feedback

    Tom Lane <tgl@sss.pgh.pa.us> — 2008-10-22T13:13:25Z

    Simon Riggs <simon@2ndQuadrant.com> writes:
    > On Wed, 2008-10-22 at 08:31 -0400, Tom Lane wrote:
    >> No, that was merely one component of the problem.  The APIs for
    >> tidbitmaps need revision too.  You can't "stream" a bitmap yet.
    
    > Please explain further.
    > Which calls? Why do we need to stream them?
    
    Well, I guess we don't absolutely *have* to --- we could insist that a
    bitmap scan on a bitmap index proceed by first sucking the whole bitmap
    into memory, the same as is done for other index types.  It seems pretty
    silly though, especially for the expected use-case of low cardinality;
    the bitmaps would get big.
    
    The idea that was being kicked around was to make it possible for
    TIDBitmap to be an alias representing an indexscan in progress.  So
    you'd pull an index page or so's worth of TIDs from the index, hand
    them back to nodeBitmapHeapscan.c to read those tuples, repeat till
    done.  With judicious use of a few "method" function pointers,
    nodeBitmapHeapscan wouldn't need to know whether it was doing this or
    using an in-memory bitmap.  ANDing and ORing of bitmaps could be made
    to work streamably too.
    
    As Greg said, the major complaint against the original patch was that
    they'd made it do this (interleave the heap and index access) by hack
    slash and burn instead of extending the existing APIs appropriately.
    
    			regards, tom lane
    
    

11. Re: Bitmap Indexes: request for feedback

    Simon Riggs <simon@2ndquadrant.com> — 2008-10-22T13:41:12Z

    On Wed, 2008-10-22 at 09:13 -0400, Tom Lane wrote:
    > Simon Riggs <simon@2ndQuadrant.com> writes:
    > > On Wed, 2008-10-22 at 08:31 -0400, Tom Lane wrote:
    > >> No, that was merely one component of the problem.  The APIs for
    > >> tidbitmaps need revision too.  You can't "stream" a bitmap yet.
    > 
    > > Please explain further.
    > > Which calls? Why do we need to stream them?
    > 
    > Well, I guess we don't absolutely *have* to --- we could insist that a
    > bitmap scan on a bitmap index proceed by first sucking the whole bitmap
    > into memory, the same as is done for other index types.  It seems pretty
    > silly though, especially for the expected use-case of low cardinality;
    > the bitmaps would get big.
    
    OK, now I understand.
    
    Realistically, introducing a new index type is non-trivial and getting
    the index working at all will be quite some feat, considering the
    requirements of HOT and Vacuum.
    
    I agree we could do the stream bitmap as well, but I'd suggest we should
    save that until the rest of the patch has been checked out. GIN wasn't
    all written in one release, and I think it likely that it may be another
    couple of releases before we do all the tuning on BMIs.
    
    Please let's not set the bar too high for the first implementation,
    especially before we have test results that indicate where our tuning
    should be focused.
    
    > The idea that was being kicked around was to make it possible for
    > TIDBitmap to be an alias representing an indexscan in progress.  So
    > you'd pull an index page or so's worth of TIDs from the index, hand
    > them back to nodeBitmapHeapscan.c to read those tuples, repeat till
    > done.  With judicious use of a few "method" function pointers,
    > nodeBitmapHeapscan wouldn't need to know whether it was doing this or
    > using an in-memory bitmap.  ANDing and ORing of bitmaps could be made
    > to work streamably too.
    
    Yes, completely agree that would be the better way.
    
    > As Greg said, the major complaint against the original patch was that
    > they'd made it do this (interleave the heap and index access) by hack
    > slash and burn instead of extending the existing APIs appropriately.
    
    Yeh, I never liked that original approach.
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

12. Re: Bitmap Indexes: request for feedback

    Tom Lane <tgl@sss.pgh.pa.us> — 2008-10-22T14:00:23Z

    Simon Riggs <simon@2ndQuadrant.com> writes:
    > I agree we could do the stream bitmap as well, but I'd suggest we should
    > save that until the rest of the patch has been checked out.
    
    Well, that would be a reasonable implementation path, but it's got
    nothing to do with the patch as presented.  The concern was getting
    rid of some massive and ugly hacks in the executor ...
    
    			regards, tom lane
    
    

13. Re: Bitmap Indexes: request for feedback

    Simon Riggs <simon@2ndquadrant.com> — 2008-10-22T14:11:07Z

    On Wed, 2008-10-22 at 10:00 -0400, Tom Lane wrote:
    > Simon Riggs <simon@2ndQuadrant.com> writes:
    > > I agree we could do the stream bitmap as well, but I'd suggest we should
    > > save that until the rest of the patch has been checked out.
    > 
    > Well, that would be a reasonable implementation path, but it's got
    > nothing to do with the patch as presented.  The concern was getting
    > rid of some massive and ugly hacks in the executor ...
    
    Agreed, no ugly hacks in executor allowed.
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

14. Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Gianni Ciolli <gianni.ciolli@2ndquadrant.it> — 2008-11-01T00:01:54Z

    Hi to everybody,
    
    following the useful feedback that we received from this list, we
    would like to submit the patch for Bitmap Indexes for the november
    CommitFest (joint work of me with Gabriele Bartolini, starting from
    Gavin Sherry's patch).
    
    There are two open issues (a bug that we are catching and something
    missing in the catalog), but we think that it is worth to submit the
    patch, for two reasons: because we are confident to fix the open
    issues soon, and moreover because bitmap index seem to have their
    non-trivial use cases (index creation is significantly faster than in
    other types, and they occupy far less disk space, while queries are
    only slightly faster).
    
    What we have done:
    
     * We refactored Gavin Sherry's patch
       http://archives.postgresql.org/pgsql-patches/2007-05/msg00013.php
       using the new access method interface; in particular, we eliminate
       a large part of the code, which has been obsoleted by the new
       access method API.
    
       Now the interaction of the patch with the existing code is
       significantly smaller, and essentially limited to the catalog
       entries and the access method API.
    
     * We fixed some wrong behaviours due to the fact that the patch
       relies on some assumptions that are no longer true because of the
       evolution of PostgreSQL (HOT tuples break the assumption that
       during index scan tuples are scanned in TID increasing order).
    
     * We added a chapter to the manual, plus some references to bitmap
       index in the remaining test;
    
     * In a separate archive we enclose some performance tests (time and
       disk size), which show that bitmap index behave slightly better
       than btree in terms of speed, especially in certain cases specific
       of the index type (low-cardinality); the main advantage (according
       to some feedback that we received from this list) is that bitmap
       indexes are significantly smaller than any other type.
    
    Current issues:
    
     * Our workaround for HOT tuples has still one bug; we are currently
       working on it and we expect to fix it soon. This bug can be
       reproduced by looking at the "rows" column of the performance test.
    
     * Two regression tests are failing (oidjoins and opr_sanity), due to
       incomplete catalog entries. We expect to fix it very soon.
    
    Now I am going to add the patch to the wiki page.
    
    Best regards,
    Dr. Gianni Ciolli - 2ndQuadrant Italia
    PostgreSQL Training, Services and Support
    gianni.ciolli@2ndquadrant.it | www.2ndquadrant.it
    

15. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Gregory Stark <stark@enterprisedb.com> — 2008-11-03T22:37:24Z

    On 2008-10-31, Gianni Ciolli <gianni.ciolli@2ndquadrant.it> wrote:
    
    >  following the useful feedback that we received from this list, we
    >  would like to submit the patch for Bitmap Indexes for the november
    >  CommitFest (joint work of me with Gabriele Bartolini, starting from
    >  Gavin Sherry's patch).
    
    I skimmed through this on the plane -- I say "skimmed" because it had
    to be pretty quick before the battery ran out :(
    
    I have some first reactions but I admit these are pretty trivial
    detail points. I'm still trying to get a good feel for the overall
    structure which I fear is where any substantial feedback would come
    from.
    
    Firstly, there are a lot of pieces of #ifdef NOTUSED or #if 0 code
    which seem to be remnants of Gavin's code which are no longer
    relevant. That's pretty trivial for a committer to strip out but if
    you cut another patch it would be appreciated if you removed all that
    crud.
    
    Secondly the locking seems to be a bit overoptimistic. I'm pretty sure
    you have to take an exclusive lock on an index page any time you make
    any data modifications in index pages -- even if you're just setting a
    bit and not moving any data around. If two processes set two bits in
    the same word one can get lost in the race condition.
    
    There are a lot of comments in the code which imply that vacuuming is
    not implemented but in fact from what I can see it is -- sort of. It
    does rewrite the bitmap in bmbulkdelete but it doesn't have to rebuild
    the index from scratch.  Are the comments out of date or am i
    misunderstanding them or the code? How complete is the vacuum
    implementation?
    
    -- 
    greg
    
    

16. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Simon Riggs <simon@2ndquadrant.com> — 2008-11-03T23:28:35Z

    On Mon, 2008-11-03 at 17:37 -0500, Greg Stark wrote:
    
    > Secondly the locking seems to be a bit overoptimistic. I'm pretty sure
    > you have to take an exclusive lock on an index page any time you make
    > any data modifications in index pages -- even if you're just setting a
    > bit and not moving any data around. If two processes set two bits in
    > the same word one can get lost in the race condition.
    
    I looked at that aspect of the patch specifically a few weeks back while
    checking for possible issues with Hot Standby. IIRC the patch is fairly
    careful with locking and uses Exclusive locks extensively throughout. I
    looked at both the theory and the implementation. Unless Gianni changed
    something in that regard recently, I don't understand that comment at
    all. Probably need to provide specific examples of your concerns.
    
    > There are a lot of comments in the code which imply that vacuuming is
    > not implemented but in fact from what I can see it is -- sort of. It
    > does rewrite the bitmap in bmbulkdelete but it doesn't have to rebuild
    > the index from scratch.  Are the comments out of date or am i
    > misunderstanding them or the code? How complete is the vacuum
    > implementation?
    
    As I understood it, complete. I think the objective was minimal change
    away from Gavin's original. But it sounds like you found some out of
    date comments. 
    
    Extensive docs have been added as a README, mainly because it was pretty
    hard to understand without them.
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

17. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Simon Riggs <simon@2ndquadrant.com> — 2008-11-03T23:39:45Z

    On Mon, 2008-11-03 at 23:28 +0000, Simon Riggs wrote:
    > On Mon, 2008-11-03 at 17:37 -0500, Greg Stark wrote:
    > 
    > > Secondly the locking seems to be a bit overoptimistic. I'm pretty sure
    > > you have to take an exclusive lock on an index page any time you make
    > > any data modifications in index pages -- even if you're just setting a
    > > bit and not moving any data around. If two processes set two bits in
    > > the same word one can get lost in the race condition.
    > 
    > I looked at that aspect of the patch specifically a few weeks back while
    > checking for possible issues with Hot Standby. IIRC the patch is fairly
    > careful with locking and uses Exclusive locks extensively throughout. I
    > looked at both the theory and the implementation. Unless Gianni changed
    > something in that regard recently, I don't understand that comment at
    > all. Probably need to provide specific examples of your concerns.
    
    Just went through patch and checked all occurrences of BM_READ. I don't
    see any out of place: there's only 11 calls that use it. Note that there
    are multiple data structures in the index, just like GIN, so you need to
    look at which structure is being locked for each operation.
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

18. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Vladimir Sitnikov <sitnikov.vladimir@gmail.com> — 2008-11-03T23:53:28Z

    > I looked at that aspect of the patch specifically a few weeks back while
    > checking for possible issues with Hot Standby. IIRC the patch is fairly
    > careful with locking and uses Exclusive locks extensively throughout. I
    > looked at both the theory and the implementation. Unless Gianni changed
    > something in that regard recently, I don't understand that comment at
    > all. Probably need to provide specific examples of your concerns.
    >
    The major thing there is to get the modifications right. There is no much
    sense in reviewing "wrong" code against "locking issues".
    
    I wish to focus on the performance aspect of the patch, however, it turned
    out there are major issues with functionality: the index stores wrong tids
    inside :(
    I really would love to fix that issue and have a chance to validate the
    performance. Unfortunately, I have spent more than a day with almost void
    success.
    
    I have two testcases for which the index fails to get the correct result:
    
    Testcase 1 (I guess there is a conflict between _bitmap_formitem and
    mergewords):
    
    Basically I create a table with all the rows equal to 1 besides 19-th, which
    is 0.
    
    create table t1 as select case when i=19 then 0 else 1 end as i from
    generate_series(1,20) as s(i)
    create index t1ix on t1 using bitmap (i) where i = 0;
    set enable_seqscan=off;
    select ctid,i From t1 where i=0; -- no rows selected.  Debug shows index
    suggests ctid==(0,35) instead of (0,19).  35==16+16+3.
    
    Testcase 2
    
    create table t2 as select i, 0 j from generate_series(1,1000) as s(i);
    update t2 set j=1 where i in (5, 230)
    create index t2ix on t2 using bitmap(j) where j=1;
    
    set enable_seqscan=off;
    select ctid, i, j from t2 where j=1; -- no rows selected. Debug shows index
    suggests ctids==(0,97) and (0,98) instead of (4,97) and (4,98) -- it loses
    page number somewhere on the way.
    
    Both testcases reveal defects in index creation.
    
    Regards,
    Vladimir Sitnikov
    

19. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Simon Riggs <simon@2ndquadrant.com> — 2008-11-04T00:12:29Z

    On Mon, 2008-11-03 at 16:53 -0700, Vladimir Sitnikov wrote:
    
    > The major thing there is to get the modifications right. There is no
    > much sense in reviewing "wrong" code against "locking issues".
    
    I didn't say there were no other bugs, nor would I know, only that I had
    reviewed the locking issues specifically because of the possible effects
    on Hot Standby. I haven't seen any problems that would be caused by
    locking. In general, all aspects of code needs to be checked, especially
    if there are bugs, else how would you resolve them?
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

20. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Vladimir Sitnikov <sitnikov.vladimir@gmail.com> — 2008-11-04T00:18:47Z

    BTW:  is there a framework to test recovery related features?
    The only idea I could take from the top of my head is to comment out all the
    page writes and leave only WAL logging. Then crash database at random and
    verify if the index still performs as expected.
    
    
    Regards,
    Vladimir Sitnikov
    

21. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Simon Riggs <simon@2ndquadrant.com> — 2008-11-04T07:23:31Z

    On Mon, 2008-11-03 at 23:28 +0000, Simon Riggs wrote:
    > On Mon, 2008-11-03 at 17:37 -0500, Greg Stark wrote:
    > 
    > > There are a lot of comments in the code which imply that vacuuming is
    > > not implemented but in fact from what I can see it is -- sort of. It
    > > does rewrite the bitmap in bmbulkdelete but it doesn't have to rebuild
    > > the index from scratch.  Are the comments out of date or am i
    > > misunderstanding them or the code? How complete is the vacuum
    > > implementation?
    > 
    > As I understood it, complete. 
    
    Looking at the code, it looks like my understanding was complete-ly
    wrong and your comments seem accurate.
    
    -- 
     Simon Riggs           www.2ndQuadrant.com
     PostgreSQL Training, Services and Support
    
    
    

22. Re: Bitmap Indexes patch

    Gregory Stark <stark@enterprisedb.com> — 2008-11-04T11:17:15Z

    Simon Riggs <simon@2ndQuadrant.com> writes:
    
    > On Mon, 2008-11-03 at 23:28 +0000, Simon Riggs wrote:
    >> On Mon, 2008-11-03 at 17:37 -0500, Greg Stark wrote:
    >> 
    >> > There are a lot of comments in the code which imply that vacuuming is
    >> > not implemented but in fact from what I can see it is -- sort of. It
    >> > does rewrite the bitmap in bmbulkdelete but it doesn't have to rebuild
    >> > the index from scratch.  Are the comments out of date or am i
    >> > misunderstanding them or the code? How complete is the vacuum
    >> > implementation?
    >> 
    >> As I understood it, complete. 
    >
    > Looking at the code, it looks like my understanding was complete-ly
    > wrong and your comments seem accurate.
    
    What I would appreciate is a README explaining how vacuum and vacuum full
    work.
    
    -- 
      Gregory Stark
      EnterpriseDB          http://www.enterprisedb.com
      Ask me about EnterpriseDB's 24x7 Postgres support!
    
    

23. Re: Bitmap Indexes patch (was Re: Bitmap Indexes: request for feedback)

    Gianni Ciolli <gianni.ciolli@2ndquadrant.it> — 2008-11-04T14:00:59Z

    On Mon, Nov 03, 2008 at 04:53:28PM -0700, Vladimir Sitnikov wrote:
    > I wish to focus on the performance aspect of the patch, however, it turned
    > out there are major issues with functionality: the index stores wrong tids
    > inside :(
    > I really would love to fix that issue and have a chance to validate the
    > performance. Unfortunately, I have spent more than a day with almost void
    > success.
    
    This can be helpful for us to explain one of the two open issues that
    we mentioned at submission time (meanwhile we have just fixed the
    other one):
    On Sat, Nov 01, 2008 at 01:01:54AM +0100, Gianni Ciolli wrote:
    >  * Our workaround for HOT tuples has still one bug; we are currently
    >    working on it and we expect to fix it soon. This bug can be
    >    reproduced by looking at the "rows" column of the performance test.
    
    As for the other problem:
    
    On Mon, Nov 03, 2008 at 05:37:24PM -0500, Greg Stark wrote:
    > There are a lot of comments in the code which imply that vacuuming is
    > not implemented but in fact from what I can see it is -- sort of. It
    > does rewrite the bitmap in bmbulkdelete but it doesn't have to rebuild
    > the index from scratch.  Are the comments out of date or am i
    > misunderstanding them or the code? How complete is the vacuum
    > implementation?
    
    This morning I looked at that part of the code, and I found that
    indeed the vacuum implementation has a lack that we didn't
    notice. After refactoring we had made some tests which suggested that
    vacuum was working, but now I realize that in the hurry we missed
    something.
    
    Now, the point is that this VACUUM problem might need more work than
    we expected, and that it might just be too much work for a review
    phase; so, despite of the interest that showed up regarding this
    feature, I will understand if the decision will be to withdraw the
    patch from this Commitfest and postpone it for the next development
    phase.
    
    Thank you to everyone for your remarks,
    
    Dr. Gianni Ciolli - 2ndQuadrant Italia
    PostgreSQL Training, Services and Support
    gianni.ciolli@2ndquadrant.it | www.2ndquadrant.it