PostgreSQL - pobierz wiersz, który ma wartość Max dla kolumny

99

Mam do czynienia z tabelą Postgres (o nazwie „lives”), która zawiera rekordy z kolumnami dla datownika, usr_id, transaction_id i lives_remaining. Potrzebuję zapytania, które da mi ostatnią liczbę pozostałych żyć dla każdego identyfikatora usr_id

  1. Istnieje wielu użytkowników (różne usr_id)
  2. time_stamp nie jest unikalnym identyfikatorem: czasami zdarzenia użytkownika (jeden po wierszu w tabeli) będą miały miejsce z tym samym znacznikiem czasu.
  3. trans_id jest unikalny tylko dla bardzo małych przedziałów czasowych: w czasie się powtarza
  4. pozostałe_lives (dla danego użytkownika) mogą zarówno rosnąć, jak i spadać w czasie

przykład:

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    

Ponieważ będę musiał uzyskać dostęp do innych kolumn wiersza z najnowszymi danymi dla każdego podanego identyfikatora usr_id, potrzebuję zapytania, które da następujący wynik:

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

Jak wspomniano, każdy usr_id może zyskać lub stracić życie, a czasami te zdarzenia z sygnaturą czasową występują tak blisko siebie, że mają ten sam znacznik czasu! Dlatego to zapytanie nie zadziała:

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

Zamiast tego muszę użyć zarówno sygnatury czasowej (pierwszej), jak i trans_id (drugiej), aby zidentyfikować właściwy wiersz. Muszę również przekazać te informacje z podzapytania do głównego zapytania, które dostarczy dane dla innych kolumn odpowiednich wierszy. Oto zhakowane zapytanie, które zabrałem do pracy:

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, więc to działa, ale mi się to nie podoba. Wymaga kwerendy w zapytaniu, samosprzężenia i wydaje mi się, że mogłoby to być znacznie prostsze, chwytając wiersz, który MAX uznał za mający największy znacznik czasu i trans_id. Tabela „żyje” ma dziesiątki milionów wierszy do przeanalizowania, dlatego chciałbym, aby to zapytanie było tak szybkie i wydajne, jak to tylko możliwe. W szczególności jestem nowy w RDBM i Postgresie, więc wiem, że muszę efektywnie wykorzystywać odpowiednie indeksy. Trochę zagubiłem się w optymalizacji.

Znalazłem podobną dyskusję tutaj . Czy mogę wykonać jakiś typ Postgres będący odpowiednikiem funkcji analitycznej Oracle?

Wszelkie porady dotyczące uzyskiwania dostępu do powiązanych informacji z kolumn używanych przez funkcję agregującą (taką jak MAX), tworzenia indeksów i tworzenia lepszych zapytań byłyby bardzo mile widziane!

PS Możesz użyć następujących, aby utworzyć moją przykładową sprawę:

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
źródło
Josh, może nie spodobać ci się fakt, że zapytanie łączy się samodzielnie itp., Ale to jest w porządku, jeśli chodzi o RDBMS.
vladr
1
To, co w rzeczywistości zostanie przetłumaczone przez samozłączenie, to proste mapowanie indeksu, w którym wewnętrzny SELECT (ten z MAX) skanuje indeks odrzucając nieistotne wpisy, a zewnętrzny SELECT po prostu pobiera resztę kolumn z tabeli odpowiadający zawężonemu indeksowi.
vladr
Vlad, dzięki za wskazówki i wyjaśnienia. Otworzyło mi oczy, aby dowiedzieć się, jak zacząć rozumieć wewnętrzne działanie bazy danych i optymalizować zapytania. Quassnoi, dzięki za świetne zapytanie i wskazówkę dotyczącą klucza podstawowego; Bill też. Bardzo pomocny.
Joshua Berry
dziękuję za pokazanie mi, jak zdobyć MAX BY2 kolumny!

Odpowiedzi:

93

W tabeli zawierającej 158 tys. Pseudolosowych wierszy (usr_id równomiernie rozłożonych między 0 a 10 tys., Równomiernie trans_idrozłożonych między 0 a 30),

Przez koszt zapytania odnoszę się poniżej do oszacowania kosztów optymalizatora opartego na kosztach Postgresa (z domyślnymi xxx_costwartościami Postgres ), które jest zważoną funkcją oszacowania wymaganych zasobów we / wy i procesora; można to uzyskać uruchamiając PgAdminIII i uruchamiając "Zapytanie / Wyjaśnij (F7)" na kwerendzie z "Opcjami Zapytania / Wyjaśnienia" ustawionymi na "Analiza"

  • Zapytanie Quassnoy zawiera kosztorys z 745k (!), I kończy w 1,3 sekundy (biorąc pod uwagę związek indeks ( usr_id, trans_id, time_stamp))
  • Zapytanie Billa ma szacowany koszt 93 tys. I trwa 2,9 sekundy (biorąc pod uwagę indeks złożony ( usr_id, trans_id))
  • Zapytanie 1 poniżej jest oszacowanie kosztów 16K, i wypełnia w 800ms (biorąc pod uwagę złożonych indeks ( usr_id, trans_id, time_stamp))
  • Zapytanie 2 poniżej jest oszacowanie kosztów w 14k, i wypełnia w 800ms (biorąc pod uwagę złożonych indeks funkcję ( usr_id, EXTRACT(EPOCH FROM time_stamp), trans_id))
    • jest to specyficzne dla Postgres
  • Zapytanie 3 poniżej (Postgres'a 8.4+) ma przybliżoną koszt i czas realizacji porównywalne (lub większą niż) zapytania 2 (przy współczynniku związek o ( usr_id, time_stamp, trans_id)); ma tę zaletę, że skanuje livestabelę tylko raz, a jeśli tymczasowo zwiększysz (w razie potrzeby) work_mem, aby pomieścić sortowanie w pamięci, będzie to zdecydowanie najszybsze ze wszystkich zapytań.

Wszystkie powyższe czasy obejmują pobranie pełnego zestawu wyników 10 tys. Wierszy.

Twoim celem jest minimalne oszacowanie kosztów i minimalny czas wykonania zapytania, z naciskiem na szacowany koszt. Wykonywanie zapytania może w znacznym stopniu zależeć od warunków środowiska wykonawczego (np. Czy odpowiednie wiersze są już w pełni buforowane w pamięci, czy nie), podczas gdy szacowanie kosztów nie. Z drugiej strony należy pamiętać, że kosztorys to dokładnie to, oszacowanie.

Najlepszy czas wykonania zapytania uzyskuje się, gdy działa na dedykowanej bazie danych bez obciążenia (np. Grając z pgAdminIII na komputerze deweloperskim). Czas zapytania będzie się różnić w produkcji w zależności od rzeczywistego obciążenia maszyny / rozrzutu dostępu do danych. Gdy jedno zapytanie wydaje się nieco szybsze (<20%) niż inne, ale ma znacznie wyższy koszt, rozsądniej będzie wybrać to, które ma dłuższy czas wykonania, ale niższe koszty.

Kiedy spodziewasz się, że nie będzie konkurencji o pamięć na twojej maszynie produkcyjnej w czasie wykonywania zapytania (np. Pamięć podręczna RDBMS i pamięć podręczna systemu plików nie zostaną zmiażdżone przez współbieżne zapytania i / lub aktywność systemu plików), wtedy uzyskany czas zapytania w trybie samodzielnym (np. pgAdminIII na komputerze deweloperskim) będzie reprezentatywny. Jeśli istnieje rywalizacja w systemie produkcyjnym, czas zapytania spadnie proporcjonalnie do szacowanego współczynnika kosztów, ponieważ zapytanie o niższym koszcie nie zależy w takim stopniu od pamięci podręcznej, podczas gdy zapytanie o wyższym koszcie będzie w kółko przeglądać te same dane (wyzwalając dodatkowe I / O w przypadku braku stabilnej pamięci podręcznej), np .:

              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 |

Nie zapomnij uruchomić ANALYZE livesraz po utworzeniu niezbędnych indeksów.


Zapytanie nr 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

Zapytanie nr 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]

Aktualizacja 2013/01/29

Wreszcie, od wersji 8.4 Postgres obsługuje funkcję okna, co oznacza, że ​​możesz napisać coś tak prostego i wydajnego, jak:

Zapytanie nr 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
źródło
Czy przez złożony indeks na (usr_id, trans_id, times_tamp) masz na myśli coś takiego jak „UTWÓRZ INDEKS lives_blah_idx ON lives (usr_id, trans_id, time_stamp)”? A może powinienem utworzyć trzy oddzielne indeksy dla każdej kolumny? Powinienem trzymać się domyślnego „UŻYWANIA btree”, prawda?
Joshua Berry
1
Tak dla pierwszego wyboru: mam na myśli CREATE INDEX lives_blah_idx ON lives (usr_id, trans_id, time_stamp). :) Twoje zdrowie.
vladr
Dzięki za wykonanie porównania kosztów vladr! Bardzo pełna odpowiedź!
Adam
@vladr Właśnie znalazłem twoją odpowiedź. Jestem trochę zdezorientowany, jak mówisz, że zapytanie 1 kosztuje 16 tys., A zapytanie 2 14 tys. Ale dalej w tabeli mówisz, że zapytanie 1 kosztuje 5 tys., A zapytanie 2 50 tys. Więc które zapytanie jest preferowane? :) dzięki
Houman
1
@Kave, tabela jest dla hipotetycznej pary zapytań w celu zilustrowania przykładu, a nie dwóch zapytań OP. Zmiana nazwy w celu zmniejszenia zamieszania.
vladr
82

Proponowałbym czystą wersję opartą na DISTINCT ON(patrz dokumentacja ):

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
źródło
6
To bardzo krótka i rozsądna odpowiedź. Ma również dobre odniesienie! To powinna być akceptowana odpowiedź.
Prakhar Agrawal
Wydawało się, że działa to dla mnie w mojej nieco innej aplikacji, w której nic innego nie działało. Zdecydowanie należy go podnieść, aby uzyskać lepszą widoczność.
Jim Factor
8

