Сортировка сущностей и фильтрация ListProperty без использования взрывающихся индексов - PullRequest
5 голосов
/ 24 мая 2011

Я разрабатываю простую платформу для ведения блогов / закладок и пытаюсь добавить тегов-исследователей / детализацию с функцией là восхитительной , чтобы пользователи могли фильтроватьсообщения с указанием списка определенных тегов.

Примерно так: enter image description here

Сообщения представлены в хранилище данных с помощью этой упрощенной модели:

class Post(db.Model):
    title = db.StringProperty(required = True)
    link = db.LinkProperty(required = True)
    description = db.StringProperty(required = True)
    tags = db.ListProperty(str)
    created = db.DateTimeProperty(required = True, auto_now_add = True)

Теги сообщенияхранится в ListProperty , и для получения списка сообщений, помеченных определенным списком тегов, модель Post предоставляет следующий статический метод:

@staticmethod
def get_posts(limit, offset, tags_filter = []):
        posts = Post.all()
        for tag in tags_filter:
          if tag:
              posts.filter('tags', tag)
        return posts.fetch(limit = limit, offset = offset)

Это хорошо работает,хотя я не особо подчеркивал это.

Проблема возникает, когда я пытаюсь добавить порядок "сортировки" в метод get_posts, чтобы сохранить результат в порядке "-created" date:

@staticmethod
def get_posts(limit, offset, tags_filter = []):
        posts = Post.all()
        for tag in tags_filter:
          if tag:
              posts.filter('tags', tag)
        posts.order("-created")
        return posts.fetch(limit = limit, offset = offset)

Порядок сортировки добавляет индекс для каждого тега для фильтрации, что приводит к страшной проблеме взрывающихся индексов .
Еще одна вещь, которая усложняет эту вещь, - это метод get_postsдолжен предоставить сомМеханизм нумерации страниц.

Знаете ли вы какую-либо стратегию / идею / обходной путь / взлом, чтобы решить эту проблему?

Ответы [ 4 ]

3 голосов
/ 09 июня 2011

Запросы с использованием ключей используют индексы так же, как запросы с участием свойства. Запросы на ключи требуют пользовательские индексы в тех же случаях, что и со свойствами, с парой исключения: фильтры неравенства или сортировка по возрастанию клавиша не требуется пользовательский индекс, но сортировка по убыванию Entity.KEY_RESERVED_PROPERTY_ ключ _ делает.

Так что используйте сортируемую строку даты для первичного ключа объекта:

class Post(db.Model):
    title = db.StringProperty(required = True)
    link = db.LinkProperty(required = True)
    description = db.StringProperty(required = True)
    tags = db.ListProperty(str)
    created = db.DateTimeProperty(required = True, auto_now_add = True)

    @classmethod
    def create(*args, **kw):
         kw.update(dict(key_name=inverse_millisecond_str() + disambig_chars()))
         return Post(*args, **kw)

...

def inverse_microsecond_str(): #gives string of 8 characters from ascii 23 to 'z' which sorts in reverse temporal order
    t = datetime.datetime.now()
    inv_us = int(1e16 - (time.mktime(t.timetuple()) * 1e6 + t.microsecond)) #no y2k for >100 yrs
    base_100_chars = []
    while inv_us:
        digit, inv_us = inv_us % 100, inv_us / 100
        base_100_str = [chr(23 + digit)] + base_100_chars
    return "".join(base_100_chars)

Теперь вам даже не нужно включать порядок сортировки в ваши запросы, хотя это не помешает явно сортировать по ключу.

Что следует помнить:

  • Это не сработает, если вы не используете здесь "create" для всех своих сообщений.
  • Вам придется перенести старые данные
  • Предки не допускаются.
  • Ключ хранится один раз для каждого индекса, поэтому его стоит сократить; вот почему я делаю кодировку base-100 выше.
  • Это не на 100% надежно из-за возможности столкновения клавиш. Приведенный выше код без disambig_chars номинально обеспечивает достоверность количества микросекунд между транзакциями, поэтому, если в пиковое время у вас было 10 сообщений в секунду, он потерпит неудачу в 1/100 000. Тем не менее, я бы выбрал пару порядков для возможных проблем с тактовыми частотами ядра приложения, поэтому я доверял этому только на 1/1000. Если этого недостаточно, добавьте disambig_chars; и если вам нужна 100% надежность, то, вероятно, вы не должны быть на движке приложения, но я думаю, вы могли бы включить логику для обработки столкновений клавиш в save ().
