X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id E64CA9DC99A for ; Wed, 14 Dec 2005 09:34:01 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 99923-01 for ; Wed, 14 Dec 2005 09:34:04 -0400 (AST) X-Greylist: delayed 00:06:37.615997 by SQLgrey- Received: from sapo.pt (relay6.ptmail.sapo.pt [212.55.154.26]) by postgresql.org (Postfix) with SMTP id 1648B9DC943 for ; Wed, 14 Dec 2005 09:33:58 -0400 (AST) Received: (qmail 25848 invoked by uid 0); 14 Dec 2005 13:27:23 -0000 Received: from unknown (HELO sapo.pt) (10.134.35.205) by relay6 with SMTP; 14 Dec 2005 13:27:23 -0000 Received: (qmail 31434 invoked from network); 14 Dec 2005 13:27:23 -0000 X-AntiVirus: PTMail-AV 0.3.87.1 X-Virus-Status: Clean (0.02268 seconds) Received: from unknown (HELO flintstone) (nop05020b@[81.193.91.110]) (envelope-sender ) by mta10 (qmail-ldap-1.03) with SMTP for ; 14 Dec 2005 13:27:23 -0000 From: To: Subject: Convert IN sublink to join Date: Wed, 14 Dec 2005 13:27:21 -0000 Message-ID: <000001c600b2$1ccb44e0$017ba8c0@flintstone> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0001_01C600B2.1CCB44E0" X-Mailer: Microsoft Office Outlook 11 Thread-Index: AcYAshydtVvyCU6JT6uypjEOaIrung== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=4.082 required=5 tests=[DEAR_SOMETHING=1.612, DNS_FROM_RFC_ABUSE=0.479, DNS_FROM_RFC_POST=1.44, HTML_MESSAGE=0.001, NO_REAL_NAME=0.55] X-Spam-Score: 4.082 X-Spam-Level: **** X-Archive-Number: 200512/328 X-Sequence-Number: 16149 This is a multi-part message in MIME format. ------=_NextPart_000_0001_01C600B2.1CCB44E0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Dear Sir or Madam: The function "convert_IN_to_join(Query *parse, SubLink *sublink)", from file: /src/backend/optimizer/plan/subselect.c, is responsible for converting IN type sublinks to joins, whenever appropriate. The following lines of code, extracted from convert_IN_to_join, verify if the subquery is correlated: /* * The sub-select must not refer to any Vars of the parent query. * (Vars of higher levels should be okay, though.) */ if (contain_vars_of_level((Node *) subselect, 1)) return NULL; By commenting this code region I was able to optimize several correlated subqueries. Apparently, the rest of the PostgreSQL code is ready to handle the "convert subquery to join" optimization. Is this test really necessary? Please analyze the following example: DDL: CREATE TABLE "students" ( sid char(5) primary key, name char(20) not null, age integer, email char(20) not null, unique( email ), avgrade float not null ); CREATE TABLE "enrolled" ( sid char(5), cid char(5), grade real not null, primary key(sid,cid), foreign key(sid) references students (sid) on delete restrict ); DML: 1) correlated IN subquery: "Find all students who's grade in 'TFC' class is higher than their average grade." select a.sid, a.name from students a where a.sid IN ( select i.sid from enrolled i where i.grade > a.avgrade AND i.cid = 'TFC'); QUERY PLAN: Seq Scan on students a (cost=0.00..5763804.50 rows=5000 width=33) Filter: (subplan) SubPlan -> Seq Scan on enrolled i (cost=0.00..1144.00 rows=3473 width=9) Filter: ((grade > $0) AND (cid = 'TFC'::bpchar)) 2) the same query after commenting out the above code region in convert_IN_to_join: QUERY PLAN: Hash Join (cost=1050.24..1518.21 rows=693 width=33) Hash Cond: ("outer".sid = "inner".sid) Join Filter: ("inner".grade > "outer".avgrade) -> Seq Scan on students a (cost=0.00..367.00 rows=10000 width=41) -> Hash (cost=1045.04..1045.04 rows=2078 width=13) -> HashAggregate (cost=1045.04..1045.04 rows=2078 width=13) -> Seq Scan on enrolled i (cost=0.00..1019.00 rows=10417 width=13) Filter: (cid = 'TFC'::bpchar) 3) Clearly, it is possible to extract the IN subquery from query 1 since the outer attribute a.sid matches, at most once, with the inner tuple i.sid. Although s.sid is not a primary key by itself, together with "i.cid = 'TFC'" conjunct, it forms a unique tuple. Here is an efficient alternative to query 1: select a.sid, a.name from students a, enrolled i where a.sid = i.sid AND i.cid = 'TFC' AND i.grade > a.avgrade; QUERY PLAN: Hash Join (cost=480.00..2366.86 rows=3473 width=33) Hash Cond: ("outer".sid = "inner".sid) Join Filter: ("outer".grade > "inner".avgrade) -> Seq Scan on enrolled i (cost=0.00..1019.00 rows=10417 width=13) Filter: (cid = 'TFC'::bpchar) -> Hash (cost=367.00..367.00 rows=10000 width=41) -> Seq Scan on students a (cost=0.00..367.00 rows=10000 width=41) I have verified that both 2) and 3) return the exact same tuples, query 1) never completed due to the highly inefficient execution plan. Please help me with this issue. Kind regards, Francisco Santos ------=_NextPart_000_0001_01C600B2.1CCB44E0 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Dear Sir or Madam:

