Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

[EDIT: I'm using Postgres, but an SQL-generic answer would be appreciated]

share|improve this question

migrated from stackoverflow.com Sep 9 '13 at 16:58

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

3  
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
3  
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

6 Answers 6

It very much depends on the 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.
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.

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

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 solutons

Recursive CTE / JOIN LATERAL / Correlated subquery

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 it in a materialized view.

Postgres 9.3 offers automated support for materialized views. But you can easily implement it manually in older versions.

share|improve this answer
1  
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.

share|improve this answer

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 no indexing

...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 with basic indexing

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 enter image description here

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.
share|improve this answer
3  
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

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.

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer
    
Doesn't seem to speed things up, unfortunately. –  Tom Ellis Sep 9 '13 at 15:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.