Received: from localhost (unknown [200.46.204.183])
	by postgresql.org (Postfix) with ESMTP id 82B6C64FD33
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri,  5 Sep 2008 12:10:44 -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 34398-09 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri,  5 Sep 2008 12:10:37 -0300 (ADT)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from rv-out-0506.google.com (rv-out-0506.google.com
 [209.85.198.224])
	by postgresql.org (Postfix) with ESMTP id 918B564FCDD
	for <pgsql-performance@postgresql.org>;
	Fri,  5 Sep 2008 12:10:37 -0300 (ADT)
Received: by rv-out-0506.google.com with SMTP id b25so640806rvf.43
	for <pgsql-performance@postgresql.org>;
	Fri, 05 Sep 2008 08:10:35 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma;
	h=domainkey-signature:received:received:message-id:date:from:to
	:subject:in-reply-to:mime-version:content-type:references;
	bh=3Q1K+Gptp6cwH9B5MxW9UAYU7En3Elju8TnAlBFM56U=;
	b=Q/zp5s+kdclRkgY+CUese54epwljynImNKJishjJzHRgWDbPoShKGlui4G43CERnTm
	wkgHVkQuu7kdQAzqQKMUkfBRDeH3ysFTghnGC5DVTrTEgPourXLQm90LCmzittrg12pE
	wEDucEWRJwQN4oMob5VMsoC/u0kKe4mEx3o5Y=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=message-id:date:from:to:subject:in-reply-to:mime-version
	:content-type:references;
	b=m23wp2vu4iSSa81vTE/kmugos/S2+rwYrCodsX8mOwT5ancgeg+d/ktxQqSL8kqjub
	dy3lMc4G3RlqW3s7uHPn7WwD5qmWtfcvosPDfZ40H6o0dZp7LIwheYp8pjKFOEjXeawX
	UmsvaVUIvLsNYIbGGf7jcyh+SH8QtVfXJSVOk=
Received: by 10.141.83.15 with SMTP id k15mr6661385rvl.289.1220627435642;
	Fri, 05 Sep 2008 08:10:35 -0700 (PDT)
Received: by 10.141.186.3 with HTTP; Fri, 5 Sep 2008 08:10:35 -0700 (PDT)
Message-ID: <1d709ecc0809050810m42bfbedfk98ac7d83f13fb7@mail.gmail.com>
Date: Fri, 5 Sep 2008 19:10:35 +0400
From: "Vladimir Sitnikov" <sitnikov.vladimir@gmail.com>
To: pgsql-performance@postgresql.org
Subject: Re: indexing for distinct search in timestamp based table
In-Reply-To: <000c01c908e4$f64e92c0$e2ebb840$@com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_40145_4061129.1220627435639"
References: <000c01c908e4$f64e92c0$e2ebb840$@com>
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/74
X-Sequence-Number: 31387

------=_Part_40145_4061129.1220627435639
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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> = ( select  min(<field>) from ad_log )
 2) record_exists = ( select 1 from ad_log where <field>=cur_<field> and
_all_other_conditions limit 1 )
 3) if record_exists==1 then add curr_<field> to the results
 3) curr_<field> = (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?

------=_Part_40145_4061129.1220627435639
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

<div dir="ltr"><span class="Apple-style-span" style="border-collapse: collapse; "><div>You might get great improvement for &#39;%&#39; cases using index on&nbsp;<span style="border-collapse: collapse; ">channel_name(&lt;field&gt;, start_time) and a little bit of pl/pgsql</span></div>
<div><span style="border-collapse: collapse; "><br></span></div><div><span style="border-collapse: collapse; ">Basically, you need to implement the following algorithm:</span></div><div><span style="border-collapse: collapse; ">&nbsp;1) curr_&lt;field&gt; = ( select &nbsp;min(&lt;field&gt;) from ad_log )</span><br>
</div><div><span style="border-collapse: collapse; ">&nbsp;2) record_exists = ( select 1 from ad_log where &lt;field&gt;=cur_&lt;field&gt; and _all_other_conditions limit 1 )</span><br></div><div><span style="border-collapse: collapse; ">&nbsp;3) if record_exists==1 then add curr_&lt;field&gt; to the results</span></div>
<div><span style="border-collapse: collapse; ">&nbsp;3) curr_&lt;field&gt; = (select min(&lt;field&gt;) from ad_log where &lt;field&gt; &nbsp;&gt; &nbsp;curr_&lt;field&gt; )&nbsp;</span></div><div><span style="border-collapse: collapse; ">&nbsp;4) if curr_&lt;field&gt; is not null then goto 2</span></div>
<div><span style="border-collapse: collapse; "><br></span></div><div><br></div><div><span style="border-collapse: collapse; ">I believe it might make sense implement this approach in the core (I would call it &quot;index distinct scan&quot;)</span></div>
<div><span style="border-collapse: collapse; "><br></span></div><div><span style="border-collapse: collapse; ">That could dramatically improve &quot;select distinct &lt;column&gt; from &lt;table&gt;&quot; and &quot;select &lt;column&gt; from &lt;table&gt; group by &lt;column&gt;&quot; kind of queries when there exists an index on &lt;column&gt; and a particular column has very small number of distinct values.</span></div>
<div><span style="border-collapse: collapse; "><br></span></div><div><span style="border-collapse: collapse; ">For instance: &nbsp;say a table has 10&#39;000&#39;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.</span></div>
<div><span style="border-collapse: collapse; "><br></span></div><div><span style="border-collapse: collapse; ">What does the community think about that?</span></div></span></div>

------=_Part_40145_4061129.1220627435639--