Recherche de N enregistrements aléatoires sur la banque de données Appengine

Question

J'essaie d'écrire une requête GQL qui renvoie N enregistrements aléatoires d'un type spécifique. Ma mise en œuvre actuelle fonctionne mais nécessite N appels au magasin de données. Je voudrais faire un appel à la banque de données si possible.

J'affecte actuellement un nombre aléatoire à chaque type que je mets dans le magasin de données. Lorsque je demande un enregistrement aléatoire, je génère un autre nombre aléatoire et une requête pour les enregistrements> rand ORDER BY asc LIMIT 1.

Cela fonctionne, cependant, il ne renvoie que 1 enregistrement, donc j'ai besoin de faire N requêtes. Des idées sur la façon de faire cette requête? Merci.

Answer 1

"Sous le capot", un seul appel de requête de recherche ne peut renvoyer qu'un ensemble de lignes consécutives à partir d'un index. C'est pourquoi certaines requêtes GQL, y compris l'utilisation de! =, Se développent en plusieurs appels de banque de données. N Les sélections aléatoires uniformes indépendantes ne sont (en général) consécutives dans aucun index.

QED.

Vous pouvez probablement utiliser memcache pour stocker les entités et réduire le coût de leur capture. Ou si cela ne vous dérange pas que les sélections "aléatoires" soient proches les unes des autres dans l'index, sélectionnez un bloc choisi au hasard de (disons) 100 dans une requête, puis choisissez N au hasard parmi celles-ci. Puisque vous avez un champ qui est déjà randomisé, il ne sera pas immédiatement évident pour un étranger que les N éléments sont liés. Au moins, pas tant qu'ils ne regardent pas beaucoup d'échantillons et remarquent que les items A et Z n'apparaissent jamais dans le même groupe, car ils sont distants de plus de 100 dans l'index randomisé. Et si les performances le permettent, vous pouvez re-randomiser vos entités de temps en temps.

Answer 2

On dirait que la seule méthode consiste à stocker la valeur entière aléatoire dans la propriété spéciale de chaque entité et d'interroger à ce sujet. Cela peut être fait tout à fait automatiquement si vous ajoutez simplement une propriété initialisée automatiquement.

Malheureusement, cela nécessitera le traitement de toutes les entités une fois si votre magasin de données est déjà rempli.

Il est bizarre, je sais.

Answer 3

Quels types de compromis recherchez-vous? Si vous êtes prêt à accepter un faible impact sur l'insertion de ces entités, vous pouvez créer une solution pour en obtenir très rapidement.

Voici ce que vous devez faire:

Lorsque vous insérez vos entités, spécifiez la clé. Vous voulez donner des clés à vos entités dans l'ordre, en commençant par 1 et en remontant à partir de là. (Cela demandera quelques efforts, car le moteur de l'application n'a pas d'auto-incrémentation(), donc vous aurez besoin de garder trace du dernier id que vous avez utilisé dans une autre entité, appelons-le IdGenerator)

Maintenant, quand vous avez besoin N entités aléatoires, génèrent N nombres aléatoires entre 1 et quel que soit le dernier identifiant que vous avez généré (votre IdGenerator le sait). Vous pouvez ensuite effectuer un traitement par lots à l'aide des touches N, qui ne nécessitent qu'un seul passage dans le magasin de données et seront plus rapides qu'une requête, car les clés sont généralement plus rapides que les requêtes, AFAIK.

Cette méthode ne nécessite traiter quelques détails gênants:

1. Votre IdGenerator pourrait devenir un goulot d'étranglement si vous insérez beaucoup de ces articles à la volée (plus de quelques seconde), ce qui nécessiterait une sorte d'implémentation IdGenerator partitionnée.Si toutes ces données sont préchargées ou si le volume n'est pas élevé, cela vous sera facile.
2. Vous trouverez peut-être que certains ID ne sont plus associés à une entité, car vous l'avez supprimée ou parce qu'un put() a échoué quelque part. Si cela se produit, vous devrez attraper une autre entité aléatoire. (Si vous voulez avoir envie et réduire les chances de cela, vous pouvez rendre cet Id disponible à l'IdGenerator pour réutiliser "remplir les trous")

Donc la question se résume à quelle vitesse vous avez besoin de ces N les éléments et la fréquence à laquelle vous les ajouterez et les supprimerez, et si un peu plus de complexité justifie cette amélioration des performances.

Answer 4

J'ai juste eu le même problème. J'ai décidé de ne pas attribuer d'ID à mes entrées déjà existantes dans le magasin de données et je l'ai fait, car j'avais déjà le compte total d'un compteur partagé.

Cette option sélectionne les entrées "count" des entrées "totalcount", triées par clé.

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

Prenez garde que cela me paraît un peu complexe, et je ne suis toujours pas conviced que je n'avez pas hors par une ou plusieurs erreurs off-by-x. Et méfiez-vous que si le compte est proche du total, cela peut être très coûteux. Et sachez que sur des millions de lignes, il ne sera peut-être pas possible de le faire à l'intérieur des limites de temps.

Answer 5

Je suis d'accord avec la réponse de Steve, il n'y a pas de façon de récupérer N lignes aléatoires dans une requête.

Cependant, même la méthode de récupération d'une entité unique ne fonctionne généralement pas de telle sorte que la probabilité d'obtention des résultats renvoyés soit uniformément répartie. La probabilité de renvoyer une entité dépend de l'écart entre son nombre assigné aléatoirement et le nombre aléatoire supérieur suivant. Par exemple. Si les nombres aléatoires 1, 2 et 10 ont été assignés (et aucun des nombres 3 à 9), l'algorithme retournera "2" 8 fois plus souvent que "1".

J'ai corrigé cela d'une manière légèrement plus dispendieuse. Si quelqu'un est intéressé, je suis heureux de partager

Answer 6

Si je comprends bien, vous devez récupérer N instance aléatoire.

C'est facile. Faites juste une requête avec seulement des clés. Et faire random.choice N fois sur le résultat de la liste des clés. Ensuite, obtenez des résultats en récupérant les clés.

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.