Efficient range estimation with NDB interpreted code

The NDB API contains a facility to write NDB interpreted code (NDB IC) programs that can be sent to the RonDB data nodes and evaluated within a RonDB cluster.This paper describes how to use RonDB from Common Lisp using the Common Lisp bindings for the C++ NDB API, or short cl-ndbapi (for Common Lisp NDB API), and also how to write NDB IC programs and use them in table and index scan.I describe how to implement a storage backend for a Resource Description Framework (RDF) triple store that is based on RonDB. I explain how triples can be stored in a very simple fashion in an SQL table and I show some simple SPARQL queries and how they translate to underlying RonDB index scans.Then I focus on how all this can be combined to implement an efficient row count estimation of a bounded index scan that runs in constant time, that is, with a bound of growth of O(1) in Bachmann-Landau notation, and returns almost instantly even on a large database with 3.3 billion statements.We use this range estimation to steer the query optimization of Dydra’s SPARQL processor SPOCQ, which needs to know the cardinalities of graph patterns.