Oto inna metoda, która nie wykorzystuje skorelowanych podzapytań ani GROUP BY. Nie jestem ekspertem w dostrajaniu wydajności PostgreSQL, więc sugeruję wypróbowanie zarówno tego, jak i rozwiązań podanych przez innych, aby zobaczyć, które działa lepiej dla Ciebie.

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;

Zakładam, że trans_idjest to unikatowe przynajmniej w stosunku do dowolnej podanej wartości time_stamp.

Bill Karwin
źródło
4

Podoba mi się styl odpowiedzi Mike'a Woodhouse'a na drugiej stronie, o której wspomniałeś. Jest to szczególnie zwięzłe, gdy maksymalizowaną rzeczą jest tylko pojedyncza kolumna, w takim przypadku podzapytanie może po prostu użyć MAX(some_col)i GROUP BYinnych kolumn, ale w twoim przypadku masz 2-częściową ilość do zmaksymalizowania, nadal możesz to zrobić, używając ORDER BYplus LIMIT 1zamiast tego (jak zrobił to 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
)

Uważam, że używanie składni konstruktora wierszy jest WHERE (a, b, c) IN (subquery)przyjemne, ponieważ ogranicza ilość potrzebnych słów.

j_random_hacker
źródło
4

Oczywiście istnieje hackerskie rozwiązanie tego problemu. Powiedzmy, że chcesz wybrać największe drzewo z każdego lasu w regionie.

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

Kiedy grupujesz drzewa według lasów, pojawi się nieposortowana lista drzew i musisz znaleźć największe. Najpierw posortuj wiersze według ich rozmiarów i wybierz pierwszy z listy. Może się to wydawać nieefektywne, ale jeśli masz miliony wierszy, będzie to znacznie szybsze niż rozwiązania zawierające warunki JOINi WHERE.

BTW, zwróć uwagę, że ORDER_BYfor array_aggzostał wprowadzony w Postgresql 9.0

burak emre
źródło
Masz błąd. Musisz napisać ORDER BY tree_size.size DESC. Ponadto dla zadań autora kod będzie wyglądał następująco: 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
3

W Postgressql 9.5 jest nowa opcja o nazwie DISTINCT ON

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

Eliminuje zduplikowane wiersze i pozostawia tylko pierwszy wiersz zdefiniowany w mojej klauzuli ORDER BY.

zobacz oficjalną dokumentację

eden
źródło
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
        )

Utworzenie indeksu w (usr_id, time_stamp, trans_id)znacznie poprawi to zapytanie.

Zawsze, zawsze powinieneś mieć jakieś PRIMARY KEYw swoich tabelach.

Quassnoi
źródło
0

Myślę, że masz tutaj jeden poważny problem: nie ma monotonnie rosnącego „licznika”, który gwarantowałby, że dany wiersz wystąpi później niż inny. Weź ten przykład:

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

Na podstawie tych danych nie można określić, który wpis jest najnowszy. Czy to druga czy ostatnia? Nie ma funkcji sort ani max (), którą można zastosować do tych danych, aby udzielić poprawnej odpowiedzi.

Zwiększenie rozdzielczości znacznika czasu byłoby ogromną pomocą. Ponieważ aparat bazy danych serializuje żądania, przy odpowiedniej rozdzielczości można zagwarantować, że żadne dwa znaczniki czasu nie będą takie same.

Alternatywnie, użyj trans_id, który nie będzie się przewijał przez bardzo, bardzo długi czas. Posiadanie trans_id, który się przewija, oznacza, że ​​nie możesz stwierdzić (dla tego samego znacznika czasu), czy trans_id 6 jest nowszy niż trans_id 1, chyba że wykonasz skomplikowaną matematykę.

Barry Brown
źródło
Tak, najlepiej byłoby, gdyby kolumna z sekwencją (autoinkrementacja) była w porządku.
vladr
Z góry założono, że dla małych przyrostów czasu trans_id nie będzie się przewijać. Zgadzam się, że tabela wymaga unikalnego indeksu podstawowego - jak niepowtarzalny identyfikator trans_id. (PS Cieszę się, że mam teraz wystarczająco dużo punktów karmy / reputacji do skomentowania!)
Joshua Berry,
Vlad twierdzi, że trans_id ma raczej krótki cykl, który często się przewraca. Nawet jeśli weźmiesz pod uwagę tylko środkowe dwa wiersze z mojej tabeli (trans_id = 6 i 1), nadal nie możesz powiedzieć, który jest najnowszy. Dlatego użycie max (trans_id) dla danego znacznika czasu nie zadziała.
Barry Brown
Tak, polegam na gwarancji autora aplikacji, że krotka (time_stamp, trans_id) jest unikalna dla danego użytkownika. Jeśli tak nie jest, wówczas „SELECT l1.usr_id, l1.lives_left, ... FROM ... WHERE ...” musi stać się „SELECT l1.usr_id, MAX / MIN (l1.lives_left), ... FROM. .. GDZIE ... GROUP BY l1.usr_id, ...
vladr
0

Inne rozwiązanie, które może okazać się przydatne.

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
źródło