Meilleure façon de sélectionner des lignes aléatoires PostgreSQL

Je veux une sélection aléatoire de lignes dans PostgreSQL, j’ai essayé ceci:

select * from table where random() < 0.01; 

Mais d’autres recommandent ceci:

 select * from table order by random() limit 1000; 

J’ai une très grande table avec 500 millions de lignes, je veux que ce soit rapide.

Quelle approche est la meilleure? Quelles sont les différences? Quelle est la meilleure façon de sélectionner des lignes aléatoires?

Compte tenu de vos spécifications (plus des informations supplémentaires dans les commentaires),

  • Vous avez une colonne d’ID numérique (nombres entiers) avec seulement quelques (ou peu) lacunes.
  • Evidemment pas ou peu d’opérations d’écriture.
  • Votre colonne d’identification doit être indexée! Une clé primaire sert bien.

La requête ci-dessous ne nécessite pas une parsing séquentielle de la grande table, seulement une parsing d’index.

Tout d’abord, obtenez des estimations pour la requête principale:

 SELECT count(*) AS ct -- optional , min(id) AS min_id , max(id) AS max_id , max(id) - min(id) AS id_span FROM big; 

La seule partie coûteuse est le count(*) (pour les tables énormes). Compte tenu des spécifications ci-dessus, vous n’en avez pas besoin. Une estimation se passera bien, disponible à peu de frais ( explication détaillée ici ):

 SELECT reltuples AS ct FROM pg_class WHERE oid = 'schema_name.big'::regclass; 

Tant que ct n’est pas beaucoup plus petit que id_span , la requête surpassera les autres approches.

 WITH params AS ( SELECT 1 AS min_id -- minimum id <= current min id , 5100000 AS id_span -- rounded up. (max_id - min_id + buffer) ) SELECT * FROM ( SELECT p.min_id + trunc(random() * p.id_span)::integer AS id FROM params p ,generate_series(1, 1100) g -- 1000 + buffer GROUP BY 1 -- trim duplicates ) r JOIN big USING (id) LIMIT 1000; -- trim surplus 
  • Générer des nombres aléatoires dans l'espace id . Vous avez "peu de lacunes", ajoutez 10% (assez pour couvrir facilement les blancs) au nombre de lignes à récupérer.

  • Chaque id peut être choisi plusieurs fois par hasard (bien que très improbable avec un grand espace d’identification), regroupez donc les nombres générés (ou utilisez DISTINCT ).

  • Joignez les id à la grande table. Cela devrait être très rapide avec l'index en place.

  • Enfin, rognez les id surplus qui n'ont pas été mangés par les dupes et les manques. Chaque rangée a une chance égale d'être choisi.

Version courte

Vous pouvez simplifier cette requête. Le CTE dans la requête ci-dessus est uniquement à des fins éducatives:

 SELECT * FROM ( SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id FROM generate_series(1, 1100) g ) r JOIN big USING (id) LIMIT 1000; 

Affiner avec rCTE

Surtout si vous n'êtes pas certain des lacunes et des estimations.

 WITH RECURSIVE random_pick AS ( SELECT * FROM ( SELECT 1 + trunc(random() * 5100000)::int AS id FROM generate_series(1, 1030) -- 1000 + few percent - adapt to your needs LIMIT 1030 -- hint for query planner ) r JOIN big b USING (id) -- eliminate miss UNION -- eliminate dupe SELECT b.* FROM ( SELECT 1 + trunc(random() * 5100000)::int AS id FROM random_pick r -- plus 3 percent - adapt to your needs LIMIT 999 -- less than 1000, hint for query planner ) r JOIN big b USING (id) -- eliminate miss ) SELECT * FROM random_pick LIMIT 1000; -- actual limit 

Nous pouvons travailler avec un surplus plus petit dans la requête de base. S'il y a trop de lacunes pour ne pas trouver suffisamment de lignes dans la première itération, le rCTE continue à itérer avec le terme récursif. Nous avons encore besoin de relativement peu d' espaces dans l'espace ID ou la récursivité peut se tarir avant que la limite ne soit atteinte - ou nous devons commencer avec un tampon suffisamment grand pour éviter d'optimiser les performances.

