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 38F429DC825 for ; Wed, 4 Jan 2006 00:12:57 -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 19708-01 for ; Wed, 4 Jan 2006 00:12:55 -0400 (AST) Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 86C619DC9A0 for ; Wed, 4 Jan 2006 00:12:54 -0400 (AST) Received: from mail.auptyma.com (64-60-124-12.cust.telepacific.net [64.60.124.12]) by svr4.postgresql.org (Postfix) with ESMTP id CC58C5AF03F for ; Wed, 4 Jan 2006 04:12:53 +0000 (GMT) Received: from demo1 (64-60-124-12.cust.telepacific.net [64.60.124.12]) (authenticated bits=0) by mail.auptyma.com (8.13.1/8.13.1) with ESMTP id k043rptv011136 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO) for ; Tue, 3 Jan 2006 19:53:52 -0800 Message-ID: <002b01c610e5$21cc7340$3100000a@demo1> From: "Virag Saksena" To: Subject: Avoiding cartesian product Date: Tue, 3 Jan 2006 20:12:51 -0800 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0028_01C610A2.12B02D40" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 X-Greylist: Sender succeded SMTP AUTH authentication, not delayed by milter-greylist-1.7.5 (mail.auptyma.com [10.0.0.47]); Tue, 03 Jan 2006 19:53:53 -0800 (PST) X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.001 required=5 tests=[HTML_MESSAGE=0.001] X-Spam-Score: 0.001 X-Spam-Level: X-Archive-Number: 200601/7 X-Sequence-Number: 16485 This is a multi-part message in MIME format. ------=_NextPart_000_0028_01C610A2.12B02D40 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I have a table which stores cumulative values I would like to display/chart the deltas between successive data = collections If my primary key only increments by 1, I could write a simple query select b.gc_minor - a.gc_minor, b.gc_major - a.gc_major from jam_trace_sys a, jam_trace_sys b where a.trace_id =3D 22 and b.trace_id =3D a.trace_id and b.seq_no =3D a.seq_no + 1 order by a.seq_no; However the difference in sequence number is variable. So (in Oracle) I used to extract the next seq_no using a correlated = sub-query select b.gc_minor - a.gc_minor, b.gc_major - a.gc_major from jam_trace_sys a, jam_trace_sys b where a.trace_id =3D 22 and (b.trace_id, b.seq_no) =3D (select a.trace_id, min(c.seq_no) from jam_trace_sys c where c.trace_id =3D a.trace_id and c.seq_no > a.seq_no) order by a.seq_no; For every row in A, The correlated sub-query from C will execute With an appropriate index, it will just descend the index Btree go one row to the right and return that row (min > :value) and join to table B SELECT STATEMENT SORT ORDER BY TABLE ACCESS BY INDEX ROWID JAM_TRACE_SYS B NESTED LOOPS TABLE ACCESS BY INDEX ROWID JAM_TRACE_SYS A INDEX RANGE SCAN JAM_TRACE_SYS_N1 A INDEX RANGE SCAN JAM_TRACE_SYS_N1 B SORT AGGREGATE INDEX RANGE SCAN JAM_TRACE_SYS_N1 C In postgreSQL A and B are doing a cartesian product then C gets executed for every row in this cartesian product and most of the extra rows get thrown out. Is there any way to force an execution plan like above where the = correlated subquery runs before going to B. The table is small right now, but it will grow to have millions of rows QUERY PLAN -------------------------------------------------------------------------= ---------------------------------------------------------- Sort (cost=3D124911.81..124944.84 rows=3D13213 width=3D20) (actual = time=3D13096.754..13097.053 rows=3D149 loops=3D1) Sort Key: a.seq_no -> Nested Loop (cost=3D4.34..124007.40 rows=3D13213 width=3D20) = (actual time=3D1948.300..13096.329 rows=3D149 loops=3D1) Join Filter: (subplan) -> Seq Scan on jam_trace_sys b (cost=3D0.00..3.75 rows=3D175 = width=3D16) (actual time=3D0.005..0.534 rows=3D175 loops=3D1) -> Materialize (cost=3D4.34..5.85 rows=3D151 width=3D16) = (actual time=3D0.002..0.324 rows=3D150 loops=3D175) -> Seq Scan on jam_trace_sys a (cost=3D0.00..4.19 = rows=3D151 width=3D16) (actual time=3D0.022..0.687 rows=3D150 loops=3D1) Filter: (trace_id =3D 22) SubPlan -> Aggregate (cost=3D4.67..4.67 rows=3D1 width=3D4) (actual = time=3D0.486..0.488 rows=3D1 loops=3D26250) -> Seq Scan on jam_trace_sys c (cost=3D0.00..4.62 = rows=3D15 width=3D4) (actual time=3D0.058..0.311 rows=3D74 = loops=3D26250) Filter: ((trace_id =3D $0) AND (seq_no > $1)) Total runtime: 13097.557 ms (13 rows) pglnx01=3D> \d jam_trace_sys Table "public.jam_trace_sys" Column | Type | Modifiers -----------------+---------+----------- trace_id | integer | seq_no | integer | cpu_utilization | integer | gc_minor | integer | gc_major | integer | heap_used | integer | Indexes: "jam_trace_sys_n1" btree (trace_id, seq_no) pglnx01=3D> select count(*) from jam_trace_Sys ; count ------- 175 (1 row) pglnx01=3D> select trace_id, count(*) from jam_trace_sys group by = trace_id ; trace_id | count ----------+------- 15 | 2 18 | 21 22 | 150 16 | 2 (4 rows) ------=_NextPart_000_0028_01C610A2.12B02D40 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable
I have a table which stores cumulative = values
I=20 would like to display/chart the deltas between successive data=20 collections
 
