Message-ID: <55DA1F9F.5040204@2ndquadrant.com>
Date: Sun, 23 Aug 2015 21:31:43 +0200
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: pgsql-hackers@postgresql.org
Subject: Re: Performance improvement for joins where outer side
 is unique
References: <20150320.121140.148610378.horiguchi.kyotaro@lab.ntt.co.jp>
 <CAPpHfdviphQFjk-gaGZGGxLAyt=YuVdJLnntsxOKnU296s9u-Q@mail.gmail.com>
 <CAKJS1f-=1y0-f5FFV2_r7LtS+CL2Lw-nhJjXB3O_0FmBqnK=3A@mail.gmail.com>
 <27152324.eFKJb4Khb5@dinodell> <8608754a32d1325c2f83ba8b1df71585@xs4all.nl>
In-Reply-To: <8608754a32d1325c2f83ba8b1df71585@xs4all.nl>
Content-Type: multipart/mixed; boundary="------------020507040007020105050101"
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

This is a multi-part message in MIME format.
--------------020507040007020105050101
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit

Hi,

I did some initial performance evaluation of this patch today, and I see 
a clear improvement on larger joins. The scenario I've chosen for the 
experiments is a simple fact-dimension join, i.e. a small table 
referenced by a large table. So effectively something like this:

CREATE TABLE dim  (id INT PRIMARY KEY, ...);
CREATE TABLE fact (dim_d INT REFERENCES dim(id), ...);

except that I haven't used the foreign key constraint. In all the 
experiments I've used a fact table 10x the size of the dimension, but I 
believe what really matters most is the size of the dimension (and how 
the hash table fits into the L2/L3 cache).

The query tested is very simple:

     select count(1) from (
         select * from f join d on (f.fact_id = d.dim_id)
     ) foo;

The outer aggregation is intentional - the join produces many rows and 
formatting them as string would completely eliminate any gains from the 
patch (even with "\o /dev/null" or such).

The following numbers come current master, running on E5-2630 v3 
(2.40GHz), 64GB of RAM and this configuration:

  checkpoint_timeout = 15min
  effective_cache_size = 48GB
  maintenance_work_mem = 1GB
  max_wal_size = 4GB
  min_wal_size = 1GB
  random_page_cost = 1.5
  shared_buffers = 4GB
  work_mem = 1GB

all the other values are set to default.

I did 10 runs for each combination of sizes - the numbers seem quite 
consistent and repeatable. I also looked at the median values.


dim 100k rows, fact 1M rows
---------------------------

          master     patched
         -------     -------
    1    286.184     265.489
    2    284.827     264.961
    3    281.040     264.768
    4    280.926     267.720
    5    280.984     261.348
    6    280.878     261.463
    7    280.875     261.338
    8    281.042     261.265
    9    281.003     261.236
   10    280.939     261.185
         -------     -------
  med    280.994     261.406 (-7%)


dim 1M rows, fact 10M rows
--------------------------

          master     patched
        --------    --------
    1   4316.235    3690.373
    2   4399.539    3738.097
    3   4360.551    3655.602
    4   4359.763    3626.142
    5   4361.821    3621.941
    6   4359.205    3654.835
    7   4371.438    3631.212
    8   4361.857    3626.237
    9   4357.317    3676.651
   10   4359.561    3641.830
        --------    --------
  med   4360.157    3648.333 (-17%)


dim 10M rows, fact 100M rows
----------------------------

          master     patched
        --------    --------
    1  46246.467   39561.597
    2  45982.937   40083.352
    3  45818.118   39674.661
    4  45716.281   39616.585
    5  45651.117   40463.966
    6  45979.036   41395.390
    7  46045.400   41358.047
    8  45978.698   41253.946
    9  45801.343   41156.440
   10  45720.722   41374.688
       ---------   ---------
  med  45898.408   40810.203 (-10%)


So the gains seem quite solid - it's not something that would make the 
query an order of magnitude faster, but it's well above the noise.

Of course, in practice the queries will be more complicated, making the 
improvement less significant, but I don't think that's a reason not to 
apply it.

Two minor comments on the patch:

1) the 'subquery' variable in specialjoin_is_unique_join is unused

2) in the explain output, there should probably be a space before the
    '(inner unique)' text, so

      Hash Join (inner unique) ...

    instead of

      Hash Join(inner unique)

but that's just nitpicking at this point. Otherwise the patch seems 
quite solid to me.

regard

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

--------------020507040007020105050101
Content-Type: application/sql;
 name="unijoins-test.sql"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
 filename="unijoins-test.sql"

