Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qDqkH-0002bP-Pf for pgsql-hackers@arkaria.postgresql.org; Mon, 26 Jun 2023 18:15:26 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1qDqkF-00084o-Vb for pgsql-hackers@arkaria.postgresql.org; Mon, 26 Jun 2023 18:15:23 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1qDqkF-00084d-6B for pgsql-hackers@lists.postgresql.org; Mon, 26 Jun 2023 18:15:23 +0000 Received: from forward500b.mail.yandex.net ([178.154.239.144]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qDqk8-000aZZ-C4 for pgsql-hackers@lists.postgresql.org; Mon, 26 Jun 2023 18:15:21 +0000 Received: from mail-nwsmtp-smtp-production-canary-88.sas.yp-c.yandex.net (mail-nwsmtp-smtp-production-canary-88.sas.yp-c.yandex.net [IPv6:2a02:6b8:c08:1d21:0:640:c9e4:0]) by forward500b.mail.yandex.net (Yandex) with ESMTP id AC8795EB59; Mon, 26 Jun 2023 21:15:10 +0300 (MSK) Received: by mail-nwsmtp-smtp-production-canary-88.sas.yp-c.yandex.net (smtp/Yandex) with ESMTPSA id 8FPiwc0DSSw0-yJGHUmoK; Mon, 26 Jun 2023 21:15:09 +0300 X-Yandex-Fwd: 1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1687803310; bh=6A7HvddMFcX+U0vIZA4c6e9HsLE1eF8eEEisIyrQpvs=; h=In-Reply-To:Cc:Date:References:To:Subject:Message-ID:From; b=MOOEY/sQnUoiZxJI0vw0rp11bqYMQ3XpJ3GSdIFLazbgNdeRSlqAVId/WBZIAN6fc rZfokzjaPP53j6yV0s9miNYJ/z8/SMiyh7dhM7berqUUCqQtpxa8Ee0nYxFci+4jJy y9ltB2cyND1z8Dv3IesecoYV9LgxlAWJZKUIGZqw= Authentication-Results: mail-nwsmtp-smtp-production-canary-88.sas.yp-c.yandex.net; dkim=pass header.i=@yandex.ru Content-Type: multipart/mixed; boundary="------------tDPHaou5Vqx0hiWSaufqV0MH" Message-ID: <7af1464e-2e24-cfb1-b6d4-1544757f8cfa@yandex.ru> Date: Mon, 26 Jun 2023 21:15:07 +0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Subject: Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs To: Andrey Lepikhov , Tomas Vondra , Tom Lane Cc: PostgreSQL Hackers References: <52b55b53-420a-722c-adbd-706922fc059b@enterprisedb.com> <104950.1687565314@sss.pgh.pa.us> <6dce55f4-e8f6-8e8e-b2af-b45ccff13598@enterprisedb.com> <6ed3a29e-b4b9-e4b6-e8a1-b1d7d00bbd88@postgrespro.ru> Content-Language: en-US From: Alena Rybakina In-Reply-To: <6ed3a29e-b4b9-e4b6-e8a1-b1d7d00bbd88@postgrespro.ru> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------tDPHaou5Vqx0hiWSaufqV0MH Content-Type: multipart/alternative; boundary="------------eb5sqqwo9sbaiu1sjOKLH8Sl" --------------eb5sqqwo9sbaiu1sjOKLH8Sl Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit 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=999900 width=16) > (actual time=0.528..596.151 rows=999900 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=1000000 width=8) > (actual time=0.069..176.138 rows=1000000 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 eqjoinsel_inner. I wrote myself in this commit as a co-author, if you don't mind, and I'm going to continue working. 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,100000) 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=99999 ...) > > 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. *postgres=# SELECT i AS id INTO l FROM generate_series(1,100000) 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; SELECT 100000 CREATE TABLE INSERT 0 2 ANALYZE                                                   QUERY PLAN ---------------------------------------------------------------------------------------------------------------  Hash Left Join  (cost=1.04..1819.07 rows=1 width=14) (actual time=0.143..114.792 rows=99999 loops=1)    Hash Cond: (l.id = r.id)    Filter: (r.v IS NULL)    Rows Removed by Filter: 1    ->  Seq Scan on l  (cost=0.00..1443.00 rows=100000 width=4) (actual time=0.027..35.278 rows=100000 loops=1)    ->  Hash  (cost=1.02..1.02 rows=2 width=10) (actual time=0.014..0.017 rows=2 loops=1)          Buckets: 1024  Batches: 1  Memory Usage: 9kB          ->  Seq Scan on r  (cost=0.00..1.02 rows=2 width=10) (actual time=0.005..0.007 rows=2 loops=1)  Planning Time: 0.900 ms  Execution Time: 126.180 ms (10 rows)* As in the previous query, even with applied the patch, the cardinality is calculated poorly here, I would even say that it has become worse: 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: 1000000    ->  Sort  (cost=158.51..164.16 rows=2260 width=8) (actual time=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=1000050 width=8) (actual time=363.016..649.103 rows=1000000 loops=1)          ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=363.012..481.480 rows=1000000 loops=1)                Sort Key: large.id                Sort Method: external merge  Disk: 17664kB                ->  Seq Scan on large (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.009..111.166 rows=1000000 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=999900 width=16) (actual time=261.480..261.482 rows=0 loops=1)    Hash Cond: (large.id = small.id)    Filter: (large.a IS NULL)    Rows Removed by Filter: 1000000    ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.006..92.827 rows=1000000 loops=1)    ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=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) * In addition, I found a few more queries, where the estimation of cardinality with the patch has become better: EXPLAIN ANALYZE   SELECT * FROM small LEFT JOIN large ON (large.id = small.id) WHERE (small.b IS NULL); MASTER: *QUERY PLAN -------------------------------------------------------------------------------------------------------------  Hash Right Join  (cost=32.74..18758.45 rows=55003 width=16) (actual time=0.100..0.104 rows=0 loops=1)    Hash Cond: (large.id = small.id)    ->  Seq Scan on large  (cost=0.00..14425.50 rows=1000050 width=8) (never executed)    ->  Hash  (cost=32.60..32.60 rows=11 width=8) (actual time=0.089..0.091 rows=0 loops=1)          Buckets: 1024  Batches: 1  Memory Usage: 8kB          ->  Seq Scan on small  (cost=0.00..32.60 rows=11 width=8) (actual time=0.088..0.088 rows=0 loops=1)                Filter: (b IS NULL)                Rows Removed by Filter: 100  Planning Time: 0.312 ms  Execution Time: 0.192 ms (10 rows)* With patch: *QUERY PLAN -----------------------------------------------------------------------------------------------------------  Hash Right Join  (cost=2.01..18177.02 rows=1 width=16) (actual time=0.127..0.132 rows=0 loops=1)    Hash Cond: (large.id = small.id)    ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (never executed)    ->  Hash  (cost=2.00..2.00 rows=1 width=8) (actual time=0.112..0.114 rows=0 loops=1)          Buckets: 1024  Batches: 1  Memory Usage: 8kB          ->  Seq Scan on small  (cost=0.00..2.00 rows=1 width=8) (actual time=0.111..0.111 rows=0 loops=1)                Filter: (b IS NULL)                Rows Removed by Filter: 100  Planning Time: 0.984 ms  Execution Time: 0.237 ms (10 rows)* EXPLAIN ANALYZE   SELECT * FROM large FULL JOIN small ON (large.id = small.id) WHERE (small.b IS NULL); MASTER: *QUERY PLAN -----------------------------------------------------------------------------------------------------------------------------------  Merge Full Join  (cost=127921.69..299941.59 rows=56503 width=16) (actual time=339.478..819.232 rows=999900 loops=1)    Merge Cond: (small.id = large.id)    Filter: (small.b IS NULL)    Rows Removed by Filter: 100    ->  Sort  (cost=158.51..164.16 rows=2260 width=8) (actual time=0.129..0.136 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.044..0.075 rows=100 loops=1)    ->  Materialize  (cost=127763.19..132763.44 rows=1000050 width=8) (actual time=339.260..605.444 rows=1000000 loops=1)          ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=339.254..449.930 rows=1000000 loops=1)                Sort Key: large.id                Sort Method: external merge  Disk: 17664kB                ->  Seq Scan on large (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.032..104.484 rows=1000000 loops=1)  Planning Time: 0.324 ms  Execution Time: 859.705 ms (15 rows) * With patch: *QUERY PLAN ----------------------------------------------------------------------------------------------------------------------  Hash Full Join  (cost=3.25..18179.25 rows=999900 width=16) (actual time=0.162..349.683 rows=999900 loops=1)    Hash Cond: (large.id = small.id)    Filter: (small.b IS NULL)    Rows Removed by Filter: 100    ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.021..95.972 rows=1000000 loops=1)    ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=0.125..0.127 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.030..0.059 rows=100 loops=1)  Planning Time: 0.218 ms  Execution Time: 385.819 ms (10 rows) * ** EXPLAIN ANALYZE   SELECT * FROM large RIGHT JOIN small ON (large.id = small.id)   WHERE (large.a IS NULL); MASTER: *QUERY PLAN -----------------------------------------------------------------------------------------------------------------------------------  Merge Left Join  (cost=127921.69..299941.59 rows=56503 width=16) (actual time=345.403..345.404 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) (actual time=0.033..0.039 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.012..0.020 rows=100 loops=1)    ->  Materialize  (cost=127763.19..132763.44 rows=1000050 width=8) (actual time=345.287..345.315 rows=101 loops=1)          ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=345.283..345.295 rows=101 loops=1)                Sort Key: large.id                Sort Method: external merge  Disk: 17664kB                ->  Seq Scan on large (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.009..104.648 rows=1000000 loops=1)  Planning Time: 0.098 ms  Execution Time: 347.807 ms (15 rows)* With patch: *QUERY PLAN ----------------------------------------------------------------------------------------------------------------------  Hash Right Join  (cost=3.25..18179.25 rows=100 width=16) (actual time=209.838..209.842 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=1000000 width=8) (actual time=0.006..91.571 rows=1000000 loops=1)    ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=0.034..0.036 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.016 rows=100 loops=1)  Planning Time: 0.168 ms  Execution Time: 209.883 ms (10 rows)* --------------eb5sqqwo9sbaiu1sjOKLH8Sl Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit
Hi, all!

