I don't really think it would be a useful plan anyway. What *would* be useful is to support HashAggregate as an implementation alternative for DISTINCT --- currently I believe we only consider that for GROUP BY. The DISTINCT planning code is fairly old and crufty and hasn't been redesigned lately.
regards, tom lane
I see this as a minor annoyance only because I can write GROUP BY instead of DISTINCT and get the speed boost. It probably annoys people trying to port applications to postgres though, forcing them to rewrite their queries.
* SELECT DISTINCT : 21442.296 ms (by default, uses an index scan) disabling index_scan => Sort + Unique : 14512.105 ms
* GROUP BY : 1793.651 ms using HashAggregate * skip index scan by function : 13.833 ms
The HashAggregate speed boost is good, but rather pathetic compared to a "skip index scan" ; but it's still worth having if updating the DISTINCT code is easy.
Note that it would also benefit UNION queries which apparently use DISTINCT internally and currently produce this : ------------------------------------------------------------------------------ explain analyze select number from ((select number from dummy) union (select number from dummy)) as foo;
Subquery Scan foo (cost=287087.62..317087.62 rows=2000000 width=4) (actual time=33068.776..35575.330 rows=255 loops=1) -> Unique (cost=287087.62..297087.62 rows=2000000 width=4) (actual time=33068.763..35574.126 rows=255 loops=1) -> Sort (cost=287087.62..292087.62 rows=2000000 width=4) (actual time=33068.757..34639.180 rows=2000000 loops=1) Sort Key: number -> Append (cost=0.00..49804.00 rows=2000000 width=4) (actual time=0.055..7412.551 rows=2000000 loops=1) -> Subquery Scan "*SELECT* 1" (cost=0.00..24902.00 rows=1000000 width=4) (actual time=0.054..3104.165 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=4) (actual time=0.051..1792.348 rows=1000000 loops=1) -> Subquery Scan "*SELECT* 2" (cost=0.00..24902.00 rows=1000000 width=4) (actual time=0.048..3034.462 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=4) (actual time=0.044..1718.682 rows=1000000 loops=1) Total runtime: 36265.662 ms ------------------------------------------------------------------------------
But could instead do this : explain analyze select number from ((select number from dummy) union all (select number from dummy)) as foo group by number;
HashAggregate (cost=74804.00..74804.00 rows=200 width=4) (actual time=10753.648..10753.890 rows=255 loops=1) -> Subquery Scan foo (cost=0.00..69804.00 rows=2000000 width=4) (actual time=0.059..8992.084 rows=2000000 loops=1) -> Append (cost=0.00..49804.00 rows=2000000 width=4) (actual time=0.055..6688.639 rows=2000000 loops=1) -> Subquery Scan "*SELECT* 1" (cost=0.00..24902.00 rows=1000000 width=4) (actual time=0.054..2749.708 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=4) (actual time=0.052..1640.427 rows=1000000 loops=1) -> Subquery Scan "*SELECT* 2" (cost=0.00..24902.00 rows=1000000 width=4) (actual time=0.038..2751.916 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=4) (actual time=0.034..1637.818 rows=1000000 loops=1) Total runtime: 10754.120 ms ------------------------------------------------------------------------------ A 3x speedup, but still a good thing to have. When I LIMIT the two subqueries to 100k rows instead of a million, the times are about equal. When I LIMIT one of the subqueries to 100k and leave the other to 1M, UNION ALL 17949.609 ms UNION + GROUP BY 6130.417 ms
Still some performance to be gained...
------------------------------------------------------------------------------ Of course it can't use a skip index scan on a subquery, but I could instead : I know it's pretty stupid to use the same table twice but it's just an example. However, if you think about table partitions and views, a "select distinct number" from a view having multiple partitions would yield this type of query, and that table partitioning seems like a hot subject lately.
let's create a dummy example view : create view dummy_view as (select * from dummy) union all (select * from dummy);
explain analyze select number from dummy_view group by number; HashAggregate (cost=74804.00..74804.00 rows=200 width=4) (actual time=10206.456..10206.713 rows=255 loops=1) -> Subquery Scan dummy_view (cost=0.00..69804.00 rows=2000000 width=4) (actual time=0.060..8431.776 rows=2000000 loops=1) -> Append (cost=0.00..49804.00 rows=2000000 width=8) (actual time=0.055..6122.125 rows=2000000 loops=1) -> Subquery Scan "*SELECT* 1" (cost=0.00..24902.00 rows=1000000 width=8) (actual time=0.054..2456.566 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=8) (actual time=0.048..1107.151 rows=1000000 loops=1) -> Subquery Scan "*SELECT* 2" (cost=0.00..24902.00 rows=1000000 width=8) (actual time=0.036..2471.748 rows=1000000 loops=1) -> Seq Scan on dummy (cost=0.00..14902.00 rows=1000000 width=8) (actual time=0.031..1104.482 rows=1000000 loops=1) Total runtime: 10206.945 ms
A smarter planner could rewrite it into this : select number from ((select distinct number from dummy) union (select distinct number from dummy)) as foo;
and notice it would index-skip-scan the two partitions (here, example with my function)
explain analyze select number from ((select sel_distinct as number from sel_distinct()) union all (select sel_distinct as number from sel_distinct())) as foo group by number; HashAggregate (cost=70.00..70.00 rows=200 width=4) (actual time=29.078..29.332 rows=255 loops=1) -> Subquery Scan foo (cost=0.00..65.00 rows=2000 width=4) (actual time=13.378..28.587 rows=510 loops=1) -> Append (cost=0.00..45.00 rows=2000 width=4) (actual time=13.373..28.003 rows=510 loops=1) -> Subquery Scan "*SELECT* 1" (cost=0.00..22.50 rows=1000 width=4) (actual time=13.373..13.902 rows=255 loops=1) -> Function Scan on sel_distinct (cost=0.00..12.50 rows=1000 width=4) (actual time=13.367..13.619 rows=255 loops=1) -> Subquery Scan "*SELECT* 2" (cost=0.00..22.50 rows=1000 width=4) (actual time=13.269..13.800 rows=255 loops=1) -> Function Scan on sel_distinct (cost=0.00..12.50 rows=1000 width=4) (actual time=13.263..13.512 rows=255 loops=1) Total runtime: 29.569 ms
So, if a query with UNION or UNION ALL+DISTINCT tries to put DISTINCT inside the subqueries and yields an index skip scan, here is a massive speedup.
You will tell me "but if the UNION ALL has 10 subqueries, planning is going to take forever !" Well not necessarily. The above query with 10 subqueries UNIONALLed then GROUPed takes : UNION : 320509.522 ms (the Sort + Unique truly becomes humongous). UNION ALL + GROUP : 54586.759 ms (you see there is already interest in rewiring DISTINCT/UNION) skip scan + UNION : 147.941 ms skip scan + UNION ALL + group : 147.313 ms
Well it would clearly be useful in this test case, where has a small number of distinct values in a large table, and an index on the column. His plpgsql function that emulates such a plan is an order of magnitude
faster than the hash aggregate plan even though it has to do entirely separate index scans for each key value.
Actually, it is more like two orders of magnitude (100x faster) : in fact the time for a seq scan is O(N rows) whereas the time for the skip index scan should be, if I'm not mistaken, something like O((N distinct values) * (log N rows)) ; in my case there are 256 distinct values for 1M rows and a speedup of 100x, so if there were 10M rows the speedup would be like 300x (depending on the base of the log which I assume is 2). And if the skip index scan is implemented in postgres instead of in a function, it could be much, much faster...
[ shrug... ] There are an infinite number of special cases for which that claim could be made. The more we load down the planner with seldom-useful special cases, the *lower* the overall performance will be, because we'll waste cycles checking for the special cases in every case ...
In a general way, you are absolutely right... special-casing a case for a speedup of 2x for instance would be worthless... but we are considering a HUGE speedup here. And, if this mode is only used for DISTINCT and GROUP BY queries, no planning cycles will be wasted at all on queries which do not use DISTINCT nor GROUP BY.
Present state is that DISTINCT and UNION are slow with or without using the GROUP BY trick. Including the index skip scan in the planning options would only happen when appropriate cases are detected. This detection would be very fast. The index skip scan would then speed up the query so much that the additional planning cost would not matter. If there are many distinct values, so that seq scan is faster than skip scan, the query will be slow enough anyway so that the additional planning cost does not matter. The only problem cases are queries with small tables where startup time is important, but in that case the planner has stats about the number of rows in the table, and again excluding skip scan from the start would be fast.
Lateral thought : Create a new index type which only indexes one row for each value. This index would use very little space and would be very fast to update (on my table it would index only 256 values). Keep the Index Scan code and all, but use this index type when you can. This solution is less general and also has a few drawbacks.
Another thought : \d dummy Table «public.dummy» Colonne | Type | Modificateurs ---------+---------+--------------- id | integer | number | integer | Index : «dummy_idx» btree (number) «dummy_idx_2» btree (number, id) explain analyze select * from dummy where id=1;
Seq Scan on dummy (cost=0.00..17402.00 rows=1 width=8) (actual time=274.480..1076.092 rows=1 loops=1) Filter: (id = 1) Total runtime: 1076.168 ms
explain analyze select * from dummy where number between 0 and 256 and id=1; Index Scan using dummy_idx_2 on dummy (cost=0.00..6.02 rows=1 width=8) (actual time=1.449..332.020 rows=1 loops=1) Index Cond: ((number >= 0) AND (number <= 256) AND (id = 1)) Total runtime: 332.112 ms
In this case we have no index on id, but using a skip index scan, emulated by the "between" to force use of the (number,id) index, even though it must look in all the 256 possible values for number, still speeds it up by 3x. Interestingly, with only 16 distinct values, the time is quite the same. Thus, the "skip index scan" could be used in cases where there is a multicolumn index, but the WHERE misses a column.
This would not waste planning cycles because : - If the index we need exists and there is no "distinct" or "group by" without aggregate, the planner does not even consider using the skip index scan. - If the index we need does not exist, the planner only loses the cycles needed to check if there is a multicolumn index which may be used. In this case, either there is no such index, and a seq scan is chosen, which will be slow, so the time wasted for the check is negligible ; or an index is found and can be used, and the time gained by the skip index scan is well amortized.
Currently one has to carefully consider which queries will be used frequently and need indexes, and which ones are infrequent and don't justify an index (but these queries will be very slow). With the skip index scan, these less frequent queries don't always mean a seq scan. Thus people will need to create less infrequently used indexes, and will have a higher INSERT/UPDATE speed/
------------------------------------------------------------------------------------------------
The skip scan would also be a winner on this type of query which is a killer, a variant of the famous 'TOP 10' query : EXPLAIN SELECT max(id), number FROM dummy GROUP BY number; -> 2229.141 ms
Postgres uses a Seq scan + HashAggregate. Come on, we have an index btree (number, id), use it ! A simple customization on my skip scan emulation function takes 13.683 ms...
I know that Postgres does not translate max() on on indexed column to ORDER BY column DESC LIMIT 1, because it would be extremely hard to implement due to the general nature of aggregates which is a very good thing. It does not bother me because I can still write ORDER BY column DESC LIMIT 1.
Where it does bother me is if I want the highest ID from each number, which can only be expressed by SELECT max(id), number FROM dummy GROUP BY number; and not with LIMITs.
Suppose I want the first 10 higher id's for each number, which is another variant on the "killer top 10 query". I'm stuck, I cannot even use max(), I have to write a custom aggregate which would keep the 10 highest values, which would be very slow, so I have to use my function and put a LIMIT 10 instead of a LIMIT 1 in each query, along with a FOR and some other conditions to check if there are less than 10 id's for a number, etc, which more or less amounts to "select the next number, then select the associated id's". It'll still be fast a lot faster than seq scan, but it gets more and more complicated.
However I'd like to write :
select number,id from dummy ORDER BY number DESC, id DESC MULTILIMIT 50,10; The MULTILIMIT means "I want 50 numbers and 10 id's for each number." MULTILIMIT NULL,10 would mean "I want all numbers and 10 id's for each number." NULL is not mandatory, it could also be -1, a keyword or something. MULTILIMIT could simply be LIMIT too, because LIMIT takes one parameter. The OFFSET clause could also evolve accordingly.
And this would naturally use a skip index scan, and benefit a whole class of queries which have traditionnaly been difficult to get right...
Conclusion :
smarting up the DISTINCT planner has the following benefits : - speedup on DISTINCT - speedup on UNION which seems to use DISTINCT internally
index skip scan has the following benefits : - massive speedup (x100) on queries involving DISTINCT or its GROUP BY variant - same thing (x300) on UNION queries if the parser tries to rewrite the query and put the DISTINCT inside the subqueries - paves the way for a MULTILIMIT which gives an elegant, and very efficient way of expressing traditionnaly difficult queries like the "Top 10 by category" which are used quite often and give headaches to dba's. - Possibility to use a multicolumn index with a WHERE not including all left columns
index skip scan has the following drawbacks : - more complexity - additional planning time
This last drawback is in fact, limited because : - It is easy and fast to know when the index skip scan will never be used, so in most queries which won't need it, the possibility can be eliminated without wasting cycles in planning - When it is used, the performance gains are so massive that it is justified - People who use many queries where planning time is significant comparing to execution time are probably using SQL functions or prepared queries.
Enough arguments, maybe not to convince you, but to have a second thought on it ?
---------------------------------------------------------------
Side Note :
What do you think about the idea of an "UniqueSort" which would do sort+unique in one pass ? This could also be simple to code, and would also offer advantages to all queries using UNION. The sort would be faster and consume less storage space because the data size would diminish as duplicates are eliminated along the way.
---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives?
http://archives.postgresql.org