Why isn't an index scan being used?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Why isn't an index scan being used?

Abi Noda
Postgres version: PostgreSQL 10.3 on x86_64-apple-darwin16.7.0
Operating system and version: MacOS v10.12.6
How you installed PostgreSQL: Homebrew

I have a table as defined below. The table contains 1,027,616 rows, 50,349 of which have state='open' and closed IS NULL. Since closed IS NULL for all rows where state='open', I want to remove the unnecessary state column.

```
CREATE TABLE tickets (
  id bigserial primary key,
  title character varying,
  description character varying,
  state character varying,
  closed timestamp,
  created timestamp,
  updated timestamp,
  last_comment timestamp,
  size integer NOT NULL,
  comment_count integer NOT NULL
);

CREATE INDEX  "state_index" ON "tickets" ("state") WHERE ((state)::text = 'open'::text));
```


As part of the process of removing the state column, I am trying to index the closed column so I can achieve equal query performance (index scan) as when I query on the state column as shown below:

```
EXPLAIN ANALYZE select title, created, closed, updated from tickets where state = 'open';

Index Scan using state_index on tickets  (cost=0.29..23430.20 rows=50349 width=64) (actual time=17.221..52.110 rows=51533 loops=1)
Planning time: 0.197 ms
Execution time: 56.255 ms
```


However, when I index the closed column, a bitmap scan is used instead of an index scan, with slightly slower performance. Why isn't an index scan being used, given that the exact same number of rows are at play as in my query on the state column? How do I index closed in a way where an index scan is used?

```
CREATE INDEX closed_index ON tickets (id) WHERE closed IS NULL;

VACUUM ANALYZE tickets;

EXPLAIN ANALYZE select title, created, closed, updated from tickets where closed IS NULL;

Bitmap Heap Scan on tickets  (cost=824.62..33955.85 rows=50349 width=64) (actual time=10.420..56.095 rows=51537 loops=1)
  Recheck Cond: (closed IS NULL)
  Heap Blocks: exact=17478
  ->  Bitmap Index Scan on closed_index  (cost=0.00..812.03 rows=50349 width=0) (actual time=6.005..6.005 rows=51537 loops=1)
Planning time: 0.145 ms
Execution time: 60.266 ms
```

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

David Rowley-3
On Wed, 20 Feb 2019 at 13:11, Abi Noda <[hidden email]> wrote:
> However, when I index the closed column, a bitmap scan is used instead of an index scan, with slightly slower performance. Why isn't an index scan being used, given that the exact same number of rows are at play as in my query on the state column?

That's down to the planner's cost estimates. Likely it thinks that
either doing a bitmap scan is cheaper, or close enough that it does
not matter.

> How do I index closed in a way where an index scan is used?

The costing does account for the size of the index. If the
"closed_index" index is large than the "state_index", then doing an
Index scan on "closed_index" is going to be costed higher.

Most of this likely boils down to random_page_cost being a guess. You
may want to check your effective_cache_size is set to something like
75% of the machine's memory, and/or tweak random page cost down, if
it's set to the standard 4 setting.  modern SSDs are pretty fast at
random reads. HDDs, not so much.

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Abi Noda
Thank you for the help.

> If the "closed_index" index is large than the "state_index", then doing an Index scan on "closed_index" is going to be costed higher.

FWIW, both indexes appear to be the same size:

select pg_size_pretty(pg_relation_size('state_index'));
1144 kB

select pg_size_pretty(pg_relation_size('closed_index'));
1144 kB

> Most of this likely boils down to random_page_cost being a guess. You may want to check your effective_cache_size is set to something like 75% of the machine's memory, and/or tweak random page cost down, if it's set to the standard 4 setting.

Ok, let me try this.


On Tue, Feb 19, 2019 at 5:51 PM David Rowley <[hidden email]> wrote:
On Wed, 20 Feb 2019 at 13:11, Abi Noda <[hidden email]> wrote:
> However, when I index the closed column, a bitmap scan is used instead of an index scan, with slightly slower performance. Why isn't an index scan being used, given that the exact same number of rows are at play as in my query on the state column?

