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

help / color / mirror / Atom feed
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
To: Alexander Korotkov <aekorotkov@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
Date: Mon, 25 Jul 2011 21:52:16 +0300
Message-ID: <4E2DBB60.80604@enterprisedb.com> (raw)
In-Reply-To: <CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com>
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@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>
	<CAPpHfdvoOh78ycX3eRePTS29635pHCSTfLdFDzHZhxTKsggCuQ@mail.gmail.com>

On 22.07.2011 12:38, Alexander Korotkov wrote:
> 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)?

Great! It would be nice to find a more scientific approach to this, but 
that's probably fine for now. It's time to start cleaning up the patch 
for eventual commit.

You got rid of the extra page pins, which is good, but I wonder why you 
still pre-create all the GISTLoadedPartItem structs for the whole 
subtree in loadTreePart() ? Can't you create those structs on-the-fly, 
when you descend the tree? I understand that it's difficult to update 
all the parent-pointers as trees are split, but it feels like there's 
way too much bookkeeping going on. Surely it's possible to simplify it 
somehow..

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



view thread (114+ messages)  latest in thread

Message-ID: <4E2DBB60.80604@enterprisedb.com>
Permalink:  ../4E2DBB60.80604@enterprisedb.com/
Also on:    postgresql.org/message-id/4E2DBB60.80604@enterprisedb.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: heikki.linnakangas@enterprisedb.com, aekorotkov@gmail.com
  Subject: Re: WIP: Fast GiST index build
  In-Reply-To: <4E2DBB60.80604@enterprisedb.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