Re: Avoiding cartesian product

Dear Virag,

AFAIK aggregates aren't indexed in postgres (at least not before 8.1, which
indexes min and max, iirc).

Also, I don't think you need to exactly determine the trace_id. Try this one
(OTOH; might be wrong):

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 = 22
and b.trace_id = 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

The trick is that DISTINCT takes the first one in each group (IIRC it is
granted, at least someone told me on one of these lists :) ) so if you order
by the DISTINCT attributes and then by b.seq_no, you'll get the smallest of
appropriate b.seq_no values for each DISTINCT values.

The idea of DISTINCTing by both columns is to make sure the planner finds
the index. (lately I had a similar problem: WHERE a=1 ORDER BY b LIMIT 1
used an index on b, instead of an (a,b) index. Using ORDER BY a,b solved it)

HTH,

--
G.

On 2006.01.04. 5:12, Virag Saksena wrote:
>
> 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 = 22
> and b.trace_id = a.trace_id
> and b.seq_no = 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 = 22
> and (b.trace_id, b.seq_no) =
> (select a.trace_id, min(c.seq_no) from jam_trace_sys c
> where c.trace_id = 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=124911.81..124944.84 rows=13213 width=20) (actual
> time=13096.754..13097.053 rows=149 loops=1)
> Sort Key: a.seq_no
> -> Nested Loop (cost=4.34..124007.40 rows=13213 width=20) (actual
> time=1948.300..13096.329 rows=149 loops=1)
> Join Filter: (subplan)
> -> Seq Scan on jam_trace_sys b (cost=0.00..3.75 rows=175
> width=16) (actual time=0.005..0.534 rows=175 loops=1)
> -> Materialize (cost=4.34..5.85 rows=151 width=16) (actual
> time=0.002..0.324 rows=150 loops=175)
> -> Seq Scan on jam_trace_sys a (cost=0.00..4.19
> rows=151 width=16) (actual time=0.022..0.687 rows=150 loops=1)
> Filter: (trace_id = 22)
> SubPlan
> -> Aggregate (cost=4.67..4.67 rows=1 width=4) (actual
> time=0.486..0.488 rows=1 loops=26250)
> -> Seq Scan on jam_trace_sys c (cost=0.00..4.62
> rows=15 width=4) (actual time=0.058..0.311 rows=74 loops=26250)
> Filter: ((trace_id = $0) AND (seq_no > $1))
> Total runtime: 13097.557 ms
> (13 rows)
>
> pglnx01=> \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=> select count(*) from jam_trace_Sys ;
> count
> -------
> 175
> (1 row)
>
> pglnx01=> 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)