That's down to the planner's cost estimates. Likely it thinks that
either doing a bitmap scan is cheaper, or close enough that it does
not matter.

> How do I index closed in a way where an index scan is used?

The costing does account for the size of the index. If the
"closed_index" index is large than the "state_index", then doing an
Index scan on "closed_index" is going to be costed higher.

Most of this likely boils down to random_page_cost being a guess. You
may want to check your effective_cache_size is set to something like
75% of the machine's memory, and/or tweak random page cost down, if
it's set to the standard 4 setting.  modern SSDs are pretty fast at
random reads. HDDs, not so much.

--
 David Rowley                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services
Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Andrew Gierth
In reply to this post by Abi Noda
>>>>> "Abi" == Abi Noda <[hidden email]> writes:

 Abi> However, when I index the closed column, a bitmap scan is used
 Abi> instead of an index scan, with slightly slower performance. Why
 Abi> isn't an index scan being used, given that the exact same number
 Abi> of rows are at play as in my query on the state column?

Most likely difference is the correlation estimate for the conditions.
The cost of an index scan includes a factor based on how well correlated
the physical position of rows is with the index order, because this
affects the number of random seeks in the scan. But for nulls this
estimate cannot be performed, and bitmapscan is cheaper than plain
indexscan on poorly correlated data.

--
Andrew (irc:RhodiumToad)

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Michael Lewis

On Tue, Feb 19, 2019, 8:00 PM Andrew Gierth <[hidden email] wrote:
>>>>> "Abi" == Abi Noda <[hidden email]> writes:

 Abi> However, when I index the closed column, a bitmap scan is used
 Abi> instead of an index scan, with slightly slower performance. Why
 Abi> isn't an index scan being used, given that the exact same number
 Abi> of rows are at play as in my query on the state column?

Most likely difference is the correlation estimate for the conditions.
The cost of an index scan includes a factor based on how well correlated
the physical position of rows is with the index order, because this
affects the number of random seeks in the scan. But for nulls this
estimate cannot be performed, and bitmapscan is cheaper than plain
indexscan on poorly correlated data.

Does this imply that the optimizer would always prefer the bitmapscan rather than index scan even if random page cost = 1, aka sequential cost, when the correlation is unknown like a null? Or only when it thinks random access is more expensive by some significant factor?


--
Andrew (irc:RhodiumToad)

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Justin Pryzby
In reply to this post by Abi Noda
On Tue, Feb 19, 2019 at 05:10:43PM -0700, Abi Noda wrote:
> I have a table as defined below. The table contains 1,027,616 rows, 50,349
> of which have state='open' and closed IS NULL. Since closed IS NULL for all
> rows where state='open', I want to remove the unnecessary state column.
>
> CREATE TABLE tickets (
>   id bigserial primary key,
>   state character varying,
>   closed timestamp,
...

> );
>
> CREATE INDEX  "state_index" ON "tickets" ("state") WHERE ((state)::text =
> 'open'::text));
>
> As part of the process of removing the state column, I am trying to index
> the closed column so I can achieve equal query performance (index scan) as
> when I query on the state column as shown below:
>
> EXPLAIN ANALYZE select title, created, closed, updated from tickets where state = 'open';
> Index Scan using state_index on tickets  (cost=0.29..23430.20 rows=50349 width=64) (actual time=17.221..52.110 rows=51533 loops=1)
>
> However, when I index the closed column, a bitmap scan is used instead of
> an index scan, with slightly slower performance. Why isn't an index scan
> being used, given that the exact same number of rows are at play as in my
> query on the state column? How do I index closed in a way where an index
> scan is used?
>
> CREATE INDEX closed_index ON tickets (id) WHERE closed IS NULL;
> EXPLAIN ANALYZE select title, created, closed, updated from tickets where closed IS NULL;
> Bitmap Heap Scan on tickets  (cost=824.62..33955.85 rows=50349 width=64) (actual time=10.420..56.095 rows=51537 loops=1)
>   ->  Bitmap Index Scan on closed_index  (cost=0.00..812.03 rows=50349 width=0) (actual time=6.005..6.005 rows=51537 loops=1)

