index-only count(*) for indexes supporting bitmap scans

Hi,

I would like to propose a patch that speeds up the queries of the form
'select
count(*) ... where ...', where the restriction clauses can be satisfied
by some
indexes. At the moment, such queries use index-only scans followed by
aggregation. Index-only scans are only possible for indexes that are
capable of
returning indexed tuples, that is, support the 'amgettuple' access
method. They
are not applicable to indexes such as GIN and RUM. However, it is
possible to
improve count(*) performance for indexes that support bitmap scans. Having
performed a bitmap index scan or a combination of such, the bits in
bitmap can
be counted to obtain the final result. Of course, the bitmap pages that are
lossy or not visible to all existing transactions will still require heap
access.

One kind of applications that can benefit from this change is the full-text
search with pagination. To show a search results page, the application
has to
know the results that go to current page, and the total number of the
results.
Getting one page is fast, when the desired sorting order can be provided
by an
index. For example, results can be sorted by date with a separate btree
index,
or by relevance with RUM index. However, getting the total number of
results is
more difficult. With text search indexes, it requires a bitmap heap
scan, which
can be rather slow due to obligatory heap access. A well-known hack for
this is
using the approximate data from 'explain' results. The proposed change
allows
the user to obtain the precise number of the results in an efficient and
idiomatic manner.

The performance of this approach was tested on an archive of pgsql-hackers
mailing list. The detailed results for two sample queries can be found
in the
attached file 'benchmark.txt'. The first test demonstrates full-text search
with RUM index, ordering the results by rank. For a query with low
selectivity,
getting the top results is much faster than counting them all with a
bitmap heap
scan. With bitmap count execution plan, the results can be counted much
faster.
A similar test is done with a GIN index, where the results are
restricted and
ordered by date using another btree index. Again, it shows a significant
speedup
for count(*) query for bitmap count scan compared to bitmap heap scan. These
results demonstrate that the bitmap count plan can indeed be useful for
full-
text search scenarios.

Structurally, the patch consists of two major parts: a specialized executor
node and the generation of corresponding paths and plans. The optimizer
behavior
here is similar to that of the min/max aggregate optimization. The main
entry
point is preprocess_count_aggs(); it is called by grouping_planner(). It
searches for count(*) expression in the target list, and, if possible,
generates
a special path for it (struct BitmapCountPath). This path is then added to
UPPERREL_GROUP_AGG upperrel, and competes with other paths at the
further stages
of planning.

The executor node (nodeBitmapCount.c) is similar to the bitmap heap scan
node,
with the main difference being that it does not access heap for tuples
that are
known to satisfy the restriction and to be visible to all transactions.

This patch has some important limitations:
* It only supports targetlist consisting of a single expression that can be
projected from count(*).
* count(expr) is not supported. We could support it for cases where the
"expr is not null" restriction can be satisfied with an index.
* The current implementation does not support parallel execution. It
could be
implemented during the PostgreSQL 11 release cycle.
* For some indexes, the bitmap index scan will always require rechecking
all
the tuples. Bitmap count plans should not be used in such cases. For
now, this
check is not implemented.

I would be glad to hear your comments on this patch.

Regards,
Alexander Kuzmenkov

On Tue, Apr 11, 2017 at 8:24 PM, Alexander Kuzmenkov <
a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:

> I would like to propose a patch that speeds up the queries of the form
> 'select
> count(*) ... where ...', where the restriction clauses can be satisfied
> by some
> indexes. At the moment, such queries use index-only scans followed by
> aggregation. Index-only scans are only possible for indexes that are
> capable of
> returning indexed tuples, that is, support the 'amgettuple' access method.
> They
> are not applicable to indexes such as GIN and RUM. However, it is possible
> to
> improve count(*) performance for indexes that support bitmap scans. Having
> performed a bitmap index scan or a combination of such, the bits in bitmap
> can
> be counted to obtain the final result. Of course, the bitmap pages that are
> lossy or not visible to all existing transactions will still require heap
> access.
>

That's a cool feature for FTS users! Please, register this patch to the
next commitfest.

This patch has some important limitations:
> * It only supports targetlist consisting of a single expression that can be
> projected from count(*).
> * count(expr) is not supported. We could support it for cases where the
> "expr is not null" restriction can be satisfied with an index.
> * The current implementation does not support parallel execution. It could
> be
> implemented during the PostgreSQL 11 release cycle.
> * For some indexes, the bitmap index scan will always require rechecking
> all
> the tuples. Bitmap count plans should not be used in such cases. For now,
> this
> check is not implemented.
>

