How do I efficiently get "the most recent corresponding row"?

Question

I have a query pattern that must be very common, but I don't know how to write an efficient query for it. I want to look up the rows of a table that correspond to "the most recent date not after" the rows of another table.

I have a table, inventory say, which represents the inventory I hold on a certain day.

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

and a table, "price" say, which holds the price of a good on a given day

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

How can I efficiently get the "most recent" price for each row of the inventory table, i.e.

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

I know one way of doing this:

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

and then join this query again to inventory. For large tables even doing the first query (without joining again to inventory) is very slow. However, the same problem is quickly solved if I simply use my programming language to issue one max(price.date) ... where price.date <= date_of_interest ... order by price.date desc limit 1 query for each date_of_interest from the inventory table, so I know there is no computational impediment. I would, however, prefer to solve the whole problem with a single SQL query, because it would allow me to do further SQL processing on the result of the query.

Is there a standard way to do this efficiently? It feels like it must come up often and that there should be a way to write a fast query for it.

I'm using Postgres, but an SQL-generic answer would be appreciated.

Answer 1

It very much depends on circumstances and exact requirements. Consider my comment.

Simple solution

With DISTINCT ON in 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;

Returned rows are ordered. See:

• Select first row in each GROUP BY group?

Or with NOT EXISTS in standard SQL (works with every RDBMS I know):

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 FROM price p1
   WHERE  p1.good = p.good
   AND    p1.the_date <= i.the_date
   AND    p1.the_date >  p.the_date
   );

Same result, but with arbitrary sort order - unless you add ORDER BY.
Depending on data distribution, exact requirements and indices, either one of these may be faster. See:

• How do I (or can I) SELECT DISTINCT on multiple columns?

With only few rows per good, DISTINCT ON is typically faster and you get a sorted result on top of it. But for certain cases other query techniques are (much) faster, yet. See below.

Solutions with subqueries to compute max / min values are typically slower. Variants with CTEs are generally slower, yet. (CTEs improved with Postgres 12.)

Plain views (like proposed by another answer) do not help performance at all in Postgres.

db<>fiddle here
_{Old sqlfiddle}

Proper solution

Strings and collation

First of all, your table layout is a sub-optimal. It may seem trivial, but normalizing your schema can go a long way.

Sorting by character types (text, varchar, ...) is done according to current COLLATION. Typically, your DB would use some local set of rules, like in my case: de_AT.UTF-8. Find out with:

SHOW lc_collate;

This makes sorting and index look-ups slower. The longer your strings (names of goods) the worse. If you do not actually care for collation rules in your output (or the sort order), this can be faster with 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;

Note the added collation in two places.
Twice as fast in my test with 20k rows each and very basic names ('good123').

Index

If your query is supposed to use an index, columns with character data have to use a matching collation (good in the example):

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

Read the last two chapters of the related answer I linked above.

You can even have multiple indexes with different collations on the same columns - if you also need goods sorted according to another (or the default) collation in other queries.

Normalize

Redundant strings (name of good) bloat tables and indexes, which makes everything slower. A proper table layout can avoid most of the problem. Could look like this:

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

The primary keys automatically provide (almost) all indices we need.
Depending on missing details, a multicolumn index on price with descending order on the second column may improve performance:

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

Again, the collation must match your query (see above).

Since Postgres 9.2 "covering indices" for index-only scans can help some more - especially if tables hold additional columns, making the table substantially bigger than the index.

These resulting queries are much faster:

DISTINCT ON

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;

NOT EXISTS

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

db<>fiddle here
_{OLD sqliddle}

Faster solutions

If that still is not fast enough, there may be faster solutions.

Recursive CTE / JOIN LATERAL / correlated subquery

Especially for data distributions with many prices per good:

• Optimize GROUP BY query to retrieve latest record per user

Materialized view

If you need to run this often and fast, I suggest you create a materialized view. I think it is safe to assume, that prices and inventories for past dates rarely change. Compute the result once and store a snapshot as materialized view.

Postgres 9.3+ has automated support for materialized views. You can easily implement a basic version in older versions.

Answer 2

As Erwin and others have noted, an efficient query depends on a lot of variables and PostgreSQL tries very hard to optimize query execution based on those variables. In general you want to write for clarity first and then modify for performance after as you identify bottlenecks.

Additionally PostgreSQL has a lot of tricks you can use to make things quite a bit more efficient (partial indexes for one) so depending on your read/write load, you might be able to optimize this very far by looking into careful indexing.

