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 DF1C59DCA2E for ; Mon, 20 Feb 2006 02:42:41 -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 13954-05 for ; Mon, 20 Feb 2006 02:42:41 -0400 (AST) Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 06AFF9DC99C for ; Mon, 20 Feb 2006 02:42:39 -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 AAB975AF02D for ; Mon, 20 Feb 2006 06:42:39 +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 k1K6Kl6Y012525 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO); Sun, 19 Feb 2006 22:20:49 -0800 Message-ID: <002c01c635e8$cfc225d0$3100000a@demo1> From: "Virag Saksena" To: "=?UTF-8?B?U3rFsWNzIEfDoWJvcg==?=" , References: <002b01c610e5$21cc7340$3100000a@demo1> <43C28854.9000605@gmail.com> Subject: Re: Avoiding cartesian product Date: Sun, 19 Feb 2006 22:42:23 -0800 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0029_01C635A5.C01622F0" 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]); Sun, 19 Feb 2006 22:20:49 -0800 (PST) X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.121 required=5 tests=[AWL=0.120, HTML_MESSAGE=0.001] X-Spam-Score: 0.121 X-Spam-Level: X-Archive-Number: 200602/317 X-Sequence-Number: 17303 This is a multi-part message in MIME format. ------=_NextPart_000_0029_01C635A5.C01622F0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Sz=C5=B1cs, Thanks for your suggestion, I guess there is more than one way to = attack the problem. I ended up using a trick with limit to get the next row ... select (b.gc_minor- a.gc_minor), (b.gc_major- a.gc_major) from jam_trace_sys a join jam_trace_sys b on (b.seq_no =3D (select 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 c.trace_id, c.seq_no limit 1) and b.trace_id =3D a.trace_id), jam_tracesnap s1, jam_tracesnap s2 where s1.trace_id =3D a.trace_id and s1.seq_no =3D a.seq_no and s2.trace_id =3D b.trace_id and s2.seq_no =3D b.seq_no and a.trace_id =3D 22 order by a.seq_no; This gave me a nice clean execution plan (there are some extra sources = listed, but that is a bug in postgresql) ... QUERY PLAN -------------------------------------------------------------------------= -------------------------------------------------------------------------= --------- Sort (cost=3D11.24..11.25 rows=3D1 width=3D20) (actual = time=3D0.040..0.040 rows=3D0 loops=3D1) Sort Key: a.seq_no ->Nested Loop (cost=3D0.00..11.23 rows=3D1 width=3D20) (actual = time=3D0.028..0.028 rows=3D0 loops=3D1) Join Filter: ("inner".seq_no =3D "outer".seq_no) ->Nested Loop (cost=3D0.00..9.20 rows=3D1 width=3D32) (actual = time=3D0.024..0.024 rows=3D0 loops=3D1) Join Filter: ("inner".seq_no =3D "outer".seq_no) ->Nested Loop (cost=3D0.00..7.17 rows=3D1 width=3D32) (actual = time=3D0.020..0.020 rows=3D0 loops=3D1) Join Filter: ("inner".seq_no =3D (subplan)) ->Index Scan using jam_trace_sys_n1 on jam_trace_sys a = (cost=3D0.00..3.41 rows=3D1 width=3D16) (actual time=3D0.016..0.016 = rows=3D0 loops=3D1) Index Cond: (trace_id =3D 22) ->Index Scan using jam_trace_sys_n1 on jam_trace_sys b = (cost=3D0.00..3.41 rows=3D1 width=3D16) (never executed) Index Cond: (22 =3D trace_id) SubPlan ->Limit (cost=3D0.00..0.33 rows=3D1 width=3D8) (never = executed) ->Index Scan using jam_trace_sys_n1 on jam_trace_sys c = (cost=3D0.00..6.36 rows=3D19 width=3D8) (never executed) Index Cond: ((trace_id =3D $0) AND (seq_no > $1)) ->Index Scan using jam_tracesnap_n1 on jam_tracesnap s1 = (cost=3D0.00..2.01 rows=3D1 width=3D8) (never executed) Index Cond: (22 =3D trace_id) ->Index Scan using jam_tracesnap_n1 on jam_tracesnap s2 = (cost=3D0.00..2.01 rows=3D1 width=3D8) (never executed) Index Cond: (22 =3D trace_id) Regards, Virag ----- Original Message -----=20 From: "Sz=C5=B1cs G=C3=A1bor" To: Sent: Monday, January 09, 2006 7:59 AM Subject: Re: Avoiding cartesian product > Dear Virag, >=20 > AFAIK aggregates aren't indexed in postgres (at least not before 8.1, = which=20 > indexes min and max, iirc). >=20 > Also, I don't think you need to exactly determine the trace_id. Try = this one=20 > (OTOH; might be wrong): >=20 > select DISTINCT ON (a.trace_id, a.seq_no) -- See below > 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 > a.seq_no -- Simply ">" is enough > order by a.trace_id, a.seq_no, b.seq_no; -- DISTINCT, see below >=20 > The trick is that DISTINCT takes the first one in each group (IIRC it = is=20 > granted, at least someone told me on one of these lists :) ) so if you = order=20 > by the DISTINCT attributes and then by b.seq_no, you'll get the = smallest of=20 > appropriate b.seq_no values for each DISTINCT values. >=20 > The idea of DISTINCTing by both columns is to make sure the planner = finds=20 > the index. (lately I had a similar problem: WHERE a=3D1 ORDER BY b = LIMIT 1=20 > used an index on b, instead of an (a,b) index. Using ORDER BY a,b = solved it) >=20 > HTH, >=20 > -- > G. >=20 >=20 > On 2006.01.04. 5:12, Virag Saksena wrote: > >=20 > > I have a table which stores cumulative values > > I would like to display/chart the deltas between successive data=20 > > collections > > =20 > > If my primary key only increments by 1, I could write a simple query > > =20 > > 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; > > =20 > > However the difference in sequence number is variable. > > So (in Oracle) I used to extract the next seq_no using a correlated=20 > > sub-query > > =20 > > 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; > > =20 > > 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 > > =20 > > 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 > > =20 > > 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=20 > > 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=20 > > 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=20 > > width=3D16) (actual time=3D0.005..0.534 rows=3D175 loops=3D1) > > -> Materialize (cost=3D4.34..5.85 rows=3D151 width=3D16) = (actual=20 > > time=3D0.002..0.324 rows=3D150 loops=3D175) > > -> Seq Scan on jam_trace_sys a (cost=3D0.00..4.19=20 > > 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=20 > > 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) > > =20 > > 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) > > =20 > > pglnx01=3D> select count(*) from jam_trace_Sys ; > > count > > ------- > > 175 > > (1 row) > > =20 > > 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) >=20 ------=_NextPart_000_0029_01C635A5.C01622F0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =EF=BB=BF
Sz=C5=B1cs,
    Thanks for your = suggestion, I=20 guess there is more than one way to attack the problem.
 