Does this limitation cause a performance drawback? When bitmap index scan
returns all rechecks, alternative to Bitmap Count is still Aggregate +
Bitmap Heap Scan. Thus, I think Bitmap Count would have the same
performance or even slightly faster. That's worth testing.

Also, what is planning overhead of this patch? That's worth testing too.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, Apr 12, 2017 at 12:40 AM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Tue, Apr 11, 2017 at 8:24 PM, Alexander Kuzmenkov <
> a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
>
>> I would like to propose a patch that speeds up the queries of the form
>> 'select
>> count(*) ... where ...', where the restriction clauses can be satisfied
>> by some
>> indexes. At the moment, such queries use index-only scans followed by
>> aggregation. Index-only scans are only possible for indexes that are
>> capable of
>> returning indexed tuples, that is, support the 'amgettuple' access
>> method. They
>> are not applicable to indexes such as GIN and RUM. However, it is
>> possible to
>> improve count(*) performance for indexes that support bitmap scans. Having
>> performed a bitmap index scan or a combination of such, the bits in
>> bitmap can
>> be counted to obtain the final result. Of course, the bitmap pages that
>> are
>> lossy or not visible to all existing transactions will still require heap
>> access.
>>
>
> That's a cool feature for FTS users! Please, register this patch to the
> next commitfest.
>
> This patch has some important limitations:
>> * It only supports targetlist consisting of a single expression that can
>> be
>> projected from count(*).
>> * count(expr) is not supported. We could support it for cases where the
>> "expr is not null" restriction can be satisfied with an index.
>> * The current implementation does not support parallel execution. It
>> could be
>> implemented during the PostgreSQL 11 release cycle.
>> * For some indexes, the bitmap index scan will always require rechecking
>> all
>> the tuples. Bitmap count plans should not be used in such cases. For now,
>> this
>> check is not implemented.
>>
>
> Does this limitation cause a performance drawback? When bitmap index scan
> returns all rechecks, alternative to Bitmap Count is still Aggregate +
> Bitmap Heap Scan. Thus, I think Bitmap Count would have the same
> performance or even slightly faster. That's worth testing.
>
> Also, what is planning overhead of this patch? That's worth testing too.
>

Another thing catch my eye. The estimated number of rows in Bitmap Count
node is the same as in Bitmap Index Scan node. Should it be 1 because it
always returns single row?

test1=# explain analyze select count(*) from pglist where fts @@
> to_tsquery( 'tom & lane' );
> QUERY
> PLAN
>
> --------------------------------------------------------------------------------------------------------------------------------------------
> Bitmap Count on pglist (cost=550.65..1095.68 rows=54503 width=8) (actual
> time=1120.281..1120.281 rows=1 loops=1)
> Recheck Cond: (fts @@ to_tsquery('tom & lane'::text))
> Heap Fetches: 0
> Heap Blocks: exact=105992
> -> Bitmap Index Scan on idx_pglist_rum_fts (cost=0.00..537.02
> rows=54503 width=0) (actual time=1056.060..1056.060 rows=222813 loops=1)
> Index Cond: (fts @@ to_tsquery('tom & lane'::text))
> Planning time: 119.568 ms
> Execution time: 1121.409 ms
> (8 rows)

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

>>>>> "Alexander" == Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:

Alexander> Structurally, the patch consists of two major parts: a
Alexander> specialized executor node

Why?

It strikes me that the significant fact here is not that we're doing
count(*), but that we don't need any columns from the bitmap heap scan
result. Rather than creating a whole new node, can't the existing
bitmap heapscan be taught to skip fetching the actual table page in
cases where it's all-visible, not lossy, and no columns are needed?

(this would also have the advantage of getting parallelism for free)

--
Andrew (irc:RhodiumToad)

Andrew Gierth <andrew(at)tao11(dot)riddles(dot)org(dot)uk> writes:
> "Alexander" == Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
> Alexander> Structurally, the patch consists of two major parts: a
> Alexander> specialized executor node

> Why?

> It strikes me that the significant fact here is not that we're doing
> count(*), but that we don't need any columns from the bitmap heap scan
> result. Rather than creating a whole new node, can't the existing
> bitmap heapscan be taught to skip fetching the actual table page in
> cases where it's all-visible, not lossy, and no columns are needed?

