Problem with Bitmap Heap Scan
Simple select give wrong result when it uses the Bitmap Heap Scan path.
postgres=# CREATE OR REPLACE FUNCTION my_exec_im_test_func(i integer)
RETURNS integer AS $$
BEGIN
RETURN i + 1;
END;
$$ LANGUAGE plpgsql;
CREATE FUNCTION
postgres=# set enable_seqscan=off;
SET
postgres=# set enable_indexscan=off;
SET
postgres=# select proname from pg_proc where proname like 'my_pro1';
proname
----------------------
my_exec_im_test_proc
(1 row)
postgres=# explain select proname from pg_proc where proname like 'my_pro1';
QUERY
PLAN
--------------------------------------------------------------------------------
-------------
Bitmap Heap Scan on pg_proc (cost=4.26..8.27 rows=1 width=64)
Recheck Cond: (proname ~~ 'my_pro1'::text)
-> Bitmap Index Scan on pg_proc_proname_args_nsp_index (cost=0.00..4.26
row
s=1 width=0)
Index Cond: ((proname >= 'my'::name) AND (proname < 'mz'::name))
(4 rows)
--
Rushabh Lathia
www.EnterpriseDB.com
Analysis:
========
While debugging bitmap heap scan (BitmapHeapNext function) found that first
we perform the underlying index scan and then iterate over bitmap. Now while
iterating, we execute ExecQual only if tbmres->recheck is true. And for the
query tbmres->recheck is false.
But from the query it seems that we should execute ExecQual as we having
"bitmpaqual" on the BitmapHeap node (Not quite sure). And when I manually
did recheck = ture, query working fine and as expected.
Regards.
Rushabh
www.EnterpriseDB.com
On Wed, Nov 19, 2008 at 4:26 PM, Rushabh Lathia <rushabh.lathia@gmail.com>wrote:
Simple select give wrong result when it uses the Bitmap Heap Scan path.
postgres=# CREATE OR REPLACE FUNCTION my_exec_im_test_func(i integer)
RETURNS integer AS $$
BEGIN
RETURN i + 1;
END;
$$ LANGUAGE plpgsql;
CREATE FUNCTIONpostgres=# set enable_seqscan=off;
SET
postgres=# set enable_indexscan=off;
SET
postgres=# select proname from pg_proc where proname like 'my_pro1';
proname
----------------------
my_exec_im_test_proc
(1 row)postgres=# explain select proname from pg_proc where proname like
'my_pro1';
QUERY
PLAN--------------------------------------------------------------------------------
-------------
Bitmap Heap Scan on pg_proc (cost=4.26..8.27 rows=1 width=64)
Recheck Cond: (proname ~~ 'my_pro1'::text)
-> Bitmap Index Scan on pg_proc_proname_args_nsp_index
(cost=0.00..4.26 row
s=1 width=0)
Index Cond: ((proname >= 'my'::name) AND (proname < 'mz'::name))
(4 rows)--
Rushabh Lathiawww.EnterpriseDB.com
--
Rushabh Lathia
"Rushabh Lathia" <rushabh.lathia@gmail.com> writes:
Simple select give wrong result when it uses the Bitmap Heap Scan path.
It's generally appropriate to mention which PG version you're working
with when you report a bug.
postgres=# explain select proname from pg_proc where proname like 'my_pro1';
QUERY
PLAN
--------------------------------------------------------------------------------
-------------
Bitmap Heap Scan on pg_proc (cost=4.26..8.27 rows=1 width=64)
Recheck Cond: (proname ~~ 'my_pro1'::text)
-> Bitmap Index Scan on pg_proc_proname_args_nsp_index (cost=0.00..4.26
row
s=1 width=0)
Index Cond: ((proname >= 'my'::name) AND (proname < 'mz'::name))
(4 rows)
Hmm, the ~~ condition should get treated as a "filter" not a "recheck".
I suppose I broke this somewhere ...
regards, tom lane
Tom Lane wrote:
"Rushabh Lathia" <rushabh.lathia@gmail.com> writes:
Simple select give wrong result when it uses the Bitmap Heap Scan path.
It's generally appropriate to mention which PG version you're working
with when you report a bug.
I was on 8.4 CVS Head, Next time will sure take care of this.
postgres=# explain select proname from pg_proc where proname like 'my_pro1';
QUERY
PLAN--------------------------------------------------------------------------------
-------------
Bitmap Heap Scan on pg_proc (cost=4.26..8.27 rows=1 width=64)
Recheck Cond: (proname ~~ 'my_pro1'::text)
-> Bitmap Index Scan on pg_proc_proname_args_nsp_index (cost=0.00..4.26
row
s=1 width=0)
Index Cond: ((proname >= 'my'::name) AND (proname < 'mz'::name))
(4 rows)Hmm, the ~~ condition should get treated as a "filter" not a "recheck".
I suppose I broke this somewhere ...
Oh ok.
Show quoted text
regards, tom lane
Tom Lane wrote:
"Rushabh Lathia" <rushabh.lathia@gmail.com> writes:
Simple select give wrong result when it uses the Bitmap Heap Scan path.
It's generally appropriate to mention which PG version you're working
with when you report a bug.postgres=# explain select proname from pg_proc where proname like 'my_pro1';
QUERY
PLAN--------------------------------------------------------------------------------
-------------
Bitmap Heap Scan on pg_proc (cost=4.26..8.27 rows=1 width=64)
Recheck Cond: (proname ~~ 'my_pro1'::text)
-> Bitmap Index Scan on pg_proc_proname_args_nsp_index (cost=0.00..4.26
row
s=1 width=0)
Index Cond: ((proname >= 'my'::name) AND (proname < 'mz'::name))
(4 rows)Hmm, the ~~ condition should get treated as a "filter" not a "recheck".
I suppose I broke this somewhere ...
I started to look at this last night. The culprit seems to be this patch:
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date: Sun Apr 13 19:18:14 2008 +0000Phase 2 of project to make index operator lossiness be determined at runtime
instead of plan time. Extend the amgettuple API so that the index AM returns
a boolean indicating whether the indexquals need to be rechecked, and make
that rechecking happen in nodeIndexscan.c (currently the only place where
it's expected to be needed; other callers of index_getnext are just erroring
out for now). For the moment, GIN and GIST have stub logic that just always
sets the recheck flag to TRUE --- I'm hoping to get Teodor to handle pushing
that control down to the opclass consistent() functions. The planner no
longer pays any attention to amopreqcheck, and that catalog column will go
away in due course.
and the changes around create_bitmap_scan_plan in particular.
create_bitmap_subplan puts the original ~~ qual into the recheck
condition, even though the indexqual is only ((proname >= 'my'::name)
AND (proname < 'mz'::name)). So, the condition put into the recheck
condition is stronger than the checked by the index.
create_bitmap_scan_plan puts all index clauses that are not in the the
Recheck condition into the Filter. If the condition in the recheck
condition is stronger than the condition normally checked by the index,
that's wrong.
Attached is a patch that changes create_bitmap_subplan so that the
condition put into Recheck condition is never stronger than the
condition automatically handled by the index. Does that look right to you?
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
Attachments:
bitmaplike-fix-1.patchtext/x-diff; name=bitmaplike-fix-1.patchDownload
*** src/backend/optimizer/plan/createplan.c
--- src/backend/optimizer/plan/createplan.c
***************
*** 1197,1202 **** create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
--- 1197,1203 ----
IndexPath *ipath = (IndexPath *) bitmapqual;
IndexScan *iscan;
ListCell *l;
+ List *scan_clauses;
/* Use the regular indexscan plan build machinery... */
iscan = create_indexscan_plan(root, ipath, NIL, NIL);
***************
*** 1210,1216 **** create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
plan->plan_rows =
clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
plan->plan_width = 0; /* meaningless */
! *qual = get_actual_clauses(ipath->indexclauses);
foreach(l, ipath->indexinfo->indpred)
{
Expr *pred = (Expr *) lfirst(l);
--- 1211,1233 ----
plan->plan_rows =
clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
plan->plan_width = 0; /* meaningless */
!
! /*
! * Put those indexquals that are automatically handled by the index to
! * the Recheck condition. Don't include clauses that are derived from,
! * but not directly included in the original scan quals. The original
! * clause they're derived from need to be checked anyway in the Filter,
! * even for non-lossy bitmaps.
! */
! scan_clauses = get_actual_clauses(ipath->indexclauses);
! *qual = NIL;
! foreach(l, iscan->indexqualorig)
! {
! Expr *q = (Expr *) lfirst(l);
! if (list_member(scan_clauses, q))
! *qual = lappend(*qual, q);
! }
!
foreach(l, ipath->indexinfo->indpred)
{
Expr *pred = (Expr *) lfirst(l);
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:
Tom Lane wrote:
Hmm, the ~~ condition should get treated as a "filter" not a "recheck".
I suppose I broke this somewhere ...
I started to look at this last night. The culprit seems to be this patch:
Yeah, it appears that I oversimplified matters in that patch. I think
that I mistakenly decided that create_bitmap_subplan() only needed one
output parameter because there was no longer a need to distinguish
between lossy and nonlossy operators. What I forgot was that the
"nonlossy" output was also coming from the "indexquals" rather than
the "indexclauses", and that's different precisely in the case where
we've got a special index operator such as LIKE.
I think what probably has to happen is revert most of that
simplification and have create_bitmap_subplan return suitable
representations of both the indexquals and indexclauses.
Attached is a patch that changes create_bitmap_subplan so that the
condition put into Recheck condition is never stronger than the
condition automatically handled by the index. Does that look right to you?
I think this is still too simplistic, but will look closer. One point
is that it's not accounting for the bitmap AND/OR structure that might
be above the individual indexscans. The original coding avoided that
problem by making all the decisions at the top level, and I'm inclined
to stick with that approach.
regards, tom lane
I wrote:
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:
Attached is a patch that changes create_bitmap_subplan so that the
condition put into Recheck condition is never stronger than the
condition automatically handled by the index. Does that look right to you?
I think this is still too simplistic, but will look closer. One point
is that it's not accounting for the bitmap AND/OR structure that might
be above the individual indexscans. The original coding avoided that
problem by making all the decisions at the top level, and I'm inclined
to stick with that approach.
I've fixed this by reverting create_bitmap_subplan to its previous
behavior with two output lists. The scheme you suggested is a bit
logically cleaner, but aside from the issue of AND/OR conditions it
has one unpleasant feature: the RECHECK condition would get copies of
derived clauses. For instance "col LIKE 'foo%'" would end up with
a plan like
Recheck: col >= 'foo' AND col < 'fop'
Filter: col ~~ 'foo%'
Index Cond: col >= 'foo' AND col < 'fop'
The tests in create_bitmap_scan_plan aren't smart enough to recognize
that the recheck conditions are redundant given the filter condition.
The former and now-restored behavior avoids this problem, though it has
the assumption that every indexclause condition came from scan_clauses
(or has been put into bitmapqualorig in the join case), else it might
fail to enforce special operators. That's certainly true at the moment
though it seems a bit ugly to assume it here. It might be a good idea
to try to refactor the representation of special/derived quals to make
this stuff a bit more straightforward. I don't care to tackle that now
though.
regards, tom lane