The first thing to try is just to do a view and join it:

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

This should perform well when doing something like:

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;

Then you can join that. The query will end up joining the view against the underlying table, but assuming you have a unique index on (date,good in that order), you should be good to go (since this will be a simple cache lookup). This will work very well with a few rows looked up but will be very inefficient if you are trying to digest millions of prices of goods.

The second thing you could do is add to the inventory table a most_recent bool column and

create unique index on inventory (good) where most_recent;

You would then want to use triggers to set most_recent to be false when a new row for a good was inserted. This adds more complexity and greater chances for bugs but it is helpful.

Again a lot of this depends on appropriate indexes being in place. For most recent date queries, you should probably have an index on date, and possible a multi-column one starting with date and including your join criteria.

Update Per Erwin's comment below, it looks like I misunderstood this. Re-reading the question I am not at all sure what is being asked. I want to mention in the update what is the potential problem I see and why this leaves this unclear.

The database design offered has no real use IME with ERP and accounting systems. It would work in a hypothetical perfect pricing model where everything sold on a given day of a given product has the same price. However this is not always the case. It isn't even the case for things like currency exchanges (although some models pretend that it does). If this is a contrived example, it is unclear. If it is a real example, there are bigger problems with the design on a data level. I am going to assume here that this is a real example.

You cannot assume that date alone specifies price for a given good. Prices in any business can be negotiated per counter-party and even sometimes per transaction. For this reason you really should store the price in the table that actually handles the inventory in or out (the inventory table). In such a case your date/goods/price table merely specifies a base price which may be subject to change based on negotiation. In such a case this problem goes from being a reporting problem to one which is transactional and operating on one row from each table at a time. For example, you could then look up the default price for a given product on a given day as:

 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;

With an index on prices (good, date) this will perform well.

I this is a contrived example, perhaps something closer to what you are working on would help.

Answer 3

FYI, I used mssql 2008, so Postgres won't have the "include" index. However, using the basic indexing shown below will change from hash joins to merge joins in Postgres: http://explain.depesz.com/s/eF6 (no index) http://explain.depesz.com/s/j9x (with index on join criteria)

I propose breaking your query into two parts. First, a view (not intended to improve performance) that can be used in a variety of other contexts that represents the relationship of inventory dates and pricing dates.

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;

Then your query can become simpler and easier to manipulate for other kinds if inquiry (such as using left joins to find inventory without recent pricing dates):

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

This yields the following execution plan: http://sqlfiddle.com/#!3/24f23/1

...All scans with a full sort. Notice performance cost of hash matches take up bulk of total cost... and we know that the table scans and sort are slow (compared to the goal: index seeks).

Now, add basic indexes to help the criteria used in your join (I make no claim these are optimal indexes, but they illustrate the point): http://sqlfiddle.com/#!3/5ec75/1

This shows improvement. The nested loop (inner join) operations no longer take up any relevant total cost for the query. The rest of the cost is now spread out among index seeks (a scan for inventory because we are pulling every inventory row). But we can do better still because the query pulls quantity and price. To get that data, after evaluating the join critera, lookups must be performed.

The final iteration uses "include" on the indexes to make it easy for the plan to slide over and get the additionally requested data right out of the index itself. So the lookups are gone: http://sqlfiddle.com/#!3/5f143/1

Now we have a query plan where the total cost of the query is spread evenly among very fast index seek operations. This will be close to as-good-as-it-gets. Surely other experts can improve this further, but the solution clears out a couple of major concerns:

1. It creates intelligible data structures in your database that are easier to compose and re-use in other areas of an application.
2. All of the most costly query operators have been factored out of the query plan using some basic indexing.

Answer 4

If you happen to have PostgreSQL 9.3 (released today) then you can use a LATERAL JOIN.

I have no way of testing this, and have never used it before, but from what I can tell from the documentation the syntax would be something like:

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;

This is basically equivalent of SQL-Server's APPLY, and there is a working example of this on SQL-Fiddle for demo purposes.

Answer 5

Another way would be to use window function lead() to get date range for every row in table price and then use between when joining inventory. I've actually used this in real life, but mainly because this was my first idea how to solve this.

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

Answer 6

Use a join from inventory to price with join conditions that limit the rec ords from the price tabelp to only those that are on or before the inventory date, then extract the max date, and where the date is the highest date from that subset

So for your inventory price:

 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)

If the price for any specified good changed more than once on the same day, and you really only have dates and no times in these columns, you may need to apply more restrictions on the joins to select only one of the price change records.