Thread: Any way to favor index scans, but not bitmap index scans?

Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
The data set I am working with has a very uneven distribution.

I had to to set random_page_cost = 0.75 to get good plans.
However, that first tries bitmap scans which perform very poorly.
Is there a way to have the planner to favor index scans and disfavor bitmap
scans? Is my best choice to just disable bitmap scans?

So far in this data set almost every time bitmap scans are used the queries
do worse, much worse. I had one extreme case where a sequential scan would
finish in 20 minutes and the same query using bitmap scans would take over
a day to finish.

My most recent test(before reducing random_page_cost)..
Sequential scan(default selected by planner): 12 minutes
Seq scan dissabled(bitmap index scans): 29.98 minutes
Seq scan disabled and bitmap index disabled: 3 seconds!

After I reduced random_page_cost and turned bitmap index off the planner is
picking up the right plan using an index scan. Now just testing more cases
to make sure the improvement is consistant for most of our queries.


--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general



Re: Any way to favor index scans, but not bitmap index scans?

From
Tom Lane
Date:
"Francisco Reyes" <lists@stringsutils.com> writes:
> So far in this data set almost every time bitmap scans are used the queries
> do worse, much worse. I had one extreme case where a sequential scan would
> finish in 20 minutes and the same query using bitmap scans would take over
> a day to finish.

That's fairly hard to believe.  Care to offer some details?

            regards, tom lane

Re: Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
On 12:40 pm 07/23/08 Tom Lane <tgl@sss.pgh.pa.us> wrote:
> That's fairly hard to believe.  Care to offer some details?


I will dig that actual project and run explain analyze. Will likely not
have it till middle of next week though because of a monthly process
starting out Friday.

However, I do have a current example where bitmap index scan was 3 times
worse. On the extremely bad case the data set was 5 times larger than the
sample below (1+ billion vs 215 million).

Sequential scan: 12 minutes
Seq scan dissabled -> bitmap index scan: 29.98 minutes
Seq scan disabled and bitmap index disabled: 3 seconds!

I have to mask the names so any discrepancy in names likely just my mistake.

2 tables involved.
historical has 215 million rows.
join_ids has 2.5 million rows.

A join from join_ids to historical will only touch about 40% of the records
in historical.

The queries below only returned 0.2% (less than 1%) of records from the
historical table.



default_statistics_target = 1000
random_page_cost = 4.0

Default query before changing settings.
Aggregate  (cost=7656776.19..7656776.20 rows=1 width=12) (actual
time=719661.082..719661.085 rows=1 loops=1)
   ->  Hash Join  (cost=9260.90..7653867.79 rows=387785 width=12)
         (actual time=2249.423..719109.201 rows=194734 loops=1)
         Hash Cond: (historical.join_id = join_ids.join_id)
         ->  Seq Scan on historical
                (cost=0.00..5825538.00 rows=207450405 width=16) (actual
time=7.966..410078.540 rows=207589225 loops=1)
               Filter: ((f5 > 0::numeric) AND (date > '2007-04-01'::date)
AND (date < '2008-05-01'::date))
         ->  Hash  (cost=9198.15..9198.15 rows=5020 width=4) (actual
time=2210.953..2210.953 rows=4437 loops=1)
               ->  Bitmap Heap Scan on join_ids join_ids
