Jak wydajnie uzyskać „najnowszy odpowiedni wiersz”?

53

Mam wzorzec zapytania, który musi być bardzo powszechny, ale nie wiem, jak napisać dla niego wydajne zapytanie. Chcę wyszukać wiersze tabeli odpowiadające „najnowszej dacie nie później” niż wiersze innej tabeli.

Mam, inventorypowiedzmy, tabelę, która reprezentuje ekwipunek, który przechowuję pewnego dnia.

date       | good | quantity
------------------------------
2013-08-09 | egg  | 5
2013-08-09 | pear | 7
2013-08-02 | egg  | 1
2013-08-02 | pear | 2

i stół, powiedzmy „cena”, który zawiera cenę towaru w danym dniu

date       | good | price
--------------------------
2013-08-07 | egg  | 120
2013-08-06 | pear | 200
2013-08-01 | egg  | 110
2013-07-30 | pear | 220

Jak mogę efektywnie uzyskać „najnowszą” cenę dla każdego wiersza tabeli zapasów, tj

date       | pricing date | good | quantity | price
----------------------------------------------------
2013-08-09 | 2013-08-07   | egg  | 5        | 120
2013-08-09 | 2013-08-06   | pear | 7        | 200
2013-08-02 | 2013-08-01   | egg  | 1        | 110
2013-08-02 | 2013-07-30   | pear | 2        | 220

Znam jeden sposób:

select inventory.date, max(price.date) as pricing_date, good
from inventory, price
where inventory.date >= price.date
and inventory.good = price.good
group by inventory.date, good

a następnie ponownie dołącz to zapytanie do spisu. W przypadku dużych tabel nawet wykonanie pierwszego zapytania (bez ponownego łączenia się z zapasami) jest bardzo wolne. Jednak ten sam problem można szybko rozwiązać, jeśli po prostu używam mojego języka programowania do wydawania jednego max(price.date) ... where price.date <= date_of_interest ... order by price.date desc limit 1zapytania dla każdego date_of_interestz tabeli inwentarza, więc wiem, że nie ma przeszkód obliczeniowych. Wolałbym jednak rozwiązać cały problem za pomocą pojedynczego zapytania SQL, ponieważ pozwoliłoby mi to na dalsze przetwarzanie kodu SQL na podstawie wyniku zapytania.

Czy istnieje standardowy sposób, aby to zrobić skutecznie? Wydaje się, że musi to często pojawiać się i powinien istnieć sposób na napisanie szybkiego zapytania.

Korzystam z Postgres, ale doceniłbym ogólną odpowiedź na SQL.

Tom Ellis
źródło
3
Głosowano na migrację do DBA.SE, ponieważ jest to kwestia wydajności. Możemy napisać zapytanie na kilka różnych sposobów, ale nie przyspieszy to.
ypercubeᵀᴹ
5
Czy faktycznie potrzebujesz wszystkich towarów na wszystkie dni z jednego zapytania? Wydaje się to mało prawdopodobnym wymogiem? Częściej pobierane są ceny za konkretny termin lub ceny za konkretny towar (w konkretnym dniu). Te alternatywne zapytania mogłyby znacznie łatwiej skorzystać z (odpowiednich) wskaźników. Musimy także wiedzieć: liczności (ile wierszy w każdej tabeli?), Pełną definicję tabeli włącznie. typy danych, ograniczenia, indeksy, ... (użyj \d tblw psql), twoja wersja Postgres i min. / max. liczba cen za towar.
Erwin Brandstetter,
@ErwinBrandstetter Czy pytasz mnie o odpowiedź? Nie jestem zbyt wykwalifikowany, aby wiedzieć, co jest najlepsze, ale ponieważ twoje ma najwięcej pozytywnych opinii, chętnie to przyjmę.
Tom Ellis
Zaakceptuj tylko, jeśli odpowie na twoje pytanie lub działa dla Ciebie. Możesz nawet zostawić komentarz, jak postąpiłeś, jeśli to może pomóc w powiązanych sprawach. Jeśli uważasz, że na twoje pytanie nie ma odpowiedzi, daj nam znać.
Erwin Brandstetter,
1
Muszę więc przeprosić, ponieważ chociaż otrzymałem coś, co wydaje się być doskonałą odpowiedzią, nie pracuję już nad problemem, który wywołał pytanie, więc nie jestem w stanie ocenić, która odpowiedź jest najlepsza, a nawet jeśli któraś z nich są naprawdę odpowiednie dla mojego przypadku użycia (tak jak było). Jeśli jest jakaś etykieta DBA.Stackexchange, której powinienem przestrzegać, proszę dać mi znać.
Tom Ellis,

