---
title: "R*Tree and dbstat"
url: https://recursiveai.org/onelite/docs/rtree/
description: "Behaviour of rtree, rtree_i32 and dbstat as OneLite implements it, with what was settled by observing the pinned shell. Results are compared with the…"
version: "0.2.0-preview.2"
source: https://github.com/recursive-ai-oss/onelite-csharp/blob/92cb7e5eaaecb9c126bddc298ffb3fc6b3d065b5/docs/rtree.md
---

# R*Tree and dbstat

Behaviour of `rtree`, `rtree_i32` and `dbstat` as OneLite implements it, with what was settled by observing the pinned shell. Results are
compared with the shell by `tools/OneLite.RTreeDiff` (seeded random scripts, statement by statement, then the shell's own checks on the file
OneLite wrote and OneLite's checks on the file the shell wrote) and by `tests/OneLite.Tests/Engine/RTreeTests.cs`.

## R*Tree

- **Shadow tables** are created in the order `%_rowid`, `%_node`, `%_parent` after the virtual table's own schema row (`rootpage` 0):
  `%_rowid(rowid INTEGER PRIMARY KEY,nodeno,a0,a1,...)` (one `aN` per auxiliary column), `%_node(nodeno INTEGER PRIMARY KEY,data)`,
  `%_parent(nodeno INTEGER PRIMARY KEY,parentnode)`. `%_node` starts with node 1, the root, as `pageSize - 64` zero bytes.
- **Node blob**: bytes 0-1 tree depth (meaningful in the root), bytes 2-3 cell count, then cells of `8 + 8 * dims` bytes: big-endian int64
  rowid (child node number above the leaves) and per dimension `min`, `max` as big-endian float32 (`rtree`) or int32 (`rtree_i32`).
  Observed: a node holds at most 51 cells whatever its size allows (the shell reports a node with more as corrupt); OneLite splits at 52.
- **Columns**: the first column is an INTEGER rowid (NULL assigns `max(rowid)+1`; other values go through the integer conversion, so `'7'` is 7
  and `'x'` is 0); `rowid` named in an INSERT or UPDATE is ignored in favour of the first column. `rtree` coordinates are REAL on the way out,
  `rtree_i32` INTEGER. Column names are the first token of each argument; `+name` marks an auxiliary column and must come last.
- **Coordinates in**: `rtree_i32` takes the low 32 bits of the integer conversion (observed: `1e300` and `9223372036854775807` both fail the
  `min <= max` check against a normal minimum). `rtree` converts to REAL; a value that is not exactly a float32 is moved outward by a relative
  2^-23 (lower bounds down, upper bounds up) and rounded to the nearest float32 (observed against the shell on 0.1, 3.7, 559.936, 592.297
  and 16777217; this is the "0.000012%" of the documentation).
- **Errors** (messages as the shell): `Too few columns for an rtree table`, `Too many columns for an rtree table` (more than 11 coordinate columns
  or 100 columns), `Wrong number of columns for an rtree table` (even number of coordinate columns), `Auxiliary rtree columns must be last`,
  `rtree constraint failed: T.(minCol<=maxCol)` (SQLITE_CONSTRAINT), `UNIQUE constraint failed: T.id` (message compared; the extended code is OneLite's choice, 1555, and has not been compared).
- **MATCH** with a geometry callback is not supported: no `rtree_geometry` or query callbacks are registered, and `x MATCH y` is not
  usable (the shell fails it with `SQL logic error`).
- **Scans**: constraints on coordinate columns (`=`, `<`, `<=`, `>`, `>=`) prune subtrees; an equality on the first column goes through
  `%_rowid`. The engine tests every term again on the returned rows (observed: `a = 0.1` finds nothing in a table holding the rounded value,
  as in the shell), so pruning only needs to keep every row that could match. Row order is the tree order and is not promised.
- **Writes**: the algorithm of Beckmann et al.: ChooseSubtree by least overlap enlargement above the leaves (the 32 best by area enlargement
  when there are more) and least area enlargement elsewhere; one forced reinsertion of the 30% of entries farthest from the node centre per
  level and insertion (closest first); otherwise the margin-sum axis and least-overlap distribution split with a minimum fill of 40%. A delete
  condenses as Guttman's: nodes under a third of capacity are dissolved and their entries reinserted, and a root with one child is lifted.
  The root stays node 1. **The shape of the tree, and so the shadow tables' bytes, differ from the shell's for the same SQL**; both are valid
  and answer every query alike, so `.dump` of two files built by the two engines matches for the table's content but not for `%_node`.
- **Suspension**: a change is planned in memory (reads of nodes, parent links and rowid rows that miss the cache throw an internal exception
  after starting the read, `Update` returns Pending, and the next call plans again from the start with the finished reads remembered), then
  written with one shadow-table write per step, each repeated with the same arguments after Pending. Scans keep their position in a stack of
  nodes and cell indexes, and load a child before moving past its cell.
- **Functions**: `rtreecheck([schema,] table)` returns `ok` or one line per problem (boxes ordered and inside the parent's, leaf cells and
  `%_rowid`, child cells and `%_parent`, row counts); the wording of problem lines is OneLite's own. `rtreedepth(blob)` and
  `rtreenode(ndim, blob)` as in the shell (`%g` coordinates).
- **Not done**: reading and writing at once (the shell fails the second with SQLITE_LOCKED; OneLite plans from a drained scan, so its UPDATE and
  DELETE do not meet that), geometry callbacks.

## dbstat

- Columns `name, path, pageno, pagetype, ncell, payload, unused, mx_payload, pgoffset, pgsize` and hidden `schema, aggregate`; eponymous, with
  `dbstat('schema', aggregate)` arguments; `CREATE VIRTUAL TABLE x USING dbstat(schema)` sets the default schema.
- B-trees in `sqlite_schema` row order, starting with the schema table itself (named `sqlite_schema`). Rows of a B-tree: a page, then for each
  cell its overflow chain (`path` `/001/000+000002`), then (for interior pages) the child; the right-most child last. The path of a child is the
  parent's path plus the 3-digit hexadecimal cell index and `/`.
- `payload` is the bytes of cell payload held on the page (the local part only), `mx_payload` the largest total payload length of a cell
  on the page, `unused` the gap before the cell content area, the freeblocks and the fragmented bytes. An overflow page reports the payload bytes
  it holds and `usable - 4 - payload` unused. Aggregate mode sums these per B-tree; `pageno` becomes the page count, `pgsize` pages times page size.
- Observed quirk reproduced: an overflow page's `pgoffset` is the offset of the page listed just before it.
- A scan reads all pages of the schema when it starts; unlike the R*Tree it is not suspendable (it waits on I/O inside `Filter`).