SQLite Pagination

A few notes on how basic pagination should work. Never mind the fact that it rarely does!

• sequential ID
• random number 0-999
• category: 0, 1, or 2
• random string up to 256 characters long
• random datetime between the beginning of the century and today

create table samples
(
    id integer primary key,
    facility integer not null,
    category integer not null,
    data text not null,
    time datetime not null
);

insert into samples(facility, category, data, time)
select abs(random() % 1000),
       abs(random()) % 3,
       hex(randomblob(random() % 128)),
       datetime(strftime('%s', '2000-01-01 00:00:00') +
                abs(random() % (strftime('%s', '2022-07-23 23:59:59') -
                                strftime('%s', '2000-01-01 00:00:00'))),
                'unixepoch')
  from generate_series(0)
 limit 1000000;

This results in about 400 megabytes of data for me which should be sufficient to test out some ideas without making it too easy on myself.

My first idea is of the kind of time series dashboard that allows for drilling into a given facet of the data. In the example here there might be a table of "facilities" with an aggregation of recent data for each. In my experience everyone makes the table first return all data at once, whether or not things are paginated client-side and only later when it becomes an obvious performance problem is any consideration given to adding pagination to the queries themselves.

Imagine a simple table:

Sometimes "readings" is instead a sparkline plot but the idea is pretty general. This works in development but falls apart when there are 100 facilities or 1000 readings.

For the generated example data there are 1000 facilities each with between 907 and 1089 pieces of data. In my particular case I created random data rather than drumming up something like fake structured data — it seemed more realistic than a single integer, given my past experience. It also ensures that the tuples aren't all neatly aligned along the same field size boundary. I'm not sure this is entirely necessary but it can't hurt to give the database a little more work.

If I had a time series chart with time along the x-axis and each point representing a measurement or reading for a given facility it may be easy to see why select * from samples doesn't scale:

Instead the idea is to subdivide the full dataset in an intuitive way that could easily map to the table show above. I imagine a frame like you might use for photography or painting that limits what you "see".

Some aspects of this are easier than others, I imagine it is obvious how you might do:

select facility, data
  from samples
 where facility in (0, 1, 2);

Which achieves the "vertical" selection part of the above. The "horizontal" part could be achieved with a date range query:

select facility, data
  from samples
 where facility in (1, 2)
   and time between '2006-01-01 00:00:00' and '2008-01-01 00:00:00'

Of course things get marginally more complicated if the sort order is configurable but it doesn't exactly ruin our day. With just these it is possible to (conceptually) slide the frame around the data while keeping responses small and fast. The pages of a table might drive the inputs to the where clauses.

The thing that got me thinking about this in the first place though was how best to achieve a query like "last 50 readings no older than a week per facility". This kind of question doesn't exactly lend itself to the visual given above, at best I guess I imagine it like:

This sort of thing requires the use of a window function, which allow you to limit an aggregation within a given partition. In my example the partition would be facility and the aggregation could be something like group_concat, max, or json_group_array. Let's start with a query that works but returns too much data:

  select facility,
         json_group_array(time)
    from samples
group by facility

For the full data set I generated at the beginning, this returns over 20MB of data. I might trim it down to just 10 facilities, which brings the total size down to about 216KB — but only for now! How about 10 facilities and only in the last 3 years?

  select facility,
         time
    from samples
   where facility < 10
     and time > date('now', '-3 years')

While that gets down to about 30KB it is also a bit fragile to my point of view. What I would like instead is a maximum upper bound on the number of readings on top of which I might add further limits rather than the other way around. Here is where window functions come in, I happen to know that there is a pretty even distribution of records per facility (because with enough random data packed into a fixed number of buckets the distribution becomes uniform). I would expect then that taking ¹/₁₀ of the number of readings (100 of ~1000) should produce an equivalent fraction of data:

select facility,
       time
  from (
    select row_number() over (partition by facility order by time desc) seqnum,
           facility,
           time
      from samples
) where seqnum <=100

As expected, this produces about 2.5MB of data. It works by segmenting the table by facility before numbering each record per-partition in order of time. A small sample of the nested query looks like this:

Circling back to the first example table, if I were going to design for more realistic data sizes I might do something like this:

  select facility, max(time) [last reading], json_group_array(time) [reading dates]
    from (
        select row_number() over (partition by facility order by time desc) seqnum,
               facility,
               time
          from samples
)
   where seqnum <= 10
     and facility <= 10
group by facility;

Thoughts

Considering the variety of ways I have seen these sorts of things done incorrectly I didn't find any of this particularly novel. Admittedly, requesting large amounts of data is always going to be a little slow but for the example above I can aggregate 100 readings for 1000 facilities (never mind the fact that one hundred thousand points of data probably don't have any business being on a single page in the first place) in 1.29 seconds without any optimization. With indexes you can then dive into any given reading by date in thousandths of a second. There's vanishingly little reason applications should be slow! There are a few more options in other databases that allow fetching along with offset without incurring the performance hit described in the SQLite docs. The SQLIte documentation also gives an interesting suggestion for using a compound row-value comparison in order to implement pagination without the same limitations I face with my own approach here.