Re: Minmax indexes

On 06/18/2014 06:09 PM, Claudio Freire wrote:
> On Tue, Jun 17, 2014 at 8:48 PM, Greg Stark <stark@mit.edu> wrote:
>> An aggregate to generate a min/max "bounding box" from several values
>> A function which takes an "bounding box" and a new value and returns
>> the new "bounding box"
>> A function which tests if a value is in a "bounding box"
>> A function which tests if a "bounding box" overlaps a "bounding box"
>
> Which I'd generalize a bit further by renaming "bounding box" with
> "compressed set", and allow it to be parameterized.

What do you mean by parameterized?

> So, you have:
>
> An aggregate to generate a "compressed set" from several values
> A function which adds a new value to the "compressed set" and returns
> the new "compressed set"
> A function which tests if a value is in a "compressed set"
> A function which tests if a "compressed set" overlaps another
> "compressed set" of equal type

Yeah, something like that. I'm not sure I like the "compressed set" term 
any more than bounding box, though. GiST seems to have avoided naming 
the thing, and just talks about "index entries". But if we can come up 
with a good name, that would be more clear.

> One problem with such a generalized implementation would be, that I'm
> not sure in-place modification of the "compressed set" on-disk can be
> assumed to be safe on all cases. Surely, for strictly-enlarging sets
> it would, but while min/max and bloom filters both fit the bill, it's
> not clear that one can assume this for all structures.

I don't understand what you mean. It's a fundamental property of minmax 
indexes that you can always replace the "min" or "max" or "compressing 
set" or "bounding box" or whatever with another datum that represents 
all the keys that the old one did, plus some.

- Heikki