From: | Emre Hasegeli <emre(at)hasegeli(dot)com> |
---|---|
To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
Cc: | PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: SP-GiST support for inet datatypes |
Date: | 2016-08-24 17:32:36 |
Message-ID: | CAE2gYzz264-9s3coGAc1Rv8bkN4vAoEALuY0rBMx+NJxZX=+2A@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
> 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.
From | Date | Subject | |
---|---|---|---|
Next Message | Alvaro Herrera | 2016-08-24 17:40:17 | Re: [COMMITTERS] pgsql: Modify BufferGetPage() to prepare for "snapshot too old" feature |
Previous Message | Jeff Janes | 2016-08-24 17:02:28 | Re: Write Ahead Logging for Hash Indexes |