Received: from maia.hub.org (maia-5.hub.org [200.46.204.29]) by mail.postgresql.org (Postfix) with ESMTP id 266B3B5F6BC for ; Mon, 6 Jun 2011 09:00:56 -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 35973-05 for ; Mon, 6 Jun 2011 12:00:48 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-qy0-f181.google.com (mail-qy0-f181.google.com [209.85.216.181]) by mail.postgresql.org (Postfix) with ESMTP id 5D0A7B5DE26 for ; Mon, 6 Jun 2011 09:00:48 -0300 (ADT) Received: by qyg14 with SMTP id 14so1892065qyg.19 for ; Mon, 06 Jun 2011 05:00:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=FJmr4l7v4pxmQzx6R378PDqCiahemTySJz/r9n7DuH8=; b=fX8udje+y2eO11ZKtF/fJN5506Yyd7Af6YVhVkmg0wMu5N70hyijxvBQM5lPfrAh6c JXtNYWXT7Xcm/RMrEiQRPwcVd6OBCGmu3JwJpw0luJtWgRTC5atz33Iv30de48mKhezB kQtk9jcUM0OR6Mu/iCHnnVdx541fkk8mhlcHk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=skKj6EtoCzuSjb+f9pth58x6OrCy2iMVyr5D7ZNnHwL1pd5OkVaQ+dSvnBcPBGuclA Bk8xFqRaNsQ5BD1+KWklWgittKNBuxTGw2QO7LFAJ5vEzI2RXY5pjmdy4I9Mn1BfF4Nr 74LYlu5eU0R2lgeh7SoipRgDgm7ejbqltEnU8= Received: by 10.229.10.131 with SMTP id p3mr3462085qcp.166.1307361648221; Mon, 06 Jun 2011 05:00:48 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.247.140 with HTTP; Mon, 6 Jun 2011 05:00:28 -0700 (PDT) In-Reply-To: <4DECB141.2040707@enterprisedb.com> References: <4DEC84D7.7040602@enterprisedb.com> <4DECB141.2040707@enterprisedb.com> From: Alexander Korotkov Date: Mon, 6 Jun 2011 16:00:28 +0400 Message-ID: Subject: Re: WIP: Fast GiST index build To: Heikki Linnakangas Cc: pgsql-hackers Content-Type: multipart/alternative; boundary=001517574684a29f3604a509da5a X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.582 tagged_above=-5 required=5 tests=BAYES_00=-1.9, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RFC_ABUSE_POST=0.001, SARE_MILLIONSOF=0.315 X-Spam-Level: X-Archive-Number: 201106/393 X-Sequence-Number: 189106 --001517574684a29f3604a509da5a Content-Type: text/plain; charset=ISO-8859-1 Hi! On Mon, Jun 6, 2011 at 2:51 PM, Heikki Linnakangas < heikki.linnakangas@enterprisedb.com> wrote: > On 06.06.2011 10:42, Heikki Linnakangas wrote: >> >> I ran another test with a simple table generated with: >> >> CREATE TABLE pointtest (p point); >> INSERT INTO pointtest SELECT point(random(), random()) FROM >> generate_series(1,50000000); >> >> Generating a gist index with: >> >> CREATE INDEX i_pointtest ON pointtest USING gist (p); >> >> took about 15 hours without the patch, and 2 hours with it. That's quite >> dramatic. >> > > Oops, that was a rounding error, sorry. The run took about 2.7 hours with > the patch, which of course should be rounded to 3 hours, not 2. Anyway, it > is still a very impressive improvement. > I have similar results on 100 millions of rows: 21.6 hours without patch and 2 hours with patch. But I found a problem: index quality is worse. See following query plans. There test is relation where index was created in ordinal way, and test2 is relation where patch was used. QUERY PLAN --------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test (cost=4391.01..270397.31 rows=100000 width=20) (actual time=1.257..2.147 rows=838 loops=1) Recheck Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box) Buffers: shared hit=968 -> Bitmap Index Scan on test_idx (cost=0.00..4366.01 rows=100000 width=0) (actual time=1.162..1.162 rows=838 loops=1) Index Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box) Buffers: shared hit=131 Total runtime: 2.214 ms (7 rows) QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test2 (cost=4370.84..270377.13 rows=100000 width=20) (actual time=5.252..6.056 rows=838 loops=1) Recheck Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box) Buffers: shared hit=1458 -> Bitmap Index Scan on test2_idx (cost=0.00..4345.84 rows=100000 width=0) (actual time=5.155..5.155 rows=838 loops=1) Index Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box) Buffers: shared hit=621 Total runtime: 6.121 ms (7 rows) QUERY PLAN --------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test (cost=4391.01..270397.31 rows=100000 width=20) (actual time=2.148..2.977 rows=850 loops=1) Recheck Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box) Buffers: shared hit=1099 -> Bitmap Index Scan on test_idx (cost=0.00..4366.01 rows=100000 width=0) (actual time=2.052..2.052 rows=850 loops=1) Index Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box) Buffers: shared hit=249 Total runtime: 3.033 ms (7 rows) QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on test2 (cost=4370.84..270377.13 rows=100000 width=20) (actual time=6.806..7.602 rows=850 loops=1) Recheck Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box) Buffers: shared hit=1615 -> Bitmap Index Scan on test2_idx (cost=0.00..4345.84 rows=100000 width=0) (actual time=6.709..6.709 rows=850 loops=1) Index Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box) Buffers: shared hit=773 Total runtime: 7.667 ms (7 rows) We can see that index scan requires read of several times more pages. Original paper denotes such effect. It explains it by the routing rectangles in less optimal ways. But this effect wasn't so dramatic in tests provided in the paper. So, I have following thoughts about this problem: 1) Number of pages, which was readed from index is too large even with ordinal index build. Querying of small area requires read of hundred of pages. It probbably caused by picksplit implementation. I've version of picksplit algorithm which seems to be much more efficient. I'll do some benchmarks with my picksplit algorithm. I hope difference in index quality will be not so dramatic. 2) I can try to do some enchancements in fast build alogrithms which could improve tree quality. In original paper Hilbert heuristic was used to achive even better tree quality than tree which was created in ordinal way. But since we use GiST we are restricted by it's interface (or we have to create new interface functions(s), but I like to avoid it). I would like to try to do some ordering by penalty value in buffer emptying process and buffers relocation on split. 3) Probably, there is some bug which affects tree quality. > Could you please create a TODO list on the wiki page, listing all the > missing features, known bugs etc. that will need to be fixed? That'll make > it easier to see how much work there is left. It'll also help anyone looking > at the patch to know which issues are known issues. > Sure. I'll create such list on wiki page. I believe that currenlty most important issue is index quality. > Meanwhile, it would still be very valuable if others could test this with > different workloads. And Alexander, it would be good if at some point you > could write some benchmark scripts too, and put them on the wiki page, just > to see what kind of workloads have been taken into consideration and tested > already. Do you think there's some worst-case data distributions where this > algorithm would perform particularly badly? I don't expect some bad cases in terms in IO. My most worrying is about index quality which is strongly related to data distribution. ------ With best regards, Alexander Korotkov. --001517574684a29f3604a509da5a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hi!