Y3JlYXRlIHRhYmxlIGYgKGZhY3RfaWQgaW50LCBmYWN0X3ZhbDEgdGV4dCwg
ZmFjdF92YWwyIG51bWVyaWMpOwpjcmVhdGUgdGFibGUgZCAoZGltX2lkIGlu
dCBwcmltYXJ5IGtleSwgZGltX3ZhbHVlMSB0ZXh0LCBkaW1fdmFsdWUyIG51
bWVyaWMpOwoKLS0gZD0xMDAwMDAgZj0xMDAwMDAwCgppbnNlcnQgaW50byBk
IHNlbGVjdCBpLCBtZDUocmFuZG9tKCk6OnRleHQpLCByYW5kb20oKSBmcm9t
IGdlbmVyYXRlX3NlcmllcygwLDk5OTk5KSBzKGkpOwppbnNlcnQgaW50byBm
IHNlbGVjdCBtb2QoaSwxMDAwMDApLCBtZDUocmFuZG9tKCk6OnRleHQpLCBy
YW5kb20oKSBmcm9tIGdlbmVyYXRlX3NlcmllcygwLDk5OTk5OSkgcyhpKTsK
CnZhY3V1bSBhbmFseXplIGQ7CnZhY3V1bSBhbmFseXplIGY7CgpcaSB1bmlq
b2lucy1xdWVyaWVzLnNxbAoKLS0gZD0xMDAwMDAwIGY9MTAwMDAwMDAKCnRy
dW5jYXRlIGQ7CnRydW5jYXRlIGY7CgppbnNlcnQgaW50byBkIHNlbGVjdCBp
LCBtZDUocmFuZG9tKCk6OnRleHQpLCByYW5kb20oKSBmcm9tIGdlbmVyYXRl
X3NlcmllcygwLDk5OTk5OSkgcyhpKTsKaW5zZXJ0IGludG8gZiBzZWxlY3Qg
bW9kKGksMTAwMDAwMCksIG1kNShyYW5kb20oKTo6dGV4dCksIHJhbmRvbSgp
IGZyb20gZ2VuZXJhdGVfc2VyaWVzKDAsOTk5OTk5OSkgcyhpKTsKCnZhY3V1
bSBhbmFseXplIGQ7CnZhY3V1bSBhbmFseXplIGY7CgpcaSB1bmlqb2lucy1x
dWVyaWVzLnNxbAoKLS0gZD0xMDAwMDAwMCBmPTEwMDAwMDAwMAoKdHJ1bmNh
dGUgZDsKdHJ1bmNhdGUgZjsKCmluc2VydCBpbnRvIGQgc2VsZWN0IGksIG1k
NShyYW5kb20oKTo6dGV4dCksIHJhbmRvbSgpIGZyb20gZ2VuZXJhdGVfc2Vy
aWVzKDAsOTk5OTk5OSkgcyhpKTsKaW5zZXJ0IGludG8gZiBzZWxlY3QgbW9k
KGksMTAwMDAwMDApLCBtZDUocmFuZG9tKCk6OnRleHQpLCByYW5kb20oKSBm
cm9tIGdlbmVyYXRlX3NlcmllcygwLDk5OTk5OTk5KSBzKGkpOwoKdmFjdXVt
IGFuYWx5emUgZDsKdmFjdXVtIGFuYWx5emUgZjsKClxpIHVuaWpvaW5zLXF1
ZXJpZXMuc3FsCg==

--------------020507040007020105050101
Content-Type: application/sql;
 name="unijoins-queries.sql"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
 filename="unijoins-queries.sql"

XHRpbWluZyBvbgoKc2VsZWN0IGNvdW50KDEpIGZyb20gKHNlbGVjdCAqIGZy
b20gZiBqb2luIGQgb24gKGYuZmFjdF9pZCA9IGQuZGltX2lkKSkgZm9vOwpz
ZWxlY3QgY291bnQoMSkgZnJvbSAoc2VsZWN0ICogZnJvbSBmIGpvaW4gZCBv
biAoZi5mYWN0X2lkID0gZC5kaW1faWQpKSBmb287CnNlbGVjdCBjb3VudCgx
KSBmcm9tIChzZWxlY3QgKiBmcm9tIGYgam9pbiBkIG9uIChmLmZhY3RfaWQg
PSBkLmRpbV9pZCkpIGZvbzsKc2VsZWN0IGNvdW50KDEpIGZyb20gKHNlbGVj
dCAqIGZyb20gZiBqb2luIGQgb24gKGYuZmFjdF9pZCA9IGQuZGltX2lkKSkg
Zm9vOwpzZWxlY3QgY291bnQoMSkgZnJvbSAoc2VsZWN0ICogZnJvbSBmIGpv
aW4gZCBvbiAoZi5mYWN0X2lkID0gZC5kaW1faWQpKSBmb287CnNlbGVjdCBj
b3VudCgxKSBmcm9tIChzZWxlY3QgKiBmcm9tIGYgam9pbiBkIG9uIChmLmZh
Y3RfaWQgPSBkLmRpbV9pZCkpIGZvbzsKc2VsZWN0IGNvdW50KDEpIGZyb20g
KHNlbGVjdCAqIGZyb20gZiBqb2luIGQgb24gKGYuZmFjdF9pZCA9IGQuZGlt
X2lkKSkgZm9vOwpzZWxlY3QgY291bnQoMSkgZnJvbSAoc2VsZWN0ICogZnJv
bSBmIGpvaW4gZCBvbiAoZi5mYWN0X2lkID0gZC5kaW1faWQpKSBmb287CnNl
bGVjdCBjb3VudCgxKSBmcm9tIChzZWxlY3QgKiBmcm9tIGYgam9pbiBkIG9u
IChmLmZhY3RfaWQgPSBkLmRpbV9pZCkpIGZvbzsKc2VsZWN0IGNvdW50KDEp
IGZyb20gKHNlbGVjdCAqIGZyb20gZiBqb2luIGQgb24gKGYuZmFjdF9pZCA9
IGQuZGltX2lkKSkgZm9vOwo=

--------------020507040007020105050101
Content-Type: text/plain
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0


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

--------------020507040007020105050101--