Are you really concerned about 4ms ?  If this is a toy-sized test system,
please try on something resembling production, perhaps by loading production or
fake data, or perhaps on a production system within a transactions (begin; CREATE
INDEX CONCURRENTLY; explain ...; rollback).

You can see that most of the estimated cost is from the table (the index scan
accounts for only 812 of total 33955 cost units).  So I'm guessing the planner
thinks that an index scan will either 1) access the table randomly; and/or, 2)
access a large fraction of the table.

If it was just built, the first (partial/conditional/predicate/where) index
will scan table in its "physical" order (if not sequentially).

The 2nd index is going to scan table in order of ID, which I'm guessing is not
"correlated" with its physical order, so an index scan cost is computed as
accessing a larger fraction of the table (but by using an "bitmap" scan it's at
least in physical order).  In fact: 50349/17478 = ~3 tuples/page is low, so
you're accessing a large fraction of the table to return a small fraction of
its tuples.

You can check what it thinks here:
https://wiki.postgresql.org/wiki/Slow_Query_Questions#Statistics:_n_distinct.2C_MCV.2C_histogram

You could try CLUSTERing the table on ID (which requires a non-partial index)
and ANALYZEing (which might cause this and other queries to be planned and/or
perform differently).  That causes the table to be locked exclusively.  Then,
the planner knows that scanning index and returning results ordered by IDs
(which doesn't matter) will also access table in physical order (which
matters), and maybe fewer pages need to be read, too.

Justin

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Abi Noda
Thanks Justin.

The 4ms different in the examples isn't an accurate benchmark. I'm seeing about a ~20% difference over a larger sample size. And this is on a fork of the production database.

Apart from the end-performance, I'm motivated to figure out why one index results in an index scan whereas the other one does not.

I didn't mention this in my original email but I've separately tested dropping the `state` index, running VACUUM FULL on the table, then recreating both indexes. The result was the same where querying on state produced an index scan whereas closed produced a bitmap scan.

Andrew's email and Michael's follow-up has me curious because it suggests I'm running into a issue specific to indexing on IS NULL, @Justin what do you think of this?

In the meantime Justin I'll investigate some more of your suggestions.

On Tue, Feb 19, 2019 at 9:37 PM Justin Pryzby <[hidden email]> wrote:
On Tue, Feb 19, 2019 at 05:10:43PM -0700, Abi Noda wrote:
> I have a table as defined below. The table contains 1,027,616 rows, 50,349
> of which have state='open' and closed IS NULL. Since closed IS NULL for all
> rows where state='open', I want to remove the unnecessary state column.
>
> CREATE TABLE tickets (
>   id bigserial primary key,
>   state character varying,
>   closed timestamp,
...
> );
>
> CREATE INDEX  "state_index" ON "tickets" ("state") WHERE ((state)::text =
> 'open'::text));
>
> As part of the process of removing the state column, I am trying to index
> the closed column so I can achieve equal query performance (index scan) as
> when I query on the state column as shown below:
>
> EXPLAIN ANALYZE select title, created, closed, updated from tickets where state = 'open';
> Index Scan using state_index on tickets  (cost=0.29..23430.20 rows=50349 width=64) (actual time=17.221..52.110 rows=51533 loops=1)
>
> However, when I index the closed column, a bitmap scan is used instead of
> an index scan, with slightly slower performance. Why isn't an index scan
> being used, given that the exact same number of rows are at play as in my
> query on the state column? How do I index closed in a way where an index
> scan is used?
>
> CREATE INDEX closed_index ON tickets (id) WHERE closed IS NULL;
> EXPLAIN ANALYZE select title, created, closed, updated from tickets where closed IS NULL;
> Bitmap Heap Scan on tickets  (cost=824.62..33955.85 rows=50349 width=64) (actual time=10.420..56.095 rows=51537 loops=1)
>   ->  Bitmap Index Scan on closed_index  (cost=0.00..812.03 rows=50349 width=0) (actual time=6.005..6.005 rows=51537 loops=1)

