Received: from maia.hub.org (unknown [200.46.204.183]) by mail.postgresql.org (Postfix) with ESMTP id D463C632287 for ; Sat, 20 Mar 2010 13:16:28 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 19392-07 for ; Sat, 20 Mar 2010 16:16:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wy0-f174.google.com (mail-wy0-f174.google.com [74.125.82.174]) by mail.postgresql.org (Postfix) with ESMTP id 04C57633635 for ; Sat, 20 Mar 2010 13:16:17 -0300 (ADT) Received: by wyb38 with SMTP id 38so1917249wyb.19 for ; Sat, 20 Mar 2010 09:16:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type; bh=SwlPUIHCydKTLMP656DQrottvQSvGYaGUb/XQxIcdjM=; b=dTcR2m43l/37Q4wtJarkU45SdQdx3wXaaMh4IPH1l5Vjs1q603uGThoZQuQ3q3Tmy9 sQUandURRFzYUyB+GOYvef7Wm6JaFcb+CfcDJ8T4RY6X3gyVZO7uJ+5U1bcBqPyrDerz ievFMMhweeXfeTeEEfRf1dZcvUzrRr8z7DtHQ= 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; b=YUaI9BfvDL+rO2K1/J2zs2RCGm9PTvDypWnTIfGeHsk5a4N9OegRc7KuGoCvtcYbn8 t3K6itJgJy5XeAu3wtnByaxVD0HDkLznV/UYRTFEQpjICN0kzr32hFgheb8+cRqebf+l z8/pAec81AvWBnrCwqFsEKsvzQAQz7/jbJhV4= MIME-Version: 1.0 Received: by 10.216.87.68 with SMTP id x46mr1605381wee.145.1269101776501; Sat, 20 Mar 2010 09:16:16 -0700 (PDT) In-Reply-To: <20100319211638.GI1218@it.is.rice.edu> References: <201002252342.o1PNgtG07127@momjian.us> <4B9FAF4B.20907@gmail.com> <4BA0A036.1070508@gmail.com> <4BA3A6C6.80406@gmail.com> <4BA3DCA1.2010808@gmail.com> <4BA3E35A.1000905@gmail.com> <20100319211638.GI1218@it.is.rice.edu> Date: Sat, 20 Mar 2010 17:16:16 +0100 Message-ID: Subject: Re: GiST index performance From: Yeb Havinga To: Kenneth Marshall Cc: Matthew Wakeling , Bruce Momjian , pgsql-performance@postgresql.org Content-Type: multipart/alternative; boundary=0016e6db2b0a9282e104823dc836 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-2.598 tagged_above=-10 required=5 tests=BAYES_00=-2.599, HTML_MESSAGE=0.001 X-Spam-Level: X-Archive-Number: 201003/253 X-Sequence-Number: 38078 --0016e6db2b0a9282e104823dc836 Content-Type: text/plain; charset=ISO-8859-1 On Fri, Mar 19, 2010 at 10:16 PM, Kenneth Marshall wrote: > Hi Yeb, > > I have not looked at the gist code, but would it be possible to > make virtual pages that have a size that is 1/power-of-2 * blocksize. > Then the leaf node could be 1/8 or even 1/16 the size of the full > pagesize. > Hello Ken, The gist virtual pages would then match more the original blocksizes that were used in Guttman's R-tree paper (first google result, then figure 4.5). Since the nature/characteristics of the underlying datatypes and keys is not changed, it might be that with the disk pages getting larger, gist indexing has therefore become unexpectedly inefficient. But I am also not really into the core-gist code, but do have a motivation to dive into it (more than 200% performance increase in Mathew's test case). However I'd like to verify for community support before working on it. Maybe Theodor or Oleg could say something about how easy or hard it is to do? regards, Yeb Havinga > > Regards, > Ken > > On Fri, Mar 19, 2010 at 09:49:30PM +0100, Yeb Havinga wrote: > > Yeb Havinga wrote: > >> > >> Since the gistpagesize is derived from the database blocksize, it might > be > >> wise to set the blocksize low for this case, I'm going to play with this > a > >> bit more. > > Ok, one last mail before it turns into spam: with a 1KB database > blocksize, > > the query now runs in 30 seconds (original 70 on my machine, shared > buffers > > 240MB). > > The per inner loop access time now 24 microsecs compared to on my machine > > original 74 microsecs with 8KB size and 8 for the btree scan. Not a bad > > speedup with such a simple parameter :-) > > > > postgres=# EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b AND > b.b > > + 2; > > QUERY PLAN > > > > > --------------------------------------------------------------------------------------------------------------------------- > > Nested Loop (cost=0.00..4169159462.20 rows=111109777668 width=8) (actual > > time=0.184..29540.355 rows=2999997 loops=1) > > -> Seq Scan on b (cost=0.00..47037.62 rows=999962 width=4) (actual > > time=0.024..1783.484 rows=1000000 loops=1) > > -> Index Scan using a_a on a (cost=0.00..2224.78 rows=111114 width=4) > > (actual time=0.021..0.024 rows=3 loops=1000000) > > Index Cond: ((a.a >= b.b) AND (a.a <= (b.b + 2))) > > Total runtime: 30483.303 ms > > (5 rows) > > > > > > postgres=# select gist_stat('a_a'); > > gist_stat > > ------------------------------------------- > > Number of levels: 5 + > > Number of pages: 47618 + > > Number of leaf pages: 45454 + > > Number of tuples: 1047617 + > > Number of invalid tuples: 0 + > > Number of leaf tuples: 1000000 + > > Total size of tuples: 21523756 bytes+ > > Total size of leaf tuples: 20545448 bytes+ > > Total size of index: 48760832 bytes+ > > (1 row) > > > > > > -- > > Sent via pgsql-performance mailing list ( > pgsql-performance@postgresql.org) > > To make changes to your subscription: > > http://www.postgresql.org/mailpref/pgsql-performance > > > --0016e6db2b0a9282e104823dc836 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Fri, Mar 19, 2010 at 10:16 PM, Kenneth Marshall <ktm@rice.edu> wrote:
Hi Yeb,

