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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

QED.

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

Answer 3

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

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

Странно, я знаю.

Answer 4

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

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

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

Answer 5

Если я правильно понимаю, вам нужно восстановить 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.

Answer 6

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

Выбирает записи «count» из записей «totalcount», отсортированные по key .

    # 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.