(cost=163.00..9198.15 rows=5020 width=4)
                   (actual time=247.903..2201.789 rows=4437 loops=1)
                     Recheck Cond: (customer_id = ANY ('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
                     ->  Bitmap Index Scan on join_ids_customer_id_join_id
(cost=0.00..161.74 rows=5020 width=0)
                         (actual time=241.111..241.111 rows=4437 loops=1)
                           Index Cond: (customer_id = ANY
('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
Total runtime: 719816.542 ms --> 12 minutes


SET ENABLE_SEQSCAN TO OFF;
Aggregate  (cost=11867354.72..11867354.73 rows=1 width=12) (actual
time=1798829.579..1798829.581 rows=1 loops=1)
   ->  Hash Join  (cost=4645436.35..11864446.33 rows=387785 width=12)
         (actual time=1086218.285..1798250.004 rows=194734 loops=1)
         Hash Cond: (historical.join_id = join_ids.join_id)
         ->  Bitmap Heap Scan on historical
             (cost=4636175.45..10036116.53 rows=207450405 width=16)
               (actual time=1086158.692..1487577.412 rows=207589225 loops=1)
               Recheck Cond: ((date > '2007-04-01'::date) AND (date <
'2008-05-01'::date))
               Filter: (f5 > 0::numeric)
               ->  Bitmap Index Scan on historical_join_id_date
                  (cost=0.00..4584312.85 rows=210080576 width=0)
                   (actual time=1085395.070..1085395.070 rows=210233223
loops=1)
                     Index Cond: ((date > '2007-04-01'::date) AND (date <
'2008-05-01'::date))
         ->  Hash  (cost=9198.15..9198.15 rows=5020 width=4) (actual
time=18.712..18.712 rows=4437 loops=1)
               ->  Bitmap Heap Scan on join_ids (cost=163.00..9198.15
rows=5020 width=4)
                    (actual time=1.541..11.654 rows=4437 loops=1)
                     Recheck Cond: (customer_id = ANY ('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
                     ->  Bitmap Index Scan on join_ids_customer_id_join_id
                         (cost=0.00..161.74 rows=5020 width=0) (actual
time=0.984..0.984 rows=4437 loops=1)
                           Index Cond: (customer_id = ANY
('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
 Total runtime: 1798847.930 ms --> 29.98 minutes


SET ENABLE_SEQSCAN TO OFF;
SET ENABLE_BITMAPSCAN TO OFF;
Aggregate  (cost=25665216.10..25665216.11 rows=1 width=12) (actual
time=3088.894..3088.896 rows=1 loops=1)
   ->  Nested Loop  (cost=0.00..25662307.70 rows=387785 width=12)
             (actual time=0.264..2624.680 rows=194734 loops=1)
         ->  Index Scan using join_ids_join_id on join_ids
             (cost=0.00..2867051.21 rows=5020 width=4) (actual
time=0.237..1236.019 rows=4437 loops=1)
               Filter: (customer_id = ANY ('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
         ->  Index Scan using historical_join_id_date on historical
             (cost=0.00..4522.43 rows=1477 width=16) (actual
time=0.010..0.153 rows=44 loops=4437)
               Index Cond: ((historical.join_id = join_ids.join_id) AND
(historical.date > '2007-04-01'::date)
               AND (historical.date < '2008-05-01'::date))
               Filter: (trans.f5 > 0::numeric)
 Total runtime: 3091.227 ms --> 3 seconds


Re: Any way to favor index scans, but not bitmap index scans?

From
"Scott Marlowe"
Date:
On Wed, Jul 23, 2008 at 11:43 AM, Francisco Reyes
<lists@stringsutils.com> wrote:
> On 12:40 pm 07/23/08 Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> That's fairly hard to believe.  Care to offer some details?
>
>
> I will dig that actual project and run explain analyze. Will likely not
> have it till middle of next week though because of a monthly process
> starting out Friday.
>
> However, I do have a current example where bitmap index scan was 3 times
> worse. On the extremely bad case the data set was 5 times larger than the
> sample below (1+ billion vs 215 million).

What is your work_mem set to?

Re: Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
On 2:23 pm 07/23/08 "Scott Marlowe" <scott.marlowe@gmail.com> wrote:
> >  However, I do have a current example where bitmap index scan was 3
> >  times worse.

> What is your work_mem set to?

For the examples that I posted it is
work_mem = 64MB


Re: Any way to favor index scans, but not bitmap index scans?

From
Tom Lane
Date:
"Francisco Reyes" <lists@stringsutils.com> writes:
> SET ENABLE_SEQSCAN TO OFF;
> SET ENABLE_BITMAPSCAN TO OFF;
> Aggregate  (cost=25665216.10..25665216.11 rows=1 width=12) (actual
> time=3088.894..3088.896 rows=1 loops=1)
>    ->  Nested Loop  (cost=0.00..25662307.70 rows=387785 width=12)
>              (actual time=0.264..2624.680 rows=194734 loops=1)
>          ->  Index Scan using join_ids_join_id on join_ids
>              (cost=0.00..2867051.21 rows=5020 width=4) (actual
> time=0.237..1236.019 rows=4437 loops=1)
>                Filter: (customer_id = ANY ('{1014,2485,4636,4635,1255,547,374,580}'::integer[]))
>          ->  Index Scan using historical_join_id_date on historical
>              (cost=0.00..4522.43 rows=1477 width=16) (actual
> time=0.010..0.153 rows=44 loops=4437)
>                Index Cond: ((historical.join_id = join_ids.join_id) AND
> (historical.date > '2007-04-01'::date)
>                AND (historical.date < '2008-05-01'::date))
>                Filter: (trans.f5 > 0::numeric)
>  Total runtime: 3091.227 ms --> 3 seconds

You might be more likely to get a sane plan if you had an index on
join_ids.customer_id.  The first indexscan above is really a completely
silly choice, and would never have been used if you weren't holding
a gun to the planner's head.  The index isn't contributing any
selectivity at all.

The other part of the problem is the factor-of-thirty overestimate of
the number of rows that the inner indexscan will produce (which means
also a factor-of-thirty overestimate of its cost).  Perhaps higher
statistics targets for these two relations would give you a better
estimate there.

But there's something else going on, because the estimated rowcount for
the join (387785) is considerably less than the product of the scan
estimates (5020 * 1477 = 7414540), when it should be the same since
there's no additional join condition.  What PG version are you running
exactly?

            regards, tom lane

Re: Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
On 3:37 pm 07/23/08 Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Francisco Reyes" <lists@stringsutils.com> writes:
> >  SET ENABLE_SEQSCAN TO OFF;
> >  SET ENABLE_BITMAPSCAN TO OFF;
> >  Aggregate  (cost=25665216.10..25665216.11 rows=1 width=12) (actual
> >  time=3088.894..3088.896 rows=1 loops=1)
> >     ->  Nested Loop  (cost=0.00..25662307.70 rows=387785 width=12)
> >               (actual time=0.264..2624.680 rows=194734 loops=1)
> >           ->  Index Scan using join_ids_join_id on join_ids
> >               (cost=0.00..2867051.21 rows=5020 width=4) (actual
> >  time=0.237..1236.019 rows=4437 loops=1)
> >                 Filter: (customer_id = ANY ('{1014,2485,4636,4635,12
> 55,547,374,580}'::integer[]))
> >           ->  Index Scan using historical_join_id_date on historical
> >               (cost=0.00..4522.43 rows=1477 width=16) (actual
> >  time=0.010..0.153 rows=44 loops=4437)
> >                 Index Cond: ((historical.join_id =
> >  join_ids.join_id) AND (historical.date > '2007-04-01'::date)
> >                 AND (historical.date < '2008-05-01'::date))
> >                 Filter: (trans.f5 > 0::numeric)
> >   Total runtime: 3091.227 ms --> 3 seconds
>
> You might be more likely to get a sane plan if you had an index on
> join_ids.customer_id.

There is an index in join_ids:
joinids_customerids_joinid" btree (customer_id, joinid) WITH (fillfactor=98)

Also, that plan is only 3 seconds. That is as good as that is going to get.
Or where you refering that the other plans would have been better?

> The first indexscan above is really a
> completely silly choice, and would never have been used if you
> weren't holding a gun to the planner's head.

I have much to learn about how to properly read an explain analyze, but as
silly as that plan may look it outperforms the other plans by orders of
magnitude. 3 seconds vs 12 minutes is a very big difference. It was so fast
that I even compared the results (which happens to be a single row) to make
sure I was getting the correct value.

>The index isn't contributing any selectivity at all.

Which index scan? Are analyze read bottom up right?
If it is this one you are refering to:

->  Index Scan using historical_join_id_date on historical
> >               (cost=0.00..4522.43 rows=1477 width=16) (actual
> >  time=0.010..0.153 rows=44 loops=4437)
> >                 Index Cond: ((historical.join_id =
> >  join_ids.join_id) AND (historical.date > '2007-04-01'::date)
> >                 AND (historical.date < '2008-05-01'::date))
> >                 Filter: (trans.f5 > 0::numeric)

I believe that is the reason performance is good with that plan.
The number of rows that need to be returned from historical is less than 1%.

> The other part of the problem is the factor-of-thirty overestimate of
> the number of rows that the inner indexscan will produce (which means
> also a factor-of-thirty overestimate of its cost).  Perhaps higher
> statistics targets for these two relations would give you a better
> estimate there.

Is it possible to go over
default_statistics_target = 1000?


> since there's no additional join condition.  What PG version are you
> running exactly?

8.3.3

I have only been at this job for 3 months and I can say that neither the
data, nor the previous design I am trying to replace play nice with
postgresql. I can't get into specifics, but I can say that our "historical"
tables have about 60% data that is not used in most queries. I think that
is partly what throws off the planner so much. My first clue was when I saw
the planner trying to do sequential scans to retrieve less than 1% of rows.
It didn't make sense.

I tried several schemes with partitioning and that was even worse.

I am going to convert the tables structure names to the mapping names I
used in these thread. Perhaps that may be informative.


Re: Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
Table layouts:
historical
  Column   |     Type     |                            Modifiers
-----------+--------------+------------------------------------------------------------------
 record_id | integer      | not null default nextval('historical_record_id_seq'::regclass)
 f3        | integer      | not null
 date      | date         | not null
 f4        | smallint     |
 f5        | numeric(9,2) | not null
 join_id   | integer      | not null
Indexes:
    "historical_f3" btree (f3) WITH (fillfactor=98), tablespace "st2"
    "historical_join_id_date" btree (join_id, date) WITH (fillfactor=98),
tablespace "st2"
    "historical_record_id" btree (record_id) WITH (fillfactor=98),
tablespace "st2"


join_ids
 Column     |  Type   | Modifiers
------------+---------+-----------
 join_id    | integer | not null
customer_id | integer | not null
Indexes:
    "join_ids_pkey" PRIMARY KEY, btree (join_id)
    "join_ids_customerid_joinid" btree (customer_id, join_id) WITH
(fillfactor=98)

Historical has 215 million rows.
join_ids has 2.5 million rows.

The number or rows in join_ids that have a matching record in historical
(by join_id) is roughly 86 million.

The select from the previous 3 explain analyze had about 0.22% (that is 1/5
of 1%... not 22%) rows that needed to be returned for that query from the
historical table.


Re: Any way to favor index scans, but not bitmap index scans?

From
Tom Lane
Date:
"Francisco Reyes" <lists@stringsutils.com> writes:
> On 3:37 pm 07/23/08 Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> You might be more likely to get a sane plan if you had an index on
>> join_ids.customer_id.

> There is an index in join_ids:
> joinids_customerids_joinid" btree (customer_id, joinid) WITH (fillfactor=98)

[ squint... ]  That makes no sense at all; it should certainly have
picked that index and not join_ids_join_id for a scan with a condition
on customer_id.  What is the datatype of the customer_id column exactly?
(Actually, if you could show us the whole schema of both these tables,
such as their psql \d descriptions, that would be helpful.)

            regards, tom lane

Re: Any way to favor index scans, but not bitmap index scans?

From
"Francisco Reyes"
Date:
On 4:12 pm 07/23/08 "Francisco Reyes" <lists@stringsutils.com> wrote:
> Also, that plan is only 3 seconds.

Minor update.
A co-worker is using another DB.. and re-running my query after he did his
work.. now the query using the index scans takes 2 minutes instead of 3
seconds. 3 seconds was likely data cached.

To re-list the times..
Sequential scan 12 minutes
Bitmap scans 30 minutes
index scan with not bitmap 2 minutes

It is worth pointing out that the bitmap test was run AFTER the sequential
scan test.. right after it.. so it should have benefited from OS caching.
The join_ids table fits completely in memory.

select pg_size_pretty(pg_total_relation_size('join_ids'));
 pg_size_pretty
----------------
 291 MB
(1 row)

par4mo=# select pg_size_pretty(pg_relation_size('join_ids'));
 pg_size_pretty
----------------
 94 MB
(1 row)