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

Question

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

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

Однако это работает, возвращает только 1 запись, поэтому мне нужно выполнить N запросов.Есть идеи, как сделать этот запрос?Спасибо.

Answer 1

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

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

КЭД.

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

Answer 2

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

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

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

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

Этот метод требует рассмотрения нескольких неприятных деталей:

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

Имейте в виду, что для меня это несколько сложно, и я до сих пор не уверен, что у меня нет ошибок «не на единицу» или «не на х».

И помните: если count близок к totalcount, это может стоить очень дорого.И помните, что для миллионов строк это может быть невозможно сделать в пределах времени appengine.

Answer 6

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

Это просто.Просто выполните запрос только с ключами.И делай случайный.выбор 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.