3 голосов
/ 25 мая 2011

Что если вы перевернули отношения?Вместо сообщения со списком тегов у вас будет объект тега со списком сообщений.

class Tag(db.Model):
  tag = db.StringProperty()
  posts = db.ListProperty(db.Key, indexed=False)

Для поиска тегов вы должны сделать tags = Tag.all().filter('tag IN', ['python','blog','async'])

Это даст ваммы надеемся, что 3 или более тегов, каждый со списком сообщений, которые используют этот тег.Затем вы можете сделать post_union = set(tags[0].posts).intersection(tags[1].posts, tags[2].posts), чтобы найти набор сообщений, которые имеют все теги.

Затем вы можете получить эти сообщения и упорядочить их по созданным (я думаю).Posts.all().filter('__key__ IN', post_union).order("-created")

Примечание : Этот код не в моей голове, я не могу вспомнить, можете ли вы манипулировать такими наборами.

Редактировать: @Yasserуказал, что вы можете выполнять запросы IN только для <30 элементов. </p>

Вместо этого вы можете задать имя ключа для каждого сообщения, начиная со времени создания.Затем вы можете отсортировать ключи, которые вы получили с помощью первого запроса, и просто выполнить команду Posts.get(sorted_posts).

. Не знаю, как это масштабируется до системы с миллионами постов и / или тегов.

Edit2: я имел в виду установить пересечение, а не объединение.

2 голосов
/ 07 июня 2011

Этот вопрос звучит примерно так:

Как указал Роберт Клюин в последнем, вы также можете рассмотреть возможность использования шаблона, аналогичного «Индексу отношений», как описано в этой презентации Google I / O .

# Model definitions
class Article(db.Model):
  title = db.StringProperty()
  content = db.StringProperty()

class TagIndex(db.Model):
  tags = db.StringListProperty()

# Tags are child entities of Articles
article1 = Article(title="foo", content="foo content")
article1.put()
TagIndex(parent=article1, tags=["hop"]).put()

# Get all articles for a given tag
tags = db.GqlQuery("SELECT __key__ FROM Tag where tags = :1", "hop")
keys = (t.parent() for t in tags)
articles = db.get(keys)

В зависимости от того, сколько страниц вы ожидаете от запроса тегов, сортировка может выполняться либо в памяти, либо путем включения представления строки даты в Article key_name

Обновлено с StringListProperty и сортировка заметок после Роберт Клюин и Wooble комментирует #appengine IRC-канал.

0 голосов
/ 24 мая 2011

Один обходной путь может быть таким:

Сортировка и объединение тегов сообщения с разделителем, как | и сохраните их как StringProperty при сохранении сообщения. Когда вы получаете tags_filter, вы можете сортировать и объединять их, чтобы создать единый фильтр StringProperty для сообщений. Очевидно, что это будет запрос AND, а не запрос OR, но похоже, что ваш текущий код тоже делает это.

РЕДАКТИРОВАТЬ: как правильно указано, это будет соответствовать только точному списку тегов, а не частичному списку тегов, что, очевидно, не очень полезно.

РЕДАКТИРОВАТЬ: что, если вы смоделируете свою модель Post с логическими заполнителями для тегов, например b1, b2, b3 и т. д. Когда определен новый тег, вы можете сопоставить его со следующим доступным заполнителем, например, blog = b1, python = b2, async = b3 и держите отображение в отдельной сущности. Когда тегу присваивается сообщение, вы просто переключаете его эквивалентное значение заполнителя на True.

Таким образом, когда вы получаете набор tag_filter, вы можете построить свой запрос по карте, например,

Post.all().filter("b1",True).filter("b2",True).order('-created')

может дать вам все сообщения с тегами python и blog.

...