Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Hi, I'm still working on it, but, unfortunately, I didn't have much time to work with it well enough that there would be something that could be shown. Now I am trying to sort out the problems that I drew attention to in the previous letter. -- Regards, Alena Rybakina Postgres Professional
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Well, I don't have a detailed plan either. In principle it shouldn't be
that hard, I think - examine_variable is loading the statistics, so it
could apply the same null_frac correction, just like nulltestsel would
do a bit later.
The main question is how to pass the information to examine_variable. It
doesn't get the SpecialJoinInfo (which is what nulltestsel used), so
we'd need to invent something new ... add a new argument?
Sorry I didn't answer right away, I could adapt the last version of the
patch [2] to the current idea, but so far I have implemented
it only for the situation where we save the number of zero values in
SpecialJoinInfo variable.
I'm starting to look for different functions scalararraysel_containment,
boolvarsel and I try to find some bad cases for current problem,
when I can fix in similar way it in those functions. But I'm not sure
about different ones functions:
(mergejoinscansel, estimate_num_groups, estimate_hash_bucket_stats,
get_restriction_variable, get_join_variables).
The examine_variable function is also called in them, and even though
there is no being outer join in them
(the absence of a SpecialJoinInfo variable), I can't think of similar
cases, when we have such problem caused by the same reasons.
The code passes all regression tests and I found no deterioration in
cardinality prediction for queries from [1], except for one:
EXPLAIN ANALYZE
SELECT * FROM large FULL JOIN small ON (large.id = small.id)
WHERE (large.a IS NULL);
MASTER:
*QUERY PLAN
---
Merge Full Join (cost=127921.69..299941.59 rows=56503
width=16)(actual time=795.092..795.094 rows=0 loops=1)
Merge Cond: (small.id = large.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 100
-> Sort (cost=158.51..164.16 rows=2260 width=8)
(actualtime=0.038..0.046 rows=100 loops=1)
Sort Key: small.id
Sort Method: quicksort Memory: 29kB
-> Seq Scan on small (cost=0.00..32.60 rows=2260
width=8)(actual time=0.013..0.022 rows=100 loops=1) -> Materialize
(cost=127763.19..132763.44 rows=150 width=8)(actual
time=363.016..649.103 rows=100 loops=1) -> Sort
(cost=127763.19..130263.31 rows=150 width=8)(actual
time=363.012..481.480 rows=100 loops=1)
Sort Key: large.id
Sort Method: external merge Disk: 17664kB
-> Seq Scan on large (cost=0.00..14425.50
rows=150width=8) (actual time=0.009..111.166 rows=100 loops=1)
Planning Time: 0.124 ms
Execution Time: 797.139 ms
(15 rows)*
With patch:
*QUERY PLAN
--
Hash Full Join (cost=3.25..18179.25 rows=00 width=16)
(actualtime=261.480..261.482 rows=0 loops=1)
Hash Cond: (large.id = small.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=100
width=8)(actual time=0.006..92.827 rows=100 loops=1) -> Hash
(cost=2.00..2.00 rows=100 width=8) (actualtime=0.032..0.034 rows=100
loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100
width=8)(actual time=0.008..0.015 rows=100 loops=1)
Planning Time: 0.151 ms
Execution Time: 261.529 ms
(10 rows)
[1]
https://www.mail-archive.com/pgsql-hackers@lists.postgresql.org/msg146044.html
[2]
https://www.postgresql.org/message-id/148ff8f1-067b-1409-c754-af6117de9b7d%40yandex.ru
Unfortunately, I found that my previous change leads to a big error in
predicting selectivity.
I will investigate this case in more detail and try to find a solution
(I wrote the code and query below).
// unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
if (nd1 != nd2)
{
selec /= Max(nd1, nd2);
*unmatched_frac = abs(nd1 - nd2) * 1.0 / Max(nd1, nd2);
}
else
{
selec /= nd2;
*unmatched_frac = 0.0;
}
postgres=# explain analyze select * from large l1 inner join large l2 on
l1.a is null where l1.a <100;
MASTER:
QUERY PLAN
Nested Loop (cost=1000.00..35058.43 rows=100 width=16) (actual
time=91.846..93.622 rows=0 loops=1)
-> Gather (cost=1000.00..10633.43 rows=1 width=8) (actual
time=91.844..93.619 rows=0 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Parallel Seq Scan on large l1 (cost=0.00..9633.33 rows=1
width=8) (actual time=86.153..86.154 rows=0 loops=3)
Filter: ((a IS NULL) AND (a < 100))
Rows Removed by Filter: 33
-> Seq Scan on large l2 (cost=0.00..14425.00 rows=100 width=8)
(never executed)
Planning Time: 0.299 ms
Execution Time: 93.689 ms
(1
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
On 7/8/23 10:29, Alena Rybakina wrote: > >> Well, one option would be to modify all selectivity functions to do >> something like the patch does for nulltestsel(). That seems a bit >> cumbersome because why should those places care about maybe running on >> the outer side of a join, or what? For code in extensions this would be >> particularly problematic, I think. > Agree. I would say that we can try it if nothing else works out. >> So what I was thinking about doing this in a way that'd make this >> automatic, without having to modify the selectivity functions. >> >> Option (3) is very simple - examine_variable would simply adjust the >> statistics by tweaking the null_frac field, when looking at variables on >> the outer side of the join. But it has issues when estimating multiple >> conditions. >> >> Imagine t1 has 1M rows, and we want to estimate >> >> SELECT * FROM t1 LEFT JOIN t2 ON (t1.id = t2.id) >> WHERE ((t2.a=1) AND (t2.b=1)) >> >> but only 50% of the t1 rows has a match in t2. Assume each of the t2 >> conditions matches 100% rows in the table. With the correction, this >> means 50% selectivity for each condition. And if we combine them the >> usual way, it's 0.5 * 0.5 = 0.25. >> >> But we know all the rows in the "matching" part match the condition, so >> the correct selectivity should be 0.5. >> >> In a way, this is just another case of estimation issues due to the >> assumption of independence. >> FWIW, I used "AND" in the example for simplicity, but that'd probably be >> pushed to the baserel level. There'd need to be OR to keep it at the >> join level, but the overall issue is the same, I think. >> >> Also, this entirely ignores extended statistics - I have no idea how we >> might tweak those in (3). > > I understood the idea - it is very similar to what is implemented in the > current patch. > > But I don't understand how to do it in the examine_variable function, to > be honest. > Well, I don't have a detailed plan either. In principle it shouldn't be that hard, I think - examine_variable is loading the statistics, so it could apply the same null_frac correction, just like nulltestsel would do a bit later. The main question is how to pass the information to examine_variable. It doesn't get the SpecialJoinInfo (which is what nulltestsel used), so we'd need to invent something new ... add a new argument? >> But (4) was suggesting we could improve this essentially by treating the >> join as two distinct sets of rows >> >> - the inner join result >> >> - rows without match on the outer side >> >> For the inner part, we would do estimates as now (using the regular >> per-column statistics). If we knew the conditions match 100% rows, we'd >> still get 100% when the conditions are combined. >> >> For the second part of the join we know the outer side is just NULLs in >> all columns, and that'd make the estimation much simpler for most >> clauses. We'd just need to have "fake" statistics with null_frac=1.0 and >> that's it. >> >> And then we'd just combine these two selectivities. If we know the inner >> side is 50% and all rows match the conditions, and no rows in the other >> 50% match, the selectivity is 50%. >> >> inner_part * inner_sel + outer_part * outer_sel = 0.5 * 1.0 + 0.0 = 0.5 >> >> Now, we still have issues with independence assumption in each of these >> parts separately. But that's OK, I think. >> >> I think (4) could be implemented by doing the current estimation for the >> inner part, and by tweaking examine_variable in the "outer" part in a >> way similar to (3). Except that it just sets null_frac=1.0 everywhere. >> >> For (4) we don't need to tweak those at all, >> because for inner part we can just apply them as is, and for outer part >> it's irrelevant because everything is NULL. > I like this idea the most) I'll try to start with this and implement the > patch. Good to hear. >> I hope this makes more sense. If not, let me know and I'll try to >> explain it better. > > Thank you for your explanation) > > I will unsubscribe soon based on the results or if I have any questions. > OK -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Well, one option would be to modify all selectivity functions to do something like the patch does for nulltestsel(). That seems a bit cumbersome because why should those places care about maybe running on the outer side of a join, or what? For code in extensions this would be particularly problematic, I think. Agree. I would say that we can try it if nothing else works out. So what I was thinking about doing this in a way that'd make this automatic, without having to modify the selectivity functions. Option (3) is very simple - examine_variable would simply adjust the statistics by tweaking the null_frac field, when looking at variables on the outer side of the join. But it has issues when estimating multiple conditions. Imagine t1 has 1M rows, and we want to estimate SELECT * FROM t1 LEFT JOIN t2 ON (t1.id = t2.id) WHERE ((t2.a=1) AND (t2.b=1)) but only 50% of the t1 rows has a match in t2. Assume each of the t2 conditions matches 100% rows in the table. With the correction, this means 50% selectivity for each condition. And if we combine them the usual way, it's 0.5 * 0.5 = 0.25. But we know all the rows in the "matching" part match the condition, so the correct selectivity should be 0.5. In a way, this is just another case of estimation issues due to the assumption of independence. FWIW, I used "AND" in the example for simplicity, but that'd probably be pushed to the baserel level. There'd need to be OR to keep it at the join level, but the overall issue is the same, I think. Also, this entirely ignores extended statistics - I have no idea how we might tweak those in (3). I understood the idea - it is very similar to what is implemented in the current patch. But I don't understand how to do it in the examine_variable function, to be honest. But (4) was suggesting we could improve this essentially by treating the join as two distinct sets of rows - the inner join result - rows without match on the outer side For the inner part, we would do estimates as now (using the regular per-column statistics). If we knew the conditions match 100% rows, we'd still get 100% when the conditions are combined. For the second part of the join we know the outer side is just NULLs in all columns, and that'd make the estimation much simpler for most clauses. We'd just need to have "fake" statistics with null_frac=1.0 and that's it. And then we'd just combine these two selectivities. If we know the inner side is 50% and all rows match the conditions, and no rows in the other 50% match, the selectivity is 50%. inner_part * inner_sel + outer_part * outer_sel = 0.5 * 1.0 + 0.0 = 0.5 Now, we still have issues with independence assumption in each of these parts separately. But that's OK, I think. I think (4) could be implemented by doing the current estimation for the inner part, and by tweaking examine_variable in the "outer" part in a way similar to (3). Except that it just sets null_frac=1.0 everywhere. For (4) we don't need to tweak those at all, because for inner part we can just apply them as is, and for outer part it's irrelevant because everything is NULL. I like this idea the most) I'll try to start with this and implement the patch. I hope this makes more sense. If not, let me know and I'll try to explain it better. Thank you for your explanation) I will unsubscribe soon based on the results or if I have any questions. -- Regards, Alena Rybakina Postgres Professional
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
On 7/6/23 15:51, Alena Rybakina wrote:
> Hi, all!
>
> On 26.06.2023 12:22, Andrey Lepikhov wrote:
>> On 24/6/2023 17:23, Tomas Vondra wrote:
>>> I really hope what I just wrote makes at least a little bit of sense.
>> Throw in one more example:
>>
>> SELECT i AS id INTO l FROM generate_series(1,10) i;
>> CREATE TABLE r (id int8, v text);
>> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
>> ANALYZE l,r;
>> EXPLAIN ANALYZE
>> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
>>
>> Here you can see the same kind of underestimation:
>> Hash Left Join (... rows=500 width=14) (... rows=9 ...)
>>
>> So the eqjoinsel_unmatch_left() function should be modified for the
>> case where nd1>
>>
>> Unfortunately, this patch could not fix the cardinality calculation in
>> this request, I'll try to look and figure out what is missing here.
>
> I tried to fix the cardinality score in the query above by changing:
>
> diff --git a/src/backend/utils/adt/selfuncs.c
> b/src/backend/utils/adt/selfuncs.c
> index 8e18aa1dd2b..40901836146 100644
> --- a/src/backend/utils/adt/selfuncs.c
> +++ b/src/backend/utils/adt/selfuncs.c
> @@ -2604,11 +2604,16 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
> * if we're calculating fraction of NULLs or fraction of
> unmatched rows.
> */
> // unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
> - if (nd1 > nd2)
> + if (nd1 != nd2)
> {
> - selec /= nd1;
> - *unmatched_frac = (nd1 - nd2) * 1.0 / nd1;
> + selec /= Max(nd1, nd2);
> + *unmatched_frac = abs(nd1 - nd2) * 1.0 /
> Max(nd1, nd2);
> }
> + /*if (nd1 > nd2)
> + {
> + selec /= nd1;
> + *unmatched_frac = nd1 - nd2 * 1.0 / nd1;
> + }*/
> else
> {
> selec /= nd2;
>
> and it worked:
>
> SELECT i AS id INTO l FROM generate_series(1,10) i;
> CREATE TABLE r (id int8, v text);
> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
> ANALYZE l,r;
> EXPLAIN ANALYZE
> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
> ERROR: relation "l" already exists
> ERROR: relation "r" already exists
> INSERT 0 2
> ANALYZE
> QUERY
> PLAN
> ---
> Hash Left Join (cost=1.09..1944.13 rows=8 width=14) (actual
> time=0.152..84.184 rows=9 loops=1)
> Hash Cond: (l.id = r.id)
> Filter: (r.v IS NULL)
> Rows Removed by Filter: 2
> -> Seq Scan on l (cost=0.00..1443.00 rows=10 width=4) (actual
> time=0.040..27.635 rows=10 loops=1)
> -> Hash (cost=1.04..1.04 rows=4 width=10) (actual time=0.020..0.022
> rows=4 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 9kB
> -> Seq Scan on r (cost=0.00..1.04 rows=4 width=10) (actual
> time=0.009..0.011 rows=4 loops=1)
> Planning Time: 0.954 ms
> Execution Time: 92.309 ms
> (10 rows)
>
> It looks too simple and I suspect that I might have missed something
> somewhere, but so far I haven't found any examples of queries where it
> doesn't work.
>
> I didn't see it breaking anything in the examples from my previous
> letter [1].
>
I think it's correct. Or at least it doesn't break anything my patch
didn't already break. My patch was simply written for one specific
query, so it didn't consider the option that the nd1 and nd2 values
might be in the opposite direction ...
> 1.
> https://www.postgresql.org/message-id/7af1464e-2e24-cfb1-b6d4-1544757f8cfa%40yandex.ru
>
>
> Unfortunately, I can't understand your idea from point 4, please explain it?
>
> The good thing is this helps even for IS NULL checks on non-join-key
> columns (where we don't switch to an antijoin), but there's a couple
> things that I dislike ...
>
> 1) It's not restricted to outer joins or anything like that (this is
> mostly just my laziness / interest in one particular query, but also
> something the outer-join-aware patch might help with).
>
> 2) We probably don't want to pass this kind of information through
> sjinfo. That was the simplest thing for an experimental patch, but I
> suspect it's not the only piece of information we may need to pass to
> the lower levels of estimation code.
>
> 3) I kinda doubt we actually want to move this responsibility (to
> consider fraction of unmatched rows) to the low-level estimation
> routines (e.g. nulltestsel and various others). AFAICS this just
> "introduces NULLs" into the relation, so maybe we could "adjust" the
> attribute statistics (in examine_variable?) by inflating null_frac and
> modifying the other frequencies in MCV/histogram.
>
> 4) But I'm not
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Hi, all!
On 26.06.2023 12:22, Andrey Lepikhov wrote:
On 24/6/2023 17:23, Tomas Vondra wrote:
I really hope what I just wrote makes at least a little bit of sense.
Throw in one more example:
SELECT i AS id INTO l FROM generate_series(1,10) i;
CREATE TABLE r (id int8, v text);
INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
ANALYZE l,r;
EXPLAIN ANALYZE
SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
Here you can see the same kind of underestimation:
Hash Left Join (... rows=500 width=14) (... rows=9 ...)
So the eqjoinsel_unmatch_left() function should be modified for the
case where nd1
Unfortunately, this patch could not fix the cardinality calculation in
this request, I'll try to look and figure out what is missing here.
I tried to fix the cardinality score in the query above by changing:
diff --git a/src/backend/utils/adt/selfuncs.c
b/src/backend/utils/adt/selfuncs.c
index 8e18aa1dd2b..40901836146 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2604,11 +2604,16 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
* if we're calculating fraction of NULLs or fraction
of unmatched rows.
*/
// unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
- if (nd1 > nd2)
+ if (nd1 != nd2)
{
- selec /= nd1;
- *unmatched_frac = (nd1 - nd2) * 1.0 / nd1;
+ selec /= Max(nd1, nd2);
+ *unmatched_frac = abs(nd1 - nd2) * 1.0 /
Max(nd1, nd2);
}
+ /*if (nd1 > nd2)
+ {
+ selec /= nd1;
+ *unmatched_frac = nd1 - nd2 * 1.0 / nd1;
+ }*/
else
{
selec /= nd2;
and it worked:
SELECT i AS id INTO l FROM generate_series(1,10) i;
CREATE TABLE r (id int8, v text);
INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
ANALYZE l,r;
EXPLAIN ANALYZE
SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
ERROR: relation "l" already exists
ERROR: relation "r" already exists
INSERT 0 2
ANALYZE
QUERY PLAN
---
Hash Left Join (cost=1.09..1944.13 rows=8 width=14) (actual
time=0.152..84.184 rows=9 loops=1)
Hash Cond: (l.id = r.id)
Filter: (r.v IS NULL)
Rows Removed by Filter: 2
-> Seq Scan on l (cost=0.00..1443.00 rows=10 width=4) (actual
time=0.040..27.635 rows=10 loops=1)
-> Hash (cost=1.04..1.04 rows=4 width=10) (actual
time=0.020..0.022 rows=4 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
-> Seq Scan on r (cost=0.00..1.04 rows=4 width=10) (actual
time=0.009..0.011 rows=4 loops=1)
Planning Time: 0.954 ms
Execution Time: 92.309 ms
(10 rows)
It looks too simple and I suspect that I might have missed something
somewhere, but so far I haven't found any examples of queries where it
doesn't work.
I didn't see it breaking anything in the examples from my previous
letter [1].
1.
https://www.postgresql.org/message-id/7af1464e-2e24-cfb1-b6d4-1544757f8cfa%40yandex.ru
Unfortunately, I can't understand your idea from point 4, please explain it?
The good thing is this helps even for IS NULL checks on non-join-key
columns (where we don't switch to an antijoin), but there's a couple
things that I dislike ...
1) It's not restricted to outer joins or anything like that (this is
mostly just my laziness / interest in one particular query, but also
something the outer-join-aware patch might help with).
2) We probably don't want to pass this kind of information through
sjinfo. That was the simplest thing for an experimental patch, but I
suspect it's not the only piece of information we may need to pass to
the lower levels of estimation code.
3) I kinda doubt we actually want to move this responsibility (to
consider fraction of unmatched rows) to the low-level estimation
routines (e.g. nulltestsel and various others). AFAICS this just
"introduces NULLs" into the relation, so maybe we could "adjust" the
attribute statistics (in examine_variable?) by inflating null_frac and
modifying the other frequencies in MCV/histogram.
4) But I'm not sure we actually want to do that in these low-level
selectivity functions. The outer join essentially produces output with
two subsets - one with matches on the outer side, one without them. But
the side without matches has NULLs in all columns. In a way, we know
exactly how are these columns correlated - if we do the usual estimation
(even with the null_frac adjusted), we just throw this information away.
And when there's a lot of rows without a match, that seems bad.
--
Regards,
Alena Rybakina
Postgres Professional
From 54a24390f1137a77c9755a875774a75ae8
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
On 6/26/23 20:15, Alena Rybakina wrote:
> Hi, all!
>
> On 24.06.2023 14:23, Tomas Vondra wrote:
>> On 6/24/23 02:08, Tom Lane wrote:
>>> Tomas Vondra writes:
The problem is that the selectivity for "IS NULL" is estimated using the
table-level statistics. But the LEFT JOIN entirely breaks the idea that
the null_frac has anything to do with NULLs in the join result.
>>> Right.
>>>
I wonder how to improve this, say by adjusting the IS NULL selectivity
when we know to operate on the outer side of the join. We're able to
do this for antijoins, so maybe we could do that here, somehow?
>>> This mess is part of the long-term plan around the work I've been doing
>>> on outer-join-aware Vars. We now have infrastructure that can let
>>> the estimator routines see "oh, this Var isn't directly from a scan
>>> of its table, it's been passed through a potentially-nulling outer
>>> join --- and I can see which one". I don't have more than vague ideas
>>> about what happens next, but that is clearly an essential step on the
>>> road to doing better.
>>>
>> I was wondering if that work on outer-join-aware Vars could help with
>> this, but I wasn't following it very closely. I agree the ability to
>> check if the Var could be NULL due to an outer join seems useful, as it
>> says whether applying raw attribute statistics makes sense or not.
>>
>> I was thinking about what to do for the case when that's not possible,
>> i.e. when the Var refers to nullable side of the join. Knowing that this
>> is happening is clearly not enough - we need to know how many new NULLs
>> are "injected" into the join result, and "communicate" that to the
>> estimation routines.
>>
>> Attached is a very ugly experimental patch doing that, and with it the
>> estimate changes to this:
>>
>> QUERY PLAN
>> --
>>Hash Left Join (cost=3.25..18179.88 rows=00 width=16)
>>(actual time=0.528..596.151 rows=00 loops=1)
>> Hash Cond: (large.id = small.id)
>> Filter: ((small.id IS NULL) OR
>> (large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
>> Rows Removed by Filter: 100
>> -> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
>> (actual time=0.069..176.138 rows=100 loops=1)
>> -> Hash (cost=2.00..2.00 rows=100 width=8)
>>(actual time=0.371..0.373 rows=100 loops=1)
>>Buckets: 1024 Batches: 1 Memory Usage: 12kB
>>-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
>> (actual time=0.032..0.146 rows=100 loops=1)
>>Planning Time: 3.845 ms
>>Execution Time: 712.405 ms
>> (10 rows)
>>
>> Seems nice, but. The patch is pretty ugly, I don't claim it works for
>> other queries or that this is exactly what we should do. It calculates
>> "unmatched frequency" next to eqjoinsel_inner, stashes that info into
>> sjinfo and the estimator (nulltestsel) then uses that to adjust the
>> nullfrac it gets from the statistics.
>>
>> The good thing is this helps even for IS NULL checks on non-join-key
>> columns (where we don't switch to an antijoin), but there's a couple
>> things that I dislike ...
>>
>> 1) It's not restricted to outer joins or anything like that (this is
>> mostly just my laziness / interest in one particular query, but also
>> something the outer-join-aware patch might help with).
>>
>> 2) We probably don't want to pass this kind of information through
>> sjinfo. That was the simplest thing for an experimental patch, but I
>> suspect it's not the only piece of information we may need to pass to
>> the lower levels of estimation code.
>>
>> 3) I kinda doubt we actually want to move this responsibility (to
>> consider fraction of unmatched rows) to the low-level estimation
>> routines (e.g. nulltestsel and various others). AFAICS this just
>> "introduces NULLs" into the relation, so maybe we could "adjust" the
>> attribute statistics (in examine_variable?) by inflating null_frac and
>> modifying the other frequencies in MCV/histogram.
>>
>> 4) But I'm not sure we actually want to do that in these low-level
>> selectivity functions. The outer join essentially produces output with
>> two subsets - one with matches on the outer side, one without them. But
>> the side without matches has NULLs in all columns. In a way, we know
>> exactly how are these columns correlated - if we do the usual estimation
>> (even with the null_frac adjusted), we just throw this information away.
>> And when there's a lot of rows without a match, that seems bad.
>>
>> So maybe we should split the join estimate into two parts, one for each
>> subset of the join result. One for the rows with a match (and then we
>> can just do what we do now, with the attribute stats we already have).
>> And one for the "unmatched part" where we know the values on the outer
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Hi, all!
On 24.06.2023 14:23, Tomas Vondra wrote:
On 6/24/23 02:08, Tom Lane wrote:
Tomas Vondra writes:
The problem is that the selectivity for "IS NULL" is estimated using the
table-level statistics. But the LEFT JOIN entirely breaks the idea that
the null_frac has anything to do with NULLs in the join result.
Right.
I wonder how to improve this, say by adjusting the IS NULL selectivity
when we know to operate on the outer side of the join. We're able to
do this for antijoins, so maybe we could do that here, somehow?
This mess is part of the long-term plan around the work I've been doing
on outer-join-aware Vars. We now have infrastructure that can let
the estimator routines see "oh, this Var isn't directly from a scan
of its table, it's been passed through a potentially-nulling outer
join --- and I can see which one". I don't have more than vague ideas
about what happens next, but that is clearly an essential step on the
road to doing better.
I was wondering if that work on outer-join-aware Vars could help with
this, but I wasn't following it very closely. I agree the ability to
check if the Var could be NULL due to an outer join seems useful, as it
says whether applying raw attribute statistics makes sense or not.
I was thinking about what to do for the case when that's not possible,
i.e. when the Var refers to nullable side of the join. Knowing that this
is happening is clearly not enough - we need to know how many new NULLs
are "injected" into the join result, and "communicate" that to the
estimation routines.
Attached is a very ugly experimental patch doing that, and with it the
estimate changes to this:
QUERY PLAN
--
Hash Left Join (cost=3.25..18179.88 rows=00 width=16)
(actual time=0.528..596.151 rows=00 loops=1)
Hash Cond: (large.id = small.id)
Filter: ((small.id IS NULL) OR
(large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
(actual time=0.069..176.138 rows=100 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8)
(actual time=0.371..0.373 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.032..0.146 rows=100 loops=1)
Planning Time: 3.845 ms
Execution Time: 712.405 ms
(10 rows)
Seems nice, but. The patch is pretty ugly, I don't claim it works for
other queries or that this is exactly what we should do. It calculates
"unmatched frequency" next to eqjoinsel_inner, stashes that info into
sjinfo and the estimator (nulltestsel) then uses that to adjust the
nullfrac it gets from the statistics.
The good thing is this helps even for IS NULL checks on non-join-key
columns (where we don't switch to an antijoin), but there's a couple
things that I dislike ...
1) It's not restricted to outer joins or anything like that (this is
mostly just my laziness / interest in one particular query, but also
something the outer-join-aware patch might help with).
2) We probably don't want to pass this kind of information through
sjinfo. That was the simplest thing for an experimental patch, but I
suspect it's not the only piece of information we may need to pass to
the lower levels of estimation code.
3) I kinda doubt we actually want to move this responsibility (to
consider fraction of unmatched rows) to the low-level estimation
routines (e.g. nulltestsel and various others). AFAICS this just
"introduces NULLs" into the relation, so maybe we could "adjust" the
attribute statistics (in examine_variable?) by inflating null_frac and
modifying the other frequencies in MCV/histogram.
4) But I'm not sure we actually want to do that in these low-level
selectivity functions. The outer join essentially produces output with
two subsets - one with matches on the outer side, one without them. But
the side without matches has NULLs in all columns. In a way, we know
exactly how are these columns correlated - if we do the usual estimation
(even with the null_frac adjusted), we just throw this information away.
And when there's a lot of rows without a match, that seems bad.
So maybe we should split the join estimate into two parts, one for each
subset of the join result. One for the rows with a match (and then we
can just do what we do now, with the attribute stats we already have).
And one for the "unmatched part" where we know the values on the outer
side are NULL (and then we can easily "fake" stats with null_frac=1.0).
I really hope what I just wrote makes at least a little bit of sense.
regards
I am also interested in this problem.
I did some refactoring of the source code in the patch, moved the
calculation of unmatched_fraction to e
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
On 24/6/2023 17:23, Tomas Vondra wrote: I really hope what I just wrote makes at least a little bit of sense. Throw in one more example: SELECT i AS id INTO l FROM generate_series(1,10) i; CREATE TABLE r (id int8, v text); INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f'); ANALYZE l,r; EXPLAIN ANALYZE SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL; Here you can see the same kind of underestimation: Hash Left Join (... rows=500 width=14) (... rows=9 ...) So the eqjoinsel_unmatch_left() function should be modified for the case where nd1 -- regards, Andrey Lepikhov Postgres Professional
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
On 6/24/23 02:08, Tom Lane wrote:
> Tomas Vondra writes:
>> The problem is that the selectivity for "IS NULL" is estimated using the
>> table-level statistics. But the LEFT JOIN entirely breaks the idea that
>> the null_frac has anything to do with NULLs in the join result.
>
> Right.
>
>> I wonder how to improve this, say by adjusting the IS NULL selectivity
>> when we know to operate on the outer side of the join. We're able to
>> do this for antijoins, so maybe we could do that here, somehow?
>
> This mess is part of the long-term plan around the work I've been doing
> on outer-join-aware Vars. We now have infrastructure that can let
> the estimator routines see "oh, this Var isn't directly from a scan
> of its table, it's been passed through a potentially-nulling outer
> join --- and I can see which one". I don't have more than vague ideas
> about what happens next, but that is clearly an essential step on the
> road to doing better.
>
I was wondering if that work on outer-join-aware Vars could help with
this, but I wasn't following it very closely. I agree the ability to
check if the Var could be NULL due to an outer join seems useful, as it
says whether applying raw attribute statistics makes sense or not.
I was thinking about what to do for the case when that's not possible,
i.e. when the Var refers to nullable side of the join. Knowing that this
is happening is clearly not enough - we need to know how many new NULLs
are "injected" into the join result, and "communicate" that to the
estimation routines.
Attached is a very ugly experimental patch doing that, and with it the
estimate changes to this:
QUERY PLAN
--
Hash Left Join (cost=3.25..18179.88 rows=00 width=16)
(actual time=0.528..596.151 rows=00 loops=1)
Hash Cond: (large.id = small.id)
Filter: ((small.id IS NULL) OR
(large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
(actual time=0.069..176.138 rows=100 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8)
(actual time=0.371..0.373 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.032..0.146 rows=100 loops=1)
Planning Time: 3.845 ms
Execution Time: 712.405 ms
(10 rows)
Seems nice, but. The patch is pretty ugly, I don't claim it works for
other queries or that this is exactly what we should do. It calculates
"unmatched frequency" next to eqjoinsel_inner, stashes that info into
sjinfo and the estimator (nulltestsel) then uses that to adjust the
nullfrac it gets from the statistics.
The good thing is this helps even for IS NULL checks on non-join-key
columns (where we don't switch to an antijoin), but there's a couple
things that I dislike ...
1) It's not restricted to outer joins or anything like that (this is
mostly just my laziness / interest in one particular query, but also
something the outer-join-aware patch might help with).
2) We probably don't want to pass this kind of information through
sjinfo. That was the simplest thing for an experimental patch, but I
suspect it's not the only piece of information we may need to pass to
the lower levels of estimation code.
3) I kinda doubt we actually want to move this responsibility (to
consider fraction of unmatched rows) to the low-level estimation
routines (e.g. nulltestsel and various others). AFAICS this just
"introduces NULLs" into the relation, so maybe we could "adjust" the
attribute statistics (in examine_variable?) by inflating null_frac and
modifying the other frequencies in MCV/histogram.
4) But I'm not sure we actually want to do that in these low-level
selectivity functions. The outer join essentially produces output with
two subsets - one with matches on the outer side, one without them. But
the side without matches has NULLs in all columns. In a way, we know
exactly how are these columns correlated - if we do the usual estimation
(even with the null_frac adjusted), we just throw this information away.
And when there's a lot of rows without a match, that seems bad.
So maybe we should split the join estimate into two parts, one for each
subset of the join result. One for the rows with a match (and then we
can just do what we do now, with the attribute stats we already have).
And one for the "unmatched part" where we know the values on the outer
side are NULL (and then we can easily "fake" stats with null_frac=1.0).
I really hope what I just wrote makes at least a little bit of sense.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Companydiff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
in
Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
Tomas Vondra writes: > The problem is that the selectivity for "IS NULL" is estimated using the > table-level statistics. But the LEFT JOIN entirely breaks the idea that > the null_frac has anything to do with NULLs in the join result. Right. > I wonder how to improve this, say by adjusting the IS NULL selectivity > when we know to operate on the outer side of the join. We're able to > do this for antijoins, so maybe we could do that here, somehow? This mess is part of the long-term plan around the work I've been doing on outer-join-aware Vars. We now have infrastructure that can let the estimator routines see "oh, this Var isn't directly from a scan of its table, it's been passed through a potentially-nulling outer join --- and I can see which one". I don't have more than vague ideas about what happens next, but that is clearly an essential step on the road to doing better. regards, tom lane
Problems with estimating OR conditions, IS NULL on LEFT JOINs
Hi,
I ran into a pretty terrible case of LEFT JOIN estimate, resulting in
pretty arbitrary underestimate. The query is pretty trivial, nothing
overly complex, and the more I think about it the more I think this is
a fairly fundamental flaw in how we estimate this type of joins.
Imagine you have two trivial tables:
CREATE TABLE large (id INT, a INT);
INSERT INTO large SELECT i, i FROM generate_series(1,100) s(i);
CREATE TABLE small (id INT, b INT);
INSERT INTO small SELECT i, i FROM generate_series(1,100) s(i);
The business meaning may be that "large" stores orders and "small" is
for events related to tiny fraction of the large table (e.g. returns).
And let's do a couple simple LEFT JOIN queries, adding conditions to it.
Let's start with no condition at all:
EXPLAIN ANALYZE
SELECT * FROM large LEFT JOIN small ON (large.id = small.id)
QUERY PLAN
--
Hash Left Join (cost=3.25..18179.25 rows=100 width=16)
(actual time=0.069..550.290 rows=100 loops=1)
Hash Cond: (large.id = small.id)
-> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
(actual time=0.010..174.056 rows=100 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual time=0.052...
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8) ...
Planning Time: 0.291 ms
Execution Time: 663.551 ms
(8 rows)
So great, this estimate is perfect. Now, let's add IS NULL condition on
the small table, to find rows without a match (e.g. orders that were not
returned):
EXPLAIN ANALYZE
SELECT * FROM large LEFT JOIN small ON (large.id = small.id)
WHERE (small.id IS NULL);
QUERY PLAN
--
Hash Anti Join (cost=3.25..27052.36 rows=00 width=16)
(actual time=0.071..544.568 rows=00 loops=1)
Hash Cond: (large.id = small.id)
-> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
(actual time=0.015..166.019 rows=100 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual time=0.051...
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8) ...
Planning Time: 0.260 ms
Execution Time: 658.379 ms
(8 rows)
Also very accurate, great! Now let's do a condition on the large table
instead, filtering some the rows:
EXPLAIN ANALYZE
SELECT * FROM large LEFT JOIN small ON (large.id = small.id)
WHERE (large.a IN (1000, 2000, 3000, 4000, 5000));
QUERY PLAN
--
Nested Loop Left Join (cost=0.00..20684.75 rows=5 width=16)
(actual time=0.957..127.376 rows=5 loops=1)
Join Filter: (large.id = small.id)
Rows Removed by Join Filter: 500
-> Seq Scan on large (cost=0.00..20675.00 rows=5 width=8)
(actual time=0.878..127.171 rows=5 loops=1)
Filter: (a = ANY ('{1000,2000,3000,4000,5000}'::integer[]))
Rows Removed by Filter: 95
-> Materialize (cost=0.00..2.50 rows=100 width=8) ...
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8) ...
Planning Time: 0.223 ms
Execution Time: 127.407 ms
(10 rows)
Also great estimate! Surely, if we do both conditions with OR, we'll get
a decent estimate too?
EXPLAIN ANALYZE
SELECT * FROM large LEFT JOIN small ON (large.id = small.id)
WHERE (small.id IS NULL)
OR (large.a IN (1000, 2000, 3000, 4000, 5000));
QUERY PLAN
--
Hash Left Join (cost=3.25..18179.88 rows=5 width=16)
(actual time=0.073..580.827 rows=00 loops=1)
Hash Cond: (large.id = small.id)
Filter: ((small.id IS NULL) OR
(large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=100 width=8)
(actual time=0.015..166.809 rows=100 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual time=0.052...
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8) ...
Planning Time: 0.309 ms
Execution Time: 694.427 ms
(10 rows)
Well, bummer! This is pretty surprising, because if we know that clause
A produces estimate 1M and clause B estimates as 5, then it's expected
that (A OR B) should be estimated as something >= max(1M, 5). For users
running this, this has to be really surprising.
It's also quite serious, because with underestimates like this the
planner is likely to
