incubator-couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Candler <B.Cand...@pobox.com>
Subject Re: Querying by foreign keys
Date Sun, 26 Apr 2009 18:05:34 GMT
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.

Mime
View raw message