Pattern for efficiently paging database rows on a web page

It shouldn’t be difficult to read rows from a database and render them on a web page – it’s a pretty fundamental operation that most web apps have to do but a surprising number don’t get quite right, especially when the volume of data grows and it can’t all be loaded and rendered within a single request. I’ve recently come across several ‘enterprise applications’ that simply fail to get it right – one extreme example loaded all the database rows into session state and then used LINQ to get and display the pages from that (!) and another took the approach of simply not paging the results at all which meant huge pages that were incredibly slow to load and as the data grew beyond the simple developer-test dataset.

So, I’m going to try and explain the technique I use for paging through rows which I’ve found works efficiently and is easy to re-use. It works well for both traditional and AJAX requests and handles sorting and filtering requirements as well. This is based on ASP.NET MVC, jQuery and NHibernate + SQL Server but the principals will be the same for other technologies (I’ve used the same basic approach with MongoDB as the back-end data-store).

Paged Data Model

We’ll start by defining a generic abstract class that will make it easy for us to re-use the approach for different lists. This will represent the ‘set’ of data on a page together with some additional information about the position of the page within the entire list, the total number of records and the sort order applied etc…

/// <summary>
/// Represents a paged list of data.
/// </summary>
/// <typeparam name="T">The item type in the list</typeparam>
/// <typeparam name="TS">The sort order specifier type.</typeparam>
public abstract class PagedList<T, TS>
{
    /// <summary>
    /// Gets or sets the list of entities.
    /// </summary>
    public IEnumerable<T> List { get; set; }

    /// <summary>
    /// Gets or sets the current page number.
    /// </summary>
    public int PageNo { get; set; }

    /// <summary>
    /// Gets or sets the number of records per page.
    /// </summary>
    public int PageSize { get; set; }

    /// <summary>
    /// Gets or sets the total number of records.
    /// </summary>
    public int RecordCount { get; set; }

    /// <summary>
    /// Gets or sets the first record number displayed.
    /// </summary>
    public int StartRecord { get; set; }

    /// <summary>
    /// Gets or sets a value indicating whether this <see cref="PagedList<T, TS>"/> is the latest page.
    /// </summary>
    /// <value><c>true</c> if latest; otherwise, <c>false</c>.</value>
    public bool Latest { get; set; }

    /// <summary>
    /// Gets or sets SortSeq.
    /// </summary>
    public TS SortSeq { get; set; }
}

The <T> and <TS> generic property types represent the type of entry that will be in the list (the ‘things’ we are paging over) and an Enum representing the sort-order required. As an example, we’ll page over a set of UserSummary entities and the sort-order will be defined with a UserSortSequence Enum:

/// <summary>
/// How users are ordered in result sets
/// </summary>
public enum UserSortSequence
{
    /// <summary>
    /// Order by name alphabetically
    /// </summary>
    ByName, 

    /// <summary>
    /// Order by date joined
    /// </summary>
    ByJoined, 

    /// <summary>
    /// Order by number of topics started
    /// </summary>
    ByTopics, 

    /// <summary>
    /// Order by number of posts
    /// </summary>
    ByPosts, 

    /// <summary>
    /// Order by reputation
    /// </summary>
    ByReputation
}

The PagedList is abstract so we need to create a specific class to represent the type of paged set that we want to use and this class will also contain any additional filtering parameters that our paging system will use. In this case, we will create a UserSet class that contains an additional Name property for filtering.

/// <summary>
/// Represents a user set.
/// </summary>
public class UserSet : PagedList<UserSummary, UserSortSequence>
{
    /// <summary>
    /// Gets or sets Name to filter.
    /// </summary>
    public string Name { get; set; }
}

Controller & Action

With these classes in place we can create a controller action to handle the request. A simplified version is shown below:

/// <summary>
/// Display paged user set filtered and sorted as required.
/// </summary>
/// <param name="name">The name filter.</param>
/// <param name="page">The page number.</param>
/// <param name="size">The page size.</param>
/// <param name="sort">The sort sequence.</param>
/// <returns></returns>
public ActionResult Index(string name, int page, int size, UserSortSequence sort)
{
    var model = new UserSet { PageNo = page, PageSize = size, SortSeq = sort, Name = name };
    this.Repository.PopulateUserSet(model);

    return View(model);
}

Data Access Layer

The real work is done in the PopulateUserSet method of the repository. This needs to do 3 things:

  1. Get the total number of rows matching whatever filter criteria are specified.
  2. Calculate the rows to display based on the page number and page size specified.
  3. Get the set of data from the database applying any sort order specified.

The sample below uses several NHibernate features and takes advantage of it’s ability to translate a paged-set request into the specific dialect of the database in question using whatever ROW_NUMBER functionality may be available so that the query operates as efficiently as possible.

/// <summary>
/// Populate user set with paged data.
/// </summary>
/// <param name="userset">The user set.</param>
public void PopulateUserSet(UserSet userset)
{
    // Get total count for all users in this set
    userset.RecordCount = this.session.CreateCriteria(typeof(Account))
        .Add(Restrictions.Like("Name", userset.Name, MatchMode.Anywhere))
        .SetProjection(Projections.RowCount())
        .UniqueResult<int>();

    // calculate the last page based on the record count and page size
    int lastPage = ((userset.RecordCount - 1) / userset.PageSize) + 1;

    // ensure page number is in range
    if (userset.PageNo < 1) {
        userset.PageNo = 1;
    }
    else if (userset.PageNo > lastPage) {
        userset.PageNo = lastPage;
        userset.Latest = true;
    }

    userset.StartRecord = (userset.PageNo - 1) * userset.PageSize;

    // create criteria to get user account with paging
    ICriteria userListCriteria = this.session.CreateCriteria(typeof(UserSummary))
        .Add(Restrictions.Like("Name", userset.Name, MatchMode.Anywhere))
        .SetFirstResult(userset.StartRecord)
        .SetMaxResults(userset.PageSize);

    // add ordering to criteria
    switch (userset.SortSeq)
    {
        case UserSortSequence.ByJoined:
            userListCriteria.AddOrder(Order.Asc("RegisteredOn"));
            break;
        case UserSortSequence.ByName:
            userListCriteria.AddOrder(Order.Asc("Name"));
            break;
        case UserSortSequence.ByPosts:
            userListCriteria.AddOrder(Order.Desc("PostCount"));
            break;
        case UserSortSequence.ByReputation:
            userListCriteria.AddOrder(Order.Desc("Reputation"));
            break;
        case UserSortSequence.ByTopics:
            userListCriteria.AddOrder(Order.Desc("TopicCount"));
            break;
    }

    // get the list of users
    userset.List = userListCriteria.List<UserSummary>();
}

View Rendering

So, we have a representation of a paged set of data, the action to retrieve it and the repository method to populate it. We now need a way of displaying the data and providing links for the user to navigate around it. How the rows are rendered obviously depends on the requirements of your application.

<%@ Page Title="" Language="C#" MasterPageFile="~/Views/Shared/Site.Master" Inherits="System.Web.Mvc.ViewPage" %>
    userSummary) %>
        $(function() {
            setPaging('', , , );
        });

        function setPaging(name, page, pageSize, records) {
            $('.paging').paging({
                page: page,
                pageSize: pageSize,
                records: records,
                url: ''.replace('***', name).replace('99999', '#')
            });
        }

Rendering Paged Links

I’m using a jQuery plug-in to display the page links because it saves doing so much work on the server and it makes it easier to AJAX enable the UI. In the full implementation the controller action can return a full view or just the JSON data for the paged set and the UI uses a template to render it and update the page links.

The paging itself is rendered using a jQuery plug-in. This is designed to intelligently decide which links to render and whether to enable or disable the previous and next links. It keeps the first and last links always visible and ensures that a few links either side of the current page (which is highlighted) are rendered while avoiding silly gaps (like having 1, 2, … 4 instead of 1, 2, 3, 4). Also, the ‘…’ separators are also links to the midpoint of the non-displayed sequence to make it easier to quickly jump around even large lists.

Here is an example of a 10 page set of links rendering using the rules outlines above:

page-links

The code to render this is below:

/*
 * jQuery paging plugin
 *
 * http://www.captaincodeman.com/
 *
 */
