12

For a large dataset, paginating with an OFFSET is known to be slow and not the best way to paginate. A much better way to paginate is with a cursor, which is just a unique identifier on the row so we know where to continue paginating from where we last left off from the last cursor position.

When it comes to a cursor where it is an auto incrementing id value, it's fairly easily to implement:

SELECT * FROM users
WHERE id <= %cursor // cursor is the auto incrementing id, ex. 100000
ORDER BY id DESC
LIMIT %limit

What we're not certain about, is if instead of an auto incrementing id cursor, the only unique sequential identifiers for the cursor are uuid and created_at on the table rows.

We can certainly query based on the uuid to get the created_at, and then select all users that are <= created_at but the issue is what if there are multiple instances of the same created_at timestamp in the users table? Any idea how to query the userstable based on uuid/created_at cursor combination to ensure we get the correct datasets (just as if we were using auto incrementing id)? Again, the only unique field is uuid since created_at may be duplicate, but their combination would be unique per row.

2
  • Your first paragraph is a nice explanation of why to use a 'cursor' instead of OFFSET. However it leaves out the bugs of skipping or duplicating rows as the user moves to the next page while rows are being inserted/deleted. (That also argues against OFFSET.)
    – Rick James
    May 15, 2018 at 20:14
  • Do you want to paginate on chronological order? If so, is it created order? or Updated order? Or do you not care what order?
    – Rick James
    Feb 15 at 6:34

2 Answers 2

6

I will answer what you asked, but first let me tell you that I don't understand why you want to do that. An autoincremental id is very good for this task. But it is correct to also use a timestamp column, because it is a bad practice to rely on an id for sorting. Why? Because there are cases when its order might not be chronological - for example, if you use Galera cluster and you have failovers.

To do what you asked, first create this index:

ALTER TABLE users
    ADD INDEX idx_created_at_uuid (created_at, uuid);

The order columns is important. If you reverse it, the index will not be useful.

Now you just need to run a query like this:

SELECT some_columns
    FROM users
    WHERE (created_at, uuid) < (x, y)
    ORDER BY created_at DESC;

uuid is only needed because created_at is not unique. The expression above uses a syntax known as row constructors. It is intuitive: it's the same as created_at < x, unless these values are equal, in which case it compares uuidandy`.

If created_at is not the first column in the index, MySQL will have to read all rows and copy them to a temporary table (which could be in-memory or on-disk) to sort them.

If you decide to use the id, just keep the above snippets, but replace uuid with id.

EDIT 16 Nov 22: The WHERE clause was incorrect. I fixed it and I explained the syntax.

13
  • 1
    Thank you for your answer, I will certainly try and use the auto incrementing id instead as it seems to be much better, but will keep this for reference.
    – Wonka
    Apr 30, 2018 at 19:39
  • 1
    Good. Note that I edited the answer, because there was a mistake in my query. Apr 30, 2018 at 20:14
  • 1
    @FedericoRazzoli - Your inequality test is inadequate. See my answer for a fix.
    – Rick James
    May 15, 2018 at 20:12
  • how to create a request to "back" action? Thanks.
    – lexa
    Dec 24, 2020 at 12:19
  • @FedericoRazzoli Is the query actually correct now? Please explain. Only uuid type 1 and 2 contains temporal part. Assume, that you processed half of 100 elements at given timestamp, and know that last uuid is type 4, random: 956ce1fb-066f-40a0-86bf-6de21d8023d2. If < comparison works, it probably yields random results. The uuid you hold does not anyhow identify which rows were processed and which not. No? Feb 21, 2023 at 16:43
12
WHERE   created_at <= x
  AND ( created_at < x OR uuid < y )
ORDER BY created_at DESC,
         uuid       DESC

or this equivalent:

WHERE (     created_at < x
       OR ( created_at = x AND uuid < y )
      )
ORDER BY created_at DESC,
         uuid       DESC

This technique works for any pair of columns where the first one (created_at) could have duplicates and the second is unique (uuid or id).

And this is required:

INDEX(created_at, uuid)

Note that both parts of the WHERE are DESC. Mixing ASC and DESC will defeat the usability of the INDEX. (MySQL 8.0 can work around that.)

Note also, that this assumes you don't care what order the rows are in when created_at is duplicated, but you do want a consistent ordering. Note that uuid will be seemingly random, but still consistent. With that said, id (with or without Galera) and uuid work equally well.

(UUIDs suck, but that is a different discussion.)

Remember where you left

More on pagination without using OFFSET .

In your case, that is the combination of created_at and whatever the PRIMARY KEY is. The former gives the desired ordering; the latter handles what to do in the case of dup dates.

This technique further optimizes things:

PRIMARY KEY(create_at, id), -- or (created_at, UUID)
INDEX(id)                   -- or (UUID)
11
  • 1
    I think in equivalent there should be WHERE created_at < x OR (created_at = x AND uuid < y)
    – Yavin
    May 14, 2020 at 7:52
  • @Yavin - Thanks! (Geez -- 2 years and 4 upvotes before someone points out an error.) I fixed it.
    – Rick James
    May 14, 2020 at 16:33
  • As a SQL noob, I love the content and format of your answer and especially your blog post. Question: would you pass only the uuid around (to/from client), and not the created_at/non-unique column since it could change? So query would be SET @created_at = (SELECT created_at FROM users WHERE uuid=x); SELECT * FROM users WHERE created_at <= @created_at AND (created_at < @created_at OR uuid < y) ORDER BY created_at DESC, uuid DESC LIMIT page_size+1;
    – onepiece
    Feb 14 at 9:06
  • Also a question related to UUID_TO_BIN: it notes This moves the more rapidly varying part to the right and can improve indexing efficiency if the result is stored in an indexed column. How does reducing variance on the left increase index efficiency? This is basically asking the basics of indexing but I'm imagining the index as a prefix tree: high variance on the left means more keys (chars) to search through in the beginning (in earlier levels of tree), which takes longer.
    – onepiece
    Feb 14 at 9:13
  • @onepiece - If (and only if) you usually access rows that are "hear" each other in time, the bit rearrangement "clusters" such rows together for more efficient access (less I/O, less cache space used, etc). See my old discussion of UUIDs
    – Rick James
    Feb 14 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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