-2

Today I realized another fascinating thing about sql databases: They don't do paging well at all.

By paging I mean selecting a slice of data defined by a starting record number and a record count according to an order one has an index on - this operation is used by user interface grids with pagers or scrollbars with lazy loading.

In my case, I noticed how the beginning of the data in my grid the ui was very responsive, but lower down the data it became sluggish. That was with Sql Server.

I checked the execution plan, and it was reading the data through an index in the correct order, but for the data lower down it would still need to scan through all the previous data to get the correct starting row.

Now that I think about it, it's fairly obvious: Efficient seeking is usually supported by a search key, not by record number.

However, it doesn't have to be that way. It very much depends on how the underlying data structure of the respective database engine is implemented. Traditional b-trees can not efficiently find a record by number, but a variant of it can: The tree would have to store the number of all records in the whole respective subtree for each node. That way, even a lookup by row number can be served in logarithmic time.

With such an implementation, paging could always be efficient.

I'm wondering which database engines have that feature, if any - which is why the question is tagged with various different sql database engine tags.

Do you know what your favorite database does on paging? Does it do a scan or can it indeed seek by record number?

closed as too broad by a_horse_with_no_name, James Anderson, Philᵀᴹ, mustaccio, Tom V Aug 31 '16 at 19:49

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    In SQL databases records do not have "numbers", because they do not have any intrinsic order. – mustaccio Aug 30 '16 at 12:07
  • @Einstein But indexes and result sets have an order. – John Aug 30 '16 at 12:08
  • 1
    There are ways to make pagination more efficient. In your code, you didn't show it but I'm guessing, you are probably reading in all of the wide rows from row 1 right through to the last page, and then lopping the first 99%. See sqlperformance.com/2015/01/t-sql-queries/… - of course if your filters don't have supporting indexes (or can't use indexes anyway, such as lastname like '%s%'), the pagination part is just a small part of the problem. – Aaron Bertrand Aug 30 '16 at 12:49
  • Few comments - pagination is sick by definition, unless to use serializable isolation level, it does not guarantee consistent output between executions. Some b-tree indexes even do not support delete, nothing in the world is for free, and storing additional information in branch block would pop-up somewhere else as un-necessary burder to the database. Except for web pages you practically never need pagination queries. Pagination queries are not a must, we use them only because application servers can not keep ResultSet open between page clicks. – ibre5041 Aug 30 '16 at 12:50
  • 1
    @John imagine you display records 1-5, then 6-10, meantime somebody deletes or inserts rows on position 1-10. Then application requests rows 11-15, what user will see? You can hardly build any deterministic businesses logic based on pagination. Pagination belongs into presentation layer, and should not be handled by databases if possible. Unfortunately the reality is different. Databases are inert, it will take a lot of time, till special index type is introduced, if it ever happens. – ibre5041 Aug 30 '16 at 13:02
2

SQL Databases ... don't do paging well at all.

Actually, databases (or RDBMS to be precise) don't do paging at all. That's up to client programs. But there are smart ways to query DBs involving indexes with varying support from different RDBMS.

"Paging" hardly defines a task. That's why your question is hard to answer. You have to specify how you define pages first.

Read-only tables are trivial. Just add a row number in a materialized view and a plain btree index on it. Every RDBMS can do that. The true art is in handling concurrent write load. You have to define exact requirements first. And that's where your question is leaving out ...

for the data lower down it would still need to scan through all the previous data to get the correct starting row.

Your description indicates that you are using a lowly OFFSET - FETCH in SQL Server - other RDBMS use different syntax. A large offset is bound to be slow this way.
Instead, remember unique (!) index column value(s) of first and last row for the current page and you can retrieve the next or previous n rows very quickly using a matching btree index - in logarithmic time.

In particular, Postgres also supports this technique for multicolumn keys (row values). Details in these related answers:

  • What if the the user directly scrolls to the middle of the data in grid? We don't need the next page, we need random pages. – John Aug 31 '16 at 6:08
  • @John: Define "middle". Also, if the users "scrolls", you have to start somewhere. And if a user can scroll from the start to the middle, we are talking about about a trivial number of rows, which should be uncritical for performance even with LIMIT / OFFSET. – Erwin Brandstetter Aug 31 '16 at 10:12
  • The middle of a billion rows is half a billion. If you have a scrollbar on a data grid, you can easily skim over millions of rows in milliseconds of a mouse move by yanking down the scrollbar thumb. That's the whole point of scroll bars. – John Aug 31 '16 at 10:15
  • @John: Again, it depends on requirements. In a read-only table, this is well-defined and simple and cheap (add a row number). With concurrent writes, it gets tricky because "half a billion" is a moving target, and the best solution depends on exact requirements. You did ask for paging, not for scrolling. – Erwin Brandstetter Aug 31 '16 at 10:26
  • It's true I should have mentioned the scrolling case right away. I thought it was obvious as basically all middleware data layers have classical pagers and virtual scrolling basically call down to the same thing: "take" and "skip" operations in the respective sql dialect. Whenever you see a grid with a pager somewhere, be assured it's probably not going to do what you're suggesting in your answer - except it was hand-crafted. The fact remains that data grids, middleware and databases don't play well together in this regard. – John Aug 31 '16 at 10:33
1

Pagination via OFFSET is both slow, and error prone. This discusses how to "remember where you left off" as a better way.

  • When the user yanks down the scrollbar thumb to the somewhere in the middle of a zillion records of a result set, that won't help. And that's the kind of paging that's actually important. I don't expect a user to click "next page" a hundred thousand times on a classical pager. – John Aug 30 '16 at 20:26
  • Search for "infinite scroll"; it became popular a couple of years ago, and probably involves Javascript and AJAX, more than MySQL. – Rick James Aug 30 '16 at 20:52
  • Or take a Toolkit from Telerik or DevExpress and bind their data grids to a Sql Server table through linq. Same thing. I doubt it came after ajax. – John Aug 30 '16 at 20:54

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