Re: [HACKERS] Experimental evaluation of PostgreSQL's query optimizer
On 12/22/2015 02:40 AM, Craig Ringer wrote: > On 21 December 2015 at 23:57, Viktor Leis <mailto:l...@in.tum.de>> wrote: > > > > Please have a look at Figure 6 (page 6) in > http://www.vldb.org/pvldb/vol9/p204-leis.pdf Disabling nested loop > joins without index scan (going from (a) to (b)) results in great > improvements across the board. And even more importantly, it avoids > most of the cases where queries took unreasonably long and timed > out. Basically this amounts to the being able to run the query on > PostgreSQL or not. > > > For that data, yes. But you're ignoring other important cases. Small or even > 1-element lookup tables can be one where a nestloop over a seqscan turns out > to be by far the fastest way to do the job. > This can really add up if it's deep in a subplan that's excuted repeatedly, > or if it's part of queries that get run very frequently on a busy OLTP system. Ok here's what I presume to be the extreme case: Joining a large table with a 1-entry table. create table r1 (a int not null); create table r2 (b int not null); insert into r1 select 1 from generate_series(1,100); insert into r2 values (1); analyze r1; analyze r2; set enable_mergejoin to off; set enable_nestloop to on; set enable_hashjoin to off; explain select count(*) from r1, r2 where r1.a = r2.b; \timing select count(*) from r1, r2 where r1.a = r2.b; \timing set enable_nestloop to off; set enable_hashjoin to on; explain select count(*) from r1, r2 where r1.a = r2.b; \timing select count(*) from r1, r2 where r1.a = r2.b; \timing I get 128.894ms vs. 183.724ms, i.e., a 43% slowdown for the hash join. However, let me stress that this is really the extreme case: - If the join has few matches (due to inserting a value different from 1 into r2), hash and nested loop join have pretty much the same performance. - If you add just one more row to r2, the hash join is faster by a similar margin. - Also if there is disk IO or network involved, I suspect that you will see no performance differences. There are many difficult tradeoffs in any query optimizer, but I do not think picking nested loops where a hash join can be used is one of those. To me this seems more like a self-inflicted wound. -- Viktor Leis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Experimental evaluation of PostgreSQL's query optimizer
Am 21.12.2015 um 15:42 schrieb Tom Lane: > Viktor Leis writes: >> I think it would be a good start to distinguish between nested loop >> joins with and without a index. > > We do. > >> In my opinion, the latter should simply NEVER be chosen. > > So, if you're given a query with a non-equality join condition > that doesn't match any index on either table, you think the planner > should just fail? This is not realistic. Certainly nestloop with > inner seqscan is likely to be slow, but that's already reflected > in the cost estimates. You are right that for non-equality joins there is no alternative, so nested loop is obviously the right choice. However, that does not make the selection of nested loop join in cases where a hash join would be possible a good choice. Please have a look at Figure 6 (page 6) in http://www.vldb.org/pvldb/vol9/p204-leis.pdf Disabling nested loop joins without index scan (going from (a) to (b)) results in great improvements across the board. And even more importantly, it avoids most of the cases where queries took unreasonably long and timed out. Basically this amounts to the being able to run the query on PostgreSQL or not. The cost model does not save you because the estimated cardinality is close to 1. Also note that a hash join is fast too if the estimate is correct. Picking nested loop join in these situations is very risky but there is practically no upside for this decision. -- Viktor Leis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Experimental evaluation of PostgreSQL's query optimizer
Am 21.12.2015 um 09:22 schrieb Albe Laurenz: > Viktor Leis wrote: >> We have recently performed an experimental evaluation of PostgreSQL's >> query optimizer. For example, we measured the contributions of >> cardinality estimation and the cost model on the overall query >> performance. You can download the resulting paper here: >> http://www.vldb.org/pvldb/vol9/p204-leis.pdf >> >> Some findings: >> 1. Perhaps unsurprisingly, we found that cardinality >> estimation is the biggest problem in query optimization. >> 2. The quality of Postgres' cardinality estimates is not generally worse >> than that of the major commerical systems. >> 3. It seems to me that one obvious way to avoid many bad situations >> would be to disable nested loop joins when the inner relation is NOT >> an index scan. >> >> I hope this will be of interest to some of you. > > I have read the paper with great interest, and I have some comments. > > - The paper mentions that the "Join Order Benchmark" has high cross-table > correlation, and this correlation is responsible for bad cardinality > estimates that cause bad plans with all RDBMS. > Wouldn't it be interesting to do the same experiment with a different > real-word data sets to see if that is indeed typical and not an > idiosyncrasy of that specific benchmark? The IMDB data set certainly has lots of correlations in comparison with synthetic benchmarks like TPC-H. I do not claim that IMDB is representative (whatever that means). But it is certainly a data set that people are putting into a database and run join queries on it. It would indeed be very interesting to do similar experiments with other real-world data sets. We had to come up with our own queries because you seldom find combinations of public relational data sets with non-trivial OLAP queries. > - The paper suggests that sampling the base tables is preferable to > using statistics because it gives better estimates, but I think that that > is only a win with long running, complicated, data warehouse style queries. > For the typical OLTP query it would incur intolerable planning times. > Any ideas on that? I agree that sampling is not suitable for most OLTP queries. (One hack would be to run the optimizer without sampling and check if the estimated cost is high and reoptimize with sampling.) In data warehouse settings, I've seen suggestions to increase default_statistics_target to a large value, which in my experience results in extremely large planning times. Sampling could be a more precise alternative. > - From my experience in tuning SQL queries I can confirm your one finding, > namely that bad cardinality estimates are the prime source for bad > plan choices. > Perhaps it would be valuable to start thinking about statistics for > inter-table correlation. What about something as "simple" as a factor > per (joinable) attribute pair that approximates the total row count > of a join on these attributes, divided by the planner's estimate? I think your suggestion amounts to caching the cardinalities of all two-way joins. One major issue is that for a query like select * from r1, r2 where r1.x = r2.y and r1.a = ? and r2.b; it depends on the specific values of r1.a and r2.b whether there is any (anti-)correlation. And obviously one cannot store correction factors for each value of a and b. > - I also can corroborate your finding that nested loop joins are often > harmful, particularly when the inner loop is a sequential scan. > One of the first things I do when investigating bad performance of a query > whose plan has a nestend loop join is to set enable_nestloop to "off" > and see if that makes a difference, and it often does. > Maybe it would be a win to bias the planner against nested loop joins. > This is dreaming, but it might be nice to have some number as to how > reliable a certain estimate is, which is high if the estimate is, say, > derived from a single filter on a base table and sinks as more conditions > are involved or numbers pulled out of thin air. I think it would be a good start to distinguish between nested loop joins with and without a index. In my opinion, the latter should simply NEVER be chosen. -- Viktor Leis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Experimental evaluation of PostgreSQL's query optimizer
Hi, We have recently performed an experimental evaluation of PostgreSQL's query optimizer. For example, we measured the contributions of cardinality estimation and the cost model on the overall query performance. You can download the resulting paper here: http://www.vldb.org/pvldb/vol9/p204-leis.pdf Some findings: 1. Perhaps unsurprisingly, we found that cardinality estimation is the biggest problem in query optimization. 2. The quality of Postgres' cardinality estimates is not generally worse than that of the major commerical systems. 3. It seems to me that one obvious way to avoid many bad situations would be to disable nested loop joins when the inner relation is NOT an index scan. I hope this will be of interest to some of you. -- Viktor Leis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
