Exact-Match Filtering, Ascending Sort

Recall that our primary key definition lists partition as the partition key column, and cluster_01 is the first clustering key. Suppose we wish to use a filter value of ‘A01’ for partition, a filter value of ‘B01’ for cluster_01, and a page size of two.

SELECT *
FROM paging_table
WHERE partition = 'A01' AND cluster_01 = 'B01'
ORDER BY cluster_01 ASC
LIMIT 2;

Suppose the current page of results is the following:

partition	cluster_01	cluster_02	cluster_03	non_primary_key
‘A01’	‘B01’	‘C01’	‘D01’	‘01’
‘A01’	‘B01’	‘C01’	‘D02’	‘02’

To retrieve the next page of data from the table, we use the results from the last record that appeared on the current page. We then add an additional restriction to the WHERE clause to ensure that we retrieve subsequent results based on the contents of the current page. To retrieve the next page in this example, execute the following query:

SELECT *
FROM paging_table
WHERE partition = 'A01' AND
    (cluster_01, cluster_02, cluster_03) > ('B01', 'C01', 'D02')
ORDER BY cluster_01 ASC
LIMIT 2;

Notice, that we although we use a tuple inequality on the clustering keys–(cluster_01, cluster_02, cluster_03) > ('B01', 'C01', 'D02')–we maintain the use of a EQUAL operator on the partition key. This is in fact required, as the partition key cannot be part of a multi-column relation.

The results for the next page query are shown below:

partition	cluster_01	cluster_02	cluster_03	non_primary_key
‘A01’	‘B01’	‘C02’	‘D03’	‘03’
‘A01’	‘B01’	‘C02’	‘D04’	‘04’

Previous Page

Suppose the current page of results is the following:

partition	cluster_01	cluster_02	cluster_03	non_primary_key
‘A01’	‘B02’	‘C03’	‘D05’	‘05’
‘A01’	‘B02’	‘C03’	‘D06’	‘06’

To retrieve the previous page of data from the table, we use the results from the first record that appears on the current page.

SELECT *
FROM paging_table
WHERE partition = 'A01' AND
    (cluster_01, cluster_02, cluster_03) < ('B01', 'C03', 'D05')
ORDER BY cluster_01 ASC
LIMIT 2;

Exact-Match Filtering, Descending Sort

The descending-order case is similar to the ascending-order case. Consult General Patterns for more information.

Range Filtering, Ascending Sort

Recall that our primary key definition lists partition as the partition key column, and cluster_01 is the first clustering key. Suppose we wish to use a filter value of ‘A01’ for partition, a filter range of ‘B01’ to ‘BO2’ (inclusive) for the cluster_01, and a page size of two.

SELECT *
FROM paging_table
WHERE partition = 'A01' AND
  cluster_01 >= 'B01' AND cluster_01 <= 'B02'
ORDER BY cluster_01 ASC
LIMIT 2;

SELECT *
FROM paging_table
WHERE partition = 'A01' AND
  (cluster_01, cluster_02, cluster_03) < ('B02', MAX_TEXT, MAX_TEXT) AND
  (cluster_01, cluster_02, cluster_03) > ('B01', 'C01', 'D02')
ORDER BY cluster_01 ASC
LIMIT 2;

SELECT *
FROM paging_table
WHERE partition = 'A01' AND
  (cluster_01, cluster_02, cluster_03) < ('B02', 'C03', 'D05') AND
  (cluster_01, cluster_02, cluster_03) > ('B01', MIN_TEXT, MIN_TEXT)
ORDER BY cluster_01 DESC
LIMIT 2;

Range Filtering, Descending Sort

The descending-order case is similar to the ascending-order case. Consult General Patterns for more information.

Paging without Filtering

It is not possible in general to page result sets when no filters are used. This is true because the partition key must be restricted in the WHERE clause by an EQUALS or IN relation (supposing secondary indexes are not used). It may be possible to implement paging without filtering when the cardinality of partition keys is very low for a particular table, but we have not explored this.

Notice that all of our query examples rely on the fact that the records to be filtered have the same partition key column value. Because this value is used to determine the location of Cassandra replicas, a potentially small subset of Cassandra nodes (which are the replicas for a particular partition key) will be burdened by handling all pagination and filtering requests for records sharing a partition key. This can be mitigated by increasing the replication factor used in a Cassandra cluster, which in turn increases the replica count and balances load more evenly.

Primary Key Uniqueness

Recall that Cassandra’s primary keys are also a uniqueness constraint; if a new record is inserted with the same primary key values as an existing record, the existing record is overwritten. When the set of filter columns is not guaranteed to be unique, it is often necessary to add an additional column whose values are always globally unique to the primary key definitions of the filtering table.

Maintaining Multiple Tables

To support filtering with n different filter columns, and only one potential order of filters is allowed, then only one Cassandra table is needed. However, to support arbitrary combinations of filters and to allow users to omit arbitrary filter columns,  tables must be created and maintained.

If these tables become inconsistent with respect to each other, this may result in significant problems for the application attempting to use them for paging. Maintaining consistency between these tables is not the scope of this document.


Client-Side Sorting

To retrieve the previous page of results, the application consuming Cassandra’s result sets must reverse the order of the query results. This is a linear-time operation in the application, and may become problematic from a performance standpoint when large page sizes are used.

Asynchronous Updates to Database

If data is changed while users are paging through data using our paging and filtering approach, unexpected behavior may occur. For example, if new data is inserted, but the user has already paged past it, the newly-inserted data will not appear in the paged result set. It is worth noting that similar issues would occur in relational databases unless a transaction was held open for the duration of the paging access.

Maintaining Page Offset

The only way to compute the current page number is to query the database for all records between the first page and a record on the current page. This is mal-performant, and often user interfaces can get away with simply using an approximation instead of the actual offset, e.g. “paged forward X times”. Also, due to the potential of asynchronous updates, a reliable page offset count cannot be maintained. As soon as the current offset is computed, it may change.

Counting Records Matching a Filter

It may be tempting to count the number of all records matching a filter for various purposes, e.g. displaying “user is on page X of Y” in a user interface. However, this should not be attempted, as SELECT COUNT is mal-performant in Cassandra.

Forward-Incompatible Queries in Cassandra

Tuple relations appear not to be tested very well in Cassandra at the time of writing. Several of our queries have broken since Cassandra 2.0.6, particularly in Cassandra 2.0.9 and the 2.1 branch. Part of the purpose of this document is to clarify the kinds of queries we intend to run so that these regressions can be fixed.

String Collation

Cassandra’s internal collation logic for data types dictates the sort order of result data. Collation also informs the MIN_VALUE and MAX_VALUE calculations in the General Patterns section. It may be possible to define custom collators in Java to mitigate this, but we have done no work in this area. This may be a concern for internationalization efforts.

General Patterns

Conventions

We use a variety of naming conventions in this section, many of which are documented here for clarity. First, partition is the partition key column of the table to page. Next, let  be the set of clustering keys for a Cassandra database table ordered according to their appearance in the table’s PRIMARY KEY clause. That is,  is the first clustering key and  is the last clustering key. Let  be the number of columns to use in the filter. Let first_result and last_result be the first and last database records presented on the current page of results, respectively. Finally, let filter_begin represent the values at the start of the filter range (inclusive) and filter_end represent the values at the end of the filter range (inclusive).

Exact-Match Filtering, Ascending Sort
First Page