Les doublons sont éliminés par l' UNION dans le rCTE.

La LIMIT externe fait que le CTE s'arrête dès que nous avons suffisamment de lignes.

Cette requête est soigneusement rédigée pour utiliser l'index disponible, générer des lignes réellement aléatoires et ne pas s'arrêter jusqu'à ce que nous atteignions la limite (à moins que la récursivité ne s'exécute). Il y a un certain nombre de pièges ici si vous allez le réécrire.

Envelopper dans la fonction

Pour une utilisation répétée avec des parameters variables:

 CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03) RETURNS SETOF big AS $func$ DECLARE _surplus int := _limit * _gaps; _estimate int := ( -- get current estimate from system SELECT c.reltuples * _gaps FROM pg_class c WHERE c.oid = 'big'::regclass); BEGIN RETURN QUERY WITH RECURSIVE random_pick AS ( SELECT * FROM ( SELECT 1 + trunc(random() * _estimate)::int FROM generate_series(1, _surplus) g LIMIT _surplus -- hint for query planner ) r (id) JOIN big USING (id) -- eliminate misses UNION -- eliminate dupes SELECT * FROM ( SELECT 1 + trunc(random() * _estimate)::int FROM random_pick -- just to make it recursive LIMIT _limit -- hint for query planner ) r (id) JOIN big USING (id) -- eliminate misses ) SELECT * FROM random_pick LIMIT _limit; END $func$ LANGUAGE plpgsql VOLATILE ROWS 1000; 

Appel:

 SELECT * FROM f_random_sample(); SELECT * FROM f_random_sample(500, 1.05); 

Vous pourriez même faire en sorte que ce générique fonctionne pour n'importe quelle table: prenez le nom de la colonne PK et de la table comme type polymorphe et utilisez EXECUTE ... Mais cela dépasse le cadre de cette question. Voir:

  • Refactoriser une fonction PL / pgSQL pour renvoyer la sortie de plusieurs requêtes SELECT

Alternative possible

Si vos exigences permettent des ensembles identiques pour les appels répétés (et nous parlons d'appels répétés), je considérerais une vue matérialisée . Exécutez la requête ci-dessus une fois et écrivez le résultat dans une table. Les utilisateurs obtiennent une sélection quasi aléatoire à la vitesse de l'éclair. Actualisez votre choix aléatoire à des intervalles ou des événements de votre choix.

Postgres 9.5 introduit TABLESAMPLE SYSTEM (n)

C'est très rapide , mais le résultat n'est pas exactement aléatoire . Le manuel:

La méthode SYSTEM est nettement plus rapide que la méthode BERNOULLI lorsque de petits pourcentages d’échantillonnage sont spécifiés, mais elle peut renvoyer un échantillon moins aléatoire de la table à la suite d’effets de clustering.

Et le nombre de lignes renvoyées peut varier énormément. Pour notre exemple, pour obtenir environ 1000 lignes, essayez:

 SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0); 

n est un pourcentage. Le manuel:

Les méthodes d'échantillonnage BERNOULLI et SYSTEM acceptent chacune un seul argument qui est la fraction de la table à échantillonner, exprimée en pourcentage entre 0 et 100 . Cet argument peut être toute expression real évaluée.

Emphase audacieuse la mienne

En relation:

  • Moyen rapide de découvrir le nombre de lignes d'une table dans PostgreSQL

Ou installez le module supplémentaire tsm_system_rows pour obtenir exactement le nombre de lignes demandées (le cas échéant) et autorisez la syntaxe la plus pratique:

 SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000); 

Voir la réponse d' Evan pour plus de détails.

Mais ce n'est pas encore tout à fait aléatoire.

Vous pouvez examiner et comparer le plan d’exécution des deux en utilisant

 EXPLAIN select * from table where random() < 0.01; EXPLAIN select * from table order by random() limit 1000; 