Odpowiedzi:

42

To bardzo zależy od okoliczności i dokładnych wymagań. Rozważ mój komentarz do pytania .

Proste rozwiązanie

Z DISTINCT ONw Postgres:

SELECT DISTINCT ON (i.good, i.the_date)
       i.the_date, p.the_date AS pricing_date, i.good, p.price
FROM   inventory  i
LEFT   JOIN price p ON i.good = p.good AND i.the_date >= p.the_date
ORDER  BY i.good, i.the_date, p.the_date DESC;

Zamówiony wynik.

Lub ze NOT EXISTSstandardowym SQL (działa z każdym znanym RDBMS):

SELECT i.the_date, p.the_date AS pricing_date, i.good, i.quantity, p.price
FROM   inventory  i
LEFT   JOIN price p ON p.good = i.good AND p.the_date <= i.the_date
WHERE  NOT EXISTS (
   SELECT 1 FROM price p1
   WHERE  p1.good = p.good
   AND p1.the_date <= i.the_date
   AND p1.the_date >  p.the_date
   );

Ten sam wynik, ale z dowolną kolejnością sortowania - chyba że dodasz ORDER BY.
W zależności od dystrybucji danych, dokładnych wymagań i wskaźników, jeden z nich może być szybszy.
Ogólnie rzecz biorąc, DISTINCT ONjest zwycięzcą, a na dodatek otrzymujesz posortowany wynik. Jednak w niektórych przypadkach inne techniki zapytań są (znacznie) szybsze. Patrz poniżej.

Rozwiązania z podzapytaniami do obliczania wartości maksymalnych / minimalnych są na ogół wolniejsze. Warianty z CTE są jednak ogólnie wolniejsze.

Zwykłe widoki (jak proponowana przez inną odpowiedź) wcale nie pomagają w wydajności w Postgres.

SQL Fiddle.


Właściwe rozwiązanie

Ciągi i zestawianie

Przede wszystkim cierpisz z powodu nieoptymalnego układu stołu. Może się to wydawać trywialne, ale normalizacja schematu może być bardzo trudna.

Sortowanie według typów znakowych ( text, varchar, ...) musi być wykonana zgodnie z lokalizacji - na zestawień w szczególności. Najprawdopodobniej twoja baza danych korzysta z lokalnego zestawu reguł (np. W moim przypadku de_AT.UTF-8:). Dowiedz się za pomocą:

SHOW lc_collate;

Powoduje to, że sortowanie i indeksowanie wyszukiwania jest wolniejsze . Im dłuższe są twoje łańcuchy (nazwy towarów), tym gorzej. Jeśli w rzeczywistości nie obchodzą Cię reguły sortowania (lub w ogóle porządek sortowania), może to być szybsze, jeśli dodasz COLLATE "C":

SELECT DISTINCT ON (i.good COLLATE "C", i.the_date)
       i.the_date, p.the_date AS pricing_date, i.good, p.price
FROM   inventory  i
LEFT   JOIN price p ON i.good = p.good AND i.the_date >= p.the_date
ORDER  BY i.good COLLATE "C", i.the_date, p.the_date DESC;

Zwróć uwagę, jak dodałem zestawienie w dwóch miejscach.
Dwa razy szybciej w moim teście, każdy z 20 tys. Wierszy i bardzo podstawowymi nazwami („good123”).

Indeks

Jeśli zapytanie ma używać indeksu, kolumny z danymi znakowymi muszą używać zgodnego sortowania ( goodw przykładzie):

CREATE INDEX inventory_good_date_desc_collate_c_idx
ON price(good COLLATE "C", the_date DESC);