(function($) {
    $.fn.paging = function(options) {

        // extend our default options with those provided.
        var settings = $.extend(true, {}, $.fn.paging.defaults, options);

        return this.each(function() {

            function render() {
                panel.empty();

                // calc pages, separators etc... to output
                var pageCount = Math.floor((settings.records - 1) / settings.pageSize) + 1;

                var pages = [];
                var pageStart, pageFinish;

                if (settings.inline) {
                    settings.prev = false;
                    settings.next = false;
                }

                var prevNextCount = 0;
                if (settings.prev) prevNextCount++;
                if (settings.next) prevNextCount++;

                if (settings.prev) {
                    if (currentPage > 1) {
                        pages[pages.length] = new PageEntry(settings.prevText, currentPage - 1, PageType.Previous);
                    } else {
                        pages[pages.length] = new PageEntry(settings.prevText, currentPage, PageType.PreviousDisabled);
                    }
                }

                if (pageCount <= settings.max + (settings.min * 2) + prevNextCount) {
                    // no separator required
                    addPages(pages, 1, pageCount);
                } else
                    if (currentPage <= settings.max) {
                    // cluster at the start
                    addPages(pages, 1, Math.max(currentPage + 1, settings.max));
                    addSeparator(pages, Math.max(currentPage + 1, settings.max), pageCount - settings.min);
                    addPages(pages, pageCount - settings.min + 1, pageCount);
                } else
                    if (currentPage >= pageCount - settings.max + 1) {
                    // cluster at the end
                    addPages(pages, 1, settings.min);
                    addSeparator(pages, settings.min, Math.min(currentPage - 1, pageCount - settings.max + 1));
                    addPages(pages, Math.min(currentPage - 1, pageCount - settings.max + 1), pageCount);
                } else {
                    // cluster in the middle
                    var offset = (settings.max - 1) / 2;
                    addPages(pages, 1, settings.min);
                    addSeparator(pages, settings.min, currentPage - offset);
                    addPages(pages, currentPage - offset, currentPage + offset);
                    addSeparator(pages, currentPage + offset, pageCount - settings.min + 1);
                    addPages(pages, pageCount - settings.min + 1, pageCount);
                }

                if (settings.next) {
                    if (currentPage < pageCount) {
                        pages[pages.length] = new PageEntry(settings.nextText, currentPage + 1, PageType.Next);
                    } else {
                        pages[pages.length] = new PageEntry(settings.nextText, currentPage, PageType.NextDisabled);
                    }
                }

                // render pages
                for (var idx = 0; idx < pages.length; idx++) {
                    if (settings.inline && pages[idx].Page == 1) {
                    } else {

                        var clickHandler = function(page) {
                            return function(event) { return pageSelected(UrlFormat(page), page, event); }
                        }

                        var item;

                        switch (pages[idx].PageType) {
                            case PageType.Previous:
                            case PageType.Next:
                                item = $("<a />")
                                    .bind("click", clickHandler(pages[idx].Page))
						            .attr("href", UrlFormat(pages[idx].Page))
						            .attr("class", 'prevnext')
						            .attr("title", "page " + pages[idx].Page)
						            .text(pages[idx].Text);
                                break;
                            case PageType.PreviousDisabled:
                            case PageType.NextDisabled:
                                item = $("<span />")
						            .attr("class", 'prevnext')
						            .text(pages[idx].Text);
                                break;
                            case PageType.Separator:
                                item = $("<a />")
                                    .bind("click", clickHandler(pages[idx].Page))
						            .attr("href", UrlFormat(pages[idx].Page))
						            .attr("class", 'sep')
						            .attr("title", "page " + pages[idx].Page)
						            .text(pages[idx].Text);
                                break;
                            case PageType.Page:
                                item = $("<a />")
                                    .bind("click", clickHandler(pages[idx].Page))
						            .attr("href", UrlFormat(pages[idx].Page))
						            .attr("title", "page " + pages[idx].Page)
						            .text(pages[idx].Text);
                                break;
                            case PageType.PageSelected:
                                item = $("<span />")
						            .attr("class", 'current')
						            .text(pages[idx].Text);
                                break;
                        }

                        panel.append(item);
                    }
                };
            }

            function pageSelected(url, page, event) {
                currentPage = page;
                var continuePropagation = settings.callback(url, page);
                if (!continuePropagation) {
                    if (event.stopPropagation) {
                        event.stopPropagation();
                    }
                    else {
                        event.cancelBubble = true;
                    }
                    render();
                }
                return continuePropagation;
            }

            function addPages(pages, start, finish) {
                for (var page = start; page <= finish; page++) {
                    if (page == currentPage) {
                        pages[pages.length] = new PageEntry(page, page, PageType.PageSelected);
                    } else {
                        pages[pages.length] = new PageEntry(page, page, PageType.Page);
                    }
                }
            }

            function addSeparator(pages, start, finish) {
                var page = Math.ceil((finish - start) / 2) + start;
                pages[pages.length] = new PageEntry(settings.separatorText, page, PageType.Separator);
            }

            function UrlFormat(page) {
                return settings.url.replace("#", page);
            }

            var panel = jQuery(this);
            var currentPage = settings.page;
            render();
        });
    };

    var PageType = {
        Previous: 3,
        PreviousDisabled: 4,
        Next: 5,
        NextDisabled: 6,
        Separator: 7,
        Page: 8,
        PageSelected: 9
    }

    function PageEntry(text, page, pageType) {
        this.Text = text;
        this.Page = page;
        this.PageType = pageType;
    }

    $.fn.paging.defaults = {
        page: 1,
        pageSize: 20,
        records: 0,
        min: 1,
        max: 3,
        inline: false,
        prev: true,
        prevText: '« prev',
        next: true,
        nextText: 'next »',
        separator: true,
        separatorText: '...',
        url: '#',
        callback: function() { return true; }
    };

})(jQuery);

Summary