Un test rapide sur une grande table 1 montre que l’ ORDER BY sortinge d’abord la table complète, puis sélectionne les 1000 premiers éléments. Le sorting d'une grande table ne lit pas seulement cette table, mais implique également la lecture et l'écriture de fichiers temporaires. Le where random() < 0.1 parsing seulement la table complète une fois.

Pour les grandes tables, cela peut ne pas être ce que vous voulez, car même une parsing complète de la table peut prendre beaucoup de temps.

Une troisième proposition serait

 select * from table where random() < 0.01 limit 1000; 

Celui-ci arrête l'parsing de la table dès que 1000 lignes ont été trouvées et revient donc plus rapidement. Bien sûr, cela alourdit un peu le caractère aléatoire, mais peut-être est-ce suffisant dans votre cas.

Edit: Outre ces considérations, vous pouvez consulter les questions déjà posées pour cela. L'utilisation de la requête [postgresql] random renvoie un certain nombre de résultats.

  • Sélection rapide des lignes aléatoires dans Postgres
  • Comment récupérer des lignes de données aléatoires à partir d'une table postgreSQL?
  • postgres: obtenir des entrées aléatoires de la table - trop lent

Et un article lié de depez décrivant plusieurs autres approches:


1 "grand" comme dans "le tableau complet ne rentrera pas dans la mémoire".

ordre postgresql par random (), sélectionnez les lignes dans un ordre aléatoire:

 select your_columns from your_table ORDER BY random() 

ordre postgresql par random () avec un distinct:

 select * from (select distinct your_columns from your_table) table_alias ORDER BY random() 

ordre postgresql par limite aléatoire une ligne:

 select your_columns from your_table ORDER BY random() limit 1 

À partir de PostgreSQL 9.5, il existe une nouvelle syntaxe dédiée à l’obtention d’éléments aléatoires à partir d’une table:

 SELECT * FROM mytable TABLESAMPLE SYSTEM (5); 

Cet exemple vous donnera 5% d’éléments de mytable .

Voir plus d’explications sur cet article du blog: http://www.postgresql.org/docs/current/static/sql-select.html

Celui avec l’ORDRE BY sera le plus lent.

select * from table where random() < 0.01; va enregistrer par enregistrement et décide de le filtrer au hasard ou non. Cela va être O(N) car il suffit de vérifier chaque enregistrement une fois.

select * from table order by random() limit 1000; va sortinger la table entière, puis choisir les 1000 premiers. Mis à part la magie vaudou dans les coulisses, l'ordre est O(N * log N) .

L'inconvénient de l' random() < 0.01 est que vous obtiendrez un nombre variable d'enregistrements de sortie.


Remarque: il existe un meilleur moyen de mélanger un dataset que le sorting aléatoire: le Fisher-Yates Shuffle , qui s'exécute dans O(N) . L'implémentation du SQL dans SQL semble être un vrai défi.

Voici une décision qui fonctionne pour moi. Je suppose que c’est très simple à comprendre et à exécuter.

 SELECT field_1, field_2, field_2, random() as ordering FROM big_table WHERE some_conditions ORDER BY ordering LIMIT 1000; 

Si vous ne voulez qu’une seule ligne, vous pouvez utiliser un offset calculé à partir du count .

 select * from table_name limit 1 offset floor(random() * (select count(*) from table_name)); 
 select * from table order by random() limit 1000; 

Si vous savez combien de lignes vous voulez, consultez le tsm_system_rows .

tsm_system_rows

module fournit la méthode d’échantillonnage de table SYSTEM_ROWS, qui peut être utilisée dans la clause TABLESAMPLE d’une commande SELECT.

Cette méthode d’échantillonnage de table accepte un seul argument entier correspondant au nombre maximal de lignes à lire. L’échantillon résultant contiendra toujours autant de lignes, à moins que la table ne contienne pas suffisamment de lignes, auquel cas la table entière est sélectionnée. A l’instar de la méthode d’échantillonnage SYSTEM intégrée, SYSTEM_ROWS effectue un échantillonnage au niveau des blocs, de sorte que l’échantillon n’est pas complètement aléatoire, mais peut être sujet à des effets de cluster, surtout si un petit nombre de lignes est demandé.