Przeczytaj dwa ostatnie rozdziały tej pokrewnej odpowiedzi na SO:

Możesz nawet mieć wiele indeksów z różnymi zestawieniami w tych samych kolumnach - jeśli potrzebujesz również towarów posortowanych według innego (lub domyślnego) zestawienia w innych zapytaniach.

Normalizować

Nadmiarowe ciągi (nazwa dobra) również nadmuchują tabele i indeksy, co czyni wszystko jeszcze wolniejszym. Przy prawidłowym układzie tabeli można na początku uniknąć większości problemów. Może wyglądać tak:

CREATE TABLE good (
  good_id serial PRIMARY KEY
, good    text   NOT NULL
);

CREATE TABLE inventory (
  good_id  int  REFERENCES good (good_id)
, the_date date NOT NULL
, quantity int  NOT NULL
, PRIMARY KEY(good_id, the_date)
);

CREATE TABLE price (
  good_id  int     REFERENCES good (good_id)
, the_date date    NOT NULL
, price    numeric NOT NULL
, PRIMARY KEY(good_id, the_date));

Klucze podstawowe automatycznie zapewniają (prawie) wszystkie potrzebne indeksy.
W zależności od brakujących szczegółów indeks wielokolumnowy włączony pricew kolejności malejącej w drugiej kolumnie może poprawić wydajność:

CREATE INDEX price_good_date_desc_idx ON price(good, the_date DESC);

Ponownie sortowanie musi pasować do zapytania (patrz wyżej).

W Postgresie 9.2 lub nowszym „indeksowanie indeksów” dla skanów tylko indeksowych może trochę pomóc - zwłaszcza jeśli tabele zawierają dodatkowe kolumny, dzięki czemu tabela jest znacznie większa niż indeks indeksujący.

Te wynikowe zapytania są znacznie szybsze:

NIE ISTNIEJE

SELECT i.the_date, p.the_date AS pricing_date, g.good, i.quantity, p.price
FROM   inventory  i
JOIN   good       g USING (good_id)
LEFT   JOIN price p ON p.good_id = i.good_id AND p.the_date <= i.the_date
AND    NOT EXISTS (
   SELECT 1 FROM price p1
   WHERE  p1.good_id = p.good_id
   AND    p1.the_date <= i.the_date
   AND    p1.the_date >  p.the_date
   );

WYRÓŻNIJ WŁ

SELECT DISTINCT ON (i.the_date)
       i.the_date, p.the_date AS pricing_date, g.good, i.quantity, p.price
FROM   inventory  i
JOIN   good       g USING (good_id)
LEFT   JOIN price p ON p.good_id = i.good_id AND p.the_date <= i.the_date
ORDER  BY i.the_date, p.the_date DESC;

SQL Fiddle.


Szybsze rozwiązania

Jeśli to nadal nie jest wystarczająco szybkie, mogą istnieć szybsze rozwiązania.

Rekurencyjne JOIN LATERALpodkwerendy CTE / /

Zwłaszcza w przypadku dystrybucji danych z wieloma cenami za towar :

Widok zmaterializowany

Jeśli musisz uruchamiać to często i szybko, sugeruję utworzenie zmaterializowanego widoku. Myślę, że można bezpiecznie założyć, że ceny i zapasy z poprzednich dat rzadko się zmieniają. Oblicz wynik raz i zapisz migawkę jako zmaterializowany widok.

Postgres 9.3+ ma zautomatyzowaną obsługę zmaterializowanych widoków. Możesz łatwo wdrożyć wersję podstawową w starszych wersjach.

Erwin Brandstetter
źródło
3
price_good_date_desc_idxIndeks polecacie znacznie poprawiło wydajność podobnym zapytaniu kopalni. Mój plan zapytań przeszedł od kosztu 42374.01..42374.86do 0.00..37.12!
cimmanon,
@cimmanon: Fajnie! Jaka jest Twoja podstawowa funkcja zapytania? NIE ISTNIEJE? WYRÓŻNIAĆ? GRUPUJ WEDŁUG?
Erwin Brandstetter,
Korzystanie z DISTINCT ON
cimmanon,
6

Do Twojej wiadomości użyłem mssql 2008, więc Postgres nie będzie miał indeksu „include”. Jednak korzystanie z podstawowej indeksacji pokazanej poniżej zmieni się ze złączeń mieszających na scalanie złączeń w Postgres: http://explain.depesz.com/s/eF6 (brak indeksu) http://explain.depesz.com/s/j9x ( z indeksem kryteriów łączenia)

Proponuję rozbić twoje zapytanie na dwie części. Po pierwsze, widok (nie mający na celu poprawy wydajności), który można wykorzystać w różnych innych kontekstach, który reprezentuje związek między datami zapasów i datami wyceny.

create view mostrecent_pricing_dates_per_good as
select i.good,i.date i_date,max(p.date)p_date
  from inventory i
  join price p on i.good = p.good and i.date >= p.date
 group by i.good,i.date;

Wówczas zapytanie może stać się prostsze i łatwiejsze do manipulowania innymi rodzajami, jeśli zapytanie (takie jak użycie lewych złączeń do znalezienia zapasów bez ostatnich dat wyceny):

select i.good
       ,i.date inventory_date
       ,i.quantity
       ,p.date pricing_date
       ,p.price       
  from inventory i
  join price p on i.good = p.good
  join mostrecent_pricing_dates_per_good x 
    on i.good = x.good 
   and p.date = x.p_date
   and i.date = x.i_date

Daje to następujący plan wykonania: http://sqlfiddle.com/#!3/24f23/1 bez indeksowania

... Wszystkie skany z pełnym rodzajem. Zauważ, że koszt wydajności dopasowań haszujących zajmuje większość kosztów całkowitych ... i wiemy, że skanowanie i sortowanie tabeli jest powolne (w porównaniu do celu: szukanie indeksu).

Teraz dodaj podstawowe indeksy, aby pomóc w kryteriach zastosowanych w twoim złączeniu (nie twierdzę, że są to indeksy optymalne, ale ilustrują one sens): http://sqlfiddle.com/#!3/5ec75/1 z podstawowym indeksowaniem

To pokazuje poprawę. Operacje na zagnieżdżonej pętli (łączenie wewnętrzne) nie obciążają już żadnych istotnych kosztów całkowitych dla zapytania. Reszta kosztów jest teraz rozłożona na poszukiwanie indeksów (skanowanie zapasów, ponieważ ściągamy każdy wiersz zapasów). Ale możemy jeszcze lepiej, ponieważ zapytanie pobiera ilość i cenę. Aby uzyskać te dane, po dokonaniu oceny kryteriów łączenia należy wykonać wyszukiwania.

Ostateczna iteracja używa „włącz” w indeksach, aby ułatwić przesuwanie się planu i pobieranie dodatkowych żądanych danych bezpośrednio z samego indeksu. Tak więc wyszukiwania zniknęły: http://sqlfiddle.com/#!3/5f143/1 wprowadź opis zdjęcia tutaj

Teraz mamy plan zapytań, w którym całkowity koszt zapytania rozkłada się równomiernie na bardzo szybkie operacje wyszukiwania indeksu. Będzie to prawie tak dobre, jak to możliwe. Z pewnością inni eksperci mogą to poprawić, ale rozwiązanie rozwiązuje kilka głównych problemów:

  1. Tworzy zrozumiałe struktury danych w bazie danych, które są łatwiejsze do komponowania i ponownego wykorzystania w innych obszarach aplikacji.
  2. Wszystkie najbardziej kosztowne operatory zapytań zostały uwzględnione w planie zapytań przy użyciu podstawowych indeksowań.
cocogorilla
źródło
3
Jest to w porządku (dla SQL-Server), ale optymalizacja dla różnych DBMS, chociaż ma podobieństwa, ma też poważne różnice.
ypercubeᵀᴹ
@ypercube to prawda. Dodałem pewne kwalifikacje dotyczące Postgres. Moim zamiarem było, aby większość przedstawionego tutaj procesu myślowego obowiązywała niezależnie od specyficznych funkcji DBMS.
cocogorilla
Odpowiedź jest bardzo głęboka, więc jej wypróbowanie zajmie mi trochę czasu. Dam ci znać, jak sobie radzę.
Tom Ellis,
5

