Re: Fixing hash index build time - Mailing list pgsql-hackers

Hannu Krosing wrote:
> ?hel kenal p?eval, K, 2007-03-21 kell 17:25, kirjutas Bruce Momjian:
> > Added to TODO:
> > 
> >         o During index creation, pre-sort the tuples to improve build speed
> > 
> >          http://archives.postgresql.org/pgsql-hackers/2007-03/msg01199.php
> 
> Maybe the TODO text should mention, that it is about HASH indexes ?

It is in the HASH section of the TODO list.

---------------------------------------------------------------------------


> 
> > ---------------------------------------------------------------------------
> > 
> > Tom Lane wrote:
> > > I wrote:
> > > > I'm not sure if this has been discussed before, but I suddenly realized
> > > > while responding to the above message that the reason for the awful
> > > > performance is pretty obvious: hashbuild starts with a minimum-size
> > > > index (two buckets) and repeatedly splits buckets as insertions are
> > > > done, exactly the same as ordinary dynamic growth of the index would do.
> > > > This means that for an N-row table, approximately N/entries-per-bucket
> > > > splits need to occur during index build, which results in roughly O(N^2)
> > > > performance because we have to reprocess already-inserted entries over
> > > > and over.
> > > 
> > > Well, unfortunately this theory seems to be all wet.  Given that the
> > > bucket loading is reasonably even, the time to split a bucket is about
> > > constant and so there's no O(N^2) effect.  (The multiplier hidden inside
> > > O(N) is pretty awful, but it doesn't change with N.)
> > > 
> > > The real reason why performance falls off a cliff for building large
> > > hash indexes seems to be much harder to fix: basically, once the size
> > > of your index exceeds working memory, it's nap time.  Given that the
> > > incoming data has randomly distributed hash values, each bucket is about
> > > as likely to be touched next as any other; there is no locality of
> > > access and so the "working set" is the same size as the index.  Once it
> > > doesn't fit in RAM anymore you're into swap hell.
> > > 
> > > The only way I can see to fix that is to try to impose some locality of
> > > access during the index build.  This is not impossible: for example,
> > > given a choice for the number of buckets, we could sort all the index
> > > tuples by hashed bucket number and then start inserting.  btree does a
> > > preliminary sort, and its index build times are way more reasonable
> > > than hash's currently are, so the cost of the sort isn't outrageous.
> > > (I note this is mainly because we know how to do sorting with locality
> > > of access...)  Before we start inserting we will know exactly how many
> > > tuples there are, so we can pre-create the right number of buckets and
> > > be sure that no on-the-fly splits will be needed for the rest of the
> > > build.  If we guessed wrong about the number of buckets there will be
> > > some places in the process where we concurrently insert into several
> > > buckets not just one, or perhaps come back to a bucket that we touched
> > > earlier, but that's still maintaining plenty of locality of access.
> > > 
> > > This is looking like more work than I want to do in the near future,
> > > but I thought I'd put it into the archives for someone to tackle.
> > > Bruce, would you add a TODO item linking to this:
> > > 
> > >     * Improve hash index build time by sorting
> > > 
> > >             regards, tom lane
> > > 
> > > ---------------------------(end of broadcast)---------------------------
> > > TIP 9: In versions below 8.0, the planner will ignore your desire to
> > >        choose an index scan if your joining column's datatypes do not
> > >        match
> > 
> -- 
> ----------------
> Hannu Krosing
> Database Architect
> Skype Technologies O?
> Akadeemia tee 21 F, Tallinn, 12618, Estonia
> 
> Skype me:  callto:hkrosing
> Get Skype for free:  http://www.skype.com
> 
> NOTICE: This communication contains privileged or other confidential
> information. If you have received it in error, please advise the sender
> by reply email and immediately delete the message and any attachments
> without copying or disclosing the contents.
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 7: You can help support the PostgreSQL project by donating at
> 
>                 http://www.postgresql.org/about/donate

--  Bruce Momjian  <bruce@momjian.us>          http://momjian.us EnterpriseDB
http://www.enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +