Я создаю приложение, в котором пользователи могут создавать профили для себя, отвечая на несколько вопросов с несколькими вариантами ответов.Пользователи также могут искать других пользователей, указав критерии ответов на эти вопросы.
Допустим, у нас есть 9 вопросов q1 .. q9, каждый из которых содержит 6 возможных ответов (от 0 до 5).Это может быть представлено в профиле пользователя следующим образом:
class UserProfile(db.Model):
user = db.StringProperty(required=True)
q1 = db.IntegerProperty()
...
q9 = db.IntegerProperty()
Теперь рассмотрим, что пользователь хочет выполнить запрос для пользователей, которые ответили:
- 0, 1 или2 для q1
- 1, 2 или 5 для q2
- ...
- 3, 4 или 5 для q9
Мы могли бынаписать запрос, такой как:
q = UserProfile.all()
q.filter("q1 IN", [0, 1, 2])
q.filter("q2 IN", [1, 2, 5])
...
q.filter("q9 IN", [3, 4, 5])
К сожалению, это сгенерирует около 20 000 подзапросов (при условии, что пользователь указал 3 возможных ответа для каждого фильтра), что значительно больше, чем разрешенные 30, неупомянуть его ужасную неэффективность.
Существует ли шаблон проектирования, позволяющий сделать это эффективно?
Я могу представить способ превратить каждый из этих фильтров в фильтры с одним равенством, представив каждый фильтр как целое число.использование двоичного кодирования (например, [1, 2, 5] -> b100110 = 38) и сохранение каждого пользовательского ответа в хранилище данных в виде списка запросов, которым он будет соответствовать (например, 1 -> bxxxx1x -> [2, 3, 6, 7, 10, 11, .., 62, 63]).Тем не менее, это выглядит немного глупо.
Я был бы признателен, если бы у кого-нибудь было более эффективное предложение для реализации.
ОБНОВЛЕНИЕ (при предложенном двоичном кодировании):
Ник Джонсон высказал некоторые интересные опасения по поводу двоичного кодирования, предложенного выше, поэтому я хотел бы прояснить предлагаемое кодирование более подробно, чтобы позволить ему и другим участникам дать четкую оценку его достоинств и проблем.
Я думаю, что конкретный пример будет работать лучше всего.Кроме того, я думаю, что начинать с механизма запросов также более интуитивно понятно.
Продолжая приведенный выше пример, давайте предположим, что есть 9 вопросов с 6 возможными ответами на каждый (от 0 до 5).Давайте также определим, что каждый запрос будет иметь форму фильтра по ряду этих вопросов для сопоставления с несколькими возможными ответами (как описано выше).Я предлагаю преобразовать каждый запрос вида "q2 IN [1, 2, 5]" в фильтр равенства с использованием двоичного кодирования, где каждая позиция бита равна 1, если это один из запрашиваемых ответов, и 0 в противном случае.Например, «q2 IN [1, 2, 5]» будет переводиться как «q2 == b100110» или «q2 == 38».Применяя это далее, составной запрос, описанный выше, будет преобразован в следующие фильтры множественного равенства:
- 0, 1 или 2 для q1 -> q1 == b000111 -> q1 == 7
- 1, 2 или 5 для q2 -> q2 == b100110 -> q2 == 38
- ...
- 3, 4 или 5 для q9 -> q9 ==b111000 -> q9 == 56
Чтобы включить превращение фильтров "IN" в фильтры "==", нам нужно заранее определить, какие запросы (в их двоично-кодированной форме) отклика профилябудет соответствовать.Например, если пользователь выбирает 2 (от 0 до 5) в качестве ответа, то этот ответ будет соответствовать любому запросу, двоичное кодирование которого имеет 1 в позиции 2, т. Е. В форме bxxx1xx, где x может быть 0 или 1Набор целых чисел, определяемых bxxx1xx: [b000100, b000101, b000110, b000111, b001100, b001101, ..., b111100, b111101, b111110, b111111] или в десятичной форме: [4, 5, 6, 7, 12,13, ..., 60, 61, 62, 63], который представляет собой список из 32 целых чисел.В общем, этот «набор совпадений запросов» будет иметь 2 ^ (n-1) элемента для ответа на вопрос с n возможными ответами, потому что 1 из n битов в двоичном кодировании будет установлен в 1, в то время как другие могутбыть 0 или 1.
Поэтому, если бы у нас было m вопросов с n возможными ответами на каждое, то число записей индекса для каждого объекта, хранящего эти «наборы совпадений запросов» для каждого вопроса, было бы mx (2 ^ (п-1)).Если у меня есть:
- 9 вопросов по 6 возможных ответов на каждый, для этого потребуется 9 x 2 ^ 5 = 288 записей индекса
- 10 вопросов с 8 возможными ответами на каждый, для этого потребуется 10 x 2 ^ 7 = 1280 записей индекса
- 15 вопросов с 9 возможными ответами каждый, для этого потребуется 15 x 2 ^ 8 = 3840 записей индекса
- 20 вопросов с 10 возможными ответами на каждый, для этого потребуется 20 x 2 ^ 9 = 10240 записей индекса (что превышает предел в 5000 единиц / сущность, установленный App Engine)
Поэтому я согласен с тем, что этот подход не подходит для произвольно большого числа вопросов, особенно если возможно и большое количество ответов на вопросы. Тем не менее, это представляется возможным, если число индексируемых вопросов составляет 10-15, а возможные ответы не превышают 6, по крайней мере, для большинства вопросов.
У меня будет не более 10 вопросов, которые необходимо проиндексировать. У большинства из них есть 3-5 возможных ответов. У некоторых есть 6-7 возможных ответов, поэтому я ожидаю, что на одну сущность приходится менее 300 записей индекса (если я не ошибаюсь в том, как я вычисляю требования индекса выше).
Я не считаю это очень элегантным решением, но:
- Похоже, что затраты на индексирование могут быть управляемыми (т. Е. Значительно ниже предела в 5000 строк индекса)
- Он вернет именно то, для чего я фильтрую (вместо того, чтобы получить частично отфильтрованный список сущностей, которые все должны быть переданы по сети, а затем отфильтрованы приложением)
- Я понял, что встроенное объединение будет достаточно быстрым, чтобы это было эффективным.
Я бы все равно оценил перспективы по следующим вопросам:
- Исходя из этого более подробного объяснения, считаете ли вы, что требования к индексации могут быть разумными? Если вы думаете, что это все еще сталкивается с ограничениями, я был бы очень признателен за ваше понимание этого вопроса.
- Даже если требования к индексации могут быть разумными, считаете ли вы, что написание планировщика запросов даст более эффективное решение? Если это так, я был бы благодарен за (а) краткое объяснение того, почему это было бы более эффективно, и (б) указание на то, как это сделать. Я не уверен, как начать работу с планировщиком запросов.