Thread
Commits
-
Clamp semijoin selectivity to be not more than inner-join selectivity.
- a314c34079cf 12.0 landed
-
BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
The Post Office <noreply@postgresql.org> — 2018-04-17T09:40:50Z
The following bug has been logged on the website: Bug reference: 15160 Logged by: Alexey Ermakov Email address: alexey.ermakov@dataegret.com PostgreSQL version: 10.3 Operating system: Linux Description: Hello, I'm wondering how planner estimates number of rows in that case: create table test_in (id int primary key); insert into test_in select id from generate_series(1,1000000) gs(id); analyze test_in; explain analyze with ids as (select id from generate_series(1,1000) gs(id) limit 200) select * from test_in where id in (select id from ids); ------------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=6.93..139.79 rows=200 width=4) (actual time=0.129..0.400 rows=200 loops=1) CTE ids -> Limit (cost=0.00..2.00 rows=200 width=4) (actual time=0.050..0.066 rows=200 loops=1) -> Function Scan on generate_series gs (cost=0.00..10.00 rows=1000 width=4) (actual time=0.050..0.057 rows=200 loops=1) -> HashAggregate (cost=4.50..6.50 rows=200 width=4) (actual time=0.117..0.133 rows=200 loops=1) Group Key: ids.id -> CTE Scan on ids (cost=0.00..4.00 rows=200 width=4) (actual time=0.051..0.086 rows=200 loops=1) -> Index Only Scan using test_in_pkey on test_in (cost=0.42..0.66 rows=1 width=4) (actual time=0.001..0.001 rows=1 loops=200) Index Cond: (id = ids.id) Heap Fetches: 200 Planning time: 0.128 ms Execution time: 0.434 ms explain analyze with ids as (select id from generate_series(1,1000) gs(id) limit 201) select * from test_in where id in (select id from ids); ------------------------------------------------------------------------------------------------------------------------------------- Nested Loop (cost=6.96..132.78 rows=500000 width=4) (actual time=0.119..0.389 rows=201 loops=1) CTE ids -> Limit (cost=0.00..2.01 rows=201 width=4) (actual time=0.048..0.064 rows=201 loops=1) -> Function Scan on generate_series gs (cost=0.00..10.00 rows=1000 width=4) (actual time=0.048..0.056 rows=201 loops=1) -> HashAggregate (cost=4.52..6.52 rows=200 width=4) (actual time=0.113..0.130 rows=201 loops=1) Group Key: ids.id -> CTE Scan on ids (cost=0.00..4.02 rows=201 width=4) (actual time=0.049..0.083 rows=201 loops=1) -> Index Only Scan using test_in_pkey on test_in (cost=0.42..0.66 rows=1 width=4) (actual time=0.001..0.001 rows=1 loops=201) Index Cond: (id = ids.id) Heap Fetches: 201 Planning time: 0.068 ms Execution time: 0.417 ms please note that it first example we got correct estimate of total number of rows - 200, but in last one where CTE returned 201 rows (instead of 200) we estimate total number of rows as 500000 (half of the table test_in). which is way off and could lead to non optimal plan and poor performance. I have same estimate if I replace IN clause with equivalent EXISTS subquery; normal join estimates number of rows fine (but it's not equivalent in general case when table_in.id is not unique). reproduced in 9.5, 9.6 and 10. interesting thing that in postgresql 10 threshold is 200 rows but in previous version it's 199. I suspect selectivity 0.5 we somehow get inside compute_semi_anti_join_factors function in costsize.c but I'm not sure. Thanks, Alexey Ermakov -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Tom Lane <tgl@sss.pgh.pa.us> — 2018-04-17T14:15:38Z
=?utf-8?q?PG_Bug_reporting_form?= <noreply@postgresql.org> writes: > I'm wondering how planner estimates number of rows in that case: See eqjoinsel_semi, particularly the change in behavior when it thinks nd2 is or is not a default estimate. Given the lack of statistics about the output of the WITH clause, it's hard to see how we'd ever get trustworthy estimates here. I think the fact that your first example yields an accurate estimate is mostly luck. regards, tom lane
-
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Maxim Boguk <maxim.boguk@gmail.com> — 2018-09-25T11:24:39Z
On Tue, Apr 17, 2018 at 5:15 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > =?utf-8?q?PG_Bug_reporting_form?= <noreply@postgresql.org> writes: > > I'm wondering how planner estimates number of rows in that case: > > See eqjoinsel_semi, particularly the change in behavior when it thinks > nd2 is or is not a default estimate. > > Given the lack of statistics about the output of the WITH clause, > it's hard to see how we'd ever get trustworthy estimates here. > I think the fact that your first example yields an accurate > estimate is mostly luck. > > regards, tom lane > > There are similar issue without CTE which look pretty weird: Good case with LIMIT 199 and adequate estimation: hh=# explain SELECT * FROM resume WHERE resume_id IN (select id from generate_series(1, 1000) gs(id) LIMIT 199); QUERY PLAN --------------------------------------------------------------------------------------------------- Nested Loop (cost=21.53..108.98 rows=199 width=519) -> Unique (cost=21.42..21.62 rows=199 width=4) -> Sort (cost=21.42..21.52 rows=199 width=4) Sort Key: gs.id -> Limit (cost=0.00..9.95 rows=199 width=4) -> Function Scan on generate_series gs (cost=0.00..50.00 rows=1000 width=4) -> Index Scan using resume_pk on resume (cost=0.11..0.39 rows=1 width=519) Index Cond: (resume_id = gs.id) Very bad case with awful estimation (only difference LIMIT 200 vs LIMIT 199): explain SELECT * FROM resume WHERE resume_id IN (select id from generate_series(1, 1000) gs(id) LIMIT 200); QUERY PLAN --------------------------------------------------------------------------------------------------- Nested Loop (cost=21.64..109.53 rows=45860504 width=519) -> Unique (cost=21.53..21.73 rows=200 width=4) -> Sort (cost=21.53..21.63 rows=200 width=4) Sort Key: gs.id -> Limit (cost=0.00..10.00 rows=200 width=4) -> Function Scan on generate_series gs (cost=0.00..50.00 rows=1000 width=4) -> Index Scan using resume_pk on resume (cost=0.11..0.39 rows=1 width=519) Index Cond: (resume_id = gs.id) It's not a problem by itself but once you start using this query with more joined tables - a lot bad things happens because 5 orders of magnitude error in selectivity estimation. PS: in reality it forces us to use not more than 199 LIMIT in complex joins for batch operations or the database start generate funny plans. Regards, Maxim -- Maxim Boguk Senior Postgresql DBA https://dataegret.com/ Phone RU: +7 985 433 0000 Phone UA: +380 99 143 0000 Phone AU: +61 45 218 5678 LinkedIn: http://www.linkedin.com/pub/maksym-boguk/80/b99/b1b Skype: maxim.boguk "Доктор, вы мне советовали так не делать, но почему мне по-прежнему больно когда я так делаю ещё раз?" -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Tom Lane <tgl@sss.pgh.pa.us> — 2018-09-25T20:11:15Z
Maxim Boguk <maxim.boguk@gmail.com> writes: > On Tue, Apr 17, 2018 at 5:15 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: >> =?utf-8?q?PG_Bug_reporting_form?= <noreply@postgresql.org> writes: >>> I'm wondering how planner estimates number of rows in that case: >> See eqjoinsel_semi, particularly the change in behavior when it thinks >> nd2 is or is not a default estimate. > There are similar issue without CTE which look pretty weird: Yeah, this is exactly the same case as Alexey's: as soon as eqjoinsel_semi decides it's dealing with a default ndistinct estimate, it chickens out and delivers a very middle-of-the-road selectivity (0.5, it looks like). It's somewhat luck that the non-default path is giving you an accurate estimate, but certainly there's no surprise in the default case being way off. I don't particularly want to make that logic more aggressive about assuming it's calculating something real. The existing behavior was put in to fix a clear bug in the other direction, see https://www.postgresql.org/message-id/flat/201104112029.14738.uwe%40oss4u.com However, while looking at this I had a bit of an epiphany. The inner-join selectivity in the same cases is pretty much on-target, so is there any way we could factor that in? Yes, there is: the size of the semijoin output could not be more than the output of a plain inner join of the same two relations. So it'd be legitimate to clamp our selectivity estimate for the semijoin case to make it not more than the inner-join estimate. A little bit of hacking later, I have the attached patch. The bulk of the patch is just refactoring to avoid repetitive information lookup when we call both eqjoinsel_semi and eqjoinsel_inner. The actual change is just to clamp eqjoinsel_semi's result, like this: /* * We should never estimate the output of a semijoin to be more * rows than the equivalent inner join; it's obviously impossible * for that to happen. The former is N1 * Psemi while the latter * is N1 * N2 * Pinner, so we may clamp Psemi <= N2 * Pinner. * Doing this is worthwhile because of the shakier estimation * rules we use in eqjoinsel_semi, particularly in cases where it * has to punt entirely. */ selec = Min(selec, inner_rel->rows * selec_inner); That makes the funny behavior go away in both test cases shown in this thread. I find one plan change in the regression tests, but it looks reasonable enough (and checking the actual row counts shows that the estimate moved closer to reality, not further away). Now, there's a certain amount of garbage-in-garbage-out to this: if for some reason the innerjoin selectivity is way off, this could do more to hurt the semijoin estimate than to help it. But I think that generally the semijoin numbers are much less reliable than the innerjoin numbers, so mostly it ought to be no-change or a win. I'll queue this up for review in the next CF. regards, tom lane -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Melanie Plageman <melanieplageman@gmail.com> — 2018-11-16T00:51:45Z
The following review has been posted through the commitfest application: make installcheck-world: tested, passed Implements feature: tested, passed Spec compliant: not tested Documentation: not tested This patch applies cleanly and works for the case described in the original email. All existing regression tests pass with the addition of the explain plan update included in the patch. I could not devise an example in which the previous method of calculating selectivity would have produced a better estimate. However, one question I have after thinking through the optimization is the following: This new selectivity calculation (targeted at semi-joins though in eqjoinsel) is: selectivity = Min(semi-join selectivity, ntuples inner * inner-join selectivity); For a join in which you do not have access to MCVs and assuming no NULLs, the inner-join selectivity used to compare to the calculated semi-join selectivity* is: selectivity = ntuples2 * 1 / max(nd1, nd2) = ntuples2 / max(nd1, nd2) if nd1 <= nd2: selectivity = ntuples2 / nd2 else: selectivity = ntuples2 / nd1 To summarize: Selectivity Type | if nd1 <= nd2 | if nd1 > nd2 | ----------------------------------|----------------|----------------- inner-join selectivity * ntuples2 | ntuples2 / nd2 | ntuples2 / nd1 | semi-join selectivity | 1 | nd2 / nd1 | Notice that ntuples2 >= nd2 so no matter what nd1 and nd2 are: inner-join selectivity * ntuples >= semi-join selectivity So, it seems like, unless you are missing NDVs of one of the sides of the join, inner join selectivity can never be less than semi-join selectivity. If this is true, why not use the default NDVs number in the semi-join selectivity calculation? * based on these summaries of the formulas for calculating selectivity inner-join selectivity when you don't have access to MCVs and assuming no NULLs is ~ 1 / max(nd1,nd2) if either nd1 or nd2 was default, nd[1,2] = min(ntuples[1,2], 200) semi-join selectivity when you don't have access to MCVs and assuming no NULLs is 0.5 when either nd1 or nd2 is default when neither are default if nd2 < 0 || nd1 <= nd2 1 else nd2/nd1 If there is a reason to keep the existing formula, then I have an additional question about the proposed selectivity calculation: selec = Min(selec, nd2 * selec_inner); When would it be incorrect to instead multiply by inner side NDVs? Besides the actual logic of the code added, Ekta and I did a code review and had some feedback on the structure and clarity of the code and comments. In the function eqjoinsel_semi, on line 2759 of the patched, rebased code, could you not move the else condition: uncertainfrac = 0.5; Up to the top of the if statement which starts on line 2663: if (have_mcvs1 && have_mcvs2 && OidIsValid(opfuncoid)) It seems like you already know and do not further modify the value of isdefault1 and isdefault2 and could exit faster before looping through all the MCVs in this case. For the function eqjoinsel_inner, why pass in vardata1 and vardata2, as they appear not to be used? Neither are the isdefault flags. This is in the existing code, however, I thought I would ask here: In eqjoinsel_semi, on line 2691 of the patched, rebased code, Why is this the min of the number of MCVs captured and the distinct values? It seems like if clamping resulted in an NDVs that is too low (i.e. impossibly low since the number of distinct values cannot be less than the number of MCVs), then you should bump it up to at least the number of MCVs: clamped_nvalues2 = Min(sslot2->nvalues, nd2); I also found the new comment added above the new selectivity calculation to be a little bit confusing: /* * We should never estimate the output of a semijoin to be more * rows than the equivalent inner join; it's obviously impossible * for that to happen. The former is N1 * Psemi while the latter * is N1 * N2 * Pinner, so we may clamp Psemi <= N2 * Pinner. * Doing this is worthwhile because of the shakier estimation * rules we use in eqjoinsel_semi, particularly in cases where it * has to punt entirely. */ selec = Min(selec, inner_rel->rows * selec_inner); After re-reading it several times, I understood what it was doing, however, it would be ideal if somehow the relationship between selectivity and cardinality were more clear. I don't have any great ideas for additional wording, however, maybe it would help to clarify that in order to clamp the cardinality correctly, we must clamp the selectivity using this formula. Basically, specify that we are not clamping the selectivity of semi-join to the selectivity of inner join, but, rather, that we are clamping the cardinality of semi-join to consider only the matching rows of the inner side (also, if that sentence is actually not correct, then some description that avoids confusion like that would be helpful). The new status of this patch is: Waiting on Author -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Tom Lane <tgl@sss.pgh.pa.us> — 2018-11-16T16:18:41Z
Melanie Plageman <melanieplageman@gmail.com> writes: > This patch applies cleanly and works for the case described in the original > email. All existing regression tests pass with the addition of the explain plan > update included in the patch. Thanks for reviewing! > I could not devise an example in which the previous method of calculating > selectivity would have produced a better estimate. However, one question I have > after thinking through the optimization is the following: > ... > To summarize: > Selectivity Type | if nd1 <= nd2 | if nd1 > nd2 | > ----------------------------------|----------------|----------------- > inner-join selectivity * ntuples2 | ntuples2 / nd2 | ntuples2 / nd1 | > semi-join selectivity | 1 | nd2 / nd1 | Um, mumble. Those functions could be using different values of nd2 thanks to the clamping logic near the head of eqjoinsel_semi, so I'm not sure that the comparison you're making really holds. > ... why not use the default NDVs number in the semi-join selectivity > calculation? Practical experience says that it doesn't work very well; see the thread I referred to before, https://www.postgresql.org/message-id/flat/201104112029.14738.uwe@oss4u.com particularly my comment :: While I don't have your specific example to try, I did some :: experimenting with queries of this form, and I noticed that 8.4's :: heuristic in eqjoinsel_semi() was going completely nuts and estimating :: that all rows in the lefthand side have join partners (thus, no rows out :: of the antijoin). This is because it has stats for one side of the :: comparison operator but not the other side (the one with the :: sub-select). But it's taking the totally-made-up ndistinct estimate for :: the sub-select at face value. It needs to be a bit warier I think. That experience is what led to the "isdefault" checks that exist now in eqjoinsel_semi. I don't think that applying a clamp based on eqjoinsel_inner is sufficient reason to remove those sanity checks. In particular, even if the clamp removes the possibility of the semijoin estimate being too high, it doesn't do anything to prevent a too-low estimate due to using baseless numbers. > If there is a reason to keep the existing formula, then I have an additional > question about the proposed selectivity calculation: > selec = Min(selec, nd2 * selec_inner); > When would it be incorrect to instead multiply by inner side NDVs? I'm confused ... isn't that exactly what this is doing? > In the function eqjoinsel_semi, on line 2759 of the patched, rebased code, > could you not move the else condition: > uncertainfrac = 0.5; > Up to the top of the if statement which starts on line 2663: > if (have_mcvs1 && have_mcvs2 && OidIsValid(opfuncoid)) > It seems like you already know and do not further modify the value of > isdefault1 and isdefault2 and could exit faster before looping through all the > MCVs in this case. Not really, because we still need to know matchfreq1, so we still have to do all the comparisons. It's true that nmatches won't be used in this case, but I don't see that we can get any meaningful savings by not computing that. > For the function eqjoinsel_inner, why pass in vardata1 and vardata2, as they > appear not to be used? Neither are the isdefault flags. It just seemed saner to keep the parameter lists similar for eqjoinsel_inner and eqjoinsel_semi (a judgment call, I admit). In practice, since there's only one call site for eqjoinsel_inner, I'd expect it to get inlined so that there's no runtime cost anyway. > This is in the existing code, however, I thought I would ask here: > In eqjoinsel_semi, on line 2691 of the patched, rebased code, Why is this the > min of the number of MCVs captured and the distinct values? It seems like if > clamping resulted in an NDVs that is too low (i.e. impossibly low since the > number of distinct values cannot be less than the number of MCVs), then you > should bump it up to at least the number of MCVs: > clamped_nvalues2 = Min(sslot2->nvalues, nd2); No, because sslot2->nvalues is the number of distinct values that ANALYZE found in the whole table. If nd2 got clamped to less than that, it's because we have a WHERE clause that is filtering the table down to fewer rows than there are distinct values in the table, so we can be sure (at least, up to the reliability of the WHERE estimate) that not all of the recorded MCVs are going to be present in the rows being joined. We don't know which ones will be present, but it seems like a reasonable bet that the most common ones will be present. Since the list is already ordered by decreasing frequency, just taking the first N of them gets us that. You could imagine trying to refine that, say by reducing the number further to allow for some of the join input rows containing non-MCVs, but I don't see an argument for increasing it. > I also found the new comment added above the new selectivity calculation to be > a little bit confusing: > /* > * We should never estimate the output of a semijoin to be more > * rows than the equivalent inner join; it's obviously impossible > * for that to happen. The former is N1 * Psemi while the latter > * is N1 * N2 * Pinner, so we may clamp Psemi <= N2 * Pinner. > * Doing this is worthwhile because of the shakier estimation > * rules we use in eqjoinsel_semi, particularly in cases where it > * has to punt entirely. > */ > selec = Min(selec, inner_rel->rows * selec_inner); > After re-reading it several times, I understood what it > was doing, however, it would be ideal if somehow the relationship between > selectivity and cardinality were more clear. Hm. Maybe the "Psemi" and "Pinner" notation is not helpful ... would "Ssemi" and "Sinner" be better? regards, tom lane
-
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Melanie Plageman <melanieplageman@gmail.com> — 2018-11-16T18:31:47Z
Thanks for the quick responses. I've put some inline follow-up questions. On a separate note, I had one additional code clarity feedback. I felt that eqjoinsel could be reorganized a bit for readability/clarity for the reader. For example, eqjoinsel_inner uses only the AttStatsSlots up until here and then suddenly uses the original stats object and the ndvs which we passed in: else { ... double nullfrac1 = stats1 ? stats1->stanullfrac : 0.0; double nullfrac2 = stats2 ? stats2->stanullfrac : 0.0; selec = (1.0 - nullfrac1) * (1.0 - nullfrac2); if (nd1 > nd2) selec /= nd1; else selec /= nd2; } It would make the process of calculating selectivity for an equijoin more clear to the reader if the nullfraction calculation was pulled out into the main eqjoinsel function. Having a clear set of steps in eqjoinsel would be helpful. Basically, my understanding of an overview of the steps is the following: 1) get NDVs 2) get nullfrac 3) get MCVs 4) calculate selectivity Based on this assumption, I've attached a patch with a rough idea for an alternative structure that I think would be more clear to the reader. > > I could not devise an example in which the previous method of calculating > > selectivity would have produced a better estimate. However, one question > I have > > after thinking through the optimization is the following: > > ... > > To summarize: > > Selectivity Type | if nd1 <= nd2 | if nd1 > nd2 | > > ----------------------------------|----------------|----------------- > > inner-join selectivity * ntuples2 | ntuples2 / nd2 | ntuples2 / nd1 | > > semi-join selectivity | 1 | nd2 / nd1 | > > Um, mumble. Those functions could be using different values of nd2 > thanks to the clamping logic near the head of eqjoinsel_semi, so I'm > not sure that the comparison you're making really holds. > That's a good point. Taking another look at that clamping logic, I realized that I don't really understand why that clamping would be done for a semi-join and not for an inner join. It seems like for an inner join it is also true that the the nd1 cannot be greater than outer rel estimated tuples and nd2 could not be greater than inner rel estimated tuples. Also, I don't understand when vardata2->rel->rows and inner_rel->rows would be different. I thought the point of doing this clamping was that, if you have a restriction, like the predicate in this subquery select * from foo where a in (select b from bar where b > 10); your row estimate for bar and your row estimate for the rows out for that subquery would be different. However, I looked at the RelOptInfos for vardata2->rel and inner_rel for this query and it seems like they are referencing the same relation and have the same rows estimate, so I'm confused when the rows would be different. > If there is a reason to keep the existing formula, then I have an > additional > > question about the proposed selectivity calculation: > > selec = Min(selec, nd2 * selec_inner); > > When would it be incorrect to instead multiply by inner side NDVs? > > I'm confused ... isn't that exactly what this is doing? > Sorry, typo, I was asking why selec = Min(selec, nd2 * selec_inner); could not be used instead of what is in the patch selec = Min(selec, inner_rel->rows * selec_inner); Thanks, Melanie -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Tom Lane <tgl@sss.pgh.pa.us> — 2018-11-17T20:22:20Z
Melanie Plageman <melanieplageman@gmail.com> writes: > On a separate note, I had one additional code clarity feedback. I felt that > eqjoinsel could be reorganized a bit for readability/clarity for the reader. > ... > Based on this assumption, I've attached a patch with a rough idea for an > alternative structure that I think would be more clear to the reader. Hmm, that doesn't really seem like an improvement to me. As things stand, all the actual calculations are in eqjoinsel_inner/semi; eqjoinsel itself is only responsible for some preliminary information lookup that's needed in all cases. My patch expands the amount of "preliminary information" but doesn't fundamentally change that division of responsibility. It seems like what you want to do here does change that, and I don't see the value of breaking down the division. I also don't like the fact that we might calculate a value that won't be used; admittedly, it's a pretty cheap calculation so that doesn't matter much, but by the same token we'd not be saving a lot of code by moving it. > That's a good point. Taking another look at that clamping logic, I > realized that I don't really understand why that clamping would be done > for a semi-join and not for an inner join. It seems like for an inner > join it is also true that the the nd1 cannot be greater than outer rel > estimated tuples and nd2 could not be greater than inner rel estimated > tuples. The main way that eqjoinsel_inner uses those values is this bit: * We do not have MCV lists for both sides. Estimate the join * selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). This * is plausible if we assume that the join operator is strict and the * non-null values are about equally distributed: a given non-null * tuple of rel1 will join to either zero or N2*(1-nullfrac2)/nd2 rows * of rel2, so total join rows are at most * N1*(1-nullfrac1)*N2*(1-nullfrac2)/nd2 giving a join selectivity of * not more than (1-nullfrac1)*(1-nullfrac2)/nd2. In the expression N2*(1-nullfrac2)/nd2, all three values are meant to be measured across the whole of the rel2 relation; if we were to decrease nd2 to reflect the effects of earlier filtering, we'd get an incorrect selectivity. The same applies to eqjoinsel_semi's calculations about the outer rel, but *not* to the inner rel, as explained here: * We clamp nd2 to be not more than what we estimate the inner relation's * size to be. This is intuitively somewhat reasonable since obviously * there can't be more than that many distinct values coming from the * inner rel. The reason for the asymmetry (ie, that we don't clamp nd1 * likewise) is that this is the only pathway by which restriction clauses * applied to the inner rel will affect the join result size estimate, * since set_joinrel_size_estimates will multiply SEMI/ANTI selectivity by * only the outer rel's size. If we clamped nd1 we'd be double-counting * the selectivity of outer-rel restrictions. (Here, both "outer rel's size" and "inner rel's size" mean the size after earlier filtering steps.) So that's why we only clamp nd2 and only do so in eqjoinsel_semi: in the other three cases, we'd be double-counting the selectivity of earlier filters if we did that. So basically the inconsistency here comes from the fact that we define the meaning of join selectivity differently for inner and semi joins. I've occasionally wondered if that was a bad choice and we should just say that selectivity should always be calculated so that the join size is outer size times inner size times selectivity. But that would certainly not make for any less need for the selectivity estimator to do things differently for inner and semi joins, so I am not seeing much upside to changing it. > Also, I don't understand when vardata2->rel->rows and inner_rel->rows would > be different. vardata2->rel->rows is going to reflect the size (post restriction quals) of the base relation that var2 came from. inner_rel->rows will be the same if the inner side of the current join is just that one base relation; but if the inner side is a lower join of several base relations, inner_rel->rows will be the size of that join. >> I'm confused ... isn't that exactly what this is doing? > Sorry, typo, I was asking why > selec = Min(selec, nd2 * selec_inner); > could not be used instead of what is in the patch > selec = Min(selec, inner_rel->rows * selec_inner); Because the selectivity is defined as something you multiply the relation size with, not the number of distinct values within the rel. regards, tom lane -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Melanie Plageman <melanieplageman@gmail.com> — 2018-11-20T20:24:59Z
Given that you have addressed all of my feedback and that it's a pretty low-risk change, I will change the status to "ready for committer". There are a couple of minor follow-up clarifications inline that relate mostly to the questions that I asked in previous emails. I did have one other question: Has there been discussion in the past about adding a planner test extension similar to those in src/test/modules for cardinality estimation? I am imagining something that is a "soft" check that either the rows estimation that comes out of calc_joinrel_size_estimate is within an expected range (given differing estimates across machines) or that the selectivity estimate that comes out of eqjoinsel is within an expected range. The former seems relatively easy to do in a manner similar to the test_predtest extension and the latter seems like it could be done even more trivially. On Sat, Nov 17, 2018 at 12:22 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > (Here, both "outer rel's size" and "inner rel's size" mean the size after > earlier filtering steps.) So that's why we only clamp nd2 and only do so > in eqjoinsel_semi: in the other three cases, we'd be double-counting the > selectivity of earlier filters if we did that. > > I just want to make sure I am understanding what the comment is saying: So, after we calculate the selectivity for inner join, when we return from calc_joinrel_size_estimate we do this math: nrows = outer_rows * inner_rows * fkselec * jselec; and in that equation, the outer and inner rows have been adjusted to account for any restrictions on the tables, so we don't clamp the ndvs for inner join in eqjoinsel_inner. However, for semi-join, that calculation is nrows = outer_rows * fkselec * jselec; Which means that we have to adjust the rows of the inner side before we get here? > So basically the inconsistency here comes from the fact that we define > the meaning of join selectivity differently for inner and semi joins. > I've occasionally wondered if that was a bad choice and we should just > say that selectivity should always be calculated so that the join size > is outer size times inner size times selectivity. But that would > certainly not make for any less need for the selectivity estimator to > do things differently for inner and semi joins, so I am not seeing much > upside to changing it. > I see what you are saying. I got tangled up in this part of the code, so I am inclined to say that it could stand to be more clear. Selectivity is a ratio, and, even if you calculate the two sides of the ratio differently, that doesn't mean the definition of the ratio should be different. Also, I wanted to address a question you asked in an earlier email: You wrote: > Hm. Maybe the "Psemi" and "Pinner" notation is not helpful ... would > "Ssemi" and "Sinner" be better? I think Ssemi and Sinner might be more clear--mostly because we haven't used P/predicate here or in most of the other selectivity estimation comments that I read. Also, in some cases when we have super limited information and make a guess, the selectivity feels pretty detached from the join predicate. Thanks! -
Re: BUG #15160: planner overestimates number of rows in join when there are more than 200 rows coming from CTE
Tom Lane <tgl@sss.pgh.pa.us> — 2018-11-23T17:17:34Z
Melanie Plageman <melanieplageman@gmail.com> writes: > Given that you have addressed all of my feedback and that it's a pretty > low-risk change, I will change the status to "ready for committer". Thanks for reviewing! > Has there been discussion in the past about adding a planner test > extension similar to those in src/test/modules for cardinality > estimation? I am imagining something that is a "soft" check that either > the rows estimation that comes out of calc_joinrel_size_estimate is > within an expected range (given differing estimates across machines) or > that the selectivity estimate that comes out of eqjoinsel is within an > expected range. The former seems relatively easy to do in a manner > similar to the test_predtest extension and the latter seems like it > could be done even more trivially. No, I don't recall any discussion about that. The regression tests in general embody a lot of checking that the planner makes expected plan choices: obviously the cases where we do an explicit EXPLAIN do that, but even where we don't, we'd be likely to get artifacts such as varying row order if an unexpected plan were chosen. Perhaps there's a use-case for a lower-level test harness such as you suggest, but I haven't really felt a need for it. > On Sat, Nov 17, 2018 at 12:22 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: >> (Here, both "outer rel's size" and "inner rel's size" mean the size after >> earlier filtering steps.) So that's why we only clamp nd2 and only do so >> in eqjoinsel_semi: in the other three cases, we'd be double-counting the >> selectivity of earlier filters if we did that. > I just want to make sure I am understanding what the comment is saying: So, > after we calculate the selectivity for inner join, when we return from > calc_joinrel_size_estimate we do this math: > nrows = outer_rows * inner_rows * fkselec * jselec; > and in that equation, the outer and inner rows have been adjusted to account > for any restrictions on the tables, so we don't clamp the ndvs for inner > join in eqjoinsel_inner. However, for semi-join, that calculation is > nrows = outer_rows * fkselec * jselec; > Which means that we have to adjust the rows of the inner side before we get > here? Yeah. Basically the point is that if we have some WHERE clause that eliminates rows from the inner side of a semijoin, we can expect that that means the size of the semijoin result will be smaller than if the WHERE clause hadn't been there --- because some of the outer-rel rows only had matches among those excluded rows. But the equation in calc_joinrel_size_estimate provides no way to factor that in, except by adjusting the selectivity value, so that's what we do. > You wrote: >> Hm. Maybe the "Psemi" and "Pinner" notation is not helpful ... would >> "Ssemi" and "Sinner" be better? > I think Ssemi and Sinner might be more clear--mostly because we haven't used > P/predicate here or in most of the other selectivity estimation comments > that I > read. Also, in some cases when we have super limited information and make a > guess, the selectivity feels pretty detached from the join predicate. OK, thanks --- I'll have another go at writing that comment. regards, tom lane