+1 ... while I hadn't actually looked at the code, it seemed to me that
anything like the optimization-as-described would be impossibly klugy
from the planner's standpoint. Your formulation sounds lots nicer.

Detecting that no columns are needed in the executor might be a bit tricky
because of the planner's habit of inserting a "physical tlist" to avoid a
projection step. (See also nearby discussion about custom scan planning.)
But we could fix that. I think one rule that would make sense is to
just disable the physical-tlist substitution if the relation's targetlist
is empty --- it wouldn't be buying much in such a case anyhow. Then the
runtime tlist for the scan node would also be empty, and away you go.

regards, tom lane

On 12.04.2017 15:04, Tom Lane wrote:
> Andrew Gierth <andrew(at)tao11(dot)riddles(dot)org(dot)uk> writes:
>> "Alexander" == Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
>> Alexander> Structurally, the patch consists of two major parts: a
>> Alexander> specialized executor node
>> Why?
>> It strikes me that the significant fact here is not that we're doing
>> count(*), but that we don't need any columns from the bitmap heap scan
>> result. Rather than creating a whole new node, can't the existing
>> bitmap heapscan be taught to skip fetching the actual table page in
>> cases where it's all-visible, not lossy, and no columns are needed?
> +1 ... while I hadn't actually looked at the code, it seemed to me that
> anything like the optimization-as-described would be impossibly klugy
> from the planner's standpoint. Your formulation sounds lots nicer.
>
> Detecting that no columns are needed in the executor might be a bit tricky
> because of the planner's habit of inserting a "physical tlist" to avoid a
> projection step. (See also nearby discussion about custom scan planning.)
> But we could fix that. I think one rule that would make sense is to
> just disable the physical-tlist substitution if the relation's targetlist
> is empty --- it wouldn't be buying much in such a case anyhow. Then the
> runtime tlist for the scan node would also be empty, and away you go.
When making an early prototype of this optimization, I did what you are
describing with the bitmap heap scan executor node. In an internal
review, it was said that the bitmap heap scan node is already
complicated enough and shouldn't have more logic added to it, so I
rewrote it a separate node. To me, your approach looks good too, so if
the community is generally in favor of this, I could rewrite the
executor as such.

With planner, the changes are more complex. Two things must be done
there. First, when the tlist is empty, we must use a different cost
function for bitmap heap scan, because the heap access pattern is
different. Second, choose_bitmap_and() must use a different algorithm
for choosing the right combination of paths. A standard algorithm
chooses the combination based on cost. For count(*) purposes, the
decisive factor is that the path has to check all the restrictions, or
else we'll need heap access to recheck some of them, which defeats the
purpose of having this optimization. The planner code that builds and
costs the index path is fairly complex, and integrating this additional
behavior into it didn't look good to me. Instead, I created a
specialized path node and isolated the logic that handles it. The
resulting implementation adds several functions, but it is mostly
self-contained and has a single entry point in grouping_planner(). It
handles the specific case of bitmap count plans and doesn't complicate
the existing code any further.

The planner part is to some extent independent of whether we use a
separate executor node or not. If we choose not to, the same count(*)
optimization code I proposed could create plain bitmap heap scan paths.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
> With planner, the changes are more complex. Two things must be done
> there. First, when the tlist is empty, we must use a different cost
> function for bitmap heap scan, because the heap access pattern is
> different. Second, choose_bitmap_and() must use a different algorithm
> for choosing the right combination of paths. A standard algorithm
> chooses the combination based on cost. For count(*) purposes, the
> decisive factor is that the path has to check all the restrictions, or
> else we'll need heap access to recheck some of them, which defeats the
> purpose of having this optimization. The planner code that builds and
> costs the index path is fairly complex, and integrating this additional
> behavior into it didn't look good to me.

TBH, I'm not sure you need to do any of that work. Have you got evidence
that the planner will fail to choose the right plan regardless? I'm
particularly unconvinced that choose_bitmap_and is a critical problem,
because once you're into having to AND multiple indexes, you're talking
about an expensive query anyhow.

regards, tom lane

