Subject: Re: Hash join gets slower as work_mem increases?
To: Albe Laurenz <laurenz.albe@wien.gv.at>,
 "pgsql-performance@postgresql.org" <pgsql-performance@postgresql.org>
References: 
 <A737B7A37273E048B164557ADEF4A58B537DC731@ntex2010i.host.magwien.gv.at>
 <56ACC50B.1090007@2ndquadrant.com>
 <A737B7A37273E048B164557ADEF4A58B537DCE5F@ntex2010i.host.magwien.gv.at>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <56AF2C97.4040303@2ndquadrant.com>
Date: Mon, 1 Feb 2016 10:59:51 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.1.0
MIME-Version: 1.0
In-Reply-To: 
 <A737B7A37273E048B164557ADEF4A58B537DCE5F@ntex2010i.host.magwien.gv.at>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-performance-owner@postgresql.org

On 02/01/2016 10:38 AM, Albe Laurenz wrote:
> Tomas Vondra wrote:
...
> I didn't post the whole plan since it is awfully long, I'll include hyperlinks
> for the whole plan.
>
> work_mem = '100MB' (http://explain.depesz.com/s/7b6a):
>
> ->  Hash Join  (cost=46738.74..285400.61 rows=292 width=8) (actual time=4296.986..106087.683 rows=187222 loops=1)
>         Hash Cond: ("*SELECT* 1_2".postadresse_id = p.postadresse_id)
>         Buffers: shared hit=1181177 dirtied=1, temp read=7232 written=7230
> [...]
>         ->  Hash  (cost=18044.92..18044.92 rows=4014 width=8) (actual time=4206.892..4206.892 rows=3096362 loops=1)
>               Buckets: 1024  Batches: 2 (originally 1)  Memory Usage: 102401kB
>               Buffers: shared hit=1134522 dirtied=1, temp written=5296
>
> work_mem = '500MB' (http://explain.depesz.com/s/Cgkl):
>
> ->  Hash Join  (cost=46738.74..285400.61 rows=292 width=8) (actual time=3802.849..245970.049 rows=187222 loops=1)
>         Hash Cond: ("*SELECT* 1_2".postadresse_id = p.postadresse_id)
>         Buffers: shared hit=1181175 dirtied=111
> [...]
>         ->  Hash  (cost=18044.92..18044.92 rows=4014 width=8) (actual time=3709.584..3709.584 rows=3096360 loops=1)
>               Buckets: 1024  Batches: 1  Memory Usage: 120952kB
>               Buffers: shared hit=1134520 dirtied=111
>
> Does that support your theory?
>
> There is clearly an underestimate here, caused by correlated attributes, but
> is that the cause for the bad performance with increased work_mem?

Yes, that's clearly the culprit here. In both cases we estimate here are 
only ~4000 tuples in the hash, and 9.3 sizes the hash table to have at 
most ~10 tuples per bucket (in a linked list).

However we actually get ~3M rows, so there will be ~3000 tuples per 
bucket, and that's extremely expensive to walk. The reason why 100MB is 
faster is that it's using 2 batches, thus making the lists "just" ~1500 
tuples long.

This is pretty much exactly the reason why I reworked hash joins in 9.5. 
I'd bet it's going to be ~20x faster on that version.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance