Received: from maia.hub.org (maia-2.hub.org [200.46.204.251]) by mail.postgresql.org (Postfix) with ESMTP id 67370B5DBDC for ; Thu, 11 Aug 2011 17:30:37 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.251]) (amavisd-maia, port 10024) with ESMTP id 55805-09 for ; Thu, 11 Aug 2011 20:30:27 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-qy0-f174.google.com (mail-qy0-f174.google.com [209.85.216.174]) by mail.postgresql.org (Postfix) with ESMTP id D2685B5DBD6 for ; Thu, 11 Aug 2011 17:30:26 -0300 (ADT) Received: by qyk38 with SMTP id 38so3706181qyk.19 for ; Thu, 11 Aug 2011 13:30:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=dO9XuNQd45s59FdKqft+SLyf0xhgXFyXZXqZ1feE0JY=; b=AZ2VQtmKOpJqJjPLAKKfcFIV7IrKZij8DMFdOshX5K/DOcQ8Y2XAodig7dfXqEQdGX 0uzBoCZ08N3l8Dg8o8UQSvrIsiGoCsBXUx7cS0MPab/r5aWy7hwtqz0lwz1D6u07CwOE 6pN4Z4YKChoQYn6Qe3ka9JSWcpE+FD1+aOjGw= Received: by 10.229.2.99 with SMTP id 35mr29155qci.280.1313094626091; Thu, 11 Aug 2011 13:30:26 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.162.197 with HTTP; Thu, 11 Aug 2011 13:30:06 -0700 (PDT) In-Reply-To: <4E43AEEA.2040105@enterprisedb.com> References: <4E2DBB60.80604@enterprisedb.com> <4E2EF83A.8000304@enterprisedb.com> <4E31D03D.70206@enterprisedb.com> <4E3977D8.1020506@enterprisedb.com> <4E3FAB1D.1060105@enterprisedb.com> <4E43AEEA.2040105@enterprisedb.com> From: Alexander Korotkov Date: Fri, 12 Aug 2011 00:30:06 +0400 Message-ID: Subject: Re: WIP: Fast GiST index build To: Heikki Linnakangas Cc: pgsql-hackers Content-Type: multipart/alternative; boundary=0016e6471302bea10a04aa40aa05 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.898 tagged_above=-5 required=5 tests=BAYES_00=-1.9, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001 X-Spam-Level: X-Archive-Number: 201108/546 X-Sequence-Number: 193301 --0016e6471302bea10a04aa40aa05 Content-Type: text/plain; charset=ISO-8859-1 On Thu, Aug 11, 2011 at 2:28 PM, Heikki Linnakangas < heikki.linnakangas@enterprisedb.com> wrote: > On 10.08.2011 22:44, Alexander Korotkov wrote: > >> Manual and readme updates. >> > > Thanks, I'm reviewing these now. > > Do we want to expose the level-step and buffersize parameters to users? > They've been useful during testing, but I'm thinking we should be able to > guess good enough values for them automatically, and just remove the > options. It's pretty much impossible for a user to tune them correctly, it > would require deep knowledge of the buffering algorithm. > > I'm thinking that even when you explicitly turn buffering on, we should > still process the first 10000 or so tuples with simple inserts. That way we > always have a sample of tuples to calculate the average tuple size from. > It's plausible that if the input data is ordered, looking at the first N > tuples will give skewed sample, but I don't think there's much danger of > that in practice. Even if the data is ordered, the length of GiST tuples > shouldn't vary much. > > What happens if we get the levelstep and pagesPerBuffer estimates wrong? > How sensitive is the algorithm to that? Or will we run out of memory? Would > it be feasible to adjust those in the middle of the index build, if we e.g > exceed the estimated memory usage greatly? I see the following risks. For levelstep: Too small: not so great IO benefit as can be Too large: 1) If subtree doesn't fit effective_cache, much more IO then should be (because of cache misses during buffer emptying) 2) If last pages of buffers don't fit to maintenance_work_mem, possible OOM For buffersize: Too small: less IO benefit, becuse buffer size is relatively small in comparison with sub-tree size. Too large: greater CPU overhead (because of more penalty calls) then can be with same IO benefit. Thereby I propose following. 1) Too large levelstep is greatest risk. Let's use pessimistic estimate for it. Pessimistic estimate has following logic: largest sub-tree => maximal tuples per page => minimal tuple size Thereby always using minimal tuple size in levelstep calculation we exclude greatest risks. 2) Risks of buffersize are comparable and not too critical. Thats why I propose to use size of first 10000 tuples for estimate. ------ With best regards, Alexander Korotkov. --0016e6471302bea10a04aa40aa05 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
On Thu, Aug 11, 2011 at 2:28 PM, Heikki Linnakan= gas <heikki.linnakangas@enterprisedb.com> = wrote:
On 10.08.2011 22:44, Alexander Korotkov wrote:
Manual and readme updates.

Thanks, I'm reviewing these now.

Do we want to expose the level-step and buffersize parameters to users? The= y've been useful during testing, but I'm thinking we should be able= to guess good enough values for them automatically, and just remove the op= tions. It's pretty much impossible for a user to tune them correctly, i= t would require deep knowledge of the buffering algorithm.

I'm thinking that even when you explicitly turn buffering on, we should= still process the first 10000 or so tuples with simple inserts. That way w= e always have a sample of tuples to calculate the average tuple size from. = It's plausible that if the input data is ordered, looking at the first = N tuples will give skewed sample, but I don't think there's much da= nger of that in practice. Even if the data is ordered, the length of GiST t= uples shouldn't vary much.

What happens if we get the levelstep and pagesPerBuffer estimates wrong? Ho= w sensitive is the algorithm to that? Or will we run out of memory? Would i= t be feasible to adjust those in the middle of the index build, if we e.g e= xceed the estimated memory usage greatly?

I see the following risks.
<= br>For levelstep:
Too small: not so great IO benefit as can be
Too la= rge:=A0
=A0 1) If subtree doesn't fit effective_cache, much more IO = then should be (because of cache misses during buffer emptying)
=A0 2) If last pages of buffers don't fit to maintenance_work_mem, poss= ible OOM

For buffersize:
Too small: = less IO benefit, becuse buffer size is relatively small in comparison with = sub-tree size.
Too large: greater CPU overhead (because of more penalty calls) then can be= with same IO benefit.

Thereby I propos= e following.
1) Too large levelstep is greatest risk. Let's use pess= imistic estimate for it. Pessimistic estimate has following logic:
largest sub-tree =3D> maximal tuples per page =3D> minimal tuple size=
Thereby always using=A0minimal tuple size in levelstep calculation we e= xclude greatest risks.
2) Risks of buffersize are comparable and not too= critical. Thats why I propose to use size of first=A010000 tuples for esti= mate.

------
With best regards,
Alexan= der Korotkov. =A0
--0016e6471302bea10a04aa40aa05--