Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id C45369FA4D3 for ; Wed, 31 Jan 2007 02:59:46 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-new, port 10024) with ESMTP id 50782-03 for ; Wed, 31 Jan 2007 02:59:44 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from exprod6og52.obsmtp.com (exprod6og52.obsmtp.com [64.18.1.185]) by postgresql.org (Postfix) with SMTP id 4EBEC9FA48D for ; Wed, 31 Jan 2007 02:59:45 -0400 (AST) Received: from source ([63.240.6.46]) (using TLSv1) by exprod6ob52.postini.com ([64.18.5.12]) with SMTP; Tue, 30 Jan 2007 22:59:24 PST Received: from 172.16.1.110 by mail.mi8.com with ESMTP (- Welcome to Mi8 Corporation www.Mi8.com (D2)); Wed, 31 Jan 2007 01:58:58 -0500 X-Server-Uuid: 7829E76E-BB9E-4995-8473-3C0929DF7DD1 Received: from MI8NYCMAIL08.Mi8.com ([172.16.1.164]) by D01SMTP01.Mi8.com with Microsoft SMTPSVC(6.0.3790.1830); Wed, 31 Jan 2007 01:58:57 -0500 Received: from 69.181.100.71 ([69.181.100.71]) by MI8NYCMAIL08.Mi8.com ( [172.16.1.190]) via Exchange Front-End Server mi8owa.mi8.com ( [172.16.1.106]) with Microsoft Exchange Server HTTP-DAV ; Wed, 31 Jan 2007 06:58:56 +0000 User-Agent: Microsoft-Entourage/11.3.3.061214 Date: Tue, 30 Jan 2007 22:58:53 -0800 Subject: Re: Querying distinct values from a large table From: "Luke Lonergan" To: "Tom Lane" , "Alvaro Herrera" cc: "Gregory Stark" , "Chad Wagner" , "Simon Riggs" , "Igor Lobanov" , "Richard Huxton" , pgsql-performance@postgresql.org Message-ID: Thread-Topic: [PERFORM] Querying distinct values from a large table Thread-Index: AcdFBUSDgstZmrD4EduuAAAWy4o9DA== In-Reply-To: <16278.1170222919@sss.pgh.pa.us> MIME-Version: 1.0 X-OriginalArrivalTime: 31 Jan 2007 06:58:57.0409 (UTC) FILETIME=[4724B710:01C74505] X-WSS-ID: 69DEE1BB4M83455359-01-01 Content-Type: multipart/alternative; boundary=B_3253042733_183245 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200701/443 X-Sequence-Number: 23044 > This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. --B_3253042733_183245 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Tom, On 1/30/07 9:55 PM, "Tom Lane" wrote: > Alvaro Herrera writes: >> Gregory Stark wrote: >>> (Incidentally I'm not sure where 2-5x comes from. It's entirely dependant on >>> your data distribution. It's not hard to come up with distributions where >>> it's >>> 1000x as fast and others where there's no speed difference.) > >> So the figure is really "1-1000x"? I bet this one is more impressive in >> PHB terms. > > Luke has a bad habit of quoting numbers that are obviously derived from > narrow benchmarking scenarios as Universal Truths, rather than providing > the context they were derived in. I wish he'd stop doing that... In this case I was referring to results obtained using grouping and distinct optimizations within sort where the benefit is from the use of a single pass instead of the multiple merge passes for external sort followed by a UNIQUE operator. In this case, the benefit ranges from 2-5x in many examples as I mentioned: "from 2-5 times faster than a typical external sort". This is also the same range of benefits we see for this optimization with a popular commercial database. With the limit/sort optimization we have seen more dramatic results, but I think those are less typical cases. Here are some results for a 1GB table and a simple COUNT(DISTINCT) on a column with 7 unique values from my dual CPU laptop running Greenplum DB (PG 8.2.1 compatible) on both CPUs. Note that my laptop has 2GB of RAM so I have the 1GB table loaded into OS I/O cache. The unmodified external sort spills the sorted attribute to disk, but that takes little time. Note that the COUNT(DISTINCT) plan embeds a sort as the transition function in the aggregation node. ================================================================= ================= No Distinct Optimization in Sort ============== ================================================================= lukelonergan=# select count(distinct l_shipmode) from lineitem; count ------- 7 (1 row) Time: 37832.308 ms lukelonergan=# explain analyze select count(distinct l_shipmode) from lineitem; QUERY PLAN ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- ---- Aggregate (cost=159175.30..159175.31 rows=1 width=8) Total 1 rows with 40899 ms to end, start offset by 3.189 ms. -> Gather Motion 2:1 (slice2) (cost=159175.25..159175.28 rows=1 width=8) recv: Total 2 rows with 39387 ms to first row, 40899 ms to end, start offset by 3.191 ms. -> Aggregate (cost=159175.25..159175.26 rows=1 width=8) Avg 1.00 rows x 2 workers. Max 1 rows (seg0) with 39367 ms to end, start offset by 22 ms. -> Redistribute Motion 2:2 (slice1) (cost=0.00..151672.00 rows=3001300 width=8) recv: Avg 3000607.50 rows x 2 workers. Max 3429492 rows (seg1) with 0.362 ms to first row, 8643 ms to end, start offset by 23 ms. Hash Key: lineitem.l_shipmode -> Seq Scan on lineitem (cost=0.00..91646.00 rows=3001300 width=8) Avg 3000607.50 rows x 2 workers. Max 3001300 rows (seg0) with 0.049 ms to first row, 2813 ms to end, start offset by 12.998 ms. Total runtime: 40903.321 ms (12 rows) Time: 40904.013 ms ================================================================= ================= With Distinct Optimization in Sort ============== ================================================================= lukelonergan=# set mpp_sort_flags=1; SET Time: 1.425 ms lukelonergan=# select count(distinct l_shipmode) from lineitem; count ------- 7 (1 row) Time: 12846.466 ms lukelonergan=# explain analyze select count(distinct l_shipmode) from lineitem; QUERY PLAN ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- ---- Aggregate (cost=159175.30..159175.31 rows=1 width=8) Total 1 rows with 13754 ms to end, start offset by 2.998 ms. -> Gather Motion 2:1 (slice2) (cost=159175.25..159175.28 rows=1 width=8) recv: Total 2 rows with 13754 ms to end, start offset by 3.000 ms. -> Aggregate (cost=159175.25..159175.26 rows=1 width=8) Avg 1.00 rows x 2 workers. Max 1 rows (seg0) with 13734 ms to end, start offset by 23 ms. -> Redistribute Motion 2:2 (slice1) (cost=0.00..151672.00 rows=3001300 width=8) recv: Avg 3000607.50 rows x 2 workers. Max 3429492 rows (seg1) with 0.352 ms to first row, 10145 ms to end, start offset by 26 ms. Hash Key: lineitem.l_shipmode -> Seq Scan on lineitem (cost=0.00..91646.00 rows=3001300 width=8) Avg 3000607.50 rows x 2 workers. Max 3001300 rows (seg0) with 0.032 ms to first row, 4048 ms to end, start offset by 13.037 ms. Total runtime: 13757.524 ms (12 rows) Time: 13758.182 ms ================= Background Information ============== lukelonergan=# select count(*) from lineitem; count --------- 6001215 (1 row) Time: 1661.337 ms lukelonergan=# \d lineitem Table "public.lineitem" Column | Type | Modifiers -----------------+-----------------------+----------- l_orderkey | integer | not null l_partkey | integer | not null l_suppkey | integer | not null l_linenumber | integer | not null l_quantity | double precision | not null l_extendedprice | double precision | not null l_discount | double precision | not null l_tax | double precision | not null l_returnflag | text | not null l_linestatus | text | not null l_shipdate | date | not null l_commitdate | date | not null l_receiptdate | date | not null l_shipinstruct | text | not null l_shipmode | text | not null l_comment | character varying(44) | not null Distributed by: (l_orderkey) lukelonergan=# select pg_relation_size(oid)/(1000.*1000.) as MB, relname as Table from pg_class order by MB desc limit 10; mb | table ------------------------+-------------------------------- 1009.4755840000000000 | lineitem 230.0559360000000000 | orders 146.7678720000000000 | partsupp 35.8072320000000000 | part 32.8908800000000000 | customer 1.9333120000000000 | supplier 1.1304960000000000 | pg_proc 0.88473600000000000000 | pg_proc_proname_args_nsp_index 0.81100800000000000000 | pg_attribute 0.81100800000000000000 | pg_depend - Luke --B_3253042733_183245 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: quoted-printable Re: [PERFORM] Querying distinct values from a large table Tom,<= BR>
On 1/30/07 9:55 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Alvaro Herrera <alvherre@commandprompt.com>= ; writes:
>> Gregory Stark wrote:
>>> (Incidentally I'm not sure where = 2-5x comes from. It's entirely dependant on
>>> your data distribution. It's not hard to come up with distribu= tions where
>>> it's
>>> 1000x as fast and others where there's no speed difference.) >
>> So the figure is really "1-1000x= "?  I bet this one is more impressive in
>> PHB terms.
>
> Luke has a bad habit of quoting numbers that are obviously derived fro= m
> narrow benchmarking scenarios as Universal Truths, rather than providi= ng
> the context they were derived in.  I wish he'd stop doing that...=

In this case I was referring to results obtained using grouping and distinc= t optimizations within sort where the benefit is from the use of a single pa= ss instead of the multiple merge passes for external sort followed by a UNIQ= UE operator.  In this case, the benefit ranges from 2-5x in many exampl= es as I mentioned: "from 2-5 times faster than a typical external sort&= quot;.  This is also the same range of benefits we see for this optimiz= ation with a popular commercial database. With the limit/sort optimization w= e have seen more dramatic results, but I think those are less typical cases.=

Here are some results for a 1GB table and a simple COUNT(DISTINCT) on a col= umn with 7 unique values from my dual CPU laptop running Greenplum DB (PG 8.= 2.1 compatible) on both CPUs. Note that my laptop has 2GB of RAM so I have t= he 1GB table loaded into OS I/O cache.  The unmodified external sort sp= ills the sorted attribute to disk, but that takes little time.  Note th= at the COUNT(DISTINCT) plan embeds a sort as the transition function in the = aggregation node.

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D No Distinct Optimization in Sort =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
lukelonergan=3D# select count(distinct l_shipmode) from lineitem;
 count
-------
     7
(1 row)

Time: 37832.308 ms

lukelonergan=3D# explain analyze select count(distinct l_shipmode) from linei= tem;             = ;            &nb= sp;            &= nbsp;            = ;            &nb= sp;            &= nbsp;            = ;            &nb= sp;      QUERY PLAN     &n= bsp;            =             &nbs= p;            &n= bsp;            =             &nbs= p;    
---------------------------------------------------------------------------= ----------------------------------------------------------------------------= -----
 Aggregate  (cost=3D159175.30..159175.31 rows=3D1 width=3D8)
   Total 1 rows with 40899 ms to end, start offset by 3.189 = ms.
   ->  Gather Motion 2:1  (slice2)  (cost=3D= 159175.25..159175.28 rows=3D1 width=3D8)
         recv:  Total 2 r= ows with 39387 ms to first row, 40899 ms to end, start offset by 3.191 ms.          ->  Aggregate=  (cost=3D159175.25..159175.26 rows=3D1 width=3D8)
            &nb= sp;  Avg 1.00 rows x 2 workers.  Max 1 rows (seg0) with 39367= ms to end, start offset by 22 ms.
            &nb= sp;  ->  Redistribute Motion 2:2  (slice1)  (cos= t=3D0.00..151672.00 rows=3D3001300 width=3D8)
            &nb= sp;        recv:  Avg 3000607.5= 0 rows x 2 workers.  Max 3429492 rows (seg1) with 0.362 ms to first row= , 8643 ms to end, start offset by 23 ms.
            &nb= sp;        Hash Key: lineitem.l_ship= mode
            &nb= sp;        ->  Seq Scan on l= ineitem  (cost=3D0.00..91646.00 rows=3D3001300 width=3D8)
            &nb= sp;            &= nbsp; Avg 3000607.50 rows x 2 workers.  Max 3001300 rows (seg0) wi= th 0.049 ms to first row, 2813 ms to end, start offset by 12.998 ms.
 Total runtime: 40903.321 ms
(12 rows)

Time: 40904.013 ms

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D With Distinct Optimization in Sort =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
lukelonergan=3D# set mpp_sort_flags=3D1;
SET
Time: 1.425 ms
lukelonergan=3D# select count(distinct l_shipmode) from lineitem;
 count
-------
     7
(1 row)

Time: 12846.466 ms

lukelonergan=3D# explain analyze select count(distinct l_shipmode) from linei= tem;
            &nb= sp;            &= nbsp;            = ;            &nb= sp;            &= nbsp;         QUERY PLAN  =             &nbs= p;            &n= bsp;            =             &nbs= p;            &n= bsp;       
---------------------------------------------------------------------------= ----------------------------------------------------------------------------= -----
 Aggregate  (cost=3D159175.30..159175.31 rows=3D1 width=3D8)
   Total 1 rows with 13754 ms to end, start offset by 2.998 = ms.
   ->  Gather Motion 2:1  (slice2)  (cost=3D= 159175.25..159175.28 rows=3D1 width=3D8)
         recv:  Total 2 r= ows with 13754 ms to end, start offset by 3.000 ms.
         ->  Aggregate=  (cost=3D159175.25..159175.26 rows=3D1 width=3D8)
            &nb= sp;  Avg 1.00 rows x 2 workers.  Max 1 rows (seg0) with 13734= ms to end, start offset by 23 ms.
            &nb= sp;  ->  Redistribute Motion 2:2  (slice1)  (cos= t=3D0.00..151672.00 rows=3D3001300 width=3D8)
            &nb= sp;        recv:  Avg 3000607.5= 0 rows x 2 workers.  Max 3429492 rows (seg1) with 0.352 ms to first row= , 10145 ms to end, start offset by 26 ms.
            &nb= sp;        Hash Key: lineitem.l_ship= mode
            &nb= sp;        ->  Seq Scan on l= ineitem  (cost=3D0.00..91646.00 rows=3D3001300 width=3D8)
            &nb= sp;            &= nbsp; Avg 3000607.50 rows x 2 workers.  Max 3001300 rows (seg0) wi= th 0.032 ms to first row, 4048 ms to end, start offset by 13.037 ms.
 Total runtime: 13757.524 ms
(12 rows)

Time: 13758.182 ms

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Background Information =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
lukelonergan=3D# select count(*) from lineitem;
  count  
---------
 6001215
(1 row)

Time: 1661.337 ms
lukelonergan=3D# \d lineitem
            &nb= sp;  Table "public.lineitem"
     Column      |  =        Type      = ;    | Modifiers
-----------------+-----------------------+-----------
 l_orderkey      | integer    =            | not null=
 l_partkey       | integer   &= nbsp;           | not= null
 l_suppkey       | integer   &= nbsp;           | not= null
 l_linenumber    | integer     &nbs= p;         | not null
 l_quantity      | double precision  &nb= sp;   | not null
 l_extendedprice | double precision      | no= t null
 l_discount      | double precision  &nb= sp;   | not null
 l_tax           | d= ouble precision      | not null
 l_returnflag    | text      &= nbsp;           | not= null
 l_linestatus    | text      &= nbsp;           | not= null
 l_shipdate      | date    &nb= sp;            &= nbsp;| not null
 l_commitdate    | date      &= nbsp;           | not= null
 l_receiptdate   | date       =            | not null=
 l_shipinstruct  | text        = ;          | not null
 l_shipmode      | text    &nb= sp;            &= nbsp;| not null
 l_comment       | character varying(44)= | not null
Distributed by: (l_orderkey)

lukelonergan=3D# select pg_relation_size(oid)/(1000.*1000.) as MB, relname as= Table from pg_class order by MB desc limit 10;
           mb  =          |    &n= bsp;        table    =           
------------------------+--------------------------------
  1009.4755840000000000 | lineitem
   230.0559360000000000 | orders
   146.7678720000000000 | partsupp
    35.8072320000000000 | part
    32.8908800000000000 | customer
     1.9333120000000000 | supplier
     1.1304960000000000 | pg_proc
 0.88473600000000000000 | pg_proc_proname_args_nsp_index
 0.81100800000000000000 | pg_attribute
 0.81100800000000000000 | pg_depend


- Luke   --B_3253042733_183245--