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 1kq4Ls-0005CC-D5 for pgsql-bugs@arkaria.postgresql.org; Fri, 18 Dec 2020 01:14:36 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1kq4Lr-0005kU-0a for pgsql-bugs@arkaria.postgresql.org; Fri, 18 Dec 2020 01:14:35 +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 1kq4Lq-0005kM-OJ for pgsql-bugs@lists.postgresql.org; Fri, 18 Dec 2020 01:14:34 +0000 Received: from mail-ej1-x634.google.com ([2a00:1450:4864:20::634]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1kq4Ln-0005Bz-IP for pgsql-bugs@lists.postgresql.org; Fri, 18 Dec 2020 01:14:33 +0000 Received: by mail-ej1-x634.google.com with SMTP id x16so802472ejj.7 for ; Thu, 17 Dec 2020 17:14:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=enterprisedb-com.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=LCKx8RLnTXLt0IQJInt5q0ozRw2DghZohmidSbGXMMY=; b=uH37xZVErB36qt4lUttjFxpKTstQX4uWnTB7CslfxM0UTiqcLjQsoLhuyd1XvpGLbT 4Z1+mdh1mO8KXXgLcgbY1M7WeK1sF+mh7nJf38lhsWYA3mwIp3i6YChryxB6OxkJEm9R EgLQGjrp11PoHke6ZsHEwUFUCMw+r8E4LZRoJab9HMzsSQ4t+l7dsU+b3d86XyF2BdGz X5KoWq5S0Kji/gwuVMG/8moA1zsL4FKG6qU6ngnuZqnBCAdDSoRipnmd1khoRF3Ka7E4 qRHg3HOwRjrhRHoOo7reacpNWPyAGjjdDFjLvB7JRq1P9v0AKgOS6XB05J9JIIdZpmEg WeRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=LCKx8RLnTXLt0IQJInt5q0ozRw2DghZohmidSbGXMMY=; b=k+j0Ipvtgl5vqqgnpEy47iWLHRijD60DvhpydHOeR05eKrsiSctH/Xq+UyalLIxRL9 fp3yiRlSdaODujx18mmA4MZWHMLCg6c2d6azuSThFu/QxlXaYtzP4UIB0y3cs4hzDveA qBFnSKThQ/FF/TlPqj73nhPplyu0x4Z54zlFd11fqB7mAddhnUTDFszK+ZPvL5M760db 0I/wpsZ2mZ94PQzpS168RjK2IXdDWgeJmJxcqYgb5J6Am3F3QMhrU6Fuzvu1+03+E2WY VVhLGv6lwNOMYsGa27DF4gZ/Y6DhcDKjN2rYpLZ39r/f2zA4F6GV7wc+kRemgmwDqvjl tVSA== X-Gm-Message-State: AOAM531/xsPH3ZAozjdO8cAFor1QO7spueMizuFp7O3xoe4rHzvP7OGE KkMb4VRws16rMb2gNQfAd0Fso1foPRH/XHS1EaULaFriNBhXiOdOW+6pEG//ubWVc2xmhLlwzXq UbVPvi5Cg/gEP7VRqkgeivi96vh6UfZGrNqlnxYW5TID+ahvr2A8A5LFU8bTotTunGqTltvN83L rGSFJlBA+6KeahO2rHOclYkz4O5UeJK7D1DFDI0g4Fwiaks7LLC5jeFbyUO8TU9liEk0f+04N8N FFGAkaR61cu5h6oeDKvw0u/xlTNsuEoI+X3B7V21nO1llHr X-Google-Smtp-Source: ABdhPJySs5BdskA2ouYeByZSQNaiBCcVdH+el8K+MJBVRII1CyDFCWoPJ25e5iKgKP5yJ2V37MXTPA== X-Received: by 2002:a17:906:9a07:: with SMTP id ai7mr1743133ejc.216.1608254069542; Thu, 17 Dec 2020 17:14:29 -0800 (PST) Received: from [10.137.0.19] (ip-86-49-249-71.net.upcbroadband.cz. [86.49.249.71]) by smtp.gmail.com with ESMTPSA id o33sm24919040edd.50.2020.12.17.17.14.27 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 17 Dec 2020 17:14:28 -0800 (PST) Subject: Re: BUG #16759: Estimation of the planner is wrong for hash join To: Bertrand Guillaumin , Tom Lane , pgsql-bugs@lists.postgresql.org References: <16759-f0980add03d8f152@postgresql.org> <1672657.1606940979@sss.pgh.pa.us> <1677883.1606948395@sss.pgh.pa.us> From: Tomas Vondra Message-ID: <18e3e4e6-2816-77fa-84c2-b85448fbe6ce@enterprisedb.com> Date: Fri, 18 Dec 2020 02:14:54 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.5.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit X-CLOUD-SEC-AV-Info: enterprisedb,google_mail,monitor X-CLOUD-SEC-AV-Sent: true X-Gm-Spam: 0 X-Gm-Phishy: 0 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk On 12/17/20 6:36 PM, Bertrand Guillaumin wrote: > Hello, > I think I just made a test that shows that even with MCV on both sides > the estimated selectivity can be pretty wrong. > test=# create table test_bug_hash2 as SELECT mod(id,500) as id , case > when id<=500 then 1 else 2 end parent_id, null::text as attrib from > (select generate_series(1,1000) as id) alias0; > SELECT 1000 > test=# update test_bug_hash2 set attrib='BEL' where id=2; > UPDATE 2 > test=# analyze test_bug_hash2; > ANALYZE > test=# explain select * from test_bug_hash2 a, test_bug_hash2 b where > a.parent_id=b.id and b.attrib='BEL'; >                                   QUERY PLAN > ------------------------------------------------------------------------------ >  Hash Join  (cost=17.52..37.56 rows=4 width=24) >    Hash Cond: (a.parent_id = b.id ) >    ->  Seq Scan on test_bug_hash2 a  (cost=0.00..15.00 rows=1000 width=12) >    ->  Hash  (cost=17.50..17.50 rows=2 width=12) >          ->  Seq Scan on test_bug_hash2 b  (cost=0.00..17.50 rows=2 > width=12) >                Filter: (attrib = 'BEL'::text) > > test=#  select count(*) from test_bug_hash2 a, test_bug_hash2 b where > a.parent_id=b.id and b.attrib='BEL'; >  count > ------- >   1000 > > I won't copy paste the pg_stats lines but most_common_vals and > most_common_freq have values for all three columns. > > I'm not a programmer but I've looked into the code of the planner a > little bit and it seems you try to estimate the selectivity of a join in > itself without any regards to the filters that can be applied on any > side of the join ( if I understood correctly). > I think that it's ultimately where the problem lies, if the filter is > not too important the selectivity stays more or less the same but with > filters like the one in this query the selectivity of the join can > change a lot so in the end you get estimations which can be totally wrong. > > Right. The problem is that the two columns are correlated, thanks to how you set the attrib value only for id=2, but the join estimation code is oblivious to that. Perhaps the multi-column/extended stats might allow us to improve this, but the code has not been written yet. regards -- Tomas Vondra EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company