No Index-Only Scan on Partial Index

On Tue, Oct 1, 2013 at 5:35 PM, David E. Wheeler <david@justatheory.com> wrote:

Hackers,

I was trying to figure out why a query was not doing an index-only scan on a partial index, when Josh Berkus pointed to this issue, reported by Merlin Moncure:

/messages/by-id/CAHyXU0x1OGao48WajAfUsbXqkUDLf=_6ho6hLMB8DSfkWdaVVw@mail.gmail.com

In short, the planner needs the column from the where clause included in the index to decide it can do an index-only scan. This test case demonstrates the truth of this finding:

CREATE TABLE try (
id INT NOT NULL,
label TEXT NOT NULL,
active BOOLEAN DEFAULT TRUE
);

INSERT INTO try
SELECT i
, (ARRAY['foo','bar','baz','wig'])[floor((random()*4))::int + 1]
, (i % 100) = 0
FROM generate_series(1, 100000) i;

VACUUM FREEZE TRY;

CREATE INDEX idx_try_active ON try(id) WHERE active;

-- Does a bitmap heap scan.
EXPLAIN (ANALYZE, FORMAT YAML)
SELECT id FROM try WHERE active;

DROP INDEX idx_try_active;
CREATE INDEX idx_try_active ON try(label, id, active) WHERE active;

-- Does an index-only scan.
EXPLAIN (ANALYZE, FORMAT YAML)
SELECT id FROM try WHERE active;

DROP TABLE try;

The first query does a bitmap heap scan, but after the index that includes the active column is added, it does an index-only scan.

However, this does not quite match my case. In my case, I'm using an immutable function call in the index where clause:

CREATE INDEX idx_try_active ON try(id, upper_inf(irange)) WHERE upper_inf(irange);

I am unable to get the planner do to an index-only scan with this index no matter what I do. Here’s the full test case:

CREATE TABLE try (
id INT NOT NULL,
label TEXT NOT NULL,
irange INT4RANGE NOT NULL
);

INSERT INTO try
SELECT i
, (ARRAY['foo','bar','baz','wig'])[floor((random()*4))::int + 1]
, int4range(1, CASE WHEN random() < 0.01 THEN NULL ELSE 2 END)
FROM generate_series(1, 100000) i;

VACUUM FREEZE TRY;

CREATE INDEX idx_try_active ON try(id) WHERE upper_inf(irange);

-- Does a bitmap heap scan.
EXPLAIN (ANALYZE, FORMAT YAML)
SELECT id FROM try WHERE upper_inf(irange);

DROP INDEX idx_try_active;
CREATE INDEX idx_try_active ON try(label, id, upper_inf(irange)) WHERE upper_inf(irange);

-- Also does a bitmap heap scan.
EXPLAIN (ANALYZE, FORMAT YAML)
SELECT id FROM try WHERE upper_inf(irange);

DROP TABLE try;

So is there something about using a function in a conditional index that prevents index-only scans? Tested on 9.2 and 9.3, BTW.

I don't think it has anything to do with the conditional index -- it's
the functional based. For some reason postgres always wants to post
filter (note the filter step below):

postgres=# create index on try(upper_inf(irange));
CREATE INDEX
Time: 12.001 ms
postgres=# explain select * from try where upper_inf(irange);
QUERY PLAN
-------------------------------------------------------------------------------
Index Scan using try_upper_inf_idx on try (cost=0.00..9.25 rows=33 width=40)
Index Cond: (upper_inf(irange) = true)
Filter: upper_inf(irange)

merlin

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

On Oct 1, 2013, at 3:56 PM, Merlin Moncure <mmoncure@gmail.com> wrote:

I don't think it has anything to do with the conditional index -- it's
the functional based. For some reason postgres always wants to post
filter (note the filter step below):

postgres=# create index on try(upper_inf(irange));
CREATE INDEX
Time: 12.001 ms
postgres=# explain select * from try where upper_inf(irange);
QUERY PLAN
-------------------------------------------------------------------------------
Index Scan using try_upper_inf_idx on try (cost=0.00..9.25 rows=33 width=40)
Index Cond: (upper_inf(irange) = true)
Filter: upper_inf(irange)

Hrm. I get a seq scan for that query:

create index on try(upper_inf(irange));
explain select * from try where upper_inf(irange);
QUERY PLAN
-----------------------------------------------------------
Seq Scan on try (cost=0.00..1887.00 rows=33333 width=68)
Filter: upper_inf(irange)

True also if I just select the irange. Is the filter the issue, here?

Best,

David

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

On Tuesday, October 1, 2013, David E. Wheeler <david@justatheory.com> wrote:

On Oct 1, 2013, at 3:56 PM, Merlin Moncure <mmoncure@gmail.com> wrote:

I don't think it has anything to do with the conditional index -- it's
the functional based. For some reason postgres always wants to post
filter (note the filter step below):

postgres=# create index on try(upper_inf(irange));
CREATE INDEX
Time: 12.001 ms
postgres=# explain select * from try where upper_inf(irange);
QUERY PLAN

-------------------------------------------------------------------------------

Index Scan using try_upper_inf_idx on try (cost=0.00..9.25 rows=33

width=40)

Index Cond: (upper_inf(irange) = true)
Filter: upper_inf(irange)

Hrm. I get a seq scan for that query:

create index on try(upper_inf(irange));
explain select * from try where upper_inf(irange);
QUERY PLAN
-----------------------------------------------------------
Seq Scan on try (cost=0.00..1887.00 rows=33333 width=68)
Filter: upper_inf(irange)

True also if I just select the irange. Is the filter the issue, here?

Turn off seq scan...

merlin

On Oct 2, 2013, at 5:07 AM, Merlin Moncure <mmoncure@gmail.com> wrote:

Hrm. I get a seq scan for that query:

create index on try(upper_inf(irange));
explain select * from try where upper_inf(irange);
QUERY PLAN
-----------------------------------------------------------
Seq Scan on try (cost=0.00..1887.00 rows=33333 width=68)
Filter: upper_inf(irange)

True also if I just select the irange. Is the filter the issue, here?

Turn off seq scan...

That rewards me with a bitmap heap scan:

EXPLAIN select * from try where upper_inf(irange);

QUERY PLAN
--------------------------------------------------------------------------------------
Bitmap Heap Scan on try (cost=935.63..2197.63 rows=33333 width=68)
Filter: upper_inf(irange)
-> Bitmap Index Scan on try_upper_inf_idx (cost=0.00..927.30 rows=50000 width=0)
Index Cond: (upper_inf(irange) = true)

But anyway, I still don’t understand why, if the function used to store the value is immutable (as upper_inf() is), why Postgres doesn't do an index scan. Is this something that could be improved in the planner?

Thanks,

David

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

David,

But anyway, I still don’t understand why, if the function used to store the value is immutable (as upper_inf() is), why Postgres doesn't do an index scan. Is this something that could be improved in the planner?

Yes. This is clearly a TODO.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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

On Oct 3, 2013, at 10:50 AM, Josh Berkus <josh@agliodbs.com> wrote:

But anyway, I still don’t understand why, if the function used to store the value is immutable (as upper_inf() is), why Postgres doesn't do an index scan. Is this something that could be improved in the planner?

Yes. This is clearly a TODO.

Added it here:

https://wiki.postgresql.org/wiki/Todo#Optimizer_.2F_Executor

Teach the planner how to better use partial indexes for index-only scans
• /messages/by-id/25141.1345072858@sss.pgh.pa.us
• /messages/by-id/79C7D74D-59B0-4D97-A5E5-55553EF299AA@justatheory.com

Best,

David

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