Jeśli zdarzyło Ci się mieć PostgreSQL 9.3 (wydany dzisiaj), możesz użyć POŁĄCZENIA BOCZNEGO.

Nie mam możliwości przetestowania tego i nigdy wcześniej go nie używałem, ale z tego, co mogę stwierdzić na podstawie dokumentacji, składnia wyglądałaby następująco:

SELECT  Inventory.Date,
        Inventory.Good,
        Inventory.Quantity,
        Price.Date,
        Price.Price
FROM    Inventory
        LATERAL
        (   SELECT  Date, Price
            FROM    Price
            WHERE   Price.Good = Inventory.Good
            AND     Price.Date <= Inventory.Date
            ORDER BY Price.Date DESC
            LIMIT 1
        ) p;

Jest to w zasadzie odpowiednik APLIKACJI SQL-Servera , i istnieje praktyczny przykład tego na SQL-Fiddle do celów demonstracyjnych.

GarethD
źródło
5

Jak zauważyli Erwin i inni, wydajne zapytanie zależy od wielu zmiennych, a PostgreSQL bardzo stara się zoptymalizować wykonanie zapytania w oparciu o te zmienne. Ogólnie rzecz biorąc, chcesz najpierw napisać dla zachowania przejrzystości, a następnie zmodyfikować wydajność po zidentyfikowaniu wąskich gardeł.

Dodatkowo PostgreSQL ma wiele sztuczek, których możesz użyć, aby uczynić rzeczy nieco bardziej wydajnymi (częściowe indeksy dla jednego), więc w zależności od obciążenia odczytu / zapisu możesz być w stanie zoptymalizować to bardzo daleko, patrząc na uważne indeksowanie.

Pierwszą rzeczą, którą należy wypróbować, jest zrobienie widoku i dołączenie do niego:

CREATE VIEW most_recent_rows AS
SELECT good, max(date) as max_date
FROM inventory
GROUP BY good;

Powinno to działać dobrze podczas robienia czegoś takiego:

SELECT price 
  FROM inventory i
  JOIN goods g ON i.goods = g.description
  JOIN most_recent_rows r ON i.goods = r.goods
 WHERE g.id = 123;

Możesz do tego dołączyć. Kwerenda ostatecznie połączy widok z bazową tabelą, ale zakładając, że masz unikalny indeks (data, dobry w tej kolejności ), powinieneś zacząć (ponieważ będzie to proste wyszukiwanie w pamięci podręcznej). Będzie to działało bardzo dobrze z kilkoma rzędami w górę, ale będzie bardzo nieefektywne, jeśli spróbujesz strawić miliony cen towarów.

Drugą rzeczą, którą możesz zrobić, to dodać do tabeli ekwipunku kolumnę bool najbardziej_recent i

create unique index on inventory (good) where most_recent;

Następnie należy użyć wyzwalaczy, aby ustawić wartość most_recent na wartość false, gdy wstawiono nowy wiersz towaru. Zwiększa to złożoność i zwiększa szanse na błędy, ale jest pomocne.

Ponownie wiele z tego zależy od istnienia odpowiednich indeksów. W przypadku najnowszych zapytań o datę prawdopodobnie powinieneś mieć indeks na datę i ewentualnie wielokolumnowy, zaczynający się od daty i zawierający kryteria łączenia.

Zaktualizuj Poniższy komentarz Erwina wygląda na to, że źle to zrozumiałem. Ponownie czytając pytanie, wcale nie jestem pewien, co jest zadawane. Chcę wspomnieć w aktualizacji o potencjalnym problemie, który widzę i dlaczego nie jest to jasne.

Oferowany projekt bazy danych nie ma rzeczywistego zastosowania edytora IME w systemach ERP i księgowych. Działałoby to w hipotetycznym modelu wyceny idealnej, w którym wszystko sprzedawane w danym dniu danego produktu ma tę samą cenę. Jednak nie zawsze tak jest. Nie dotyczy to nawet wymiany walut (chociaż niektóre modele udają, że tak jest). Jeśli jest to wymyślony przykład, jest niejasny. Jeśli jest to prawdziwy przykład, występują większe problemy z projektem na poziomie danych. Zakładam tutaj, że to prawdziwy przykład.

