PostgreSQL - récupère la ligne qui a la valeur Max pour une colonne

96

J'ai affaire à une table Postgres (appelée "lives") qui contient des enregistrements avec des colonnes pour time_stamp, usr_id, transaction_id et lives_remaining. J'ai besoin d'une requête qui me donnera le total de lives_remaining le plus récent pour chaque usr_id

  1. Il y a plusieurs utilisateurs (usr_id distincts)
  2. time_stamp n'est pas un identifiant unique: parfois les événements utilisateur (un par ligne dans la table) se produiront avec le même time_stamp.
  3. trans_id n'est unique que pour de très petites plages de temps: avec le temps, il se répète
  4. left_lives (pour un utilisateur donné) peut à la fois augmenter et diminuer avec le temps

exemple:

horodatage | lives_remaining | usr_id | trans_id
-----------------------------------------
  07h00 | 1 | 1 | 1    
  09h00 | 4 | 2 | 2    
  10:00 | 2 | 3 | 3    
  10:00 | 1 | 2 | 4    
  11h00 | 4 | 1 | 5    
  11h00 | 3 | 1 | 6    
  13h00 | 3 | 3 | 1    

Comme je devrai accéder aux autres colonnes de la ligne avec les dernières données pour chaque usr_id donné, j'ai besoin d'une requête qui donne un résultat comme celui-ci:

horodatage | lives_remaining | usr_id | trans_id
-----------------------------------------
  11h00 | 3 | 1 | 6    
  10:00 | 1 | 2 | 4    
  13h00 | 3 | 3 | 1    

Comme mentionné, chaque usr_id peut gagner ou perdre des vies, et parfois ces événements horodatés se produisent si près les uns des autres qu'ils ont le même horodatage! Par conséquent, cette requête ne fonctionnera pas:

SELECT b.time_stamp,b.lives_remaining,b.usr_id,b.trans_id FROM 
      (SELECT usr_id, max(time_stamp) AS max_timestamp 
       FROM lives GROUP BY usr_id ORDER BY usr_id) a 
JOIN lives b ON a.max_timestamp = b.time_stamp

Au lieu de cela, je dois utiliser à la fois time_stamp (premier) et trans_id (deuxième) pour identifier la ligne correcte. Je dois également ensuite transmettre ces informations de la sous-requête à la requête principale qui fournira les données pour les autres colonnes des lignes appropriées. Voici la requête piratée que j'ai obtenue:

SELECT b.time_stamp,b.lives_remaining,b.usr_id,b.trans_id FROM 
      (SELECT usr_id, max(time_stamp || '*' || trans_id) 
       AS max_timestamp_transid
       FROM lives GROUP BY usr_id ORDER BY usr_id) a 
JOIN lives b ON a.max_timestamp_transid = b.time_stamp || '*' || b.trans_id 
ORDER BY b.usr_id

D'accord, ça marche, mais je n'aime pas ça. Cela nécessite une requête dans une requête, une auto-jointure, et il me semble que cela pourrait être beaucoup plus simple en saisissant la ligne que MAX a trouvé comme ayant le plus grand horodatage et trans_id. La table "lives" a des dizaines de millions de lignes à analyser, donc j'aimerais que cette requête soit aussi rapide et efficace que possible. Je suis nouveau dans RDBM et Postgres en particulier, donc je sais que je dois utiliser efficacement les bons index. Je ne sais pas trop comment optimiser.

J'ai trouvé une discussion similaire ici . Puis-je effectuer un type de Postgres équivalent à une fonction analytique Oracle?

Tout conseil sur l'accès aux informations de colonne associées utilisées par une fonction d'agrégation (comme MAX), la création d'index et la création de meilleures requêtes serait très apprécié!

PS Vous pouvez utiliser ce qui suit pour créer mon exemple de cas:

create TABLE lives (time_stamp timestamp, lives_remaining integer, 
                    usr_id integer, trans_id integer);
