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