Received: from localhost (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id 0820F64FC5A for ; Wed, 19 Nov 2008 11:12:50 -0400 (AST) Received: from mail.postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 80534-03 for ; Wed, 19 Nov 2008 11:12:46 -0400 (AST) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from yw-out-2324.google.com (yw-out-2324.google.com [74.125.46.31]) by mail.postgresql.org (Postfix) with ESMTP id 02D9764FE3D for ; Wed, 19 Nov 2008 11:12:45 -0400 (AST) Received: by yw-out-2324.google.com with SMTP id 3so1424442ywj.73 for ; Wed, 19 Nov 2008 07:12:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:subject :cc:in-reply-to:mime-version:content-type:references; bh=40l2p2x6wNkusDFrGEK3T9p/agc25s8bUnppqQSrbW8=; b=vg6Ql39LZeUhiNMoMVzjPJHfP6wnyiFEvQsLJ+97AZRj7wlOLiv6Hji4iCf7dBKw0w qftv0+NO7xc84+iOX0nFUMa+XEJKsZiU55NgcCbQIPRdrPPcxhXqVmQ9sn/uqb9syqjw BcPUojcujTdfoDzXOvu0ZGPvx/8GSFg3J0pVE= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:subject:cc:in-reply-to:mime-version :content-type:references; b=k+UZmDmTl5x9xGFJULXBOBCJ74SsoCoi4I7wpmvCQ3Zqk927NjHuTUYGkCC50ChH+u qNMjCssuFfOvscst/SQz+MUS4ut+o+1DW/sBrQmyrBdx07FdngUMqIhD7O/kT/eBebSL VJGJaXo7sgubRbOGBqirstkhUgJtG81fBxDzw= Received: by 10.65.153.10 with SMTP id f10mr1166853qbo.70.1227107563907; Wed, 19 Nov 2008 07:12:43 -0800 (PST) Received: by 10.65.22.1 with HTTP; Wed, 19 Nov 2008 07:12:43 -0800 (PST) Message-ID: <331e40660811190712p416c371t9c9237ac98ab06fb@mail.gmail.com> Date: Wed, 19 Nov 2008 17:12:43 +0200 From: "=?ISO-8859-5?B?svbi0Nv22SDC2Nzn2OjY3Q==?=" Subject: Re: PostgreSQL NOT IN performance Cc: pgsql-performance@postgresql.org In-Reply-To: <91db404146cba5910fcafdba91db5b9b@intranet.sc.senai.br> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_75322_25533135.1227107563908" References: <331e40660811190351n6bde6caic5fd8cc3a0f777d2@mail.gmail.com> <91db404146cba5910fcafdba91db5b9b@intranet.sc.senai.br> X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.582 tagged_above=0 required=5 tests=HTML_MESSAGE=0.001, MISSING_HEADERS=1.581 X-Spam-Level: * X-Archive-Number: 200811/165 X-Sequence-Number: 31896 ------=_Part_75322_25533135.1227107563908 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 2008/11/19 DANIEL CRISTIAN CRUZ > Something weird with your example which doesn't have the same result, see > row count with explain analyze: > My fault. EXCEPT ALL would not work here, so this method with EXCEPT can be used only when either operation is done on unique key on t1 or result is going to be made unique. > cruz=# SELECT version(); > version > -------------------------------------------------------------------------------------------- > PostgreSQL 8.3.5 on i486-pc-linux-gnu, compiled by GCC gcc-4.3.real (Debian 4.3.2-1) 4.3.2 > (1 registro) > > cruz=# EXPLAIN ANALYZE select * from t1 where id not in (select id from t2); > QUERY PLAN > ------------------------------------------------------------------------------------------------------------------ > Seq Scan on t1 (cost=1643.00..4928.00 rows=100000 width=4) (actual time=256.687..585.774 rows=73653 loops=1) > Filter: (NOT (hashed subplan)) > SubPlan > -> Seq Scan on t2 (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.052..86.867 rows=100000 loops=1) > Total runtime: 625.471 ms > (5 registros) > > cruz=# EXPLAIN ANALYZE select * from t1 except all (select id from t2); > QUERY PLAN > ----------------------------------------------------------------------------------------------------------------------------------------- > SetOp Except All (cost=34469.90..35969.90 rows=30000 width=4) (actual time=2598.574..3663.712 rows=126733 loops=1) > -> Sort (cost=34469.90..35219.90 rows=300000 width=4) (actual time=2598.550..3178.387 rows=300000 loops=1) > Sort Key: "*SELECT* 1".id > Sort Method: external merge Disk: 5864kB > -> Append (cost=0.00..7178.00 rows=300000 width=4) (actual time=0.037..1026.367 rows=300000 loops=1) > -> Subquery Scan "*SELECT* 1" (cost=0.00..4785.00 rows=200000 width=4) (actual time=0.035..439.507 rows=200000 loops=1) > -> Seq Scan on t1 (cost=0.00..2785.00 rows=200000 width=4) (actual time=0.029..161.355 rows=200000 loops=1) > -> Subquery Scan "*SELECT* 2" (cost=0.00..2393.00 rows=100000 width=4) (actual time=0.107..255.160 rows=100000 loops=1) > -> Seq Scan on t2 (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.097..110.639 rows=100000 loops=1) > Total runtime: 3790.831 ms > (10 registros) > > Sometimes I got a better result (on older versions) with this kind of > query, but in this case it doesn't: > > cruz=# EXPLAIN ANALYZE SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id WHERE t2.id IS NULL; > QUERY PLAN > ----------------------------------------------------------------------------------------------------------------------- > Merge Right Join (cost=30092.86..35251.53 rows=155304 width=8) (actual time=850.232..1671.091 rows=73653 loops=1) > Merge Cond: (t2.id = t1.id) > Filter: (t2.id IS NULL) > -> Sort (cost=9697.82..9947.82 rows=100000 width=4) (actual time=266.501..372.560 rows=100000 loops=1) > Sort Key: t2.id > Sort Method: quicksort Memory: 4392kB > -> Seq Scan on t2 (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.029..78.087 rows=100000 loops=1) > -> Sort (cost=20394.64..20894.64 rows=200000 width=4) (actual time=583.699..855.427 rows=273364 loops=1) > Sort Key: t1.id > Sort Method: quicksort Memory: 8784kB > -> Seq Scan on t1 (cost=0.00..2785.00 rows=200000 width=4) (actual time=0.087..155.665 rows=200000 loops=1) > Total runtime: 1717.062 ms > (12 registros) > > Yes, your method is even better on 8.3.3 I have. I will try to update to 8.3.5 to see if there was optimizer improvements. You could try increasing values, say, by 10 in table filling to see if NOT IT will switch to "slow" version (for me it starts being slow from some magic row count in t2). I suppose it is the moment it switches from "hashed subplan" to "subplan". For me for 10000 values it is "hashed subplan" (and it is momentary fast), for 100000 - it is "subplan" and it is sloow. BTW: Which (memory?) configuration variable can affect such a switch? ------=_Part_75322_25533135.1227107563908 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline

2008/11/19 DANIEL CRISTIAN CRUZ <daniel.cruz@sc.senai.br>

Something weird with your example which doesn't have the same result, see row count with explain analyze:

My fault. EXCEPT ALL would not work here, so this method with EXCEPT can be used only when either operation is done on unique key on t1 or result is going to be made unique. 

cruz=# SELECT version();
                                          version                                          
--------------------------------------------------------------------------------------------
 PostgreSQL 8.3.5 on i486-pc-linux-gnu, compiled by GCC gcc-4.3.real (Debian 4.3.2-1) 4.3.2
(1 registro)

cruz=# EXPLAIN ANALYZE select * from t1 where id not in (select id from t2);
                                                    QUERY PLAN                                                   
------------------------------------------------------------------------------------------------------------------
 Seq Scan on t1  (cost=1643.00..4928.00 rows=100000 width=4) (actual time=256.687..585.774 rows=73653 loops=1)
   Filter: (NOT (hashed subplan))
   SubPlan
     ->  Seq Scan on t2  (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.052..86.867 rows=100000 loops=1)
 Total runtime: 625.471 ms
(5 registros)

cruz=# EXPLAIN ANALYZE select * from t1 except all (select id from t2);
                                                               QUERY PLAN                                                               
-----------------------------------------------------------------------------------------------------------------------------------------
 SetOp Except All  (cost=34469.90..35969.90 rows=30000 width=4) (actual time=2598.574..3663.712 rows=126733 loops=1)
   ->  Sort  (cost=34469.90..35219.90 rows=300000 width=4) (actual time=2598.550..3178.387 rows=300000 loops=1)
         Sort Key: "*SELECT* 1".id
         Sort Method:  external merge  Disk: 5864kB
         ->  Append  (cost=0.00..7178.00 rows=300000 width=4) (actual time=0.037..1026.367 rows=300000 loops=1)
               ->  Subquery Scan "*SELECT* 1"  (cost=0.00..4785.00 rows=200000 width=4) (actual time=0.035..439.507 rows=200000 loops=1)
                     ->  Seq Scan on t1  (cost=0.00..2785.00 rows=200000 width=4) (actual time=0.029..161.355 rows=200000 loops=1)
               ->  Subquery Scan "*SELECT* 2"  (cost=0.00..2393.00 rows=100000 width=4) (actual time=0.107..255.160 rows=100000 loops=1)
                     ->  Seq Scan on t2  (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.097..110.639 rows=100000 loops=1)
 Total runtime: 3790.831 ms
(10 registros)

Sometimes I got a better result (on older versions) with this kind of query, but in this case it doesn't:

cruz=# EXPLAIN ANALYZE SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id WHERE t2.id IS NULL;
                                                      QUERY PLAN                                                      
-----------------------------------------------------------------------------------------------------------------------
 Merge Right Join  (cost=30092.86..35251.53 rows=155304 width=8) (actual time=850.232..1671.091 rows=73653 loops=1)
   Merge Cond: (t2.id = t1.id)
   Filter: (t2.id IS NULL)
   ->  Sort  (cost=9697.82..9947.82 rows=100000 width=4) (actual time=266.501..372.560 rows=100000 loops=1)
         Sort Key: t2.id
         Sort Method:  quicksort  Memory: 4392kB
         ->  Seq Scan on t2  (cost=0.00..1393.00 rows=100000 width=4) (actual time=0.029..78.087 rows=100000 loops=1)
   ->  Sort  (cost=20394.64..20894.64 rows=200000 width=4) (actual time=583.699..855.427 rows=273364 loops=1)
         Sort Key: t1.id
         Sort Method:  quicksort  Memory: 8784kB
         ->  Seq Scan on t1  (cost=0.00..2785.00 rows=200000 width=4) (actual time=0.087..155.665 rows=200000 loops=1)
 Total runtime: 1717.062 ms
(12 registros)

Yes, your method is even better on 8.3.3 I have. I will try to update to 8.3.5 to see if there was optimizer improvements. You could try increasing values, say, by 10 in table filling to see if NOT IT will switch to "slow" version (for me it starts being slow from some magic row count in t2). I suppose it is the moment it switches from "hashed subplan" to "subplan". For me for 10000 values it is "hashed subplan" (and it is momentary fast), for 100000 - it is "subplan" and it is sloow.
BTW: Which (memory?) configuration variable can affect such a switch?
------=_Part_75322_25533135.1227107563908--