GIN index build speed

While playing around with the "GIN fast insert" patch, I was puzzled why
building a GIN index seemed to take so long. The test case I use was simply:

CREATE TABLE foo (bar tsvector);
INSERT INTO foo SELECT to_tsvector('foo' || a) FROM generate_series(1,
200000) a;
CREATE INDEX foogin ON foo USING gin (bar);

The CREATE INDEX step takes about 40 seconds on my laptop, which seems
excessive.

The issue is that the GIN index build code accumulates the lexemes into
a binary tree, but there's nothing to keep the tree balanced. My test
case with almost monotonically increasing keys, happens to be a
worst-case scenario, and the tree degenerates into almost linked list
that every insertion has to grovel through.

The obvious fix is to use a balanced tree algorithm. I wrote a quick
patch to turn the tree into a splay tree. That fixed the degenerative
behavior, and the runtime of CREATE INDEX for the above test case fell
from 40s to 1.5s.

Magnus kindly gave me a dump of the full-text-search tables from
search.postgresql.org, for some real-world testing. Quick testing with
that suggests that the patch unfortunately makes the index build 5-10%
slower with that data set.

We're in commitfest, not supposed to be submitting new features, so I'm
not going to pursue this further right now. Patch attached, however,
which seems to work fine.

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