Are you really concerned about 4ms ?  If this is a toy-sized test system,
please try on something resembling production, perhaps by loading production or
fake data, or perhaps on a production system within a transactions (begin; CREATE
INDEX CONCURRENTLY; explain ...; rollback).

You can see that most of the estimated cost is from the table (the index scan
accounts for only 812 of total 33955 cost units).  So I'm guessing the planner
thinks that an index scan will either 1) access the table randomly; and/or, 2)
access a large fraction of the table.

If it was just built, the first (partial/conditional/predicate/where) index
will scan table in its "physical" order (if not sequentially).

The 2nd index is going to scan table in order of ID, which I'm guessing is not
"correlated" with its physical order, so an index scan cost is computed as
accessing a larger fraction of the table (but by using an "bitmap" scan it's at
least in physical order).  In fact: 50349/17478 = ~3 tuples/page is low, so
you're accessing a large fraction of the table to return a small fraction of
its tuples.

You can check what it thinks here:
https://wiki.postgresql.org/wiki/Slow_Query_Questions#Statistics:_n_distinct.2C_MCV.2C_histogram

You could try CLUSTERing the table on ID (which requires a non-partial index)
and ANALYZEing (which might cause this and other queries to be planned and/or
perform differently).  That causes the table to be locked exclusively.  Then,
the planner knows that scanning index and returning results ordered by IDs
(which doesn't matter) will also access table in physical order (which
matters), and maybe fewer pages need to be read, too.

Justin
Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Justin Pryzby
In reply to this post by Michael Lewis
On Tue, Feb 19, 2019 at 09:29:46PM -0700, Michael Lewis wrote:

> On Tue, Feb 19, 2019, 8:00 PM Andrew Gierth <[hidden email]> wrote:
>
> > >>>>> "Abi" == Abi Noda <[hidden email]> writes:
> >  Abi> However, when I index the closed column, a bitmap scan is used
> >  Abi> instead of an index scan, with slightly slower performance. Why
> >  Abi> isn't an index scan being used, given that the exact same number
> >  Abi> of rows are at play as in my query on the state column?
> >
> > Most likely difference is the correlation estimate for the conditions.
> > The cost of an index scan includes a factor based on how well correlated
> > the physical position of rows is with the index order, because this
> > affects the number of random seeks in the scan. But for nulls this
> > estimate cannot be performed, and bitmapscan is cheaper than plain
> > indexscan on poorly correlated data.
>
> Does this imply that the optimizer would always prefer the bitmapscan
> rather than index scan even if random page cost = 1, aka sequential cost,
> when the correlation is unknown like a null? Or only when it thinks random
> access is more expensive by some significant factor?

No; for one, since for a bitmap scan, the heap scan can't begin until the index
scan is done, so there's a high(er) initial cost.

Otherwise bitmap scan could always be used and all access could be ordered
(even if not sequential).

Justin

Reply | Threaded
Open this post in threaded view
|

Re: Why isn't an index scan being used?

Jeff Janes
In reply to this post by Abi Noda

On Tue, Feb 19, 2019 at 11:59 PM Abi Noda <[hidden email]> wrote:
Thanks Justin.

The 4ms different in the examples isn't an accurate benchmark. I'm seeing about a ~20% difference over a larger sample size. And this is on a fork of the production database.

Please show the execution plans from that larger sample, if that is the one that is most relevant.

You can "set enable_bitmapscan = off" to get rid of the bitmap scan in order to see the estimated cost and actual performance of the next-best plan (which will probably the regular index scan).

Cheers,

Jeff