On 24.06.2023 14:23, Tomas Vondra wrote:
On 6/24/23 02:08, Tom Lane wrote:

Tomas Vondra <tomas.vondra@enterprisedb.com> 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=999900 width=16)
                   (actual time=0.528..596.151 rows=999900 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=1000000 width=8)
                     (actual time=0.069..176.138 rows=1000000 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 eqjoinsel_inner.
I wrote myself in this commit as a co-author, if you don't mind, and I'm going to continue working.


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,100000) 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=99999 ...)

So the eqjoinsel_unmatch_left() function should be modified for the case where nd1<nd2.

Unfortunately, this patch could not fix the cardinality calculation in this request, I'll try to look and figure out what is missing here.

postgres=# SELECT i AS id INTO l FROM generate_series(1,100000) 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;
SELECT 100000
CREATE TABLE
INSERT 0 2
ANALYZE
                                                  QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
 Hash Left Join  (cost=1.04..1819.07 rows=1 width=14) (actual time=0.143..114.792 rows=99999 loops=1)
   Hash Cond: (l.id = r.id)
   Filter: (r.v IS NULL)
   Rows Removed by Filter: 1
   ->  Seq Scan on l  (cost=0.00..1443.00 rows=100000 width=4) (actual time=0.027..35.278 rows=100000 loops=1)
   ->  Hash  (cost=1.02..1.02 rows=2 width=10) (actual time=0.014..0.017 rows=2 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 9kB
         ->  Seq Scan on r  (cost=0.00..1.02 rows=2 width=10) (actual time=0.005..0.007 rows=2 loops=1)
 Planning Time: 0.900 ms
 Execution Time: 126.180 ms
(10 rows)


As in the previous query, even with applied the patch, the cardinality is calculated poorly here, I would even say that it has become worse:

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: 1000000
   ->  Sort  (cost=158.51..164.16 rows=2260 width=8) (actual time=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=1000050 width=8) (actual time=363.016..649.103 rows=1000000 loops=1)
         ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=363.012..481.480 rows=1000000 loops=1)
               Sort Key: large.id
               Sort Method: external merge  Disk: 17664kB
               ->  Seq Scan on large  (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.009..111.166 rows=1000000 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=999900 width=16) (actual time=261.480..261.482 rows=0 loops=1)
   Hash Cond: (large.id = small.id)
   Filter: (large.a IS NULL)
   Rows Removed by Filter: 1000000
   ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.006..92.827 rows=1000000 loops=1)
   ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=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)