insert into lives values ('2000-01-01 07:00', 1, 1, 1);
insert into lives values ('2000-01-01 09:00', 4, 2, 2);
insert into lives values ('2000-01-01 10:00', 2, 3, 3);
insert into lives values ('2000-01-01 10:00', 1, 2, 4);
insert into lives values ('2000-01-01 11:00', 4, 1, 5);
insert into lives values ('2000-01-01 11:00', 3, 1, 6);
insert into lives values ('2000-01-01 13:00', 3, 3, 1);
Joshua Berry
la source
Josh, vous n'aimerez peut-être pas le fait que la requête s'auto-joint, etc., mais ce n'est pas grave en ce qui concerne le SGBDR.
vladr le
1
Ce que l'auto-jointure finira en fait par se traduire est un simple mappage d'index, où le SELECT interne (celui avec MAX) scanne l'index en jetant les entrées non pertinentes, et où le SELECT externe saisit juste le reste des colonnes de la table correspondant à l’indice réduit.
vladr
Vlad, merci pour les conseils et les explications. Cela m'a ouvert les yeux sur la manière de commencer à comprendre le fonctionnement interne de la base de données et d'optimiser les requêtes. Quassnoi, merci pour l'excellente requête et le conseil sur la clé primaire; Bill aussi. Très utile.
Joshua Berry
merci de m'avoir montré comment obtenir un MAX BY2 colonnes!

Réponses:

90

Sur une table avec 158k lignes pseudo-aléatoires (usr_id uniformément réparti entre 0 et 10k, trans_iduniformément réparti entre 0 et 30),

Par coût de requête, ci-dessous, je fais référence à l'estimation des coûts de l'optimiseur basé sur les coûts de Postgres (avec les xxx_costvaleurs par défaut de Postgres ), qui est une estimation de fonction pondérée des ressources d'E / S et du processeur requises; vous pouvez l'obtenir en lançant PgAdminIII et en exécutant "Query / Explain (F7)" sur la requête avec "Query / Explain options" réglé sur "Analyze"

  • La requête de Quassnoy a une estimation des coûts de 745k (!), Et finalise en 1,3 secondes (donné un indice composé sur ( usr_id, trans_id, time_stamp))
  • La requête de Bill a un coût estimé de 93k et se termine en 2,9 secondes (étant donné un index composé sur ( usr_id, trans_id))
  • Requête # 1 ci - dessous présente une estimation des coûts de 16k, et finalise dans 800ms (donné un indice composé sur ( usr_id, trans_id, time_stamp))
  • Requête # 2 ci - dessous présente une estimation des coûts de 14k, et finalise à 800ms (donné un indice de fonction composé sur ( usr_id, EXTRACT(EPOCH FROM time_stamp), trans_id))
    • ceci est spécifique à Postgres
  • Requête # 3 ci - dessous (Postgres 8.4+) a une estimation des coûts et du délai d' exécution comparable à (ou mieux) que la requête n ° 2 (donné un indice composé sur ( usr_id, time_stamp, trans_id)); il a l'avantage de ne scanner la livestable qu'une seule fois et, si vous augmentez temporairement (si nécessaire) work_mem pour accueillir le tri en mémoire, ce sera de loin la plus rapide de toutes les requêtes.

Toutes les heures ci-dessus incluent la récupération du jeu de résultats complet de 10 000 lignes.

Votre objectif est une estimation des coûts minimale et un temps d'exécution des requêtes minimal, en mettant l'accent sur le coût estimé. L'exécution des requêtes peut dépendre de manière significative des conditions d'exécution (par exemple si les lignes pertinentes sont déjà entièrement mises en cache en mémoire ou non), alors que l'estimation des coûts ne l'est pas. D'autre part, gardez à l'esprit que l'estimation des coûts est exactement cela, une estimation.

Le meilleur temps d'exécution de la requête est obtenu lors de l'exécution sur une base de données dédiée sans charge (par exemple, jouer avec pgAdminIII sur un PC de développement.) Le temps de requête variera en production en fonction de la charge réelle de la machine / de la répartition de l'accès aux données. Lorsqu'une requête apparaît légèrement plus rapide (<20%) que l'autre mais a un coût beaucoup plus élevé, il sera généralement plus sage de choisir celle avec un temps d'exécution plus long mais un coût inférieur.

