Better database for "keep always the 5 latest entries per ID and delete older"?

Question

I have a PostgreSQL database with a history table where I store an fooID (not a primary key serial but a text), an attribute target and the current timestamp whenever the target for this fooID changes:

CREATE TABLE history (
  fooId       text not null,
  target      text not null,
  updated_at  timestamp not null default default now()
);

There are several million entries in this table and a couple of thousand changes per day. Every day I will scan the table and keep the last 5 entries per fooId and delete any older entries.

The DELETE ... WHERE id in ... rank() over (partiton by nr order by created_at... query is not my question, that works. Just takes awful long.

My question is rather: Is a standard PostgreSQL table the best approach for this problem?

Would PostgreSQL table partitioning help here? I know partitioning is used to easily throw away big chunks of data that are older than X days, but partitioning by fooId would seem to create too many partitions in my case.

Are there NoSQL databases that would be much faster because they store the data differently?

Are there other PostgreSQL tricks that help me to store the data differently and more optimized for the use case of the daily purging (SELECTs are not an issue, it gets rarely queried)?

An exclusive lock for an 1 hour per week would be acceptable. There are about 1 million different fooIDs so no chance of having a separate table per fooID.

Answer 1

One option I can think of is to delete the oldest row as soon as you insert a new one. That will only require a very quick lookup limited to at most 6 rows rather then going through all rows at a time.

To do that efficiently you need a unique key on the table:

create table history 
(
  id          serial primary key, -- to make a lookup on a single row efficient
  fooid       text not null,
  target      text not null,
  updated_at  timestamp not null default now()
);
-- to make finding the oldest row for one fooid efficient
create index on history(fooid, updated_at);

Then create a trigger that only keeps the 5 most recent rows for a fooid:

create or replace function remove_last() 
  returns trigger
as
$$
begin
  with ranked as (
    select id, row_number() over (partition by fooid order by updated_at) as rn
    from history
    where id <> new.id
      and fooid = new.fooid 
  )
  delete from history
  where id in (select id 
               from ranked 
               where rn >= 5);
  return new;
end;
$$
language plpgsql;

create trigger remove_last_trigger 
  after insert on history
  for each row execute procedure remove_last();

On my laptop, a simple test setup with 5 million rows (1 million different fooid values) showed a trigger overhead that was less then a millisecond:

insert into history (fooid, target) values ('1', 'new stuff');

QUERY PLAN                                                                                          
----------------------------------------------------------------------------------------------------
Insert on stuff.history  (cost=0.00..0.01 rows=1 width=76) (actual time=0.062..0.062 rows=0 loops=1)
  Buffers: shared hit=8                                                                             
  ->  Result  (cost=0.00..0.01 rows=1 width=76) (actual time=0.017..0.017 rows=1 loops=1)           
        Output: nextval('history_id_seq'::regclass), '1'::text, 'new stuff'::text, now()            
        Buffers: shared hit=1                                                                       
Planning time: 0.024 ms                                                                             
Trigger remove_last_trigger: time=0.438 calls=1
Execution time: 0.524 ms

How much overhead that is in your system and whether or not that is acceptable for you I don't know, but "thousand changes per day" doesn't sound like a very busy system.

Answer 2

The important information is this:

There are several million entries in this table and a couple of thousand changes per day.

And:

SELECTs are not an issue, it gets rarely queried.

What matters is write performance. For daily maintenance, only a very small percentage of old rows has to be considered if we can keep new additions separate - while still allowing convenient access to the whole table. Add the right index to the table of old entries, and this is very fast. You wrote:

Would PostgreSQL table partitioning help here? I know partitioning is used to easily throw away big chunks of data that are older than X days, but partitioning by fooId would seem to create too many partitions in my case.

I think you were on the right track with table partitioning. Especially since one of the major features of Postgres 10 (to be released soon) is a new partitioning system. The release notes:

Add table partitioning syntax that automatically creates partition constraints and handles routing of tuple insertions and updates (Amit Langote).

Details in the manual for Postgres 10:

• https://www.postgresql.org/docs/10/static/ddl-partitioning.html#ddl-partitioning-declarative

So don't bother with Postgres 9.6 and start with Postgres 10 right away.

Setup

 CREATE TABLE history (  -- partition parent
   fooid      text      NOT NULL,
   target     text      NOT NULL,
   updated_at timestamp NOT NULL DEFAULT now()
 )
 PARTITION BY RANGE (updated_at);

 CREATE TABLE history_past
    PARTITION OF history FOR VALUES FROM (MINVALUE)         TO ('2017-09-15 0:0');  -- partition for timestamps before 2017-09-15 ("past")
 CREATE TABLE history_20170915
    PARTITION OF history FOR VALUES FROM ('2017-09-15 0:0') TO ('2017-09-16 0:0');  -- partition 2017-09-15 ("today");
 CREATE TABLE history_20170916
    PARTITION OF history FOR VALUES FROM ('2017-09-16 0:0') TO ('2017-09-17 0:0');  -- partition 2017-09-16 ("tomorrow");
 -- more daily tables ahead of time ...

Just keep inserting into history. Rows end up in the appropriate partition automatically. The only index you need to make the daily consolidation fast:

CREATE INDEX history_past_fooid_updated_at_idx ON history_past (fooid, updated_at);

Index maintenance does not affect write performance at all since new rows end up in the partition of "today" without any index - as fast as can be.

Daily consolidation

Run once per day at hours of low traffic. Best with a cron job or pgagent:

 -- trim excess from new day (rare case!)
 DELETE FROM history_20170915 h
 USING (
    SELECT fooid, updated_at
         , row_number() OVER (PARTITION BY fooid ORDER BY updated_at DESC) AS rn
    FROM   history_past
    ) d
 WHERE  d.fooid = h.fooid
 AND    d.updated_at = h.updated_at
 AND    d.rn > 5;

 -- trim excess from past to make room for new rows
 DELETE FROM history_past h
 USING (
    SELECT fooid, updated_at, new_rows
         , row_number() OVER (PARTITION BY fooid ORDER BY updated_at DESC) AS rn
    FROM   (SELECT fooid, count(*) AS new_rows FROM history_20170915 GROUP BY 1) ct
    JOIN   history_past p USING (fooid)  -- only consider few where rows were added
    ) d
 WHERE  d.fooid = h.fooid
 AND    d.updated_at = h.updated_at
 AND    d.rn + d.new_rows > 5;

 ALTER TABLE history DETACH PARTITION history_past;

 INSERT INTO history_past   -- identical structure guaranteed
 TABLE   history_20170915;  -- short syntax

 DROP TABLE history_20170915;

 ALTER TABLE history ATTACH PARTITION history_past
 FOR VALUES FROM (MINVALUE) TO ('2017-09-16 0:0');  -- "yesterday" added to the past

dbfiddle here

Replace all history_20170915 with yesterday's table and adapt the date for history_past accordingly.

Create partitions for the next month or so ahead of time to be sure. The daily cron job also checks and adds partitions to keep the buffer at one month.

A trigger solution like @a_horse provided is fast for each single entry, but the cost sums up for thousands of daily entries. You also need to factor in index maintenance.

And to see the complete history you can still just:

SELECT * FROM history WHERE fooid = 'foo';