Received: from maia.hub.org (maia-5.hub.org [200.46.204.29]) by mail.postgresql.org (Postfix) with ESMTP id 22FD5B5DBC4 for ; Thu, 22 Sep 2011 07:05:45 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.29]) (amavisd-maia, port 10024) with ESMTP id 91934-08 for ; Thu, 22 Sep 2011 10:05:38 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0-rc2 Received: from exprod7og108.obsmtp.com (exprod7og108.obsmtp.com [64.18.2.169]) by mail.postgresql.org (Postfix) with ESMTP id DEAE2B5DC61 for ; Thu, 22 Sep 2011 07:05:37 -0300 (ADT) Received: from mail-fx0-f48.google.com ([209.85.161.48]) (using TLSv1) by exprod7ob108.postini.com ([64.18.6.12]) with SMTP ID DSNKTnsIcQFqBy6oSnVMjINSBwwZtt/Qu5/h@postini.com; Thu, 22 Sep 2011 03:05:38 PDT Received: by mail-fx0-f48.google.com with SMTP id 23so2453439fxd.7 for ; Thu, 22 Sep 2011 03:05:37 -0700 (PDT) Received: by 10.223.39.91 with SMTP id f27mr2787952fae.26.1316685936895; Thu, 22 Sep 2011 03:05:36 -0700 (PDT) Received: from [192.168.1.183] (dsl-hkibrasgw2-ff7ac300-240.dhcp.inet.fi. [88.195.122.240]) by mx.google.com with ESMTPS id e17sm6996810fae.17.2011.09.22.03.05.34 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 22 Sep 2011 03:05:35 -0700 (PDT) Message-ID: <4E7B086D.5050602@enterprisedb.com> Date: Thu, 22 Sep 2011 13:05:33 +0300 From: Heikki Linnakangas User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; fi-FI; rv:1.9.2.21) Gecko/20110831 Icedove/3.1.13 MIME-Version: 1.0 To: Oleg Bartunov CC: Pgsql Hackers Subject: Re: WIP: SP-GiST, Space-Partitioned GiST References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.9 tagged_above=-5 required=5 tests=BAYES_00=-1.9 X-Spam-Level: X-Archive-Number: 201109/1113 X-Sequence-Number: 195302 On 06.09.2011 20:34, Oleg Bartunov wrote: > Here is the latest spgist patch, which has all planned features as well as > all overhead, introduced by concurrency and recovery, so performance > measurement should be realistic now. I'm ignoring the text suffix-tree part of this for now, because of the issue with non-C locales that Alexander pointer out. Regarding the quadtree, have you compared the performance of that with Alexander's improved split algorithm? I ran some tests using the test harness I still had lying around from the fast GiST index build tests: testname | time | accesses | indexsize -------------------------+-----------------+----------+----------- points unordered auto | 00:03:58.188866 | 378779 | 522 MB points ordered auto | 00:07:14.362355 | 177534 | 670 MB points unordered auto | 00:02:59.130176 | 46561 | 532 MB points ordered auto | 00:04:00.50756 | 45066 | 662 MB points unordered spgist | 00:03:05.569259 | 78871 | 394 MB points ordered spgist | 00:01:46.06855 | 422104 | 417 MB (8 rows) These tests were with a table with 7500000 random points. In the ordered-tests, the table is sorted by x,y coordinates. 'time' is the time used to build the index on it, and 'accesses' is the total number of index blocks hit by a series of 10000 bounding box queries, measured from pg_statio_user_indexes.idx_blks_hit + idx_blks_read. The first two tests in the list are with a GiST index on unpatched PostgreSQL. The next six tests are with Alexander's double-sorting split patch. The last two tests are with an SP-GiST index. It looks like the query performance with GiST using the double-sorting split is better than SP-GiST, although the SP-GiST index is somewhat smaller. The ordered case seems pathologically bad, is that some sort of a worst-case scenario for quadtrees? -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com