Dear Sir or Madam:

The function "convert_IN_to_join(Query *parse, SubLink = *sublink)", from file: <postgres-8.0.4 = root>/src/backend/optimizer/plan/subselect.c, is responsible for converting IN type sublinks to joins, whenever appropriate.

The following lines of code, extracted from convert_IN_to_join, verify = if the subquery is correlated:

      /*
       * The sub-select must not refer to = any Vars of the parent query.
       * (Vars of higher levels should be = okay, though.)
       */
      if (contain_vars_of_level((Node *) = subselect, 1))
      =         return NULL;

By commenting this code region I was able to optimize several correlated subqueries. Apparently, the rest of the PostgreSQL code is ready to = handle the "convert subquery to join" optimization. Is this test really = necessary?

Please analyze the following example:

DDL:
CREATE TABLE "students" ( sid char(5) primary key, name = char(20) not null, age integer, email char(20) not null, unique( email ), avgrade = float not null );
CREATE TABLE "enrolled" ( sid char(5), cid char(5), grade real = not null, primary key(sid,cid), foreign key(sid) references students (sid) = on delete restrict  );

DML:

1) correlated IN subquery:
"Find all students who's grade in 'TFC' class is higher than their = average grade."
select a.sid, a.name from students a where a.sid IN ( select i.sid from enrolled i where i.grade > a.avgrade AND i.cid =3D 'TFC');

QUERY PLAN:

 Seq Scan on students a  (cost=3D0.00..5763804.50 rows=3D5000 = width=3D33)
   Filter: (subplan)
   SubPlan
     ->  Seq Scan on enrolled i  = (cost=3D0.00..1144.00 rows=3D3473 width=3D9)
           Filter: = ((grade > $0) AND (cid =3D 'TFC'::bpchar))

2) the same query after commenting out the above code region in convert_IN_to_join:

QUERY PLAN:

 Hash Join  (cost=3D1050.24..1518.21 rows=3D693 = width=3D33)
   Hash Cond: ("outer".sid =3D = "inner".sid)
   Join Filter: ("inner".grade > = "outer".avgrade)
   ->  Seq Scan on students a  = (cost=3D0.00..367.00 rows=3D10000 width=3D41)
   ->  Hash  (cost=3D1045.04..1045.04 rows=3D2078 = width=3D13)
         ->  = HashAggregate  (cost=3D1045.04..1045.04 rows=3D2078 width=3D13)
            &= nbsp;  ->  Seq Scan on enrolled i  = (cost=3D0.00..1019.00 rows=3D10417 width=3D13)
            &= nbsp;        Filter: (cid =3D = 'TFC'::bpchar)


3) Clearly, it is possible to extract the IN subquery from query 1 since = the outer attribute a.sid matches, at most once, with the inner tuple i.sid. Although s.sid is not a primary key by itself, together with "i.cid = =3D 'TFC'" conjunct, it forms a unique tuple. Here is an efficient = alternative to query 1:

select a.sid, a.name from students a, enrolled i where a.sid =3D i.sid = AND  i.cid =3D 'TFC' AND i.grade > a.avgrade;

QUERY PLAN:

 Hash Join  (cost=3D480.00..2366.86 rows=3D3473 = width=3D33)
   Hash Cond: ("outer".sid =3D = "inner".sid)
   Join Filter: ("outer".grade > = "inner".avgrade)
   ->  Seq Scan on enrolled i  = (cost=3D0.00..1019.00 rows=3D10417 width=3D13)
         Filter: (cid =3D = 'TFC'::bpchar)
   ->  Hash  (cost=3D367.00..367.00 rows=3D10000 = width=3D41)
         ->  Seq Scan on = students a  (cost=3D0.00..367.00 rows=3D10000 width=3D41)


I have verified that both 2) and 3) return the exact same tuples, query = 1) never completed due to the highly inefficient execution plan.
Please help me with this issue.

Kind regards,
Francisco Santos

 

------=_NextPart_000_0001_01C600B2.1CCB44E0--