2

My end goal is to create pagination and I'm wondering if there's a better or correct way to do things.

Given a Table with multiple columns for sorting, as in ORDER BY s1, s2, s3 I want to get the next n records after a given record. It's assumed that I know the full record including it's values for s1, s2, s3.

What I came up with so far looks like this:

-- Given current entry (prefixed with e_), get next n records

SELECT * FROM Entries
  WHERE
    (s1 < e_s1) OR
    (s1 = e_s1 AND s2 < e_s2) OR
    (s1 = e_s1 AND s2 = e_s2 AND s3 < e_s3)
  ORDER BY s1, s2, s3
  LIMIT n;

While I did create an index over (s1, s2, s3) I feel that this is not the most efficient or elegant way to do this. The query also gets bloated the more sort keys there are. Even so, this query is easy to adapt to look backwards, which I also need to be able to do.

I don't have access to the current offset of the record and I fear that it might be more inefficient to go by that way since I have to calculate it by using a subquery and aggregation (window functions are not available on my platform since it's android).

Is there a better/more elegant/efficient way of querying the data?

Here's an SQL Fiddle with some sample data

Important for anyone using this method: You should always have a unique column as the last column in the ordering and comparing plus the corresponding index. This makes the index perform better and also provides the necessary tie-breaking when you have two equal rows.

This of course is not necessary when there's a unique constraint on the combination of your columns [i.e. there's an unique index on (s1, s2, s3)]

JensV
  • 3,997
  • 2
  • 19
  • 43
  • Of its for pagination, how come you don't know the offset? – MatBailie Dec 24 '20 at 00:23
  • 1
    It may not be the most elegant, but your method is the efficient method. Using `OFFSET` is not efficient. Have a look at [Pagination Done the Right Way](https://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way) The only thing - make sure that your supporting index is unique. If it is not unique right now, add some `id` to it (and to the `WHERE` part of the query) to make the search repeatable. – Vladimir Baranov Dec 24 '20 at 07:48
  • @MatBailie I need to be able to start at a specific item and scroll back and forth relative to that. Synchronization of that also happens in the background which means arbitrary items may get removed which changes the index of items. (I will manually invalidate ranges of data to account for changes in the currently visible page). I know it's possible to calculate the current index of an item, but that query needs to scan through until it finds the current item and is thus inefficient. – JensV Dec 25 '20 at 12:29
  • 1
    Thanks @VladimirBaranov! that outlined my plan pretty clearly with the indexes and even had some details which I wouldn't have thought about. Thank you very much! – JensV Dec 25 '20 at 12:38
  • I'm on my phone so this is a comment rather than an answer. Perhaps you can use `rowid`? *(Assumes `PRIMARY KEY (S1, S2, S3)`, that you're not using `WITHOUT ROWID`, and you VACUUM after INSERT or UPDATE that would put your table out of order, as VACUUM will then rebuild the `ROWID`.)* Then perhaps you can use `SELECT rowid, * FROM entries WHERE rowid < $current_first_rowid ORDER BY rowid LIMIT n` to go back a page? Or use `SELECT rowid FROM entries WHERE S1=$S1 AND S2=$S2 AND S3=$S3` to find a starting row? (Perhaps as a sub query?) – MatBailie Dec 25 '20 at 22:07

2 Answers2

1

SQLite supports tuple comparison, so you can do:

SELECT * 
FROM Entries
WHERE (s1, s2, s3) < (29, 30, 30)
ORDER BY s1, s2, s3
LIMIT 5;
GMB
  • 216,147
  • 25
  • 84
  • 135
  • 1
    Sadly, I have to support Android SDK 21 which apparently ships with SQLite 3.8.6. And the so called *row value comparison* was introduced in 3.15.0 – JensV Dec 17 '20 at 17:27
0

Much better way would be using OFFEST with the LIMIT and then no need to put any conditions in the WHERE. Every page you retrieve, you just need to remember the offset (or give back to user as "next token"). The offset of course starts from 0. Every call to a page you increase (or decrease if you want to go backwards) the offset by n.

Like this:

SELECT * FROM Entries
  ORDER BY s1, s2, s3
  LIMIT n OFFSET offset

Note1: the syntax of the limit could also be written: LIMIT {offset},{limit}.

Note2: the ORDER BY must be unique, to make sure we always get same entry at same offset.

https://www.sqlite.org/lang_select.html#limitoffset

If you do NOT want to use the offset, you can concat with padding all indexes and do one comparison. This looks more elegant:

SELECT * FROM Entries
  WHERE 
     PRINTF('%04d%04d%04d',s1,s2,s3) < PRINTF('%04d%04d%04d',29,30,30)
  ORDER BY s1, s2, s3
  LIMIT 5;

The simple padding was taken from here.

Chananel P
  • 1,704
  • 1
  • 18
  • 19
  • Thanks for the input. The first solution is a possibility although less efficient outlined in the question and verified by Vladimirs linked article. The second solution is infeasible since that cannot be indexed afaik. – JensV Dec 25 '20 at 12:41
  • 1
    @JensV, actually, the second suggestion can lead to the most elegant and efficient method **IF** your RDBMS supports indexes over the calculated column. In SQL Server it is called "persisted calculated column" and can be indexed. I don't know if SQLite has anything like that. In essence, you create a single calculated column that concatenates your `s1, s2, s3, id` columns as a long binary (or text) string, index that calculated column, then use that in the `WHERE` part. In this case the `WHERE` part would be simple `<` or `>=`. – Vladimir Baranov Dec 25 '20 at 12:54
  • @VladimirBaranov actually just double checked, and SQLite does support [Indexes On Expressions](https://sqlite.org/expridx.html) but only for SQLite version >= 3.9.0 :| It does feel like working around the missing tuple comparisons which basically do the same thing. – JensV Dec 25 '20 at 13:06
  • 1
    @JensV, yes, exactly. It is a work-around if RDBMS doesn't support tuple comparison. – Vladimir Baranov Dec 25 '20 at 13:09