Millionen Zeilen denomalisierter Daten oder SQL-Magie speichern?

8

Meine DBA-Erfahrung geht nicht viel weiter als das einfache Speichern und Abrufen von Daten im CMS-Stil - dies kann also eine dumme Frage sein, ich weiß es nicht!

Ich habe ein Problem, bei dem ich die Urlaubspreise für eine bestimmte Gruppengröße und eine bestimmte Anzahl von Tagen innerhalb eines bestimmten Zeitraums nachschlagen oder berechnen muss. Z.B:

Wie viel kostet ein Hotelzimmer für 2 Personen für 4 Nächte im Januar?

Ich habe Preis- und Verfügbarkeitsdaten für beispielsweise 5000 Hotels, die wie folgt gespeichert sind:

Hotel ID | Date | Spaces | Price PP
-----------------------------------
     123 | Jan1 | 5      | 100
     123 | Jan2 | 7      | 100
     123 | Jan3 | 5      | 100
     123 | Jan4 | 3      | 100
     123 | Jan5 | 5      | 100
     123 | Jan6 | 7      | 110
     456 | Jan1 | 5      | 120
     456 | Jan2 | 1      | 120
     456 | Jan3 | 4      | 130
     456 | Jan4 | 3      | 110
     456 | Jan5 | 5      | 100
     456 | Jan6 | 7      |  90

Mit dieser Tabelle kann ich eine Abfrage wie folgt durchführen:

SELECT hotel_id, sum(price_pp)
FROM hotel_data
WHERE
    date >= Jan1 and date <= Jan4
    and spaces >= 2
GROUP BY hotel_id
HAVING count(*) = 4;

Ergebnisse

hotel_id | sum
----------------
     123 | 400

Die HAVINGKlausel hier stellt sicher, dass für jeden einzelnen Tag zwischen meinen gewünschten Daten ein Eintrag vorhanden ist, für den die verfügbaren Plätze verfügbar sind. dh. Das Hotel 456 hatte am 2. Januar 1 freien Platz, die HAVING-Klausel würde 3 zurückgeben, sodass wir für das Hotel 456 kein Ergebnis erhalten.

So weit, ist es gut.

Gibt es jedoch eine Möglichkeit, alle 4 Nachtperioden im Januar herauszufinden, in denen Platz verfügbar ist? Wir könnten die Abfrage 27 Mal wiederholen und die Daten jedes Mal erhöhen, was etwas umständlich erscheint. Oder ein anderer Weg könnte darin bestehen, alle möglichen Kombinationen in einer Nachschlagetabelle wie folgt zu speichern:

Hotel ID | total price pp | num_people | num_nights | start_date
----------------------------------------------------------------
     123 |            400 | 2          | 4          | Jan1
     123 |            400 | 2          | 4          | Jan2
     123 |            400 | 2          | 4          | Jan3
     123 |            400 | 3          | 4          | Jan1
     123 |            400 | 3          | 4          | Jan2
     123 |            400 | 3          | 4          | Jan3

Und so weiter. Wir müssten die maximale Anzahl von Nächten und die maximale Anzahl von Personen, nach denen wir suchen würden, begrenzen - z. B. maximale Anzahl von Nächten = 28, maximale Anzahl von Personen = 10 (begrenzt auf die Anzahl der verfügbaren Plätze für diesen festgelegten Zeitraum ab diesem Datum).

Für ein Hotel könnten wir 28 * 10 * 365 = 102000 Ergebnisse pro Jahr erzielen. 5000 Hotels = 500 Millionen Ergebnisse!

Aber wir hätten eine sehr einfache Frage, um den günstigsten 4-Nächte-Aufenthalt im Januar für 2 Personen zu finden:

SELECT
hotel_id, start_date, price
from hotel_lookup
where num_people=2
and num_nights=4
and start_date >= Jan1
and start_date <= Jan27
order by price
limit 1;

