Re: Finding matching ranges

IMHO the "range matching" problem RMP is related but not equivalent to spacial queries. In spacial queries you compare 2dimensional fixed row values ("points") against a range, wheras in the RMP you compare row ranges against a fixed value. In the RMP the range is in the table and in SQ the point is in the table, so to speak.

If you assume a minimum value of 0 and a maximum value M then the RM problem can be written as

        where 0 < l < x
        and   x < h < M

(with l,h being the range boundaries in the table and x the value to match).

This is in fact a 2 dimensional spacial query, but the rectangle is quite large. I believe the spacial problem is harder then the RMP and cannot be solved with standard btrees.

I am still looking for a transformation, that restricts the rows to scan by a simple range scan. Here is one solution I came up with, but selectivity is very poor, because you always have to scan half the rows. This is not any better than the brute force aproach.

If you index the value (l+h)/2 then all matching ranges (plus some others) will certainly satisfy

        x/2 < (l+h)/2 < (M+x)/2

This is a simple range scan of (l+h)/2.

I wonder if you can get better selectivity with a different function

(l,h) -> number = (l+h)/2 here

BTW the brute force method can be seen as

(l,h) -> l

and all matching rows (plus some others) satisfy

        0 < l < x

In average this returns half of the rows too (since x is between 0 and M) as stated above. I wonder if *any* transformation will have this property, i.e. if there is a law saying "there is no range scan ... that will scan less that half the rows".

All the example above assume that every range is as likely as any other range. Received on Fri Jun 08 2001 - 23:06:05 CEST