Обсуждение: SELECT DISTINCT never uses an index?
Take the following table as an example: CREATE TABLE grue (id SERIAL PRIMARY KEY,size VARCHAR(255) ); CREATE INDEX grue_size ON grue(size); Now insert approximately eleventy jillion rows, but ensure that there are only about 20 distinct values for size. SELECT DISTINCT size FROM grue; Always does a seq scan on Postgres 9.5.2. (Yes, I know we're a patch behind, the upgrade is on the schedule) on Ubuntu 14. I would expect it to be possible, and significantly more efficient to do an index scan for that query. Is this a bug, an optimization that is simply waiting for someone to take the time to implement, or is there some underlying reason why this isn't possible that I'm not seeing. And, yes, I know that's not a normalized table and that properly normalizing it makes the problem disappear. And yes, this is repeatable (I'm working with about 6 tables with similar structure that all exhibit the same behavior) and yes I've done ANALYZE and VACUUM and the behavior doesn't change. -- Bill Moran
On Thu, Jul 7, 2016 at 4:56 PM, Bill Moran <wmoran@potentialtech.com> wrote: > Take the following table as an example: > > CREATE TABLE grue ( > id SERIAL PRIMARY KEY, > size VARCHAR(255) > ); > CREATE INDEX grue_size ON grue(size); > > Now insert approximately eleventy jillion rows, but ensure > that there are only about 20 distinct values for size. > > SELECT DISTINCT size FROM grue; > > Always does a seq scan on Postgres 9.5.2. (Yes, I know we're > a patch behind, the upgrade is on the schedule) on > Ubuntu 14. > > I would expect it to be possible, and significantly more > efficient to do an index scan for that query. Well, there are two possible ways to implement uniqueness: hashing and grouping. You haven't included the EXPLAIN ANALYZE output so it's hard to be sure which sort of plan you are getting, but my guess is that you are getting a HashAggregate. So basically what it's doing is: 1. Read a row. 2. Check the value in the hash table to see if we've seen it already. 3. If not, add it. 4. Go to step 1. If you've got to visit the whole table anyway, doing it in sequential order is smart, so this plan sounds reasonably good. The alternative worth considering is presumably something like: GroupAggregate -> Index Only Scan on grue_size Scanning an entire index in order is pretty expensive, but it seems possible that this could be faster than the Seq Scan, especially on a table with other wide columns, because then the index might be a lot smaller than the table. Even if the index traversal generates some random I/O, if it's sufficiently smaller than the table you will still come out ahead. I'm not positive that the planner will actually consider this plan, but it seems like it should; you might be able to persuade it to do so by setting enable_hashagg=false, which would let you check whether it's actually faster. We're probably missing a few tricks on queries of this type. If the index-traversal machinery had a mechanism to skip quickly to the next distinct value, that could be used here: walk up the btree until you find a page that contains keyspace not equal to the current key, then walk back down until you find the first leaf page that contains such a value. That would potentially let you step over large chunks of the index without actually examining all the leaf pages, which for a query like this seems like it could be a big win. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Fri, Jul 8, 2016 at 9:49 AM, Robert Haas <robertmhaas@gmail.com> wrote: > On Thu, Jul 7, 2016 at 4:56 PM, Bill Moran <wmoran@potentialtech.com> wrote: >> SELECT DISTINCT size FROM grue; >> >> Always does a seq scan on Postgres 9.5.2. (Yes, I know we're >> a patch behind, the upgrade is on the schedule) on >> Ubuntu 14. >> >> I would expect it to be possible, and significantly more >> efficient to do an index scan for that query. > > [...] > > We're probably missing a few tricks on queries of this type. If the > index-traversal machinery had a mechanism to skip quickly to the next > distinct value, that could be used here: walk up the btree until you > find a page that contains keyspace not equal to the current key, then > walk back down until you find the first leaf page that contains such a > value. That would potentially let you step over large chunks of the > index without actually examining all the leaf pages, which for a query > like this seems like it could be a big win. FWIW I messed around with prototyping this idea here: https://www.postgresql.org/message-id/CADLWmXWALK8NPZqdnRQiPnrzAnic7NxYKynrkzO_vxYr8enWww@mail.gmail.com I hope to return to that and some related ideas eventually as I learn more about the relevant areas of the source code, if someone doesn't beat me to it. https://wiki.postgresql.org/wiki/Loose_indexscan shows a recursive CTE that does the same thing at a higher level. -- Thomas Munro http://www.enterprisedb.com
On 8 July 2016 at 09:49, Robert Haas <robertmhaas@gmail.com> wrote: > We're probably missing a few tricks on queries of this type. If the > index-traversal machinery had a mechanism to skip quickly to the next > distinct value, that could be used here: walk up the btree until you > find a page that contains keyspace not equal to the current key, then > walk back down until you find the first leaf page that contains such a > value. That would potentially let you step over large chunks of the > index without actually examining all the leaf pages, which for a query > like this seems like it could be a big win. Thomas Munro did take some initial steps to implementing this a few years ago: https://www.postgresql.org/message-id/CADLWmXXbTSBxP-MzJuPAYSsL_2f0iPm5VWPbCvDbVvfX93FKkw%40mail.gmail.com -- David Rowley http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services
Robert Haas <robertmhaas@gmail.com> writes:
> The alternative worth considering is presumably something like:
> GroupAggregate
> -> Index Only Scan on grue_size
> Scanning an entire index in order is pretty expensive, but it seems
> possible that this could be faster than the Seq Scan, especially on a
> table with other wide columns, because then the index might be a lot
> smaller than the table. Even if the index traversal generates some
> random I/O, if it's sufficiently smaller than the table you will still
> come out ahead. I'm not positive that the planner will actually
> consider this plan,
Of course it does. Simple example in the regression database:
regression=# explain select distinct unique1 from tenk1; QUERY PLAN
--------------------------------------------------------------------------------
------------Unique (cost=0.29..295.29 rows=10000 width=4) -> Index Only Scan using tenk1_unique1 on tenk1
(cost=0.29..270.29rows=100
00 width=4)
(2 rows)
I think though that this depends on being an IOS, with a fairly wide and
all-all-visible table, in order for the cost estimate to come out cheaper
than a seqscan. If you disable IOS then the planner's second choice is
a seqscan:
regression=# set enable_indexonlyscan to 0;
SET
regression=# explain select distinct unique1 from tenk1; QUERY PLAN
-----------------------------------------------------------------HashAggregate (cost=483.00..583.00 rows=10000
width=4) Group Key: unique1 -> Seq Scan on tenk1 (cost=0.00..458.00 rows=10000 width=4)
(3 rows)
A whole-table plain indexscan, or IOS with any significant number of heap
probes needed, is not going to be preferred over a seqscan because of the
amount of random I/O it implies.
> We're probably missing a few tricks on queries of this type. If the
> index-traversal machinery had a mechanism to skip quickly to the next
> distinct value, that could be used here:
Yeah, I suspect Bill was imagining that that sort of plan could be
used; but it requires execution machinery we have not got.
regards, tom lane