Re: Parameters of GiST indexes

Hi hackers,

I found that some parameters of GiST implementation are builin in the code.
For example, following can be found in the backend/utils/adt/tsgistidx.c:

#define SIGLENINT 31 /* >121 => key will toast, so it will not
work
* !!! */

#define SIGLEN ( sizeof(int4) * SIGLENINT )
#define SIGLENBIT (SIGLEN * BITS_PER_BYTE)

I think that such parameters don't have optimal value for all the cases; and
it would be a great option to let user define such parameters for particular
index.
For example, following syntax can be used:

CREATE INDEX name ON table USING gist(column) WITH (SIGLENINT=63);

With best regards,
Korotkov Alexander.

On Sun, Jun 6, 2010 at 10:24 AM, Alexander Korotkov
<aekorotkov(at)gmail(dot)com> wrote:
> I think that such parameters don't have optimal value for all the cases;

What makes you think that?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company

On Tue, Jun 8, 2010 at 12:40 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Sun, Jun 6, 2010 at 10:24 AM, Alexander Korotkov
> <aekorotkov(at)gmail(dot)com> wrote:
>> I think that such parameters don't have optimal value for all the cases;
>
> What makes you think that?

Actually the whole signature method is a bit of a crock. I posted
about this previously as a tangent on a thread about bloom filters but
I can't find it now.

In short the "signature" is actually a degenerate bloom filter with
one hash function. Sizing bloom filters and choosing the number of
hash functions is a solved problem and while we don't necessarily have
all the input variables needed to do it optimally it's clear that a
single hash function is virtually never going to be ideal and these
filters are very small leading to high false positive rates.

To improve matters I think you need to know the number of distinct
values that are going to appear in an array. That's something the user
would have to provide or we would have to calculate due an ANALYZE
run. Then we can select the ideal number of hash functions and size
the array to target a chosen false-positive rate.

To *really* improve matters the index structure has to be adjusted to
allow for variable size arrays. Then we can use large filters at
higher index levels and smaller filters at lower levels where they
hold fewer values. I don't see how to make that work offhand though
unless we rescan the heap tuples when we grow the arrays.

--
greg

On Tue, Jun 8, 2010 at 8:53 AM, Greg Stark <gsstark(at)mit(dot)edu> wrote:
> On Tue, Jun 8, 2010 at 12:40 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Sun, Jun 6, 2010 at 10:24 AM, Alexander Korotkov
>> <aekorotkov(at)gmail(dot)com> wrote:
>>> I think that such parameters don't have optimal value for all the cases;
>>
>> What makes you think that?
>
> Actually the whole signature method is a bit of a crock.

My point was just that we're unlikely to make any changes to the code
without, say, some performance results. I suspect we're unlikely to
make the exact change being asked for in any case, but the point is
that if you think something isn't right, it's good to back up that
position with some data

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise Postgres Company