DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:cc:content-type:content-transfer-encoding;
	b=AH7LkpKFv5/PCNjU5AIK3gpcF8aJCuk+J5J1fuX/+k6czdqCu1Dl4NT5nSh4Dlaxue
	xd7FG2DQV3RMoCkJpoZhQenetidVU34hxCp1aOnEn88ZlAzst9KB6zOuFY8EO1njmuLS
	ypMsqh6QHcv1jMmYEvBw18ALzy+NqRswLu7dY=
MIME-Version: 1.0
In-Reply-To: 
 <076DC33A3D38CE4BBC64D35DDD9DE70C0A17259D@mse4be2.mse4.exchange.ms>
References: <ca24673e1002241331l4099482aqc73649d93611767a@mail.gmail.com>
	<076DC33A3D38CE4BBC64D35DDD9DE70C0A17259D@mse4be2.mse4.exchange.ms>
Date: Wed, 24 Feb 2010 16:47:54 -0600
Message-ID: <ca24673e1002241447i2209385cvc11fafa1e37f67bf@mail.gmail.com>
Subject: Re: Extracting superlatives - SQL design philosophy
From: Dave Crooke <dcrooke@gmail.com>
To: Garrett Murphy <gmurphy@lawlogix.com>
Cc: pgsql-performance <pgsql-performance@postgresql.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Garrett's is the best answer from the list .... the only fly in the
ointment here is that it performs a full sort of the records, which
isn't strictly necessary to the required output. This is functionally
equivalent to what I came up with for a MODE (most common value)
aggregation, but the syntax is a bit neater.

Craig / Geroge - there are lots of ways to do this with a subquery or
join back against the bar table. My goal was actually to avoid this
dual lookup and join, not for this contrived example but for my
real-world case where the "bar" table is not actually a table but is a
record set generated on the fly with a non-trivial subquery which I
don't want to repeat.

Mose - I think I get what you're aiming at here, but your query as
stated returns a syntax error.

What I'd like to have is a way in SQL to get an execution plan which
matches Java algorithm below, which just does one "table scan" down
the data and aggregates in place, i.e. it's O(n) with row lookups:

   HashMap<String,Row> winners =3D new HashMap<String,Row>();

   for (Row r : rows) {
        Row oldrow =3D winners.get(r.city);
        if (oldrow =3D=3D null || r.temp > oldrow.temp) winnders.put(r.city=
, r);
    };
    for (String city : winners.keySet()) System.out.println(winners.get(cit=
y));

I'd imagine it would be possible to have a query planner optimization
that would convert Garrett's DISTINCT ON syntax to do what I was
trying to, by realizing that DISTINCT ON X ... ORDER BY Y DESC is
going to return the the one row for each X which has the highest value
of Y, and so use a MAX-structured accumulation instead of a sort.

Cheers
Dave

On Wed, Feb 24, 2010 at 3:43 PM, Garrett Murphy <gmurphy@lawlogix.com> wrot=
e:
> This looks to be a perfect use for SELECT DISTINCT ON:
>
> SELECT DISTINCT ON (city)
> * FROM bar
> ORDER BY city, temp desc
>
> Or am I misunderstanding the issue?
>
> Garrett Murphy
>
> -----Original Message-----
> From: pgsql-performance-owner@postgresql.org [mailto:pgsql-performance-ow=
ner@postgresql.org] On Behalf Of Dave Crooke
> Sent: Wednesday, February 24, 2010 2:31 PM
> To: pgsql-performance
> Subject: [PERFORM] Extracting superlatives - SQL design philosophy
>
> This is a generic SQL issue and not PG specific, but I'd like to get
> an opinion from this list.
>
> Consider the following data:
>
> # \d bar
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Table "public.bar"
> =A0Column |=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Type=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0 | Modifiers
> --------+-----------------------------+-----------
> =A0city=A0=A0 | character varying(255)=A0=A0=A0=A0=A0 |
> =A0temp=A0=A0 | integer=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0 |
> =A0date=A0=A0 | timestamp without time zone |
>
> # select * from bar order by city, date;
> =A0 city =A0 =A0| temp | =A0 =A0 =A0 =A0date
> -----------+------+---------------------
> =A0Austin =A0 =A0| =A0 75 | 2010-02-21 15:00:00
> =A0Austin =A0 =A0| =A0 35 | 2010-02-23 15:00:00
> =A0Edinburgh | =A0 42 | 2010-02-23 15:00:00
> =A0New York =A0| =A0 56 | 2010-02-23 15:00:00
> =A0New York =A0| =A0 78 | 2010-06-23 15:00:00
> (5 rows)
>
> If you want the highest recorded temperature for a city, that's easy
> to do, since the selection criteria works on the same column that we
> are extracing:
>
> # select city, max(temp) from bar group by city order by 1;
> =A0 city =A0 =A0| max
> -----------+-----
> =A0Austin =A0 =A0| =A075
> =A0Edinburgh | =A042
> =A0New York =A0| =A078
> (3 rows)
>
>
> However there is (AFAIK) no simple way in plain SQL to write a query
> that performs such an aggregation where the aggregation criteria is on
> one column and you want to return another, e.g. adding the the *date
> of* that highest temperature to the output above, or doing a query to
> get the most recent temperature reading for each city.
>
> What I'd like to do is something like the below (and I'm inventing
> mock syntax here, the following is not valid SQL):
>
> -- Ugly implicit syntax but no worse than an Oracle outer join ;-)
> select city, temp, date from bar where date=3Dmax(date) group by city,
> temp order by city;
>
> or perhaps
>
> -- More explicit
> select aggregate_using(max(date), city, temp, date) from bar group by
> city, temp order by city;
>
> Both of the above, if they existed, would be a single data access
> followed by and sort-merge.
>
> The only way I know how to do it involves doing two accesses to the data,=
 e.g.
>
> # select city, temp, date from bar a where date=3D(select max(b.date)
> from bar b where a.city=3Db.city) order by 1;
> =A0 city =A0 =A0| temp | =A0 =A0 =A0 =A0date
> -----------+------+---------------------
> =A0Austin =A0 =A0| =A0 35 | 2010-02-23 15:00:00
> =A0Edinburgh | =A0 42 | 2010-02-23 15:00:00
> =A0New York =A0| =A0 78 | 2010-06-23 15:00:00
> (3 rows)
>
>
> # explain select * from bar a where date=3D(select max(b.date) from bar
> b where a.city=3Db.city) order by 1;
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0QUERY PLAN
> -------------------------------------------------------------------------=
-
> =A0Sort =A0(cost=3D1658.86..1658.87 rows=3D1 width=3D528)
> =A0 Sort Key: a.city
> =A0 -> =A0Seq Scan on bar a =A0(cost=3D0.00..1658.85 rows=3D1 width=3D528=
)
> =A0 =A0 =A0 =A0 Filter: (date =3D (subplan))
> =A0 =A0 =A0 =A0 SubPlan
> =A0 =A0 =A0 =A0 =A0 -> =A0Aggregate =A0(cost=3D11.76..11.77 rows=3D1 widt=
h=3D8)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 -> =A0Seq Scan on bar b =A0(cost=3D0.00..=
11.75 rows=3D1
> width=3D8) =A0 =A0 -- would be an index lookup in a real scenario
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 Filter: (($0)::text =3D (city=
)::text)
> (8 rows)
>
> --
> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org=
)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance
>