# How do I efficiently get “the most recent corresponding row”?

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.

-

## migrated from stackoverflow.comSep 9 '13 at 16:58

This question came from our site for professional and enthusiast programmers.

Voted to be migrated to DBA.SE as it's an efficiency question. We could write the query in a few different ways but that won't make it much faster. – ypercubeᵀᴹ Sep 9 '13 at 16:09
Do you actually need all goods for all days from a single query? Seems like an unlikely requirement? More commonly one would retrieve prices for a specific date or the price(s) for a specific good (at a specific date). Those alternative queries could much more easily benefit from (appropriate) indices. We also need to know: cardinalities (how many rows in each table?), the complete table definition incl. data types, constraints, indices, ... (use `\d tbl` in psql), your version of Postgres and min. / max. number of prices per good. – Erwin Brandstetter Sep 9 '13 at 20:00
@ErwinBrandstetter Are you asking me to accept an answer? I'm not really qualified to know which is best, though as yours has the most upvotes I'm happy to accept it. – Tom Ellis Sep 18 '15 at 18:05
Only accept if it answers your question or works for you. You might even leave a comment how you proceeded if that could help related cases. If you feel your question is unanswered, let us know. – Erwin Brandstetter Sep 18 '15 at 18:52
I have to apologise then, because although I have received what seem to be excellent answers I am no longer working on the problem that provoked the question so I'm in no place to judge which is the best answer, or if indeed any of them are really suitable for my use case (as it was). If there is some DBA.Stackexchange ettiquette I should follow in this case please let me know. – Tom Ellis Sep 27 '15 at 11:17

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

## 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;
``````

Ordered result.

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 1 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.
Generally, `DISTINCT ON` is the victor 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 generally slower. Variants with CTEs are generally slower, yet.

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

SQL Fiddle.

## Proper solution

### Strings and collation

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

Sorting by character types (`text`, `varchar`, ...) has to be done according to the locale - the COLLATION in particular. Most likely your DB uses 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 at all), this can be faster if you add `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 how I added the 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);``````

Be sure to read the last two chapters of this related answer on SO:

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) also bloat your tables and indexes, which makes everything even slower. With a proper table layout you could avoid most of the problem to begin with. 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).

In Postgres 9.2 or later "covering indices" for index-only scans could help some more - especially if your tables hold additional columns, making the table substantially bigger than the covering index.

These resulting queries are much faster:

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

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

SQL Fiddle.

## 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:

### 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.

-
The `price_good_date_desc_idx` index you recommend dramatically improved the performance for a similar query of mine. My query plan went from a cost of `42374.01..42374.86` down to `0.00..37.12`! – cimmanon Dec 11 '13 at 16:04
@cimmanon: Nice! What's your core query feature? NOT EXISTS? DISTINCT ON? GROUP BY? – Erwin Brandstetter Dec 12 '13 at 3:55
Using DISTINCT ON – cimmanon Dec 12 '13 at 14:18

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.

-

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.

-
The `most_recent` approach should work well for the most recent price absolutely. It would seem like the OP needs the most recent price relative to each inventory date, though. – Erwin Brandstetter Sep 10 '13 at 3:23
Good point. Re-reading though I spot some real practical deficiencies with the proposed data but I can't tell if it is just a contrived example. As a contrived example, I can't tell what is missing. Maybe an update to point this out would be in order too. – Chris Travers Sep 10 '13 at 5:05
@ChrisTravers: It is a contrived example, but I'm not at liberty to post the actual schema that I am working with. Perhaps you could say a little bit about what practical deficiencies you have spotted. – Tom Ellis Sep 11 '13 at 16:35
I dont think it needs to be exact, but worried about the problem being lost in the allegory. Something a little closer would be helpful. The issue is that with pricing, the price at a certain day is likely to be a default, and consequently you wouldn't use it for reporting only as a default for transaction entry, so your interesting queries are typically only a few rows at a time. – Chris Travers Sep 12 '13 at 7:56

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.
-
This is fine (for SQL-Server) but optimizing for different DBMS while it has similarities, it has serious differences as well. – ypercubeᵀᴹ Sep 9 '13 at 17:28
@ypercube that is true. I added some qualifications about Postgres. My intention was that most of the thought process illustrated here would apply regardless of DBMS specific features. – cocogorilla Sep 9 '13 at 18:13
The answer is very in depth, so it will take me some time to try it out. I shall let you know how I get on. – Tom Ellis Sep 10 '13 at 12:46

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

-

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

`````` 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.

-
Doesn't seem to speed things up, unfortunately. – Tom Ellis Sep 9 '13 at 15:50