Lorsque vous prévoyez qu'il n'y aura pas de concurrence pour la mémoire sur votre machine de production au moment de l'exécution de la requête (par exemple, le cache du SGBDR et le cache du système de fichiers ne seront pas détruits par des requêtes simultanées et / ou l'activité du système de fichiers), alors l'heure de requête obtenue en mode autonome (par exemple pgAdminIII sur un PC de développement) sera représentatif. En cas de conflit sur le système de production, le temps de requête se dégradera proportionnellement au rapport de coût estimé, car la requête avec le coût le plus bas ne dépend pas autant du cache alors que la requête avec un coût plus élevé revisitera les mêmes données encore et encore (déclenchement E / S supplémentaires en l'absence de cache stable), par exemple:

              cost | time (dedicated machine) |     time (under load) |
-------------------+--------------------------+-----------------------+
some query A:   5k | (all data cached)  900ms | (less i/o)     1000ms |
some query B:  50k | (all data cached)  900ms | (lots of i/o) 10000ms |

N'oubliez pas d'exécuter ANALYZE livesune fois après avoir créé les index nécessaires.


Requête n ° 1

-- incrementally narrow down the result set via inner joins
--  the CBO may elect to perform one full index scan combined
--  with cascading index lookups, or as hash aggregates terminated
--  by one nested index lookup into lives - on my machine
--  the latter query plan was selected given my memory settings and
--  histogram
SELECT
  l1.*
 FROM
  lives AS l1
 INNER JOIN (
    SELECT
      usr_id,
      MAX(time_stamp) AS time_stamp_max
     FROM
      lives
     GROUP BY
      usr_id
  ) AS l2
 ON
  l1.usr_id     = l2.usr_id AND
  l1.time_stamp = l2.time_stamp_max
 INNER JOIN (
    SELECT
      usr_id,
      time_stamp,
      MAX(trans_id) AS trans_max
     FROM
      lives
     GROUP BY
      usr_id, time_stamp
  ) AS l3
 ON
  l1.usr_id     = l3.usr_id AND
  l1.time_stamp = l3.time_stamp AND
  l1.trans_id   = l3.trans_max

Requête n ° 2

-- cheat to obtain a max of the (time_stamp, trans_id) tuple in one pass
-- this results in a single table scan and one nested index lookup into lives,
--  by far the least I/O intensive operation even in case of great scarcity
--  of memory (least reliant on cache for the best performance)
SELECT
  l1.*
 FROM
  lives AS l1
 INNER JOIN (
   SELECT
     usr_id,
     MAX(ARRAY[EXTRACT(EPOCH FROM time_stamp),trans_id])
       AS compound_time_stamp
    FROM
     lives
    GROUP BY
     usr_id
  ) AS l2
ON
  l1.usr_id = l2.usr_id AND
  EXTRACT(EPOCH FROM l1.time_stamp) = l2.compound_time_stamp[1] AND
  l1.trans_id = l2.compound_time_stamp[2]

Mise à jour du 29/01/2013

Enfin, à partir de la version 8.4, Postgres prend en charge la fonction Window, ce qui signifie que vous pouvez écrire quelque chose d'aussi simple et efficace que:

Requête n ° 3

-- use Window Functions
-- performs a SINGLE scan of the table
SELECT DISTINCT ON (usr_id)
  last_value(time_stamp) OVER wnd,
  last_value(lives_remaining) OVER wnd,
  usr_id,
  last_value(trans_id) OVER wnd
 FROM lives
 WINDOW wnd AS (
   PARTITION BY usr_id ORDER BY time_stamp, trans_id
   ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
 );
