Запрос N случайных записей в хранилище данных Appengine

Question

Я пытаюсь написать запрос GQL, который возвращает N случайных записей определенного вида. Моя текущая реализация работает, но требует N обращений к хранилищу данных. Я хотел бы сделать это 1 звонок в хранилище данных, если это возможно.

В настоящее время я назначаю случайное число каждому виду, который помещаю в хранилище данных. Когда я запрашиваю случайную запись, я генерирую другое случайное число и запрашиваю записи> rand ORDER BY asc LIMIT 1.

Это работает, однако, он возвращает только 1 запись, поэтому мне нужно сделать N запросов. Любые идеи о том, как сделать этот запрос? Благодарю.

Answer 1

"Под капотом" один вызов поискового запроса может вернуть только набор последовательных строк из некоторого индекса. Вот почему некоторые запросы GQL, включая любое использование!=, Расширяются до нескольких вызовов хранилища данных.

N независимых равномерных случайных выборок не являются (в общем) последовательными ни по одному индексу.

QED.

Вероятно, вы могли бы использовать memcache для хранения сущностей и снизить стоимость захвата N из них. Или, если вы не возражаете против "случайного" выбора, находящегося близко друг к другу в индексе, выберите случайно выбранный блок (скажем) 100 в одном запросе, а затем выберите N случайным образом из этих запросов. Поскольку у вас есть поле, которое уже рандомизировано, постороннему не будет сразу очевидно, что N элементов связаны между собой. По крайней мере, пока они не рассмотрят множество выборок и не заметят, что элементы A и Z никогда не появляются в одной и той же группе, потому что они находятся на расстоянии более 100 друг от друга в рандомизированном индексе. И если производительность позволяет, вы можете время от времени повторно рандомизировать свои объекты.

Answer 2

Какие компромиссы вы ищете? Если вы готовы смириться с небольшим снижением производительности при вставке этих объектов, вы можете создать решение, чтобы быстро получить N из них.

Вот что вам нужно сделать:

Когда вы вставляете свои сущности, укажите ключ. Вы хотите дать ключи своим сущностям по порядку, начиная с 1 и далее оттуда. (Это потребует некоторых усилий, так как движок приложения не имеет автоинкремента (), поэтому вам нужно отслеживать последний идентификатор, который вы использовали в каком-то другом объекте, давайте назовем его IdGenerator)

Теперь, когда вам нужно N случайных объектов, сгенерируйте N случайных чисел от 1 до того, каким был последний сгенерированный вами идентификатор (ваш IdGenerator будет это знать). Затем вы можете выполнить пакетное получение по ключу, используя N ключей, что потребует только одной поездки в хранилище данных, а также будет быстрее, чем запрос, так как получение ключа, как правило, быстрее, чем запросы, AFAIK.

Этот метод требует работы с несколькими раздражающими деталями:

1. Ваш IdGenerator может стать узким местом, если вы вставляете много этих элементов "на лету" (более нескольких секунд), что потребует какой-то изолированной реализации IdGenerator. Если все эти данные предварительно загружены или не имеют большого объема, вам будет легко.
2. Вы можете обнаружить, что у некоторого идентификатора больше нет сущности, связанной с ним, потому что вы удалили его или потому что где-то произошел сбой put(). Если бы это случилось, вам пришлось бы схватить другую случайную сущность. (Если вы хотите проявить фантазию и уменьшить шансы на это, вы можете сделать этот Id доступным IdGenerator для повторного использования, чтобы "заполнить дыры")

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

Answer 3

Похоже, что единственный метод - хранить случайное целочисленное значение в специальном свойстве каждого объекта и запрашивать его. Это можно сделать довольно автоматически, если вы просто добавите автоматически инициализированное свойство.

К сожалению, это потребует обработки всех сущностей один раз, если ваше хранилище данных уже заполнено.

Это странно, я знаю.

Answer 4

Я согласен с ответом Стива, что нет такого способа извлечь N случайных строк в одном запросе.

Однако даже метод извлечения одной единственной сущности обычно не работает таким образом, что пригодность возвращаемых результатов распределяется равномерно. Вероятность возврата данного объекта зависит от разрыва его случайно назначенного номера и следующего более высокого случайного числа. Например, если были назначены случайные числа 1,2 и 10 (и ни одно из чисел 3-9), алгоритм будет возвращать "2" в 8 раз чаще, чем "1".

Я исправил это немного более затратным способом. Если кому-то интересно, я с удовольствием поделюсь

Answer 5

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

При этом выбираются записи "count" из записей "totalcount", отсортированные по ключу.

    # select $count from the complete set
    numberlist = random.sample(range(0,totalcount),count)
    numberlist.sort()

    pagesize=1000

    #initbuckets
    buckets = [ [] for i in xrange(int(max(numberlist)/pagesize)+1) ]
    for k in numberlist:
        thisb = int(k/pagesize)
        buckets[thisb].append(k-(thisb*pagesize))
    logging.debug("Numbers: %s. Buckets %s",numberlist,buckets)

    #page through results.

    result = []
    baseq =  db.Query(MyEntries,keys_only=True).order("__key__")
    for b,l in enumerate(buckets):
        if len(l) > 0: 
            result += [ wq.fetch(limit=1,offset=e)[0] for e in l ]

        if b < len(buckets)-1: # not the last bucket
            lastkey  = wq.fetch(1,pagesize-1)[0]
            wq = baseq.filter("__key__ >",lastkey)

Остерегайтесь, что это для меня несколько сложно, и я все еще не убежден, что у меня нет ошибок "один на один" или "один за другим".

И учтите, что если счет близок к общему количеству, это может быть очень дорого. И имейте в виду, что на миллионах строк это может быть невозможно сделать в пределах времени appengine.

Answer 6

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

Это просто. Просто сделайте запрос только с ключами. И сделайте random.choice N раз в списке результатов ключей. Тогда получите результаты, выбирая ключи.

keys = MyModel.all(keys_only=True)

n = 5 # 5 random instance

all_keys = list(keys)
result_keys = []

for _ in range(0,n) 
    key = random.choice(all_keys)
    all_keys.remove(key)
    result_keys.append(key)

# result_keys now contain 5 random keys.