Return-Path: 
 <user-return-4714-apmail-couchdb-user-archive=couchdb.apache.org@couchdb.apache.org>
Delivered-To: apmail-couchdb-user-archive@www.apache.org
Received: (qmail 69463 invoked from network); 4 May 2009 21:18:45 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3)
  by minotaur.apache.org with SMTP; 4 May 2009 21:18:45 -0000
Received: (qmail 78614 invoked by uid 500); 4 May 2009 21:18:44 -0000
Delivered-To: apmail-couchdb-user-archive@couchdb.apache.org
Received: (qmail 78529 invoked by uid 500); 4 May 2009 21:18:44 -0000
Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:user-help@couchdb.apache.org>
List-Unsubscribe: <mailto:user-unsubscribe@couchdb.apache.org>
List-Post: <mailto:user@couchdb.apache.org>
List-Id: <user.couchdb.apache.org>
Reply-To: user@couchdb.apache.org
Delivered-To: mailing list user@couchdb.apache.org
Received: (qmail 78519 invoked by uid 99); 4 May 2009 21:18:43 -0000
Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230)
    by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 04 May 2009 21:18:43 +0000
X-ASF-Spam-Status: No, hits=-0.0 required=10.0
	tests=SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (nike.apache.org: domain of paul.joseph.davis@gmail.com
 designates 209.85.132.240 as permitted sender)
Received: from [209.85.132.240] (HELO an-out-0708.google.com) (209.85.132.240)
    by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 04 May 2009 21:18:34 +0000
Received: by an-out-0708.google.com with SMTP id b6so2159348ana.5
        for <user@couchdb.apache.org>; Mon, 04 May 2009 14:18:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:mime-version:received:in-reply-to:references
         :date:message-id:subject:from:to:content-type
         :content-transfer-encoding;
        bh=87tPj3AIxeMBxUAoo8kA0dfAL/tQA8qOr7cXpyaqLsU=;
        b=Qq4E8iNC8VNe6iOKNnYoV5YCpGtW/lPzsK01QESAo2dhuYpUkTh8aM96PqAPAOneST
         vxOx8LvoV1RIM4HxFuXEy01iwg5v0+7M5PLlyO7wcL1BAarWWJlJTEgbNUxcP8Qb0Q86
         KXiiOAFhYsTHvfmBvpu1iXkevKG7ioXRRMz+U=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :content-type:content-transfer-encoding;
        b=KDZXj/njNdjhA2cgVmUN7iQXaaWxeAeQlnT5xHdxCf52zpSV1QsBgxg6H7+tfa3PCU
         ykC8bKPGJIbAWpNllG5AZ8N4qj6knWsDH5rcyOwSkgKZpFJ8rs3mXckXTLh5CdVdTBrI
         O0o2Drkh87qmHYl/WX68eyN+YVFUPt3YNzJh4=
MIME-Version: 1.0
Received: by 10.100.227.18 with SMTP id z18mr14095749ang.49.1241471893638;
	Mon, 04 May 2009 14:18:13 -0700 (PDT)
In-Reply-To: <e282921e0905041415r10f3df77oac375f208ebf98b7@mail.gmail.com>
References: <20090504210046.GC7083@uk.tiscali.com>
	 <e282921e0905041415r10f3df77oac375f208ebf98b7@mail.gmail.com>
Date: Mon, 4 May 2009 17:18:13 -0400
Message-ID: <e2111bbb0905041418y27bcfc0fs650cf71faedb3e7c@mail.gmail.com>
Subject: Re: Efficient range queries
From: Paul Davis <paul.joseph.davis@gmail.com>
To: user@couchdb.apache.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Virus-Checked: Checked by ClamAV on apache.org

On Mon, May 4, 2009 at 5:15 PM, Chris Anderson <jchris@apache.org> wrote:
> On Mon, May 4, 2009 at 2:00 PM, Brian Candler <B.Candler@pobox.com> 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:
>>
>> =A0lower: <value1>,
>> =A0upper: <value2>
>>
>> I want to be able to search these documents, such that when given a valu=
e 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
> http://jchrisa.net
> http://couch.io
>

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