Is there a better way to reconstruct a data from hundreds of millions of entries spread over a long period of time?

Question

(first of all - apologies for the title but I couldn't come up with a better one)

Here is my problem - I have a table with 4 columns - entity::INT, entry::TEXT, state::INT and day::INT.

There could be anywhere from 50 to 1,000 entities. Each entity can have over 100 million entries. Each entry can have one or more states, which changes if the data stored in the entry has changed but only one state can be written for any particular day. The day starts at one and is incremented each day.

Example:

entity | entry  | state     | day
-------------------------------------
1      | ABC123 | 1         | 1
1      | ABC124 | 2         | 1
1      | ABC125 | 3         | 1
...
1      | ABC999 | 999       | 1
2      | BCD123 | 1000      | 1
...
1      | ABC123 | 1001      | 2
2      | BCD123 | 1002      | 3

The index is set to (entity, day, state).

What I want to achieve is to efficiently select the most current state of each entry on day N.

Currently, every week I write all the entries with their latest state to the table so to minimize the number of days that we need to scan, however, given the total number of entries (worst case scenario - 1,000 entities times 100,000,000 entries is a lot of rows to write each week) the table is slowly but surely bloats and everything becomes really slow.

I need to be able to stop writing this "full" version weekly and instead have a setup that will still be fast enough to achieve that. I considered to use DISTINCT ON with a different index set to (entity, entry, day DESC, state) so that I could:

SELECT DISTINCT ON (entity, entry) entry, state
FROM table
WHERE entity = <entity> AND day <= <day>
ORDER BY entity, entry, day DESC, state;

Would that be the most efficient way to do it or there are better ways? Or entry possibly having hundreds of millions of unique values makes it a poor choice for the second column in the index and the performance will eventually come to a halt?

Answer 1

You want to rank the entries by time an take the latest one. That's the same as ranking them in reverse time orse and taking the first one. And ROW_NUMBER() is one way to do that.

WITH
    ranked AS
(
    SELECT
        *, 
        ROW_NUMBER()
            OVER (
                PARTITION BY entity, entry
                    ORDER BY day DESC
            )
              AS entity_entry_rank
    FROM
        yourTable
)
SELECT
    *
FROM
     ranked
WHERE
    entity_entry_rank = 1

The day column can then become a timestamp, and you don't need to store a new copy every day.

The appropriate index would be (entity, entry, timestamp)

Also, it's common to have two tables. One with the history, one with the latest value. That makes use of the current value quicker, at a minor disk overhead.

(Apologies for errors or formating, I'm on my phone.)

Answer 2

DISTINCT ON is simple, and performance is great - for few rows per entry. See:

• Select first row in each GROUP BY group?

Not for many rows per entry, though.

Each entity can have over 100 million entries

See:

• Optimize GROUP BY query to retrieve latest row per user

Assuming an entry table that holds one row for each existing entry (each relevant distinct combination of (entity, entry)), this query is very efficient to get the latest state for a given day:

SELECT e.entity, e.entry, t.day, t.state
FROM   entry e
LEFT   JOIN LATERAL (
   SELECT day, state
   FROM   tbl
   WHERE  (entity, entry) = (e.entity, e.entry)
   AND    day <= <day>  -- given day
   ORDER  BY day DESC
   LIMIT  1
   ) t ON true;
ORDER  BY e.entity, e.entry; -- optional

Use CROSS JOIN LATERAL instead of the LEFT JOIN if you only want entries that have at least one row in tbl.

The perfect index for this is on (entity, entry, day) INCLUDE (state).

If you have no table entry, consider creating one. (Typically, there should be one.) The rCTE techniques outlined in the linked answer above can also be used to create such a table.