pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Alexander Korotkov <aekorotkov@gmail.com>
To: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
Date: Fri, 22 Jul 2011 13:38:35 +0400
Message-ID: <CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com> (raw)
In-Reply-To: <CAPpHfdtVJJyinb1TuFF3gw6-YLre2O9svUZgZGAWzogXswP6Bg@mail.gmail.com>
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@mail.gmail.com>
	<BANLkTinN6C8q61Fb8ASZVOPbYq7VoqoHOw@mail.gmail.com>
	<BANLkTin=gyX5PJW-JaN59uqRBSgdDHVNNA@mail.gmail.com>
	<BANLkTikSbaun6Sf8hJSkO0D4nu7VC2O35A@mail.gmail.com>
	<4E044D68.5070605@enterprisedb.com>
	<BANLkTi=umLx8LBCSmALKpoGTFguqQxQ61w@mail.gmail.com>
	<BANLkTinK-ZL-yQCNtKZLfGS=8VGmO13b8g@mail.gmail.com>
	<4E0894FF.8080202@enterprisedb.com>
	<BANLkTi=1TL+pH2sxiR7nf3oMFdWAHHgSyA@mail.gmail.com>
	<CAPpHfdt6ER8LKEEmnVnbYuaODKpDb4S5UuGRa5prio--Kp=LFw@mail.gmail.com>
	<26338.1310134685@sss.pgh.pa.us>
	<CAPpHfduE1LM7aCk7MZ_u_n2z58Jxps=TBD0eX4WX4gwBrkk=Yw@mail.gmail.com>
	<CAPpHfdvcAo2L2RVtnr+BtPE18Q4mJLaLf-R7SrKMTUousv8ChA@mail.gmail.com>
	<4E1DA4CB.9020209@enterprisedb.com>
	<CAPpHfdvSC3p7zR_BwbNhm+3fvg8b-rwe+p=HJ9Gii8_rethbuw@mail.gmail.com>
	<4E1EABD9.5000308@enterprisedb.com>
	<CAPpHfdsO3BBEXzBwcrVGHXE=dYUOhQ+corT3gLLtCkjNXacHoQ@mail.gmail.com>
	<CAPpHfdv=V+UGFyq=EJeLUzxygN3m63H0yocX4jsAmEBha7NKRw@mail.gmail.com>
	<4E1F5763.9090109@enterprisedb.com>
	<CAPpHfdszFQ7KyWurN7+AMSdG-v4m-p=HgpLPH=XUZqbnGJf+og@mail.gmail.com>
	<CAPpHfdtVJJyinb1TuFF3gw6-YLre2O9svUZgZGAWzogXswP6Bg@mail.gmail.com>

Hi!

Patch with my try to detect ordered datasets is attached. The implemented
idea is desribed below.
Index tuples are divided by chunks of 128. On each chunk we measure how much
leaf pages where index tuples was inserted don't match those of previous
chunk. Based on statistics of several chunks we estimate distribution of
accesses between lead pages (exponential distribution law is accumed and
it's seems to be an error). After that we can estimate portion of index
tuples which can be processed without actual IO. If this estimate exceeds
threshold then we should switch to buffering build.
Now my implementation successfully detects randomly mixed datasets and well
ordered datasets, but it's seems to be too optimistic about intermediate
cases. I believe it's due to wrong assumption about distribution law.
Do you think this approach is acceptable? Probably there are some researches
about distribution law for such cases (while I didn't find anything relevant
in google scholar)?
As an alternative I can propose take into account actual average IO
operations per tuple rather then an estimate.

------
With best regards,
Alexander Korotkov.

On Mon, Jul 18, 2011 at 10:00 PM, Alexander Korotkov
<aekorotkov@gmail.com>wrote:

> Hi!
>
> New version of patch is attached. There are following changes.
> 1) Since proposed tchnique is not always a "fast" build, it was renamed
> everywhere in the patch to "buffering" build.
> 2) Parameter "buffering" now has 3 possible values "yes", "no" and "auto".
> "auto" means automatic switching from regular index build to buffering one.
> Currently it just switch when index size exceeds maintenance_work_mem.
> 3) Holding of many buffers pinned is avoided.
> 4) Rebased with head.
>
> TODO:
> 1) Take care about ordered datasets in automatic switching.
> 2) Take care about concurrent backends in automatic switching.
>
> ------
> With best regards,
> Alexander Korotkov.
>

Attachments:

  gist_fast_build-0.8.0.patch.gz (application/x-gzip, 28.8K) download

view thread (114+ messages)  latest in thread

Message-ID: <CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com>
Permalink:  ../CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com/
Also on:    postgresql.org/message-id/CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-hackers@postgresql.org
  Cc: aekorotkov@gmail.com, heikki.linnakangas@enterprisedb.com
  Subject: Re: WIP: Fast GiST index build
  In-Reply-To: <CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox