PostgreSQL - busca a linha que tem o valor máximo para uma coluna

96

Estou lidando com uma tabela Postgres (chamada "vidas") que contém registros com colunas para time_stamp, usr_id, transaction_id e lives_remaining. Preciso de uma consulta que me dê o total de vidas_remanentes mais recentes para cada usr_id

  1. Existem vários usuários (usr_id's distintos)
  2. time_stamp não é um identificador único: às vezes os eventos do usuário (um por linha na tabela) ocorrerão com o mesmo time_stamp.
  3. trans_id é único apenas para intervalos de tempo muito pequenos: com o tempo, ele se repete
  4. restantes_vidas (para um determinado usuário) podem aumentar e diminuir ao longo do tempo

exemplo:

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    

Como precisarei acessar outras colunas da linha com os dados mais recentes para cada usr_id fornecido, preciso de uma consulta que forneça um resultado como este:

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

Conforme mencionado, cada usr_id pode ganhar ou perder vidas e, às vezes, esses eventos com carimbo de data / hora ocorrem tão próximos que têm o mesmo carimbo de data / hora! Portanto, esta consulta não funcionará:

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

Em vez disso, preciso usar time_stamp (primeiro) e trans_id (segundo) para identificar a linha correta. Também preciso passar essas informações da subconsulta para a consulta principal que fornecerá os dados para as outras colunas das linhas apropriadas. Esta é a consulta hackeada que comecei a trabalhar:

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

Ok, isso funciona, mas eu não gosto. Requer uma consulta dentro de uma consulta, uma auto-junção, e parece-me que poderia ser muito mais simples capturando a linha que MAX descobriu ter o maior carimbo de data / hora e trans_id. A tabela "vidas" tem dezenas de milhões de linhas para analisar, então eu gostaria que essa consulta fosse o mais rápida e eficiente possível. Eu sou novo em RDBM e Postgres em particular, então eu sei que preciso fazer uso efetivo dos índices apropriados. Estou um pouco perdido em como otimizar.

Eu encontrei uma discussão semelhante aqui . Posso executar algum tipo de Postgres equivalente a uma função analítica Oracle?

Qualquer conselho sobre como acessar informações de colunas relacionadas usadas por uma função agregada (como MAX), criar índices e criar consultas melhores seria muito apreciado!

PS Você pode usar o seguinte para criar meu caso de exemplo:

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
fonte
Josh, você pode não gostar do fato de que a consulta se auto-junta etc., mas tudo bem no que diz respeito ao RDBMS.
vladr
1
O que a auto-junção vai realmente acabar traduzindo é um mapeamento de índice simples, onde o SELECT interno (aquele com MAX) verifica o índice jogando fora as entradas irrelevantes, e onde o SELECT externo apenas pega o resto das colunas da tabela correspondendo ao índice estreito.
vladr
Vlad, obrigado pelas dicas e explicações. Isso abriu meus olhos para como começar a entender o funcionamento interno do banco de dados e como otimizar as consultas. Quassnoi, obrigado pela ótima consulta e dica sobre a chave primária; Bill também. Muito útil.
Joshua Berry
obrigado por me mostrar como conseguir MAX BY2 colunas!

Respostas:

90

Em uma tabela com 158k linhas pseudo-aleatórias (usr_id uniformemente distribuído entre 0 e 10k, trans_iduniformemente distribuído entre 0 e 30),

Por custo de consulta, abaixo, estou me referindo à estimativa de custo do otimizador baseado em custo do Postgres (com os xxx_costvalores padrão do Postgres ), que é uma estimativa de função ponderada de recursos de I / O e CPU necessários; você pode obter isso abrindo PgAdminIII e executando "Query / Explain (F7)" na consulta com "Query / Explain options" definido como "Analyze"

  • Consulta de Quassnoy tem uma estimativa de custo de 745k (!), E completa em 1,3 segundos (dado um índice composto em ( usr_id, trans_id, time_stamp))
  • A consulta de Bill tem uma estimativa de custo de 93k e é concluída em 2,9 segundos (dado um índice composto em ( usr_id, trans_id))
  • Consulta # 1 abaixo tem uma estimativa de custo de 16k, e completa em 800ms (dado um índice composto em ( usr_id, trans_id, time_stamp))
  • Consulta # 2 abaixo tem uma estimativa de custo de 14k, e completa em 800ms (dado um índice função composto em ( usr_id, EXTRACT(EPOCH FROM time_stamp), trans_id))
    • isto é específico do Postgres
  • Consulta # 3 abaixo (Postgres 8.4+) tem um cálculo de custos e tempo de conclusão comparável a (ou melhor do que) consulta # 2 (dado um índice composto em ( usr_id, time_stamp, trans_id)); ele tem a vantagem de verificar a livestabela apenas uma vez e, se você aumentar temporariamente (se necessário) work_mem para acomodar a classificação na memória, será de longe a mais rápida de todas as consultas.

Todos os tempos acima incluem a recuperação de todo o conjunto de resultados de 10 mil linhas.

Seu objetivo é a estimativa de custo mínimo e o tempo mínimo de execução da consulta, com ênfase no custo estimado. A execução da consulta pode depender significativamente das condições de tempo de execução (por exemplo, se as linhas relevantes já estão totalmente armazenadas em cache na memória ou não), ao passo que a estimativa de custo não está. Por outro lado, tenha em mente que a estimativa de custo é exatamente isso, uma estimativa.

O melhor tempo de execução de consulta é obtido ao executar em um banco de dados dedicado sem carga (por exemplo, jogando com pgAdminIII em um PC de desenvolvimento). O tempo de consulta irá variar na produção com base na carga real da máquina / distribuição de acesso aos dados. Quando uma consulta parece um pouco mais rápida (<20%) do que a outra, mas tem um custo muito maior, geralmente será mais sensato escolher aquela com maior tempo de execução, mas menor custo.

Quando você espera que não haja competição pela memória em sua máquina de produção no momento em que a consulta for executada (por exemplo, o cache RDBMS e o cache do sistema de arquivos não serão prejudicados por consultas simultâneas e / ou atividade do sistema de arquivos), então o tempo de consulta obtido no modo autônomo (por exemplo, pgAdminIII em um PC de desenvolvimento) será representativo. Se houver contenção no sistema de produção, o tempo de consulta será reduzido proporcionalmente à relação de custo estimada, pois a consulta com o custo mais baixo não depende tanto do cache, enquanto a consulta com custo mais alto revisitará os mesmos dados repetidamente (acionando E / S adicional na ausência de um cache estável), por exemplo:

              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ão se esqueça de executar ANALYZE livesuma vez após criar os índices necessários.


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

Consulta # 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]

Atualização de 29/01/2013

Finalmente, a partir da versão 8.4, o Postgres suporta a função de janela, o que significa que você pode escrever algo tão simples e eficiente como:

Consulta # 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
fonte
Por um índice composto em (usr_id, trans_id, times_tamp), você quer dizer algo como "CRIAR INDEX lives_blah_idx ON vidas (usr_id, trans_id, time_stamp)"? Ou devo criar três índices separados para cada coluna? Devo ficar com o padrão "USANDO btree", certo?
Joshua Berry
1
Sim para a primeira escolha: quer dizer, CREATE INDEX lives_blah_idx ON lives (usr_id, trans_id, time_stamp). :) Felicidades.
vladr
Obrigado por fazer a comparação de custos vladr! Resposta muito completa!
Adam
@vladr Acabei de encontrar sua resposta. Estou um pouco confuso, como você diz que a consulta 1 tem um custo de 16k e a consulta 2 um custo de 14k. Porém, mais abaixo na tabela, você diz que a consulta 1 tem um custo de 5k e a consulta 2 tem um custo de 50k. Então, qual consulta é preferível usar? :) obrigado
Houman
1
@Kave, a tabela é para um par hipotético de consultas para ilustrar um exemplo, não as duas consultas do OP. Renomeando para reduzir a confusão.
vladr
77

Eu proporia uma versão limpa com base em DISTINCT ON(ver documentos ):

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
fonte
6
Esta é uma resposta muito curta e sólida. Também tem uma boa referência! Esta deve ser a resposta aceita.
Prakhar Agrawal
Isso pareceu funcionar para mim em meu aplicativo ligeiramente diferente, onde nada mais funcionaria. Definitivamente, deve ser elevado para maior visibilidade.
Jim Factor
8

Aqui está outro método, que não usa subconsultas correlacionadas ou GROUP BY. Não sou especialista em ajuste de desempenho do PostgreSQL, então sugiro que você experimente isso e as soluções fornecidas por outras pessoas para ver qual funciona melhor para você.

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;

Estou assumindo que trans_idé único pelo menos em relação a qualquer valor de time_stamp.

Bill Karwin
fonte
4

Gosto do estilo da resposta de Mike Woodhouse na outra página que você mencionou. É especialmente conciso quando o que está sendo maximizado é apenas uma única coluna, caso em que a subconsulta pode usar apenas MAX(some_col)e GROUP BYas outras colunas, mas no seu caso você tem uma quantidade de 2 partes a ser maximizada, você ainda pode fazer isso usando ORDER BYmais em LIMIT 1vez disso (como feito por 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
)

Acho bom usar a sintaxe do construtor de linha WHERE (a, b, c) IN (subquery)porque ela reduz a quantidade de verbosidade necessária.

j_random_hacker
fonte
3

Na verdade, há uma solução hacky para esse problema. Digamos que você queira selecionar a maior árvore de cada floresta em uma região.

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

Quando você agrupa árvores por florestas, haverá uma lista não classificada de árvores e você precisa encontrar a maior. A primeira coisa que você deve fazer é classificar as linhas por seus tamanhos e selecionar a primeira de sua lista. Pode parecer ineficiente, mas se você tiver milhões de linhas, será muito mais rápido do que as soluções que incluem JOIN's e as WHEREcondições.

BTW, observe que ORDER_BYfor array_aggé introduzido no Postgresql 9.0

burak emre
fonte
Você tem um erro. Você precisa escrever ORDER BY tree_size.size DESC. Além disso, para a tarefa do autor, o código será semelhante a este: 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

Há uma nova opção no Postgressql 9.5 chamada DISTINCT ON

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

Ele elimina linhas duplicadas e deixa apenas a primeira linha, conforme definido na cláusula ORDER BY.

veja a documentação oficial

Éden
fonte
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
        )

Criação de um índice em (usr_id, time_stamp, trans_id) irá melhorar muito esta consulta.

Você deve sempre, sempre ter algum tipo de PRIMARY KEYem suas mesas.

Quassnoi
fonte
0

Acho que você tem um grande problema aqui: não há um "contador" monotonicamente crescente para garantir que uma determinada linha tenha ocorrido mais tarde do que outra. Veja este exemplo:

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

Você não pode determinar a partir desses dados qual é a entrada mais recente. É o segundo ou o último? Não há função sort ou max () que você possa aplicar a qualquer um desses dados para fornecer a resposta correta.

Aumentar a resolução do timestamp seria uma grande ajuda. Como o mecanismo de banco de dados serializa as solicitações, com resolução suficiente, você pode garantir que dois carimbos de data / hora não serão iguais.

Como alternativa, use um trans_id que não irá acumular por muito, muito tempo. Ter um trans_id que rola significa que você não pode dizer (para o mesmo timestamp) se trans_id 6 é mais recente do que trans_id 1, a menos que você faça algumas contas complicadas.

Barry Brown
fonte
Sim, idealmente uma coluna de sequência (incremento automático) estaria em ordem.
vladr
A suposição acima era que, para pequenos incrementos de tempo, trans_id não rolaria. Concordo que a tabela precisa de um índice primário exclusivo - como um trans_id não repetitivo. (PS: Estou feliz que agora tenho pontos de carma / reputação suficientes para comentar!)
Joshua Berry
Vlad afirma que trans_id tem um ciclo bastante curto que muda frequentemente. Mesmo se você considerar apenas as duas linhas do meio da minha tabela (trans_id = 6 e 1), você ainda não consegue dizer qual é a mais recente. Portanto, usar o max (trans_id) para um determinado carimbo de data / hora não funcionará.
Barry Brown
Sim, estou contando com a garantia do autor do aplicativo de que a tupla (time_stamp, trans_id) é exclusiva para um determinado usuário. Se não for o caso, então "SELECT l1.usr_id, l1.lives_left, ... FROM ... WHERE ..." deve se tornar "SELECT l1.usr_id, MAX / MIN (l1.lives_left), ... FROM. .. ONDE ... GRUPO POR l1.usr_id, ...
vladr
0

Outra solução que você pode achar útil.

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
fonte