Gibt es eine Möglichkeit, diese Abfrage für die ursprüngliche Tabelle durchzuführen, ohne die 500-m-Zeilen-Nachschlagetabelle generieren zu müssen? zB die 27 möglichen Ergebnisse in einer temporären Tabelle oder einer anderen solchen inneren Abfragemagie generieren?

Momentan werden alle Daten in einer Postgres-Datenbank gespeichert. Können wir die Daten bei Bedarf zu einem anderen geeigneten Ort verschieben? Nicht sicher, ob diese Art von Abfrage zu den Map / Reduce-Mustern für DBs im NoSQL-Stil passt ...

Guy Bowden
quelle

Antworten:

6

Mit Fensterfunktionen kann man viel anfangen . Präsentation von zwei Lösungen : eine mit und eine ohne materialisierte Ansicht.

Testfall

Aufbauend auf dieser Tabelle:

CREATE TABLE hotel_data (
   hotel_id int
 , day      date  -- using "day", not "date"
 , spaces   int
 , price    int
 , PRIMARY KEY (hotel_id, day)  -- provides essential index automatically
);

Tage pro hotel_idmüssen eindeutig sein (hier von PK erzwungen), sonst ist der Rest ungültig.

Mehrspaltiger Index für Basistabelle:

CREATE INDEX mv_hotel_mult_idx ON mv_hotel (day, hotel_id);

Beachten Sie die umgekehrte Reihenfolge im Vergleich zur PK. Sie werden wahrscheinlich beide Indizes benötigen. Für die folgende Abfrage ist der 2. Index unerlässlich. Ausführliche Erklärung:

Direkte Abfrage ohne MATERIALIZED VIEW

SELECT hotel_id, day, sum_price
FROM  (
   SELECT hotel_id, day, price, spaces
        , sum(price)      OVER w * 2   AS sum_price
        , min(spaces)     OVER w       AS min_spaces
        , last_value(day) OVER w - day AS day_diff
        , count(*)        OVER w       AS day_ct
   FROM   hotel_data
   WHERE  day BETWEEN '2014-01-01'::date AND '2014-01-31'::date
   AND    spaces >= 2
   WINDOW w AS (PARTITION BY hotel_id ORDER BY day
                ROWS BETWEEN CURRENT ROW AND 3 FOLLOWING) -- adapt to nights - 1
   ) sub
WHERE  day_ct = 4
AND    day_diff = 3  -- make sure there is not gap
AND    min_spaces >= 2
ORDER  BY sum_price, hotel_id, day;
-- LIMIT 1 to get only 1 winner;

Siehe auch die Variante von @ ypercube mitlag() , die ersetzt werden kann day_ctund day_diffmit einem einzigen Scheck.

