Received: from localhost (unknown [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 16FB364FCE6 for ; Mon, 8 Sep 2008 00:54:30 -0300 (ADT) Received: from postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 11811-10 for ; Mon, 8 Sep 2008 00:54:24 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from ichigo.office.vanten.com (static-222-230-136-226.b-fam.svips.gol.ne.jp [222.230.136.226]) by postgresql.org (Postfix) with ESMTP id 48F24650068 for ; Mon, 8 Sep 2008 00:54:22 -0300 (ADT) Received: from rainerxp (rainer-xp.office.vanten.com [192.168.220.186]) by ichigo.office.vanten.com (Postfix) with ESMTP id AFD785081C; Mon, 8 Sep 2008 12:54:18 +0900 (JST) From: "Rainer Mager" To: "'Vladimir Sitnikov'" , References: <000c01c908e4$f64e92c0$e2ebb840$@com> <1d709ecc0809050810m42bfbedfk98ac7d83f13fb7@mail.gmail.com> In-Reply-To: <1d709ecc0809050810m42bfbedfk98ac7d83f13fb7@mail.gmail.com> Subject: Re: indexing for distinct search in timestamp based table Date: Mon, 8 Sep 2008 12:54:04 +0900 Message-ID: <000001c91166$89b6ba40$9d242ec0$@com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0001_01C911B1.F99E6240" X-Mailer: Microsoft Office Outlook 12.0 Thread-Index: AckPaapOY0jg0tRJQauV7NuSYePJawB2lOjQ Content-Language: en-us X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.001 tagged_above=0 required=5 tests=HTML_MESSAGE=0.001 X-Spam-Level: X-Archive-Number: 200809/82 X-Sequence-Number: 31395 This is a multipart message in MIME format. ------=_NextPart_000_0001_01C911B1.F99E6240 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Thanks for the suggestion. This seems to work pretty well on 8.3, but not so well on 8.2. We were planning on upgrading to 8.3 soon anyway, we just have to move up our schedule a bit. I think that this type of algorithm would make sense in core. I suspect that being in there some further optimizations could be done that pl/pgsql can't do. --Rainer From: pgsql-performance-owner@postgresql.org [mailto:pgsql-performance-owner@postgresql.org] On Behalf Of Vladimir Sitnikov Sent: Saturday, September 06, 2008 12:11 AM To: pgsql-performance@postgresql.org Subject: Re: [PERFORM] indexing for distinct search in timestamp based table You might get great improvement for '%' cases using index on channel_name(, start_time) and a little bit of pl/pgsql Basically, you need to implement the following algorithm: 1) curr_ = ( select min() from ad_log ) 2) record_exists = ( select 1 from ad_log where =cur_ and _all_other_conditions limit 1 ) 3) if record_exists==1 then add curr_ to the results 3) curr_ = (select min() from ad_log where > curr_ ) 4) if curr_ is not null then goto 2 I believe it might make sense implement this approach in the core (I would call it "index distinct scan") That could dramatically improve "select distinct from " and "select from

group by " kind of queries when there exists an index on and a particular column has very small number of distinct values. For instance: say a table has 10'000'000 rows, while column of interest has only 20 distinct values. In that case, the database will be able to get every of those 20 values in virtually 20 index lookups. What does the community think about that? ------=_NextPart_000_0001_01C911B1.F99E6240 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

Thanks for the suggestion. This seems to work pretty well = on 8.3, but not so well on 8.2. We were planning on upgrading to 8.3 soon = anyway, we just have to move up our schedule a bit.

I think that this type of algorithm would make sense in = core. I suspect that being in there some further optimizations could be done = that pl/pgsql can’t do.

--Rainer

From:= pgsql-performance-owner@postgresql.org [mailto:pgsql-performance-owner@postgresql.org] On Behalf Of = Vladimir Sitnikov
Sent: Saturday, September 06, 2008 12:11 AM
To: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] indexing for distinct search in timestamp = based table

You might get great improvement for '%' cases using = index on channel_name(<field>, start_time) and a little bit of = pl/pgsql

Basically, you need to implement the following = algorithm:

1) curr_<field> =3D ( select min(<field>) from ad_log )

2) record_exists =3D ( select 1 from ad_log = where <field>=3Dcur_<field> and _all_other_conditions limit 1 = )

3) if record_exists=3D=3D1 then add = curr_<field> to the results

3) curr_<field> =3D (select = min(<field>) from ad_log where <field> > curr_<field> = )

4) if curr_<field> is not null then = goto 2

I believe it might make sense implement this = approach in the core (I would call it "index distinct scan")

That could dramatically improve "select = distinct <column> from <table>" and "select <column> = from <table> group by <column>" kind of queries when there = exists an index on <column> and a particular column has very small number = of distinct values.

For instance: say a table has 10'000'000 = rows, while column of interest has only 20 distinct values. In that case, the = database will be able to get every of those 20 values in virtually 20 index = lookups.

What does the community think about = that?

------=_NextPart_000_0001_01C911B1.F99E6240--