5 ms·

How do you guys implement / What's the best practice for paginating your db using sql and nosql? I know there are a bunch of gotcha's to look out for

ldjb 10y ago
I feel there are essentially two approaches. You could store the entire article text as a single chunk of data. The text would be marked-up to indicate where the page breaks are. Each time a page of the article is requested, the entire article is fetched from the database, but the website software extracts only the necessary extract. This is rather inefficient in principle, although it is possible to optimise, and it does keep things relatively simple. On the other hand, you could have an "articles" table and a "pages" table with the relationship: articles 1 <--> 1..* pages Each page's text is stored as a separate row in the "pages" table, along with the article ID and a page number. When a page is requested, only the page that matches the requested article's ID and the appropriate page number. The database schema here is more complex, but is likely to be more efficient.
- err4nt 10y ago
  I'm no DB programmer, but despite the inefficiencies of the first approach (fetch entire article each time and display a different chunk) it would allow for users (or admins) to change page length after the article is written a LOT more easily than if each page was stored separately. Is this a potential concern of using the second method where each chunk is in its own field?
  - ldjb 10y ago
    Assuming there is an actual user interface for composing and publishing articles, that interface doesn't have to be dictated by the way the data is stored. Whichever method you choose, the software will need to be able to transform the data between two formats: one suitable for the user interface, and one suitable for the database. However you designed the UI, it would be possible to use either approach for the database. For example, suppose the UI used a single textarea and had a special notation for delimiting pages. For the first approach, the contents of the textarea can simply be stored in its own field. For the second approach, the software would take the contents of the textarea, split it into its individual pages, then store each page separately. If the UI had separate textareas for each page, then for the first approach, the software combines the contents of the textareas and puts in delimiters. For the second approach, each textarea is mapped to their own database field. I suppose some of combinations are easier for the programmer than others, but so long as the UI is designed to be easy to use, the user need never know how the article is actually represented in the database.
fbonetti 10y ago
It's really easy to paginate data with SQL - just use LIMIT and OFFSET. limit = page_size offset = (current_page - 1) * limit For example, let's say you have a table with 1000 products in it, and you want to display page 3 with a page size of 50. Here's how you would write it: SELECT * FROM products LIMIT 50 OFFSET 100
- pmarreck 10y ago
  And if the data frequently changes during pagination?
  - objclxt 10y ago
    That's why it's often better to use a cursor in your client-facing API (or a pseudo-cursor that maps to something you have in your database), rather than passing the limit/offset through.
- danneu 10y ago
  The downside is that OFFSET is slow if you have a lot of items, like on a forum. At which point you could assign each post in a topic an indexed `position` column that always increases from 0 within that topic, which lets you jump to arbitrary pages and parameterize perPage. fromPos = (page - 1) * perPage SELECT * FROM posts WHERE topic_id = $1 AND position >= fromPos AND position < fromPos + perPage ORDER BY id For simpler needs, your "Next" button could load items that come after the last ID on the current page but with a LIMIT. <ul> {% for item in items %} <li>{{ item }}</li> {% endfor %} </ul> <a href="/items?afterId={{ items[items.length - 1].id }}">Next</a> SELECT * FROM items WHERE id > $afterId LIMIT $perPage That's fast and really easy.
  - lox 10y ago
    This sounds like a really premature optimization to me. Let the DB do it's job unless you have an explain trace showing it's slow for your workload. Trying to do things like sequence columns adds complexity, when this is often handled by the engine.
tantalor 10y ago
One great approach is cursors. Basically, you keep track of the value of the sort function (e.g., relevance) of the last record on the page, and add that to your filter (e.g., WHERE relevance > $LAST_RELEVANCE) to get the next page. This is very efficient when your table is indexed by that field; you can seek directly to the next record. Some database APIs do this for you! I wrote up my experience implementing this on App Engine here, http://johntantalo.com/blog/paginating-with-bookmarks-in-app-engine/ http://johntantalo.com/blog/paginating-with-bookmarks-in-app...
xrstf 10y ago
As fbonetti already said, LIMIT is the canonical way to do it with SQL databases (I would just add to their comment that you should ensure a positive page_size and offset, because "LIMIT -5" is invalid in at least MySQL, and to limit the page size to some sensible values). For NoSQL, specifically (only?) CouchDB, you start iterating from a given key (in SQL, this would effectively be "WHERE id >= $start ORDER BY id ASC LIMIT n"). This difference is why I would recommend, especially for paginated REST APIs, to provide links to the next/prev pages, so API clients can follow these links without thinking about how pagination is accomplished exactly. To prevent people from guessing the inner workings and working around your links, you can encode the parameters in a "cursor" (so instead of ?pagesize=20&page=10 you could have ?cursor=base64encode("20,10") (SQL) or ?cursor=base64encode("$startKey") (NoSQL)). IIRC Facebook does it this way. Encrypting or authenticating the cursor is IMHO overblown here, given cursor values can be easily validated and rejected if fiddled with. Using an opaque cursor also gives you the ability to change how pagination works without breaking existing API clients. If you plan for lots of data and many pages, think twice before outputting links to all pages (on a website) or outputting the total number of elements (in an API). COUNT(*) on InnoDB is slow and I heard it's not the quickest thing in NoSQL databases either.
- yeukhon 10y ago
  How do you keep the cursor / know where you left off with the database? For example, I don't want to repeat what I saw in page 1 in page 2 because someone else just added more articles.
  - HappyTypist 10y ago
    Use continuations.