I ended up using a trick with limit to = get the next=20 row ...
 
select (b.gc_minor- a.gc_minor), = (b.gc_major-=20 a.gc_major)
from jam_trace_sys a join jam_trace_sys b on
(b.seq_no = =3D=20 (select c.seq_no from jam_trace_sys c
 where c.trace_id =3D = a.trace_id and=20 c.seq_no > a.seq_no
 order by c.trace_id, c.seq_no limit=20 1)
 and b.trace_id =3D a.trace_id),
jam_tracesnap s1, = jam_tracesnap=20 s2
where s1.trace_id =3D a.trace_id
and s1.seq_no =3D = a.seq_no
and=20 s2.trace_id =3D b.trace_id
and s2.seq_no =3D b.seq_no
and = a.trace_id =3D=20 22
order by a.seq_no;
 
This gave me a nice clean execution = plan (there are=20 some extra sources listed, but that is a bug in postgresql) = ...
 
QUERY=20 PLAN
-----------------------------------------------------------------= -------------------------------------------------------------------------= -----------------
Sort =20 (cost=3D11.24..11.25 rows=3D1 width=3D20) (actual time=3D0.040..0.040 = rows=3D0=20 loops=3D1)
 Sort Key: a.seq_no
 ->Nested Loop =20 (cost=3D0.00..11.23 rows=3D1 width=3D20) (actual time=3D0.028..0.028 = rows=3D0=20 loops=3D1)
    Join Filter: ("inner".seq_no =3D=20 "outer".seq_no)
    ->Nested Loop  = (cost=3D0.00..9.20=20 rows=3D1 width=3D32) (actual time=3D0.024..0.024 rows=3D0=20 loops=3D1)
       Join Filter: = ("inner".seq_no =3D=20 "outer".seq_no)
       ->Nested = Loop =20 (cost=3D0.00..7.17 rows=3D1 width=3D32) (actual time=3D0.020..0.020 = rows=3D0=20 loops=3D1)
          = Join Filter:=20 ("inner".seq_no =3D=20 (subplan))
          = ->Index=20 Scan using jam_trace_sys_n1 on jam_trace_sys a  (cost=3D0.00..3.41 = rows=3D1=20 width=3D16) (actual time=3D0.016..0.016 rows=3D0=20 loops=3D1)
          = ;  =20 Index Cond: (trace_id =3D=20 22)
          ->Index = Scan=20 using jam_trace_sys_n1 on jam_trace_sys b  (cost=3D0.00..3.41 = rows=3D1=20 width=3D16) (never=20 executed)
          =   =20 Index Cond: (22 =3D=20 trace_id)
         =20 SubPlan
         =20 ->Limit  (cost=3D0.00..0.33 rows=3D1 width=3D8) (never=20 executed)
          =  =20 ->Index Scan using jam_trace_sys_n1 on jam_trace_sys c  = (cost=3D0.00..6.36=20 rows=3D19 width=3D8) (never=20 executed)
          =     =20 Index Cond: ((trace_id =3D $0) AND (seq_no >=20 $1))
       ->Index Scan using=20 jam_tracesnap_n1 on jam_tracesnap s1  (cost=3D0.00..2.01 rows=3D1 = width=3D8)=20 (never = executed)
          = Index=20 Cond: (22 =3D trace_id)
    ->Index Scan using=20 jam_tracesnap_n1 on jam_tracesnap s2  (cost=3D0.00..2.01 rows=3D1 = width=3D8)=20 (never executed)
       Index Cond: (22 = =3D=20 trace_id)
