Efficient pagination of a SQL table with 100M records

If you need to do operations like this on a database with this setup I'd suggest checking out the following config options:

    1. max_heap_table_size
    2. read_buffer_size
    3. sort_buffer_size
    4. join_buffer_size
    5. thread_concurrency
    6. tmp_table_size

I have not included values in this because the values that make sense for you are likely not the values that make sense for me. Check out MySQL's documentation for what these values effect [0]. The defaults in even MySQL's huge config are very outdated for the horsepower that modern computers bring to the table. It's funny that MySQL's once massive 4GB of RAM config file is now the appropriate setup for my laptop.

[0] - https://dev.mysql.com/doc/refman/5.7/en/server-system-variab...

Write activity impacts database query caches. Many applications do not require realtime-accurate results from the database and generate a substantial number of the same paginated queries. For these cases, it is very important to consider higher-level caches within the system -- CDN, page-level caches, page block-level caches, etc. as caching your 99% traffic pattern will provide DB platform headroom to support your 1% traffic pattern.

Where the results you are paginating are based on any sort of matching (SQL WHERE), most read applications see a sizable benefit in integrating a search platform. Data selection for display is handled in the search layer, and underlying data retrieval for display happens either from the search layer or via the backing database using inexpensive lookups via primary key.

One of the key considerations not covered in the article is the need for result consistency when paginating, e.g. if the underlying data changes. It is the need for this consistency, not the desire for performance, that I see as the primary reason to include primary key identifiers or timestamp values in your pagination strategy.

I typed out the example queries below from memory, hopefully I haven't made any logic errors. Note:

a) Requires additional indexes to make it efficient.

b) Accounts for inserted and deleted rows.

c) You cannot use page numbers. You can only do first page, next and previous pages, and last page.

d) Example is for 20 items per page. The query pulls 21 (+1) items, so app can determine whether there is a next or previous page.

e) In a web app or api for example, your parameters get crazy, such as: /users?page=next&sort=name&sortId=20&sortVal=George

  -- first page
  SELECT name, id
  FROM users
  GROUP BY name, id
  ORDER BY name, id
  LIMIT 21;

  -- next page (ex: last item on current
  -- page has id 20 and name 'George')
  SELECT name, id
  FROM users
  WHERE name >= 'George' AND id > 20
  GROUP BY name, id
  ORDER BY name, id
  LIMIT 21;

  -- prev page (ex: first item on current
  -- page has id 21 and name 'Harry')
  SELECT name, id
  FROM users
  WHERE name <= 'Harry' AND id < 21
  GROUP BY name, id
  -- need DESC, reverse order in app for display
  ORDER BY name DESC, id DESC
  LIMIT 21;

  -- last page
  SELECT name, id
  FROM users
  GROUP BY name, id
  -- need DESC, reverse order in app for display
  ORDER BY name DESC, id DESC
  LIMIT 21;

"Five ways to paginate in Postgres, from the basic to the exotic"

https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin...

I'm leaning with @jerf that the LIMIT/OFFSET approach can trap you on the 100M record scale, however in all honesty, most of us don't deal with databases at this size. As @alvil stated, his approach works fine for 1M records, which is way more then most personal and application databases will contain.

Maybe the solution is for the database vendor to actually implement and document a definitive solution for this. Maybe re-engineering the LIMIT/OFFSET approach under the hood to take advantage of this new way.

As for the article... I really have a personal problem when authors get lazy and take the easy way out by assuming everyone knows what they are talking about. Take this portion of the article

========================

Simplified algorithm:

We get PAGE_SIZE number of records from the table. Starting offset value is 0.

Use the max returned value for user_id in the batch as the offset for the next page.

Get the next batch from the records which have user_id value higher than current offset.

========================

The author took the time to write an entire article debating and demonstrating their solution to the whole pagination problem and they couldn't take 5 minutes to show the code behind these steps in their solution?

As I stated, it's just a personal thing.

UPDATE: Down the internet rabbit hole I go. Here is a very nice article similarly demonstrating and debating the LIMIT/OFFSET approach in MSSQL between their OFFSET/FETCH and CTE.

https://sqlperformance.com/2015/01/t-sql-queries/pagination-...

What? Why? It should just instantiate a cursor and return the first batch size worth of records.

I’m not sure why the dB pulls load the entire result set into ram to return results unless it requires a sort on a non indexed field.

  > You need to walk thru the table,
  > extract each record,
  > transform it inside your application’s code
  > and insert to another place.

It looks like he's using MySQL. I've used PostgreSQL for over a decade, and I just don't see this happening, though I've tested only on a table with a few million rows. But anyway I doubt PostgreSQL loads the whole table into memory when you select it. It seems to load just parts at a time, as needed. And for what it's worth, an offset of a few million rows still took just a few seconds.

Actually what I would first try to is dump the table to a file, transform it if possible with Linux command-line tools like sed and awk, and then load the file into the new table.

Can anyone confirm if Postgres would die like MySQL did on too big a dataset --- selecting everything without paginating but fetching just one row at a time in the application?

  $items = db("SELECT a,b,c FROM item
           JOIN (SELECT id
              FROM item
              WHERE
              <your-where-conditions>
              ORDER BY id DESC
              LIMIT <offset>, <limit>)
              AS x ON
              x.id = item.id");