> Aside from the disturbing frequency of 100-to-1 split ratios, it also > looks like the inclusion of the masklen bit is hardly pulling its weight, > though that might be a artifact of this data set.
I was expecting this. Including masklen bit to decision was something we could easily do. It doesn't make the index more complicated, even more simpler. I think it would be useful, when host addresses with masklen are indexed. IRRExplorer dataset is just networks. > I think that it'd be worth investigating changing to a split rule that > uses the next two or three or four bits of the address, not just the > single next bit, to index into more than four subnodes. It's pretty clear > how to adjust the insertion functions to support that, and a crude hack in > that line suggested that the index does get noticeably smaller. However, > I didn't quite grok how to adjust the search (consistent) functions. > Obviously we could apply the same rules in a loop, considering each > successive address bit, but there may be a better way. I have experimented with such designs before posting this patch, but couldn't make any of them work. It gets very complicated when more than one bit is used. When only 2 bits are used, there would be 12 child nodes: * network bits 00 * network bits 01 * network bits 10 * network bits 11 * network bit 0 and host bit 0 * network bit 0 and host bit 1 * network bit 1 and host bit 0 * network bit 1 and host bit 1 * host bits 00 * host bits 01 * host bits 10 * host bits 11 Another design would be a prefix tree. We could split by using a byte, and store that byte as label. Then there wouldn't be static number of nodes. We would need to iterate trough the labels and re-execute the condition on all of them. Surely this would perform better for some working sets, but I don't think on all them. I will experiment with this, if I get the chance. I belive the current index is useful as it is. The wasted space depends on the distribution of the keys: > # create table a3 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 8)::text || '.0.0')::inet from generate_series(1, 1000000) > as i; > SELECT 1000000 > # create table a4 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 16)::text || '.0.0')::inet from generate_series(1, 1000000) > as i; > SELECT 1000000 > # create table a5 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 32)::text || '.0.0')::inet from generate_series(1, 1000000) > as i; > SELECT 1000000 > # create table a6 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 64)::text || '.0.0')::inet from generate_series(1, 1000000) > as i; > SELECT 1000000 > # create index on a3 using spgist (inet); > CREATE INDEX > # create index on a4 using spgist (inet); > CREATE INDEX > # create index on a5 using spgist (inet); > CREATE INDEX > # create index on a6 using spgist (inet); > CREATE INDEX > # \di+ > List of relations > Schema | Name | Type | Owner | Table | Size | Description > -------+-------------+-------+----------+-------+-------+------------- > public | a3_inet_idx | index | hasegeli | a3 | 42 MB | > public | a4_inet_idx | index | hasegeli | a4 | 46 MB | > public | a5_inet_idx | index | hasegeli | a5 | 55 MB | > public | a6_inet_idx | index | hasegeli | a6 | 56 MB | > (4 rows) It also gets better with the number of keys: > # create table a6 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 64)::text || '.0.0')::inet from generate_series(1, 1000000) > as i; > SELECT 1000000 > # create table b6 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 64)::text || '.0.0')::inet from generate_series(1, 2000000) > as i; > SELECT 2000000 > # create table c6 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 64)::text || '.0.0')::inet from generate_series(1, 4000000) > as i; > SELECT 4000000 > # create table d6 as select (trunc(random() * 256)::text || '.' || > trunc(random() * 64)::text || '.0.0')::inet from generate_series(1, 8000000) > as i; > SELECT 8000000 > # create index on a6 using spgist (inet); > CREATE INDEX > # create index on b6 using spgist (inet); > CREATE INDEX > # create index on c6 using spgist (inet); > CREATE INDEX > # create index on d6 using spgist (inet); > CREATE INDEX > # \di+ > List of relations > Schema | Name | Type | Owner | Table | Size | Description > -------+-------------+-------+----------+-------+--------+------------- > public | a6_inet_idx | index | hasegeli | a6 | 56 MB | > public | b6_inet_idx | index | hasegeli | b6 | 109 MB | > public | c6_inet_idx | index | hasegeli | c6 | 181 MB | > public | d6_inet_idx | index | hasegeli | a6 | 336 MB | > (4 rows) Thank you for committing this. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers