Virtual rendering for massive speed and scalability

giorgio79

Been noticing a bit of a slowdown for larger tables, over 200 rows with input fields, and been looking around. Noticed some upcoming grids, that have so called virtual rendering like SlickGrid:
https://github.com/mleibman/SlickGrid/wiki

Would love to see sg like this for Datatables. :)

giorgio79

It seems like this is already possible :)
http://datatables.net/examples/basic_init/scroll_y_infinite.html

Awesome :)

allan

Performance is always a key point (although 200 rows is rather poor - normally the tail off is about 2000 rows in IE, and 5000 in the other browsers - at that point it's best to switch to server-side processing with DataTables).

SlickGrid is a superb project - and some very impressive techniques behind it. However, DataTables and SlickGrid are trying to solve different problems. From the SlickGrid site:

"The key difference is between SlickGrid and other grid implementation I have seen is that they focus too much on being able to understand and work with data (search, sort, parse, ajax load, etc.) and not enough on being a better “grid” (or, in case of editable grids, a spreadsheet). It’s great if all you want to do is “spruce up” an HTML TABLE or slap a front end onto a simple list, but too inflexible for anything else."

DataTables _is_ trying to spruce up an HTML table. This can be seen, for example, by the use of the TABLE tag by DataTables, while SlickGrid uses DIV elements to create a display which looks like a table. As such, there are a number of techniques, like the virtual rendering, which can be used with the DIVs - but not with a table. It's not possible to simply render rows 100-110 and not the first 100 in a table, but it's no problem with DIVs, so I'm afraid that this isn't applicable at the moment. What would need to be done is to convert DataTables to using a DIV tag markup, but then you loose the primary goal of DataTables, which is focus on progressive enhancement and accessibility.

So as I say, SlickGrid is an awesome project, but focused on something different (albeit similar) to DataTables.

Regards,
Allan

giorgio79

Thanks Allan for this explanation. Your infinite scrolling example with a javascript array data source is quite close to most grids out there, except that as you mention, it may not be infinitely scalable, since as I understand it is adding rows with scrolling, but not removing invisible ones. :)

Still 5000 sounds good, hence I will try to remove input fields which are probably the cause of slowness, and try to make cells editable with your keytable plugin. :)

vicaya

Allan,

Since dataTables already supports server-side processing, it seems to me that you'd only need minor changes to the core to support a pluggable ajax function to implement server-side processing on the client side on js arrays etc. i.e., if the ajax call is pluggable, someone (maybe myself :) can write a virtual rendering plugin for dataTables.

Does this make sense?

allan

Hi vicaya,

What sort of changes are you thinking of? I'd certainly be delighted to add support as required for this sort of extension, but I'm not clear on how it would work exactly. There is the fnServerData callback at the moment which can be used to implement custom server calls, and examples like the pipelining one to retrieve more data than needed for a single draw to ease the number of calls to the server. However, I'm not sure how virtual rendering would be done with a TABLE tag? Solutions like the one slickgrid uses make use of DIV elements so you can effectively do random access drawing to the screen. Any thoughts one it would be very welcome indeed!

Regards,
Allan

vicaya

Ah, fnServerData, I think this should be enough. SlickGrid got nothing on DataTables!

The current bottleneck of table rendering is the not the size of js arrays (which can handle up to few million elements in modern browsers) but the number of DOM nodes. This is also the reason pure html table doesn't scale beyond few thousand rows either. However the current implementation of aaData and ajaxSource without bServerSide would try to add ALL the DOM nodes via fnAddData. In bServerSide mode, only iDisplayLength of rows worth of DOM nodes are created and an fnServerData plugin can do virtual serverside processing (sorting, searching/filtering in pure js) on a million element js array.

So we can call this virtual rendering via virtual server-side processing :)

Does it make sense?

vicaya

On the second thought, I think virtual server-side processing should really be built in to the core (there is much code to share for processing) and that DT should automatically use virtual server-side processing for aaData and ajaxSource. You can potentially have a DT with less code and scales to a million rows!

BTW, fnServerData would suffice for my current needs (also gonna be an open source project).

Thanks again, Allan!

allan

Server-side processing could almost be called virtual rendering I suppose although I think "true" virtual rendering is the ability that slickgrid and other projects have to show any row in a table by positioning (for example the DOM might include rows 1-20, 81-90 and 3011-3200). With a table you can't do that - you must include all of the "in between" rows. Slickgrid and DataTables, although very similar in scope, are trying to solve slightly different problems - and I believe are complimentary to each other.

Look forward to seeing what you come up with!

Allan

vicaya

The following example demonstrates a dataTable with 1 billion rows, searching (full word only now), sorting and paging all work as expected. I bet no user can tell the difference between virtual and real, except for the fact it's seems too fast for a 1 billion row table :) Feel free to include the example as a demonstration of the power of dataTables.

[code]
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">



DataTables with 1 billion rows








table { width: 100%; border-collapse: collapse; border-spacing: 0 }
.css_left { float:left }
.css_right { float:right }


$(function() {
$('#test').dataTable({bJQueryUI:true, bServerSide:true,
sPaginationType:"full_numbers", sAjaxSource:"1 billion rows",
aoColumns:[null, {bSortable:false}, {bSortable:false}],
fnServerData: function(sSource, aoData, fnCallback) {
var params = {};
for (var i = 0; i < aoData.length; ++i) {
var pair = aoData[i];
params[pair.name] = pair.value;
}
var nrecs = 1000000000;
var result = {sEcho:params["sEcho"], iTotalRecords:nrecs,
iTotalDisplayRecords:nrecs, aaData:[]};
var query = params["sSearch"];
if (query.length > 0) {
var q = query.match(/^row(\d+)$/);
if (!q || q[1] < 1 || q[1] > nrecs) {
result["iTotalDisplayRecords"] = 0;
fnCallback(result);
return;
}
result["iTotalDisplayRecords"] = 1;
result.aaData.push([q[0], "r"+ q[1] +"c2", "r"+ q[1] +"c3"]);
fnCallback(result);
return;
}
var dir = params["sSortDir_0"];
var start = parseInt(params["iDisplayStart"]);
var len = parseInt(params["iDisplayLength"]);
if (dir == 'asc') {
for (var i = start; i < start + len && i < nrecs; ++i) {
result.aaData.push(["row"+ i, "r"+ i +"c1", "r"+ i +"c2"]);
}
} else {
for (var i = nrecs - start - 1; i >= nrecs - start - len && i >= 0; --i) {
result.aaData.push(["row"+ i, "r"+ i +"c1", "r"+ i +"c2"]);
}
}
fnCallback(result);
}
});
});

DataTables with 1 billion rows




Column 0
Column 1
Column 2


row0
r0c1
r1c2


[/code]

vicaya

A bug in the example the "q[1] < 1" in the if statement should be "q[1] < 0", otherwise row0 would not be searchable. In any case, I'm really happy with how things turn out (bServerSide doesn't have any show stopping bugs yet!)

One suggestion: add a contrib directory in your github repo, and put all the plugins in the directory, so people can contribute patches against the js files instead of the html pages :)