Hacker News Reader

Comment by kevindeasis | Hacker News Reader

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

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.

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?

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.

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.

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

And if the data frequently changes during pagination?

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.

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.

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.

You need this if it's for a feed that gets frequent updates. Imagine a paginated Twitter feed, and the user clicks a link with ?page=3, and suddenly there's a new tweet, causing page 3 to have a tweet the user saw on page 2. Using afterId solves that.

OFFSET is not "handled by the engine". It heapsorts the entire dataset before you offset to a page.

The top-level comment is asking for good ways to paginate. OFFSET works on localhost and with hundreds of rows. My solution is one that works in production once OFFSET fails you. For me, it was day 2.

It was day 2 for you, with the specific engine you used.

You don't need to heapsort the entire dataset before you offset to a page, and there are engines capable of doing this.

Or they could be speaking from experience, because back in the day when webforums where the place to make online communities, as they grew beyond a certain size this sort of thing became THE bottleneck, especially for large threads.

I empirically know this was an issue back then. I also agree it's something a DB engine should handle, and I do hope that databases do a better job today.

So instead of calling out "premature optimization", maybe instead come with a practical example of a DB engine that properly handles this?

I just wrote about doing it this way yesterday.

http://www.mozartreina.com/

You should at least reference the fact that with MySQL, the server has to step through OFFSET result rows before it can start streaming you data. This can get surprisingly expensive, surprisingly quickly. See http://stackoverflow.com/questions/4481388/why-does-mysql-hi...

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.

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.

Use continuations.

Use the seek method:

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-t...

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...

Why would you break content into "pages"? If the requestor wants the data, give it to them

Forcing artificial page-breaks is abusive.

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?

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.

Reply on news.ycombinator.com