Installez d’abord l’extension

 CREATE EXTENSION tsm_system_rows; 

Ensuite, votre requête,

 SELECT * FROM table TABLESAMPLE SYSTEM_ROWS(1000); 

Une variante de la vue matérialisée “Alternative possible” décrite par Erwin Brandstetter est possible.

Disons, par exemple, que vous ne voulez pas de doublons dans les valeurs aléatoires renvoyées. Vous devrez donc définir une valeur booléenne sur la table primaire contenant votre ensemble de valeurs (non aléatoire).

En supposant que ceci est la table d’entrée:

 id_values id | used ----+-------- 1 | FALSE 2 | FALSE 3 | FALSE 4 | FALSE 5 | FALSE ... 

ID_VALUES table ID_VALUES si nécessaire. Ensuite, comme décrit par Erwin, créez une vue matérialisée qui randomise la table ID_VALUES une fois:

 CREATE MATERIALIZED VIEW id_values_randomized AS SELECT id FROM id_values ORDER BY random(); 

Notez que la vue matérialisée ne contient pas la colonne utilisée, car celle-ci deviendra rapidement obsolète. La vue ne doit pas non plus contenir d’autres colonnes qui peuvent se trouver dans la table id_values .

Pour obtenir (et “consumr”) des valeurs aléatoires, utilisez un UPDATE-RETURNING sur id_values , en sélectionnant id_values de id_values_randomized avec une jointure et en appliquant les critères souhaités pour obtenir uniquement les possibilités pertinentes. Par exemple:

 UPDATE id_values SET used = TRUE WHERE id_values.id IN (SELECT i.id FROM id_values_randomized r INNER JOIN id_values i ON i.id = r.id WHERE (NOT i.used) LIMIT 5) RETURNING id; 

Modifiez la LIMIT si nécessaire – si vous n’avez besoin que d’une valeur aléatoire à la fois, modifiez LIMIT à 1 .

Avec les index id_values sur id_values , je pense que UPDATE-RETURNING devrait s’exécuter très rapidement avec peu de charge. Il renvoie des valeurs aléatoires avec un aller-retour de firebase database. Les critères pour les lignes “éligibles” peuvent être aussi complexes que nécessaire. De nouvelles lignes peuvent être ajoutées à la table id_values à tout moment et elles seront accessibles à l’application dès que la vue matérialisée est actualisée (ce qui peut probablement être exécuté à des heures creuses). La création et le rafraîchissement de la vue matérialisée seront lents, mais ils ne doivent être exécutés que lorsque de nouveaux identifiants sont ajoutés à la table id_values .

Ajoutez une colonne appelée r avec le type serial . Index r .

Supposons que nous ayons 200 000 lignes, nous allons générer un nombre aléatoire n , où 0 < n <= 200 000.

Sélectionnez des lignes avec r > n , sortingez-les en ASC et sélectionnez la plus petite.

Code:

 select * from YOUR_TABLE where r > ( select ( select reltuples::bigint AS estimate from pg_class where oid = 'public.YOUR_TABLE'::regclass) * random() ) order by r asc limit(1); 

Le code est explicite. La sous-requête au milieu est utilisée pour estimer rapidement le nombre de lignes de la table à partir de https://stackoverflow.com/a/7945274/1271094 .

Au niveau de l’application, vous devez exécuter l’instruction à nouveau si n > le nombre de lignes ou si vous devez sélectionner plusieurs lignes.

Je sais que je suis un peu en retard à la fête, mais je viens de trouver cet outil génial appelé pg_sample :

pg_sample – extrait un petit dataset à partir d’une firebase database PostgreSQL plus grande tout en maintenant l’intégrité référentielle.

J’ai essayé ceci avec une firebase database de lignes 350M et c’était très rapide, je ne connais pas le caractère aléatoire .

 ./pg_sample --limit="small_table = *" --limit="large_table = 100000" -U postgres source_db | psql -U postgres target_db