2b:null 2c:["$","title",null,{"children":"A very short NDB interpreted program: row counts and range estimations | datagenous | Observable"}] 31:Tb828,${await FileAttachment("Datagraph-a-very-short-ndb-interpreted-program.png").image( {title: "A very short NDB interpreted program: row counts and range estimations", style: "margin-bottom: 20px"})} # A very short NDB interpreted program:
row counts and range estimations November 17, 2025. Max-Gerd Retzlaff, Datagraph GmbH, Berlin. *This is the third article in [a series on using NDB interpreted code (IC) programs with RonDB](/@datagenous/ndb-interpreted-code-article-series) and discusses:* - *an example of a very short but still very useful interpreted code program and* - *I outline how it is used in RonDB to do quick row counts of entire tables, but* - *the main part is how this is adapted to be useful to improve [our graph database Dydra](https://dydra.com/home).* *This is not just a theoretical discussion but a significant improvement and actually essential for Dydra.* *I explain how triples can be stored in a very simply fashion in an SQL table and I show some simple SPARQL queries and how they translate to underlying RonDB index scans. All that combined with a simple interpreted program, bounded scans and retrieval of extra values. With the older `RecAttr` interface as well as the newer `Record` interface of the NDB API*. *So this article contains a lot of source code for a change. C++. SQL, SPARQL and Common Lisp.* ## A minimal NDB interpreted code program One very simple but at the same time very useful program consists of just one code word, in Lisp with `cl-ndbapi` it looks like this: ```lisp (let ((code-words 1)) (cffi:with-foreign-pointer (code-space (* code-words (cffi:foreign-type-size :unsigned-int))) (ndbapi.ic:with-code (code (cffi:null-pointer) code-space code-words) (ndbapi.ic:interpret-exit-last-row code) (ndbapi.ic:finalise code) ...))) ``` (Note: There was a short introduction to reading Lisp code in the first article of the series ["NDB interpreted code, cl-ndbapi, and the new NDB IC compiler"](https://blog.dydra.com/@datagenous/ndb-interpreted-code-cl-ndbapi-and-the-ndb-ic-compiler).) While in C++ with the ndbapi the same code looks like this: ```cpp const Uint32 codeWords = 1; Uint32 codeSpace[codeWords]; NdbInterpretedCode code(NULL, // Table is irrelevant &codeSpace[0], codeWords); if ((code.interpret_exit_last_row() != 0) || (code.finalise() != 0)) { NDB_ERR(code.getNdbError()); return NdbToolsProgramExitCode::FAILED; } ``` (This code snippet has been taken from `https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/tools/select_count.cpp`; copyright note for this code excerpt: `Copyright (c) 2003, 2024, Oracle and/or its affiliates.`) In both examples, first some space for the code is allocated big enough to hold just one instruction. Then the call to `interpret_exit_last_row()` puts that instruction in the code space as its first interpreter instruction. The second call `finalize()` on the other hand does not add an instruction instead it resolves all jumps, branch and subroutine calls. Usually, a scan iterates over all applicable rows. This little program instead just returns one single row only. (Well, actually one row per fragment as the tables are usually partitioned with RonDB and each partition is scanned in parallel, thus there is one scan per partition.) (To be more exact, [`interpret-exit-last-row`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbinterpretedcode.html#ndb-ndbinterpretedcode-interpret-exit-last-row) indicates that the current row is to be returned as part of the scan and that no more rows should be returned. But as the little interpreted program above just calls `interpret-exit-last-row` unconditionally and for the first row already without any more elaborate flow control, only this single row is returned.) ## Row count of a table Why would such a program be useful? Well, there are the special *pseudo columns* that you can return instead of the actual columns, as documented in the section ["Get special values"](https://docs.rondb.com/rondb_ndb_api/#get-special-values). One such candidate is: ```cpp ROW_COUNT This returns the current number of rows in the partition. A row is seen in this view when the row insert has committed. It is a 64-bit column. ``` And that is exactly what the ndb tool [ndb_select_count](https://dev.mysql.com/doc/refman/9.4/en/mysql-cluster-programs-ndb-select-count.html) uses to determine "the number of rows in one or more NDB tables" efficiently. First, it sets up the short interpreted code mentioned above, that just consists of `interpret-exit-last-row` (in [line 135](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/tools/select_count.cpp#L135)), and then it access the *pseudo column* `ROW_COUNT` (in [line 181](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/tools/select_count.cpp#L181)): ```cpp Uint64 tmp; // ... pOp->getValue(NdbDictionary::Column::ROW_COUNT, (char *)&tmp); // ... check = pTrans->execute(NdbTransaction::NoCommit); if (check == -1) { NDB_ERR(pTrans->getNdbError()); pNdb->closeTransaction(pTrans); return NdbToolsProgramExitCode::FAILED; } Uint64 row_count = 0; int eof; while ((eof = pOp->nextResult(true)) == 0) { row_count += tmp; } // ... pNdb->closeTransaction(pTrans); if (count_rows != NULL) { *count_rows = row_count; } return NdbToolsProgramExitCode::OK; ``` And thus one can efficiently determine the total number of rows: one scan per partition but each only returns this one *pseudo column* value, which you just have to add up to acquire the total. ## Range estimations Quite nice, but not what we needed for [Dydra](https://dydra.com) at Datagraph GmbH. So that was the easy part and not comes the harder part, and the longer part of this article, to adapt the example to our needs. Our SPARQL processor [SPOCQ](http://docs.dydra.com/faq#what-technologies-is-dydra-built-on) needs to know the cardinalities of graph patterns to steer its query optimization. So we do not need full table counts but bounded scans. Remember that a row in a RonDB table is a RDF statement for us, the row has five columns: subject (S), predicate (P), object (O), context or graph (C/G), and visibility which encodes the revision history of the statement. A graph pattern is translated to a bounded scan with the [NDB API](https://docs.rondb.com/rondb_ndb_api/). And as we have multiple indexes for each combination of the quad patterns, we have six individual indexes. And the scan needs to be on the particular index not on the underlying table. So that is the second thing that needs to be changed so that we could use this NDB API query to improve SPOCQ. ### A RonDB table to store quads This is too abstract, so let's show how this actually looks in RonDB and with its NDB API! A simple triple store graph repository without revisions could be created with this SQL call: ```sql create table test (g int unsigned not null, s int unsigned not null, p int unsigned not null, o int unsigned not null, index gspo (g,s,p,o), index gpos (g,p,o,s), index gosp (g,o,s,p), index spog (s,p,o,g), index posg (p,o,s,g), index ospg (o,s,p,g), unique (g,s,p,o)); ``` As an optimization we can turn the first index into a primary index and get rid of the extra unique definition: ```sql create table test (g int unsigned not null, s int unsigned not null, p int unsigned not null, o int unsigned not null, primary key (g,s,p,o), index gpos (g,p,o,s), index gosp (g,o,s,p), index spog (s,p,o,g), index posg (p,o,s,g), index ospg (o,s,p,g)); ``` ### SPARQL query with a graph clause Now let as a look at a simple SPARQL query. Here is one that will select all triples of one particular graph named ``: ```sql select ?s ?p ?o where { graph { ?s ?p ?o } } ``` Internally, Dydra interns all terms and then uses term IDs to refer to the terms. The term `` is interned as ID `54316`. This will result scan for the quad pattern `(54316 0 0 0)` against the index `(0 1 2 3)`, which is the primary index also called GSPO, that is, the order is graph, subject, predicate, object. In SPOCQ, this will translate to an NDB API [`NdbTransaction::scanIndex()`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbtransaction.html#ndb-ndbtransaction-scanindex) without partition pruning, without multiple bounds and with the `SF-ORDER-BY` flag set to true. There will be one [`NdbIndexScanOperation::IndexBound`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbindexscanoperation.html#ndb-ndbindexscanoperation-indexbound) for the bounded scan: ```cpp bound 0: low-key: (54316 0 0 0) low-key-count: 1 low-inclusive: t high-key: (54316 0 0 0) high-key-count: 1 high-inclusive: t range-no: 0 ``` ### SPARQL query against the default graph A SPARQL query without a graph clause will use the default graph: ```sql select ?s ?p ?o where { ?s ?p ?o } ``` As we indicate the default graph with `-1`, which in the two's complement is hexadecimal `#xFFFFFFFF` or `4294967295` as a decimal number. So instead of the term OD `54316` of the previous query, this query will use the pseudo term ID `-1` or `4294967295`. The rest is the same: The query will result scan for the quad pattern `(4294967295 0 0 0)` against the index `(0 1 2 3)`, which is the primary index also called GSPO, that is, the order is graph, subject, predicate, object. And in SPOCQ, this will translate to an NDB API index scan without partition pruning, without multiple bounds and with the `SF-ORDER-BY` flag set to true. There will be one index bound for the bounded scan: ```cpp bound 0: low-key: (4294967295 0 0 0) low-key-count: 1 low-inclusive: t high-key: (4294967295 0 0 0) high-key-count: 1 high-inclusive: t range-no: 0 ``` ### SPARQL query with given graph and predicate It will be more interesting when we fill in a second position of the quad pattern, e.g. the predicate: in this case the keyword `a`, which is the shorthand for the RDF IRI `http://www.w3.org/1999/02/22-rdf-syntax-ns#type`: ```sql select ?s ?o where { graph { ?s a ?o } } ``` The query will result scan for the quad pattern `(54316 0 1 0)` against the index `(0 2 3 1)`, which is the GPOS index, which is in the order graph, predicate, object, subject. Which is correct, as we have now graph and predicate specified in the query. And in SPOCQ, this will again translate to an NDB API index scan without partition pruning, without multiple bounds and with the `SF-ORDER-BY` flag set to true. And the one index bound for the bounded scan is: ```cpp bound 0: low-key: (54316 1 0 0) low-key-count: 1 low-inclusive: t high-key: (54316 1 0 0) high-key-count: 1 high-inclusive: t range-no: 0 ``` Notice here that it is not `(54316 0 1 0)` anymore, but now it is `(54316 1 0 0)`. This is very important as we have now selected the index GPOS and this one has the predicate at the second position! That is the whole reason we have this extra index, and in fact six indexes in total: to be able to do a bounded scan against it which will result in all quads for that particular quad pattern! ### Back to the row count… And there is one more thing that is suboptimal about [`select-count` tool](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/tools/select_count.cpp), which computes the row count of a table, and that is that it uses the older `RecAttr` interface, not the newer `Record` interface of the NDB API. Refer to the ["NDB API Example Comparing RecAttr and NdbRecord"](https://dev.mysql.com/doc/ndbapi/en/ndb-examples-recattr-vs-ndbrecord.html) of the MySQL documentation for a comparison. And you cannot mix both interfaces. So I had to translate from `RecAttr` to `Record`, set up bounded scans and then get access to the counts for the scans somehow. Ah, and we do not scan against the table but against an index. That was all not quite straightforward. I found the documentations a bit lacking, so I had to progress step by step and try to get it work. Back then, RonDB and the NDB API were still quite new to me. In summary, these three things needed to be different: 1. scan against an index not the full table, 2. allow for bounded scans, and 3. use the newer `Record` interface. *Note: If you are not interested in problems but just in solutions, just skip directly to the next section ["Final version of the scan-count example"](#final-version-of-the-scan-count-example).* That turned to be a bigger task than I anticipated and I struggled for a few days, hitting a wall several times. In the following I'll describe a bit these of my struggles. Not everything was easy and learning something new is sometimes hard. Especially, when you do something new in a different language and documentation is scarce on that particular topic and even fewer examples. That is at least three three obstacles at the same time. With the newer `Record` API, I could not read the "pseudo column" `NdbDictionary::Column::ROW_COUNT`, which is supposed to return the "Read row count (committed)" according to a comment in [`AttributeHeader.hpp`](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/include/kernel/AttributeHeader.hpp#L52). So that was the state of the example in [commit 8bee3534db](https://github.com/datagraph/cl-ndbapi/commit/8bee3534dba9a247da2308e903414340223c75a3) on Oct 31, 2022. I changed the example to the older `RecAttr` interface in [commit 38e965649b](https://github.com/datagraph/cl-ndbapi/commit/38e965649b1c792f3d62a151de23865cd27e5e0f) but only got the error: ```cpp set-bound() failed: Error with code 4284: Cannot mix NdbRecAttr and NdbRecord methods in one operation ``` In order to proceed, I switched to the ["old API" variant of `setBound`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbindexscanoperation.html#ndb-ndbindexscanoperation-setbound) in [commit 063b43d1ad](https://github.com/datagraph/cl-ndbapi/commit/063b43d1ad86dbc306988a8ea4e42619f2063e23), as a working basis to try accessing `ROW_COUNT` with the old API. I added the values of "Pseudo Columns" listed in class Column in `rondb/storage/ndb/include/ndbapi/NdbDictionary.hpp` in [commit 85357e3669](https://github.com/datagraph/cl-ndbapi/commit/85357e36698d53f4884434259b62013511e76b3b) and changed the example in [commit 59e98d9d1b](https://github.com/datagraph/cl-ndbapi/commit/59e98d9d1b54593dbb144baa87cd93b8bf783fe6) as described in this comment: ```cpp try adding retrieval of column count via get-value of (ndbapi:pseudo-columns.+row-count+) and reading the result value via count-ptr ``` but that was not allowed as I got the error: ```cpp ndb-scan-operation-set-interpreted-code() failed: Error with code 4004: Attribute name or id not found in the table ``` One really has to use the [`static const Column`s defined in `NdbDictionary.hpp`](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/include/ndbapi/NdbDictionary.hpp#L696) but these are only defined when [`NdbColumnImpl::create_pseudo_columns()` is called](https://github.com/logicalclocks/rondb/blob/24.10-main/storage/ndb/src/ndbapi/NdbDictionaryImpl.cpp#L410), as I commented in [commit 042349af51](https://github.com/datagraph/cl-ndbapi/commit/042349af51f2524b3805e6724fd4f5f4c90d1d35): ```lisp /* Note: The pseudo columns as NdbDictionary::Column::ROW_COUNT * are created by NdbColumnImpl::create_pseudo_columns(), * which is called when making a cluster connection (specifically in * function Ndb_cluster_connection_impl::Ndb_cluster_connection_impl()). * So it is only available in the context of a cluster connection. * Sadly, there is no accessor function so we define our own here. * One would never want to change its value from the outside, * so this direction suffices. */ ``` I did this change in [commit 67b6c3f94e](https://github.com/datagraph/cl-ndbapi/commit/67b6c3f94ec2f30077f28470ca2fbed6bc94d2c9) and generalized it to all `pseudo columns` in [commit 70d56cdfea](https://github.com/datagraph/cl-ndbapi/commit/70d56cdfeab130a253b8632743f7414c2c171cd4) and that worked finally. But it uses [`getValue()`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndboperation.html#ndb-ndboperation-getvalue) so only works with the `RecAttr` interface. And most importantly, if I remember correctly, now that I write this article three years later in 2025, it did still return full table counts not bounded ones. I was almost giving up again. The solution offered itself when reading the RonDB's documentation again and especially the section ["Get special values"](https://docs.rondb.com/rondb_ndb_api/#get-special-values): The solution is to not to use `ROW_SIZE` but instead the 2nd value of `RECORDS_IN_RANGE` as documented in the section [`RECORDS_IN_RANGE`](https://docs.rondb.com/rondb_ndb_api/#records_in_range), which contains the number of rows in the range. One important thing to note though is that the values of `RECORDS_IN_RANGE` are all only estimations. But as we just want to steer SPOCQ's query optimization that is good enough for us. ### Final version of the `scan-count` example A working version using the old `RecAttr` interface you'll find in the file [`ndbapi-scan-count-recattr.lisp`](https://github.com/datagraph/cl-ndbapi/blob/main/examples/ndbapi-scan-count-recattr.lisp), and that I was able to translate that one back into a working version using the newer `Record` API. You'll find that one in the file [`ndbapi-scan-count.lisp`](https://github.com/datagraph/cl-ndbapi/blob/main/examples/ndbapi-scan-count.lisp). Let's now look at the source code in that file. I'll just copy the source code and add a few explanations. These explanations are in *italic font*. *First the copyright notice and changing to the right package, followed by a short description where this code comes from and what it does differently:* ```lisp ;;; Copyright (c) 2022 Max-Gerd Retzlaff , Datagraph GmbH. ;;; Distributed under the terms of the GNU General Public License, Version 2.0, ;;; see file LICENSE in the top level directory of this repository. (in-package :ndb.scan-count) ;; based on the NDB cluster command ndb_select_count - Print Row Counts for NDB Tables ;; and its implementation in rondb/storage/ndb/tools/select_count.cpp ;; but modified to the second value column records-in-range, which is the number ;; of rows in range, instead of column row-count, as we want to do counts of ;; bounded scans not full table counts ``` *Then a long comment describing what it does:* ```lisp ;; what it does is: ;; 1. set up a small interpreted code so that for our scanning operation ;; each each fragment (or partition) returns only one row (interpret-exit-last-row) ;; 2. in the scan options specify an extra get value for pseudo column records-in-range ;; and give it space for the for uint32 values it will return as app-storage ;; 3. in the scan index call: specify a result-mask mask of 0 as :unsigned-char ;; so that actually no columns of the underlying table will be extracted ;; (Note: I hope that actually means that only the index is used and the ;; underlying table are not accessed at all. That would be good.) ;; 4. ndbapi:ndb-scan-operation-next-result will have one round per partition ;; now and each round will have the four values of records-in-range set; ;; the second value will hold the "number of rows in the range" ;; (We still have to call the three arguments version of ;; NdbScanOperation::nextResult() with a pointer for the row-data ;; as the second value, as the two argument versions are part of the ;; recattr API and using those will lead to error: "Error with code 4284: ;; Cannot mix NdbRecAttr and NdbRecord methods in one operation". ;; So we have to specify the row-data pointer, but as we have configured ;; 0 as the result-mask no rows will actually get retrieved.) ;; 5. we get the number of rows in our range from each partition, ;; summing them up will result in the total matching columns ;; ;; Warning: This gives only an estimate of the counts! ;; See rondb/storage/ndb/src/kernel/blocks/dbtux/DbtuxStat.cpp ;; explaining records-in-range as: ;; ;; // RECORDS_IN_RANGE ;; ;; /* ;; * Estimate entries in range. Scan is at first entry. Search for last ;; * entry i.e. start of descending scan. Use the 2 positions to estimate ;; * entries before and after the range. Finally get entries in range by ;; * subtracting from total. Errors come from imperfectly balanced tree ;; * and from uncommitted entries which differ only in tuple version. ;; * ;; * Returns 4 Uint32 values: 0) total entries 1) in range 2) before range ;; * 3) after range. 1-3) are estimates and need not add up to 0). ;; */ ;; ;; Copyright of this extract of 12 lines of the RonDB source code ;; in the file rondb/storage/ndb/src/kernel/blocks/dbtux/DbtuxStat.cpp: ;; Copyright (c) 2005, 2019, Oracle and/or its affiliates. All rights reserved. ``` *A short description that for exact counts, the [simple-scan example](https://github.com/datagraph/cl-ndbapi/blob/main/examples/ndbapi-simple-scan.lisp) can simply be used instead with the `:just-count` flag set to `t` (=true):* ```lisp ;; An exact count could be achieved by not using the interpreted code, ;; still extract no columns and just add up 1 per round of ;; ndbapi:ndb-scan-operation-next-result. Without interpret-exit-last-row ;; next-result will not be called once per partition but once per column. ;; This is actually implemented in simple-scan.lisp when calling ;; simple-scan:simple-scan with :just-count t in the argument list. ``` *A comment detailing how the example table can be created by executing a `SQL` query (e.g. in the `mysql` shell program):* ```sql #| create table as: create table test (g int unsigned not null, s int unsigned not null, p int unsigned not null, o int unsigned not null, index gspo (g,s,p,o), index gpos (g,p,o,s), index gosp (g,o,s,p), index spog (s,p,o,g), index posg (p,o,s,g), index ospg (o,s,p,g), unique (g,s,p,o)); load data with: load data infile '/path/to/data.tsv' into table test; |# ``` *The [data.tsv](https://github.com/datagraph/cl-ndbapi/blob/main/examples/data.tsv) is also included in the repository.* *First the function definition:* ```lisp (defun scan-count (&key connection-string database-name table-name index-name bound-specs ;; list of specs: (&key low high (low-inclusive t) (high-inclusive t)) debug (lock-mode :+lm-committed-read+) ;; might switch to: :+lm-committed-read+ or other modes ) "WARNING: scan-count just gives an estimation of the matching rows. If you need an exact count call simple-scan instead with :just-count t" ``` *Ensuring that the NDB API library has been loaded, `ndb_init` has been called, making an `ndb-cluster-connection`, and making an `ndb` object, which is bound to `ndb` for the context of the `ndbapi:with-ndb` form:* ```lisp (ndbapi:ensure-ndb-api-initialisation) (ndbapi:with-ndb-cluster-connection (ndbapi:*connection* (connection-string) :name "ndbapi-scan-count") (ndbapi:with-ndb (ndb (ndbapi:*connection* database-name)) ``` *Create the interpreted code object:* ```lisp (let ((code-words 1)) (cffi:with-foreign-pointer (code-space (* code-words (cffi:foreign-type-size :unsigned-int))) (ndbapi.ic:with-code (code (cffi:null-pointer) code-space code-words) (ndbapi.ic:interpret-exit-last-row code) (ndbapi.ic:finalise code) ``` *Create the transaction and retrieve some objects, also defines the local variable `scan-flags`, which is here set to a constant list of just the [`ScanFlag`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbscanoperation.html#ndb-ndbscanoperation-scanflag) SF-MULTI-RANGE:* ```lisp (ndbapi:with-ndb-transaction (transaction ndb) (let* ((dict (ndbapi:ndb-get-dictionary ndb)) (table (ndbapi:dictionary-get-table dict table-name)) (index (ndbapi:dictionary-get-index dict index-name (ndbapi:table-get-name table))) (index-default-record (ndbapi:index-get-default-record index)) (table-default-record (ndbapi:table-get-default-record table)) (scan-flags '(:+SF-MULTI-RANGE+))) ``` *Allocate some memory to hold the result of `records-in-range`, allocate struct [`get-value-spec`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndboperation.html#ndb-ndboperation-getvaluespec), introduce the local variable `extra-get-values` for it and make it to retrieve the column `records-in-range`:* ```lisp (cffi:with-foreign-object (records-in-range-ptr :uint32 4) (ndbapi:with-foreign-struct (extra-get-values (list :column (ndbapi:column-records-in-range) :app-storage records-in-range-ptr :rec-attr (cffi:null-pointer) ;; next two lines are strictly necessary ;; starting with rondb 24.10 ;; to avoid error with code 4566 :m-start-pos 0 :m-size 0) '(:struct ndbapi:get-value-spec)) ``` *Allocate a struct [`scan-options`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbscanoperation.html#ndb-ndbscanoperation-scanoptions), call it `scan-options` with scan options `so-scanflags`, `so-getvalue` and `so-interpreted` and set the options to the already created objects `scan-flags`, `extra-get-values` and the code object:* ```lisp (ndbapi:with-foreign-struct (scan-options (list :options-present '(:+SO-SCANFLAGS+ :+SO-GETVALUE+ :+SO-INTERPRETED+) :scan-flags scan-flags :extra-get-values extra-get-values :num-extra-get-values 1 :interpreted-code (ndbapi:foreign-pointer code)) '(:struct ndbapi:scan-options)) ;;(break "~a" (cffi:convert-from-foreign scan-options '(:struct ndbapi:scan-options))) ``` *Allocate a `result-mask` that will not retrieve any columns:* ```lisp (cffi:with-foreign-object (result-mask :unsigned-char) (setf (cffi:mem-ref result-mask :unsigned-char) #b00000000) ``` *Call [`scanIndex()`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbtransaction.html#ndb-ndbtransaction-scanindex), name the returned scan index operation `scan`:* ```lisp (ndbapi:with-ndb-transaction-scan-index (scan (transaction index-default-record table-default-record lock-mode result-mask (cffi:null-pointer) scan-options (cffi:foreign-type-size '(:struct ndbapi:scan-options))) (t)) ``` *Set the bounds for the bounded scans for the quad pattern, as a bound specification of form `(&key low high (low-inclusive t) (high-inclusive t))`:* ```lisp ;; set bounds for scan (let ((bounds-count (length bound-specs))) (cffi:with-foreign-objects ((low-quads '(:struct ndb.quads:quad) bounds-count) (high-quads '(:struct ndb.quads:quad) bounds-count) (bounds '(:struct ndbapi:index-bound) bounds-count)) (loop for bound-spec in bound-specs for i from 0 do (destructuring-bind (&key low high (low-inclusive t) (high-inclusive t)) bound-spec (setf (cffi:mem-aref low-quads '(:struct ndb.quads:quad) i) (ndb.quads:list-to-quad low) (cffi:mem-aref high-quads '(:struct ndb.quads:quad) i) (ndb.quads:list-to-quad high) (cffi:mem-aref bounds '(:struct ndbapi:index-bound) i) (list :low-key (cffi:mem-aptr low-quads '(:struct ndb.quads:quad) i) :low-key-count (length low) :low-inclusive low-inclusive :high-key (cffi:mem-aptr high-quads '(:struct ndb.quads:quad) i) :high-key-count (length high) :high-inclusive high-inclusive :range-no i)) (let ((bound (cffi:mem-aptr bounds '(:struct ndbapi:index-bound) i))) (ndbapi:ndb-index-scan-operation-set-bound scan index-default-record bound)))) ``` *Execute the transaction and thus do the index scan:* ```lisp ;; execute transaction (ndbapi:ndb-transaction-execute transaction :+NO-COMMIT+))) ;; explicitly check for errors ;; as there might still be errors even though the execute call itself was successful ;; Update: this is done by ndbapi:ndb-transaction-execute already now (20221213 mgr). ;; (ndbapi:explicitly-check-for-transaction-error transaction) ``` *Collect results in a loop:* ```lisp ;; do scan and print (when debug (format t "~&table: ~a" table-name)) ``` *Introduce a local variable `total-row-count`:* ```lisp (let ((total-row-count 0)) ``` *Allocate a pointer `row-data` to point to the current row:* ```lisp (cffi:with-foreign-object (row-data :pointer) ``` *Call [`nextResult`](https://dev.mysql.com/doc/ndbapi/en/ndb-ndbscanoperation.html#ndb-ndbscanoperation-nextresult) which options `fetchAllowed` set to `t` (=true) and `forceSend` to `nil` (=false):* ```lisp (loop for rc = (ndbapi:ndb-scan-operation-next-result scan row-data t nil) for j from 0 ``` *While the return code of `nextResult` is zero, meaning "Another tuple has been received":* ```lisp while (zerop rc) ``` *Access the second value of the returned `records-in-range`at index `1` and store in local variable `range-count`:* ```lisp for range-count = (cffi:mem-aref records-in-range-ptr :uint32 1) ;;for row = (ndb.quads:convert-foreign-quad (cffi:mem-aref row-data :pointer)) do (when debug (let ((partition-count (cffi:mem-aref records-in-range-ptr :uint32 0)) (before-count (cffi:mem-aref records-in-range-ptr :uint32 2)) (after-count (cffi:mem-aref records-in-range-ptr :uint32 3))) (format t "~&~t#partition: ~8d~t#range: ~8d~t#before: ~8d~t#after: ~8d" partition-count range-count before-count after-count))) ``` *Increase `total-row-count` by `range-count`:* ```lisp (incf total-row-count range-count) ``` *Check at the end if all is good, that is if the last return code returned by `nextResult()` was `1`, meaning "There are no more tuples to scan". Any other value means an error had occurred:* ```lisp finally (assert (= rc 1) () "scan-operation-next-result() failed: ~a" (ndbapi:get-ndb-error transaction #'ndbapi:ndb-transaction-get-ndb-error)))) ``` *Return the total count:* ```lisp total-row-count)))))))))))))) ``` *The rest of the file just contains example calls, all commented out with `#+(or)` so that they are not executed when compiling the file:* ```lisp #+(or) (let ((args (list :connection-string "localhost:1186,localhost:1187" :database-name "mgr" :table-name "test" :index-name "gspo"))) (list (apply #'ndb.simple-scan:simple-scan args) (apply #'ndb.simple-scan:simple-scan :just-count t args) (apply #'ndb.scan-count:scan-count :debug t args))) #+(or) (let ((args (list :connection-string "localhost:1186,localhost:1187" :database-name "mgr" :table-name "test" :index-name "ospg" :bound-specs '((:low (1106 1105 638 1105) :low-inclusive t :high (1109 1106 1108 1105) :high-inclusive t))))) (list (apply #'ndb.simple-scan:simple-scan args) (apply #'ndb.simple-scan:simple-scan :just-count t args) (apply #'ndb.scan-count:scan-count :debug t args))) #+(or) (let ((args (list :connection-string "localhost:1186,localhost:1187" :database-name "mgr" :table-name "test" :index-name "gpos" :bound-specs '((:low (1105 2000000) :low-inclusive t :high (1105 2200000) :high-inclusive t))))) (list (apply #'ndb.simple-scan:simple-scan args) (apply #'ndb.simple-scan:simple-scan :just-count t args) (apply #'ndb.scan-count:scan-count :debug t args))) #+(or) (let ((args (list :connection-string "localhost:1186,localhost:1187" :database-name "mgr" :table-name "test" :index-name "ospg" :bound-specs '((:low (1109 1106 1137) :low-inclusive t :high (2108202 1106 603481) :high-inclusive t))))) (list (apply #'ndb.simple-scan:simple-scan args) (apply #'ndb.simple-scan:simple-scan :just-count t args) (apply #'ndb.scan-count:scan-count :debug t args))) #+(or) (let ((args (list :connection-string "localhost:1186,localhost:1187" :database-name "mgr" :table-name "test" :index-name "ospg" :bound-specs '((:low (1106 1105 638 1105) :low-inclusive t :high (1109 1106 1108 1105 ) :high-inclusive t) (:low (600000) :low-inclusive nil :high (662743) :high-inclusive t))))) (list (apply #'ndb.simple-scan:simple-scan args) (apply #'ndb.simple-scan:simple-scan :just-count t args) (apply #'ndb.scan-count:scan-count :debug t args))) ``` *This is the file as of [commit 806b86a183](https://github.com/datagraph/cl-ndbapi/commit/806b86a183a7d9ab6e358ca663918d03f72da744), which is currently in the public repository as file [`ndbapi-scan-count.lisp`](https://github.com/datagraph/cl-ndbapi/blob/main/examples/ndbapi-scan-count.lisp).* ## Results So, let us look at a few scans to see the difference between the `scan-count`, which is just an estimation: ```lisp * (time (ndb.scan-count:scan-count :database-name "redacted°togovar-rondb-subject" :table-name "quads" :index-name "PRIMARY")) Evaluation took: 0.004 seconds of real time 0.000671 seconds of total run time (0.000485 user, 0.000186 system) 25.00% CPU 3,628,950 processor cycles 0 bytes consed 3252619378 ``` … and a full count, without transferring any actual column data from the RonDB data node to the SPOCQ data node: ```lisp * (time (ndb.simple-scan:simple-scan :database-name "redacted°togovar-rondb-subject" :table-name "quads" :index-name "PRIMARY" :just-count t)) Evaluation took: 563.845 seconds of real time 224.437368 seconds of total run time (212.529065 user, 11.908303 system) 39.80% CPU 1,406,785,291,800 processor cycles 1,485,296 bytes consed 3252619492 ``` This is a big database with 3.3 billion quads. It runs on a server with 1 TB of RAM. The estimation is run in negligible time of 0.004 seconds while the full count needs almost ten minutes (9 minutes, 23.8 seconds). The estimate is 141 thousand times faster, while it is off by 256 entries (of 3,252,619,492 in total). Let's estimate the count of all quads with keyword `a` as predicate, or RDF IRI `http://www.w3.org/1999/02/22-rdf-syntax-ns#type`, which happens to always have term ID `1` in Dydra: ```lisp * (time (ndb.scan-count:scan-count :database-name "redacted°togovar-rondb-subject" :table-name "quads" :index-name "psog" :bound-specs '((:low (1) :low-inclusive t :high (1) :high-inclusive t)))) Evaluation took: 0.004 seconds of real time 0.001416 seconds of total run time (0.001416 user, 0.000000 system) 25.00% CPU 6,708,350 processor cycles 2 page faults 0 bytes consed 292056083 ``` A real count of the same quads: ```lisp * (time (ndb.simple-scan:simple-scan :database-name "redacted°togovar-rondb-subject" :table-name "quads" :index-name "psog" :bound-specs '((:low (1) :low-inclusive t :high (1) :high-inclusive t)) :just-count t)) Evaluation took: 129.628 seconds of real time 21.025530 seconds of total run time (19.667508 user, 1.358022 system) 16.22% CPU 323,413,452,025 processor cycles 195,840 bytes consed 331013545 ``` 129.628 seconds vs. 0.004 seconds, the result is off by 38,957,462 entries, which is 11.8 %. These are extreme results for a big database. It's the corner case of a full table scan. Let as look on a more typical production database of 4.5 million quads on one of our development servers. Estimate: ```lisp IMPLEMENTATION> (time (ndb.scan-count:scan-count :database-name "mgr°plm-stats" :table-name "quads" :index-name "PRIMARY")) Evaluation took: 0.002 seconds of real time 0.001184 seconds of total run time (0.000000 user, 0.001184 system) 50.00% CPU 4,667,888 processor cycles 0 bytes consed 4474991 ``` Full count: ```lisp IMPLEMENTATION> (time (ndb.simple-scan:simple-scan :database-name "mgr°plm-stats" :table-name "quads" :index-name "PRIMARY" :just-count t)) Evaluation took: 0.437 seconds of real time 0.385666 seconds of total run time (0.385666 user, 0.000000 system) 88.33% CPU 1,052,493,662 processor cycles 0 bytes consed 4474991 ``` 0.437 seconds vs. 0.002 seconds and the result happens to be exact. Still 217 times faster. Let us count the triples in the graph ``, which is interned as term as ID `54316`, as in the SPARQL example above. Estimation: ```lisp (time (ndb.scan-count:scan-count :database-name "mgr°plm-stats" :table-name "quads" :index-name "PRIMARY" :bound-specs '((:low (54316) :low-inclusive t :high (54316) :high-inclusive t)) )) Evaluation took: 0.002 seconds of real time 0.001201 seconds of total run time (0.000494 user, 0.000707 system) 50.00% CPU 5,439,072 processor cycles 0 bytes consed 234 ``` Full count: ```lisp IMPLEMENTATION> (time (ndb.simple-scan:simple-scan :database-name "mgr°plm-stats" :table-name "quads" :index-name "PRIMARY" :bound-specs '((:low (54316) :low-inclusive t :high (54316) :high-inclusive t)) :just-count 1 )) Evaluation took: 0.002 seconds of real time 0.001191 seconds of total run time (0.001191 user, 0.000000 system) 50.00% CPU 4,990,752 processor cycles 0 bytes consed 255 ``` Okay, only 255 statements. Here the estimation is not faster (and off by 21 entries, or 8 %). But looking at all quads with keyword `a` as predicate, or RDF IRI `http://www.w3.org/1999/02/22-rdf-syntax-ns#type`, makes a difference again. Estimation: ```lisp IMPLEMENTATION> (time (ndb.scan-count:scan-count :database-name "mgr°plm-stats" :table-name "quads" :index-name "posg" :bound-specs '((:low (1) :low-inclusive t :high (1) :high-inclusive t)))) Evaluation took: 0.003 seconds of real time 0.001207 seconds of total run time (0.000497 user, 0.000710 system) 33.33% CPU 6,280,160 processor cycles 32,640 bytes consed 591102 ``` Full count: ```lisp IMPLEMENTATION> (time (ndb.simple-scan:simple-scan :database-name "mgr°plm-stats" :table-name "quads" :index-name "posg" :bound-specs '((:low (1) :low-inclusive t :high (1) :high-inclusive t)) :just-count 1 )) Evaluation took: 0.183 seconds of real time 0.129964 seconds of total run time (0.129964 user, 0.000000 system) 71.04% CPU 441,008,240 processor cycles 0 bytes consed 1110182 ``` 0.183 seconds vs. 0.003 seconds, which means the estimation is 61 times faster. The result is off by 519,080 quads, which is 47 %. Well, an error of almost 50 % is quite a bit, but it is still good enough for our purpose. As mentioned before, we use this estimation of counts to steer the query optimization of our SPARQL processor [SPOCQ](http://docs.dydra.com/faq#what-technologies-is-dydra-built-on), which needs to know the cardinalities of graph patterns. Given that the estimation is more or less instant, this is quite adequate, as the query optimization should, of course, help and not add a lot of overhead on its own. ## Next topics In the next article of [this series](/@datagenous/ndb-interpreted-code-article-series) we will look at the [NDB IC Compiler](https://github.com/datagraph/cl-ndbapi/tree/main/ndb-ic-compiler). 32:[{"id":"1bd8dadfe6bede78f5989a45bfac22bbebf39907efa0e2b0a3766b4111692beceb6885370cbffeeb5088759289f43e264ab944679bbd43041939c7e72aa31884","href":"https://static.observableusercontent.com/files/1bd8dadfe6bede78f5989a45bfac22bbebf39907efa0e2b0a3766b4111692beceb6885370cbffeeb5088759289f43e264ab944679bbd43041939c7e72aa31884","name":"Datagraph-a-very-short-ndb-interpreted-program.png","type":"image/png","lastModified":1763233983122.25,"size":352547}] 2f:{"id":"e2105cd9737a487e","slug":"a-very-short-ndb-interpreted-program","title":"A very short NDB interpreted program: row counts and range estimations","thumbnail":"fcd200e9abcbde4576ce41a2bccd9bd462b89e451bd6659ecb39f60cd1f5f655","access_level":"public","create_time":"$D2025-10-06T16:21:44.715Z","update_time":"$D2025-11-17T10:57:42.241Z","view_time":null,"first_public_time":"$D2025-11-17T10:08:22.432Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro"},"version":136,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"cc40bc930b0bd5be","login":"m-g-r","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3d8d3d6bceb13f29844542fa149f42aace63dab374dca089697458626fa9f5d3","tier":null}],"members":[{"type":"individual","id":"cc40bc930b0bd5be","login":"m-g-r","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3d8d3d6bceb13f29844542fa149f42aace63dab374dca089697458626fa9f5d3","tier":null,"role":"editor"},{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"A very short NDB interpreted program: row counts and range estimations","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":31,"value":"\n","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"