Received: from maia.hub.org (unknown [200.46.208.211]) by mail.postgresql.org (Postfix) with ESMTP id 6BB846332DC for ; Tue, 2 Mar 2010 12:23:37 -0400 (AST) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.208.211]) (amavisd-maia, port 10024) with ESMTP id 67579-03 for ; Tue, 2 Mar 2010 16:23:26 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-fx0-f223.google.com (mail-fx0-f223.google.com [209.85.220.223]) by mail.postgresql.org (Postfix) with ESMTP id 850E1632B8A for ; Tue, 2 Mar 2010 12:23:26 -0400 (AST) Received: by fxm23 with SMTP id 23so6492fxm.3 for ; Tue, 02 Mar 2010 08:23:25 -0800 (PST) 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 :content-transfer-encoding; bh=b1Wkvb0b2CjoU/QIEtjdClneG5650dtz6XLCUKgdKWU=; b=YwH0VhIgah2v9OwZu5vOET8YGq2SYRhBLEHAq7gkoU6PyOxv+g5MSTzDqHu1TtT5Zx qxTXLZo5OUPPgIRMDbsA0d3wC23MlirQPdwstRh9sFz9H0x5bohDwWrs3fZjbWh4ZPD4 mjO2jKHyXPW6+BIBdNH5XMwVve0g5FKlcwbF8= 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=sa3vpw01WeO4jfJjIBm5sXRf8a1e4udckQGpdaDhjwCKIJGU0PXVFu5qQozIopA7jv qFYZzMYTo9CSXFz/MnBD/wL+/xkQ6gT9bdeFId9i2iJWMEwriCo11EOCMR2j7rUQaNNH nRNQmCrnTCqbzVWepAXrnSefSRC+MSlnd3cOI= MIME-Version: 1.0 Received: by 10.239.186.80 with SMTP id f16mr729378hbh.125.1267547002802; Tue, 02 Mar 2010 08:23:22 -0800 (PST) In-Reply-To: <201002252344.o1PNi2007379@momjian.us> References: <201002252344.o1PNi2007379@momjian.us> Date: Tue, 2 Mar 2010 11:23:22 -0500 Message-ID: <603c8f071003020823k128f1b85y9240d954293d0602@mail.gmail.com> Subject: Re: GiST index performance From: Robert Haas To: Bruce Momjian Cc: Matthew Wakeling , Oleg Bartunov , Tom Lane , Teodor Sigaev , Kevin Grittner , pgsql-performance@postgresql.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-2.481 tagged_above=-10 required=5 tests=AWL=0.118, BAYES_00=-2.599 X-Spam-Level: X-Archive-Number: 201003/21 X-Sequence-Number: 37846 On Thu, Feb 25, 2010 at 6:44 PM, Bruce Momjian wrote: > Was this corrected? =A0I don't see any commits to seg.c. I don't think this was ever reviewed. It seems like a good patch but I'd be skeptical of committing it now unless someone has the time to review it carefully. If not, let's add it to the next CF so we don't lose it again. ...Robert > > -------------------------------------------------------------------------= -- > > Matthew Wakeling wrote: >> On Thu, 7 May 2009, Oleg Bartunov wrote: >> > Did you try Guttman quadratic split algorithm ? We also found linear >> > split algorithm for Rtree. >> >> The existing (bugfixed) seg split algorithm is the Guttman quadratic spl= it >> algorithm. Guttman did all his work on two-dimensional and above data, >> dismissing one-dimensional data as being handled adequately by B-trees, >> which is not true for segment overlaps. It turns out that the algorithm >> has a weakness with certain types of data, and one-dimensional data is >> almost certain to exercise that weakness. The greater the number of >> dimensions, the less the weakness is exercised. >> >> The problem is that the algorithm does not calculate a split pivot. >> Instead it finds two suitable entries, and adds the remaining entries to >> those two in turn. This can lead to the majority of the entries being >> added to just one side. In fact, I saw lots of cases where 367 entries >> were being split into two pages of 366 and one entry. >> >> Guttman's linear split algorithm has the same weakness. >> >> >> One thing I am seeing is a really big difference in performance betwe= en >> >> Postgres/GiST and a Java implementation I have written, using the sam= e >> >> algorithms. Postgres takes three minutes to perform a set of index lo= okups >> >> while java takes six seconds. The old version of bioseg took an hour.= I >> >> can't see anything in the GiST support code that could account for th= is. >> > >> > is the number of index lookups different, or just index lookup time is= very >> > big ? >> >> Same number of index lookups. Same algorithms. I have a set of 681879 >> segments, and I load them all into the index. I then query the index for >> overlaps for each one in turn. For some reason, GiST lookups seem to be >> slow, even if they are using a good algorithm. I have seen that problem >> with btree_gist on integers too. I can't see any reason for this is the >> GiST code - it all seems pretty tight to me. We probably need to do some >> profiling. >> >> Matthew >> >> -- >> =A0I suppose some of you have done a Continuous Maths course. Yes? Conti= nuous >> =A0Maths? Whoah, it was like that, was i= t! >> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 = =A0 =A0 -- Computer Science Lecturer >> >> -- >> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.or= g) >> To make changes to your subscription: >> http://www.postgresql.org/mailpref/pgsql-performance > > -- > =A0Bruce Momjian =A0 =A0 =A0 =A0 =A0http://momjian.us > =A0EnterpriseDB =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 h= ttp://enterprisedb.com > =A0PG East: =A0http://www.enterprisedb.com/community/nav-pg-east-2010.do > =A0+ If your life is a hard drive, Christ can be your backup. + > > -- > Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org= ) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-performance >