In addition, I found a few more queries, where the estimation of cardinality with the patch has become better:


EXPLAIN ANALYZE
  SELECT * FROM small LEFT JOIN large ON (large.id = small.id)
WHERE (small.b IS NULL);

MASTER:

                                                 QUERY PLAN                                                  
-------------------------------------------------------------------------------------------------------------
 Hash Right Join  (cost=32.74..18758.45 rows=55003 width=16) (actual time=0.100..0.104 rows=0 loops=1)
   Hash Cond: (large.id = small.id)
   ->  Seq Scan on large  (cost=0.00..14425.50 rows=1000050 width=8) (never executed)
   ->  Hash  (cost=32.60..32.60 rows=11 width=8) (actual time=0.089..0.091 rows=0 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 8kB
         ->  Seq Scan on small  (cost=0.00..32.60 rows=11 width=8) (actual time=0.088..0.088 rows=0 loops=1)
               Filter: (b IS NULL)
               Rows Removed by Filter: 100
 Planning Time: 0.312 ms
 Execution Time: 0.192 ms
(10 rows)

With patch:

                                                QUERY PLAN                                                 
-----------------------------------------------------------------------------------------------------------
 Hash Right Join  (cost=2.01..18177.02 rows=1 width=16) (actual time=0.127..0.132 rows=0 loops=1)
   Hash Cond: (large.id = small.id)
   ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (never executed)
   ->  Hash  (cost=2.00..2.00 rows=1 width=8) (actual time=0.112..0.114 rows=0 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 8kB
         ->  Seq Scan on small  (cost=0.00..2.00 rows=1 width=8) (actual time=0.111..0.111 rows=0 loops=1)
               Filter: (b IS NULL)
               Rows Removed by Filter: 100
 Planning Time: 0.984 ms
 Execution Time: 0.237 ms
(10 rows)

EXPLAIN ANALYZE
  SELECT * FROM large FULL JOIN small ON (large.id = small.id)
WHERE (small.b IS NULL);

MASTER:

                                                            QUERY PLAN                                                             
-----------------------------------------------------------------------------------------------------------------------------------
 Merge Full Join  (cost=127921.69..299941.59 rows=56503 width=16) (actual time=339.478..819.232 rows=999900 loops=1)
   Merge Cond: (small.id = large.id)
   Filter: (small.b IS NULL)
   Rows Removed by Filter: 100
   ->  Sort  (cost=158.51..164.16 rows=2260 width=8) (actual time=0.129..0.136 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.044..0.075 rows=100 loops=1)
   ->  Materialize  (cost=127763.19..132763.44 rows=1000050 width=8) (actual time=339.260..605.444 rows=1000000 loops=1)
         ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=339.254..449.930 rows=1000000 loops=1)
               Sort Key: large.id
               Sort Method: external merge  Disk: 17664kB
               ->  Seq Scan on large  (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.032..104.484 rows=1000000 loops=1)
 Planning Time: 0.324 ms
 Execution Time: 859.705 ms
(15 rows)

With patch:

                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Hash Full Join  (cost=3.25..18179.25 rows=999900 width=16) (actual time=0.162..349.683 rows=999900 loops=1)
   Hash Cond: (large.id = small.id)
   Filter: (small.b IS NULL)
   Rows Removed by Filter: 100
   ->  Seq Scan on large  (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.021..95.972 rows=1000000 loops=1)
   ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=0.125..0.127 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.030..0.059 rows=100 loops=1)
 Planning Time: 0.218 ms
 Execution Time: 385.819 ms