I have not looked at the gist code, but would it be possible to
make virtual pages that have a size that is 1/power-of-2 * blocksize.
Then the leaf node could be 1/8 or even 1/16 the size of the full
pagesize.

Hello Ken,

The gist virtual pages= would then match more the original blocksizes that were used in Guttman= 9;s R-tree paper (first google result, then figure 4.5). Since the nature/c= haracteristics of the underlying datatypes and keys is not changed, it migh= t be that with the disk pages getting larger, gist indexing has therefore b= ecome unexpectedly inefficient.

But I am also not really into the core-gist code, but do have a motivat= ion to dive into it (more than 200% performance increase in Mathew's te= st case). However I'd like to verify for community support before worki= ng on it.

Maybe Theodor or Oleg could say something about how easy or hard it is = to do?

regards,
Yeb Havinga
=A0

Regards,
Ken

On Fri, Mar 19, 2010 at 09:49:30PM +0100, Yeb Havinga wrote:
> Yeb Havinga wrote:
>>
>> Since the gistpagesize is derived from the database blocksize, it = might be
>> wise to set the blocksize low for this case, I'm going to play= with this a
>> bit more.
> Ok, one last mail before it turns into spam: with a 1KB database block= size,
> the query now runs in 30 seconds (original 70 on my machine, shared bu= ffers
> 240MB).
> The per inner loop access time now 24 microsecs compared to on my mach= ine
> original 74 microsecs with 8KB size and 8 for the btree scan. Not a ba= d
> speedup with such a simple parameter :-)
>
> postgres=3D# EXPLAIN ANALYSE SELECT * FROM a, b WHERE a.a BETWEEN b.b = AND b.b
> + 2;
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0QUERY PLAN
>
> ----------------------------------------------------------------------= -----------------------------------------------------
> Nested Loop =A0(cost=3D0.00..4169159462.20 rows=3D111109777668 width= =3D8) (actual
> time=3D0.184..29540.355 rows=3D2999997 loops=3D1)
> =A0 -> =A0Seq Scan on b =A0(cost=3D0.00..47037.62 rows=3D999962 wid= th=3D4) (actual
> time=3D0.024..1783.484 rows=3D1000000 loops=3D1)
> =A0 -> =A0Index Scan using a_a on a =A0(cost=3D0.00..2224.78 rows= =3D111114 width=3D4)
> (actual time=3D0.021..0.024 rows=3D3 loops=3D1000000)
> =A0 =A0 =A0 =A0 Index Cond: ((a.a >=3D b.b) AND (a.a <=3D (b.b += 2)))
> Total runtime: 30483.303 ms
> (5 rows)
>
>
> postgres=3D# select gist_stat('a_a');
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 gist_stat
> -------------------------------------------
> Number of levels: =A0 =A0 =A0 =A0 =A05 =A0 =A0 =A0 =A0 =A0 =A0 +
> Number of pages: =A0 =A0 =A0 =A0 =A0 47618 =A0 =A0 =A0 =A0 +
> Number of leaf pages: =A0 =A0 =A045454 =A0 =A0 =A0 =A0 +
> Number of tuples: =A0 =A0 =A0 =A0 =A01047617 =A0 =A0 =A0 +
> Number of invalid tuples: =A00 =A0 =A0 =A0 =A0 =A0 =A0 +
> Number of leaf tuples: =A0 =A0 1000000 =A0 =A0 =A0 +
> Total size of tuples: =A0 =A0 =A021523756 bytes+
> Total size of leaf tuples: 20545448 bytes+
> Total size of index: =A0 =A0 =A0 48760832 bytes+
> (1 row)
>
>
> --
> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance
>

--0016e6db2b0a9282e104823dc836--