These are all the pieces and hopefully it gives you an idea of how it all works. A full implementation will usually contain some extra pieces – besides the AJAX enabled rendering using JSON and client-side templates I’ll also have other links to enable to page-size to be adjusted and the sort-order changed and these are persisted to a cookie in the controller action using a custom binder. Hopefully though, what I’ve shown here will help you get a good solid and efficient paging system implemented.

Please let me know if any part of this is unclear or you’d like further details on any of the pieces.

Homongous! MongoDB, NoSQL and CQRS

I’ve got what I consider to be a pretty good development stack – all the usual suspects: MVC for the front-end; data stored in SQL Server or MySQL and accessed via NHibernate with mappings using FluentNHibernate conventions; the domain model mapped to a view model using AutoMapper and a sprinkling of NInject dependency injection to tie it all together without direct dependencies.

And of course it works, it’s proven – lots of people use this approach. Lately though I’ve been reading a lot about different architectural approaches and in particular CQRS or ‘Command Query Responsibility Segregation‘ from Udi Dahan and Greg Young which, among other things, promotes the idea of having a separate denormalized repository for querying data and another, possibly normalized relational database, for writing to.

Because the query-side repository is denormalized it really lends itself to using a NoSQL approach which seems to be gaining ground so I thought I’d give it a try to see how well it would work using a forum app I’ve been re-developing (currently an MVC/NHibernate/SQL Server based app).

Now, it’s not facebook but it’s not trivial either – there are about 4m posts spread over 200k topics and I’ve done quite a bit of work on the database side of things to make sure it’s efficient and normalized. One feature I’m implementing is to go away from the old and boring topic list that most forums have (where they show the topic title, author, date, number of replies and sometimes the date and author of the latest reply) and present it more graphically with the avatar of the topic starter, the title, date and folder it’s in and then the avatars of the last 3 or more (depending on configuration) people who have replied. Here’s an example:

Now, to do this with the relational model means that I need to do quite a few table joins and when there are 4m+ rows that I need to be able to sort and page over it can start to chug a little. So, to speed things up I’ve spent some time optimizing the queries to use Indexed Views to combine the Topic, Folder and Author and Common Table Expressions (CTE) to get the last 3 replies which means joining the Topic, Post and Author tables again. It all works and it’s pretty quick but it’s been a lot of work to get it to that point.

So, the first test was to pick a NoSQL database to try as an alternative. I read up on quite a few and looked at the features and compatibility with Windows/C#/.NET including CouchDB, MongoDB, Cassandra, Voldemort and others and in the end decided to go with MongoDB.

Downloading and installing MongoDB (basically just unzipping the files) was easy and with the excellent documentation I was up and running really quickly and ready to start trying things out.

The first step was to try reading and writing documents using C# and this was really straightforward using the mongodb-csharp driver. So, next step was to convert the data from SQL Server into it. I already had the queries that created the paged views of data – typically with 10 or 20 records per page and thought I’d just re-use that. Running against the whole recordset really slowed it down though but after SQL Server chugged away for 10 or 15 minutes and used 6.5Gb of RAM it managed to give me the data and I created the JSON documents in-memory ready for inserting.

So, I call ‘Insert’ to add the collection of documents to the MongoDB store. And it failed. Well, actually … I assumed it failed because it only seemed to take about 5 seconds and my console app finished. When I went to the MongoDB console and queried the data though it was all there … and I could query it, sort it, page through it, very VERY quickly – much quicker than using SQL Server and the relational model. Windows process explorer showed MongoDB used just a few Mb of RAM to do this.

Because querying was so easy and so direct I no longer needed to use an OR/M to address the object-relational impedance mismatch (a fancy way of saying an RDBMS sucks for OO) and I no longer needed to transform the persistent domain model into a view model before presenting it. I can just get the view model objects straight from the store and render them. Fast, simple, and I get to delete lots of code which is kind of soul destroying when you’ve written it but I’m excited at all the code I won’t have to write in future with this approach and the performance.

MongoDB is very, very fast and very easy to use although it requires a slightly different way of thinking when you’re more used to working with a relational model. One of the big selling points is that it’s easier to scale than a relational system and while I didn’t try the sharding support (which is in alpha) I did give the replication a go – again, it was much easier to setup than the equivalent would be with SQL Server and it performed very well.

Finally, I did a few more experiments to test the insert performance compared to SQL Server and basically setup a simple table with an Id, Name and Number column and inserted 500,000 rows. I used parameterized queries for SQL Server, re-used the same command object and wrapped it all in a single transaction but it took over 55 seconds to run (plus I had to create the database and table in advance which took a minute or two). Doing the same thing with MongoDB ran in under 10 seconds and the client code was much simpler and I didn’t have any initial setup.

I’m definitely going to explore MongoDB more and plan on making use of it in future projects when it’s appropriate. The next piece to look at is the Command side of CQRS where I want to use event sourcing for storage and an event driven / service oriented architecture and better domain driven design techniques.