Erklären

  • Berücksichtigen Sie in der Unterabfrage nur Tage innerhalb Ihres Zeitrahmens ("im Januar" bedeutet, dass der letzte Tag im Zeitrahmen enthalten ist).

  • Der Rahmen für die Fensterfunktionen umfasst die aktuelle Zeile sowie die nächsten num_nights - 1( 4 - 1 = 3) Zeilen (Tage). Berechnen Sie die Differenz in Tagen , die Anzahl der Zeilen und das Minimum an Leerzeichen, um sicherzustellen, dass der Bereich lang genug , lückenlos und immer ausreichend Leerzeichen ist .

    • Leider akzeptiert die Frame-Klausel von Fensterfunktionen keine dynamischen Werte und kann daher nicht für eine vorbereitete Anweisung parametrisiert werden.ROWS BETWEEN CURRENT ROW AND 3 FOLLOWING`
  • Ich habe alle Fensterfunktionen in der Unterabfrage sorgfältig entworfen, um dasselbe Fenster mit einem einzigen Sortierschritt wiederzuverwenden .

  • Der resultierende Preis sum_pricewird bereits mit der Anzahl der angeforderten Plätze multipliziert.

Mit MATERIALIZED VIEW

Speichern Sie nur die Spalten, die Sie benötigen, sowie drei redundante, berechnete Werte aus der Basistabelle, um zu vermeiden, dass viele Zeilen ohne Erfolgschance überprüft werden. Stellen Sie sicher, dass das MV auf dem neuesten Stand ist. Wenn Sie mit dem Konzept nicht vertraut sind, lesen Sie zuerst das Handbuch .

CREATE MATERIALIZED VIEW mv_hotel AS
SELECT hotel_id, day
     , first_value(day) OVER (w ORDER BY day) AS range_start
     , price, spaces
     ,(count(*)    OVER w)::int2 AS range_len
     ,(max(spaces) OVER w)::int2 AS max_spaces

FROM  (
   SELECT *
        , day - row_number() OVER (PARTITION BY hotel_id ORDER BY day)::int AS grp
   FROM   hotel_data
   ) sub1
WINDOW w AS (PARTITION BY hotel_id, grp);
  • range_start speichert den ersten Tag jedes kontinuierlichen Bereichs für zwei Zwecke:

    • um eine Reihe von Zeilen als Mitglieder eines gemeinsamen Bereichs zu markieren
    • um den Beginn des Bereichs für mögliche andere Zwecke anzuzeigen.
  • range_lenist die Anzahl der Tage im lückenlosen Bereich.
    max_spacesist das Maximum der Freiflächen im Bereich.

    • Beide Spalten werden verwendet, um unmögliche Zeilen sofort von der Abfrage auszuschließen.
  • Ich habe beide in smallint(max. 32768 sollte für beide ausreichend sein) umgewandelt, um die Speicherung zu optimieren: nur 52 Bytes pro Zeile (inkl. Heap-Tupel-Header und Elementzeiger). Einzelheiten:

Mehrspaltenindex für MV:

CREATE INDEX mv_hotel_mult_idx ON mv_hotel (range_len, max_spaces, day);

Abfrage basierend auf MV

SELECT hotel_id, day, sum_price
FROM  (
   SELECT hotel_id, day, price, spaces
        , sum(price)      OVER w * 2   AS sum_price
        , min(spaces)     OVER w       AS min_spaces
        , count(*)        OVER w       AS day_ct
   FROM   mv_hotel
   WHERE  day BETWEEN '2014-01-01'::date AND '2014-01-31'::date
   AND    range_len >= 4   -- exclude impossible rows
   AND    max_spaces >= 2  -- exclude impossible rows
   WINDOW w AS (PARTITION BY hotel_id, range_start ORDER BY day
                ROWS BETWEEN CURRENT ROW AND 3 FOLLOWING) -- adapt to $nights - 1
   ) sub
WHERE  day_ct = 4
AND    min_spaces >= 2
ORDER  BY sum_price, hotel_id, day;
-- LIMIT 1 to get only 1 winner;

Dies ist schneller als die Abfrage in der Tabelle, da sofort mehr Zeilen entfernt werden können. Auch hier ist der Index von wesentlicher Bedeutung. Da Partitionen hier lückenlos sind, reicht eine Überprüfung day_ctaus.

SQL Fiddle demonstriert beides .

Wiederholter Gebrauch

Wenn Sie es häufig verwenden, würde ich eine SQL-Funktion erstellen und nur Parameter übergeben. Oder eine PL / pgSQL- Funktion mit dynamischem SQL und EXECUTEzum Anpassen der Frame-Klausel.

Alternative

Bereichstypen, bei denen date_rangefortlaufende Bereiche in einer einzigen Zeile gespeichert werden sollen, können eine Alternative sein - in Ihrem Fall kompliziert durch mögliche Preis- oder Platzschwankungen pro Tag.

Verwandte Antworten

Erwin Brandstetter
quelle
@ GuyBowden: Besser ist der Feind des Guten. Betrachten Sie die weitgehend umgeschriebene Antwort.
Erwin Brandstetter
3

Ein anderer Weg, mit der LAG()Funktion:

WITH x AS
  ( SELECT hotel_id, day, 
           LAG(day, 3) OVER (PARTITION BY hotel_id 
                             ORDER BY day)
              AS day_start,
           2 * SUM(price) OVER (PARTITION BY hotel_id 
                                ORDER BY day
                                ROWS BETWEEN 3 PRECEDING 
                                         AND CURRENT ROW)
              AS sum_price
    FROM hotel_data
    WHERE spaces >= 2
   -- AND day >= '2014-01-01'::date      -- date restrictions 
   -- AND day <  '2014-02-01'::date      -- can be added here
  )
SELECT hotel_id, day_start, sum_price
FROM x
WHERE day_start = day - 3 ;

Test bei: SQL-Fiddle

ypercubeᵀᴹ
quelle
Sehr elegante Lösung! Wahrscheinlich sehr schnell mit einem mehrspaltigen Index (spaces, day), vielleicht sogar einem abdeckenden Index (spaces, day, hotel_id, price).
Erwin Brandstetter
3
SELECT hotel, totprice
FROM   (
       SELECT r.hotel, SUM(r.pricepp)*@spacesd_needed AS totprice
       FROM   availability AS a
       JOIN   availability AS r 
              ON r.date BETWEEN a.date AND a.date + (@days_needed-1) 
              AND a.hotel = r.hotel
              AND r.spaces >= @spaces_needed
       WHERE  a.date BETWEEN '2014-01-01' AND '2014-01-31'
       GROUP BY a.date, a.hotel
       HAVING COUNT(*) >= @days_needed
       ) AS matches
ORDER BY totprice ASC
LIMIT 1;

Sie sollten das gewünschte Ergebnis erhalten, ohne zusätzliche Strukturen zu benötigen. Abhängig von der Größe der Eingabedaten, Ihrer Indexstruktur und der Helligkeit des Abfrageplaners kann die innere Abfrage jedoch zu einem Spool auf die Festplatte führen. Möglicherweise finden Sie es jedoch ausreichend effizient. Vorsichtsmaßnahme: Mein Fachwissen bezieht sich auf MS SQL Server und die Funktionen seines Abfrageplaners. Daher benötigt die obige Syntax möglicherweise zwei Wochen, wenn auch nur in Funktionsnamen (ypercube hat die Syntax so angepasst, dass sie jetzt vermutlich postgres-kompatibel ist, siehe Antwortverlauf für die TSQL-Variante) .

Die oben genannten finden Aufenthalte, die im Januar beginnen, aber bis in den Februar hinein andauern. Das Hinzufügen einer zusätzlichen Klausel zum Datumstest (oder das Anpassen des Enddatumswerts) kann dies problemlos beheben, wenn dies nicht erwünscht ist.

David Spillett
quelle
1

Unabhängig von HotelID können Sie eine Summiertabelle mit einer berechneten Spalte wie folgt verwenden:

SummingTable Rev3

Diese Tabelle enthält keine Primär- oder Fremdschlüssel, da sie nur zur schnellen Berechnung mehrerer Wertekombinationen verwendet wird. Wenn Sie mehr als einen berechneten Wert benötigen oder möchten, erstellen Sie eine neue Ansicht mit einem neuen Ansichtsnamen für jeden Monatswert in Kombination mit jedem der Personen- und Preis-PP-Werte:

PSEUDO-CODE-BEISPIEL

CREATE VIEW NightPeriods2People3DaysPricePP400 AS (
SELECT (DaysInverse - DaysOfMonth) AS NumOfDays, (NumberOfPeople * PricePP * NumOfDays) AS SummedColumn 
FROM SummingTable
WHERE NumberOfPeople = 2) AND (DaysInverse = 4) AND (DaysOfMonth = 1) AND (PricePP = 400)
)

SummedColumn = 2400

Zuletzt verbinden Sie die Ansicht mit der HotelID. Dazu müssen Sie eine Liste aller HotelIDs in SummingTable speichern (siehe oben), obwohl HotelID nicht zur Berechnung in der Ansicht verwendet wird. Gefällt mir So:

MEHR PSEUDO-CODE

SELECT HotelID, NumOfDays, SummedColumn AS Total
FROM NightPeriods2People3DaysPricePP400
INNER JOIN Hotels
ON SummingTable.HotelID = Hotels.HotelID
eyoung100
quelle