On Mon, Jun 6, 2011 at 2:51 PM, Heikki Linnakangas &l= t;heikki.linnakangas= @enterprisedb.com> wrote:
On 06.06.2011 10:42, Heikki Linnakangas w= rote:
I ran another test with a simple table generated with:

CREATE TABLE pointtest (p point);
INSERT INTO pointtest SELECT point(random(), random()) FROM
generate_series(1,50000000);

Generating a gist index with:

CREATE INDEX i_pointtest ON pointtest USING gist (p);

took about 15 hours without the patch, and 2 hours with it. That's quit= e
dramatic.

Oops, that was a rounding error, sorry. The run took about 2.7 hours with t= he patch, which of course should be rounded to 3 hours, not 2. Anyway, it i= s still a very impressive improvement.
I have similar= =A0results on 100 millions of rows:=A021.6 hours without patch and 2 hours = with patch. But I found a problem: index quality is worse. See following qu= ery plans. There test is relation where index was created in ordinal way, a= nd test2 is relation where patch was used.

=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 =A0 QUERY PLAN = =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 =A0=A0
-------------------------= ---------------------------------------------------------------------------= -----------------------
=A0Bitmap Heap Scan on test =A0(cost=3D4391.01..270397.31 rows=3D10000= 0 width=3D20) (actual time=3D1.257..2.147 rows=3D838 loops=3D1)
= =A0 =A0Recheck Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box)
=
=A0 =A0Buffers: shared hit=3D968
=A0 =A0-> =A0Bitmap Index Scan on test_idx =A0(cost=3D0.00..4366.01= rows=3D100000 width=3D0) (actual time=3D1.162..1.162 rows=3D838 loops=3D1)=
=A0 =A0 =A0 =A0 =A0Index Cond: (v <@ '(0.903,0.203),(0.9,= 0.2)'::box)
=A0 =A0 =A0 =A0 =A0Buffers: shared hit=3D131
=A0Total runtime: 2.= 214 ms
(7 rows)

