An In-memory Bitmap Index Bug
There is a bug in the in-memory bitmap index on the CVS Tip.
Consider this query: select * from bt1 where g=2 and e=20, which will generate the following query plan:
QUERY PLAN
----------------------------------------------------------------------------------------
Bitmap Heap Scan on bt1 (cost=2041.47..19807.47 rows=8451 width=159)
Recheck Cond: ((e = 20) AND (g = 2))
-> BitmapAnd (cost=2041.47..2041.47 rows=8451 width=0)
-> Bitmap Index Scan on bt1_btree_e (cost=0.00..145.91 rows=25404 width=0)
Index Cond: (e = 20)
-> Bitmap Index Scan on bt1_btree_g (cost=0.00..1895.31 rows=332661 width=0)
Index Cond: (g = 2)
(7 rows)
With default work_mem setting (1024), the bitmap generated for (e=20) will not have lossy pages, while the bitmap generated for (g=2) will have lossy pages.
The problem appears when a page in the first bitmap tries to intersect with the second bitmap. The current code didn't set the page in the first bitmap to lossy after the intersection. As a result, incorrect answers are returned.
A patch is attached in this email.
Sincerely,
Jie Zhang
Greenplum
Attachments:
pgsql-bitmapscan-bugfix.patchapplication/octet-stream; name=pgsql-bitmapscan-bugfix.patchDownload
*** ./src/backend/nodes/tidbitmap.c.orig Sat Jul 23 12:38:58 2005
--- ./src/backend/nodes/tidbitmap.c Sat Jul 23 12:41:16 2005
***************
*** 135,141 ****
/* Local function prototypes */
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage);
! static bool tbm_intersect_page(PagetableEntry *apage, const TIDBitmap *b);
static const PagetableEntry *tbm_find_pageentry(const TIDBitmap *tbm,
BlockNumber pageno);
static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
--- 135,141 ----
/* Local function prototypes */
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage);
! static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b);
static const PagetableEntry *tbm_find_pageentry(const TIDBitmap *tbm,
BlockNumber pageno);
static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
***************
*** 382,388 ****
/* Scan through chunks and pages in a, try to match to b */
if (a->status == TBM_ONE_PAGE)
{
! if (tbm_intersect_page(&a->entry1, b))
{
/* Page is now empty, remove it from a */
Assert(!a->entry1.ischunk);
--- 382,388 ----
/* Scan through chunks and pages in a, try to match to b */
if (a->status == TBM_ONE_PAGE)
{
! if (tbm_intersect_page(a, &a->entry1, b))
{
/* Page is now empty, remove it from a */
Assert(!a->entry1.ischunk);
***************
*** 401,407 ****
hash_seq_init(&status, a->pagetable);
while ((apage = (PagetableEntry *) hash_seq_search(&status)) != NULL)
{
! if (tbm_intersect_page(apage, b))
{
/* Page or chunk is now empty, remove it from a */
if (apage->ischunk)
--- 401,407 ----
hash_seq_init(&status, a->pagetable);
while ((apage = (PagetableEntry *) hash_seq_search(&status)) != NULL)
{
! if (tbm_intersect_page(a, apage, b))
{
/* Page or chunk is now empty, remove it from a */
if (apage->ischunk)
***************
*** 424,430 ****
* Returns TRUE if apage is now empty and should be deleted from a
*/
static bool
! tbm_intersect_page(PagetableEntry *apage, const TIDBitmap *b)
{
const PagetableEntry *bpage;
int wordnum;
--- 424,430 ----
* Returns TRUE if apage is now empty and should be deleted from a
*/
static bool
! tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
{
const PagetableEntry *bpage;
int wordnum;
***************
*** 470,475 ****
--- 470,478 ----
}
else if (tbm_page_is_lossy(b, apage->blockno))
{
+ // The apage should be marked as lossy here.
+ tbm_mark_page_lossy (a, apage->blockno) ;
+
/* page is lossy in b, cannot clear any bits */
return false;
}
