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=MITddY9rzweSvQgMEbybLP8XPYYtoaA8qqM8iGQCoDMb7LUH2Ecy5TftwCIV5p6858
	gcg8iSeS6IBvGso6MKVlKGeou43IKn6UNrfDIOMHKS43w2ZL+79K2LymayujQ8pJlC93
	6Ub1Y5lk62E2VCZYZlP63tjbNjXI02QK9Nb9I=
MIME-Version: 1.0
In-Reply-To: <4B85B259.4030900@archonet.com>
References: <ca24673e1002241331l4099482aqc73649d93611767a@mail.gmail.com>
	<076DC33A3D38CE4BBC64D35DDD9DE70C0A17259D@mse4be2.mse4.exchange.ms>
	<ca24673e1002241447i2209385cvc11fafa1e37f67bf@mail.gmail.com>
	<4B85B259.4030900@archonet.com>
Date: Wed, 24 Feb 2010 17:37:11 -0600
Message-ID: <ca24673e1002241537o5ce1295egee3e2154a9f1b8a2@mail.gmail.com>
Subject: Re: Extracting superlatives - SQL design philosophy
From: Dave Crooke <dcrooke@gmail.com>
To: Richard Huxton <dev@archonet.com>
Cc: Garrett Murphy <gmurphy@lawlogix.com>,
	pgsql-performance <pgsql-performance@postgresql.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

1. The city temps table is a toy example, not meant to be realistic :-)

2. Yes, my (Java) algorithm is deterministic ... it will return
exactly one row per city, and that will be the row (or strictly, *a*
row) containing the highest temp. Temp value ties will break in favour
of earlier rows in Guinness Book of Records tradition :-) It's
equivalent to a HashAggregate implementation.


The following two query plans (from my real schema) illustrate the
itch I am trying to scratch .... I want the functionality of the 2nd
one, but with the execution plan structure of the first:

# explain analyse select a, max(b) from perf_raw_2010_02_23 group by a;
                                                              QUERY
PLAN
---------------------------------------------------------------------------=
-----------------------------------------------------------
 HashAggregate  (cost=3D117953.09..117961.07 rows=3D639 width=3D8) (actual
time=3D10861.845..10863.008 rows=3D1023 loops=3D1)
   ->  Seq Scan on perf_raw_2010_02_23  (cost=3D0.00..91572.39
rows=3D5276139 width=3D8) (actual time=3D0.038..4459.222 rows=3D5276139
loops=3D1)
 Total runtime: 10863.856 ms
(3 rows)

Time: 10864.817 ms
# explain analyse select distinct on (a) * from perf_raw_2010_02_23
order by a, b desc ;
                                                                 QUERY
PLAN
---------------------------------------------------------------------------=
------------------------------------------------------------------
 Unique  (cost=3D1059395.04..1085775.73 rows=3D639 width=3D28) (actual
time=3D46011.204..58428.210 rows=3D1023 loops=3D1)
   ->  Sort  (cost=3D1059395.04..1072585.39 rows=3D5276139 width=3D28)
(actual time=3D46011.200..53561.112 rows=3D5276139 loops=3D1)
         Sort Key: a, b
         Sort Method:  external merge  Disk: 247584kB
-- actually OS RAM buffers
         ->  Seq Scan on perf_raw_2010_02_23  (cost=3D0.00..91572.39
rows=3D5276139 width=3D28) (actual time=3D0.047..6491.036 rows=3D5276139
loops=3D1)
 Total runtime: 58516.185 ms
(6 rows)

Time: 58517.233 ms

The only difference between these two is that the second query returns
the whole row. The *ratio* in cost between these two plans increases
in proportion to log(n) of the table size ... at 5.5m rows its
livable, at 500m it's probably not :-!

Cheers
Dave

On Wed, Feb 24, 2010 at 5:12 PM, Richard Huxton <dev@archonet.com> wrote:
> On 24/02/10 22:47, Dave Crooke wrote:
>>
>> 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.
>
> Why is there only one row? For city temperatures, that seems unlikely.
>
> In the event of more than one row does your algorithm give repeatable
> results?
>
> --
> =A0Richard Huxton
> =A0Archonet Ltd
>