Saturday, March 20, 2010

A Really, Really Big HTML Table

I recently needed to create a scrollable HTML table which could handle a lot of rows quickly. My first target was about 3,000 rows, but as you will see, I managed to put together something that will "render" 1 million rows without breaking a sweat.

This problem has already been solved before. A typical approach for handling large amounts of data is what I like to broadly refer to as data partitioning. There are many ways to partition data, one of which is pagination. The most common example? Google. When you perform a Google search, even if there are a million results, only 10 are displayed at a time. This principle is also commonly applied to "table components" in many Javascript frameworks. For example, the YUI DataTable supports pagination.

One slant on pagination is the concept of making a scrollable table which somehow "paginates" on the data which is actually visible. Quite a few frameworks now support this concept, such as qooxdoo's virtual table. My goal was to create a table component which used this scrolling concept to allow for Really, Really Big tables. This article describes a generic method for creating such a table, as well as a proof-of-concept implementation.

The first step in the method is to assume a fixed row height. While this is not ideal, in most cases the row heights are fixed anyways, and it helps us to do simple calculations. For instance, if we know the row height, and we know the number of rows, then the scrollable height of the container should be (row height * number of rows). We know that for a particular scroll position, rows i through n are visible, where i is (scroll position / row height) and n is ( (scroll position + visible area height) / row height). So now we have the math to set up a scrollbar with the correct height and how to figure out which rows need to be rendered when the user scrolls.

The next part is structuring this in HTML.We want fixed headers and a scrollable body.


The blue outline is the visible header area. The red outline is the visible body area. Both the headers and the body extend outside of the visible region which creates scrollbars for the body (gray). The blue and red outlines are simply divs, each containing a table.

Next, we need to make the table body tall enough to force a vertical scrollbar. In addition to this, we need a way to very selectively "fill in" rows. One approach is to go ahead and create the table row elements (but not cells) for each row. This is surprisingly pretty fast, but not fast enough (will work for 3,000 rows, won't work for 1,000,000). The solution I came up with is to create "filler" row elements to fill in the gaps between rendered rows.


The green areas are rendered rows. The yellow area is a filler row with an explicit height set. This "pushes down" the rows beneath it to their correct positions. When initially creating the table, one filler row is created for the entire height of all rows.

When the user scrolls (and on initial creation), the table determines which rows are visible based on the scroll position. Those rows are created if not already done. The filler rows are then created, removed, or updated as necessary to keep everything in the right spot. Maintaining the filler rows is the most complicated piece of the puzzle, but not overly difficult.

The end result? For a table of 1 million rows, only the visible rows + 1 are actually created in the DOM. One nice thing about this approach is that it practically scales in a constant (not linear) time.

Click here for a proof-of-concept example with 1,000,000 rows

The source code for the proof-of-concept is available at http://github.com/jbrantly/bigtable. Note that it is not ready for production. Instead, it simply demonstrates that this technique is feasible and could be used to create a more full-featured component. Also note that many details crucial to the successful implementation of such a component were omitted or glossed over in either the article or the source code.

21 comments:

  1. Thanks for sharing your info. I really appreciate your efforts and I will be waiting for your further write ups thanks once again.

    ReplyDelete
  2. Thanks for your contribution. Its a well programmed structure for implementing big tables. Pls can you say me whether it works the same with mysql data.?

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Great idea. You should check out Michael Liebman's slickgrid https://github.com/mleibman/SlickGrid/wiki.

    ReplyDelete
  5. patriots jerseys, http://www.newenglandpatriotsjerseys.us/
    saints jerseys, http://www.neworleanssaintsjerseys.us/
    fitflop, http://www.fitflop.in.net/
    karen millen uk, http://www.karenmillendressesoutlets.co.uk/
    air jordan 11 free shipping, http://www.airjordan11.net/
    hollister canada, http://www.hollistercanada.com/
    hollister uk, http://www.hollistershirts.co.uk/
    tods outlet, http://www.todsoutlet.us.com/
    air jordan 4 free shipping, http://www.airjordan4.org/
    pandora jewelry, http://www.pandora.eu.com/
    coach outlet online, http://www.coachoutletstores.com.co/
    tiffany and co, http://www.tiffanyandco.in.net/
    prada outlet, http://www.pradaoutlet.us/
    ravens jerseys, http://www.baltimoreravensjerseys.us/
    supra shoes, http://www.suprashoes.us.com/
    hogan,hogan outlet,scarpe hogan,hogan sito ufficiale,hogan interactive
    michael kors outlet, http://michaelkors.outletonlinestores.us.com/
    juicy couture tracksuit, http://www.juicycoutureoutlet.net/
    chicago bulls, http://www.chicagobullsjerseys.net/
    jets jersey, http://www.newyorkjetsjersey.us/
    cai2015912

    ReplyDelete
  6. Quester is a Pakistan-based questioning answering website where people can ask questions and we try our best to provide them with the best answers. Anyone can ask any legit question in English or Roman Urdu and we provide answers in the same language format. www.quester.pk

    ReplyDelete
  7. Tu artículo es muy intersante, gracias por compartir. desde Cuenca - Ecuador

    ReplyDelete