On 12.04.2017 17:24, Tom Lane wrote:
> TBH, I'm not sure you need to do any of that work. Have you got evidence
> that the planner will fail to choose the right plan regardless? I'm
> particularly unconvinced that choose_bitmap_and is a critical problem,
> because once you're into having to AND multiple indexes, you're talking
> about an expensive query anyhow.
The most expensive part would probably be accessing the heap in the
bitmap heap scan. It may be worth trying to choose an index path that
checks all the restriction and therefore allows us to skip this heap
access. This path might not be the cheapest one, though. The standard
AND selection procedure would have discarded it based on cost.
I've seen this happen on the regression database. Somehow I can't seem
to reproduce it on my earlier full-text search example.

An example:

regression=# explain select count(*) from tenk1 where hundred < 90 and
thousand < 31;
QUERY PLAN
-------------------------------------------------------------------------------------------
Bitmap Count on tenk1 (cost=182.69..185.56 rows=1 width=8)
Recheck Cond: ((thousand < 31) AND (hundred < 90))
-> BitmapAnd (cost=182.69..182.69 rows=287 width=0)
-> Bitmap Index Scan on tenk1_thous_tenthous (cost=0.00..6.68
rows=319 width=0)
Index Cond: (thousand < 31)
-> Bitmap Index Scan on tenk1_hundred (cost=0.00..175.62
rows=8978 width=0)
Index Cond: (hundred < 90)
(7 rows)

regression=# set enable_bitmapcount to off;
SET
regression=# explain select count(*) from tenk1 where hundred < 90 and
thousand < 31;
QUERY PLAN
-------------------------------------------------------------------------------------------
Aggregate (cost=375.34..375.35 rows=1 width=8)
-> Bitmap Heap Scan on tenk1 (cost=6.75..374.62 rows=287 width=0)
Recheck Cond: (thousand < 31)
Filter: (hundred < 90)
-> Bitmap Index Scan on tenk1_thous_tenthous (cost=0.00..6.68
rows=319 width=0)
Index Cond: (thousand < 31)
(6 rows)

--

Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 12.04.2017 12:29, Alexander Korotkov wrote:

> That's a cool feature for FTS users! Please, register this patch to
> the next commitfest.
I've added this to the 2017-07 commitfest:
https://commitfest.postgresql.org/14/1117/

> Also, what is planning overhead of this patch? That's worth
> testing too.
>
The planning overhead is about 0.1 - 0.07 ms on the samples from my
first letter.

> Another thing catch my eye. The estimated number of rows in Bitmap
> Count node is the same as in Bitmap Index Scan node. Should it be 1
> because it always returns single row?
You're right, I'll fix this in the next version of the patch.

> Does this limitation cause a performance drawback? When bitmap
> index scan returns all rechecks, alternative to Bitmap Count is
> still Aggregate + Bitmap Heap Scan. Thus, I think Bitmap Count
> would have the same performance or even slightly faster. That's
> worth testing.
>
Bitmap heap scan can indeed be faster, because it prefetches heap pages,
and can be run in parallel. When the table data is not cached, the
difference is not big on my machine. It could probably be significant if
I used a storage that supported parallel reads. When the data is cached
in memory, the parallel bitmap heap scan can be significantly faster.
We could use the standard bitmap heap scan node with some tweaks, as
discussed in the other subthread, to avoid this regression.

Here are some test queries:

--- not cached
-------------------------------------------------------------------------------------------------------------------
test1=# explain analyze select count(*) from pglist where fts @@
to_tsquery( 'tom & lane' );
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Bitmap Count on pglist (cost=542.65..1087.68 rows=54503 width=8)
(actual time=30264.174..30264.177 rows=1 loops=1)
Recheck Cond: (fts @@ to_tsquery('tom & lane'::text))
Rows Removed by Index Recheck: 270853
Heap Fetches: 66138
Heap Blocks: exact=39854 lossy=66138
-> Bitmap Index Scan on idx_pglist_fts (cost=0.00..529.02
rows=54503 width=0) (actual time=525.341..525.341 rows=222813 loops=1)
Index Cond: (fts @@ to_tsquery('tom & lane'::text))
Planning time: 128.238 ms
Execution time: 30264.299 ms
(9 rows)

