Re: Fixing hash index build time

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(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +