PostgreSQL - récupération de la ligne qui a la valeur maximale pour une colonne

Question

Je travaille avec 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 donne le total de lives_remaining le plus récent pour chaque usr_id.

1. Il y a plusieurs utilisateurs (usr_id's distincts)

2. time_stamp n'est pas un identifiant unique : il arrive que des événements utilisateurs (un par ligne dans la table) se produisent avec le même time_stamp.

3. trans_id n'est unique que pour de très petites périodes : au fil du temps, il se répète.

4. remaining_lives (pour un utilisateur donné) peut à la fois augmenter et diminuer dans le temps.

exemple :

time\_stamp|lives\_remaining|usr\_id|trans\_id
-----------------------------------------
  07:00  |       1       |   1  |   1    
  09:00  |       4       |   2  |   2    
  10:00  |       2       |   3  |   3    
  10:00  |       1       |   2  |   4    
  11:00  |       4       |   1  |   5    
  11:00  |       3       |   1  |   6    
  13:00  |       3       |   3  |   1    

Comme j'aurai besoin d'accéder à d'autres colonnes de la ligne contenant 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 :

time\_stamp|lives\_remaining|usr\_id|trans\_id
-----------------------------------------
  11:00  |       3       |   1  |   6    
  10:00  |       1       |   2  |   4    
  13:00  |       3       |   3  |   1    

Comme mentionné, chaque usr_id peut gagner ou perdre des vies, et parfois ces événements horodatés sont si proches 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 le time_stamp (premier) et le trans_id (deuxième) pour identifier la bonne ligne. Je dois également 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 modifiée que j'ai réussi à faire fonctionner :

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

Bon, ça marche, mais je n'aime pas ça. Elle nécessite une requête dans une requête, une auto-jonction, et il me semble que cela pourrait être beaucoup plus simple en saisissant la ligne que MAX trouve avoir le plus grand timestamp et trans_id. La table "lives" contient des dizaines de millions de lignes à analyser, j'aimerais donc que cette requête soit aussi rapide et efficace que possible. Je suis nouveau dans le RDBM et Postgres en particulier, je sais donc que je dois utiliser efficacement les index appropriés. Je suis un peu perdu sur la façon d'optimiser.

J'ai trouvé une discussion similaire aquí . Puis-je exécuter un type d'équivalent Postgres d'une fonction analytique Oracle ?

Tout conseil sur l'accès aux informations des colonnes connexes 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é !

P.S. Vous pouvez utiliser les éléments suivants pour créer mon cas d'exemple :

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

Answer 1

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

_Par coût de la requête, ci-dessous, je fais référence à l'estimation du coût de l'optimiseur basé sur le coût de Postgres (avec l'algorithme par défaut de Postgres). xxx_cost ), qui est une estimation de la fonction de pesée des ressources E/S et CPU 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 un coût estimé de 745k ( !), et se complète en 1.3 secondes (étant donné un index 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 ))
• Question n° 1 ci-dessous a un coût estimé de 16k, et se termine en 800ms (étant donné un index composé sur ( usr_id , trans_id , time_stamp ))
• Question n° 2 ci-dessous a un coût estimé de 14k, et se termine en 800ms (étant donné un index de fonction composée sur ( usr_id , EXTRACT(EPOCH FROM time_stamp) , trans_id ))
  • ceci est spécifique à Postgres
• Question n° 3 ci-dessous (Postgres 8.4+) a une estimation de coût et un temps d'exécution comparables à (ou meilleurs que) la requête n°2 (étant donné un index composé sur ( usr_id , time_stamp , trans_id )) ; elle présente l'avantage de balayer le fichier lives qu'une seule fois et, si vous augmentez temporairement (si nécessaire) travail_mémoire pour accueillir le tri en mémoire, elle sera de loin la plus rapide de toutes les requêtes.

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

Votre objectif est d'obtenir une estimation minimale des coûts et le temps d'exécution minimal des requêtes, en mettant l'accent sur l'estimation des coûts. L'exécution d'une requête 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 du coût ne l'est pas. D'autre part, n'oubliez pas que l'estimation du coût est exactement cela, une estimation.

Le meilleur temps d'exécution des requêtes est obtenu lors de l'exécution sur une base de données dédiée sans charge (par exemple, en jouant avec pgAdminIII sur un PC de développement.) Le temps d'exécution des requêtes variera en production en fonction de la charge réelle de la machine/de la répartition des accès aux données. Lorsqu'une requête semble légèrement plus rapide (<20%) que l'autre, mais qu'elle a un temps de réponse plus long que celui de l'autre requête, il est recommandé d'en tenir compte. beaucoup plus élevé, il sera généralement plus sage de choisir celui dont le temps d'exécution est plus élevé mais le coût plus faible.

Si vous pensez 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 battus par des requêtes concurrentes et/ou par l'activité du système de fichiers), le temps de requête obtenu en mode autonome (par exemple, pgAdminIII sur un PC de développement) sera représentatif. S'il y a des conflits sur le système de production, le temps de requête se dégradera proportionnellement au ratio 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 ayant le coût le plus élevé revisitera les mêmes données encore et encore (déclenchant des E/S supplémentaires en l'absence d'un cache stable), par ex :

              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 lives une fois après avoir créé les indices 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]

2013/01/29 mise à jour

Enfin, à partir de la version 8.4, Postgres prend en charge les éléments suivants Fonction de la fenêtre 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
 );

Answer 2

Voici une autre méthode, qui n'utilise ni sous-requêtes corrélées ni GROUP BY. Je ne suis pas un expert en optimisation des performances de PostgreSQL, je vous suggère donc d'essayer cette méthode 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_id est unique au moins pour toute valeur donnée de time_stamp .

Answer 3

En fait, il existe une solution de fortune pour ce problème. Disons que vous voulez sélectionner le plus grand arbre de chaque forêt dans 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êt, vous obtenez une liste d'arbres non triés et vous devez trouver le plus grand d'entre eux. La première chose à faire est de trier les lignes en fonction de leur taille et de sélectionner la première ligne de votre liste. Cette méthode peut sembler inefficace, mais si vous avez des millions de lignes, elle sera plus rapide que les solutions suivantes JOIN et WHERE conditions.

BTW, notez que ORDER_BY pour array_agg est introduit dans Postgresql 9.0

Answer 4

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
        )

Création d'un index sur (usr_id, time_stamp, trans_id) améliorera grandement cette requête.

Vous devriez toujours, toujours avoir une sorte de PRIMARY KEY dans vos tableaux.

Answer 5

Je pense que vous avez un problème majeur ici : il n'y a pas de "compteur" à croissance monotone pour garantir qu'une ligne donnée s'est produite plus tard dans le temps qu'une autre. Prenez 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 la deuxième ou la dernière ? Il n'y a pas de fonction de tri ou de max() que vous pouvez appliquer à ces données pour vous donner la bonne réponse.

Augmenter 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 que deux horodatages ne seront pas identiques.

Sinon, utilisez un trans_id qui ne se retournera pas avant très, très longtemps. Avec un trans_id qui se renouvelle, vous ne pouvez pas savoir (pour le même horodatage) si le trans_id 6 est plus récent que le trans_id 1, à moins de faire des calculs compliqués.