test1=# set enable_bitmapcount to off;
SET
test1=# explain analyze select count(*) from pglist where fts @@
to_tsquery( 'tom & lane' );
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=119989.73..119989.74 rows=1 width=8) (actual
time=31699.829..31699.830 rows=1 loops=1)
-> Gather (cost=119989.52..119989.73 rows=2 width=8) (actual
time=31698.699..31699.819 rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (cost=118989.52..118989.53 rows=1
width=8) (actual time=31689.289..31689.290 rows=1 loops=3)
-> Parallel Bitmap Heap Scan on pglist
(cost=542.65..118932.74 rows=22710 width=0) (actual
time=608.532..31634.692 rows=74271 loops=3)
Recheck Cond: (fts @@ to_tsquery('tom & lane'::text))
Rows Removed by Index Recheck: 90284
Heap Blocks: exact=13242 lossy=21960
-> Bitmap Index Scan on idx_pglist_fts
(cost=0.00..529.02 rows=54503 width=0) (actual time=552.136..552.136
rows=222813 loops=1)
Index Cond: (fts @@ to_tsquery('tom &
lane'::text))
Planning time: 160.055 ms
Execution time: 31724.468 ms
(13 rows)

----- cached
-------------------------------------------------------------------------------------------------------------------------------------
test1=# explain analyze select count(*) from pglist where fts @@
to_tsquery( 'tom & lane' );
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=119989.73..119989.74 rows=1 width=8) (actual
time=1250.973..1250.973 rows=1 loops=1)
-> Gather (cost=119989.52..119989.73 rows=2 width=8) (actual
time=1250.588..1250.964 rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (cost=118989.52..118989.53 rows=1
width=8) (actual time=1246.144..1246.144 rows=1 loops=3)
-> Parallel Bitmap Heap Scan on pglist
(cost=542.65..118932.74 rows=22710 width=0) (actual
time=82.781..1237.585 rows=74271 loops=3)
Recheck Cond: (fts @@ to_tsquery('tom & lane'::text))
Rows Removed by Index Recheck: 90284
Heap Blocks: exact=13221 lossy=22217
-> Bitmap Index Scan on idx_pglist_fts
(cost=0.00..529.02 rows=54503 width=0) (actual time=78.366..78.366
rows=222813 loops=1)
Index Cond: (fts @@ to_tsquery('tom &
lane'::text))
Planning time: 0.722 ms
Execution time: 1256.028 ms
(13 rows)

test1=# set enable_bitmapcount to on;
SET
test1=# explain analyze select count(*) from pglist where fts @@
to_tsquery( 'tom & lane' );
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Bitmap Count on pglist (cost=542.65..1087.68 rows=54503 width=8)
(actual time=2745.740..2745.742 rows=1 loops=1)
Recheck Cond: (fts @@ to_tsquery('tom & lane'::text))
Rows Removed by Index Recheck: 270853
Heap Fetches: 66138
Heap Blocks: exact=39854 lossy=66138
-> Bitmap Index Scan on idx_pglist_fts (cost=0.00..529.02
rows=54503 width=0) (actual time=85.572..85.572 rows=222813 loops=1)
Index Cond: (fts @@ to_tsquery('tom & lane'::text))
Planning time: 0.701 ms
Execution time: 2745.800 ms
(9 rows)

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

|Hello everyone,

I made a new patch according to the previous comments. It is simpler
now, only adding a few checks to the bitmap heap scan node. When the
target list for the bitmap heap scan is empty, and there is no filter,
and the bitmap page generated by the index scan is exact, and the
corresponding heap page is visible to all transaction, we don't fetch it.

The performance is better than with the previous patch, because now it
can leverage the parallel heap scan logic. A simple benchmark is
attached: this patch is more than ten times faster on a frequent search
term, and two times faster on an infrequent one.

Still, there is one thing that is bothering me. I use empty targetlist
as the marker of that I should not fetch tuples. Because of that, I have
to make sure that use_physical_tlist() doesn't touch empty tlists.
Consequently, if count(*) sits on top of a subquery, this subquery has
to project and cannot be deleted (see trivial_subqueryscan). There is
such a query in the regression test select_distinct: "select count(*)
from (select distinct two, four, two from tenk1);". For that particular
query it shouldn't matter much, so I changed the test, but the broader
implications of this escape me at the moment.

The cost estimation is very simplified now: I just halve the number of
pages to be fetched. The most important missing part is checking whether
we have any quals that are not checked by the index: if we do, we'll
have to fetch all the tuples. Finding nonindex qualifications is
somewhat convoluted for the bitmap index scan tree involving multiple
indexes, so I didn't implement it for now. We could also consider
estimating the number of lossy pages in the tid bitmap given current
work_mem size.

I'll be glad to hear your thoughts on this.|

The following review has been posted through the commitfest application:
make installcheck-world: tested, failed
Implements feature: not tested
Spec compliant: not tested
Documentation: not tested

Hi Alexander,

make check-world fails on contrib/postgres_fdw because of Subquery Scan on ... Probably, query plan was changed.

The new status of this patch is: Waiting on Author

On 04.09.2017 15:17, Alexey Chernyshov wrote:
> make check-world fails on contrib/postgres_fdw because of Subquery Scan on ... Probably, query plan was changed.

Hi Alexey,

Thanks for testing! This is the same problem as the one in
'select_distinct' I mentioned before. I changed the test, the updated
patch is attached.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: tested, passed
Documentation: tested, passed

One thing I have noticed is a trailing whitespace after "bogus one":

123 + * If we don't have to fetch the tuple, just return a
124 + * bogus one
125 + */

The new status of this patch is: Ready for Committer

Alexander Kuzmenkov <a(dot)kuzmenkov(at)postgrespro(dot)ru> writes:
> On 04.09.2017 15:17, Alexey Chernyshov wrote:
>> make check-world fails on contrib/postgres_fdw because of Subquery Scan on ... Probably, query plan was changed.

> Thanks for testing! This is the same problem as the one in
> 'select_distinct' I mentioned before. I changed the test, the updated
> patch is attached.

I've pushed the executor part of this, but mostly not the planner part,
because I didn't think the latter was anywhere near ready for prime
time: the regression test changes it was causing were entirely bogus.

You had basically two categories of plan changes showing up in the
regression tests. One was insertion of Subquery Scan nodes where
they hadn't been before; that was because the use_physical_tlist
change broke the optimization that removed no-op Subquery Scans.
I fixed that by narrowing the use_physical_tlist change to apply
only to BitmapHeapPath nodes, which is the only case where there
would be any benefit anyway. The remaining plan diffs after making
that change all amounted to replacing regular index-only scan plans
with bitmap scans, which seems to me to be silly on its face: if we
can use an IOS then it is unlikely that a bitmap scan will be better.
Those changes indicate that the cost adjustment you'd inserted in
cost_bitmap_heap_scan was way too optimistic, which is hardly
surprising. I think a realistic adjustment would have to account
for all or most of these factors:

* Whether the index AM is ever going to return recheck = false.
The planner has no way to know that at present, but since there are
lots of cases where it simply won't ever happen, I think assuming
that it always will is not acceptable. Perhaps we could extend the
AM API so that we could find out whether recheck would happen always,
never, or sometimes. (Doing better than "sometimes" might be too hard,
but I think most opclasses are going to be "always" or "never" anyway.)

* Whether the bitmap will become lossy, causing us to have to make
rechecks anyway. We could probably estimate that pretty well based
on comparing the initial number-of-pages estimate to work_mem.

* Whether the plan will need to fetch heap tuples to make filter-qual
checks. In principle the planner ought to know that. In practice,
right now it doesn't bother to figure out whether the qual will be
empty until createplan.c time, because that's rather a significant
amount of work and it's undesirable to expend it for paths we might
not end up using. We might be able to approximate it better than
we do now, though. It's a live problem for regular indexscan costing
as well as bitmap scans, IIRC.

* What fraction of the table is actually all-visible. You'd effectively
hard-wired that at 50%, but it's easy to do better --- the regular
IOS code does

if (indexonly)
pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));

and it would be appropriate to do the same here if we conclude that
the other gating conditions apply.

Without a patch that deals more realistically with these concerns,
I think we're better off not changing the cost estimate at all.

As far as the executor side goes, I made several cosmetic changes
and one not so cosmetic one: I changed the decision about whether
to prefetch so that it looks at whether the potential prefetch
page is all-visible. This still relies on the same assumption you
had that the recheck flag will stay the same from one page to the
next, but at least it's not assuming that the all-visible state
will stay the same.

I'm going to mark the CF entry closed, but if you feel like working
on the cost estimate business, feel free to submit another patch
for that.

regards, tom lane

> I've pushed the executor part of this, but mostly not the planner part,
> because I didn't think the latter was anywhere near ready for prime
> time: the regression test changes it was causing were entirely bogus.
>
Hi Tom,

Thanks for the commit and the explanation. I'll try to address your
comments if I continue working on the planner part.

--

Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company