Ok, I've updated the wiki page as promised: http://wiki.apache.org/couchdb/EntityRelationship under "Querying by multiple keys" A minor correction to the preceding discussion: I think the number of keys is 2^(n-1). Brian, in your example, you would have to emit "5" as a key. My analysis of the three key case seems to confirm this. Thanks again for the input, Adam On Sun, Apr 26, 2009 at 11:05 AM, Brian Candler wrote: > On Sat, Apr 25, 2009 at 03:48:02PM -0400, Paul Davis wrote: >> I've contemplated something like this, but I'm pretty sure it breaks >> when you start contemplating that a key may end up being [a, e] in >> which case your querying needs to account for all possible values >> between a and e. > > For a document which contains five values 1,2,3,4,5 you'd need to emit > naively the following combinations: > > 12345 > 1234    * > 1235 > 1245 > 1345 > 2345 > 123     * > 124     * > 125 > 134     * > 135 > 145 > 234     * > 235 > 245 > 345 > 12      * > 13      * > 14      * > 15 > 23      * > 24      * > 25 > 34      * > 35 > 45 > 1       * > 2       * > 3       * > 4       * > 5       * > > That's 31 keys; however you don't need to emit the keys marked * because > they are prefixes of existing keys. That is, if you want to search for [3,4] > then you can search for startkey=[3,4,null]&endkey=[3,4,{}] and you will hit > the other entry for 345, which by definition includes the values 3 and 4. > > Hence this gets you down to 15 keys to emit, but it's still exponential: > 2^(n-1) - 1 > > Regards, > > Brian. >