Regards,
 
Virag
----- Original Message -----
From: "Sz=C5=B1cs G=C3=A1bor" = <surrano@gmail.com>
To: <pgsql-performance@postgresql.org>
Sent: Monday, January 09, 2006 7:59 = AM
Subject: Re: Avoiding cartesian=20 product

> Dear Virag,
>
> AFAIK aggregates aren't = indexed in=20 postgres (at least not before 8.1, which
> indexes min and max,=20 iirc).
>
> Also, I don't think you need to exactly = determine the=20 trace_id. Try this one
> (OTOH; might be wrong):
>
> = select=20 DISTINCT ON (a.trace_id, a.seq_no) -- See below
>    = b.gc_minor=20 - a.gc_minor, b.gc_major - a.gc_major
> from jam_trace_sys a,=20 jam_trace_sys b
> where a.trace_id =3D 22
>    and = b.trace_id =3D a.trace_id
>    and b.seq_no > = a.seq_no --=20 Simply ">" is enough
> order by a.trace_id, a.seq_no, b.seq_no; = --=20 DISTINCT, see below
>
> The trick is that DISTINCT takes = the first=20 one in each group (IIRC it is
> granted, at least someone told me = on one=20 of these lists :) ) so if you order
> by the DISTINCT attributes = and then=20 by b.seq_no, you'll get the smallest of
> appropriate b.seq_no = values for=20 each DISTINCT values.
>
> The idea of DISTINCTing by both = columns=20 is to make sure the planner finds
> the index. (lately I had a = similar=20 problem: WHERE a=3D1 ORDER BY b LIMIT 1
> used an index on b, = instead of an=20 (a,b) index. Using ORDER BY a,b solved it)
>
> HTH,
> =
> --
> G.
>
>
> On 2006.01.04. 5:12, = Virag=20 Saksena wrote:
> >
> > I have a table which stores = cumulative=20 values
> > I would like to display/chart the deltas between = successive=20 data
> > collections
> > 
> > If my = primary=20 key only increments by 1, I could write a simple query
> = > =20
> > select b.gc_minor - a.gc_minor, b.gc_major - = a.gc_major
>=20 >   from jam_trace_sys a, jam_trace_sys b
> = >  where=20 a.trace_id =3D 22
> >    and b.trace_id =3D=20 a.trace_id
> >    and b.seq_no =3D a.seq_no + = 1
>=20 >  order by a.seq_no;
> > 
> > However = the=20 difference in sequence number is variable.
> > So (in Oracle) I = used to=20 extract the next seq_no using a correlated
> > = sub-query
>=20 > 
> > 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, b.seq_no) =3D
> = > (select=20 a.trace_id, min(c.seq_no) from jam_trace_sys c
> > where = c.trace_id =3D=20 a.trace_id and c.seq_no > a.seq_no)
> >  order by=20 a.seq_no;
> > 
> > For every row in A, The = correlated=20 sub-query from C will execute
> > With an appropriate index, it = will=20 just descend the index Btree
> > go one row to the right and = return=20 that row (min > :value)
> > and join to table B
> = > =20
> > SELECT STATEMENT
> >   SORT ORDER = BY
>=20 >    TABLE ACCESS BY INDEX ROWID JAM_TRACE_SYS = B
>=20 >      NESTED LOOPS
>=20 >        TABLE ACCESS BY INDEX = ROWID=20 JAM_TRACE_SYS  A
>=20 >          INDEX RANGE = SCAN=20 JAM_TRACE_SYS_N1  A
> = >       =20 INDEX RANGE SCAN JAM_TRACE_SYS_N1 B
>=20 >          SORT=20 AGGREGATE
>=20 >            = INDEX=20 RANGE SCAN JAM_TRACE_SYS_N1 C
> > 
> > In = postgreSQL A=20 and B are doing a cartesian product
> > then C gets executed = for every=20 row in this cartesian product
> > and most of the extra rows = get thrown=20 out.
> > Is there any way to force an execution plan like above = where=20 the
> > correlated subquery runs before going to B.
> = > The=20 table is small right now, but it will grow to have millions of = rows
> >=20 QUERY PLAN
> >=20 -------------------------------------------------------------------------= ----------------------------------------------------------
>=20 >  Sort  (cost=3D124911.81..124944.84 rows=3D13213 = width=3D20) (actual=20
> > time=3D13096.754..13097.053 rows=3D149 loops=3D1)
>=20 >    Sort Key: a.seq_no
> >    = ->  Nested Loop  (cost=3D4.34..124007.40 rows=3D13213 = width=3D20) (actual=20
> > time=3D1948.300..13096.329 rows=3D149 loops=3D1)
>=20 >          Join Filter:=20 (subplan)
> = >         =20 ->  Seq Scan on jam_trace_sys b  (cost=3D0.00..3.75 = rows=3D175
>=20 > width=3D16) (actual time=3D0.005..0.534 rows=3D175 = loops=3D1)
>=20 >          -> =20 Materialize  (cost=3D4.34..5.85 rows=3D151 width=3D16) (actual =
> >=20 time=3D0.002..0.324 rows=3D150 loops=3D175)
>=20 >           &nb= sp;   =20 ->  Seq Scan on jam_trace_sys a  (cost=3D0.00..4.19 =
> >=20 rows=3D151 width=3D16) (actual time=3D0.022..0.687 rows=3D150 = loops=3D1)
>=20 >           &nb= sp;         =20 Filter: (trace_id =3D 22)
>=20 >          = SubPlan
>=20 >           =20 ->  Aggregate  (cost=3D4.67..4.67 rows=3D1 width=3D4) = (actual
>=20 > time=3D0.486..0.488 rows=3D1 loops=3D26250)
>=20 >           &nb= sp;     =20 ->  Seq Scan on jam_trace_sys c  (cost=3D0.00..4.62 =
> >=20 rows=3D15 width=3D4) (actual time=3D0.058..0.311 rows=3D74 = loops=3D26250)
>=20 >           &nb= sp;           =20 Filter: ((trace_id =3D $0) AND (seq_no > $1))
> >  = Total runtime:=20 13097.557 ms
> > (13 rows)
> > 
> >=20 pglnx01=3D> \d jam_trace_sys
> = >      Table=20 "public.jam_trace_sys"
> >     =20 Column      |  Type   |=20 Modifiers
> > -----------------+---------+-----------
>=20 >  trace_id        | integer=20 |
> > =20 seq_no          | integer = |
>=20 >  cpu_utilization | integer |
> > =20 gc_minor        | integer |
>=20 >  gc_major        | integer=20 |
> >  heap_used       | = integer=20 |
> > Indexes:
> >     = "jam_trace_sys_n1"=20 btree (trace_id, seq_no)
> > 
> > pglnx01=3D> = select=20 count(*) from jam_trace_Sys ;
> >  count
> >=20 -------
> >    175
> > (1 row)
>=20 > 
> > pglnx01=3D> select trace_id, count(*) from=20 jam_trace_sys group by trace_id ;
> >  trace_id | = count
>=20 > ----------+-------
> = >       =20 15 |     2
>=20 >        18 |    = 21
>=20 >        22 |   = 150
>=20 >        16 = |    =20 2
> > (4 rows)
> ------=_NextPart_000_0029_01C635A5.C01622F0--