Pagination with Cassandra and what we can learn from it

Like everybody else it took me a while to wrap my head around the BigTable concepts in Cassandra. The brain needs some time to accept that a column in Cassandra is really not the same as a column in our beloved RDBMS. After that I wrote the first Web Application and run into a pretty typical problem. I needed to list a large number of results and needed to page this for my web page. And like many others I ran straight into the next wall. Only this time it was not Cassandras fault really and I thought I share what I found.

Pagination in the table oriented world

In the mind of every developer there is a simple solution for paging. You add an sequence column to the table that is monotonically increasing and use a select like the following:

select * from my_data where sq_num between 25 and 50

This would get me 25 rows. It is fast too, because I made sure the sq_num column had an index attached to it. Now on the face of it this sounds easy, but you run into problems quickly. Almost every use case requires the result to be sorted by some of the columns. In addition the data would not be static, but be inserted to and possible updated all the time. Imagine you are returning a list of names, sorted by first name. The sq_cnt approach will not work because you cannot re-sequence large amounts of data every time. But luckily databases have a solution for that. You can do crazy selects like the following:

select name, address
  from (
  select rownum r, name, address
    from person sort by name;
  )
where r >  25 and
      r < 50;

It looks crazy, but is actually quite fast on Oracle (and I think SQLServer too) as it is optimized for it. Although all databases have similar concepts, most don’t do so well in terms of performance. Often the only thing possible, with acceptable performance is to limit the number of return rows. Offset queries, as presented here, incur a serve performance overhead. With that in mind I tried to do the same for Cassandra.

Pagination in Cassandra

I had a very simple use case. I stored a list of Journeys on a per Tenant basis in a Column Family. The name of the Journey was the column name and the value was the actual journey. So getting the first 25 items was simple.

get_slice("key" : tenant_key,
	  "column_parent" : {"column_family" : "Journeys_by_Tenant"},
	  "predicate" :
		{ "slice_range" : 
 { "start" : "A", 
 "end" : "Z", 
 "reverse" : "false", 
 "count : "25" }
 } )

But like so many I got stuck here, how to get the next 25 items? I looked, but there was not “offset” parameter, so I checked doctor google and the first thing I found was: “Don’t do it!” But after some more reading I found the solution and it is very elegant indeed. More so than what I was doing in my RDBMS and best of all it is applicable to RDBMS!

The idea is simple, instead of using an numeric position and a counter you simply remember the last returned column name and use it as a starting point in your next request. So if the first result returned a list of Journeys and the 25th was “Bermuda” then the “next” button would execute the following:

get_slice("key" : tenant_key,
	  "column_parent" : {"column_family" : "Journeys_by_Tenant"},
	  "predicate" :
	   { "slice_range" : 
 { "start" : "Bermuda", 
 "end" : "Z", 
 "reverse" : "false", 
 "count : "26" }
 } )

You will notice that I now retrieve 26 items. This is because start and end are inclusive and I will simply ignore the first item in the result. Sounds super, but how to go backwards? Turns out it is simple. You use the “first” result of your last page and execute the following:

get_slice("key" : tenant_key,
	  "column_parent" : {"column_family" : "Journeys_by_Tenant"},
	  "predicate" :
	   { "slice_range" : 
 { "start" : "Bermuda", 
 "end" : "A", 
 "reverse" : "true", 
 "count : "26" }
 } )

The reverse attribute will tell get_slice to go backwards. What’s important is that the end of a reverse slice must be „before“ the start. Done! Well not quite. Having a “First” and “Last” button is no problem (simply use reverse starting with Z for the last page), but if like many Web pages, you want to have direct jumpers to the page numbers, you will have to add some ugly cruft code.

However you should ask yourself, how useful it is to jump to page 16 really! There is no contextual meaning of the 16th page. It might be better to add bookmarks like A,B,C instead of direct page numbers.

Applying this to RDBMS?

The pagination concept found in Cassandra can be applied to every RDBMS. For the first select simply limit the number of return rows either by ROWNUM, LIMIT or similar (you might also use the jdbc api).

select name, address
    from person
    sort by name
    fetch first 25 rows only;

For the “next” call, we can apply what we learned from Cassandra:

select name, address
    from person
    where name > 'Andreas'
    sort by name
    fetch first 25 rows only;

If we want to apply this to the “previous” button it will look like this:

select name, address
    from person
    where name < 'Michael'
    sort by name desc
    fetch first 25 rows only;

For the “Last” button simply omit the where clause. The advantage? It is far more portable then “offset selects” – virtually every database will support it. It should also be performing rather well, as long as you have an index on the name column (the one that you sort by). Finally there is no need to have a counter column!

Conclusion

NoSQL Databases challenge us, because they require some rewiring of our RDBMS trained brain. However some of the things we learn can also make our RDBMS applications better.

Of course you can always do even better and build pagination into your API. Amazons SimpleDB is doing that, but more on SimpleDB later, stay tuned…