If my primary key only increments by 1, = I could=20 write a simple query
 
select b.gc_minor - a.gc_minor, = b.gc_major -=20 a.gc_major
  from jam_trace_sys a, jam_trace_sys = b
 where=20 a.trace_id =3D 22
   and b.trace_id =3D = a.trace_id
   and=20 b.seq_no =3D a.seq_no + 1
 order by a.seq_no;
 
However the difference in sequence = number is=20 variable.
So (in Oracle) I used to extract the next seq_no using a = correlated=20 sub-query
 
select b.gc_minor - a.gc_minor, = b.gc_major -=20 a.gc_major
from jam_trace_sys a, jam_trace_sys b
where a.trace_id = =3D=20 22
and (b.trace_id, b.seq_no) =3D
(select a.trace_id, = min(c.seq_no) from=20 jam_trace_sys c
where c.trace_id =3D a.trace_id and c.seq_no >=20 a.seq_no)
 order by a.seq_no;
 
For every row in A, The correlated = sub-query from C=20 will execute
With an appropriate index, it will just descend the = index=20 Btree
go one row to the right and return that row (min > = :value)
and=20 join to table B
 
SELECT STATEMENT
  SORT ORDER=20 BY
   TABLE ACCESS BY INDEX ROWID JAM_TRACE_SYS=20 B
     NESTED=20 LOOPS
       TABLE ACCESS BY INDEX = ROWID=20 JAM_TRACE_SYS  = A
         INDEX=20 RANGE SCAN JAM_TRACE_SYS_N1  = A
      =20 INDEX RANGE SCAN JAM_TRACE_SYS_N1=20 B
         SORT=20 AGGREGATE
          = INDEX=20 RANGE SCAN JAM_TRACE_SYS_N1 C
 
In postgreSQL A and B are doing a = cartesian=20 product
then C gets executed for every row in this cartesian = product
and=20 most of the extra rows get thrown out.
Is there any way to force an = execution=20 plan like above where the correlated subquery runs before going to = B.
The=20 table is small right now, but it will grow to have millions of=20 rows
QUERY=20 PLAN
-----------------------------------------------------------------= ------------------------------------------------------------------
&nb= sp;Sort =20 (cost=3D124911.81..124944.84 rows=3D13213 width=3D20) (actual=20 time=3D13096.754..13097.053 rows=3D149 loops=3D1)
   Sort = Key:=20 a.seq_no
   ->  Nested Loop  = (cost=3D4.34..124007.40=20 rows=3D13213 width=3D20) (actual time=3D1948.300..13096.329 rows=3D149=20 loops=3D1)
         Join = Filter:=20 (subplan)
         = ->  Seq=20 Scan on jam_trace_sys b  (cost=3D0.00..3.75 rows=3D175 width=3D16) = (actual=20 time=3D0.005..0.534 rows=3D175=20 loops=3D1)
         = -> =20 Materialize  (cost=3D4.34..5.85 rows=3D151 width=3D16) (actual = time=3D0.002..0.324=20 rows=3D150=20 loops=3D175)
         &nb= sp;    =20 ->  Seq Scan on jam_trace_sys a  (cost=3D0.00..4.19 = rows=3D151=20 width=3D16) (actual time=3D0.022..0.687 rows=3D150=20 loops=3D1)
          = ;          =20 Filter: (trace_id =3D = 22)
        =20 SubPlan
          =20 ->  Aggregate  (cost=3D4.67..4.67 rows=3D1 width=3D4) = (actual=20 time=3D0.486..0.488 rows=3D1=20 loops=3D26250)
         &= nbsp;      =20 ->  Seq Scan on jam_trace_sys c  (cost=3D0.00..4.62 = rows=3D15 width=3D4)=20 (actual time=3D0.058..0.311 rows=3D74=20 loops=3D26250)
         &= nbsp;           &n= bsp;=20 Filter: ((trace_id =3D $0) AND (seq_no > $1))
 Total runtime: = 13097.557=20 ms
(13 rows)
 
pglnx01=3D> \d=20 jam_trace_sys
     Table=20 "public.jam_trace_sys"
    =20 Column      |  Type   |=20 Modifiers
-----------------+---------+-----------
 trace_id&nb= sp;      =20 | integer=20 |
 seq_no          = |=20 integer |
 cpu_utilization | integer=20 |
 gc_minor        | integer=20 |
 gc_major        | integer=20 |
 heap_used       | integer=20 |
Indexes:
    "jam_trace_sys_n1" btree (trace_id,=20 seq_no)
 
pglnx01=3D> select count(*) from = jam_trace_Sys=20 ;
 count
-------
   175
(1 row)
 
pglnx01=3D> select trace_id, = count(*) from=20 jam_trace_sys group by trace_id ;
 trace_id |=20 count
----------+-------
       15=20 |     2
       18=20 |    21
       22 = |  =20 150
       16 |     = 2
(4=20 rows)
------=_NextPart_000_0028_01C610A2.12B02D40--