(10 rows)

EXPLAIN ANALYZE
  SELECT * FROM large RIGHT JOIN small ON (large.id = small.id)
  WHERE (large.a IS NULL);

MASTER:

                                                            QUERY PLAN                                                             
-----------------------------------------------------------------------------------------------------------------------------------
 Merge Left Join  (cost=127921.69..299941.59 rows=56503 width=16) (actual time=345.403..345.404 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) (actual time=0.033..0.039 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.012..0.020 rows=100 loops=1)
   ->  Materialize  (cost=127763.19..132763.44 rows=1000050 width=8) (actual time=345.287..345.315 rows=101 loops=1)
         ->  Sort  (cost=127763.19..130263.31 rows=1000050 width=8) (actual time=345.283..345.295 rows=101 loops=1)
               Sort Key: large.id
               Sort Method: external merge  Disk: 17664kB
               ->  Seq Scan on large  (cost=0.00..14425.50 rows=1000050 width=8) (actual time=0.009..104.648 rows=1000000 loops=1)
 Planning Time: 0.098 ms
 Execution Time: 347.807 ms
(15 rows)

With patch:

                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Hash Right Join  (cost=3.25..18179.25 rows=100 width=16) (actual time=209.838..209.842 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=1000000 width=8) (actual time=0.006..91.571 rows=1000000 loops=1)
   ->  Hash  (cost=2.00..2.00 rows=100 width=8) (actual time=0.034..0.036 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.016 rows=100 loops=1)
 Planning Time: 0.168 ms
 Execution Time: 209.883 ms
