couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Davis <>
Subject Re: Efficient range queries
Date Mon, 04 May 2009 21:18:13 GMT
On Mon, May 4, 2009 at 5:15 PM, Chris Anderson <> wrote:
> On Mon, May 4, 2009 at 2:00 PM, Brian Candler <> wrote:
>> Just a quick check to see if someone has a view strategy I can borrow.
>> Suppose I have a large collection of documents each of which contains a
>> range like this:
>>  lower: <value1>,
>>  upper: <value2>
>> I want to be able to search these documents, such that when given a value v,
>> I quickly find all documents where v lies between the lower and upper
>> values. Any suggestions?
> The simplest approach is to define a granularity for your queries and
> then emit each value within the range at that granularity from each
> document.
> Otherwise you end up intersecting potentially very large data sets on
> the client. Going down this second route can be optimized a bit if
> there is a maximum size each range can have. If the ranges are
> unbounded, then so too will be the result sets you must intersect.
> Or maybe someone can come up with a more clever method.
> --
> Chris Anderson

There's a data structure called a nested containment list that is
specifically meant for this type of query. It's on my todo list, but
no where near the top. If someone wants to add an indexer that'd be
pretty awesome.

Paul Davis

View raw message