spottedquoll 10y ago
Why would you break content into "pages"? If the requestor wants the data, give it to them Forcing artificial page-breaks is abusive.
- gnaritas 10y ago
  So if someone requires the entire table you think a single API call should just send it? Does it not occur to you that people used page data to limit response sizes and manage the performance of their API's?
- detaro 10y ago
  So HN should be a single page with all submissions ever? ;) Yes, don't unnecessarily break up content. But most pages are going to include lists of some sort that you want to be paginated in some way. If you look at HNs /new queue, there are submission IDs in the next links, so you can click "more" multiple times without seeing content multiple times, even if new submissions have pushed them down in the global list by now. Useful if there are many updates and new entries come in at the "top" of the list.
deathanatos 10y ago
http://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way http://use-the-index-luke.com/blog/2013-07/pagination-done-t... Essentially, once your rows are ordered, your next page is "rows > the last row on the previous page, limit <number of items to return>" This has the fantastic benefit of being index-friendly, which OFFSET is not, and if you structure the URLs for the pages well, obvious what you're getting back. (e.g., if your records are by date, you might get /daily-reports?since=2015-01-04&limit=50 for the page that starts at 2015-01-04) It's from an SQL site, but the concept is not specific to SQL. I'm working on an implementation of it for data stored in Mongo, at the moment.
emmelaich 10y ago
Use the seek method: http://use-the-index-luke.com/sql/partial-results/fetch-next-page http://use-the-index-luke.com/sql/partial-results/fetch-next... edit: more on this via a slideshare presentation or pdf: http://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way http://use-the-index-luke.com/blog/2013-07/pagination-done-t...

ldjb 10y ago

I feel there are essentially two approaches. You could store the entire article text as a single chunk of data. The text would be marked-up to indicate where the page breaks are. Each time a page of the article is requested, the entire article is fetched from the database, but the website software extracts only the necessary extract. This is rather inefficient in principle, although it is possible to optimise, and it does keep things relatively simple. On the other hand, you could have an "articles" table and a "pages" table with the relationship: articles 1 <--> 1..* pages Each page's text is stored as a separate row in the "pages" table, along with the article ID and a page number. When a page is requested, only the page that matches the requested article's ID and the appropriate page number. The database schema here is more complex, but is likely to be more efficient.

err4nt 10y ago
I'm no DB programmer, but despite the inefficiencies of the first approach (fetch entire article each time and display a different chunk) it would allow for users (or admins) to change page length after the article is written a LOT more easily than if each page was stored separately. Is this a potential concern of using the second method where each chunk is in its own field?
- ldjb 10y ago
  Assuming there is an actual user interface for composing and publishing articles, that interface doesn't have to be dictated by the way the data is stored. Whichever method you choose, the software will need to be able to transform the data between two formats: one suitable for the user interface, and one suitable for the database. However you designed the UI, it would be possible to use either approach for the database. For example, suppose the UI used a single textarea and had a special notation for delimiting pages. For the first approach, the contents of the textarea can simply be stored in its own field. For the second approach, the software would take the contents of the textarea, split it into its individual pages, then store each page separately. If the UI had separate textareas for each page, then for the first approach, the software combines the contents of the textareas and puts in delimiters. For the second approach, each textarea is mapped to their own database field. I suppose some of combinations are easier for the programmer than others, but so long as the UI is designed to be easy to use, the user need never know how the article is actually represented in the database.

fbonetti 10y ago

It's really easy to paginate data with SQL - just use LIMIT and OFFSET. limit = page_size offset = (current_page - 1) * limit For example, let's say you have a table with 1000 products in it, and you want to display page 3 with a page size of 50. Here's how you would write it: SELECT * FROM products LIMIT 50 OFFSET 100

pmarreck 10y ago
And if the data frequently changes during pagination?
- objclxt 10y ago
  That's why it's often better to use a cursor in your client-facing API (or a pseudo-cursor that maps to something you have in your database), rather than passing the limit/offset through.
danneu 10y ago
The downside is that OFFSET is slow if you have a lot of items, like on a forum. At which point you could assign each post in a topic an indexed `position` column that always increases from 0 within that topic, which lets you jump to arbitrary pages and parameterize perPage. fromPos = (page - 1) * perPage SELECT * FROM posts WHERE topic_id = $1 AND position >= fromPos AND position < fromPos + perPage ORDER BY id For simpler needs, your "Next" button could load items that come after the last ID on the current page but with a LIMIT. <ul> {% for item in items %} <li>{{ item }}</li> {% endfor %} </ul> <a href="/items?afterId={{ items[items.length - 1].id }}">Next</a> SELECT * FROM items WHERE id > $afterId LIMIT $perPage That's fast and really easy.
- lox 10y ago
  This sounds like a really premature optimization to me. Let the DB do it's job unless you have an explain trace showing it's slow for your workload. Trying to do things like sequence columns adds complexity, when this is often handled by the engine.

tantalor 10y ago

One great approach is cursors. Basically, you keep track of the value of the sort function (e.g., relevance) of the last record on the page, and add that to your filter (e.g., WHERE relevance > $LAST_RELEVANCE) to get the next page. This is very efficient when your table is indexed by that field; you can seek directly to the next record. Some database APIs do this for you! I wrote up my experience implementing this on App Engine here, http://johntantalo.com/blog/paginating-with-bookmarks-in-app-engine/ http://johntantalo.com/blog/paginating-with-bookmarks-in-app...

xrstf 10y ago

As fbonetti already said, LIMIT is the canonical way to do it with SQL databases (I would just add to their comment that you should ensure a positive page_size and offset, because "LIMIT -5" is invalid in at least MySQL, and to limit the page size to some sensible values). For NoSQL, specifically (only?) CouchDB, you start iterating from a given key (in SQL, this would effectively be "WHERE id >= $start ORDER BY id ASC LIMIT n"). This difference is why I would recommend, especially for paginated REST APIs, to provide links to the next/prev pages, so API clients can follow these links without thinking about how pagination is accomplished exactly. To prevent people from guessing the inner workings and working around your links, you can encode the parameters in a "cursor" (so instead of ?pagesize=20&page=10 you could have ?cursor=base64encode("20,10") (SQL) or ?cursor=base64encode("$startKey") (NoSQL)). IIRC Facebook does it this way. Encrypting or authenticating the cursor is IMHO overblown here, given cursor values can be easily validated and rejected if fiddled with. Using an opaque cursor also gives you the ability to change how pagination works without breaking existing API clients. If you plan for lots of data and many pages, think twice before outputting links to all pages (on a website) or outputting the total number of elements (in an API). COUNT(*) on InnoDB is slow and I heard it's not the quickest thing in NoSQL databases either.

yeukhon 10y ago
How do you keep the cursor / know where you left off with the database? For example, I don't want to repeat what I saw in page 1 in page 2 because someone else just added more articles.
- HappyTypist 10y ago
  Use continuations.

spottedquoll 10y ago

Why would you break content into "pages"? If the requestor wants the data, give it to them Forcing artificial page-breaks is abusive.

gnaritas 10y ago
So if someone requires the entire table you think a single API call should just send it? Does it not occur to you that people used page data to limit response sizes and manage the performance of their API's?
detaro 10y ago
So HN should be a single page with all submissions ever? ;) Yes, don't unnecessarily break up content. But most pages are going to include lists of some sort that you want to be paginated in some way. If you look at HNs /new queue, there are submission IDs in the next links, so you can click "more" multiple times without seeing content multiple times, even if new submissions have pushed them down in the global list by now. Useful if there are many updates and new entries come in at the "top" of the list.

deathanatos 10y ago

http://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way http://use-the-index-luke.com/blog/2013-07/pagination-done-t... Essentially, once your rows are ordered, your next page is "rows > the last row on the previous page, limit <number of items to return>" This has the fantastic benefit of being index-friendly, which OFFSET is not, and if you structure the URLs for the pages well, obvious what you're getting back. (e.g., if your records are by date, you might get /daily-reports?since=2015-01-04&limit=50 for the page that starts at 2015-01-04) It's from an SQL site, but the concept is not specific to SQL. I'm working on an implementation of it for data stored in Mongo, at the moment.

emmelaich 10y ago

Use the seek method: http://use-the-index-luke.com/sql/partial-results/fetch-next-page http://use-the-index-luke.com/sql/partial-results/fetch-next... edit: more on this via a slideshare presentation or pdf: http://use-the-index-luke.com/blog/2013-07/pagination-done-the-postgresql-way http://use-the-index-luke.com/blog/2013-07/pagination-done-t...