Received: from localhost (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id 47EBE64FCFB for ; Wed, 19 Nov 2008 08:50:11 -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 47026-10 for ; Wed, 19 Nov 2008 08:50:07 -0400 (AST) X-Greylist: delayed 00:27:42.878749 by SQLgrey-1.7.6 Received: from mail.sc.senai.br (mail.sc.senai.br [201.34.162.10]) by mail.postgresql.org (Postfix) with ESMTP id 3D2FD64FC5A for ; Wed, 19 Nov 2008 08:50:05 -0400 (AST) Received: from localhost (localhost.localdomain [127.0.0.1]) by mail.sc.senai.br (Postfix) with ESMTP id B516B18386; Wed, 19 Nov 2008 10:22:11 -0200 (BRST) X-Virus-Scanned: amavisd-new at mail.sc.senai.br Received: from mail.sc.senai.br ([127.0.0.1]) by localhost (mail.sc.senai.br [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kZTM7oxXlKdf; Wed, 19 Nov 2008 10:22:06 -0200 (BRST) Received: from intranet.sc.senai.br (unknown [10.1.3.1]) by mail.sc.senai.br (Postfix) with ESMTP id 2A124183BE; Wed, 19 Nov 2008 10:22:06 -0200 (BRST) Received: from phpmailer ([10.1.121.204]) by intranet.sc.senai.br with HTTP (PHPMailer); Wed, 19 Nov 2008 10:22:06 -0200 Date: Wed, 19 Nov 2008 10:22:06 -0200 To: ??????? ???????? , pgsql-performance@postgresql.org From: DANIEL CRISTIAN CRUZ Subject: Re: PostgreSQL NOT IN performance Message-ID: <91db404146cba5910fcafdba91db5b9b@intranet.sc.senai.br> X-Priority: 3 X-Mailer: PHPMailer [version 1.71] X-Mailer: FeLaMiMail In-Reply-To: <331e40660811190351n6bde6caic5fd8cc3a0f777d2@mail.gmail.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="b1_91db404146cba5910fcafdba91db5b9b" X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.001 tagged_above=0 required=5 tests=HTML_MESSAGE=0.001 X-Spam-Level: X-Archive-Number: 200811/161 X-Sequence-Number: 31892 --b1_91db404146cba5910fcafdba91db5b9b Content-Type: text/plain; charset = "iso-8859-1" Content-Transfer-Encoding: quoted-printable Something weird with your example which doesn't have the same result, see row count with explain analyze: cruz=3D# SELECT version(); version = =20 =20 --------------------------------------------------------------------------= ------------------ 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=3D# EXPLAIN ANALYZE select * from t1 where id not in (select id from t2); QUERY PLAN = =20 =20 --------------------------------------------------------------------------= ---------------------------------------- Seq Scan on t1 (cost=3D1643.00..4928.00 rows=3D100000 width=3D4) (actual time=3D256.687..585.774 rows=3D73653 loops=3D1) Filter: (NOT (hashed subplan)) SubPlan -> Seq Scan on t2 (cost=3D0.00..1393.00 rows=3D100000 width=3D4) = (actual time=3D0.052..86.867 rows=3D100000 loops=3D1) Total runtime: 625.471 ms (5 registros) cruz=3D# EXPLAIN ANALYZE select * from t1 except all (select id from t2); QUERY PLAN = =20 =20 --------------------------------------------------------------------------= --------------------------------------------------------------- SetOp Except All (cost=3D34469.90..35969.90 rows=3D30000 width=3D4) = (actual time=3D2598.574..3663.712 rows=3D126733 loops=3D1) -> Sort (cost=3D34469.90..35219.90 rows=3D300000 width=3D4) (actual time=3D2598.550..3178.387 rows=3D300000 loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0 Sort Key: "*SELECT* 1".id =A0=A0=A0=A0=A0=A0=A0=A0 Sort Method:=A0 external merge=A0 Disk: 5864kB =A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Append=A0 (cost=3D0.00..7178.00 = rows=3D300000 width=3D4) (actual time=3D0.037..1026.367 rows=3D300000 loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Subquery Scan "*SELECT* = 1"=A0 (cost=3D0.00..4785.00 rows=3D200000 width=3D4) (actual time=3D0.035..439.507 rows=3D200000 = loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq = Scan on t1=A0 (cost=3D0.00..2785.00 rows=3D200000 width=3D4) (actual time=3D0.029..161.355 rows=3D200000 loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Subquery Scan "*SELECT* = 2"=A0 (cost=3D0.00..2393.00 rows=3D100000 width=3D4) (actual time=3D0.107..255.160 rows=3D100000 = loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq = Scan on t2=A0 (cost=3D0.00..1393.00 rows=3D100000 width=3D4) (actual time=3D0.097..110.639 rows=3D100000 loops=3D1) =A0Total 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=3D# EXPLAIN ANALYZE SELECT * FROM t1 LEFT JOIN t2 ON t1.id =3D t2.id = WHERE t2.id IS NULL; =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0 QUERY PLAN=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0=A0 --------------------------------------------------------------------------= --------------------------------------------- =A0Merge Right Join=A0 (cost=3D30092.86..35251.53 rows=3D155304 width=3D8) = (actual time=3D850.232..1671.091 rows=3D73653 loops=3D1) =A0=A0 Merge Cond: (t2.id =3D t1.id) =A0=A0 Filter: (t2.id IS NULL) =A0=A0 ->=A0 Sort=A0 (cost=3D9697.82..9947.82 rows=3D100000 width=3D4) = (actual time=3D266.501..372.560 rows=3D100000 loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0 Sort Key: t2.id =A0=A0=A0=A0=A0=A0=A0=A0 Sort Method:=A0 quicksort=A0 Memory: 4392kB =A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq Scan on t2=A0 (cost=3D0.00..1393.00 = rows=3D100000 width=3D4) (actual time=3D0.029..78.087 rows=3D100000 loops=3D1) =A0=A0 ->=A0 Sort=A0 (cost=3D20394.64..20894.64 rows=3D200000 width=3D4) = (actual time=3D583.699..855.427 rows=3D273364 loops=3D1) =A0=A0=A0=A0=A0=A0=A0=A0 Sort Key: t1.id =A0=A0=A0=A0=A0=A0=A0=A0 Sort Method:=A0 quicksort=A0 Memory: 8784kB =A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq Scan on t1=A0 (cost=3D0.00..2785.00 = rows=3D200000 width=3D4) (actual time=3D0.087..155.665 rows=3D200000 loops=3D1) =A0Total runtime: 1717.062 ms (12 registros) Regards, "??????? ????????" escreveu: >Hello. > >It's second query rewrite postgresql seems not to handle - making EXCEPT >from NOT IT. >Here is an example: >Preparation: > >drop table if exists t1; >drop table if exists t2; >create temporary table t1(id) as=20 >select=20 >(random()*100000)::int from generate_series(1,200000) a(id); > >create temporary table t2(id) as=20 >select=20 >(random()*100000)::int from generate_series(1,100000) a(id); >analyze t1; >analyze t2; > >Query 1: >select * from t1 where id not in (select id from t2); >Plan: >"Seq Scan on t1=A0 (cost=3D1934.00..164105319.00 rows=3D100000 = width=3D4)" >"=A0 Filter: (NOT (subplan))" >"=A0 SubPlan" >"=A0=A0=A0 ->=A0 Materialize=A0 (cost=3D1934.00..3325.00 rows=3D100000 = width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq Scan on t2=A0 = (cost=3D0.00..1443.00 rows=3D100000 width=3D4)" > >Query 2 (gives same result as Q1): >select * from t1 except all (select id from t2); >Plan: >"SetOp Except All=A0 (cost=3D38721.90..40221.90 rows=3D30000 width=3D4)" >"=A0 ->=A0 Sort=A0 (cost=3D38721.90..39471.90 rows=3D300000 width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0 Sort Key: "*SELECT* 1".id" >"=A0=A0=A0=A0=A0=A0=A0 ->=A0 Append=A0 (cost=3D0.00..7328.00 = rows=3D300000 width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Subquery Scan "*SELECT* = 1"=A0 (cost=3D0.00..4885.00 >rows=3D200000 width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq Scan = on t1=A0 (cost=3D0.00..2885.00 rows=3D200000 >width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Subquery Scan "*SELECT* = 2"=A0 (cost=3D0.00..2443.00 >rows=3D100000 width=3D4)" >"=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ->=A0 Seq Scan = on t2=A0 (cost=3D0.00..1443.00 rows=3D100000 >width=3D4)" > >If I am correct, planner simply do not know that he can rewrite NOT IN as >"EXCEPT ALL" operator, so all NOT INs when list of values to remove is = long >takes very much time. >So the question is: I am willing to participate in postgresql development >because it may be easier to fix planner then to rewrite all my queries = :). >How can I? (I mean to work on query planner enhancements by providing new >options of query rewrite, not to work on other thing nor on enhancing >planner in other ways, like better estimations of known plans). > > > > =A0 -- Daniel Cristian Cruz Administrador de Banco de Dados Dire=E7=E3o Regional=A0- N=FAcleo de Tecnologia da Informa=E7=E3o SENAI - SC Telefone: 48-3239-1422 (ramal 1422) --b1_91db404146cba5910fcafdba91db5b9b Content-Type: text/html; charset = "iso-8859-1" Content-Transfer-Encoding: quoted-printable

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

cruz=3D# SELECT version();
                                          version                          =
               =20
--------------------------------------------------------------------------=
------------------
 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=3D# EXPLAIN ANALYZE select * from t1 where id not in (select id from =
t2);
                                                    QUERY PLAN             =
                                     =20
--------------------------------------------------------------------------=
----------------------------------------
 Seq Scan on t1  (cost=3D1643.00..4928.00 rows=3D100000 width=3D4) (actual =
time=3D256.687..585.774 rows=3D73653 loops=3D1)
   Filter: (NOT (hashed subplan))
   SubPlan
     ->  Seq Scan on t2  (cost=3D0.00..1393.00 rows=3D100000 width=3D4) =
(actual time=3D0.052..86.867 rows=3D100000 loops=3D1)
 Total runtime: 625.471 ms
(5 registros)

cruz=3D# EXPLAIN ANALYZE select * from t1 except all (select id from t2);
                                                               QUERY PLAN  =
                                                            =20
--------------------------------------------------------------------------=
---------------------------------------------------------------
 SetOp Except All  (cost=3D34469.90..35969.90 rows=3D30000 width=3D4) =
(actual time=3D2598.574..3663.712 rows=3D126733 loops=3D1)
   ->  Sort  (cost=3D34469.90..35219.90 rows=3D300000 width=3D4) =
(actual time=3D2598.550..3178.387 rows=3D300000 loops=3D1)
         Sort Key: "*SELECT* 1".id
         Sort Method:  =
external merge  Disk: 5864kB
         ->  Append  =
(cost=3D0.00..7178.00 rows=3D300000 width=3D4) (actual =
time=3D0.037..1026.367 rows=3D300000 loops=3D1)
            &#=
160;  ->  Subquery Scan "*SELECT* 1"  =
(cost=3D0.00..4785.00 rows=3D200000 width=3D4) (actual =
time=3D0.035..439.507 rows=3D200000 loops=3D1)
            &#=
160;        ->  Seq Scan on =
t1  (cost=3D0.00..2785.00 rows=3D200000 width=3D4) (actual =
time=3D0.029..161.355 rows=3D200000 loops=3D1)
            &#=
160;  ->  Subquery Scan "*SELECT* 2"  =
(cost=3D0.00..2393.00 rows=3D100000 width=3D4) (actual =
time=3D0.107..255.160 rows=3D100000 loops=3D1)
            &#=
160;        ->  Seq Scan on =
t2  (cost=3D0.00..1393.00 rows=3D100000 width=3D4) (actual =
time=3D0.097..110.639 rows=3D100000 loops=3D1)
 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=3D# EXPLAIN ANALYZE SELECT * FROM t1 LEFT JOIN t2 ON t1.id =3D t2.id =
WHERE t2.id IS NULL;
            &#=
160;           =
0;            =
            &#=
160;    QUERY PLAN       =
;            &=
#160;           =
60;            =
;          
--------------------------------------------------------------------------=
---------------------------------------------
 Merge Right Join  (cost=3D30092.86..35251.53 rows=3D155304 =
width=3D8) (actual time=3D850.232..1671.091 rows=3D73653 loops=3D1)
   Merge Cond: (t2.id =3D t1.id)
   Filter: (t2.id IS NULL)
   ->  Sort  (cost=3D9697.82..9947.82 rows=3D100000 =
width=3D4) (actual time=3D266.501..372.560 rows=3D100000 loops=3D1)
         Sort Key: t2.id
         Sort Method:  =
quicksort  Memory: 4392kB
         ->  Seq Scan on =
t2  (cost=3D0.00..1393.00 rows=3D100000 width=3D4) (actual =
time=3D0.029..78.087 rows=3D100000 loops=3D1)
   ->  Sort  (cost=3D20394.64..20894.64 =
rows=3D200000 width=3D4) (actual time=3D583.699..855.427 rows=3D273364 =
loops=3D1)
         Sort Key: t1.id
         Sort Method:  =
quicksort  Memory: 8784kB
         ->  Seq Scan on =
t1  (cost=3D0.00..2785.00 rows=3D200000 width=3D4) (actual =
time=3D0.087..155.665 rows=3D200000 loops=3D1)
 Total runtime: 1717.062 ms
(12 registros)

Regards,

"??????? ????????" <tivv00@gmail.com> escreveu:

Hello.

It's second query rewrite postgresql seems not to handle - making EXCEPT = from NOT IT.
Here is an example:
Preparation:

drop table if exists t1;
drop table if exists t2;
create temporary table t1(id) as
select
(random()*100000)::int from generate_series(1,200000) a(id);

create temporary table t2(id) as
select
(random()*100000)::int from generate_series(1,100000) a(id);
analyze t1;
analyze t2;

Query 1:
select * from t1 where id not in (select id from t2);
Plan:
"Seq Scan on t1  (cost=3D1934.00..164105319.00 rows=3D100000 = width=3D4)"
"  Filter: (NOT (subplan))"
"  SubPlan"
"    ->  Materialize  (cost=3D1934.00..3325.00 = rows=3D100000 width=3D4)"
"          ->  Seq = Scan on t2  (cost=3D0.00..1443.00 rows=3D100000 width=3D4)"

Query 2 (gives same result as Q1):
select * from t1 except all (select id from t2);
Plan:
"SetOp Except All  (cost=3D38721.90..40221.90 rows=3D30000 = width=3D4)"
"  ->  Sort  (cost=3D38721.90..39471.90 rows=3D300000 = width=3D4)"
"        Sort Key: "*SELECT* 1".id"
"        ->  Append  = (cost=3D0.00..7328.00 rows=3D300000 width=3D4)"
"            &= #160; ->  Subquery Scan "*SELECT* 1"  (cost=3D0.00..4885.00 = rows=3D200000 width=3D4)"
"            &= #160;       ->  Seq Scan on t1  = (cost=3D0.00..2885.00 rows=3D200000 width=3D4)"
"            &= #160; ->  Subquery Scan "*SELECT* 2"  (cost=3D0.00..2443.00 = rows=3D100000 width=3D4)"
"            &= #160;       ->  Seq Scan on t2  = (cost=3D0.00..1443.00 rows=3D100000 width=3D4)"

If I am correct, planner simply do not know that he can rewrite NOT IN as = "EXCEPT ALL" operator, so all NOT INs when list of values to remove is = long takes very much time.
So the question is: I am willing to participate in postgresql development = because it may be easier to fix planner then to rewrite all my queries :). = How can I? (I mean to work on query planner enhancements by providing new = options of query rewrite, not to work on other thing nor on enhancing = planner in other ways, like better estimations of known plans).



 


Daniel Cristian Cruz
Administrador de Banco de Dados
Dire=E7=E3o Regional - N=FAcleo de Tecnologia da = Informa=E7=E3o
SENAI - SC
Telefone: 48-3239-1422 (ramal 1422)

--b1_91db404146cba5910fcafdba91db5b9b--