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.
