Re: Optomized Range Searching....

>> I am wondering if there are any papers on ways to optomize range
searching. (Specifically numerical range searching.) <<

I cannot think of any papers just off hand; have you done a search on the ACM websites?

Obviously, if you have a system that uses indexes and the search column is indexed, you can go directly to the data pages which what you are looking for. If the table is in sorted order on the search column (what the Sybase family calls a clustered index), you can do a sequential read from contigous data pages which is even faster.

On the other hand, without an index in such products, you are stuck with a table scan.

Bit vector indexes can assemble a bit pattern for the entire range and apply it to the data, returning the rows which have a bit in any of the right places.

Hashing systems will depend on the hashing algorithm used. You might be able to get a white paper from Teradata on this topic. If (hash(x) < hash (y)) ==> (x < y) holds, then you are in luck. Or if you have a function T() such that hash(n+k) = T(hash(n)), then you can do something, especially if (k =1). Otherwise, you might be stuck with (hash(a) UNION hash(a+1) UNION ... UNION hash(b)) to cover all of the range (a,b).

--CELKO--
Joe Celko, SQL and Database Consultant
When posting, inclusion of SQL (CREATE TABLE ..., INSERT ..., etc) which can be cut and pasted into Query Analyzer is appreciated.

Sent via Deja.com http://www.deja.com/
Before you buy. Received on Thu Aug 17 2000 - 00:08:47 CEST