vladr
la source
Par un index composé sur (usr_id, trans_id, times_tamp), voulez-vous dire quelque chose comme "CREATE INDEX lives_blah_idx ON lives (usr_id, trans_id, time_stamp)"? Ou devrais-je créer trois index distincts pour chaque colonne? Je devrais m'en tenir à la valeur par défaut "UTILISATION de btree", non?
Joshua Berry
1
Oui au premier choix: je veux dire CREATE INDEX lives_blah_idx ON lives (usr_id, trans_id, time_stamp). :) À votre santé.
vladr le
Merci d'avoir même fait la comparaison des coûts vladr! Réponse très complète!
Adam
@vladr Je viens de tomber sur votre réponse. Je suis un peu confus, comme vous le dites, la requête 1 a un coût de 16k et la requête 2 un coût de 14k. Mais plus bas dans le tableau, vous dites que la requête 1 a un coût de 5k et la requête 2 a un coût de 50k. Alors, quelle requête est préférable d'utiliser? :) merci
Houman
1
@Kave, le tableau est pour une paire hypothétique de requêtes pour illustrer un exemple, pas les deux requêtes de l'OP. Renommer pour réduire la confusion.
vladr
77

Je proposerais une version propre basée sur DISTINCT ON(voir docs ):

SELECT DISTINCT ON (usr_id)
    time_stamp,
    lives_remaining,
    usr_id,
    trans_id
FROM lives
ORDER BY usr_id, time_stamp DESC, trans_id DESC;
Marco
la source
6
C'est une réponse très courte et solide. A également une bonne référence! Cela devrait être la réponse acceptée.
Prakhar Agrawal
Cela semblait fonctionner pour moi sur mon application légèrement différente où rien d'autre ne le ferait. Il devrait certainement être soulevé pour plus de visibilité.
Jim Factor
8

Voici une autre méthode, qui n'utilise aucune sous-requête corrélée ou GROUP BY. Je ne suis pas expert dans le réglage des performances de PostgreSQL, donc je vous suggère d'essayer à la fois ceci et les solutions proposées par d'autres personnes pour voir laquelle fonctionne le mieux pour vous.

SELECT l1.*
FROM lives l1 LEFT OUTER JOIN lives l2
  ON (l1.usr_id = l2.usr_id AND (l1.time_stamp < l2.time_stamp 
   OR (l1.time_stamp = l2.time_stamp AND l1.trans_id < l2.trans_id)))
WHERE l2.usr_id IS NULL
ORDER BY l1.usr_id;

Je suppose que trans_idc'est unique au moins sur une valeur donnée de time_stamp.

Bill Karwin
la source
4

J'aime le style de la réponse de Mike Woodhouse sur l'autre page que vous avez mentionnée. C'est particulièrement concis lorsque l'élément maximisé n'est qu'une seule colonne, auquel cas la sous-requête peut simplement utiliser MAX(some_col)et GROUP BYles autres colonnes, mais dans votre cas, vous avez une quantité en 2 parties à maximiser, vous pouvez toujours le faire en utilisant ORDER BYplus à la LIMIT 1place (comme fait par Quassnoi):

SELECT * 
FROM lives outer
WHERE (usr_id, time_stamp, trans_id) IN (
    SELECT usr_id, time_stamp, trans_id
    FROM lives sq
    WHERE sq.usr_id = outer.usr_id
    ORDER BY trans_id, time_stamp
    LIMIT 1
)

Je trouve que l'utilisation de la syntaxe du constructeur de lignes est WHERE (a, b, c) IN (subquery)agréable car elle réduit la quantité de verbiage nécessaire.

j_random_hacker
la source
3

En fait, il existe une solution hacky à ce problème. Supposons que vous souhaitiez sélectionner le plus grand arbre de chaque forêt d'une région.

SELECT (array_agg(tree.id ORDER BY tree_size.size)))[1]
FROM tree JOIN forest ON (tree.forest = forest.id)
GROUP BY forest.id

Lorsque vous regroupez les arbres par forêts, il y aura une liste non triée d'arbres et vous devez trouver le plus grand. La première chose à faire est de trier les lignes en fonction de leur taille et de sélectionner la première de votre liste. Cela peut sembler inefficace, mais si vous avez des millions de lignes, ce sera bien plus rapide que les solutions qui incluent JOINles et les WHEREconditions.

BTW, notez que ORDER_BYfor array_aggest introduit dans Postgresql 9.0

burak emre
la source
Vous avez une erreur. Vous devez écrire ORDER BY tree_size.size DESC. En outre, pour la tâche de l'auteur, le code ressemblera à ceci: SELECT usr_id, (array_agg(time_stamp ORDER BY time_stamp DESC))[1] AS timestamp, (array_agg(lives_remaining ORDER BY time_stamp DESC))[1] AS lives_remaining, (array_agg(trans_id ORDER BY time_stamp DESC))[1] AS trans_id FROM lives GROUP BY usr_id
alexkovelsky
2

Il y a une nouvelle option dans Postgressql 9.5 appelée DISTINCT ON

SELECT DISTINCT ON (location) location, time, report
    FROM weather_reports
    ORDER BY location, time DESC;

Il élimine les lignes en double et ne laisse que la première ligne telle que définie dans la clause ORDER BY.

voir la documentation officielle

Eden
la source
1
SELECT  l.*
FROM    (
        SELECT DISTINCT usr_id
        FROM   lives
        ) lo, lives l
WHERE   l.ctid = (
        SELECT ctid
        FROM   lives li
        WHERE  li.usr_id = lo.usr_id
        ORDER BY
          time_stamp DESC, trans_id DESC
        LIMIT 1
        )

La création d'un index sur (usr_id, time_stamp, trans_id)améliorera considérablement cette requête.

Vous devriez toujours, toujours avoir une sorte de PRIMARY KEYdans vos tables.

Quassnoi
la source
0

Je pense que vous avez un problème majeur ici: il n'y a pas de «compteur» à augmentation monotone pour garantir qu'une ligne donnée s'est produite plus tard qu'une autre. Prenons cet exemple:

timestamp   lives_remaining   user_id   trans_id
10:00       4                 3         5
10:00       5                 3         6
10:00       3                 3         1
10:00       2                 3         2

Vous ne pouvez pas déterminer à partir de ces données quelle est l'entrée la plus récente. Est-ce le deuxième ou le dernier? Il n'y a pas de fonction sort ou max () que vous pouvez appliquer à l'une de ces données pour vous donner la bonne réponse.

L'augmentation de la résolution de l'horodatage serait d'une grande aide. Étant donné que le moteur de base de données sérialise les demandes, avec une résolution suffisante, vous pouvez garantir qu'aucun horodatage ne sera identique.

Vous pouvez également utiliser un trans_id qui ne se retournera pas pendant très, très longtemps. Avoir un trans_id qui survole signifie que vous ne pouvez pas dire (pour le même horodatage) si trans_id 6 est plus récent que trans_id 1 à moins que vous ne fassiez des calculs compliqués.

Barry Brown
la source
Oui, idéalement, une colonne de séquence (auto-incrémentation) serait en ordre.
vladr
L'hypothèse ci-dessus était que pour de petits incréments de temps, trans_id ne roulerait pas. Je conviens que la table a besoin d'un index primaire unique - comme un trans_id non répétitif. (PS, je suis heureux d'avoir maintenant assez de points de karma / réputation pour commenter!)
Joshua Berry
Vlad déclare que trans_id a un cycle assez court qui se retourne fréquemment. Même si vous ne considérez que les deux lignes du milieu de ma table (trans_id = 6 et 1), vous ne pouvez toujours pas dire quelle est la plus récente. Par conséquent, l'utilisation du max (trans_id) pour un horodatage donné ne fonctionnera pas.
Barry Brown
Oui, je compte sur la garantie de l'auteur de l'application que le tuple (time_stamp, trans_id) est unique pour un utilisateur donné. Si ce n'est pas le cas, alors "SELECT l1.usr_id, l1.lives_left, ... FROM ... WHERE ..." doit devenir "SELECT l1.usr_id, MAX / MIN (l1.lives_left), ... FROM. .. WHERE ... GROUP BY l1.usr_id, ...
vladr
0

Une autre solution que vous pourriez trouver utile.

SELECT t.*
FROM
    (SELECT
        *,
        ROW_NUMBER() OVER(PARTITION BY usr_id ORDER BY time_stamp DESC) as r
    FROM lives) as t
WHERE t.r = 1
Turbcool
la source