Store millions of rows of denomalized data or some SQL magic?

Question

My DBA experience doesn't go much further than simple storage + retrieval of CMS style data - so this may be a silly question, I don't know!

I have a problem whereby I need to lookup or calculate holiday prices for a certain group size and a certain number of days within a certain time period. E.g.:

How much is a hotel room for 2 people for 4 nights anytime in January?

I have pricing and availability data for, say, 5000 hotels stored like so:

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

With this table, I can do a query like so:

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;

results

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

The HAVING clause here makes sure that there is an entry for every single day between my desired dates that has the spaces available. ie. Hotel 456 had 1 space available on Jan2, the HAVING clause would return 3, so we don't get a result for hotel 456.

So far so good.

However, is there a way to find out all the 4 night periods in January where there is space available? We could repeat the query 27 times - incrementing the dates each time, which does seem a little bit awkward. Or another way around could be to store all possible combinations in a lookup table like so:

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

And so on. We'd have to limit max number of nights, and the max number of people we would search for - e.g. max nights = 28, max people = 10 (limited to the number of spaces available for that set period starting on that date).

For one hotel, this could give us 28*10*365=102000 outcomes per year. 5000 hotels = 500m outcomes!

But we'd have a very simple query to find the cheapest 4 night stay in Jan for 2 people:

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;

Is there a way to perform this query on the initial table without having to generate the 500m row lookup table!? e.g. generate the 27 possible outcomes in a temporary table or some other such inner query magic?

At the moment all data is held in a Postgres DB - if needs be for this purpose we can move the data out to something else more suitable? Not sure if this type of query fits the map/reduce patterns for NoSQL style DBs ...

Answer 1

You can do much with window functions. Presenting two solutions: one with and one without materialized view.

Test case

Building on this table:

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

Days per hotel_id must be unique (enforced by PK here), or the rest is invalid.

Multicolumn index for base table:

CREATE INDEX mv_hotel_mult_idx ON mv_hotel (day, hotel_id);

Note the reversed order as compared to the PK. You will probably need both indexes, for the following query, the 2nd index is essential. Detailed explanation:

• Is a composite index also good for queries on the first field?
• Working of indexes in PostgreSQL

Direct query without 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;

Also see @ypercube's variant with lag(), which can replace day_ct and day_diff with a single check.

How?

• In the subquery, only consider days within your time frame ("in January" means, the last day is included in the time frame).

• The frame for the window functions spans the current row plus the next num_nights - 1 (4 - 1 = 3) rows (days). Calculate the difference in days , the count of rows and the minimum of spaces to make sure the range is long enough, gapless and always has enough spaces.

  • Unfortunately, the frame clause of window functions does not accept dynamic values, so ROWS BETWEEN CURRENT ROW AND 3 FOLLOWING` cannot be parameterized for a prepared statement.

• I carefully drafted all window functions in the subquery to reuse the same window, using a single sort step.

• The resulting price sum_price is already multiplied by the number of spaces requested.

With MATERIALIZED VIEW

To avoid inspecting many rows without chance of success, save only the columns you need plus three redundant, calculated values from the base table. Be sure the MV is up to date. If you are not familiar with the concept, read the manual first.

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 stores the first day of each continuous range for two purposes:

  • to mark a set of rows as members of a common range
  • to show the start of the range for possible other purposes.

• range_len is the number of days in the gapless range.
  max_spaces is the maximum of open spaces in the range.

  • Both columns are used to exclude impossible rows from the query immediately.

• I cast both to smallint ( max. 32768 should be plenty for both) to optimize storage: only 52 bytes per row (incl. heap tuple header and item identifier). Details:

  • Configuring PostgreSQL for read performance

Multicolumn index for MV:

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

Query based on 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;

This is faster than the query on the table because more rows can be eliminated immediately. Again, the index is essential. Since partitions are gapless here, checking day_ct is enough.

SQL Fiddle demonstrating both.

Repeated use

If you use it a lot, I would create an SQL function and only pass parameters. Or a PL/pgSQL function with dynamic SQL and EXECUTE to allow adapting the frame clause.

Alternative

Range types with date_range to store continuous ranges in a single row might be an alternative - complicated in your case with potential variations on prices or spaces per day.

Related:

• Find available apartments given a date range, a duration, and a list of unavailable dates
• Native way of performing this hours of operation query in PostgreSQL

Answer 2

Another way, using the LAG() function:

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 at: SQL-Fiddle

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

should get you the result you are looking for without needing extra structures, though depending on the size of the input data, your index structure, and how bright the query planner is the inner query may result in a spool to disk. You may find it sufficiently efficient though. Caveat: my expertise is with MS SQL Server and its query planner's capabilities, so the above syntax may need tweeks if only in function names _{^{(ypercube has adjusted the syntax so it is presumably postgres compatible now, see answer history for TSQL variant)}}.

The above will find stays that start in January but continue on into February. Adding an extra clause to the date test (or adjusting the end date value going in) will easily deal with that if it is not desirable.

Answer 4

Regardless of HotelID, you could use a summing table, with a calculated column, like so:

There are no Primary or Foreign Keys in this table, as it is only used to quickly calculate multiple combinations of Values. If you need or want more than one calculated value, create a new view with a new view name for each of the month values in combination with each of the People and Price PP Values:

PSEUDO CODE EXAMPLE

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

Lastly, Join the View to the HotelID. To do that you will need to Store a list of all HotelID's in SummingTable(I Did in the Table Above), even though HotelID isn't used to calculate in the View. Like So:

MORE PSEUDO CODE

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