Nie można zakładać, że sama data określa cenę danego towaru. Ceny w każdej firmie mogą być negocjowane dla kontrahenta, a czasem nawet dla transakcji. Z tego powodu naprawdę powinieneś przechowywać cenę w tabeli, która faktycznie obsługuje inwentaryzację zapasów (tabela inwentaryzacji). W takim przypadku tabela daty / towarów / cen określa jedynie cenę bazową, która może ulec zmianie w wyniku negocjacji. W takim przypadku problem ten przechodzi od problemu raportowania do problemu transakcyjnego i działającego w jednym wierszu z każdej tabeli na raz. Na przykład możesz sprawdzić domyślną cenę danego produktu w danym dniu jako:

 SELECT price 
   FROM prices p
   JOIN goods g ON p.good = g.good
  WHERE g.id = 123 AND p."date" >= '2013-03-01'
  ORDER BY p."date" ASC LIMIT 1;

Dzięki indeksowi cen (dobry, data) będzie to działać dobrze.

I to jest wymyślony przykład, być może coś bliższego temu, nad czym pracujesz, pomogłoby.

Chris Travers
źródło
most_recentPodejście powinno działać dobrze dla ostatniej ceny absolutnie . Wydaje się, że OP potrzebuje najnowszej ceny w odniesieniu do każdej daty inwentaryzacji.
Erwin Brandstetter,
Słuszna uwaga. Ponowne czytanie dostrzegam jednak pewne praktyczne braki w proponowanych danych, ale nie wiem, czy jest to wymyślony przykład. Jako wymyślony przykład nie mogę powiedzieć, czego brakuje. Być może aktualizacja również by to wskazała.
Chris Travers
@ChrisTravers: To wymyślony przykład, ale nie wolno mi opublikować rzeczywistego schematu, z którym pracuję. Być może mógłbyś powiedzieć trochę o tym, jakie praktyczne braki zauważyłeś.
Tom Ellis,
Nie sądzę, że to musi być dokładne, ale martwię się, że problem zostanie utracony w alegorii. Przydałoby się coś nieco bliższego. Problem polega na tym, że przy wycenie cena w danym dniu może być domyślna, w związku z czym nie użyłbyś jej do raportowania tylko jako domyślnego przy wprowadzaniu transakcji, więc twoje interesujące zapytania są zwykle tylko kilka wierszy na raz czas.
Chris Travers
3

Innym sposobem byłoby użycie funkcji okna, lead()aby uzyskać zakres dat dla każdego wiersza w cenie tabeli, a następnie użyć betweenprzy dołączaniu zapasów. Użyłem tego w prawdziwym życiu, ale głównie dlatego, że był to mój pierwszy pomysł, jak to rozwiązać.

with cte as (
  select
    good,
    price,
    date,
    coalesce(lead(date) over(partition by good order by date) - 1
            ,Now()::date) as ndate
  from
    price
)

select * from inventory i join cte on
  (i.good = cte.good and i.date between cte.date and cte.ndate)

SqlFiddle

Tomas Greif
źródło
1

Użyj sprzężenia z zapasów do wyceny z warunkami łączenia, które ograniczają zamówienia z tabeli cen tylko do tych, które są w dniu zapasu lub przed nim, a następnie wyodrębnij datę maksymalną i gdzie data jest najwyższą datą z tego podzbioru

Tak więc w przypadku ceny zapasów:

 Select i.date, p.Date pricingDate,
    i.good, quantity, price        
 from inventory I join price p 
    on p.good = i.good
        And p.Date = 
           (Select Max(Date from price
            where good = i.good
               and date <= i.Date)

Jeśli cena dowolnego określonego towaru zmieniła się więcej niż raz w tym samym dniu, a tak naprawdę w tych kolumnach są tylko daty, a nie czasy, może być konieczne nałożenie dodatkowych ograniczeń na połączenia, aby wybrać tylko jeden z rekordów zmiany ceny.


źródło
Niestety nie przyspiesza.