Take the 2-minute tour ×

I'm building an application where users are able to create profiles for themselves by answering a bunch of multiple-choice questions. Users are also able to search for other users by specifying criteria for answers to these questions.

Let's say we have 9 questions q1 .. q9, each with 6 possible answers (0 through 5). This could be represented in a user profile as something like:

class UserProfile(db.Model):
    user = db.StringProperty(required=True)
    q1 = db.IntegerProperty()
    q9 = db.IntegerProperty()

Now, consider that a user wants to run a query for users that answered:

  • 0, 1 or 2 for q1
  • 1, 2 or 5 for q2
  • ...
  • 3, 4, or 5 for q9

We could write a query such as:

q = UserProfile.all()
q.filter("q1 IN", [0, 1, 2])
q.filter("q2 IN", [1, 2, 5])
q.filter("q9 IN", [3, 4, 5])

Unfortunately, this would generate close to 20,000 sub-queries (assuming that the user specified 3 possible answers for each filter), which is significantly greater than the 30 allowed, not to mention its horrible inefficiency.

Is there a design pattern to do this efficiently?

I can envision a way to turn each of these filters into single equality filters by representing each filter as an integer using binary encoding (e.g., [1, 2, 5] -> b100110 = 38) and storing each user answer in the datastore as a list of queries it would match (e.g., 1 -> bxxxx1x -> [2, 3, 6, 7, 10, 11, .. , 62, 63]). However, this seems a bit kludgy.

I would appreciate if anyone has a more efficient suggestion for an implementation.

UPDATE (on proposed binary encoding):

Nick Johnson raised some interesting concerns about the binary encoding proposed above, so I would like to clarify the proposed encoding in more detail to allow him and others to provide a clear evaluation of its merits and challenges.

I think a concrete example will work best. Also, I think that starting with the query mechanism is also more intuitive.

Continuing with the example from above, let's assume that there are 9 questions with 6 possible answers each (0 through 5). Let's also define that each query will be in the form of a filter on a number of these questions for matching against multiple possible answers (as described above). I propose to convert each query of the form "q2 IN [1, 2, 5]" to an equality filter using binary encoding, where each bit position is 1 if it's one of the queried responses and 0 otherwise. For example, "q2 IN [1, 2, 5]" would translate to "q2 == b100110" or "q2 == 38". Applying this further, the composite query described above would be translated into the following multiple equality filters:

  • 0, 1 or 2 for q1 -> q1 == b000111 -> q1 == 7
  • 1, 2 or 5 for q2 -> q2 == b100110 -> q2 == 38
  • ...
  • 3, 4, or 5 for q9 -> q9 == b111000 -> q9 == 56

To enable turning the "IN" filters into "==" filters, we need to determine in advance which queries (in their binary-encoded form) a profile response will match. For example, if a user selects 2 (among 0 through 5) as the answer, then that response will match any query whose binary encoding has a 1 in the 2-position, i.e. of the form bxxx1xx, where x could be 0 or 1. The set of integers defined by bxxx1xx are [b000100, b000101, b000110, b000111, b001100, b001101, ... , b111100, b111101, b111110, b111111] or in decimal form: [4, 5, 6, 7, 12, 13, ..., 60, 61, 62, 63], which is a list of 32 integers. In general, this "query match set" will have 2^(n-1) elements for a response to a question with n possible answers, because 1 of the n bits in the binary encoding will be fixed to 1, while the others could be 0 or 1.

Therefore, if we had m questions with n possible answers each, then the number of index entries for each entity storing these "query match sets" for each question would be m x (2 ^ (n-1)). If I have:

  • 9 questions with 6 possible answers each, this would require 9 x 2^5 = 288 index entries
  • 10 questions with 8 possible answers each, this would require 10 x 2^7 = 1280 index entries
  • 15 questions with 9 possible answers each, this would require 15 x 2^8 = 3840 index entries
  • 20 questions with 10 possible answers each, this would require 20 x 2^9 = 10240 index entries (which is above the 5000/entity limit imposed by App Engine)

Therefore, I agree that this is not a suitable approach for an arbitrarily large number of questions, especially if the possible number of answers to questions is large also. However, it appears feasible if the number of questions to be indexed is 10-15 and the possible answers don't number more than 6, at least for a majority of the questions.

