title: App Engine - Efficient queries over user profiles containing many multiple-choice responses
body: <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>class UserProfile(db.Model):
      user = db.StringProperty(required=True)
      q1 = db.IntegerProperty()
      ...
      q9 = db.IntegerProperty()
  </code></pre>
  
  <p>Now, consider that a user wants to run a query for users that answered:</p>
  
  <ul>
  <li>0, 1 or 2 for q1</li>
  <li>1, 2 or 5 for q2</li>
  <li>...</li>
  <li>3, 4, or 5 for q9</li>
  </ul>
  
  <p>We could write a query such as:</p>
  
  <pre><code>q = UserProfile.all()
  q.filter("q1 IN", [0, 1, 2])
  q.filter("q2 IN", [1, 2, 5])
  ...
  q.filter("q9 IN", [3, 4, 5])
  </code></pre>
  
  <p>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.</p>
  
  <p>Is there a design pattern to do this efficiently?</p>
  
  <p>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.</p>
  
  <p>I would appreciate if anyone has a more efficient suggestion for an implementation.</p>
  
  <p><strong>UPDATE</strong> (on proposed binary encoding):</p>
  
  <p>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.</p>
  
  <p>I think a concrete example will work best.  Also, I think that starting with the query mechanism is also more intuitive.</p>
  
  <p>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:</p>
  
  <ul>
  <li>0, 1 or 2 for q1 -> q1 == b000111 -> q1 == 7</li>
  <li>1, 2 or 5 for q2 -> q2 == b100110 -> q2 == 38</li>
  <li>...</li>
  <li>3, 4, or 5 for q9 -> q9 == b111000 -> q9 == 56</li>
  </ul>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <ul>
  <li>9 questions with 6 possible answers each, this would require 9 x 2^5 = 288 index entries</li>
  <li>10 questions with 8 possible answers each, this would require 10 x 2^7 = 1280 index entries</li>
  <li>15 questions with 9 possible answers each, this would require 15 x 2^8 = 3840 index entries</li>
  <li>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)</li>
  </ul>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>I don't really view this as a very elegant solution, but:</p>
  
  <ul>
  <li>It appears that indexing overhead could be manageable (i.e. well below the 5000 index rows limit)</li>
  <li>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)</li>
  <li>I had gathered that the built-in merge-join would be fast enough for this to be effective.</li>
  </ul>
  
  <p>I would still appreciate perspectives on the following questions:</p>
  
  <ol>
  <li>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.</li>
  <li>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.</li>
  </ol>