gistchoose vs. bloat

Hackers,

While experimenting with gistchoose I achieve interesting results about relation of gistchoose behaviour and gist index bloat.

I've created following testcase for reproducing gist index bloating:

1) Create test table with 1000000 points from geonames

# create table geotest (id serial, point point);

# insert into geotest (point) (select * from geonames order by random() limit 1000000);

2) Create gist index and statistics table. Insert initial statistics (rows count, index size) into table.

# create index geotest_idx on geotest using gist (point) with (buffering = off);

# create table geotest_stats (id serial, count bigint, size bigint);

# insert into geotest_stats (count, size) values ((select count(*) from geotest), pg_relation_size('geotest_idx'));

3) Delete 10% of geotest and vacuum it.

delete from geotest where id in (select id from geotest order by random() limit 100000);

vacuum geotest;

4) Insert new 100000 points fromg eonames.

insert into geotest (point) (select * from geonames order by random() limit 100000);

5) Insert current statistics (rows count, index size) into table.

insert into geotest_stats (count, size) values ((select count(*) from geotest), pg_relation_size('geotest_idx'));

6) Repeat 3-5 steps 50 times.

I get following results with current gistchoose implementation:

Index grow about from 75 MB to 100 MB.

Current implementation of gistchoose select first index tuple which have minimal penalty. It is possible for several tuples to have same minimal penalty. I've created simple patch which selects random from them. I then I've following results for same testcase.

I've following explanation of that. If index tuples are overlapping then possibility of insertion into last tuple is much lower than possibility of insertion to the first tuple. Thereby, freed space underlying to last tuples of inner page is not likely to be reused. Selecting random tuple increase that chances.

Obviously, it makes insertion more expensive. I need some more benchmarks to measure it. Probably, we would need a user-visible option for cheaper insert or less bloat.