I will have no more than 10 questions that need to be indexed. Most of them have 3-5 possible answers. Some have 6-7 possible answers, so I'm expecting less than 300 index entries per entity (unless I'm wrong about how I'm calculating the index requirements above).

I don't really view this as a very elegant solution, but:

  • It appears that indexing overhead could be manageable (i.e. well below the 5000 index rows limit)
  • It will return exactly what I'm filtering for (rather than getting a partially filtered list of entities, which all need to be transported over the network, only to be filtered further by the application)
  • I had gathered that the built-in merge-join would be fast enough for this to be effective.

I would still appreciate perspectives on the following questions:

  1. Based on this more detailed explanation, do you think that the indexing requirements could be reasonable? If you think that this still bumps up against limitations, I really would appreciate your insights on this.
  2. Even if the indexing requirements could be reasonable, do you think that writing a query planner would yield a more efficient solution? If so, I would be grateful for (a) a brief explanation of why this would be more efficient and (b) a pointer to how to go about doing this. I'm not sure about how to even get started with a query planner.
share|improve this question
A simply guess would be try to use mapreduce for your problem code.google.com/p/appengine-mapreduce –  lucemia Dec 13 '11 at 22:04
If there were 20K different profiles, 1 query could match every single profile. MapReduce or your idea are all I can think of. –  Iain Dec 13 '11 at 23:10
How would you order the results? I believe that may influence the solution... –  Iain Dec 13 '11 at 23:14
Iain - Can you please comment further on what the impact of result ordering is? I'm much more concerned about giving people the ability to narrow search than I am with the ordering. Also, I need this to be a real-time query (i.e. user specifies the search criteria and gets the results within the http response). I didn't think that the MapReduce API supports this use case. I would appreciate if you could point me to documentation highlighting features that support this real-time use case. –  cv12 Dec 19 '11 at 20:52
add comment

1 Answer

up vote 2 down vote accepted

There's simply no efficient way to structure the data for queries as you describe them. The only way to do this is to query on the criteria you think will be most restrictive, then filter manually in memory for the remaining criteria.

If you tell us more about the specific sorts of queries people might execute and why, we may be able to provide concrete suggestions for something more efficient.

share|improve this answer
Nick - I think that the closest analogy would be profile search on a dating site (like match or okcupid) even though that is not what I'm building. So, somebody could search for people within 25 miles; in 25-35 age group; ethnicity of 3-4 named groups; doesn't smoke or sometimes smokes; drinks socially or rarely; religion of 2-3 named categories; education of college, masters or advanced degree; likes children ... Any new thoughts? Also, I would appreciate if you could comment on the binary encoding I outlined above. My concern was that it was contrived. Do you think it is also inefficient? –  cv12 Dec 19 '11 at 20:46
@cv12 The encoding you proposed won't work because you'd have to store an intractably large number of index elements. I think the only practical option open to you is to write your own query planner, which filters as closely as it can while still being indexable, then filters the remaining results in memory. –  Nick Johnson Dec 19 '11 at 23:22
Nick - Once again, thanks for your response. I really appreciate your insight. How do you define "intractably large"? If I have 10 responses (each chosen from 6 possible answers) in each profile, then each profile would have 2**5=32 index entries per property (storing encoding for response), or 320 index entries. Is this intractably large? If so, why is that? Also, do you have pointers for how I could go about writing a query planner in App Engine (e.g., a tutorial or blog post I could get started with)? –  cv12 Dec 20 '11 at 5:26
By the way, since the queries using my proposed encoding are based on multiple equality filters, I was assuming that App Engine would be using the built-in indexes for each property and using the built-in merge-join. Does the built-in merge-join have limitations (e.g. max number of equality filters)? –  cv12 Dec 20 '11 at 5:35
@cv12 If I understand your proposed encoding properly, you would have to insert 2^9 elements per property, since you need to appear for every result regardless of the value of the other answers. Even if 2^5 is correct, you can see that the number of values required grows exponentially. –  Nick Johnson Dec 20 '11 at 6:12
show 3 more comments

Your Answer