(10 rows)

--------------eb5sqqwo9sbaiu1sjOKLH8Sl-- --------------tDPHaou5Vqx0hiWSaufqV0MH Content-Type: text/x-patch; charset=UTF-8; name="0001-Fixed-the-case-of-calculating-underestimated-cardina.patch" Content-Disposition: attachment; filename*0="0001-Fixed-the-case-of-calculating-underestimated-cardina.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSBlODY1MzQ3N2ZiZTczMjEzMjUxMjJhMmQ1MDMyNzk4Y2Q2YTk1YThiIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBUb21hcyBWb25kcmEgPHRvbWFzLnZvbmRyYUBlbnRl cnByaXNlZGIuY29tPgpEYXRlOiBNb24sIDI2IEp1biAyMDIzIDE1OjM5OjExICswMzAwClN1 YmplY3Q6IFtQQVRDSF0gRml4ZWQgdGhlIGNhc2Ugb2YgY2FsY3VsYXRpbmcgdW5kZXJlc3Rp bWF0ZWQgY2FyZGluYWxpdHkgZm9yCiBhbiBMRUZUIEpPSU4gd2l0aCB0aGUgcmVzdHJpY3Rp b24gIklTIE5VTEwiIGluIHRoZSBjbGF1c2UuIFRoaXMgZXJyb3IgaXMKIGNhdXNlZCBieSBh biBpbmNvcnJlY3QgY2FsY3VsYXRpb24gb2Ygc2VsZWN0aXZpdHkgaW4gdGhlICJJUyBOVUxM IiBjbGF1c2UsCiBzaW5jZSBpdCB0b29rIGludG8gYWNjb3VudCBvbmx5IHRhYmxlLWxldmVs IHN0YXRpc3RpY3Mgd2l0aG91dCB6ZXJvIHZhbHVlcyBpbgogdGhlIHJlc3VsdHMgb2YgdGhl IGpvaW4gb3BlcmF0aW9uLiBUaGlzIHBhdGNoIGZpeGVzIHRoaXMgYnkgY2FsY3VsYXRpbmcg dGhlCiBmcmFjdGlvbiBvZiB6ZXJvIHZhbHVlcyBvbiB0aGUgcmlnaHQgc2lkZSBvZiB0aGUg am9pbiB3aXRob3V0IG9mIG1hdGNoaW5nIHJvdwogb24gbGVmdC4KCkNvLWF1dGhvcmVkLWJ5 OiBBbGVuYSBSeWJha2luYSA8YS5yeWJha2luYUBwb3N0Z3Jlc3Byby5ydT4KLS0tCiBzcmMv YmFja2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYyB8IDM1ICsrKysrKysrKysrKysrKysrKysr KysrKysrKysrLS0tCiBzcmMvaW5jbHVkZS9ub2Rlcy9wYXRobm9kZXMuaCAgICB8ICAzICsr KwogMiBmaWxlcyBjaGFuZ2VkLCAzNSBpbnNlcnRpb25zKCspLCAzIGRlbGV0aW9ucygtKQoK ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9zZWxmdW5jcy5jIGIvc3JjL2Jh Y2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNzLmMKaW5kZXggYzRmY2QwMDc2ZWEuLjhlMThhYTFk ZDJiIDEwMDY0NAotLS0gYS9zcmMvYmFja2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYworKysg Yi9zcmMvYmFja2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYwpAQCAtMTUzLDcgKzE1Myw3IEBA IHN0YXRpYyBkb3VibGUgZXFqb2luc2VsX2lubmVyKE9pZCBvcGZ1bmNvaWQsIE9pZCBjb2xs YXRpb24sCiAJCQkJCQkJICBib29sIGlzZGVmYXVsdDEsIGJvb2wgaXNkZWZhdWx0MiwKIAkJ CQkJCQkgIEF0dFN0YXRzU2xvdCAqc3Nsb3QxLCBBdHRTdGF0c1Nsb3QgKnNzbG90MiwKIAkJ CQkJCQkgIEZvcm1fcGdfc3RhdGlzdGljIHN0YXRzMSwgRm9ybV9wZ19zdGF0aXN0aWMgc3Rh dHMyLAotCQkJCQkJCSAgYm9vbCBoYXZlX21jdnMxLCBib29sIGhhdmVfbWN2czIpOworCQkJ CQkJCSAgYm9vbCBoYXZlX21jdnMxLCBib29sIGhhdmVfbWN2czIsIGRvdWJsZSAqdW5tYXRj aGVkX2ZyYWMpOwogc3RhdGljIGRvdWJsZSBlcWpvaW5zZWxfc2VtaShPaWQgb3BmdW5jb2lk LCBPaWQgY29sbGF0aW9uLAogCQkJCQkJCSBWYXJpYWJsZVN0YXREYXRhICp2YXJkYXRhMSwg VmFyaWFibGVTdGF0RGF0YSAqdmFyZGF0YTIsCiAJCQkJCQkJIGRvdWJsZSBuZDEsIGRvdWJs ZSBuZDIsCkBAIC0xNzEwLDYgKzE3MTAsOSBAQCBudWxsdGVzdHNlbChQbGFubmVySW5mbyAq cm9vdCwgTnVsbFRlc3RUeXBlIG51bGx0ZXN0dHlwZSwgTm9kZSAqYXJnLAogCQlzdGF0cyA9 IChGb3JtX3BnX3N0YXRpc3RpYykgR0VUU1RSVUNUKHZhcmRhdGEuc3RhdHNUdXBsZSk7CiAJ CWZyZXFfbnVsbCA9IHN0YXRzLT5zdGFudWxsZnJhYzsKIAorCQlpZiAoc2ppbmZvKQorCQkJ ZnJlcV9udWxsID0gZnJlcV9udWxsICsgc2ppbmZvLT51bm1hdGNoZWRfZnJhYyAtIGZyZXFf bnVsbCAqIHNqaW5mby0+dW5tYXRjaGVkX2ZyYWM7CisKIAkJc3dpdGNoIChudWxsdGVzdHR5 cGUpCiAJCXsKIAkJCWNhc2UgSVNfTlVMTDoKQEAgLTIzMTMsMTMgKzIzMTYsMjQgQEAgZXFq b2luc2VsKFBHX0ZVTkNUSU9OX0FSR1MpCiAJfQogCiAJLyogV2UgbmVlZCB0byBjb21wdXRl IHRoZSBpbm5lci1qb2luIHNlbGVjdGl2aXR5IGluIGFsbCBjYXNlcyAqLworCS8qCisJICog Y2FsY3VsYXRlIGZyYWN0aW9uIG9mIHJpZ2h0IHdpdGhvdXQgb2YgbWF0Y2hpbmcgcm93IG9u IGxlZnQKKwkgKgorCSAqIEZJWE1FIFNob3VsZCBiZSByZXN0cmljdGVkIHRvIEpPSU5fTEVG VCwgd2Ugc2hvdWxkIGhhdmUgc2ltaWxhciBsb2dpYworCSAqIGZvciBKT0lOX0ZVTEwuCisJ ICoKKwkgKiBYWFggUHJvYmFibHkgc2hvdWxkIGNhbGN1bGF0ZSB1bm1hdGNoZWQgYXMgZnJh Y3Rpb24gb2YgdGhlIGpvaW4gcmVzdWx0LAorCSAqIG5vdCBvZiB0aGUgcmVsYXRpb24gb24g dGhlIHJpZ2h0IChiZWNhdXNlIHRoZSBtYXRjaGVkIHBhcnQgY2FuIGhhdmUgbW9yZQorCSAq IG1hdGNoZXMgcGVyIHJvdyBhbmQgdGh1cyBncm93KS4gTm90IHN1cmUuIERlcGVuZHMgb24g aG93IGl0J3MgdXNlZCBsYXRlci4KKwkgKi8KIAlzZWxlY19pbm5lciA9IGVxam9pbnNlbF9p bm5lcihvcGZ1bmNvaWQsIGNvbGxhdGlvbiwKIAkJCQkJCQkJICAmdmFyZGF0YTEsICZ2YXJk YXRhMiwKIAkJCQkJCQkJICBuZDEsIG5kMiwKIAkJCQkJCQkJICBpc2RlZmF1bHQxLCBpc2Rl ZmF1bHQyLAogCQkJCQkJCQkgICZzc2xvdDEsICZzc2xvdDIsCiAJCQkJCQkJCSAgc3RhdHMx LCBzdGF0czIsCi0JCQkJCQkJCSAgaGF2ZV9tY3ZzMSwgaGF2ZV9tY3ZzMik7CisJCQkJCQkJ CSAgaGF2ZV9tY3ZzMSwgaGF2ZV9tY3ZzMiwKKwkJCQkJCQkJICAmc2ppbmZvLT51bm1hdGNo ZWRfZnJhYyk7CiAKIAlzd2l0Y2ggKHNqaW5mby0+am9pbnR5cGUpCiAJewpAQCAtMjQwNyw3 ICsyNDIxLDcgQEAgZXFqb2luc2VsX2lubmVyKE9pZCBvcGZ1bmNvaWQsIE9pZCBjb2xsYXRp b24sCiAJCQkJYm9vbCBpc2RlZmF1bHQxLCBib29sIGlzZGVmYXVsdDIsCiAJCQkJQXR0U3Rh dHNTbG90ICpzc2xvdDEsIEF0dFN0YXRzU2xvdCAqc3Nsb3QyLAogCQkJCUZvcm1fcGdfc3Rh dGlzdGljIHN0YXRzMSwgRm9ybV9wZ19zdGF0aXN0aWMgc3RhdHMyLAotCQkJCWJvb2wgaGF2 ZV9tY3ZzMSwgYm9vbCBoYXZlX21jdnMyKQorCQkJCWJvb2wgaGF2ZV9tY3ZzMSwgYm9vbCBo YXZlX21jdnMyLCBkb3VibGUgKnVubWF0Y2hlZF9mcmFjKQogewogCWRvdWJsZQkJc2VsZWM7 CiAKQEAgLTI1MDMsNyArMjUxNywxMCBAQCBlcWpvaW5zZWxfaW5uZXIoT2lkIG9wZnVuY29p ZCwgT2lkIGNvbGxhdGlvbiwKIAkJfQogCQlDTEFNUF9QUk9CQUJJTElUWShtYXRjaGZyZXEx KTsKIAkJQ0xBTVBfUFJPQkFCSUxJVFkodW5tYXRjaGZyZXExKTsKKworCQkqdW5tYXRjaGVk X2ZyYWMgPSB1bm1hdGNoZnJlcTE7CiAJCW1hdGNoZnJlcTIgPSB1bm1hdGNoZnJlcTIgPSAw LjA7CisKIAkJZm9yIChpID0gMDsgaSA8IHNzbG90Mi0+bnZhbHVlczsgaSsrKQogCQl7CiAJ CQlpZiAoaGFzbWF0Y2gyW2ldKQpAQCAtMjU4MSwxMCArMjU5OCwyMiBAQCBlcWpvaW5zZWxf aW5uZXIoT2lkIG9wZnVuY29pZCwgT2lkIGNvbGxhdGlvbiwKIAkJZG91YmxlCQludWxsZnJh YzIgPSBzdGF0czIgPyBzdGF0czItPnN0YW51bGxmcmFjIDogMC4wOwogCiAJCXNlbGVjID0g KDEuMCAtIG51bGxmcmFjMSkgKiAoMS4wIC0gbnVsbGZyYWMyKTsKKworCQkvKgorCQkgKiBY WFggU2hvdWxkIHRoaXMgbG9vayBhdCBudWxsZnJhYyBvbiBlaXRoZXIgc2lkZT8gUHJvYmFi bHkgZGVwZW5kcyBvbgorCQkgKiBpZiB3ZSdyZSBjYWxjdWxhdGluZyBmcmFjdGlvbiBvZiBO VUxMcyBvciBmcmFjdGlvbiBvZiB1bm1hdGNoZWQgcm93cy4KKwkJICovCisJCS8vIHVubWF0 Y2hmcmVxID0gKDEuMCAtIG51bGxmcmFjMSkgKiAoMS4wIC0gbnVsbGZyYWMyKTsKIAkJaWYg KG5kMSA+IG5kMikKKwkJewogCQkJc2VsZWMgLz0gbmQxOworCQkJKnVubWF0Y2hlZF9mcmFj ID0gKG5kMSAtIG5kMikgKiAxLjAgLyBuZDE7CisJCX0KIAkJZWxzZQorCQl7CiAJCQlzZWxl YyAvPSBuZDI7CisJCQkqdW5tYXRjaGVkX2ZyYWMgPSAwLjA7CisJCX0KIAl9CiAKIAlyZXR1 cm4gc2VsZWM7CmRpZmYgLS1naXQgYS9zcmMvaW5jbHVkZS9ub2Rlcy9wYXRobm9kZXMuaCBi L3NyYy9pbmNsdWRlL25vZGVzL3BhdGhub2Rlcy5oCmluZGV4IGMxN2I1M2Y3YWRiLi42YmM2 M2U2NDhlNiAxMDA2NDQKLS0tIGEvc3JjL2luY2x1ZGUvbm9kZXMvcGF0aG5vZGVzLmgKKysr IGIvc3JjL2luY2x1ZGUvbm9kZXMvcGF0aG5vZGVzLmgKQEAgLTI4NTMsNiArMjg1Myw5IEBA IHN0cnVjdCBTcGVjaWFsSm9pbkluZm8KIAlib29sCQlzZW1pX2Nhbl9oYXNoOwkvKiB0cnVl IGlmIHNlbWlfb3BlcmF0b3JzIGFyZSBhbGwgaGFzaCAqLwogCUxpc3QJICAgKnNlbWlfb3Bl cmF0b3JzOyAvKiBPSURzIG9mIGVxdWFsaXR5IGpvaW4gb3BlcmF0b3JzICovCiAJTGlzdAkg ICAqc2VtaV9yaHNfZXhwcnM7IC8qIHJpZ2h0aGFuZC1zaWRlIGV4cHJlc3Npb25zIG9mIHRo ZXNlIG9wcyAqLworCisJLyogRm9yIG91dGVyIGpvaW4sIGZyYWN0aW9uIG9mIHJvd3Mgd2l0 aG91dCBhIG1hdGNoLiAqLworCVNlbGVjdGl2aXR5CXVubWF0Y2hlZF9mcmFjOwogfTsKIAog LyoKLS0gCjIuMzQuMQoK --------------tDPHaou5Vqx0hiWSaufqV0MH--