Message-ID: <4E64F911.8010007@enterprisedb.com>
Date: Mon, 05 Sep 2011 19:30:09 +0300
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
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
CC: Alexander Korotkov <aekorotkov@gmail.com>,
	Robert Haas <robertmhaas@gmail.com>,
	pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@mail.gmail.com>
	<CA+TgmoZoON6aAE3NB9=GF9oAdF=Kkz21+MmoE5P_kA9aKN-OQA@mail.gmail.com>
	<CAPpHfdu4DusbHtMLE+csQJj61rMg_JtFOGSwrQVoOF5wPBkixQ@mail.gmail.com>
	<CAPpHfdtMe6yizpbT+Lsx0mWSW9thPV9KosSrUsSEMNRBHUWUPw@mail.gmail.com>
	<4E4AAC49.7070401@enterprisedb.com>
	<CAPpHfduTY5FqYdA_AB2zQ5MYyaeEqc5fRLLPgGBOymDXu16gFQ@mail.gmail.com>
	<4E4AC0B9.8070203@enterprisedb.com>
	<4E4AC1C3.4070003@enterprisedb.com>
	<CAPpHfdtAcs9UujarOUJdJR2-uPczBbaegooAa3vYwM6q5zVBBQ@mail.gmail.com>
	<CAPpHfdu80rXcNHZ9gen-qA4sZc0bQAKS9hEU_EP5GRqWN4F0Ng@mail.gmail.com>
	<4E569D9A.4020308@enterprisedb.com>
	<CAPpHfdsoHciGGearBYQv8+J5L=Eni3mzJ0qjHpq3jb+BjzzYGg@mail.gmail.com>
	<4E5CA88C.50008@enterprisedb.com>
	<CAPpHfdu=BUTTqk-t04DrqTyWH1MHH2JPJZwsNLjbDAk8SH5EyQ@mail.gmail.com>
	<4E5F495F.2010303@enterprisedb.com>
	<CAPpHfdsUTusxjB26cHnbVWCFkxQc87juJsTkkoPUj=GrJzU5ag@mail.gmail.com>
	<4E64AE3E.9000901@enterprisedb.com>
In-Reply-To: <4E64AE3E.9000901@enterprisedb.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 05.09.2011 14:10, Heikki Linnakangas wrote:
> On 01.09.2011 12:23, Alexander Korotkov wrote:
>> On Thu, Sep 1, 2011 at 12:59 PM, Heikki Linnakangas<
>> heikki.linnakangas@enterprisedb.com> wrote:
>>
>>> So I changed the test script to generate the table as:
>>>
>>> CREATE TABLE points AS SELECT random() as x, random() as y FROM
>>> generate_series(1, $NROWS);
>>>
>>> The unordered results are in:
>>>
>>> testname | nrows | duration | accesses
>>> -----------------------------+**-----------+-----------------+**----------
>>>
>>> points unordered buffered | 250000000 | 05:56:58.575789 | 2241050
>>> points unordered auto | 250000000 | 05:34:12.187479 | 2246420
>>> points unordered unbuffered | 250000000 | 04:38:48.663952 | 2244228
>>>
>>> Although the buffered build doesn't lose as badly as it did with more
>>> overlap, it still doesn't look good :-(. Any ideas?
>>
>> But it's still a lot of overlap. It's about 220 accesses per small area
>> request. It's about 10 - 20 times greater than should be without
>> overlaps.
>> If we roughly assume that 10 times more overlap makes 1/10 of tree to be
>> used for actual inserts, then that part of tree can easily fit to the
>> cache.
>> You can try my splitting algorithm on your test setup (it this case I
>> advice
>> to start from smaller number of rows, 100 M for example).
>> I'm requesting real-life datasets which makes troubles in real life from
>> Oleg. Probably those datasets is even larger or new linear split produce
>> less overlaps on them.
>
> I made a small tweak to the patch, and got much better results (this is
> with my original method of generating the data):
>
> testname | nrows | duration | accesses
> -----------------------------+-----------+-----------------+----------
> points unordered buffered | 250000000 | 03:34:23.488275 | 3945486
> points unordered auto | 250000000 | 02:55:10.248722 | 3767548
> points unordered unbuffered | 250000000 | 04:02:04.168138 | 4564986

The full results of this test are in:

           testname           |   nrows   |    duration     | accesses
-----------------------------+-----------+-----------------+----------
  points unordered buffered   | 250000000 | 03:34:23.488275 |  3945486
  points unordered auto       | 250000000 | 02:55:10.248722 |  3767548
  points unordered unbuffered | 250000000 | 04:02:04.168138 |  4564986
  points ordered buffered     | 250000000 | 02:00:10.467914 |  5572906
  points ordered auto         | 250000000 | 02:16:01.859039 |  5435673
  points ordered unbuffered   | 250000000 | 03:23:18.061742 |  1875826
(6 rows)

Interestingly, in this test case the buffered build was significantly 
faster even in the case of ordered input - but the quality of the 
produced index was much worse. I suspect it's because of the 
last-in-first-out nature of the buffering, tuples that pushed into 
buffers first are flushed to lower levels last. Tweaking the data 
structures to make the buffer flushing a FIFO process might help with 
that, but I'm afraid that might make our cache hit ratio worse when 
reading pages from the temporary file.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com