=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 =A0 =A0QUERY PLAN =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 =A0=A0
----------------------------------------------------------------------= ------------------------------------------------------
=A0Bitmap = Heap Scan on test2 =A0(cost=3D4370.84..270377.13 rows=3D100000 width=3D20) = (actual time=3D5.252..6.056 rows=3D838 loops=3D1)
=A0 =A0Recheck Cond: (v <@ '(0.903,0.203),(0.9,0.2)'::box)<= /div>
=A0 =A0Buffers: shared hit=3D1458
=A0 =A0-> =A0Bitma= p Index Scan on test2_idx =A0(cost=3D0.00..4345.84 rows=3D100000 width=3D0)= (actual time=3D5.155..5.155 rows=3D838 loops=3D1)
=A0 =A0 =A0 =A0 =A0Index Cond: (v <@ '(0.903,0.203),(0.9,0.2)&#= 39;::box)
=A0 =A0 =A0 =A0 =A0Buffers: shared hit=3D621
= =A0Total runtime: 6.121 ms
(7 rows)

=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 =A0 QUERY PLAN =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 =A0=A0
----------------------------------------------------------------------= -----------------------------------------------------
=A0Bitmap H= eap Scan on test =A0(cost=3D4391.01..270397.31 rows=3D100000 width=3D20) (a= ctual time=3D2.148..2.977 rows=3D850 loops=3D1)
=A0 =A0Recheck Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box)<= /div>
=A0 =A0Buffers: shared hit=3D1099
=A0 =A0-> =A0Bitma= p Index Scan on test_idx =A0(cost=3D0.00..4366.01 rows=3D100000 width=3D0) = (actual time=3D2.052..2.052 rows=3D850 loops=3D1)
=A0 =A0 =A0 =A0 =A0Index Cond: (v <@ '(0.503,0.503),(0.5,0.5)&#= 39;::box)
=A0 =A0 =A0 =A0 =A0Buffers: shared hit=3D249
= =A0Total runtime: 3.033 ms
(7 rows)

=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 =A0 =A0QUERY PLAN =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 =A0=A0
----------------------------------------------------------------------= ------------------------------------------------------
=A0Bitmap = Heap Scan on test2 =A0(cost=3D4370.84..270377.13 rows=3D100000 width=3D20) = (actual time=3D6.806..7.602 rows=3D850 loops=3D1)
=A0 =A0Recheck Cond: (v <@ '(0.503,0.503),(0.5,0.5)'::box)<= /div>
=A0 =A0Buffers: shared hit=3D1615
=A0 =A0-> =A0Bitma= p Index Scan on test2_idx =A0(cost=3D0.00..4345.84 rows=3D100000 width=3D0)= (actual time=3D6.709..6.709 rows=3D850 loops=3D1)
=A0 =A0 =A0 =A0 =A0Index Cond: (v <@ '(0.503,0.503),(0.5,0.5)&#= 39;::box)
=A0 =A0 =A0 =A0 =A0Buffers: shared hit=3D773
= =A0Total runtime: 7.667 ms
(7 rows)

We can see that index scan requires read of several times more pages.=A0O= riginal paper denotes such effect. It explains it by the routing rectangles= in less optimal ways. But this effect wasn't so dramatic in tests prov= ided in the paper. So, I have following thoughts about this problem:

1) Number of pages, which was readed from index is too la= rge even with ordinal index build. Querying of small area requires read of = hundred of pages. It probbably caused by picksplit implementation. I've= version of picksplit algorithm which seems to be much more efficient. I= 9;ll do some benchmarks with my picksplit algorithm. I hope difference in i= ndex quality will be not so dramatic.

2) I can try to do some enchancements in fast build alo= grithms which could improve tree quality. In original paper Hilbert=A0heuri= stic was used to achive even better tree quality than tree which was create= d in ordinal way. But since we use GiST we are restricted by it's inter= face (or we have to create new interface functions(s), but I like to avoid = it). I would like to try to do some ordering by penalty value in buffer emp= tying process and buffers relocation on split.

3) Probably, there is some bug which affects tree quali= ty.
=A0
Could you please cre= ate a TODO list on the wiki page, listing all the missing features, known b= ugs etc. that will need to be fixed? That'll make it easier to see how = much work there is left. It'll also help anyone looking at the patch to= know which issues are known issues.
Sure. I'll create such list on wiki page. I believe t= hat currenlty most important issue is index quality.
=A0
Meanwhile, it would still be very valuable if others could test this with d= ifferent workloads. And Alexander, it would be good if at some point you co= uld write some benchmark scripts too, and put them on the wiki page, just t= o see what kind of workloads have been taken into consideration and tested = already. Do you think there's some worst-case data distributions where = this algorithm would perform particularly badly?
I don't expect some bad cases in terms in IO. My most worrying is = about index quality which is strongly related to data distribution.

------<= span class=3D"Apple-style-span" style=3D"border-collapse: collapse; font-fa= mily: arial, sans-serif; font-size: 13px; ">
With best regards,
Alexander Korotkov.
--001517574684a29f3604a509da5a--