RetractorDB

RetractorDB is an Edge Signal Processing Engine (ESPE) designed to continuously process regular time series close to the data source. Its declarative RQL language describes transformations, aggregations, and rules; their results can be published live or materialized as artifacts that remain available for later inspection and correction. The system complements central time-series databases and stream-processing systems by reducing the volume of data sent to them, but it does not replace those systems.

The name combines two ideas. Retractor denotes a tool that extracts, separates, joins, and processes data contained in time series, while DB points to mechanisms familiar from databases: a declarative query language, schema descriptions, access methods, and persistent result storage. The origin of the name is explained in Why Was This Name Chosen for the System?.

This documentation leads from the mathematical foundations and the construction of RQL, through the system architecture, query compilation and execution, to application examples and reference appendices. First-time readers should follow the chapter order in the table of contents because later sections build on concepts introduced earlier. Readers looking for a specific solution can go directly to the relevant chapter, then use the examples and appendices as practical and reference material.

RetractorDB among neighboring fields

This chapter is a map, not a catalog. Instead of listing everything ever written about streams and signals, I show eight strands of research literature at whose intersection RetractorDB sits, and for each of them I answer three questions: what has this strand already solved, how does RetractorDB differ from it, and what does this strand not touch. Comparing them reveals the gap this project fills.

✅ Note

This system is an: Edge Signal Processing Engine. RetractorDB supports - rather than replaces - time-series databases (TSDB) and data stream management systems (DSMS): it works close to the signal source, pre-processes and filters high-frequency measurements using a declarative query language, keeps a partial, correctable record of past events and scheduled future ones in inspectable artifacts, and passes exact, deterministic results up the architecture - so that only reduced, already-processed streams reach the central architecture.

ℹ️ Info

Why did I place this chapter so early? Because an honest answer to the question “is this needed?” first requires showing what already exists. Most ideas in computer science have already been thought of once - reinventing the wheel wastes someone else’s effort. This chapter is my attempt to prove that this particular wheel has not, in fact, been invented yet.

Eight neighboring fields

The problem RetractorDB solves does not belong entirely to any single discipline. It lies at the intersection of eight strands:

I discuss them in turn, from the foundation toward the application.

Number theory: Beatty sequences and covering systems (1)

RetractorDB’s entire algebra rests on the Beatty sequence and its generalization by Fraenkel to rational numbers. I cite these results in Formal Foundations and Proofs. Here I’m interested in the broader backdrop: how this mathematics functions in the contemporary literature, and whether anyone has already applied it where I have.

Beatty sequences have a rich combinatorial literature and documented applications in aperiodic tilings (quasicrystals), periodic scheduling, computer vision (digital lines), and formal language theory [11]. The strand is alive: Schaeffer, Shallit, and Zorcic (2024) showed that a non-homogeneous Beatty sequence is synchronizable by a finite automaton, which leads to decidability of the first-order theory of these sequences [12]. For me, however, the most relevant work is that of Berger, Felzenbaum, and Fraenkel (1986) on disjoint covering systems based on rational Beatty sequences [13] - exactly the variant my de-interleaving is based on, and one I did not cite in the original paper.

What this strand does not touch: number theory studies these sequences as mathematical objects. It does not connect them to a database, to a stream-processing model, or to signal processing. It supplies bricks, not a building.

Task scheduling via Beatty sequences (2)

This is the strand I must discuss most honestly, because it uses the same proof machinery as my theorems - just for a different purpose. In the periodic-scheduling problem (so-called pinwheel scheduling), tasks with different repeat periods are distributed so that tasks with one repeat time land in time slots belonging to the first complementary Beatty sequence, and those with the other, into the second [14]. Recent work (2025) proves results on the Rayleigh/Beatty partition using identities on floor and ceiling functions of the type ⌈(m+l)a⌉ − ⌈ma⌉ [15] - almost identical, point for point, to the apparatus in my proof that de-interleaving satisfies Fraenkel’s postulates.

The conclusion, for me, is twofold. On one hand - this is independent confirmation that the approach is correct and natural; if someone else arrives, by the same road, at a working scheduling scheme, the foundation is solid. On the other - it narrows what I can call novel. “Beatty sequences for scheduling” already exists and is being actively published. Interestingly, my system uses this mathematics internally, precisely for task scheduling (see Query Execution) - but that’s not where the original contribution lies.

What this strand does not touch: scheduling treats sequences as a tool for allocating time slots to processors. It doesn’t build a data algebra on top of them, doesn’t use them to express operations on signals, and doesn’t create a query language.

Synchronous and cyclo-static dataflow (SDF/CSDF) (3)

In SDF, actors consume and produce statically known token counts, which makes it possible to derive a graph schedule before execution [26]. CSDF extends this model with cyclically changing production and consumption rates and supports static schedules and buffer bounds [27]. This is a mature model of declarative multirate dataflow, so neither rate analysis nor static scheduling is unique to RetractorDB.

SDF/CSDF can describe related multirate behavior, which justifies the “partial” assessment for lossless sample partition. A Beatty partition is not, however, a distinct semantic operator in those models. RetractorDB places that operator in a query language and connects it to persistent results.

What this strand does not touch: SDF/CSDF does not define this particular lossless partition of sample positions as the semantics of a query system or provide an artifact inspection and replay model around it.

Synchronous languages and clock calculi (4)

Synchronous languages describe periodic streams through clocks and can check their compatibility and derive required buffers and delays during compilation. In n-synchronous models, clock relations may have rational rate ratios, and the compiler takes over part of the synchronization burden [28]. This is one of the closest reference points for RetractorDB’s declarative boundary.

The object being described is different, however: a clock usually marks whether a value is present at a logical tick, whereas RetractorDB assigns a rational interval to a regular stream and uses it to form one ordered stream from two inputs.

What this strand does not touch: clock calculi primarily support the compilation of reactive programs. They do not carry this semantics into a query engine with public descriptors and persistent, replayable artifacts.

Digital signal processing: nonuniform sampling and filter banks (5)

Interleaving and de-interleaving meet DSP in the problem of working with streams at different sampling rates, but they are not simply another signal-reconstruction method. The closest bridge is the work of Samadi, Ahmad, and Swamy (2004), which formulates the perfect-reconstruction condition for nonuniform filter banks from the system’s response to delayed unit-step signals [16]. The broader strand includes periodic nonuniform sampling of band-limited signals [17] and filter banks with rational decimation factors (Kovačević and Vetterli) [18].

Number-theoretic constructions even show up there: Ramanujan filter banks extract periodic components of a signal [19]. But I have not found Beatty sequences or Fraenkel’s theorem specifically in this literature - and that’s part of the gap.

What this strand does not touch: the cited DSP methods reconstruct or transform signal values. They do not define this particular Beatty-based interleaving of sample positions or embed it in an artifact-producing query engine.

Data stream management systems (DSMS) (6)

On the database side, the canon is CQL from Stanford’s STREAM project (Arasu, Babu, Widom). In this model, a stream is a potentially infinite multiset of elements ⟨s, τ⟩, where s is a tuple and τ a timestamp [20]; query semantics is built on windows and stream↔relation mappings. A second close neighbor is the temporal algebra of Krämer and Seeger (the PIPES system), providing deterministic results for continuous queries and a rich set of transformation rules underlying optimization [21].

This is the proper reference point for my algebra and my expression rewrite rules. The difference, however, is fundamental and concerns the data model itself. CQL and PIPES build their semantics on the (s, τ) model - every tuple carries its own timestamp, and operators act through windows. I adopt a differential model (sₙ, Δ), with a rational, fixed value of Δ per stream, and I derive the operators that align streams with different Δ from number theory. This is not a cosmetic difference in syntax - it’s a different data model, leading to a different class of operators (interleaving, de-interleaving) and a different optimization method.

In deployment terms, the relationship is complementary rather than competitive: RetractorDB acts as an edge-level pre-processing and buffering stage, whose exact, deterministic results can feed a windowed DSMS.

What this strand does not touch: DSMS encompass both deterministic semantics and mechanisms for scaling, windows, out-of-order handling, and state management. The cited systems do not, however, define this particular lossless partition of regular sample positions using Beatty sequences or use number theory as the semantics of resampling.

Multi-query sharing and shared state (7)

Multi-query optimization has long reused common parts of query plans. More recent streaming systems also share maintained indexes and state across concurrent dataflows [29], while semantic normalization makes it possible to merge queries whose syntax or plan structure differs [30]. Automatic sharing is therefore not, by itself, a new contribution of RetractorDB.

In RetractorDB, this problem concerns materialized intermediate streams. The compiler may share them only after plan normalization and a compatibility check grounded in regular-series semantics. This is close to existing shared-state mechanisms, although the compatibility criterion here follows from the stream-rate model.

What this strand does not touch: the cited methods do not use rate alignment and a Beatty partition to normalize a plan before deciding whether to share. The detailed boundary of this comparison is beyond the scope of the system documentation.

Time-series systems (TSMS) and in-database DSP (8)

This is the narrowest niche - and the closest to RetractorDB’s actual goal. The canonical survey is Jensen, Pedersen, and Thomsen’s “Time Series Management Systems: A Survey” (IEEE TKDE, 2017) [22]. The Plato system described there is the closest real “DSP inside a database”: it combines an RDBMS with signal-processing methods, eliminating the need to export data to external tools like R or SPSS [22]. The other approaches to “signals in a database” boil down to approximation and compression - wavelet, dictionary, and shape-based representations.

These approaches focus on approximation, compression, or after-the-fact analytics. They do not make Beatty-based multiplexing of sample positions a first-class operator within a query algebra. RetractorDB does not compete with them on ingestion scale or retention: it runs ahead of a central system and supplies deterministic results and correctable artifacts.

What this strand does not touch: TSMS optimize ingestion scale, compression, and retention. DSP is a second-class citizen in them - an analytical add-on, not the core of the semantics.

The blank spot: where the contribution lies

The table below is a qualitative capability map, not evidence of priority or a claim that the review is complete. The final column concerns evaluation through inspectable artifacts or replay, not persistence alone. “Partial” denotes a related capability, not semantic equivalence.

The strongest neighbors in the execution-model dimension are SDF/CSDF and synchronous languages and clock calculi: they already provide multirate declarative dataflow, deterministic semantics, static schedules, or buffer inference. The multi-query strand is equally close along an axis not represented by the columns: it can share maintained state automatically and formulate preservation conditions for individual queries. Its “partial” entry understates that proximity because the table does not describe how the identity of a shared object is established.

RetractorDB’s integration scope is narrower: the system combines a Beatty-defined, exactly invertible partition of sample positions with a query compiler, a sequential slot runtime, and persistent artifacts that can be inspected and replayed. This describes the system’s architecture and semantics; it does not claim that the individual ingredients are new. RetractorDB does not claim hard real-time guarantees.

⚠️ Warning

Hence a real risk, which I point out directly: the scheduling community has been publishing this same Beatty/Fraenkel machinery in 2023–2025. The problem itself - together with the need for a declarative stream algebra and a continuous query language - was already formulated back in 2003–2005, in the context of computer-assisted fetal monitoring [25]; I laid the “covering systems ↔ stream alignment and DSP” bridge in a 2006 publication [3], but in a venue with low discoverability. If this result doesn’t reach well-cited circulation, the same bridge may be independently built and credited to someone else.

Methodological caveat

This is a targeted review, not a systematic one - based on searching across eight strands, not a full citation analysis. A “forward citation” review of Samadi’s paper [16] confirms the point: according to Semantic Scholar (as of July 2026), its only recorded citations are a paper on Gabor window design, two systems-theoretic papers on multirate systems, and the 2006 bridge paper itself [3] - none of them uses Beatty sequences or Fraenkel’s theorem. The closest use of this machinery outside number theory that I’m aware of is the construction of exponential Riesz bases from Beatty–Fraenkel sequences (Pfander, Revay, and Walnut) [24] - but that belongs to pure harmonic analysis and doesn’t touch filter banks or sample-rate conversion. What remains for full closure is a systematic review of the scheduling strand [14] and of the filter-bank literature as a whole; the query-sharing discussion cites representative mechanisms rather than attempting a complete catalog. If a use of Fraenkel’s theorem in multirate DSP exists, it narrows the scope of the novelty claim and should be accounted for here.

Mathematical Foundations

Mathematical Foundations

ℹ️ Info

Do you know what the Fields Medal is? It is an award given exclusively to outstanding mathematicians under the age of 40. It is called the mathematical Nobel Prize. Interestingly, no mathematician will ever receive the actual Nobel Prize - as per the founder’s wishes. John Charles Fields himself (1863-1932) was a Canadian mathematician. John Charles Fields had one doctoral student - Samuel Beatty (1881-1970).

In 1926, Samuel Beatty published the following theorem [1]:

If p, q are positive irrational numbers satisfying the relation

\[ \frac{1}{p}+\frac{1}{q}=1 \]

then the sequences

\[ \left\{ \left\lfloor np\right\rfloor \right\} _{n=1}^{\infty }=\left\lfloor p\right\rfloor ,\left\lfloor 2p\right\rfloor ,\left\lfloor 3p\right\rfloor ,\ldots \]

and

\[ \left\{ \left\lfloor nq\right\rfloor \right\} _{n=1}^{\infty }=\left\lfloor q\right\rfloor ,\left\lfloor 2q\right\rfloor ,\left\lfloor 3q\right\rfloor ,\ldots \]

partition the set of positive integers.

These two sequences partition the set of natural numbers. This means that given two irrational numbers satisfying the relation stated in the theorem, we can split the entire set of natural numbers into two disjoint sets (Fig. 1).

The Beatty theorem is a fascinating observation in its own right - but in computer systems we run into a problem with irrational numbers. Real numbers - despite the fact that some programming languages use the words Real or Float for the real-number type - have little in common with actual real numbers. The fundamental problem is that we don’t have them, and presumably never will.

And here our journey would have abruptly ended, were it not for another theorem. The situation changed dramatically thanks to a mathematician - Aviezri Siegmund Fraenkel (1926), who specializes in combinatorial aspects of game theory.

In 1969 he presented the following theorem [2]. The starting point is a parameterized Beatty sequence:

\[ \mathcal{B}(\alpha ,\alpha ^{\prime }):= \left( \left\lfloor \frac{n-\alpha^{\prime }}{\alpha }\right\rfloor \right) _{n=1}^{\infty } \]

This single definition generates an entire family of sequences. The theorem always concerns a pair of its instances with different parameters: the sequence

\[ \mathcal{B}(\alpha ,\alpha ^{\prime }) \quad\text{and}\quad \mathcal{B}(\beta ,\beta ^{\prime }):= \left( \left\lfloor \frac{n-\beta^{\prime }}{\beta }\right\rfloor \right) _{n=1}^{\infty } \]

These sequences partition the set ℕ if and only if the following five conditions are satisfied:

1.

\[ 0<\alpha<1 \]

2.

\[ \alpha+\beta=1 \]

3.

\[ 0\leq \alpha +\alpha ^{\prime }\leq 1 \]

4. If α is an irrational number, then:

\[ \alpha ^{\prime }+\beta ^{\prime }=0 \]

and

\[ k\alpha +\alpha ^{\prime }\not\in \mathbb{Z} \]

for

\[ 2\leq k\in \mathbb{N} \]

5. If α is a rational number (let q∈N be the smallest number such that qα∈N), then

\[ \frac{1}{q}\leq \alpha +\alpha ^{\prime } \]

and

\[ \left\lceil q\alpha ^{\prime }\right\rceil +\left\lceil q\beta ^{\prime}\right\rceil =1 \]

And that is exactly what we need! We don’t have irrational numbers, but rational numbers understood as the ratio of two natural numbers are something a computer can handle just fine.

In our case, I first built prototype equations in Python, and then started looking for mathematical foundations that looked similar and could serve as well-documented equations backed by formal proofs. Proofs, of course, carried out by more experienced mathematicians. Modest as my skills were, they were enough to identify these two publications as relevant to my ideas.

This document does not include formal proofs. That is why I present here only the equations and theorems actually used in the system. For the formal proofs, I refer the reader to my scientific publications [3].

Algebra of Regular Time Series

Algebra - understood as a construct consisting of a defined set and defined operations on it - forms the basis for the declarative query language developed here. Throughout the rest of this work, when referring to “the Algebra” (without a further qualifier) I mean the Algebra of regular time series. When I want to refer to Relational Algebra, I will state the qualifier explicitly.

I proposed [3] the following definition of a regular time series (the so-called data model), along with the following operations and definitions.

✅ Note

By a data stream we understand an ordered pair S := (s_n,∆) - where the first element is an ordered series of data and the second, denoted by the symbol delta, is the regular time interval between consecutive elements of the series.

We adopt a fixed indexing convention: stream indices run from zero, and element s_n carries an implicit, default timestamp of (n+1)·∆. In other words - the first element of the stream appears after a full interval ∆ has elapsed since the stream’s creation. The timestamp is not carried within the tuple; it is derived from the position n and the rate ∆. It is precisely this differential data model that distinguishes the system from classical DSMS, where a stream is a multiset of pairs ⟨s,τ⟩ with a timestamp attached to every tuple.

A data series defined this way is referred to in the system as a data stream. Such a regularly flowing set of data passing through the system, usually described by a data schema, contains fields of various types. Each reading occurs at an equal time interval between consecutive measurements. This construction resembles a digital signal more than an irregular data stream - however, referring to it as a “stream” throughout the rest of the research will prove justified.

ℹ️ Info

Note:
The terms “stream” and “time series” are used interchangeably in this work and mean the same thing.
Formally, in the scientific literature a stream is denoted as a set of pairs (a,t) - where a denotes a tuple, and t denotes its moment of registration or occurrence.
A stream allows tuples whose time t coincides for different tuples. In the case of a time series, we distinguish two types of series - regular and irregular.
- For irregular series - a series is a sequence of tuples ordered in time - {a_t,t_n}, where the time t_n is unique in the set for each tuple.
- A regular time series, on the other hand, can be described by a sequence of tuples and a regular time interval between their occurrences - ({a_t},D) - and it is this latter definition that forms the basis for further operations in the system developed here.

The operations that can be performed on such a data set are defined as follows:

• interleaving and de-interleaving
• sum and difference
• sequence shift
• aggregation and serialization

The interleaving operation involves two different data streams.

We define it as follows:

\[ c_{n}=\left\{ \begin{array}{cc} b_{n-\left\lfloor n z \right\rfloor } & \left\lfloor n z \right\rfloor =\left\lfloor \left( n+1\right) z \right\rfloor \\ a_{\left\lfloor n z \right\rfloor } & \left\lfloor n z \right\rfloor \neq \left\lfloor \left( n+1\right) z \right\rfloor% \end{array}% \right. , z =\frac{\Delta _{b}}{\Delta _{a}+\Delta _{b}},\Delta _{c}=% \frac{\Delta _{a}\Delta _{b}}{\Delta _{a}+\Delta _{b}} \]

The arguments of the interleaving operation are two data streams A and B, each with its own data arrival rate. The result is an output stream C - with a new rate, different from the two source rates, determined by the formula above.

We denote the operation with the symbol #.

We define the de-interleaving operation by means of two operations.

1. Left-hand de-interleaving, producing stream A in the form:

\[ a_{n} = c_{n+ \left\lceil \frac{(n+1)\Delta _{a}}{\Delta _{b}} \right\rceil },\ \Delta _{a}=\frac{\Delta _{c}\Delta _{b}}{\left\vert \Delta _{c}-\Delta _{b}\right\vert } \]

2. Right-hand de-interleaving, producing stream B in the form:

\[ b_{n} = c_{n+\left\lfloor \frac{n\Delta_{b}}{\Delta_{a}}\right\rfloor},\ \Delta_{b}=\frac{\Delta_{c}\Delta_{a}}{\left\vert \Delta_{c}-\Delta_{a}\right\vert } \]

We denote de-interleaving operations 1 and 2 with the symbols & and %.

The argument of the de-interleaving operation is an interleaved data stream together with a rational number specifying the arrival rate of the stream being extracted. The result of the operation is a data stream with the rate determined by the formula above.

The interleaving and de-interleaving operations are complementary. This means they resemble multiplication and division on the set of natural numbers. Multiplication yields a single result, whereas division sometimes leaves a remainder; what matters is also what we divide by, and in what order.

I defined the sum operation as follows:

\[ c_{n}=\left\{ \begin{array}{cc} a_{n}|b_{ \left\lfloor \frac{n\Delta_{a}}{\Delta_{b}} \right\rfloor } & \Delta_{a}\leq \Delta_{b} \\ a_{ \left\lfloor \frac {n\Delta_{b}}{\Delta_{a}} \right\rfloor }|b_{n} & \Delta_{a}>\Delta_{b} \end{array} \right. ,\Delta_{c}=\min \left( \Delta_{a},\Delta_{b}\right) \]

The faster stream dictates the rate of the result: each of its elements is joined (the symbol | denotes tuple concatenation) with the element occupying the co-indexed slot of the slower stream.

The difference, on the other hand, is described by the formula:

\[ a_{n}=\left\{ \begin{array}{cc} c_{n} & \Delta_{b}\geqslant \Delta_{a} \\ c_{\left\lceil \frac{n\Delta_{a}}{\Delta_{b}}\right\rceil } & \Delta_{b}<\Delta_{a} \end{array} \right. \]

We denote these operations with the symbols + and -.

Causal execution augments the mathematical stream S = (s_n, ∆) with a logical origin O_S ∈ ℕ and a startup tail W_S ∈ ℕ. The logical origin is the index of the first record that exists at all; the tail is the number of subsequent slots for which an existing record is not yet ready. Neither kind of slot is a record: the engine inserts neither zeros nor all-null placeholders.

\[ \widehat{S} := \left((s_n,\Delta),O_S,W_S\right) \]

We define the shift as a read of an older index: output record \(n\) carries the contents of producer record \(n-m\). In the causal realization:

\[ O_{\tau_m(S)}=O_S+m, \qquad W_{\tau_m(S)}=\max(0,W_S-m), \qquad m\in\mathbb{N} \]

A shift neither discards source elements nor creates a prefix. It moves delay into the logical origin, while reading an older record can absorb part of the producer’s tail. The compiler reports both quantities as origin= and tail=. The runtime emits no records in any silent slot, of which there are origin + tail. Details: Tails, logical origins and operator observability.

I denote the shift operation with the symbol >.

The last operation within the defined algebra is the aggregation and serialization operation - abbreviated as Agse. Although it may look like two separate operations, I have defined a two-argument operator implementing the logic of a sliding data window. The first argument is the window’s hop, the second is its width. The hop is a natural number specifying by how much the sliding data window must be shifted over the stream. We assume that the source data stream is split with respect to the data schema, which modifies its arrival rate. The window width is an integer, non-zero. Negative width values reverse the order in which the resulting elements are created, mirror-image fashion. Positive values preserve the sequential character of the sliding data windows created.

I denote the Agse operation with the symbol @.

To summarize, the algebra underlying the declarative query language is as follows:

\[ A_{rql}::=((s_n,\Delta_s), (\#,\&,\%,+,-,>,@)) \]

where the first element of the pair defining the algebra is the data model (s_n - the data series, ∆_s - its regular time interval), and the second is the set of operations formally defined on this data model.

Formal Foundations and Proofs

In the chapter on the algebra of regular time series I presented a set of operators together with the equations describing them. I deliberately omitted formal proofs there - I wanted to first show what the system does before explaining why it is allowed to do so. This page fills that gap. Here I gather the formal skeleton of the algebra: the connection between the stream operators and covering-system theory, along with proofs of the theorems underlying the correctness and optimization of query plans.

ℹ️ Info

The entire construction below stays within a single domain - the rational numbers. This is not a stylistic choice. It is the whole point. Beatty’s theorem needs irrational numbers, which a computer does not have. Fraenkel’s theorem lets us descend to rational numbers. The proofs on this page show that the interleaving and de-interleaving operations are a special case of Beatty sequences satisfying Fraenkel’s postulates - and are therefore realizable using rational numbers alone.

Covering systems as the foundation

The literature on covering systems [4] belongs to combinatorics and cryptanalysis within number theory. The problem under consideration is how to determine a partition of the set of positive natural numbers. We say that two sequences partition the set of positive natural numbers if the sets formed from the elements of these sequences have an empty intersection, and their union forms the set of positive natural numbers.

The basis for these considerations is the parameterized Beatty sequence. In its general form it is written using the floor function:

\[ \mathcal{B}(\alpha ,\alpha ^{\prime }) := \left( \left\lfloor \frac{n-\alpha ^{\prime }}{\alpha }\right\rfloor \right) _{n=1}^{\infty } \]

This single definition generates an entire family of sequences. Partition results always concern a pair of its instances with different parameters: we write the pair as B(α, α′) and B(β, β′), where the second notation denotes the complementary term.

The parameters of this sequence have a clear geometric interpretation:

• α denotes the density of the sequence,
• 1/α denotes the slope,
• α′ denotes the offset,
• −α′/α denotes the y-intercept (the point where it crosses the y-axis).

The Beatty theorem guarantees a partition of the set for irrational numbers. The Fraenkel theorem is a generalization that - crucially for us - also allows rational numbers, provided five postulates are satisfied (quoted in the introductory chapter). An accessible proof of Fraenkel’s theorem can be found in K. O’Bryant’s paper “Fraenkel’s partition and Brown’s decomposition” [23].

The remainder of this page boils down to a single idea: showing that the stream operators are, in essence, machines generating Beatty sequences that partition (cover) the set of natural numbers.

Tools: floor and ceiling properties

The proofs rely almost exclusively on the floor function (⌊x⌋ - the integer part) and the ceiling function (⌈x⌉ - the smallest integer not less than x). I therefore first present a set of identities that will be used repeatedly. Let x ∈ ℝ, and let C denote an integer:

\[ \left\lfloor x\right\rfloor = \left\lceil x\right\rceil \iff x \in \mathbb{Z} \]

\[ \left\lfloor x\right\rfloor + 1 = \left\lceil x\right\rceil \iff x \in \mathbb{R} \setminus \mathbb{Z} \]

The second of these identities carries over directly to Beatty sequences themselves. The ceiling variant of the sequence, B′_α(n) = ⌈nα⌉, is - for irrational α - merely a shifted version of the floor variant:

\[ B_{\alpha}^{\prime}(n) = \left\lceil n\alpha \right\rceil = \left\lfloor n\alpha \right\rfloor + 1 \]

In a true Beatty sequence α must be irrational, so nα is never an integer for any n > 0 - the premise of the second identity holds for every term, and the ceiling variant simply raises every term of the floor variant by exactly 1. For us, however, this is the case that does not exist inside a computer. In the rational domain, admitted only by Fraenkel’s theorem, nα is sometimes an integer, and then ⌈nα⌉ = ⌊nα⌋, so the shift by 1 disappears. The constant offset between the ceiling and the floor variant therefore ceases to hold globally and has to be settled term by term - which is exactly what the case analysis in part three of the proof of Theorem 2 (de-interleaving satisfies Fraenkel’s postulates) does, where gcd(a, b) decides which of the two cases applies.

\[ \left\lfloor x + C\right\rfloor = \left\lfloor x\right\rfloor + C \]

(the last identity holds for every C ∈ ℤ). Additionally, in analyzing the residue of the de-interleaving sequence we will use relationships tying the greatest common divisor (gcd) to the domain of the quotient a/b. For a, b ∈ ℕ_>0:

\[ \operatorname{gcd}(a,b) = b \iff \frac{a}{b} \in \mathbb{N} \]

and otherwise:

\[ 1 \leq \operatorname{gcd}(a,b) \leq \min(a,b) \]

These two cases disjointly cover the entire domain of interest to us - which will let us carry out a proof “by cases.”

Operators in formal notation

The operators introduced in the query language have their formal counterparts. The table below ties the formal notation (used in the proofs) to the symbols found in the query language:

For the proofs to be self-contained, I restate two definitions I will refer to directly.

Interleaving φ(A, B) produces an output stream whose successive tuples are determined by the rule:

\[ c_{n}= \left\{ \begin{array}{cc} b_{n-\left\lfloor n z \right\rfloor } & \left\lfloor n z \right\rfloor = \left\lfloor \left( n+1\right) z \right\rfloor \\ a_{\left\lfloor n z \right\rfloor } & \left\lfloor n z \right\rfloor \neq \left\lfloor \left( n+1\right) z \right\rfloor \end{array} \right. , \ z = \frac{\Delta _{b}}{\Delta _{a}+\Delta _{b}}, \ \Delta _{c}=\frac{\Delta _{a}\Delta _{b}}{\Delta _{a}+\Delta _{b}} \]

De-interleaving is defined by two complementary formulas - operator Θ, which recovers the original stream, and operator ∼Θ, which determines the “remainder” of the de-interleaving:

\[ a_{n} = c_{n+ \left\lceil \frac{(n+1)\Delta _{a}}{\Delta _{b}} \right\rceil },\ \Delta _{a}=\frac{\Delta _{c}\Delta _{b}}{\left\vert \Delta _{c}-\Delta _{b}\right\vert } \]

\[ b_{n} = c_{n+\left\lfloor \frac{n\Delta_{b}}{\Delta_{a}}\right\rfloor},\ \Delta_{b}=\frac{\Delta_{c}\Delta_{a}}{\left\vert \Delta_{c}-\Delta_{a}\right\vert } \]

Theorem 1: interleaving guarantees set coverage

✅ Note

Theorem. The interleaving operation guarantees sequential coverage of both index sets of the data streams that are its arguments: every element of stream A and every element of stream B is selected exactly once, in order, without gaps and without repetition.

Proof. Since 0 < z < 1, the increment

\[ d_{n} := \left\lfloor \left( n+1\right) z \right\rfloor - \left\lfloor n z \right\rfloor \]

equals 0 or 1 for every n ≥ 0. The interleaving equation selects an element of stream B exactly at those steps where d_n = 0 (the equality branch), and an element of stream A exactly at steps where d_n = 1.

Consider the selection index for sequence B: x_n = n − ⌊nz⌋. In a single step, x_n+1 − x_n = 1 − d_n: the index increases by exactly 1 at every step selecting from B, and otherwise remains unchanged. So if n < n′ are two consecutive steps selecting from B, then x_n′ = x_n + 1. The first step selecting from B is n = 0, since 0 < z < 1 implies ⌊0⌋ = ⌊z⌋ = 0, i.e. d₀ = 0, and x₀ = 0. Selections from sequence B therefore use indices 0, 1, 2, … in order, without gaps or repetitions.

Symmetrically: the selection index for sequence A, i.e. ⌊nz⌋, increases by exactly 1 at every step selecting from A (d_n = 1), and otherwise remains unchanged; at the first such step its value is 0 (all earlier steps have d = 0). The elements of sequence A are therefore also selected exactly once each, in order. ∎

Theorem 2: de-interleaving satisfies Fraenkel’s postulates

This is the central theorem of this page. It proves that the two sequences describing the de-interleaving operation are a special case of Beatty sequences satisfying the postulates of Fraenkel’s theorem for rational numbers. Without this theorem, the whole system remains merely a promise.

✅ Note

Theorem. Let a, b ∈ ℕ_>0 represent the rational ratio of the rates of the component streams, ∆_a/∆_b = a/b. Both tuple-selection sequences describing the de-interleaving operation are - up to the index alignment shown in the proof - a special case of Beatty sequences satisfying the postulates of Fraenkel’s theorem for rational parameters. Consequently they partition the set ℕ₀ := ℕ ∪ {0}, i.e. the index set of the interleaved stream, and de-interleaving exactly inverts interleaving using rational-number arithmetic alone.

Proof - part one (reduction to Beatty form). The tuple-selection sequence for the de-interleaving residue (operator ∼Θ) has the form:

\[ \left( n + \left\lfloor \frac{nb}{a} \right\rfloor \right) _{n=0}^{\infty } \]

Its initial term (n = 0) equals 0; the terms for n ≥ 1 form the Beatty part. For n ∈ ℕ, by the property ⌊x + C⌋ = ⌊x⌋ + C, we have n + ⌊nb/a⌋ = ⌊n + nb/a⌋, so we seek α, α′ such that:

\[ \left( \left\lfloor \frac{n-\alpha ^{\prime }}{\alpha }\right\rfloor \right) _{n=1}^{\infty } = \left( \left\lfloor n\frac{a + b}{a} \right\rfloor \right) _{n=1}^{\infty } \]

Reading off the slope and the offset: with a shift of α′ = 0 we obtain α = a/(a+b), and the selection sequence restricted to n ≥ 1 is exactly:

\[ \mathcal{B}\!\left( \frac{a}{a + b}, 0 \right) = \left( \left\lfloor n\frac{a + b}{a} \right\rfloor \right) _{n=1}^{\infty } \]

Proof - part two (verifying the five postulates and determining the residue). We check the postulates of Fraenkel’s theorem in turn for α = a/(a+b), α′ = 0:

1. The value α = a/(a+b) for a, b > 0 is greater than zero and less than one.
2. The condition α + β = 1 is satisfied for β = b/(a+b).
3. For α′ = 0 the postulate is equivalent to postulate 1.
4. The postulate is vacuous, since α is a rational number.
5. The smallest number q for which qα ∈ ℕ is q = (a+b)/gcd(a,b); then the condition 1/q ≤ α + α′ = α is satisfied, and the condition ⌈qα′⌉ + ⌈qβ′⌉ = 1 with α′ = 0 forces ⌈qβ′⌉ = 1, i.e. 0 < β′ ≤ gcd(a,b)/(a+b). Every admissible value generates the same sequence (the complement of the sequence B(a/(a+b), 0) in ℕ is unique); we take β′ = gcd(a,b)/(a+b).

The sequence complementing B(a/(a+b), 0) in the sense of Fraenkel’s postulates is therefore:

\[ \mathcal{B}\!\left( \frac{b}{a + b}, \frac{\operatorname{gcd}(a, b)}{a + b} \right) \]

After reindexing n ↦ n + 1, so that it runs from n = 0 - matching the selection sequences in the definition of de-interleaving - it takes the form:

\[ \left( \left\lfloor \frac{(n + 1) - \frac{\operatorname{gcd}(a,b)}{a+b}}{\frac{b}{a+b}} \right\rfloor \right) _{n=0}^{\infty } \]

Expanding the above expression:

\[ \left\lfloor \frac{(n + 1) - \frac{\operatorname{gcd}(a,b)}{a+b}}{\frac{b}{a+b}} \right\rfloor = \left\lfloor n\frac{a}{b} + n + \frac{a}{b} + 1 - \frac{\operatorname{gcd}(a, b)}{b} \right\rfloor \]

Comparing this - term by term for n ≥ 0 - with the tuple-selection sequence of the recovered stream (operator Θ):

\[ \left( n + \left\lceil \frac{(n + 1)a}{b} \right\rceil \right) _{n=0}^{\infty } \]

and factoring out the integer part n + 1 via the property ⌊x + C⌋ = ⌊x⌋ + C, the claim reduces (after substituting n for n + 1, so that n ranges over ℕ_>0) to the identity:

\[ \left\lfloor n\frac{a}{b} - \frac{\operatorname{gcd}(a, b)}{b} \right\rfloor + 1 = \left\lceil n\frac{a}{b} \right\rceil ,\quad n \in \mathbb{N}_{>0} \]

Proof - part three (case analysis). Using the properties of the coefficient gcd(a, b), we consider two disjoint cases covering the entire domain.

Case 1: gcd(a, b) = b, i.e. a/b ∈ ℕ. Then n·a/b ∈ ℕ, so by the identity ⌊x⌋ = ⌈x⌉ ⟺ x ∈ ℤ we have ⌈n·a/b⌉ = ⌊n·a/b⌋, and by ⌊x + C⌋ = ⌊x⌋ + C:

\[ \left\lfloor n\frac{a}{b} - 1 \right\rfloor + 1 = \left\lfloor n\frac{a}{b} \right\rfloor \]

Both sides of the identity being proved coincide.

Case 2: b ∤ a, i.e. 1 ≤ gcd(a, b) < b and 0 < gcd(a,b)/b < 1.

If n·a/b ∉ ℤ, then by ⌊x⌋ + 1 = ⌈x⌉ ⟺ x ∈ ℝ ∖ ℤ we have ⌈n·a/b⌉ = ⌊n·a/b⌋ + 1. The fractional part of n·a/b is a nonzero multiple of gcd(a,b)/b, and hence at least gcd(a,b)/b; subtracting gcd(a,b)/b from n·a/b therefore cannot drop below the integer ⌊n·a/b⌋, whence:

\[ \left\lfloor n\frac{a}{b} - \frac{\operatorname{gcd}(a, b)}{b} \right\rfloor = \left\lfloor n\frac{a}{b} \right\rfloor \]

and the identity being proved holds.

If n·a/b ∈ ℤ, then ⌈n·a/b⌉ = n·a/b, and since 0 < gcd(a,b)/b < 1:

\[ \left\lfloor n\frac{a}{b} - \frac{\operatorname{gcd}(a, b)}{b} \right\rfloor = n\frac{a}{b} - 1 \]

which again gives the identity being proved.

Both selection sequences describing the de-interleaving operation are therefore - up to the unit reindexing from part two - Beatty sequences satisfying Fraenkel’s postulates for rational parameters: the pair B(a/(a+b), 0) and B(b/(a+b), gcd(a,b)/(a+b)) partitions the set ℕ, and together with the initial residue term 0 from part one - the set ℕ₀, the full index set of the interleaved stream. The recovered stream and the residue are therefore exact. ∎

✅ Note

Corollary (exact invertibility over the rationals). For streams with rational rates, the operators Θ and ∼Θ recover the component streams of φ(A, B) exactly (bit for bit): no tuple is lost, duplicated, or reordered relative to its component stream. The pair (φ; Θ, ∼Θ) therefore behaves like multiplication and division, and the pair (Σ; δ) like addition and subtraction, on the set of regular time series.

⚠️ Warning

The practical takeaway from this proof: the implementation must never leave the domain of rational numbers, not even momentarily. An implicit cast of an intermediate result to a floating-point number breaks the assumptions of the theorem above. Materialization into floating-point form must be deferred until an explicit application of the floor or ceiling operation.

Operator properties used in optimization

Based on the algebra presented, a number of properties of data streams can be shown. They have direct application in the data-management system - during query-plan optimization and result interpretation.

Disruption of event ordering

✅ Note

Theorem. The order of elements in a stream does not reflect the actual order in which the elements occurred in the real world.

Proof (by counterexample). Consider two streams:

Alpha(char),2:   {1,2,3,4,5,6,...}
Epsilon(char),3: {a,b,c,d,e,f,...}

The expression φ(Epsilon, Alpha) produces the output stream:

Tau(char),6/5:   {1,2,a,3,b,4,5,c,6,d,...}

In stream Tau, the tuple labeled c occurs after the tuple labeled 5. Yet tuple c appears in stream Epsilon at second 9, while tuple 5 appears in stream Alpha at second 10. The natural order of events has been violated in the resulting stream. Conclusion: when analyzing time embedded in streams, applying the de-interleaving operation is necessary to recover the original form of the data streams. ∎

Commutativity of summation

✅ Note

Theorem. The stream-summation operation, disregarding attribute order, is commutative.

Proof. Assume ∆_a ≤ ∆_b; the opposite case is symmetric. The first case of the sum definition gives, as the n-th element of stream Σ(A, B), the tuple:

\[ c_{n} = \left( a_{n},\ b_{\left\lfloor n\Delta_{a}/\Delta_{b} \right\rfloor} \right) \]

whereas for Σ(B, A) the roles of the arguments are swapped, and its second case applies (or, at ∆_a = ∆_b, its first), giving as the n-th element:

\[ c_{n} = \left( b_{\left\lfloor n\Delta_{a}/\Delta_{b} \right\rfloor},\ a_{n} \right) \]

Both streams carry ∆_c = ∆_a. They therefore coincide up to the order of the joined attributes. ∎

Interleaving alignment method

The interleaving operation is not commutative in general: since 0 < z < 1, at n = 0 the equality branch of the interleaving definition always applies, so the stream φ(A, B) begins with element b₀, while the stream φ(B, A) begins with element a₀. Interleaving is, however, equivariant with respect to time shifts matched to the streams’ rates - which is valuable for query-plan optimization.

In the causal realization a stream has the form \(\widehat{S}=((s_n,\Delta),W_S)\), where \(W_S\) is its startup tail. We define conversion of a producer’s tail into output slots as:

\[ \operatorname{conv}(w,\Delta_s,\Delta_o):= \left\lceil\frac{w\Delta_s}{\Delta_o}\right\rceil \]

The tail of an interleave with interval \(\Delta_c=\Delta_a\Delta_b/(\Delta_a+\Delta_b)\) follows directly from the operator definition, without going through a single phase term.

Record \(i\) of \(\varphi(A,B)\) carries the content of record \(j(i)\) of exactly one component - the one the interleave definition selects in slot \(i\). Write \(\Delta_{s(i)}\) and \(W_{s(i)}\) for the interval and tail of the selected component. Record \(j(i)\) is determined at time \(\bigl(j(i)+1+W_{s(i)}\bigr)\Delta_{s(i)}\), while consumer slot \(i\) ends at \((i+1+W)\Delta_c\). The causality condition for every \(i\) is:

\[ W\ge \left\lceil\frac{\bigl(j(i)+1+W_{s(i)}\bigr)\Delta_{s(i)}}{\Delta_c}\right\rceil -1-i \]

Let \(\Delta_a/\Delta_b=p/q\), where \(p,q\in\mathbb{N}_{>0}\) and \(\gcd(p,q)=1\). Both the component selection and the residue determining \(j(i)\) repeat with period \(p+q\), so the maximum of the right-hand side over one period is the maximum over all records:

\[ W_{\varphi(A,B)} =\max_{0\le i<p+q}\left( \left\lceil\frac{\bigl(j(i)+1+W_{s(i)}\bigr)\Delta_{s(i)}}{\Delta_c}\right\rceil -1-i \right) \]

The formula is exact: it neither overshoots nor undershoots the event-model bound for any node. The period scan starts at zero - the logical origin shifts the consumer index and the component index by the same amount, so the window \([0,,p+q)\) yields the same value as any shifted window.

The earlier closed form

\[ W_{\varphi(A,B)} =\max\left( \operatorname{conv}(W_A,\Delta_a,\Delta_c), \operatorname{conv}(W_B,\Delta_b,\Delta_c) +H_{a,b} \right), \qquad H_{a,b}=\left\lceil\frac{p+q-1}{p}\right\rceil \]

protected the worst read phase of the second argument, but did not check whether that phase actually falls on the record that waits longest - hence it overshot the tail by one slot for some nodes. It survives in the implementation as the fallback for \(p+q\) above the scan threshold (kHashPhaseScanLimit in SOperations.hpp): overshooting costs one slot of latency, whereas undershooting would mean emitting a record before its dependency is determined. Tail slots are not records.

The shift \(\tau_m\) does not change the emitted record sequence, but it does change the index at which that sequence appears: record \(n\) carries the content of record \(n-m\). Records with an index below \(O_S+m\) have no definition, hence

\[ O_{\tau_m(S)}=O_S+m, \qquad W_{\tau_m(S)}=\max\left(0,;W_S-m\right) \]

The tail decreases: record \(n-m\) is older than the current one and therefore all the more available - the slot deficit is \(W_S-m\) and is constant. Details and measurement: Tails, logical origins and operator observability.

✅ Note

Theorem (R1, commuting a shift with an interleave). If numbers i, k ∈ ℕ are chosen such that i·∆_a = k·∆_b (both arguments shifted by the same amount of time), then interleaving the shifted streams and the interleaving of the original streams shifted by the sum of these numbers have the same record sequence, the same interval and the same logical origin. Their tails satisfy an inequality - the factored side is never the later one.

Formally, with \(L:=i+k\):

\[ \operatorname{Obs}\Bigl(\varphi\bigl(\tau_{i}(A),\tau_{k}(B)\bigr)\Bigr) =\operatorname{Obs}\Bigl(\tau_{i+k}\bigl(\varphi(A,B)\bigr)\Bigr), \qquad i\Delta_{a}=k\Delta_{b},\quad i,k\in\mathbb{N} \]

\[ W_{\mathrm{RHS}}=\max\left(0,;W_{\varphi(A,B)}-L\right)\le W_{\mathrm{LHS}} \]

where \(\operatorname{Obs}\) is the value part of the observation (interval, logical origin, record sequence with its NULL map, descriptor, gap trace, materialization policy) - see Tails, logical origins and operator observability.

Proof.

Interval. Both sides arise from the same interleave, so both have \(\Delta_c=\Delta_a\Delta_b/(\Delta_a+\Delta_b)\).

Auxiliary step. From i·∆_a = k·∆_b it follows that

\[ \frac{i\Delta_a}{\Delta_c} =\frac{i\Delta_a(\Delta_a+\Delta_b)}{\Delta_a\Delta_b} =\frac{i\Delta_a}{\Delta_b}+i =k+i =L\in\mathbb{N}, \]

and symmetrically \(k\Delta_b/\Delta_c=L\). Shifting each argument by its own number of slots therefore corresponds to the same number \(L\) of result slots.

Record sequence and logical origin. Within one period the interleave takes \(i\) records from A and \(k\) records from B, filling exactly \(L=i+k\) slots of C. Shifting A by \(i\) and B by \(k\) therefore moves the mapping threshold of both components by exactly \(L\) result slots without changing their relative phase: \(O_{\mathrm{LHS}}=O_{\varphi(A,B)}+L=O_{\mathrm{RHS}}\). The content of a record at a given logical index is the same on both sides, because the choice of component depends only on phase, which is unchanged.

Tails. Let \(s(n)\in\{A,B\}\) denote the component selected in phase \(n\), and \(j(n)\) its index. Write the shifts as \(t_A=i\) and \(t_B=k\). After shifting, the component tail is \(W_s^{\prime}=\max(0,W_s-t_s)\ge W_s-t_s\). The intervals and the choice of component and its index in each interleave phase remain unchanged. Let \(R_n\) be the availability requirement from the phase formula above for tails \(W_A,W_B\), and \(R_n^{\prime}\) the requirement for \(W_A^{\prime},W_B^{\prime}\). The auxiliary step gives \(t_s\Delta_s/\Delta_c=L\in\mathbb{N}\) for both components. Monotonicity of the ceiling and its compatibility with shifts by the integer \(L\) give, in every phase:

\[ \begin{aligned} R_n^{\prime} &=\left\lceil \frac{(j(n)+1+W_{s(n)}^{\prime})\Delta_{s(n)}}{\Delta_c} \right\rceil-1-n\\ &\ge\left\lceil \frac{(j(n)+1+W_{s(n)}-t_{s(n)})\Delta_{s(n)}}{\Delta_c} \right\rceil-1-n =R_n-L. \end{aligned} \]

We take the maximum over the same full period \(p+q\), since the shifts do not change the interval ratio. Using nonnegativity of tails as well, we obtain:

\[ W_{\mathrm{LHS}} \ge\max\left(0,\max_{0\le n<p+q}R_n-L\right) =\max\left(0,W_{\varphi(A,B)}-L\right) =W_{\mathrm{RHS}}. \]

Above the scan limit, the engine uses the \(O(1)\) fallback bound described earlier. For that bound, the same inequality follows from monotonicity of both \(\operatorname{conv}\) terms: a matched shift reduces each by at most \(L\), while the \(H_{a,b}\) term remains unchanged. Both sides use the same calculation variant because their intervals do not change. The fallback bound need not equal the exact phase maximum. ∎

⚠️ Scope of the theorem

Equality of tails does not hold. Counterexample: \(\Delta_a=1/10\), \(\Delta_b=1/5\), \(W_A=W_B=0\), \(H_{a,b}=2\), \(i=2\), \(k=1\), \(L=3\). Then \(W_{\mathrm{LHS}}=2\) while \(W_{\mathrm{RHS}}=\max(0,2-3)=0\). The unfactored side reads its components after their own shift, so it waits longer for the same content; the factored side reads it directly from the interleave.

Practical consequence: the rewrite rule \(\varphi(\tau_i(A),\tau_k(B))\to\tau_{i+k}(\varphi(A,B))\) is a latency optimization, not a neutral rewrite. It preserves the entire value part of the observation and never emits a record before its dependencies are determined, but the result is ready sooner.

Previously both sides had the same tail solely because the realization of \(\tau_m\) overestimated its own tail by \(\min(W_S,m)\). The overestimate was removed by addressing the producer with a logical index instead of a relative offset. Regressions guarding this scope: it_r1_identity_nulls, it_optimizer_ablation-factor-name-collision-semantic.

In the compiler, additional invariants preserve public stream field names, null value maps, and the materialization policy.

Why this matters

The theorems presented are not formalism for its own sake. Each of them plays a concrete role in the working system:

• Theorems 1 and 2 guarantee that the pairs of operations interleaving/de-interleaving and sum/difference are complementary - data is neither lost nor duplicated in an uncontrolled way. They are what allow us to treat these operations like multiplication/division and addition/subtraction on the set of regular time series.
• Theorem 2 in particular proves that the entire construction can be realized using rational numbers alone - and thus deterministically and exactly on a computer. This is the condition without which RetractorDB could not exist.
• The theorems on operator properties (commutativity of summation, interleaving alignment, ordering disruption) provide rewrite rules for stream expressions. The query-plan optimizer uses them to transform plans into cheaper-to-execute forms without changing the result.

The branch of mathematics in which these equations are situated is the theory of covering systems [4] within number theory. I presented the full formalism along with a complete set of proofs in the paper A Deterministic Method for Processing Data Sequences [3].

ℹ️ Info

A numerical verification of the equations above - Python prototypes operating on rational numbers (the Fraction library) - can be found on the Model Implementation page and in the repository github.com/michalwidera/equations.

Tails, logical origins and operator observability

A causal realization extends a stream \(S=(s_n,\Delta_S)\) with two integer quantities, not one. The distinction matters: they answer different questions and behave differently under plan rewrites.

Neither is a prefix of zeros or of all-null records. The boundary principle holds unchanged: NULL is a data value, never a placeholder. The number of initial slots in which the stream stays silent is \(O_S+W_S\) - and only that sum was visible before the two quantities were separated.

The logical index is the currency of every mapping between streams. A stream with a non-zero \(O_S\) has no earlier records, so its physical record 0 carries logical index \(O_S\); the conversion to a buffer offset is performed solely by dataModel::fetchForward().

Operator audit

In the table, “own tail” is the delay required by the operator beyond producer availability. Producer tails are converted to result slots beforehand.

“Mapping threshold” is the smallest index \(n\) from which every later record maps onto existing component records. It is not “the first index with complete dependencies”: with an interleave of components having different origins, record 0 may be complete while record 1 is not. A stream is a sequence of records, not a set with holes - the boundary principle forbids filling a hole with NULL - so the logical origin is the first index with no remaining gap. All record-to-record mappings are non-decreasing, so such an index exists and is unique.

The difference operator takes a target interval \(\Delta\) that may not be smaller than the source interval \(\Delta_C\). For the ratio \(r=\Delta/\Delta_C=p/q\) the maximum phase lead of the index \(\lceil nr\rceil\) is \((q-1)/q\).

Tails of phase operators

Difference and both de-interleaves use one availability rule. Let \(r=\Delta_{out}/\Delta_{src}\), let \(W_S\) be the source tail, and let \(e_{max}\) be the largest phase lead reached by the index mapping. Then:

\[ W_{out}=\max\left(0, \left\lceil\frac{e_{max}+W_S+1}{r}\right\rceil-1 \right) \]

For difference, \(e_{max}=(q-1)/q\), where \(q\) is the denominator of the reduced ratio \(r\). For left de-interleave, with \(\Delta_{out}/\Delta_{other}=a/b\), the value is \(e_{max}=(a+b-1)/b\). For right de-interleave, \(e_{max}=0\). In particular, left de-interleave does not unconditionally add one slot: for an integral ratio, its own tail can be zero.

The interleave tail

The interleave is the only operator whose tail does not decompose into “converted producer tails plus an own constant”. Record \(i\) carries the content of record \(j(i)\) of just one component - the one the operator definition selects in slot \(i\) - so the required latency depends on which component, and which of its phases, a given slot falls on:

\[ W_{\#} =\max_{0\le i<p+q}\left( \left\lceil\frac{\bigl(j(i)+1+W_{s(i)}\bigr)\Delta_{s(i)}}{\Delta_c}\right\rceil -1-i \right), \qquad \frac{\Delta_a}{\Delta_b}=\frac{p}{q},\quad \gcd(p,q)=1 \]

The component selection and the phase repeat with period \(p+q\), so the maximum over one period is the maximum over all records; the logical origin shifts both indices equally and does not change the result. The formula is exact. For periods exceeding kHashPhaseScanLimit, a safe closed form protects the worst read phase. It may delay emission, but it cannot allow a record to be emitted before its dependencies are available.

The shift \(\tau_N\)

Record \(n\) carries the content of producer record \(n-N\). Hence both quantities:

\[ O_{\tau_N(S)}=O_S+N, \qquad W_{\tau_N(S)}=\max\left(0,;W_S-N\right) \]

The tail decreases, it does not grow. Record \(n-N\) is older than the current one, so it is available all the more readily: the deficit of slot \(n\) is \((n-N+1+W_S)-(n+1)=W_S-N\) and is constant, independent of \(n\). The shift therefore moves silence from the tail into the logical origin, and additionally absorbs the producer tail whenever \(N\ge W_S\).

The sum \(O+W\) is not invariant here: for \(N<W_S\) it equals \(W_S\), whereas the realization from before the separation gave \(W_S+N\). That earlier realization overestimated the tail by \(\min(W_S,N)\); the overestimate was removed by addressing the producer with a logical index instead of a relative offset.

The full AGSE window

The window is stamped by the interval end: record \(n\) spans flattened source positions from \(nk-(\lvert L\rvert-1)\) to \(nk\). Its newest field therefore lies exactly at position \(nk\), and the window’s logical index denotes the same instant as the source’s logical index - joining a window with its own source (a FIR pipeline) does not lead the signal.

The price of the convention is that for small \(n\) the window would reach before the start of the source. Those records are not produced. Let the source have \(F\) fields and logical origin \(O_S\); requiring the whole window to fit gives

\[ O_{\operatorname{AGSE}} =\left\lceil\frac{O_S F+\lvert L\rvert-1}{k}\right\rceil \]

Availability is governed by the newest field, which lies in record \(\lfloor nk/F\rfloor\). Substituting \(r_n=(nk)\bmod F\), the availability condition for every \(n\) becomes \(W\ge\bigl(F(1+W_S)-r_n\bigr)/k-1\). The residues \(r_n\) run through multiples of \(\gcd(F,k)\) periodically, so the minimum \(r_n=0\) is attained regardless of the index at which the stream starts. Hence

\[ W_{\operatorname{AGSE}} =\left\lceil\frac{(1+W_S)F}{k}\right\rceil-1 \]

The phase term \(P_{F,k,L}=\lfloor(\lvert L\rvert-1)/g\rfloor,g\), present in the form used before the re-stamping, disappeared from the tail: the window span is not waiting but undefinedness, and moved wholly into the logical origin. The sum \(O+W\) describes the same silence as before.

A positive width preserves the historical RetractorDB convention - the newest field comes first; a negative width mirrors it, giving arrival order.

Source history capacity has no closed form here. The backward distance at the moment record \(n\) is emitted,

\[ \left\lfloor\frac{(n+1+W)k}{F}\right\rfloor-W_S-1 ;-; \left\lfloor\frac{nk-\lvert L\rvert+1}{F}\right\rfloor, \]

is periodic with period \(F/\gcd(F,k)\) output slots, so the maximum is computed exactly, by scanning one full period from \(O_{\operatorname{AGSE}}\). A closed form would be guesswork here, and underestimating means reading outside history, not merely one slot of delay. A declared source has one record armed when the storage is opened plus a zero prefetch, so its capacity bound contains two extra records. Capacity is a property of execution, not part of the result.

The observability relation

Stream observation splits into two parts, because plan rewrites preserve them to different degrees.

Value part - preserved by rewrites exactly:

\[ \operatorname{Obs}(S) =\left(\Delta_S,O_S,D_S,(s_n,N_n)_{n\ge O_S},G_S,M_S\right) \]

where:

• \(O_S\) is the logical origin, the index of the first record;
• \(D_S\) is the public descriptor and field-name order;
• \(N_n\) is the record’s NULL map - a true NULL remains a data value and is carried through AGSE;
• \(G_S\) is the gap trace; detection currently works for declarations, while computed streams have \(G_S=\varnothing\);
• \(M_S\) describes the materialization policy (DEFAULT, MEMORY, VOLATILE and the remaining storage kinds).

Latency part - the tail \(W_S\) - carries a weaker guarantee:

a plan rewrite never increases \(W_S\) and never emits a record before its dependencies are determined; it may, however, decrease \(W_S\).

The split is not a formality. The \(R_1\) factoring (\(\varphi(\tau_i(A),\tau_k(B))\to\tau_{i+k}(\varphi(A,B))\)) preserves the whole value part but shortens the tail: the factored form reads content directly from the interleave, whereas the unfactored form reads components only after their own shift. Rationale: Formal foundations and proofs, theorem on commuting a shift with an interleave. Regressions: it_r1_identity_nulls, it_optimizer_ablation-factor-name-collision-semantic.

Changing any component of the value part changes the observable artifact. In particular, enabling gap propagation for computed streams in the future requires a versioned semantic change.

A read outside available history internally returns an all-null record as a failsafe. A correctly compiled plan never materializes it: logicalOrigin skips slots without a definition, startupLatency skips slots not yet determined, and the history capacity retains every required index. The it_k19_boundaries test distinguishes this case from a genuine NULL located inside a full window. Since 23 September 2026 the convention holds along the whole read path: storage::read() and storage::revRead() report a missing record through a separate status and also set an all-null pattern, so a reducer absorbs such a record instead of folding zeros out of it (→ Files).

The operator formulas in this chapter are enforced on every commit: boundaries and observability by it_k19_boundaries, history depths by it_k24_capacity, and agreement of logical origin and tail for all canonical operator classes and their compositions by the ut_h10aGate unit test.

Algebraic Expressions

The defined algebra entails the possibility of defining algebraic expressions. Typical algebraic expressions over the set of rational numbers are material covered in elementary school. Algebraic expressions in RetractorDB occur in two forms. In the field list of the SELECT command, we have the typical expressions familiar from school. In the argument list of the SELECT command’s FROM clause, we have an algebraic expression built on the newly defined algebra.

This means that in the field list after the SELECT clause, the plus operator means one thing, while in the FROM clause it means something else entirely. An innocent-looking query from the definition combines two entirely different worlds and concepts: one, an algebra based on numbers; the other, based on regular time series.

Example. As an example, we present an algebraic expression built over the set of regular time series (hereafter called streams). Assume the existence of two streams: A(a₁ int, a₂ int),1 and B(b₁ int),½ - where,

• A denotes a stream containing, in each record, two fields of type int - a₁ and a₂ - arriving once per second, and
• B contains, in each record, a field of type int named b₁ arriving twice per second.

The algebraic expression C=A+B creates a data stream with fields C(a₁ int, a₂ int, b₁ int),½.

To interleave a data stream, sets A and B should have the same data schema. Let’s assume, then, that there is a stream D(d₁ int),1 - arriving, like stream A, once per second.

The algebraic expression E=B#D creates the stream: E(e₁ int),⅓. The rate ⅓ comes from the formula (1*½)/(1+½). You will find this formula in the definition of the interleaving operation.

For streams defined this way, the following expression is still valid:

F=((B#D)+A)>2

And such expressions may appear as valid, with respect to the developed time-series algebra, in the body of a query.

Further examples

Continuing with the streams defined above, A(a₁ int, a₂ int),1, B(b₁ int),½ and D(d₁ int),1, and the output streams C=A+B and E=B#D - below is a further set of valid algebraic expressions. Equivalents of all these expressions appear in FROM clauses of queries in the system’s integration tests, and are verified on every build of the project.

Interleaving the result of an interleave:

G=E#D

Stream E has rate ⅓, stream D has rate 1, both share the same schema with a single int field. The interleaving formula gives a rate of (⅓·1)/(⅓+1)=¼, so G(g₁ int),¼. The result of one operation is a fully valid stream and can be the argument of the next one.

Sum of three streams:

H=A+B+D

Summation joins tuples, so the result schema is the concatenation of the schemas, and the rate is dictated by the fastest component: H(a₁ int, a₂ int, b₁ int, d₁ int),½.

Sum with a shifted component, and a shift of an interleaving argument:

I=D+((A+B)>1)
J=(B>1)#D

Shifting a sequence does not change the stream’s rate - it only changes data access by a given number of samples. Therefore I has rate min(1,½)=½, and J - just like E - has rate ⅓.

De-interleaving:

K=E&1
L=E%½

The right-hand argument of the de-interleaving operators is a rational number, not a stream. Substituting into the de-interleaving formulas: K has rate (⅓·1)/|⅓−1|=½ - left-hand de-interleaving recovers stream B from the interleave E. Similarly L has rate (⅓·½)/|⅓−½|=1 - right-hand de-interleaving recovers stream D. De-interleaving is the inverse of interleaving, just as division is the inverse of multiplication.

Difference:

M=C-1

Difference is the inverse operation to sum - it extracts, from the joined stream C, the component indicated by the rational number on the right-hand side of the operator.

Aggregation and serialization:

N=A@(1,4)
P=A@(1,-4)
R=A@(2,2)
S=(A@(2,2))@(1,1)

N creates a sliding window of width 4 shifted by one element, P - thanks to its negative width - builds the same windows mirror-imaged, R creates disjoint windows (hop equal to the width). Expression S shows that the result of an Agse operation can be the argument of another Agse operation.

All of the above forms can be combined into arbitrarily complex expressions - like F=((B#D)+A)>2 from the example above - as long as the data schemas of the arguments satisfy the requirements of the respective operations.

Coverage of examples in integration tests

Each of the expression forms cited has a counterpart in the RetractorDB repository’s shared test/IntegrationTest directory, executed on every project build:

The tests compare query execution results against pattern files, so the expressions above are verified not only syntactically, but also in terms of the values and rates of the resulting streams.

Model Implementation

The developed algebra equations were first implemented in Python. This is, to my knowledge, the most effective way to model and numerically verify hypotheses. Each operator was implemented inside a separate function. Operations are carried out on rational variables (the Fraction library). Results are presented as bounded arrays. In the final implementation, however, these operators operate on infinite data structures.

Interleaving operation

Let’s start by building the interleaving operation:

Source code

# Interleaving (hash) operation on two lists with given steps (delta).
from fractions import Fraction
from math import floor, ceil

A = range(1, 24)
deltaA = Fraction(1, 2)
B = list(map(chr, range(ord('a'), ord('z')+1)))
deltaB = Fraction(1, 2)

def hash(A: list, deltaA: Fraction, B: list, deltaB: Fraction):
  result = []
  delta = deltaB / (deltaA + deltaB)
  for i in range(0, 20):
      if floor(i*delta) == floor((i+1)*delta):
          result.append(B[i-int(floor((i+1)*delta))])
      else:
          result.append(A[int(floor(i*delta))])
  deltaC = (deltaA*deltaB)/(deltaA+deltaB)
  return result, deltaC
  
def main():
    print("A:", A[0:10], " deltaA:", deltaA)
    print("B:", B[0:10], " deltaB:", deltaB)
    hash_result1, delta_hash1 = hash(A, deltaA, B, deltaB)
    hash_result2, delta_hash2 = hash(B, deltaB, A, deltaA)
    print("Hash(A,B):", hash_result1[0:10], " deltaHash:", delta_hash1)
    print("Hash(B,A):", hash_result2[0:10], " deltaHash:", delta_hash2)

if __name__ == '__main__':
    main()

Run output

$ python hash.py
A: range(1, 11) deltaA: 1/2
B: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'] deltaB: 1/2
Hash(A,B): ['a', 1, 'b', 2, 'c', 3, 'd', 4, 'e', 5] deltaHash: 1/4
Hash(B,A): [1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e'] deltaHash: 1/4

Running the code prints the input data A and B, along with the results of the operations A#B and B#A. As you can see, the interleaving operation is not commutative.

De-interleaving operation

The de-interleaving operation requires implementing two complementary operations.

Source code - even

# De-interleaving (dehash) operation, even.
from fractions import Fraction
from math import floor, ceil

A = range(1, 24)
deltaA = Fraction(1, 2)
B = list(map(chr, range(ord('a'), ord('z')+1)))
deltaB = Fraction(1, 2)

def hash(A: list, deltaA: Fraction, B: list, deltaB: Fraction):
  result = []
  delta = deltaB / (deltaA + deltaB)
  for i in range(0, 20):
      if floor(i*delta) == floor((i+1)*delta):
          result.append(B[i-int(floor((i+1)*delta))])
      else:
          result.append(A[int(floor(i*delta))])
  deltaC = (deltaA*deltaB)/(deltaA+deltaB)
  return result, deltaC

def dehasheven(C: list, deltaC: Fraction, deltaA: Fraction):

  result = []
  deltaB = deltaA*deltaC / (deltaA - deltaC)

  for i in range(0, 6):
      result.append(C[i+int(ceil((i+1)*deltaA/deltaB))])
  return result, deltaB

def main():
    hash_result, delta_hash = hash(B, deltaB, A, deltaA)
    print("Hash(A,B):", hash_result[0:10], " deltaHash:", delta_hash)
    mod_result, delta_mod = dehasheven(hash_result, delta_hash, deltaA)
    print("Mod(Hash):", mod_result[0:10], " deltaMod:", delta_mod)

if __name__ == '__main__':
    main()

result - even

$ python dehash_even.py
Hash(A,B): [1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e'] deltaHash: 1/4
Mod(Hash): ['a', 'b', 'c', 'd', 'e', 'f'] deltaMod: 1/2

Source code - odd

# De-interleaving (dehash) operation, odd.
from fractions import Fraction
from math import floor, ceil

A = range(1, 24)
deltaA = Fraction(1, 2)
B = list(map(chr, range(ord('a'), ord('z')+1)))
deltaB = Fraction(1, 2)

def hash(A: list, deltaA: Fraction, B: list, deltaB: Fraction):
  result = []
  delta = deltaB / (deltaA + deltaB)
  for i in range(0, 20):
      if floor(i*delta) == floor((i+1)*delta):
          result.append(B[i-int(floor((i+1)*delta))])
      else:
          result.append(A[int(floor(i*delta))])
  deltaC = (deltaA*deltaB)/(deltaA+deltaB)
  return result, deltaC

def dehashodd(C: list, deltaC: Fraction, deltaB: Fraction):

  result = []
  deltaA = deltaB*deltaC / (deltaB - deltaC)

  for i in range(0, 6):
      result.append(C[i+int(i*deltaB/deltaA)])
  return result, deltaA

def main():
    hash_result, delta_hash = hash(B, deltaB, A, deltaA)
    print("Hash(A,B):", hash_result[0:10], " deltaHash:", delta_hash)
    div_result, delta_div = dehashodd(hash_result, delta_hash, deltaB)    
    print("Div(Hash):", div_result[0:10], " deltaDiv:", delta_div)

if __name__ == '__main__':
    main()

result - odd

$ python dehash_odd.py
Hash(A,B): [1, 'a', 2, 'b', 3, 'c', 4, 'd', 5, 'e']  deltaHash: 1/4
Div(Hash): [1, 2, 3, 4, 5, 6]  deltaDiv: 1/2

This code first joins two streams and then extracts the source data back out.

Sum operation

Summation joins two data streams arriving at different rates.

Source code

# Summation operation on two lists with given steps (delta).
from fractions import Fraction
from math import floor, ceil

A = range(1, 24)
deltaA = Fraction(1, 2)
B = list(map(chr, range(ord('a'), ord('z')+1)))
deltaB = Fraction(1)

def sum(A: list, deltaA: Fraction, B: list, deltaB: Fraction):
  result = []
  deltaC = min(deltaA, deltaB)
  for i in range(0, 20):
      if deltaC == deltaA:
          result.append(str(A[i])+B[int(i*deltaA/deltaB)]),
      else:
          result.append(str(A[int(i*deltaB/deltaA)])+B[i]),
  return result, deltaC

def main():
    print("A:", A[0:10], " deltaA:", deltaA)
    print("B:", B[0:10], " deltaB:", deltaB)
    sum_result, delta_sum = sum(A, deltaA, B, deltaB)
    print("Sum:", sum_result[0:10], " deltaSum:", delta_sum)

if __name__ == '__main__':
    main()

result

$  python sum.py
A: range(1, 11)  deltaA: 1/2
B: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']  deltaB: 1
Sum: ['1a', '2a', '3b', '4b', '5c', '6c', '7d', '8d', '9e', '10e']  deltaSum: 1/2

Difference operation

The complementary operation to sum is the difference operation.

Source code

# Difference (diff) operation on two lists with given steps (delta).
from fractions import Fraction
from math import floor, ceil

A = range(1, 24)
deltaA = Fraction(1, 2)
B = list(map(chr, range(ord('a'), ord('z')+1)))
deltaB = Fraction(1)

def sum(A: list, deltaA: Fraction, B: list, deltaB: Fraction):
  result = []
  deltaC = min(deltaA, deltaB)
  for i in range(0, 20):
      if deltaC == deltaA:
          result.append(str(A[i])+B[int(i*deltaA/deltaB)]),
      else:
          result.append(str(A[int(i*deltaB/deltaA)])+B[i]),
  return result, deltaC

def diff(C: list, deltaA: Fraction, deltaB: Fraction):
  result = []
  deltaC = min(deltaA, deltaB)
  for i in range(0, 10):
      if deltaA > deltaB:
          result.append(C[int(ceil(i*deltaA/deltaB))])
      else:
          result.append(C[i])
  return result, deltaC

def main():
    sum_result, delta_sum = sum(A, deltaA, B, deltaB)
    diff_result, delta_diff = diff(sum_result, deltaA, deltaB)
    print("Sum:", sum_result[0:10], " deltaSum:", delta_sum)
    print("Diff(Sum):", diff_result[0:10], " deltaDiff:", delta_diff)

if __name__ == '__main__':
    main()

result

$ python diff.py
Sum: ['1a', '2a', '3b', '4b', '5c', '6c', '7d', '8d', '9e', '10e']  deltaSum: 1/2
Diff(Sum): ['1a', '2a', '3b', '4b', '5c', '6c', '7d', '8d', '9e', '10e']  deltaDiff: 1/2

Source code

The source code for the examples shown here can be found in the project repository under the /examples/python-model/ directory.

A JavaScript implementation can be tested directly on the site:

https://retractordb.com/assets/interlace.html

https://retractordb.com/assets/sum.html

Graphical Representation

Fig. 2 shows, schematically, the relationships between the developed time-series algebra operators. In the figure, I have combined the relationships between the developed operators, their symbolic notation used in the query language, and the directions of data processing.

The figure shown is also a graphical summary of the content presented in this chapter. I hope this graphical form of representation makes it easier to absorb the rules governing the introduced operators. For clarity, the aggregation/serialization and time-shift operators have been omitted. Be aware that the diagram is incomplete without them.

Summary

I initially modeled these equations as Python programs. The formal form presented here took shape only at the very end of the search process. To numerically prove the correctness of the developed equations, I constructed sequences of operations on streams. If any elements got lost in the course of carrying out the operations shown, it meant I had made a mistake. It turns out, for instance, that it is essential in the implementation never to leave the domain of rational numbers, even for a moment. A mistake can be made by accident, by implicitly casting the result to a floating-point number. Materializing the result as a floating-point number must be deferred, in the calculations, until the result is explicitly carried over via the floor or ceiling operation. If we assemble a Python program into a sequence of operations on infinite streams and no data disappears as a result of that operation - we have an object ready for further research and formal analysis, ready for a formal mathematical proof of correctness. The formal proof (the mathematical formalism) can be found in the paper titled A Deterministic Method for Processing Data Sequences [3].

The branch of mathematics that contains the research related to these equations is called covering systems [4] within number theory.

ℹ️ Info

Presenting the mathematical foundations of the system is necessary in order to understand the further technical aspects of the solution. The methods presented go beyond the standard material currently taught in technical-science degree programs. This is because I drew the mathematical foundations from an area that, to my knowledge, had not previously been applied in engineering. These are methods that make it possible to build a new way of processing data. This is one of the aspects that sets RetractorDB apart from other similar solutions.

Query Language Construction

Communication between the developed system and the user takes place through a purpose-built, declarative query language. The language’s construction is based on the algebra presented in the previous chapter. Just as, for relational systems, relational algebra forms the basis for the SQL language - in our case, the developed algebra forms the basis for the RQL query language.

RQL stands for RetractorDB Query Language. Its syntax is very similar to SQL syntax. Bear in mind, however, that the correct term here is a False Friend. That is, it looks like SQL, but has little in common with it.

Valid statements in RQL currently begin with a handful of keywords. The most recognizable is the command starting with the keyword SELECT, followed by a list of attributes in the form of algebraic expressions - an algebra based on real numbers.

Statements are written in a text file. Its extension is conventionally .rql, but any other extension will also be accepted and processed. An RQL text file contains a sequence of statements beginning with defined keywords.

The # character starts a comment only when it is the first non-whitespace character on a line. The whole line, including an indented one, is discarded before parsing. Inside a FROM expression, # always means interleave regardless of whitespace. An end-of-line comment starts with //; block comments use /* ... */.

The query language was implemented using the Antlr4 parser generator [5]. The RQL grammar is written down, defined, and after every modification is compiled into the language in which RetractorDB itself was built. Every statement in a query file that is not a comment is compiled, processed, and modifies the system’s internal state. A statement may span multiple lines - line continuation is signaled with a \ character at the end of the line.

DECLARE Command

The DECLARE command is used to declare a data source.

Its syntax is described as follows:

DECLARE field type[N] [, field type[N]]
STREAM name, rate
BINFILE | TEXTFILE | DEVICE source
[TIMEOUT time]
[DISPOSABLE]
[ONESHOT]
[HOLD]

Fig. 3. DECLARE command syntax diagram

The railroad diagram in Fig. 3 was generated from the declare_statement rule in the system’s ANTLR4 grammar (RQL.g4). The diagram is read by following the lines from left to right: rounded green boxes are keywords and symbols entered literally, rectangles are values supplied by the user. A loop looping back through a comma means multiple field declarations are possible; the branch at the rate shows it can be written as a fraction (numerator/denominator) or as a single number; the branch before the source is the choice of the source kind (BINFILE, TEXTFILE, DEVICE or the deprecated FILE); the track bypassing TIMEOUT means the read deadline is optional, and its value - like the rate - is written as a fraction or a number; tracks bypassing DISPOSABLE, ONESHOT, and HOLD mean each of these directives is optional.

Source kinds

The data format follows from the keyword, never from the name or extension of the path:

DECLARE MLII INTEGER, V1 INTEGER STREAM ecg, 1/360 BINFILE 'rec205'
DECLARE bp_coef INTEGER[25] STREAM bpf, 1 TEXTFILE 'bp_coef.txt'
DECLARE sample BYTE STREAM sensor, 0.02 DEVICE '/dev/urandom'

The extension selects nothing: BINFILE 'bytes.txt' reads raw bytes, and TEXTFILE 'values.dat' parses text.

DEVICE is a live source, so it takes neither DISPOSABLE nor HOLD - these directives apply to replayed files (BINFILE, TEXTFILE), see Read Options. It does take ONESHOT and its own TIMEOUT clause, described in Reading a DEVICE source and TIMEOUT. Opening a FIFO declared as DEVICE does not wait for a writer - the plan starts, and the writer may connect later.

The words BINFILE, TEXTFILE, DEVICE and TIMEOUT are reserved - no stream or field may be named that way (in lowercase either).

File kind check

Before the plan starts - also on a plan reload (xqry --reset) and on an ad hoc import (xqry -a) - the system checks the kind of file at the path of every declaration, without opening it. A path of the wrong kind (a directory, a block device, a socket, a FIFO for BINFILE/TEXTFILE, a regular file for DEVICE) refuses the plan with the stream name and the path, e.g.:

xretractor: stream 'src': BINFILE 'feed.fifo' is a FIFO, not a regular file

A path that does not exist is not a refusal: the stream then yields NULL records. Whether read warnings are available depends on the build mode, as described below for DEVICE. Compilation with -c does not perform this check - it does not have to run on the machine with the data.

Reading a DEVICE source and TIMEOUT

Reading a DEVICE source never waits without end and never holds up the rest of the system. The device or FIFO is opened and read without blocking, and the only waiting happens before the slot is computed, outside the data model locks. An xqry client therefore gets its answer also while the engine waits for device data, and the waiting time does not enter the measured slot computation time (E1).

The optional TIMEOUT clause gives the read deadline in seconds. The value is written the same way as the stream rate - as a fraction, a number with a point, or an integer:

DECLARE a BYTE STREAM s0, 1/50 DEVICE '/dev/sensor0'
DECLARE b BYTE STREAM s1, 1/50 DEVICE '/dev/sensor1' TIMEOUT 1/100
DECLARE c BYTE STREAM s2, 1/50 DEVICE '/dev/sensor2' TIMEOUT 0

An explicit clause wins over the configuration - including an explicit TIMEOUT 0, which switches off a positive value from retractor.toml for a single source. A negative value is an error: there is no “wait forever” deadline. A deadline longer than a day is a plan error as well, and so is TIMEOUT on BINFILE, TEXTFILE and the deprecated FILE (on FILE with a hint to declare the source with an explicit DEVICE). The configuration key is described in Command-line options - xretractor.

Reading properties:

• The deadline is not renewed. A system call interrupted by a signal and a spurious wakeup do not extend the wait - the deadline is fixed from the start of the slot.
• Several sources wait in parallel. All DEVICE sources due in a slot wait together, so the slot grows by at most the largest deadline, not by their sum.
• An incomplete record survives the deadline. Bytes that arrived before the deadline wait in the source buffer; a record completed later goes to the next due slot. Only a record that is incomplete at the moment the writer disconnects is dropped - the record boundary is lost together with the writer, so the next writer starts a new record.
• The moment of reading. A DEVICE record consumed in slot k is read at the start of slot k, not at the end of the previous slot as for BINFILE and TEXTFILE. The logical record indices are the same: the same bytes given as BINFILE and through a FIFO as DEVICE give the same results, also behind operators that join streams of different rates.
• End of data. The end of data is decided only by a read returning zero bytes (a FIFO without a writer, a hung-up terminal). Without ONESHOT it means “there is no writer right now”: the slot gets a NULL record, the source stays open, and a writer connecting again resumes the data. With ONESHOT (also in --until-eof mode) exhaustion is the first end of data after at least one byte was received - an end before the first data is a writer that has not connected yet. A writer that connects and disconnects without writing therefore does not end the run.
• A read error other than a momentary lack of data (e.g. an unplugged USB device) gives NULL records without exhausting the source. Reopening an unplugged device is not supported.
• Mode without a clock. In --no-clock (-f) mode the deadline of every DEVICE source is 0: real seconds have no conversion to virtual time. One immediate attempt in every due slot remains, so a FIFO with data written up front gives a repeatable run.

Dropped incomplete records and changes in the DEVICE connection state (no writer, resumed data, read error) have diagnostics at the WARN level. These warnings are available in the log in a Debug build; in Release, they are disabled at compile time by SPDLOG_ACTIVE_LEVEL=SPDLOG_LEVEL_ERROR. The absence of a warning in Release therefore does not confirm a successful read or complete records. Diagnostics at the ERROR level remain available.

The effective deadline of every DEVICE source and its origin (RQL, config, default or no-clock) goes to the engine log when the plan starts and on an ad hoc import, e.g. DEVICE stream 's1': effective TIMEOUT 0.01 s (RQL). The xretractor -c listing shows an explicit clause in the same form as the rate, e.g. timeout=1/100.

⚠️ Warning Limits of real time:

• Reading without blocking does not protect against a driver that blocks inside the read call despite the non-blocking mode. Such a device needs isolation in a separate process or thread.
• A deadline longer than the stream rate overruns the slot. Compilation then prints a warning, e.g. DECLARE s1: TIMEOUT 0.05 s (RQL) is longer than the interval 0.02 s; waiting overruns the slot, taking the value from retractor.toml into account as well.
• Every clocked mode, with the --realtime option and without it, schedules slots against a fixed anchor of the time axis. Waiting for a DEVICE source that fits in the slot together with the computation does not shift the following slots. A longer wait delays the next slots, which are then made up without sleeping; if waiting and computation persistently exceed the period, the backlog grows - see Slot schedule.
• The schedule does not synchronize the device clock. A producer persistently faster than the plan still builds a backlog in the source buffer. A persistently slower one lacks samples: this gives NULL records in the ticks in which a record did not arrive in time, and TIMEOUT can at most turn them into a delay growing together with the shortfall.

NOTE: Reading a DEVICE source, TIMEOUT and the end of data are covered by the device_timeout test and by the ut_faccbindev unit test.

Field types

Every field has a name and a type. Available types:

Field arrays (type[N])

Any field can be given an array multiplier [N] - the field then occupies N × type_size bytes and creates N consecutive positions in the record schema:

DECLARE coef INTEGER[25] STREAM filter, 1 TEXTFILE 'coefficients.txt'

The field coef INTEGER[25] creates a record of size 25 × 4 = 100 bytes and gives access to indices filter[0] … filter[24]. This is the standard way of passing coefficient arrays (e.g. FIR filters) into the system.

Multiple fields of different types can be combined in a single record:

DECLARE id UINT, value FLOAT, name STRING[16] \
STREAM measurement, 0.1 \
BINFILE 'sensor.dat'

Record size: 4 + 4 + 16 = 24 bytes.

RetractorDB, running under Linux, reads and writes data to files. On Linux, access to most resources is carried out through access to various kinds of files. This approach unifies the way data is accessed.

An example of a command that creates an object in RetractorDB returning random values from the /dev/random stream 10 times per second, with values of type int, looks as follows:

DECLARE random_field INTEGER STREAM random_stream, 0.1 DEVICE '/dev/random'

A file declared as TEXTFILE is interpreted as a continuous, unbounded data file read line by line. Upon reaching the end of the file, reading resumes from the beginning. Basic support for the format is provided - if we specify two integer fields in the declaration, and the file contains two integer values separated by a space, those values will be read as consecutive elements of the record.

DECLARE field_1 INTEGER STREAM cyclic_stream, 0.1 TEXTFILE 'file.txt'

NOTE: The functionality described here is covered by the test: Pattern7, described in the appendix Integration Tests.

A file declared as BINFILE is read as a sequence of raw records, also in a loop: after the last record has been read, the read position moves back to the beginning of the file.

The three optional directives (ONESHOT, DISPOSABLE, HOLD) control the lifecycle of file sources - a detailed description and comparison table can be found in the chapter Read Options.

Deprecated FILE form

DECLARE ... FILE 'path' is still accepted for backward compatibility. The source kind is then chosen by a fixed rule from the path - the same rule the system applied before the explicit keywords existed. The rows of the table are checked in order:

After translation the rules of the chosen kind apply, including the file kind check. A FILE pointing at a FIFO outside /dev is refused with a hint of the right keyword:

xretractor: stream 'src': BINFILE 'feed.fifo' is a FIFO, not a regular file (deprecated FILE resolved this path as BINFILE; declare it with DEVICE)

A FILE declaration resolved as DEVICE gets the whole DEVICE reading described above and takes ONESHOT, but not DISPOSABLE, HOLD or TIMEOUT - its deadline comes only from [sources] timeout_s or is 0. New plans should use the explicit keywords - the FILE form will be removed from the language in the future. FILE in the SELECT command still only names the result file and is not a deprecated form.

The warning about the deprecated form is silent by default, so existing plans do not change the program output. With --verbose (-v) xretractor prints one warning per declaration to stderr - at startup and in -c mode:

xretractor: warning: line 3: DECLARE core: FILE 'data.txt' is deprecated, resolved as TEXTFILE

On an ad hoc import (xqry -a) and on a plan reload (xqry --reset) the server’s --verbose decides, and the warning goes to the server’s stderr.

Source descriptor

The system writes the descriptor of every declaration in the storage directory as <stream_name>.desc: the fields, the path (REF) and the type (TYPE BINFILE, TYPE TEXTSOURCE or TYPE DEVICE). The descriptor stays between runs and on the next start it must match the plan also in type and path. Changing the source kind or the path while the descriptor is kept refuses the plan with the stream name:

xretractor: stream 'src': temp/src.desc was written for source 'v.txt' and the plan reads 'w.txt'; remove temp/src.desc to start the stream afresh

The exception is a descriptor written by earlier versions of the system for a regular binary file: it had TYPE DEVICE. If apart from the type it matches the plan, the start replaces it with a descriptor carrying TYPE BINFILE.

NOTE: Source kinds, the file kind check, the deprecated form and the descriptor are covered by the test source_kinds.

ℹ️ Info

Support for NULL values (per field) is implemented in RetractorDB. Null metadata is stored in the .meta file alongside the binary data, managed by the metaData class.

DECLARE Read Options

The DECLARE command accepts three optional directives that affect how a declared file source is read and its lifecycle:

DECLARE field type STREAM name, rate BINFILE | TEXTFILE source
    [DISPOSABLE]
    [ONESHOT]
    [HOLD]

The directives are independent and can be combined freely. They apply to replayed files (BINFILE, TEXTFILE). The live source DEVICE takes only ONESHOT of them, with the meaning described below - see the matrix at the end of the chapter. The read deadline of DEVICE is set by the separate TIMEOUT clause, described in the DECLARE Command chapter.

ONESHOT

Without ONESHOT, a file is read in an infinite loop - once the end of the file is reached, the read position returns to the beginning. ONESHOT disables the loop: the file is read exactly once, and once exhausted the stream returns records with every field marked NULL. The record bytes are zeroed, but the null markers distinguish missing data from a numeric zero. Exhausting the file neither ends the process nor deletes the file.

DECLARE measurement INTEGER STREAM burst, 0.1 BINFILE 'data.dat' ONESHOT

Use case: one-off loading of historical data into the system.

A DEVICE source has no file to rewind, so ONESHOT changes only the meaning of the end of data. Without ONESHOT the end of data means there is no writer: the slot gets a NULL record, and a writer connecting again resumes the data. With ONESHOT exhaustion is the first end of data after at least one byte was received; from then on the source returns only NULL records, also when another writer connects.

DECLARE sample INTEGER STREAM recording, 1/100 DEVICE '/tmp/recording.fifo' ONESHOT

The --until-eof (-u) option of xretractor reads all sources as if every declaration carried ONESHOT, and stops processing once the first of them is exhausted. For a DEVICE source exhaustion is checked before the slot that would get a NULL record from beyond the end of data, so such a record reaches no stream.

DISPOSABLE

When the source’s storage is closed - at the end of the process or when the plan is replaced - the system deletes the input file named in the declaration itself, the stream descriptor (.desc) and the metadata files (.meta, .meta.shadow), if they exist. The deletion depends neither on the end of the data nor on ONESHOT: a file read in a loop is deleted at closing as well, even if it was not read to the end.

DECLARE temp INTEGER STREAM one_time, 0.1 BINFILE 'temp.dat' DISPOSABLE ONESHOT

The combination DISPOSABLE ONESHOT is useful for temporary one-off input, but it is not required.

HOLD

The file is opened when the plan starts, but physical data reading is held until the first request for this stream’s data - fetching data by a query or preparing a record for a client (e.g. an Ad Hoc query). Merely listing the plan does not release the hold. Until the stream is queried, the system shows zero values for it; the first record of the file is read in the next step after the release. The hold is one-off - it does not return when the consumers go away.

DECLARE sparse INTEGER STREAM optional_stream, 1.0 BINFILE 'sparse.dat' HOLD

Use case: keeping the start of a recording until it is first needed, e.g. on user request via xqry. The combination ONESHOT HOLD replays the file once, from the moment of the first request.

Comparison table

Options and source kinds matrix

DEVICE with DISPOSABLE or HOLD is a compile error naming the stream and the option, e.g. DECLARE s: DEVICE does not take HOLD. The reasons: holding the reads does not stop the producer, it only builds up a backlog, and DISPOSABLE would delete the path of the device or FIFO, whose lifecycle does not belong to the reader. ONESHOT on DEVICE does not rewind a file, it only marks the end of data - see ONESHOT.

The deprecated FILE form resolved as DEVICE (a /dev/... path) behaves the same: it refuses DISPOSABLE and HOLD and accepts ONESHOT - see Deprecated FILE form.

SELECT Command

Every SELECT command in RetractorDB creates a continuous query. These queries run from the moment they appear in the system until the system shuts down.

The syntax of the SELECT command is as follows:

SELECT algebraic_expression [, algebraic_expression] 
STREAM output_stream_name [instance_count]
FROM stream_algebraic_expression 
[FILE 'artifact_file_name'] 
[RETENTION capacity [segments]]
[VOLATILE | PERSISTENT]
[STORAGE profile]

Fig. 4. SELECT command syntax diagram

The railroad diagram in Fig. 4 was generated from the select_statement rule in the system’s ANTLR4 grammar (RQL.g4). The diagram is read by following the lines from left to right: rounded green boxes are keywords and symbols entered literally, rectangles are values supplied by the user. The branch after the word SELECT shows that the field list is either an asterisk (the full record) or one or more expressions separated by commas (a loop looping back through a comma). An optional size in square brackets after the stream name creates a stream family. Tracks bypassing the FILE, RETENTION (with an optional second parameter - the number of segments), VOLATILE/PERSISTENT, and STORAGE clauses mean each of them is optional.

Readers familiar with SQL will immediately notice that the command shown above differs significantly from what they know from relational databases.

The first difference, beyond syntax, is that once entered into the system, these commands run until the system shuts down. Every SELECT command is a continuous query. The STREAM clause requires the author to give every query a unique name. While the algebraic expressions in the SELECT clause’s field list don’t differ from the form familiar from relational systems, the stream algebraic expression must satisfy the conditions presented in the previous chapter on algebraic expressions. The optional FILE and RETENTION clauses provide processes for directing results and managing their retention. Old, segmented output files can be deleted on an ongoing basis, keeping room in the system for new data in continuous motion.

An example of a query creating a new data stream might be the following RQL command.

SELECT str1[0]*10 + str1[1]*10, str1[2] STREAM str1 FROM A+B

A query built this way assumes that someone has declared streams A and B. This could have been done with the DECLARE keyword or with another SELECT command. Based solely on the line containing the query, we cannot tell how fast the data of stream str1 arrives. This information is computed at compile time, based on streams A and B and the algebraic expression in the FROM clause.

Stream generators

An optional size after the name in the STREAM clause expands one template into that many queries. The $ symbol denotes a zero-based instance ordinal:

DECLARE cell INTEGER[4] STREAM cells, 1/10 TEXTFILE 'cells.txt'

SELECT cells[$] STREAM cell[4] FROM cells
SELECT *        STREAM grouped FROM cell[0]#cell[1]#cell[2]#cell[3]

The first SELECT creates the physical streams cell$0, cell$1, cell$2, and cell$3. A reference such as cell[2] in the FROM clause denotes instance cell$2; in a SELECT-list expression, cells[2] still denotes field index 2.

Within a template, $ may occur:

• as a field index, for example cells[$] or cells[3-$];
• as an expression value, for example cells[0]+$;
• in a reference to another family in the FROM clause, for example cell[$]@(2,4).

A generator-index expression is integral and may contain literals, $, parentheses, and the operators *, +, and -. The family size must be positive and the template must actually use $. A generator cannot carry a FILE clause because one file name cannot serve multiple streams. The compiler also rejects family indices outside the declared range, negative field indices, field indices beyond the source’s slots, and collisions between generated and existing stream names. The field-index range is checked by the same rule as for a hand-written index - see Index out of range.

Expansion is the compiler’s first pass. Afterwards the plan is identical to one containing hand-written cell$0…cell$3 streams; runtime has no separate generator mechanism.

A generator may cover successive stages of the same pipeline. This lets one computation be written once and applied independently to every input channel:

DECLARE sample INTEGER[8] STREAM samples, 1/1000 TEXTFILE 'samples.txt'

SELECT sample[$]^2 STREAM square[8] FROM samples
SELECT *           STREAM energy[8] FROM SUMC(square[$]@(25,100))

This creates eight pairs of square$N and energy$N streams, one per channel. The $ symbol selects a family-instance ordinal while the template is expanded. Do not confuse it with [_], which replicates a field expression within one query according to the flattened input schema.

NOTE: Generator syntax, including [$], is checked by the stream_generator integration test and by ut_compiler cases in test/UnitTest/test_compiler.cpp. Record-window aggregates are checked by window_aggregate. Integration tests are described in Integration Tests.

The VOLATILE clause creates an ephemeral form of the query. Its data remains in an in-memory buffer whose capacity the compiler sets to meet the plan’s needs; only the descriptor describing the data structure appears on disk.

The STORAGE clause allows choosing how the artifacts created are managed and stored. The full table of types, with a description of each, is in the chapter Storage Types.

FROM clause operators

The stream algebraic expression in the FROM clause can include:

MIN/MAX/AVG/SUMC(expression : W) aggregates occur in the SELECT list rather than the FROM stream expression. They reduce W historical records and may be operands in a larger field expression, for example 2*MIN(a : 5)+1. See Aggregate Operators for both aggregation axes.

Precedence and associativity

From strongest to weakest binding:

1. a reducer call, stream name, or parenthesized expression;
2. the chainable postfix operators @, &, %, >, -, and the deprecated .aggregator form;
3. interleave #;
4. sum +.

The binary operators # and + are left-associative. Postfix operators also compose from the left, so A@(1,4)&2 means (A@(1,4))&2.

⚠️ Warning A#B>N means A#(B>N), because shift binds more tightly than interleave. To shift the interleave result, write (A#B)>N. The same rule applies to A#B-r.

Whitespace around # does not affect its meaning: A # B and A#B are the same interleave.

Field expressions

The SELECT list and RULE conditions use scalar expressions containing field references, arithmetic operators, NULL values, and functions. The complete syntax, precedence, function list, and conversion rules are documented in Field Expressions and Scalar Functions.

Exponentiation

The ^ operator exponentiates numeric values in the SELECT list and in RULE conditions. It binds more tightly than * and /, which in turn bind more tightly than + and -. Exponentiation is right-associative:

SELECT v*w^2, v^w^2 STREAM powers FROM source

This means v*(w^2) and v^(w^2). Writing (v*w)^2 requires explicit parentheses.

For integer and rational types, a non-negative integral power has exactly the semantics of repeated multiplication, including type promotion and overflow. Other cases use floating-point computation; an infinite or NaN result becomes NULL. Text operands are not allowed.

ℹ️ Info A negative literal is one grammar atom: -2^2 means (-2)^2. For a field, -v^2 means -(v^2). Use parentheses whenever the intended grouping might be unclear.

⚠️ Warning After an interleave A#B, do not refer to its components as A[0], A.field, A[_], or A.*. An interleave has one shared schema; use the output stream name or recover a component with &/%. See Aliasing for details.

NOTE: The shift operator A > N is covered by the test: issue56_timeshift, described in the appendix Integration Tests.

NOTE: Null-value propagation through SELECT expressions is covered by the test: issue121_null_propagation, described in the appendix Integration Tests.

DEFAULT VOLATILE sets default volatility for the plan. PERSISTENT overrides it for one result. See VOLATILE and PERSISTENT.

Field Expressions and Scalar Functions

A field expression computes one value of an output record. It occurs in the SELECT list, in a RULE condition, and as the argument of a record-history aggregate. Do not confuse it with the stream expression in FROM, which constructs and schedules an entire stream.

Building an expression

Operands are numeric and text literals, $ inside a stream generator, field references, and function results. A field may be addressed by name, stream-qualified name, or flat index, for example temperature, src.temperature, and src[0]. For a numeric declaration a T[N], bare a denotes the complete array entry and is not a scalar operand; use a[0]…a[N-1]. STRING[N] is one text field.

The basic arithmetic operators are +, -, *, /, and ^. Parentheses change grouping. * and / bind more strongly than + and -; exponentiation ^ binds most strongly and is right-associative:

SELECT v*w^2, v^w^2, (v*w)^2 STREAM powers FROM source

These fields mean v*(w^2), v^(w^2), and (v*w)^2. A negative literal is one grammar atom: -2^2 means (-2)^2, while -v^2 means -(v^2).

For integer and rational types, a non-negative integral power has the semantics of repeated multiplication, including type promotion and overflow. Other cases use floating-point computation; an infinite or NaN result becomes NULL. Text operands are not allowed.

NULL propagates through ordinary arithmetic. Division by zero yields NULL for every numeric type and does not stop later stream processing. Comparison and three-valued logic in a RULE condition are documented in Logical Condition.

Addition, subtraction, and multiplication on UINT fields are checked: a sum or product outside the unsigned 32-bit range, or a negative difference, yields NULL instead of a wrapped value. An operation on an INTEGER and a UINT operand is computed on the exact values, and only the result is narrowed to UINT: it yields NULL only when the result does not fit. With u = 10 and i = -2, u + i yields 8 while u * i yields NULL; comparing such a pair, for example i < u, is exact as well. INTEGER and RATIONAL arithmetic also yields NULL on overflow.

⚠️ Warning After an interleave A#B, do not refer to its components as A[0], A.field, A[_], or A.*. An interleave has one shared schema; use the output stream name or recover a component with & or %. See Aliasing.

Unary operators

The behavior in this section requires an engine version containing the fix for #328.

The operators +, -, and ~ accept a field, a function result, or a parenthesized expression. Each item in the SELECT list still produces one output field, and an operand in a RULE condition remains part of that condition.

For a BYTE value of 0, both -a and ~a yield 255; for 1 they yield 254, and for 255 they yield 0. For UINT, the corresponding results for 0 and 1 are 4294967295 and 4294967294. This is neither subtraction from zero nor logical NOT. To obtain an arithmetic negative value from an unsigned field, explicitly convert its type first, for example -to_double(a).

The type is that of the computed operand, rather than just the source field. The literal -1 is a negative INTEGER; it does not use the bitwise-complement rule for BYTE or UINT. An allowed operator passes NULL through unchanged. Overflow in arithmetic negation of an INTEGER or RATIONAL yields NULL; for example, -a over an INTEGER value of -2147483648 yields NULL.

The operand of a unary operator includes exponentiation, multiplication, and division, but stops before binary + or -. Thus -a+1 means (-a)+1, while -(a+1) negates the entire sum. -a*b means -(a*b); write (-a)*b to negate only a. This distinction can change the operand type, the bitwise-complement result, or where overflow occurs. Likewise, ~a*b means ~(a*b). The exponentiation distinction remains: -2^2 yields 4, whereas -a^2 means -(a^2); write (-a)^2 to square a negated field.

DECLARE b BYTE, u UINT, i INTEGER STREAM src, 1 TEXTFILE 'source.txt'
SELECT -src[0], ~src[0], -src[1], ~src[1], +src[2], -(src[2]+1), -src[2]+1 STREAM unary FROM src
RULE negative ON unary WHEN -unary[4] < 0 DO DUMP -1 TO 0

For input 0 1 5, the result has seven fields: 255, 255, 4294967294, 4294967294, 5, -6, -4. The rule checks the negation of the fifth field, that is -5 < 0.

-a over STRING and ~a over INTEGER, RATIONAL, FLOAT, DOUBLE, or STRING are rejected during compilation, both in SELECT and in a RULE condition. Diagnostics state the reason: unary '-' is not defined for STRING or unary '~' is defined only for BYTE and UINT, not for .... When checking a file with xretractor -c, the reason appears in Check result:. Rejecting such an ad-hoc query (xqry -a) leaves the running plan and service active.

Available scalar functions

The sole name-and-arity list shared by the compiler and evaluator is the rqlFunctions.hpp table. Matching is case-insensitive and the canonical spelling is stored in the plan. An unknown function or invalid arity stops compilation rather than being deferred to runtime.

Every function takes one expression argument. The only exception is the optional output field width in to_string(expression : width).

Predicates and missing values

• isnull(x) returns 1 for NULL and 0 for a present value;
• null2zero(x) maps NULL to integer zero but passes a present value without changing its type;
• IsZero(x) and IsNonZero(x) return integer 1 or 0 for a numeric argument.

null2zero is lossy: afterwards, an original missing value cannot be distinguished from an actual zero. It does not replace the NULL bitmap stored in .meta.

String length

Length(x) accepts a string only. It counts the actual value up to the first zero byte, not the declared STRING[N] width. A STRING[8] field containing alpha therefore yields 5. A numeric argument is a runtime error.

Conversions

to_integer, to_float, and to_double convert a numeric or textual value to the named type. NULL passes through unchanged. to_integer truncates toward zero rather than flooring: to_integer(-8/3) yields -2. A floating-point value that INTEGER cannot hold - NaN and infinity included - yields NULL, exactly like arithmetic overflow. The same rule covers mathematical functions over an integer field whose result returns to the argument type: Sqrt(-4) and log(0) over an INTEGER field yield NULL. The range is checked after truncating the fractional part: for a DOUBLE argument, the value 2147483647.5 yields 2147483647, whereas 2147483648.0 yields NULL. The rule does not stop at integer types: NaN and infinity have no rational approximation, so a floating-point value written into a RATIONAL field yields NULL just as it does for INTEGER, not zero.

Converting an integer or rational value to a narrower integer type also yields NULL if the result does not fit: this includes a negative value directed to UINT, a UINT above INT_MAX directed to INTEGER or RATIONAL, and a value outside 0..255 directed to BYTE. Conversion from RATIONAL to an integer type first truncates toward zero, then checks the range. Invalid numeric text yields NULL. Approximation of a finite floating-point number as RATIONAL stops at the last fraction whose numerator and denominator both fit in int. For a finite FLOAT or DOUBLE argument, the integer part of its absolute value is checked first: 2147483647.5 and -2147483647.5 can be approximated, while 2147483648.0 and -2147483648.0 yield NULL.

to_string creates a text field. Without a second part its width is 32 bytes; to_string(x : N) declares N bytes. The separator is a colon because a comma separates fields in the SELECT list:

N must be in 1..65536. to_string(x : 0) is a parser error (to_string width 0 must be greater than zero), and the resulting string concatenation must also fit the field limit. See Plan Size Limits.

SELECT to_string(value : 10), Length(label), null2zero(optional) \
STREAM converted FROM source

The output text width is inferred after field references have been resolved, so a pure copy of STRING[N] and text concatenation retain the correct descriptor. The type of the whole expression, including numeric expressions, is determined by compiler::inferFieldShapes() after field references are resolved; see Type Promotion.

The declared width is a property of the field, not a side effect of one particular compilation pass. It also holds when the whole argument is constant: to_string(42 : 16) yields STRING[16], not STRING[2]. Expression simplification folds the argument underneath the call but never removes to_string itself - otherwise the declaration would disappear together with the program on a second compilation of the plan, that is after an ad-hoc query (xqry -a), which compiles the live plan a second time.

sin, cos, and exp

All three functions take a numeric argument and return DOUBLE, regardless of the argument’s type. sin and cos interpret angles in radians. For an INTEGER field k, the expressions sin(k), cos(k), and exp(k) therefore produce DOUBLE fields without truncating fractional results. A NULL argument yields NULL; a non-finite result, such as exp(1000), also yields NULL without stopping the stream.

A RATIONAL argument is the exception: the compiler rejects it and requires an explicit to_double, exactly as it does for Sqrt - see the section below.

Changing the result type of sin and cos can change the .desc descriptor and record layout relative to an older engine: INTEGER and FLOAT occupy 4 bytes, while DOUBLE occupies 8. An existing artifact with the old schema must be recreated or written to a separate output stream.

Irrational functions over a RATIONAL value

Sqrt, sin, cos, exp, tan, log, and log2 do not accept a RATIONAL argument - the compiler rejects such a query through the Check result: channel and names the workaround. In practice this concerns stream reducers over BYTE, INTEGER, UINT, and RATIONAL fields, whose result type is RATIONAL. Reducers over FLOAT and DOUBLE preserve the input type:

SELECT * STREAM m FROM AVG(src)
SELECT Sqrt(m[0]) STREAM o FROM m              // rejected at compilation
SELECT Sqrt(to_double(m[0])) STREAM o FROM m   // correct

One rule applies: a function with an irrational range over an exact rational value requires an explicit to_double. The same rule covers a rule condition (RULE ... WHEN), which the compiler checks in a separate pass.

For Sqrt, tan, log, and log2, the reason for the gate is the return from a double calculation to RATIONAL: the result used to be approximated by a fraction with a large denominator (for the rational argument 2/1, the square root yielded 19601/13860 and the logarithm 2731/3940). In an older version, two further multiplications of such an approximation could silently overflow its 32-bit numerator or denominator; Sqrt(x)*Sqrt(x)*Sqrt(x) returned -4.247 instead of +2.828. Arithmetic on INTEGER and RATIONAL field values now detects overflow and writes NULL, but these functions still require an explicit to_double.

For sin, cos, and exp the reason is different: these three end at DOUBLE and never return to RATIONAL, so they would compute correctly. Their rejection is a language contract decision, made so that no list of exceptions has to be remembered - one rule instead of seven separate behaviours. The price is a to_double in every query computing, say, an RMS over a reducer.

The restriction extends neither to the remaining functions nor to other argument types. The rounding functions Floor, Ceil, round, and trunc over RATIONAL are safe, because their result is integral and therefore has denominator 1, and Abs operates on the value directly and never touches the denominator.

The gate covers only the pairing with RATIONAL and changes no function’s result type. tan, log, and log2 over INTEGER still yield INTEGER, that is, they truncate the fractional part - an explicit and intended loss, not an overflow. Bringing them to DOUBLE, as sin, cos, and exp are, would change the field type in .desc, so it is a separate task.

NOTE: Functions and type propagation are covered by the integration tests fncall_runtime_case, string_field_passthrough, issue121_isnull, issue128_numeric_to_string, and issue128_string_to_numeric, and by the ut_compiler, ut_expeval, and ut_facctxtsrc unit tests.

Summation Operation Sequencing

Data flows into the system and is processed within it. The order in which it arrives and is processed can be described by the term sequencing. The way data is combined is described by the algebraic expression placed in the FROM clause. These expressions are written as a series of algebraic operations subject to strict rules - rules similar to those we learned in elementary school, governing arithmetic operations on numbers such as addition, multiplication, division, and subtraction.

Let’s start by analyzing the following query:

DECLARE a BYTE STREAM A, 1 TEXTFILE 'data1.txt'
DECLARE a BYTE STREAM B, 2 TEXTFILE 'data2.txt'
SELECT * STREAM str1 FROM A+B

I’ll save the query in a file named qplan1.rql. Then I’ll run the following commands:

$ xretractor -c qplan1.rql -w 1:3 > out.txt
$ swirly out.txt -o out.svg

The swirly program was installed from its GitHub repository [6]. This program is used to generate marble diagrams used to explain the behavior of RxJs asynchronous operations [7].

The modification I applied for my use case is an alternative meaning for the vertical lines. In my case, vertical lines separate uniform time intervals - showing the number of cycles requested at invocation time (in this case, 3 cycles). The generated image is shown in Fig. 5:

A few words of explanation are needed here about this generator and how its input is produced. I built into the compiler an option for visualizing the execution of a sequence of operations. Diagrams produced by the Swirly program are one convenient way of presenting time dependencies. On input, the Swirly program expects a text file describing the diagram. A generator that simulates the requested number of cycles and builds a file for Swirly has been built into the compiler.

When xretractor is given, as its first parameter, the name of the file containing the query execution plan, it requires a second parameter ( -w [–diagram] ) - indicating that we expect marble-diagram output. The required argument of the -w parameter is two numbers separated by a colon. The first tells the program whether to insert time separators into the diagram (the vertical lines separating cycles); the second parameter is how many cycles should be shown in the diagram.

If you look at the generated out.txt file, you’ll see the following content:

% Creating diagram output grid is on, cycle count:3
% Minimum interval is 1000ms
% Maximum interval is 2000ms
% Grid time is 500ms, divider:2
% Full cycle step count in grid is 4
-|a-a-|a-a-|a-a-|-
title = A,1

-|b---|b---|b---|-
title = B,2

> SELECT * STREAM str1 FROM A+B

-|c-c-|c-c-|c-c-|-
title = str1,1

In this file, note the data shown in the comments. These are the times computed while generating the diagram, relative to the scale shown in the marble diagram. As you can see, for our query the minimum window interval is 1 second and the maximum is 2 seconds. The identified and computed grid is half a second. On the diagram, each letter or dash represents a half-second period between successive operations.

We can manually change the generated content. If we replace the content as follows:

-|a-b-|c-d-|e-f-|-
title = A,1

-|g---|h---|i---|-
title = B,2

> SELECT * STREAM str1 FROM A+B

-|j-k-|l-m-|n-o-|-
title = str1,1
j:=ag
k:=bg
l:=ch
m:=dh
n:=ei
o:=fi

and then run the swirly program again, we’ll see a more detailed picture showing the sequence of events occurring in the system.

In the diagram shown in Fig. 6, you can see which marbles were joined and which marbles they were formed from. Remember, though, that this is a manually corrected image, made for the purposes of this work - the generator built into the compiler does not implement this functionality.

NOTE: The functionality described here is covered by the tests: Pattern1, issue167_triarg, described in the appendix Integration Tests.

The same name more than once in FROM

A stream may appear in a FROM expression more than once - directly and under another operator, e.g. bar + MAX(bar) or src + src>1, or twice under different operators, e.g. src@(1,5) + src@(2,3). The input record then holds a separate block of fields for each occurrence, and a reference by name (bar[0], src[4]) as well as the SELECT * expansion must point to one of them. The compiler picks the first occurrence in a fixed order: first the direct operands of the expression in the order they are written, only then the streams nested under operators (a reducer, a shift, a window), also in the order they are written. The index range check uses the same order, so the bound of src[k] is measured on the occurrence the reference will actually read.

DECLARE v INTEGER[3] STREAM bar, 1/50 TEXTFILE 'a.txt'
SELECT * STREAM chk FROM bar + MAX(bar)

The chk stream has four fields: the three fields of the bar that stands directly in FROM, and the record maximum. A direct operand always points to its own fields, even when it is written second: in src>1 + src the reference src[0] reads the current sample, not the shifted one. In src@(1,5) + src@(2,3) the name src is reachable only through windows, so it points to the first of them: src[4] is valid, and src[5] is a compilation error. To refer to the fields of the second occurrence, give it its own name in a separate query, e.g. SELECT * STREAM w2 FROM src@(2,3), and use w2 in the FROM expression.

NOTE: The first-occurrence rule is checked by the ut_compiler unit tests: direct_operand_keeps_its_own_slots_beside_a_nested_occurrence and range_check_and_offset_agree_on_a_name_reached_twice.

Interleaving Operation Sequencing

Let’s now analyze the interleaving operation. Let’s create a file qplan2.rql with the following content:

DECLARE a BYTE STREAM A, 1 TEXTFILE 'data1.txt'
DECLARE a BYTE STREAM B, 2 TEXTFILE 'data2.txt'
SELECT * STREAM str1 FROM A#B

Aside from the # symbol instead of the + symbol in the from clause, the two files are identical. Let’s run the compilation and the swirly program. The resulting graphic will look as follows:

In Fig. 7 we see a change. The marbles of stream str1 have been evenly arranged in time. The events occurring in the declared input data streams have not changed. What has changed is the way the output stream str1 is built.

If we look at the generated text schema, we’ll see that the time values have changed too:

% Minimum interval is 666ms
% Maximum interval is 2000ms
% Grid time is 333ms, divider:2
% Full cycle step count in grid is 6

I encourage further experimentation with this way of presenting the defined operations on time series.

NOTE: The functionality described here is covered by the tests: operations, Pattern1, described in the appendix Integration Tests.

VOLATILE Clause

The VOLATILE clause in the SELECT command creates a stream stored in memory. On disk, only the .desc descriptor file describing the data schema appears - the data itself is never written.

Default volatility and the PERSISTENT exception

DEFAULT VOLATILE selects in-memory storage for SELECT results without an explicit policy and for compiler-generated substrates. It replaces repeated VOLATILE clauses and the SUBSTRAT 'memory' directive:

DEFAULT VOLATILE
DECLARE a INTEGER STREAM sensor, 0.1 DEVICE '/dev/sensor0'
SELECT sensor[0]*100 STREAM scaled  FROM sensor
SELECT scaled[0]     STREAM history FROM scaled PERSISTENT

scaled stays in memory, while history writes data to disk using the usual FILE, RETENTION, and STORAGE settings. PERSISTENT affects only that SELECT result; its substrates still inherit the default volatility.

The directive may appear once, before the first DECLARE, SELECT, or RULE. It does not change DECLARE sources. Programs without it retain their existing settings. VOLATILE and PERSISTENT are mutually exclusive clauses.

An explicit STORAGE profile on a SELECT overrides the default; for example, STORAGE DEFAULT selects ordinary file storage. Explicit VOLATILE retains its precedence over STORAGE. Combining PERSISTENT STORAGE MEMORY is an error. Explicit SUBSTRAT 'profile' selects substrate storage regardless of the order of the two directives in the header. FILE or RETENTION alone does not disable default volatility: add PERSISTENT to store history. RETENTION capacity segments on an in-memory stream is a compilation error with that hint.

Behavior

SELECT expression STREAM name FROM source VOLATILE

The parser initially sets the storage type to MEMORY with a capacity of 1, or n from a RETENTION n clause:

if (ctx->VOLATILE() != nullptr || inheritVolatile) {
    qry.policy = std::make_pair("MEMORY", std::max<size_t>(qry.policy.second, 1));
}

The compiler then determines the capacity required by the plan. If another stream reads the history of a VOLATILE result, the buffer may hold more than one record. This means that:

• the in-memory buffer holds at least the most recent record and any history its consumers need,
• data never reaches disk,
• the .desc descriptor is still created - other processes can learn the stream’s schema.

The ring has capacity max(RETENTION n, plan need, 1) and counts against [limits] history_memory_mib. Attaching an ad-hoc DO DUMP -H TO M rule requires H+1 slots, including the current record. For H > 0, the server rejects the request when capacity N <= H; the ring cannot be enlarged in a running plan. See Alerting implementation for the rules on waiting for history. See Plan Size Limits.

Difference from STORAGE MEMORY

VOLATILE is useful when the query result is being pulled by xqry on an ongoing basis and history is not needed - e.g. the current value of a sensor exposed by the operating system.

Example

DECLARE a INTEGER STREAM sensor, 0.1 DEVICE '/dev/sensor0'

SELECT sensor[0] * 100 STREAM scaled FROM sensor VOLATILE

The scaled stream contains, at every moment, a single, current value. The xqry process can read it via shared memory.

STORAGE Types

The STORAGE clause in the SELECT command, and the SUBSTRAT directive, accept one of the following identifiers. Each maps to a specific data-accessor class in the implementation.

Type table

Any other value in STORAGE or SUBSTRAT is a compile error. The DECLARE source types - BINFILE, TEXTSOURCE and DEVICE, written to the TYPE field of the source descriptor - are not storage profiles: their accessors (binaryDeviceRO, textSourceRO) are read-only, so a SELECT result cannot be created in them. The source kind is chosen by the keyword in DECLARE.

The refusal names the stream and the allowed profiles:

STORAGE DEVICE of stream dst is not a storage profile but a source kind of DECLARE; use DEFAULT, MEMORY, DIRECT, POSIX, POSIXSHD or GENERIC

In the STORAGE clause a profile, like every keyword, has two spellings - upper case or lower case (MEMORY, memory); Memory is an error. The value of the SUBSTRAT directive is a string and its case does not matter.

Retention - artifacts are rotated, older files are deleted automatically (requires RETENTION capacity segments on SELECT).
Shadow - every modification is written to a separate .shadow file; historical data is protected from being overwritten.

For MEMORY, retention works in memory as a circular buffer: successive appends overwrite the oldest slot (index % capacity). Data is not segmented into files and never reaches disk. RETENTION n sets the ring size (at least what the plan needs) - the same for STORAGE MEMORY and VOLATILE; the segmented form RETENTION n s is a compilation error here.

Even without RETENTION, a MEMORY store has a finite capacity: at least one record, increased by the compiler to meet consumer needs. Formerly, STORAGE MEMORY could grow without bound or, with RETENTION n, write to disk under the wrong storage type. The ring size and total history cost now count against the plan budget. An ad-hoc DO DUMP -H TO M rule requires H+1 slots for history plus the current record. For H > 0 and capacity N <= H, the request is rejected; attaching a rule does not enlarge a live store. See Alerting implementation for the rules on waiting for history.

Retention on disk

The DEFAULT and DIRECT stores keep data in segments: RETENTION capacity segments keeps at most segments files of capacity records each, and the oldest segment is deleted when a new one is opened. The one-argument form RETENTION n means only the size of a MEMORY ring; on a file store it is a compilation error with the hint RETENTION n <segments>. segments = 0 means “no segment limit”.

For example, RETENTION 100 STORAGE DIRECT is rejected because it omits the segment count. Write RETENTION 100 4 STORAGE DIRECT instead. For STORAGE MEMORY the rule is reversed: RETENTION 100 sizes the ring, while RETENTION 100 4 is rejected as segmented retention on a RAM store.

Right after a rotation only (segments - 1) * capacity + 1 records remain on disk. A plan that reads further back into the stream (a >N shift, an @ window, a DUMP range) is a compilation error - reading a deleted segment would stop the running server.

A file stream without RETENTION, with segments = 0, or in a store without retention (POSIX, POSIXSHD, GENERIC) grows on disk without bound. This is allowed - durable history. With --verbose, xretractor lists such streams on stderr, both at startup and in -c mode, including with --quiet and for intermediate streams extracted by the compiler. Without --verbose, this list does not appear on stderr; WARN diagnostics in the log depend on the logging configuration and are disabled in Release builds. The operator can bound every DEFAULT/DIRECT stream without RETENTION with the key default_retention = [capacity, segments] in the [storage] section of retractor.toml. Without that key, history limits come from explicit RETENTION; startup cleanup is described below.

A start without the ROTATION directive begins SELECT outputs and substrates from scratch: it deletes their whole file families - data with its .shadow file, .desc, .meta, and retention segments. It does not delete DECLARE source files. With ROTATION, retained disk-store files must match the plan: if a kept .desc has another storage type or retention, the start (and xqry --reset) is refused, naming the stream and both configurations. For MEMORY, old descriptor and metadata files are removed even under ROTATION, so the new ring cannot inherit the previous plan’s configuration. Changing the capacity over kept segments would shift record addressing, so the operator chooses: restore the previous configuration in the plan, or remove the stream’s files.

NOTE: The MEMORY type (SUBSTRAT ‘memory’) is covered by the tests: issue61_tmpmem (serial and parallel), described in the appendix Integration Tests.

Links in storage paths

Storage writes refuse to follow a symbolic link at the final data, shadow, metadata, or descriptor filename. An explicit caller-supplied REF can authorize a main data-file link; the exception covers neither retention-segment names nor auxiliary files. Links in parent directories remain permitted. See Files for refusal behavior, the REF exception, and the protection boundary.

When to use which

The choice depends on the environment’s requirements:

• Production environment, critical data → DEFAULT (retention + shadow)
• Production environment, historically insignificant data → MEMORY (zero disk usage, retention in RAM)
• Development and debugging → DEFAULT or DIRECT (data visible on disk)
• Reading from a binary file, a text file or a device → not through STORAGE, but through the source kind in DECLARE (BINFILE, TEXTFILE, DEVICE)

Example

SELECT str1[0] STREAM str1 FROM core0 STORAGE MEMORY
SELECT str2[0] STREAM str2 FROM core0 RETENTION 100 4 STORAGE DIRECT

For substrates globally - the SUBSTRAT directive:

SUBSTRAT 'memory'

Aggregate Operators

Two aggregation axes (MIN, MAX, AVG, SUMC)

The same four keywords describe two different constructs. In FROM, a reducer folds the fields of one current record. In the SELECT list, a record-history aggregate folds one expression value evaluated for each consecutive historical record. The location therefore determines whether reduction runs horizontally across fields or vertically across time.

Current-record reducers in FROM

Stream reducers operate on a stream with multiple fields - typically the output of the @(k,w) operator or a record that contains a numeric array. They reduce all flat slots of one record to one value.

Syntax

FROM AGGREGATOR(stream_expression)

where AGGREGATOR is one of:

Keywords are accepted in both lowercase and uppercase. They are reserved, so a stream cannot be named min, MAX, avg, or SUMC.

The argument may be a complete stream expression rather than just one stream name. A window and its reduction can therefore be written without an auxiliary query:

SELECT * STREAM total FROM SUMC(src@(1,5))

The postfix forms stream.min, .max, .avg, and .sumc remain backward compatible but are deprecated. The parser emits a warning and recommends the function form. The existing src@(1,5).sumc syntax is valid, but new queries should use SUMC(src@(1,5)).

The reducer result is not read by name in the SELECT list. The compiler rejects SELECT avg STREAM o FROM AVG(src) through the Check result: channel, because in that position avg is a stream operator rather than a field, and nothing can execute it. Read the reduction result with SELECT *, or - when further computation is needed - materialize the reducer as a separate stream:

SELECT *      STREAM m FROM AVG(src)
SELECT m[0]*2 STREAM o FROM m

Array fields and NULL values

A numeric declaration T[N] is one descriptor entry but occupies N flat record slots. The reducer visits every one of them. This query therefore finds the minimum across all 24 cells in the current record, not just cells[0]:

DECLARE cells INTEGER[24] STREAM battery, 1 TEXTFILE 'cells.txt'
SELECT * STREAM cell_min FROM MIN(battery)

Derived stream schemas expand numeric arrays to scalar fields while preserving slot order and byte layout. STRING[N], by contrast, is one N-byte text field rather than an array of N numbers.

NULL values are skipped. If every slot in the record is NULL, the reduction result is NULL, not zero.

Output interval

Aggregates do not change the stream’s rate - the output interval is the same as the source’s:

\[\Delta_{result} = \Delta_{stream}\]

Result type

The result type depends on the input value type:

Integer and rational inputs are reduced as rational numbers, so AVG does not lose the remainder. This also applies to MIN and MAX: the minimum of three sevens has type RATIONAL and value 7/1, not type INTEGER. FLOAT and DOUBLE preserve their types; an artifact with such an input does not turn into a RATIONAL field.

A consumer of a RATIONAL field must know its numerator-denominator layout (→ The RATIONAL field layout) or explicitly pass the result through to_string, to_double, or to_integer.

Example: mean of an AGSE-window record

DECLARE val INTEGER STREAM src, 1 TEXTFILE 'data.txt'

# AGSE builds a five-sample record; AVG reduces its five fields
SELECT * STREAM ma5 FROM AVG(src@(1,5))

The ma5 stream contains, at every moment, the average of five consecutive src samples. This is an AGSE operator composed with a record reducer, not the SELECT-list aggregate described below.

Example: signal filter (sumc)

An excerpt from the signal-filter implementation example:

SELECT source[_] * filter[_] STREAM accRow FROM source@(1,25)+filter
SELECT accRow[0]             STREAM output FROM SUMC(accRow)

The window appears directly in FROM, so it does not require a separate query. source[_] expands according to the 25 slots contributed to the input record by source@(1,25). SUMC(accRow) sums all fields of the accRow record - the products of signal samples and filter coefficients - producing the output of an FIR filter.

Example: MIN and MAX

DECLARE v INTEGER STREAM src, 0.1 DEVICE '/dev/urandom'
SELECT * STREAM min10 FROM MIN(src@(1,10))
SELECT * STREAM max10 FROM MAX(src@(1,10))

NOTE: Current-record reducers are covered by simple_max, wide_from_names, agse_array, and array_derived, described in the appendix Integration Tests.

Record-history aggregates in SELECT

Syntax

SELECT expression_with_AGGREGATOR(record_value : width) \
STREAM result FROM source

AGGREGATOR(record_value : width) itself is an operand in an ordinary field expression. It may be combined with literals, other fields, arithmetic operators, and scalar functions:

SELECT 2*MIN(a : 5)+1, null2zero(AVG(a+b : 5))-10 \
STREAM transformed \
FROM src

Only nesting a history aggregate inside another history aggregate is forbidden. width is a positive number of records. For an output record with logical index n, the aggregate evaluates record_value separately on source records n-(width-1) through n, then reduces exactly those values. The window is end-stamped and advances by one record. The output interval stays equal to the source interval, logical origin advances by width-1, and the startup tail is inherited from the source.

DECLARE a INTEGER, b INTEGER STREAM src, 1 TEXTFILE 'data.txt'

SELECT MIN(a : 5), MAX(a : 5), AVG(a+b : 5), SUMC(a : 5) \
STREAM stats \
FROM src

Several aggregates over the same expression, source, and width share one history scan. NULL values are skipped; a window with no present value yields NULL. The result follows the same type-promotion table as a current-record reducer, and that type is preserved through pure copies, shifts, and other schema-copying operators.

Argument restrictions

The argument must be a numeric expression that reads at least one field of one stored source. A query containing a record-history aggregate must have one plain stream reference in FROM. The compiler rejects:

• a non-positive width;
• a text expression or a constant that reads no field;
• an expression that mixes histories from several streams;
• a nested history aggregate or an aggregate in a RULE condition;
• a compound FROM clause such as FROM src - 2;
• a bare numeric-array name.

For DECLARE a INTEGER[3], select one channel, for example MIN(a[0] : 5). MIN(a : 5) does not mean all array elements from every record and is rejected. Reduce all elements of one record separately with FROM MIN(stream).

Combining reductions across channels and time

The two axes can be composed without serializing the array or manually creating a separate stream for every channel:

DECLARE value INTEGER[24] STREAM sensors, 1/10 TEXTFILE 'sensors.txt'

SELECT *                    STREAM row_min      FROM MIN(sensors)
SELECT MIN(row_min[0] : 10) STREAM interval_min FROM row_min

The first MIN reduces the 24 parallel values in one record. The second reduces results from ten consecutive records, so interval_min is the minimum of 240 values while retaining the source interval and emitting a sliding window after every record. If a sparser result is needed, decimate the completed stream as described in the next section.

Hopping windows

A SELECT aggregate has no step argument. Build a hopping window by decimating the completed window stream with - in a second node:

SELECT MIN(a : 5) STREAM sliding FROM src
SELECT *          STREAM hopping FROM sliding - 2

The argument of - is the target output interval. For hop H over a source interval \(\Delta\), pass \(H\Delta\). Splitting the construction preserves five consecutive records in every window and only then selects every H-th result. Direct SELECT MIN(a : 5) ... FROM src - 2 is not shorthand for this construction and does not compile.

NOTE: Syntax, types, boundaries, shared computations, expressions, NULL values, and restrictions are covered by window_aggregate and by the ut_compiler and ut_expeval unit tests.

Further computation on an aggregate result

Scalar functions belong to field-expression syntax, not to either kind of window. The full list, name and arity rules, and type semantics are documented in Field Expressions and Scalar Functions. Only conversions particularly relevant when consuming an aggregate result remain below.

isnull(x) returns 1 for NULL and 0 for a present value. null2zero(x) maps NULL to integer zero but passes a present value without changing its type. It is a lossy conversion, not a way to export missingness. Division by zero yields NULL for every numeric type and does not stop later stream processing.

Conversion example: to_string

The to_string function converts a numeric expression to a text string of a given width. The result goes into a field of type STRING in the output stream.

Syntax

to_string(expression : width)
to_string(expression)

The width parameter (a natural number after the colon :) specifies the output field’s width in bytes. Omitting the parameter gives a default width of 32 bytes.

ℹ️ Info

The argument separator is a colon :, not a comma ,. A comma is the SELECT list separator - using a comma in to_string(x, n) will cause a parse error.

Example

DECLARE v INTEGER STREAM src, 1 TEXTFILE 'data.txt'

SELECT to_string(src[0]:10) STREAM labels FROM src

The labels stream contains the values of src formatted as text in a 10-byte field.

Concatenation with a literal

The resulting string can be joined with a string literal using the + operator:

SELECT to_string(src[0]:8) + '_ok' STREAM tagged FROM src

Output field size: 8 (from to_string) + 3 (literal _ok) = 11 bytes.

Use cases

to_string is useful when exporting to systems that accept text data (Graphite, InfluxDB via xqry), or when creating event labels combined with DO DUMP output.

NOTE: The functionality described here is covered by the tests: issue121_isnull, issue128_numeric_to_string, issue128_string_to_numeric, described in the appendix Integration Tests.

Conversion example: to_integer

The to_integer function converts a numeric expression into a field of type INTEGER. It is the primary way of reading an artifact that holds an aggregate: it turns a RATIONAL field into a whole number the reader can consume without knowing the numerator-denominator layout.

Syntax

to_integer(expression)

Rounding

⚠️ Warning

to_integer truncates toward zero; it does not floor. For negative values the result differs from the floor by one.

The rule is the same for a rational and for a floating-point argument - in both cases the fractional part is dropped and the sign is kept:

A NULL passes through unchanged - to_integer(NULL) yields NULL, not zero.

A pitfall when porting to Python

Python’s // operator floors, so a naive transcription of the query diverges from the engine on every negative value:

>>> -8 // 3        # Python: floor
-3
>>> int(-8 / 3)    # what to_integer does
-2

A model reproducing the engine’s behavior has to compute the truncated mean explicitly:

def truncated_mean(values):
    """Truncate toward zero, matching the cast applied to the rational window mean."""
    total = sum(values)
    quotient = abs(total) // len(values)
    return quotient if total >= 0 else -quotient

The same problem arises in any language whose integer division floors.

Use cases

to_integer fits wherever the consumer of the artifact expects a whole number and the fractional part is not needed. Where the value must stay exact, the right choice is to_string, which writes the fraction as the text numerator/denominator, or reading the pair directly (→ The RATIONAL field layout).

NOTE: The functionality described here is covered by the test issue128_string_to_numeric, described in the appendix Integration Tests, and by the unit tests ut_payload and ut_convertTypes, which pin the RATIONAL field layout and the rounding rule.

RULE Command

This command is one of the most recent extensions I have developed for the system. It extends the system’s functionality with an alerting mechanism.

NOTE: The functionality described here is covered by the tests: issue42_rule, described in the appendix Integration Tests.

The syntax of the RULE command is as follows:

RULE rule_name
ON data_stream_name
WHEN logical_condition
DO DUMP steps_back TO steps_forward [RETENTION segments]

Or like this:

RULE rule_name
ON data_stream_name
WHEN logical_condition
DO SYSTEM system_command

Fig. 8. RULE command syntax diagram

The railroad diagram in Fig. 8 was generated from the rule_statement rule in the system’s ANTLR4 grammar (RQL.g4) and covers both forms of the command shown above in a single track: the branch after the word DO leads either to the DUMP variant (with a data-window dump and optional retention), or to the SYSTEM variant (with a system command in quotes). Rounded green boxes are keywords and symbols entered literally, rectangles are values supplied by the user; tracks bypassing the minus sign and the RETENTION clause mean they are optional.

Events defined this way attach to defined data streams. A rule name must be unique within the stream selected by ON; different streams may have rules with the same name. The data stream must be defined before the rule-creation command appears in the rql file.

In both versions of the RULE command, a rule name, a logical condition, and the name of the stream to which the process launched by the DO command is attached are created. The logical condition should refer to variables available in the schema of the data stream following the ON clause.

In the first version of the command, which includes the DO DUMP clause, we define a process that allows collecting data that will arrive in the future. If we omit the RETENTION clause, the dump goes directly to a file named after the rule, prefixed with the stream name. If we add the RETENTION clause, the files will be subject to retention within the range defined by the ‘segments’ parameter. Sequential numbers will be appended to the end of each dump. Dumps are binary and preserve the schema of all fields of the source data stream. It is worth noting here that the command creates a process in the system which, once the logical condition becomes true, pulls data from the past and also expects its arrival and registration in the future. Nothing prevents us, however, from collecting data only from the past or only from the future. If the step_* values are negative, they refer to the past (i.e. to data that is historical relative to the moment the event described by the logical condition occurred).

The DO SYSTEM clause allows a system event to be triggered once the logical condition based on recorded data is met. This way, an arbitrary system command can be invoked.

Examples of rule declarations in RQL:

RULE testrule1 ON str1 WHEN str1[0] > 11 DO DUMP -5 TO 5 RETENTION 100

RULE testrule2 \
ON str1 \
WHEN str1[0] = 13 OR str1[0] = 11 \
DO SYSTEM 'echo "systemcall"'

Assume that a stream str1 has previously been defined, whose data - integer values - arrives once per second. In this case, the first rule, attached to this stream, waits for data whose value exceeds 11. Should such an event occur, a dump of the data is made, covering the range from 5 seconds before to 5 seconds after the event described by the logical condition.

The second rule, with a slightly different logical condition, prints the text “systemcall” to the screen from which the RetractorDB process was started.

RULE Command Syntax

The full syntax of the RULE command is:

RULE <name>
ON <stream>
WHEN <condition>
DO <action>

Where <action> can take one of two forms:

SYSTEM '<system_command>'
DUMP [-]<step_back> TO [-]<step_forward> [RETENTION <n>]

Restriction

A rule can only be attached to a stream declared with a SELECT command (an artifact or substrate). Attaching it to a DECLARE input stream is a compilation error:

# INVALID - core0 is a declaration, a rule cannot be attached to it
RULE r1 ON core0 WHEN core0[0] > 10 DO SYSTEM 'echo alarm'

The WHEN condition

The condition is a logical expression evaluated to true/false after every new sample of the stream.

Comparison operators: =, !=, <, >, <=, >=. Logical operators: OR, AND, NOT. Examples:

WHEN str1[0] > 100
WHEN str1[0] = 0 OR str1[0] = 255
WHEN str1[0] >= 10 AND str1[0] <= 90
WHEN NOT str1[0] = 0

The DO SYSTEM action

The DO SYSTEM action executes the given shell command (via a system(3) call) the moment the condition is satisfied. RetractorDB logs the command’s exit code - a non-zero code is reported as an error in the log.

RULE alert1 \
ON results \
WHEN results[0] > 1000 \
DO SYSTEM 'curl -s http://monitoring/alert'

Any program available on PATH can be used in the command: shell scripts, Python programs, REST calls, sending notifications, etc.

A DO SYSTEM rule may be asked for only in the plan file the instance starts from - the author of that file is whoever runs the service. Both IPC channels refuse it: xqry --adhoc accepts only DO DUMP from a rule, and xqry --reset rejects the whole plan carrying DO SYSTEM, because that channel carries no authorship (→ xqry). An operator who deliberately hands the reset channel over sets service.unrestricted = true in the TOML configuration (→ xretractor).

The DO DUMP action

The DO DUMP action writes a window of stream samples to a binary file the moment the condition is satisfied. It lets you preserve the context of an event: data before it occurred and data after it.

RULE event ON results WHEN results[0] > 500 DO DUMP -10 TO 5

Range parameters:

Total number of dumped records: abs(step_forward - step_back). Example: DUMP -5 TO 5 → 10 records (5 historical + 5 subsequent). DUMP 0 TO 1 → 1 record (the current sample).

The step_back bound must be strictly less than step_forward. Equal or reversed bounds are rejected by the parser, including when attaching a rule ad hoc. The step_back value can be negative (history) or non-negative (delay). Both values being negative is not supported.

Dump files

Files are created in the directory configured by the STORAGE directive. Naming convention:

<stream>_<rule_name>_dump.tmp          # without RETENTION
<stream>_<rule_name>_dump_<n>.tmp      # with RETENTION (n = 0..N-1)

The file format is raw binary data matching the stream descriptor (no header). The xtrdb tool can be used to read the file.

A dump carries values only. Neither a .desc nor a .meta file accompanies it, so the schema has to be supplied from outside, and the NULL map and the transmission gaps have no representation in it whatsoever: a NULL field is written as the substitute value of its type, and a record the engine did not have is written as zeros. Absence and gaps are notions of the engine’s interior and do not leave it - the full contract, together with the routes that do preserve fidelity, is described in Alerting implementation.

The RETENTION option

The RETENTION <n> parameter limits the number of stored dumps - the oldest file is overwritten by the new one (a circular buffer). Without RETENTION, every trigger overwrites a single _dump.tmp file.

RULE event ON results WHEN results[0] > 500 DO DUMP -10 TO 5 RETENTION 20

The example above keeps the last 20 dumps in files results_event_dump_0.tmp … results_event_dump_19.tmp.

Multiple rules for a single stream

Any number of rules of different types can be attached to a single stream:

RULE high_alert \
ON measurements \
WHEN measurements[0] > 900 \
DO SYSTEM 'notify-send "Threshold exceeded"'

RULE low_alert \
ON measurements \
WHEN measurements[0] < 10 \
DO SYSTEM 'notify-send "Value too low"'

RULE anomaly_log \
ON measurements \
WHEN measurements[0] > 900 \
DO DUMP -20 TO 10 RETENTION 5

All rules for a given stream are evaluated on every new sample.

Mechanism Construction

By alerting we mean the process of processing current data and having the system react in real time when it recognizes a phenomenon that has occurred. For alerting to work, the system needs mechanisms supporting this process. In RetractorDB I developed an alerting model based on declaring rules tied to the observation of data streams. These rules contain mathematical operations allowing analysis of logical conditions and the triggering of external processes, or performing a data dump within a chosen time window.

NOTE: The functionality described here is covered by the tests: issue42_rule, described in the appendix Integration Tests.

The presentation of the RULE command’s syntax on page 24 already touches on this functionality. In this chapter I would like to explain in more detail how this solution works.

To build an example demonstrating how alerting works, let’s create the following query file - query.rql:

DECLARE a UINT STREAM core0, 1 TEXTFILE 'datafile1.txt'
SELECT str4[0] STREAM str4 FROM core0>1

RULE regulation1 \
ON str4 \
WHEN str4[0] = 20 or str4[0] = 23 \
DO SYSTEM 'echo "test"'

The file datafile1.txt contains numbers, as text, from 20 to 28.

$ seq 20 28 > datafile1.txt

The three commands above declare an ephemeral data source, one data-processing command that shifts it in time by one sample, and an alerting rule. Running the following command:

$ xretractor -c query.rql -d -u -p -i > out.dot &&
dot -Tpng out.dot -o out.png

Viewing the resulting out.png file, we will see something like this (Fig. 9):

The image shows the relationship between the processes responsible for artifacts, alerting, and ephemerides. It should equally be possible to attach the process responsible for alerting to a substrate.

Alerting objects are shown in blue and connected, via red undirected lines, to the objects they monitor.

More than one alerting object can be attached. Multiple RULE commands can be associated with a given data-stream-creating command.

Looking more closely, we see that the process responsible for alerting is triggered by a condition. The following command lets us inspect what’s actually happening there:

$ xretractor -c query.rql -d -u -p > out.dot &&
dot -Tpng out.dot -o out.png

The output file looks as follows (Fig. 10):

In its final form, this condition must evaluate to an expression representing true or false.

Logical Condition in RULE

The WHEN clause of the RULE command takes a logical expression, which is evaluated on every new record of the specified stream. If the expression evaluates to true, the process defined in the DO clause is triggered.

Comparison operators

Logical connectives

A bare STRING field is true when its value is nonempty. String comparisons and NOT over a string return INTEGER 1 or 0. AND and OR use the left operand’s type, or the right operand’s type if the left is NULL; a result based on a string is INTEGER. Thus WHEN NOT status[0] is true for an empty string, and a false string comparison does not trigger a rule through OR. NULL still follows the condition’s three-valued logic.

Expression structure

A condition is built from the fields of the stream schema specified in the ON clause. Fields are identified the same way as in SELECT - by the stream name with an index:

WHEN stream[index] operator value

Compound conditions are joined with connectives:

WHEN stream[0] > 10 AND stream[1] != 0
WHEN stream[0] = 5 OR stream[0] = 7
WHEN NOT stream[0] < 0

Examples

RULE high_alarm \
ON measurements \
WHEN measurements[0] > 100 OR measurements[0] < -100 \
DO DUMP -10 TO 10 RETENTION 50

RULE signaling \
ON status \
WHEN status[0] = 1 AND status[1] != 0 \
DO SYSTEM 'systemctl restart sensor-reader'

RULE one_time ON data WHEN NOT data[0] = 0 DO DUMP -5 TO 0

Field access

The condition refers to the fields of the stream specified in ON. The field index corresponds to its position in that stream’s schema - the same as in the SELECT clause. The condition reads the stream’s output record, so an index equal to or greater than its field count is a compilation error (see Index out of range). Aliasing works exactly as described in the chapter Aliasing.

If the stream in ON was produced by an interleave A#B, the condition must use the output stream name:

RULE valid ON result WHEN result[0] > 0 DO DUMP -1 TO 0

A reference to a named interleave component is ambiguous and causes compilation to fail:

RULE invalid ON result WHEN A[0] > 0 DO DUMP -1 TO 0

The same rule applies when # is hidden in a substrate generated for a compound FROM expression.

Alerting Example

In a terminal window, we start the xretractor process, running the query.rql file shown at the start of the chapter.

$ xretractor query.rql
test
test
test
…

In a second terminal window, I suggest running the command:

$ xqry -s str4
27
28
20
21
22
23
24
25
26
27

I suggest placing both windows side by side. We will see that the appearance of the values 20 and 23 triggers the server-side action that prints “test”. Keep in mind that any system command or invocation of any program can appear here, depending on what we put in the DO SYSTEM declaration.

Session recording (animation below):

Example 2: recording event context (DO DUMP)

The DO DUMP action lets you capture a window of samples surrounding an event - data before and after it occurred. This is useful when we want to preserve the context of an anomaly for later analysis.

We create a query.rql file:

STORAGE 'temp'

DECLARE a INTEGER STREAM core0, 1 TEXTFILE 'datafile1.txt'
SELECT str1[0] STREAM str1 FROM core0

RULE anomaly_log ON str1 WHEN str1[0] > 24 DO DUMP -3 TO 3

Input data - numbers from 20 to 28:

$ seq 20 28 > datafile1.txt

We run xretractor:

$ xretractor query.rql

When the value of stream str1 exceeds 24, the rule triggers a write of 6 records (3 historical + 3 subsequent) to the binary file temp/str1_anomaly_log_dump.tmp.

Reading the dump file

The dump file contains no .desc header - when opening it in xtrdb, the schema must be specified manually:

$ xtrdb
> storage temp
> open str1_anomaly_log_dump { INTEGER a }
> size
> list 6
> quit

The printed values are everything the file carries: a dump has no .meta file either, so NULL and a transmission gap have no representation in it, and a zero may be a genuine zero, a NULL field, or a record the engine did not have (→ Alerting implementation).

Example 3: rotating dumps (DO DUMP with RETENTION)

Without RETENTION, each successive trigger of the rule overwrites the same file. When events repeat, use RETENTION N to keep the last N dumps in separate files.

STORAGE 'temp'

DECLARE a INTEGER STREAM core0, 1 TEXTFILE 'datafile1.txt'
SELECT str1[0] STREAM str1 FROM core0

RULE anomaly_log ON str1 WHEN str1[0] > 24 DO DUMP -3 TO 3 RETENTION 5

Each trigger creates the next file (circular rotation):

temp/str1_anomaly_log_dump_0.tmp
temp/str1_anomaly_log_dump_1.tmp
temp/str1_anomaly_log_dump_2.tmp
temp/str1_anomaly_log_dump_3.tmp
temp/str1_anomaly_log_dump_4.tmp

Once capacity is exceeded (RETENTION 5), the oldest file is overwritten by the new one.

Example 4: multiple rules on a single stream

Any number of rules can be attached to a single stream. The example below combines both actions - a system notification and context recording:

STORAGE 'temp'

DECLARE a INTEGER STREAM core0, 1 TEXTFILE 'datafile1.txt'
SELECT str1[0] STREAM str1 FROM core0

RULE lower_threshold \
ON str1 \
WHEN str1[0] < 21 \
DO SYSTEM 'echo "ALARM: value below lower threshold" >> alarm.log'

RULE upper_threshold \
ON str1 \
WHEN str1[0] > 26 \
DO SYSTEM 'echo "ALARM: value above upper threshold" >> alarm.log'

RULE context_log ON str1 WHEN str1[0] > 26 DO DUMP -5 TO 5 RETENTION 10

The upper_threshold and context_log rules react to the same condition independently - crossing the upper threshold both writes a log entry and captures the data window at the same time. The lower_threshold rule handles the lower threshold separately.

All three rules are evaluated on every new sample of the str1 stream.

Configuration Directives

Four configuration directives are available:

• STORAGE
• SUBSTRAT
• ROTATION
• DEFAULT VOLATILE

STORAGE, SUBSTRAT, and ROTATION take a text argument in single quotes. DEFAULT VOLATILE takes no string. Example directives with arguments:

STORAGE 'temp_folder'
SUBSTRAT 'memory'
ROTATION 'rotation_counter.txt'

Fig. 11. Configuration directive syntax diagram

The railroad diagram in Fig. 11 was generated from the compiler_option and default_statement rules in the system’s ANTLR4 grammar (RQL.g4). The three upper branches (the compiler_option rule) have an identical structure: one of the keywords STORAGE, SUBSTRAT, or ROTATION (rounded green boxes), followed by a value enclosed in single quotes - arbitrary text (a directory path for STORAGE, a counter-file name for ROTATION), or the name of one of the predefined memory profiles (for SUBSTRAT). The bottom branch (the default_statement rule) is the keyword pair DEFAULT VOLATILE with no value.

The STORAGE directive selects the directory for output files. Without it, xretractor uses storage.dir from the TOML configuration, falling back to the process’s current directory only when that key is also unset. An explicit RQL directive takes precedence over configuration (see configuration file).

Substrates are queries and their effects that arise from the compiler decomposing system commands based on time-series algebra expressions. These are queries visible in the query execution plan but not specified directly in the .rql file. They arise from the implementation of the query-execution-plan construction process.

Without DEFAULT VOLATILE or explicit SUBSTRAT, such queries materialize data on disk in DEFAULT storage. Without retention their files grow without bound; the TOML key storage.default_retention can also limit substrate history. Keeping intermediate results on disk can be useful during software development, while SUBSTRAT 'memory' keeps only the history needed by the plan in a bounded RAM buffer.

The possible options for the SUBSTRAT command are: memory, default, direct, posix, posixshd, generic (case does not matter). Any other value is a compile error - including device and textsource, which are DECLARE source types, not storage profiles. A full description of each type - the C++ class, retention handling, and shadow support - can be found in the chapter Storage Types.

The last directive - Rotation - indicates an alternative shutdown mode for the system. By default, after compilation, all files produced by the system remain in whatever state the system left the recorded data. On the next invocation of the system command, all artifact and substrate files are deleted. Using the Rotation directive in an rql file containing query declarations makes the system create the file named in the directive’s parameter and store there a counter incremented on every system startup. Artifact and substrate files are renamed at the end of every system run - they get an .old extension plus a number derived from the increasing counter. This process is called artifact rotation.

DEFAULT VOLATILE

DEFAULT VOLATILE

This directive (the default_statement rule) selects default in-memory storage for both named SELECT results and compiler-generated substrates. It may appear once in the header, before DECLARE, SELECT, and RULE. Explicit SUBSTRAT takes precedence for substrates; PERSISTENT or explicit STORAGE on a SELECT overrides the default for its result. DECLARE sources remain unchanged. For examples and the complete rules, see VOLATILE and PERSISTENT.

System Architecture

The construction of the data-processing system is a strictly technical chapter. Here I present how the system was designed and built, and where and how its functionality is currently laid out.

RetractorDB was implemented in C++ under Linux. The source code goes through continuous integration and testing on GitHub, backed by CircleCI. The code is run and developed locally on the Linux WSL2 platform. I abandoned development and implementation of the system under Windows. In the early phase I kept that option open, and I may return to it in the future. However, maintaining too many development platforms significantly slows down rapid prototyping and system development. I still keep and maintain the system’s functionality on the Linux ARM platform. The code is compiled and tested on ARM and x86-64 architecture machines running in CircleCI’s resources. Raspberry Pi is one of the intended production platforms for RetractorDB, aimed at Edge IoT needs.

The build uses Conan 2, CMake, and Ninja. Tool preparation, source builds, and release-package installation are described in Installation Process. Linux remains the general deployment contract of this manual; the Apple port is solely for development and testing, with its limitations covered in a separate section of that appendix.

Overview of topics covered in this chapter

The chapter is built in layers - from the general view down to implementation detail.

Three commands are enough to run a complete pipeline:

xretractor -c query.rql          # verify the query file's correctness
xretractor query.rql             # start processing
xqry -s <stream>                 # read current data

A fourth element - xtrdb - comes into play for diagnostics and testing, not in a typical production workflow.

General Perspective

The system is built around 3 programs available as system commands. The first is the compiler and query-plan execution engine. The second is the client for accessing current data. The third is the program that provides access to binary dumps. Their names are, in order:

• xretractor
• xqry
• xtrdb

The xretractor program creates a process that executes one independent RetractorDB plan. Several named instances can run on a host, each with its own shared-memory area. The xqry program creates processes that communicate with a selected instance, while a shared bus enables discovery and routing. The xtrdb program is used to analyze data and metadata stored in the database’s files.

Below, Fig. 12 schematically shows RetractorDB’s architecture. All currently existing components are included. The areas enclosed in boxes with headers filled with system commands correspond to the existing components. The artifact-storage area is a symbolic representation of the filesystem.

In Fig. 12 we see the processes carried out by the xretractor, xtrdb, and xqry programs. The figure presents one execution instance; in a multi-server deployment, the xretractor block together with its IPC and clients is repeated for every name. Relationships between instances are described in Multiple Instances and the Bus.

An xretractor process communicates with xqry processes through its own named shared-memory area. In this memory, a data queue is created for every xqry subscription. Data is received by xqry processes on an ongoing basis. The job of the xqry processes is to forward the data on to other systems or processes. If an xqry process dies or is terminated, the relevant xretractor instance frees the resources dedicated to that client.

Besides directing data for delivery through shared memory, RetractorDB also writes data to the so-called artifact-storage area. Currently this is a directory to which the results of the stream-processing carried out according to RetractorDB’s query execution plans are continuously written.

⚠️ Warning

The “Database” shown in the figure is not a relational database. By “database” in the figure shown, we mean a set of binary or text files managed by RetractorDB. Data is pulled from devices and written to rotating or non-rotating binary or text files. Access to this data is carried out via the xtrdb tool, or, while the system is running, via the xqry process.

The file with RQL queries and directives is given as the first argument to the command that starts the system. That argument is optional: invoking xretractor without a query file starts it in idle mode - the process comes up, takes the service lock, opens the IPC channel and waits, building neither a plan nor a timeline. This lets a systemd unit come up together with the operating system, before the operator supplies a query set. The exception is --onlycompile mode, where a missing file remains an error - there is nothing to compile.

A query set can be supplied later in three ways. xqry -a adds one SELECT, DECLARE, or RULE to an active plan. xqry --reset file.rql atomically replaces the complete plan without restarting the process and can start the first epoch of an idle instance. Running xretractor file.rql while the service is live can instead validate the file, store it as the startup plan, and restart the systemd unit. The latter two routes accept a complete set including :STORAGE, :SUBSTRAT, and :ROTATION directives.

NOTE: Idle mode is covered by the service_idle test (variants using the --service flag and the XRETRACTOR_SERVICE environment variable).

Multiple Instances and the Bus

Several xretractor processes can run concurrently on one host. Each instance has its own name, lock, IPC area, plan, and clients. The shared xrdbbus bus registers live instances, lets xqry discover them, and ensures that two plans do not claim resources that cannot be shared safely.

In Fig. 13 every instance compiles its own plan and claims its own set of stream names in a bus slot; numbered nodes stand in for the names there, because all that matters is that they never repeat across instances. What is disjoint are the object names, not the memory area: on Linux the bus segment and the IPC objects of every instance live in the same /dev/shm and differ only by the instance-name suffix - for instance alpha these are the command queue RetractorQueryQueue.alpha, the response segment RetractorReply_v1.alpha, and the client subscription queue brcdbr.alpha.<pid>. The response segment has fixed slots and atomic states; it does not use a separate named map mutex. The storage directory is shared as well, with the files of the individual instances kept disjoint.

Service mode is the exception: exactly one instance may be marked as the service in the host’s default namespace. By default it receives the stable name service, so scripts can address --server service without first inspecting the bus.

Instance identity

An instance can be identified in three ways:

An explicit --name takes precedence over configuration. A name must match [a-z][a-z0-9_-]* and may contain at most 32 characters. --name and --autoname are mutually exclusive.

Omitting the name preserves the historical identity: IPC object names and the lock file have no suffix. This instance is also published on the bus, as (unnamed), and takes part in collision checks.

The RDB_NAMESPACE environment variable selects a separate bus segment and, when neither --name nor --autoname is given, becomes the default server name and xqry target. It is used primarily by parallel integration tests. Explicit --name, --autoname, and --server options still take precedence. The one-service limit is enforced separately in each bus namespace. Different RDB_NAMESPACE values with the same explicit server name do not separate IPC objects: their names follow the selected instance identity.

Before startup, an instance acquires its file lock in paths.lock_dir (the temporary directory by default) and an additional IPC identity lock at /tmp/xretractor_ipc.<command-queue-name>.lock. The latter location is fixed, independently of TMPDIR and paths.lock_dir. A held IPC identity blocks startup before artifacts are removed or IPC is created, even if the bus is unavailable. Changing the lock directory or bus namespace does not allow taking over a live server’s objects.

Private and shared resources

Named instances have separate Boost.Interprocess objects. The base names of the command queue and response segment receive the instance suffix; a subscriber queue also contains the client PID. Stopping an instance ends only its subscriptions and removes its IPC; it may also clean up resources abandoned by dead processes. Live instances remain protected.

New IPC objects created by the server receive an explicit 0600 mode, which restricts access to the server account without relying on the process umask. This applies to the command queue, subscription queues, response segment, and bus segment. Separate names keep the resources of cooperating instances apart, and locks coordinate their creation and cleanup.

The fix for #465 creates command queues, subscription queues, and the response segment through create_only. A name collision does not lead to adopting an existing object. When opening a queue or segment, the server and client require its owner to match their own effective UID (geteuid()) and its mode to be exactly 0600. The expected UID comes from the process credentials, not from the metadata of the object being opened. Before mapping, the checks also cover object type, a single link, agreement between the name and the opened object, and directory protection against entry substitution by another account.

At startup or restart, the server may remove leftovers owned by its own account after acquiring the IPC identity lock; older, broader permissions on such an object do not prevent cleanup. Resubscription removes the previous queue belonging to that account and creates a new one with the requested capacity. Cleanup refuses to remove an object owned by a different UID, including when performed by root. Abandoned locks belonging to other accounts are skipped, and identity and presence locks continue to protect live instances. The abandoned-resource sweeper does not enumerate all subscription queues left after SIGKILL.

A refusal is logged at ERROR level, including in Release, with the object name, reason, and owner UID when it can be determined. A foreign command queue or response segment refuses startup; a foreign subscription queue refuses that subscription. The bus may open an existing segment only after the same verification, and a rejected segment remains untouched. Its unavailability retains the single-server fallback described below.

⚠️ Warning

xqry must run with the same effective UID as the server. This also applies to administrators: running the client as root alone does not allow it to open IPC owned by another service account. For a service running as retractor, use, for example, sudo -u retractor xqry --server service --dir. Sharing the bus requires the same UID; an instance name or RDB_NAMESPACE does not replace owner verification. Allowing SYSTEM rules in a replacement plan still depends on service.unrestricted (see xqry).

The bus is shared by the host or RDB_NAMESPACE. Every live server publishes its name, PID, operating modes, plan file, and stream names. When the process entry is readable, a slot remains live if its PID and nonzero start time match; a zombie process does not retain resources. On Linux the engine reads /proc/<pid>/task/<pid>/stat, while on macOS it uses the platform adapter.

An unreadable process entry means the engine cannot decide, rather than confirming that the owner is dead. On Linux a failed read confirms absence only when kill(pid, 0) returns ESRCH; success or EPERM leaves the result uncertain. bus::isProcessAlive() then keeps the slot and its claims, including when it cannot compare start times. This protects an owner hidden by hidepid or ProtectProc, but may retain stale claims after PID reuse. Lack of access to an entry alone therefore does not authorize releasing resources. The rule is checked by ut_bus::BusFixture.UnreadableOwnerKeepsSlot.

The current layout uses the xrdbbus_v7 segment, or xrdbbus_v7_<RDB_NAMESPACE> when RDB_NAMESPACE is set. Each namespace has its own registry and collision checks. Segment users hold a presence lock through flock; the last one leaving can remove the unused segment. Layout versions have separate registries: concurrently running binaries using v6 and v7 does not provide collision checks between their streams and storage paths. Stop older instances before upgrading.

Shared presence-lock acquisition retries nonblocking flock calls for up to 500 ms. A transient exclusive holder may release its lock within that period; if it still holds it, the bus remains unavailable instead of blocking attachment indefinitely. This deadline applies to waiting for flock, not to the entire file-opening procedure.

Before starting or replacing a plan, the bus checks that the following do not overlap:

• all stream names, including compiler-generated and ad hoc streams;
• normalized paths of storage files being written;
• the counter file of the :ROTATION directive.

Resources are claimed before old artifacts are removed and before IPC is created. A losing instance therefore cannot delete data belonging to a live owner. The rejection message identifies the conflicting resource, instance name, and PID.

For xqry --reset, the new plan’s resources are reserved first. Only after the new epoch has been built successfully does that reservation atomically replace the active set. A parse error, compilation error, limit error, or collision leaves the current plan and its claims unchanged.

An unrecoverable bus-mutex error, ENOTRECOVERABLE, is reported at ERROR level, including in Release, once per Bus object. The message identifies the /dev/shm segment to remove after all instances mapping it have stopped. Removing a segment still used by a live instance can split the resource registry. Startup and ad hoc import retain the emergency mode described below; plan replacement is rejected when an attached bus has an unusable mutex.

⚠️ Warning

An unavailable or corrupted bus does not stop an individual server if it can acquire its instance and IPC identity locks. Startup is allowed with a warning, but global stream-name and storage-path protection is then not enforced. The IPC identity lock still applies. This is an emergency mode, not a valid multi-server configuration.

Routing xqry commands

xqry resolves its target from a single snapshot of the bus in the current RDB_NAMESPACE, without probing servers in turn or waiting for their timeouts. The combined --bus listing does not expand the routing scope of other commands.

An ad hoc query cannot combine sources from different instances. RetractorDB does not transfer streams between servers; the plans remain independent execution graphs.

Inspecting the bus

xqry --bus does not contact any server. Without setting RDB_NAMESPACE, it discovers every bus of the current version that is accessible to the current account and has live instances. Each bus gets a separate NAMESPACE: section with instance names, PIDs, modes, query files, and streams; (default) denotes the bus without a namespace. The --yaml modifier produces one apiVersion: xqry/v1 document with a servers list. Every entry has a namespace field: null for the default bus or a quoted namespace name. With no live instances, table output is empty and YAML contains servers: [].

The MODE column can contain several letters:

Example session:

xretractor alpha.rql --name alpha --noanykey &
xretractor beta.rql --name beta --noanykey &

xqry --bus
xqry --select temperature         # routed by stream owner
xqry --server alpha --dir         # explicit instance-wide command
xqry --server beta --kill         # stops only the beta instance

Data and Control Flow

Data and control in RetractorDB give rise to several potential ways of using the system’s components. Fig. 14 schematically shows the flow of data between RetractorDB’s processes, Linux system processes, and the source data and results produced by each process.

The thickest lines represent the flow that is always present when regular time series are processed. After receiving an .rql file, xretractor compiles it, builds the query-plan tree, begins processing incoming data, and creates binary files containing artifacts. Without a file it can start idle and wait for a complete plan delivered by xqry --reset.

NOTE: The functionality described here is covered by the test: consistency, described in the appendix Integration Tests.

To control the xretractor process once it has started, we use the xqry process. Through it, we can stop the xretractor process, retrieve statistics, or request access to current data.

The remaining arrows represent data flows that depend on the specific process being carried out with RetractorDB. Dashed arrows are typically intended for diagnostic purposes.

Each process on the diagram is additionally labeled with the number of continuous processes of that kind maintained in the system. The historical label “1” next to xretractor describes the one plan instance shown in the figure, not the current host-wide limit. Named instances can run concurrently; exactly one may act as the service in the default host namespace. The xrdbbus bus enforces separation of their resources. The xtrdb program does not maintain a continuous process: it reads data, returns a result, and exits, or runs interactively. The xqry process is labeled “N” because several clients can connect to each xretractor instance.

Stopping xretractor

The xretractor process handles system signals and shuts down in a controlled manner upon receiving:

All three signals produce the same effect: a graceful shutdown - the processing loop finishes the current cycle and stops. A signal that finds the loop waiting for the deadline of the next slot ends it immediately, and the slot whose deadline has not yet come is no longer computed (see Slot schedule). This allows xretractor, running as a service, to be shut down safely without risking corruption of artifact files.

Stopping via xqry

Besides system signals, xretractor can be stopped programmatically - using the command:

xqry --server name --kill

How the shutdown proceeds step by step

1. xqry sends a “kill” request

The xqry process resolves an instance from --server or from the bus, builds an IPC message, and places it on that instance’s command queue. The base name RetractorQueryQueue receives the named-instance suffix. The message contains the xqry process’s identifier (PID) and the kill command.

2. xretractor receives the command and sets the stop flag

The selected instance’s IpcServer communication thread continuously listens on its queue. After receiving a kill message, executorsm::commandProcessor sets the atomic iLoopLimitCnt counter to stop_now and wakes the execution loop. The same mechanism is used by the system-signal handler - regardless of the source, the effect is identical for that one instance.

3. The main processing loop detects the flag and finishes the current cycle

The main loop checks iLoopLimitCnt on every iteration. When it detects the value stop_now, it finishes the current cycle and exits the loop - without interrupting mid-computation. This ensures the integrity of the artifacts being written.

4. xretractor notifies all connected clients (OOB broadcast)

After exiting the loop, xretractor calls IpcServer::broadcastOutOfBusiness(). The IPC object walks the subscription registry, where the show command stored each client’s PID and stream name. It sends every registered client a special OUT_OF_BUSSINESS message on its dedicated queue.

5. Every xqry client receives the termination signal and exits

Every xqry subscription has its own queue containing the server name and client PID. Upon receiving the OUT_OF_BUSSINESS message, xqry sets its internal done flag and shuts down in a controlled manner - regardless of how much data it had received up to that point.

6. IPC resource cleanup

Finally, xretractor removes its response segment, command queue, mutex, and client queues, and releases its bus slot and locks. The owner removes lock files before releasing their locks. Additional cleanup at exit removes accessible resources abandoned by dead instances; live processes remain untouched. The last user of a bus segment can remove it after acquiring the exclusive presence lock.

After SIGKILL, exit handlers do not run and resources may remain. xretractor --cleanup removes recognized leftovers without starting a plan. Its scope, limitations, and counters are described in the xretractor options. It does not remove client response queues or older bus-layout segments.

Fatal errors and emergency cleanup

A fatal error during startup or in the communication thread follows the same final resource ownership policy but does not attempt to continue the processing cycle. The spdlog registry is flushed rather than destroyed before atexit handlers run. If the error originated in the communication thread itself, cleanup detaches that thread instead of attempting to join it from itself. It then removes IPC queues and shared memory and releases the service lock last.

The process exits with status 1. A later start therefore finds neither orphaned IPC nor a stale service lock, and the primary failure is not masked by a secondary SIGSEGV or SIGABRT during shutdown.

NOTE: fatal_exit_path covers both startup failure and failure reported by the communication thread.

What happens with multiple xqry processes

RetractorDB is designed to work with multiple parallel clients. If, say, three xqry processes are running simultaneously, subscribed to different streams, and one of them calls xqry --kill:

• the selected xretractor processes the kill request once, regardless of which client sent it,
• IpcServer::broadcastOutOfBusiness() sends the OUT_OF_BUSSINESS message to all clients registered with that instance,
• each of the three xqry processes receives the termination signal and exits on its own,
• clients that hadn’t subscribed to any stream (e.g. xqry invoked only with --dir or --hello) are not entered in the map and don’t need to be notified - these commands exit immediately after providing their response.

Clients connected to other named instances do not receive the message and continue running.

It’s worth noting that xqry also detects server inactivity: if no data arrives for 10 seconds, the client shuts itself down with a warning in the log. This is a safeguard in case xretractor crashes suddenly without being able to send the OOB message.

Artifacts, Substrates, Ephemerides

Given that the system is designed for continuous operation, and that, theoretically, the results obtained without a data-retention process would fill up any storage medium, we introduce additional definitions related to the nature of the data being processed.

In presenting the description of Fig. 14, artifacts were mentioned. This is one of the terms that needs explaining.

✅ Note

Definition (Artifact): By artifacts we mean data processed in the system in the form of streams that are ultimately materialized as a durable result and effect of processing other data.

Continuous time series can be read from devices, then processed - reduced or resized in time and in dimension. But as a rule, certain data should be saved. Whether that data is later subject to retention is a secondary matter. Data that constitutes the result and expected output of the system, we call artifacts. Something we expect and materialize for the end user’s needs.

✅ Note

Definition (Substrate): Substrates are intermediate objects. As a result of processing time series, data streams may arise that are ephemeral - needed only for and during processing.

Their size can be significant, considering how far back we go, for example when dumping historical monitoring data. However, their existence is irrelevant with respect to the system’s desired output. We call such data streams substrates. They arise as a result of the system’s operation; as a rule they do not appear explicitly in queries - but they result from the process of processing time series, and yet their results are necessary to accomplish the task.

✅ Note

Definition (Ephemeris): Ephemerides are objects on the basis of which we create source data streams - data that cannot be stored. As a rule, these are ephemeral, transient data.

For example, the system reads random numbers at a given rate, and it is precisely this data source that provides ephemeral data. It cannot be returned; storing it is, as a rule, pointless - it must be passed on for further processing in order to produce artifacts or substrates, and then discarded and replaced with new, current data.

Data Storage Format

The system processes time series in three forms: artifacts, ephemerides, and substrates. Each type has a different purpose and a different storage strategy.

Substrates and Artifacts are formally no different in the system. The only difference is that substrates were generated based on data-stream algebra equations and were not written directly in the sequence of commands given to the compiler. If we declare an Artifact stream that covers what would otherwise be a substrate, the substrate is eliminated. Ephemerides are streams created via the Declare command - they contain values that exist only briefly.

Storage accessor types

NOTE: The functionality described here is covered by the test: txtsrc, described in the appendix Integration Tests.

The TYPE field in the descriptor (or the STORAGE directive in RQL) selects the FileInterface implementation:

The artifact and substrate file set

Artifacts and substrates written to disk can be associated with up to five files:

%% pdf-width: 70%
graph TD
  D[".desc: descriptor (record schema)"]
  B["Binary data file (N×R-byte records)"]
  M[".meta: metadata (null and gap index)"]
  S[".shadow: data shadow file (record modifications)"]
  MS[".meta.shadow: index shadow (null overrides)"]

    D -->|"describes structure"| B
    B -->|"companion index"| M
    B -->|"optional overrides"| S
    S -.->|"consistency pair"| MS
    M -->|"pattern overrides"| MS

    style S fill:#f9c,color:#000
    style MS fill:#f9c,color:#000
    style M fill:#cdf,color:#000

Fig. 15. The artifact file set and their relationships

The diagram in Fig. 15 shows the static relationship between artifact files: .desc defines the record structure, .meta indexes nulls and gaps, .shadow stores optional record overrides, and .meta.shadow the null-pattern overrides that correspond to them. The two shadow files always go together.

The shadow files and the metadata file are optional. With continuous, gap-free, unmodified data arrival, the binary data file and the descriptor alone are enough.

Ephemerides have no data file of their own - their source is an external object (a text file, a device) that the system neither creates nor deletes. A .desc descriptor describing the read schema is created for them, however. No .meta index appears: declared sources get an inert metadata-index variant that works purely in memory.

The dump file produced by a DO DUMP rule does not belong to this set, although its records have the same layout. No .desc, no .meta and no header accompany it, so it carries values only: the information about NULL and about a transmission gap stays inside the engine and never reaches the dump. The dump contract is described in Alerting implementation.

Chapters

• Artifact Files - descriptor, binary data, metadata, shadow file, and the relationships between them
• File Rotation Mechanism - the ROTATION directive, file lifecycle, session examples
• Inspection Tool xtrdb -s - the storage map, report sections, examples
• Summary - rationale for the chosen structure, comparison of approaches

Files

This chapter describes the five files that make up the complete file set of an artifact or substrate: the schema descriptor (.desc), the main binary data file, the metadata index (.meta), the data shadow file (.shadow), and the index shadow file (.meta.shadow). For each file, the binary format, field semantics, and read/write rules are presented. The chapter also covers the metaData class - the RLE compression mechanism, transmission-gap handling, the update interface, and persistence across restarts. The final section shows the relationships between all the files at the level of append, update, and read operations.

The scope of this chapter does not include the file-rotation mechanism between sessions (→ Rotation) or the xtrdb -s inspection tool (→ Inspection Tool).

File opens and symbolic links

Storage files - data, .shadow, .meta, .meta.shadow, and .desc - are opened with O_NOFOLLOW: a symbolic link at the final filename causes the open to be refused instead of writing to or truncating its target. For GENERIC, refusal may occur only at the first write. An unavailable metadata index may disable its persistence without stopping the stream; refusal to open a link therefore does not always mean rejection of the entire plan.

The exception is the main data file named by an explicit REF supplied by the caller (a plan or a schema in xtrdb). That operator choice can authorize a final data-file link. A REF read only from an existing .desc does not grant this permission, nor does allowing a directory through storage.ref_dirs. The exception covers neither auxiliary files nor retention-segment names generated by the engine.

O_NOFOLLOW checks only the last path component. The storage directory and its ancestors may still be links; replacement of a parent directory during path resolution remains outside this guarantee. ut_rdb checks refusals and permitted controls. DUMP files have a separate policy that removes the final entry and exclusively creates a new file - see Alerting Implementation.

The descriptor file (.desc)

The .desc file describes the record structure. It is parsed by an ANTLR4 grammar (DESC.g4) and can contain data fields, storage-type meta-information, and a retention policy.

Syntax

{ <statement>* }

Each statement is one of the following:

BYTE     name [N]          # array of N bytes (default N=1)
INTEGER  name [N]          # 32-bit signed integers
UINT     name [N]          # 32-bit unsigned
FLOAT    name [N]          # 32-bit floating point (IEEE 754)
DOUBLE   name [N]          # 64-bit floating point
RATIONAL name [N]          # pair of int32: numerator and denominator
STRING   name [size]       # fixed-length string
REF      "path/file"       # data file (relative paths use the process's working directory)
TYPE     identifier        # storage type (DEFAULT, MEMORY, POSIXSHD, …)
RETENTION capacity segment # cyclic on-disk retention
RETMEMORY capacity         # cyclic in-memory retention

Example .desc files

A default artifact - two numeric fields, DEFAULT storage (data file + shadow file):

{
  INTEGER  ts
  FLOAT    value
  TYPE     DEFAULT
}

A SELECT result or substrate in RAM - MEMORY storage with a one-record ring (ephemeris sources declared with DECLARE have type BINFILE, TEXTSOURCE, or DEVICE):

{
  DOUBLE   x
  DOUBLE   y
  TYPE     MEMORY
  RETMEMORY 1
}

A substrate with retention - up to 1000 records on disk (10 segments of 100):

{
  INTEGER  ts
  FLOAT    a
  FLOAT    b
  TYPE     DEFAULT
  RETENTION 100 10
}

A binary source declaration (DECLARE in RQL generates this schema):

{
  INTEGER  a
  FLOAT    b
  TYPE     BINFILE
  REF      "sensor/data.bin"
}

Field type sizes

For array fields name[N], the total size = type_size × N. The TYPE, REF, RETENTION, and RETMEMORY fields take no space in the record - they are descriptor metadata.

Record size R = the sum of the sizes of all data fields.

The RATIONAL field layout

A RATIONAL field stores a rational number as a pair of signed integers, written into the record directly, with no header and no type tag:

offset +0   int32   numerator
offset +4   int32   denominator

The byte order is the machine’s native one - little-endian on x86-64 and ARM64, the same as for INTEGER and UINT fields. The field occupies 8 bytes; in an array field RATIONAL name[N] the pairs follow one another, 8 × N bytes in total.

The value is always stored in lowest terms, and the denominator is always positive - the sign is carried by the numerator alone. This follows from boost::rational arithmetic, which normalizes the result on every assignment; it is not a writing convention. In particular:

• zero is stored as 0/1, never as 0/0 or 0/5;
• a whole number is stored as n/1 - a RATIONAL field with denominator 1 is exactly an integer, with no rounding involved (the slot-divisibility test in the query tree traversal algorithm relies on the same invariant);
• the denominator is never zero - no write path in the system produces such a pair.

The invariant describes writing, however, not every file that can be handed to the engine. Since 23 September 2026 the read path checks it at the bytes-to-value boundary: a pair whose denominator is less than or equal to zero yields NULL, not a rational number. This covers a zeroed record (0/0), a denominator equal to INT_MIN, and the pair INT_MIN/-1 - exactly the bytes on which the previous version terminated the process with SIGFPE. A pair with a positive denominator also passes through normalization, so a reducible representation comes back reduced (2/4 as 1/2). The pair 1/-2 yields NULL because its denominator is negative. For a file written by the system this changes nothing - it contains no such pairs.

RATIONAL fields are produced by the MIN, MAX, AVG, and SUMC reducers when the input value has type BYTE, INTEGER, UINT, or RATIONAL. This covers current-record reducers in FROM, the deprecated .min/.max/.avg/.sumc notation, and record-history AGG(expression : W) in the SELECT list. FLOAT and DOUBLE inputs preserve their types (→ Aggregate Operators). A reducer over integer or rational input is, in practice, the main source of RATIONAL in an artifact.

A measured example

A plan computing the mean over a window of three samples:

DECLARE v INTEGER STREAM src, 1 TEXTFILE 'data.txt'

SELECT * STREAM ravg FROM AVG(src@(1,3))

fed with -3, -3, -2, 7, 7, 7, … yields the descriptor { RATIONAL avg } and a data file whose first record is eight bytes long:

f8 ff ff ff   03 00 00 00
└ numerator ┘ └ denominator ┘
   -8              3            →  -8/3

The fourth record is 07 00 00 00 01 00 00 00, that is 7/1 - the mean of three sevens, stored as a rational number with denominator 1 rather than as an INTEGER.

Reading the value without decoding bytes

The pair layout only matters when reading the binary file directly. That a field is of type RATIONAL and occupies 8 bytes is reported by xtrdb -s name from the descriptor (→ Inspection Tool) - the tool shows structure, not values. The value itself is obtained by passing the field through a conversion in the query; three functions offer three different trade-offs:

For export to text-based systems to_string is the right choice, because it preserves the value exactly; to_integer is convenient but drops the fractional part, and does so differently from Python’s flooring // - the rounding rule is documented alongside the expression functions.

The TYPE field and storage strategy

The TYPE field in the descriptor directly determines which accessor (FileInterface) is used by storage::initializeAccessor(). The absence of a TYPE field is equivalent to DEFAULT. The value is case-insensitive (MEMORY = memory).

The binary data file

The data file is a sequence of fixed-length records, written one after another with no header at all. The size of a single record R is determined by the descriptor as the sum of all field sizes in bytes.

Every record contains the packed field values in the order defined by the descriptor:

The append operation (adding a new record) writes data to the end of the file. The update operation (modifying an existing record) - if a shadow file exists - goes into the shadow file, not the main file.

Example

DECLARE a INTEGER, b FLOAT STREAM src, 0.1 BINFILE 'data.dat'
SELECT * STREAM str1 FROM src

Record size: INTEGER (4 B) + FLOAT (4 B) = 8 bytes. After 50 records have been written, the output file str1 occupies 50 x 8 = 400 bytes. With a 0.1 s interval, this represents 5 seconds of data. data.dat is an existing read-only source; DECLARE does not grow it.

Reading a record that does not exist

A request for an index past the last record - or a read from an empty store - is not a successful read. Since 23 September 2026 storage::read() and storage::revRead() return a separate NoSuchRecord status, zero the destination buffer, and set the entire null pattern to true: a record that does not exist is an undetermined value, not a zero record. This is the same convention dataModel::fetchBack() and fetchForward() apply to a read beyond the accumulated history.

This matters for the result, not only for diagnostics. Previously that branch returned success and marked the zeroed record explicitly as not null, so NULL absorption did not kick in and the MIN, MAX, SUMC, and AVG reducers folded a fabricated zero into the result instead of skipping the missing record (→ Aggregate Operators). The xtrdb tool distinguishes an initial out-of-range refusal (record out of range, with no payload change) from a failed read of an allowed index (error and, for a list, fetch error). See xtrdb for details.

The null pattern lives in the payload and in the .meta index, that is, inside the engine. A DO DUMP dump does not carry it - a non-existent record is written there as zeros indistinguishable from data (→ Alerting implementation).

The metadata file (.meta)

The .meta file is an index of null values and transmission gaps. It stores information about which record fields have null values, and where gaps occurred - without duplicating the data itself.

File format

RLE entry format

Each entry describes a run of consecutive records with an identical null pattern:

The null pattern belongs to a particular record: a bit set for one field does not change the other fields or other records described by the same descriptor. A numeric array field T[N] is one descriptor entry and has one shared null bit for all N elements; a set bit means the entire field is null. When N scalar fields are converted into one T[N] field, a null in any of them sets that shared bit.

RLE compression

Consecutive records with the same null pattern are merged into a single entry by incrementing recordCount. A new entry is only created once the pattern changes.

10 records, 2 fields, no nulls:

Field 1 becomes null starting at record 5:

Transmission gap after record 3:

The transmission-gap marker

A transmission gap (e.g. a system shutdown, a lost signal) is recorded as an entry with isGap=true and all null bits set to true. The count parameter stores the length of the gap in units of the stream’s interval. The binary data file itself contains no additional records for the gap - that information lives solely in the .meta file.

NOTE: The functionality described here is covered by the tests: issue113_meta_internal, issue113_meta_autocreate, described in the appendix Integration Tests.

The metaData class

The .meta file is managed by the rdb::metaData class. It acts as a coordinator: it keeps the RLE policy itself (lazy overwrite of the last entry, record numbering) and delegates the specialized parts to separate units:

metaData itself encapsulates three areas of responsibility:

1. In-memory RLE aggregation - it buffers the current segment (the most recent run of records with an identical null pattern) in the currentEntry_ field, without writing it to the file on every record.
2. Data persistence - only completed segments (when the pattern changes, or on an explicit call to flushCurrentEntry()) are written to the file as committed entries.
3. A query index - it exposes an interface for querying the null pattern of any record and for detecting transmission gaps.

The class holds two states:

Object lifecycle

The state diagram (Fig. 16) shows the transitions between phases of a metaData object:

%% pdf-width: 30%
stateDiagram-v2
    [*] --> Construction : constructor
    Construction --> Active : loadIndex()
    Active --> Active : onRecordAppended()
    Active --> Active : onRecordModified()
    Active --> Active : onTransmissionGap()
    Active --> Active : flushCurrentEntry()
    Active --> [*] : destructor (auto flush)

Fig. 16. Lifecycle of a metaData object

Constructor (metaData(descriptor, path)):

• Initializes an empty currentEntry_ based on the number of fields in the descriptor.
• Calls loadIndex() - if the file exists, it loads all committed segments, determines committedRecordCount_, and moves the last non-gap segment back into currentEntry_ (allowing the RLE run to continue after a restart).
• If the file does not exist, it creates it and writes the header (8 reserved bytes, zeros).

The destructor automatically calls flushCurrentEntry(), guaranteeing that the current buffer reaches disk even when the program exits normally.

The update interface

The class distinguishes three scenarios for changing metadata state:

onRecordAppended(nullBitset)

Called by storage after every new record is appended to the data file.

pattern identical to currentEntry_?
├─ YES → increment currentEntry_.recordCount (RLE accumulation, no I/O)
└─ NO  → flushCurrentEntry() (previous segment to disk)
          set currentEntry_ = {nullBitset, count=1}

I/O only happens when the pattern changes - for a run of identical records, the cost is a single in-memory counter increment.

onRecordModified(index, nullBitset)

Called by storage when updating an existing record. Behavior depends on the operating mode:

Normal mode (no data shadow file): it locates the record within the RLE segments and splits the segment into up to three parts: before the modified record, the record itself, and after it.

is the record in currentEntry_ (memory)?
├─ YES → splitSegment() in memory, new fragments appended to the file
└─ NO  → read the file, splitSegment(), rewrite the file (rewriteFile)

Example of splitting a segment [allNull × 5] when modifying record 2:

Before: [allNull × 5]
After:  [allNull × 2] [allPresent × 1] [allNull × 2]

Shadow variant (storageShadow, injected in place of the base metaData for stores that maintain a .shadow file): instead of modifying the main index, it appends a single null-pattern override to the .meta.shadow file. The main .meta index remains untouched and consistent with the main data file.

index object is a storageShadow?
├─ YES → metaShadow::appendOverride(index, nullBitset) → entry in .meta.shadow
└─ NO  → modify the main index → splitSegment()

onTransmissionGap(duration)

Records a transmission gap of the given length (in units of the stream’s interval). It first commits the current segment (flushCurrentEntry()), then appends an entry with isGap=true to the file (Fig. 17).

sequenceDiagram
    participant S as storage
    participant M as metaData
    participant F as .meta file

    S->>M: onTransmissionGap(5)
    M->>F: flushCurrentEntry() - write [normal, count=N]
    M->>F: appendEntry(isGap=true, count=5)
    Note over F: the file now contains a gap marker

Fig. 17. Gap-recording sequence - onTransmissionGap

Safety mechanism: flushCurrentEntry() and overwriting (tail_.dirty)

The storage class calls flushCurrentEntry() after a successful physical record append, following the metadata update by onRecordAppended(). A record absorbed by the transmission-gap mechanism and a refused append to a read-only source return from write() earlier. Overwriting an existing record calls onRecordModified(), which updates either the main index or its shadow, depending on the store type.

flushCurrentEntry() writes the current index entry to the file, reducing the amount of metadata held only in process memory. This write does not include fsync after every record or a transactional commit of the data together with the index, so it does not by itself guarantee consistency after a process crash or power loss. The ut_metaData_usage test checks an append followed by an explicit flush; it does not simulate a process crash.

A naive implementation would append a new entry to the file on every flush - causing file growth proportional to the number of records, even without any change in the null pattern.

The solution: a lazy overwrite mechanism flagged by tail_.dirty.

flushCurrentEntry() → write [pattern, count=2] to disk
onRecordAppended(the same pattern):
    currentEntry_.count = 2 (restored from disk)
    tail_.markDirty()        ← the next flush will overwrite, not append
    currentEntry_.count++    → count = 3
flushCurrentEntry() → seek to the last entry, overwrite [pattern, count=3]
    (file size unchanged)

The sequence diagram for storage’s typical pattern (append + flush after every record) is shown in Fig. 18:

%% pdf-height: 55%
sequenceDiagram
    participant S as storage
    participant M as metaData
    participant F as .meta file

    S->>M: onRecordAppended([F,F])
    S->>M: flushCurrentEntry()
    M->>F: appendEntry([F,F], count=1)

    S->>M: onRecordAppended([F,F])
    S->>M: flushCurrentEntry()
    Note over M: tail_.dirty=true, overwrite last entry
    M->>F: overwrite last entry: [F,F] count=2

    S->>M: onRecordAppended([F,F])
    S->>M: flushCurrentEntry()
    M->>F: overwrite last entry: [F,F] count=3

    S->>M: onRecordAppended([T,F])
    Note over M: different pattern → new entry
    S->>M: flushCurrentEntry()
    M->>F: appendEntry([T,F], count=1)

Fig. 18. The lazy-overwrite mechanism - overwriting the last .meta entry

Thanks to this, the .meta file grows only when the null pattern changes - not on every record. With continuous, uniform data arrival, the file has a constant size regardless of the number of records.

Persistence and state recovery

After the process restarts, a new metaData object loads the file via loadIndex() (sequence shown in Fig. 19):

1. It skips the header - 8 reserved bytes; nothing in them is interpreted.
2. It loads all committed entries from the file.
3. If the last entry is not a gap, it moves it back into currentEntry_ and removes it from the file (allowing the RLE run to continue after a restart without duplication).
4. It computes committedRecordCount_ as the sum of recordCount over all non-gap entries remaining in the file.

sequenceDiagram
    participant Proc1 as First session
    participant F as .meta file
    participant Proc2 as Second session

    Proc1->>F: writes segments [A×500][B×200]
    Note over Proc1: destructor → flushCurrentEntry()
    Proc1->>F: last segment committed

    Proc2->>F: loadIndex()
    F-->>Proc2: reads all segments
    Note over Proc2: last segment moved into currentEntry_
    Note over Proc2: ready to continue the RLE run
    Proc2->>Proc2: totalRecords() = 700

Fig. 19. Persistence and state recovery after a restart

Query interface

The index-shadow interface

Methods of the storageShadow class - the index variant injected by makeMetaIndex() for stores that maintain a data shadow file. The base metaData does not have them, and there is no mode switch: the presence of a shadow is decided by the choice of class at store initialization.

Usage example - a typical production scenario

storage.write(rec0)           → onRecordAppended([F,F,F]) + flushCurrentEntry()
storage.write(rec1)           → onRecordAppended([F,F,F]) + flushCurrentEntry()
storage.write(rec2_val_null)  → onRecordAppended([T,F,F]) + flushCurrentEntry()
storage.write(rec3)           → onRecordAppended([F,F,F]) + flushCurrentEntry()

The .meta file after the above operations (4 flushes, 2 segments):
  [isGap=F, count=2, bitset=[F,F,F]]   ← entry 0
  [isGap=F, count=1, bitset=[T,F,F]]   ← entry 1  (rec2)
  [isGap=F, count=1, bitset=[F,F,F]]   ← entry 2  (rec3, currently in memory)

getNullBitset(2) → [T,F,F]   (field 0 of record 2 is null)
isGapBefore(2)  → false
totalRecords()  → 4

The shadow file (.shadow)

The shadow file allows modification of recorded records without destroying the original data. Deleting the .shadow file restores the original state of the data.

Entry format

Every modification appends a new entry to the end of the shadow file. With multiple modifications of the same record, the file may contain multiple entries for the same position - the most recent one is the current one.

Read priority

Read priority is the rule for deciding which source the system should return a record’s value from, when the same index could appear in both the main file and the shadow file at once. In RetractorDB, priority is defined deterministically: .shadow is checked first (from the end, to pick the most recent modification), and only if there’s no entry is a read performed from the main file. This concept concerns the consistency and read versioning of data after modifications, not the physical record-storage format of the binary file itself.

%% pdf-width: 100%
flowchart LR
    Q["Read record at position P"]
    Q --> SH{"Look up P in .shadow\n(from the end)"}
    SH -->|found| RET1["Return data from .shadow\n(the most recent modification)"]
    SH -->|not found| MAIN["Read from the main file\npread(fd, pos=P×R)"]
    MAIN --> RET2["Return the original data"]

Fig. 20. Record read priority relative to the shadow file

Fig. 20 shows the record-read logic: the system first checks for an entry in .shadow, and only reads the record from the main file if there is none.

Merging (merge)

The merge() operation merges changes from the shadow file into the main file and clears the shadow file. After merging, the original data is irrecoverably overwritten.

sequenceDiagram
    participant App
    participant Shadow as .shadow
    participant Main as main file

    App->>Shadow: read all entries (i, data_i)
    loop for every entry
        Shadow-->>App: (position=i, data=data_i)
        App->>Main: pwrite(data_i, offset=i×R)
    end
    App->>Shadow: ftruncate(0) - clear the shadow file

Fig. 21. Merging the shadow file into the main file

Fig. 21 shows the flow of merge(): successive (position, data) entries from .shadow are written to the main file, and once finished, the shadow file is cleared.

Example: modifying a record

# Stream str1: 2 INTEGER fields (4B each), recordSize = 8B
# Record 2 (original): [100, 200]
# Modification: field 0 → 999

# The .shadow file after the modification:
# offset 0: [position=2 (8B)][999, 200 (8B)]

Reading record 2 will return [999, 200]. Reading records 0 and 1 will return data from the main file (they have no entries in the shadow file).

The index shadow file (.meta.shadow)

The .meta.shadow file is the counterpart of .shadow at the null-index level. It records overrides of null patterns for individual records without modifying the main .meta file, keeping the pairing consistent: main file ↔ .meta and shadow file ↔ .meta.shadow.

When it’s created

The .meta.shadow file is created automatically when two conditions are met:

1. The store is of type DEFAULT or POSIXSHD - i.e. one that keeps record modifications in a .shadow file (not in the main file).
2. At least one modification of an existing record (storage::write() at an index other than the maximum) is made during the given session.

Condition 1 is not a mode switch but a choice of class. At store initialization the makeMetaIndex() factory (accessorFactory.hpp) asks the accessor for hasShadow() and returns:

storageShadow derives from metaData and overrides the virtual onRecordModified(), getNullBitset(), and reset(); the .meta.shadow file itself is managed by its metaShadow member. As a result, storage contains no branching on shadow mode.

File format

The .meta.shadow file has no header. It is a sequence of entries in the same binary format as the entries in the .meta file, with the difference that the recordCount field stores the absolute record index (not the number of records in an RLE run):

Every call to onRecordModified() in shadow mode appends one entry to the end of the file. Multiple entries for the same position are allowed - the last entry governs (last-write-wins semantics, matching the .shadow file).

Read priority

storageShadow::getNullBitset(i) scans the list of overrides from the end. If it finds an entry for index i, it returns that entry’s null pattern without consulting the main index (Fig. 22):

flowchart TD
    Q["getNullBitset(i)"]
    Q --> SM{"object is a storageShadow?"}
    SM -->|yes| SCAN{"metaShadow::lookup(i)\n(from the end): entry for i?"}
    SCAN -->|found| RET1["Return the nullBitset from the override\n(the most recent wins)"]
    SCAN -->|not found| MAIN["Look up in the main index\n(RLE segments on disk)"]
    SM -->|no| MAIN
    MAIN --> RET2["Return the pattern from .meta"]

Fig. 22. Null-pattern read priority - main index vs. index shadow

Lifecycle

The .meta.shadow file is managed in parallel with the data shadow file:

Persistence across restarts

After the process restarts, a new storageShadow object restores the shadow state already in its constructor, via metaShadow::load() (Fig. 23):

1. It reads all entries from .meta.shadow (no header - a direct format).
2. It loads them into the override list in write order.
3. getNullBitset() and subsequent calls to onRecordModified() behave exactly as they did before the restart.

%% pdf-width: 100%
sequenceDiagram
    participant Proc1 as First session
    participant MS as .meta.shadow
    participant Meta as .meta

    Proc1->>Meta: onRecordAppended([F,F,F]) × 5
    Proc1->>MS: onRecordModified(2, [T,T,T]) → append entry (index=2)
    Note over Meta: .meta unchanged [allNull×5]
    Note over MS: .meta.shadow: [(index=2, [T,T,T])]

    Note over Proc1: restart

    participant Proc2 as Second session
    Proc2->>MS: storageShadow constructor → metaShadow::load()
    MS-->>Proc2: [(index=2, [T,T,T])]
    Note over Proc2: getNullBitset(2) → [T,T,T]
    Proc2->>Meta: mergeShadow() → applyModificationToMainIndex(2, [T,T,T])
    Proc2->>MS: delete the .meta.shadow file

Fig. 23. Index shadow - restoring null patterns after a restart

Usage example - correcting a record while preserving consistency

# 5 records in stream str1, 3 FLOAT fields
# Record 2 has a null value in field 0: nullBitset=[T,F,F]
# The operator corrects field 0 of record 2 → pattern changes to [F,F,F]

# Operations:
storage.write(rec2_corrected, pos=2)
  → .shadow: append (position=2, data_corrected)
  → storageShadow.onRecordModified(2, [F,F,F])
    → .meta.shadow: append (index=2, [F,F,F])

# File state:
# .meta        - unchanged: [isGap=F, count=2, [F,F,F]],
# >> [isGap=F, count=1, [T,F,F]], [isGap=F, count=2, [F,F,F]]
# .meta.shadow - new entry: [gapFlag=0, recordCount=2, bitset=[F,F,F]]

# Read:
getNullBitset(2) → [F,F,F]  (from .meta.shadow)
getNullBitset(1) → [F,F,F]  (from .meta)

# After merging:
storage.merge() → .shadow absorbed into the main file
storageShadow.mergeShadow() → .meta rebuilt, .meta.shadow deleted
# .meta after merge: [isGap=F, count=5, [F,F,F]]  (all records complete)

NOTE: The .meta.shadow mechanism is covered by the unit tests ut_metaShadow_usage (shadow-file format and lifecycle) and ut_storageShadow_usage (integration with metaData and the accessor).

The relationship between the files

In this section, the relationships between the files are shown at two levels. The structural level describes how the data file carries the records, the .desc descriptor defines their format, the .meta file stores information about null values and transmission gaps, .shadow collects data modifications without destroying the original, and .meta.shadow similarly collects overrides of null patterns. The operational level (Fig. 24) shows the read and write flow: reads check .shadow and .meta.shadow first and fall back to the main file and .meta only when there is no entry. In this way the append, update, and read operations keep the data and metadata consistent throughout the artifact’s lifecycle. Merging with merge() / mergeShadow() is not part of this flow: it is a separate API operation that the engine never invokes on its own (Fig. 21).

%% pdf-width: 100%
graph LR
    UP["update<br/>write(N), N < count"] -->|append| SHD
    AP["append<br/>write(N), N ≥ count"] -->|append at the end| MAIN

    subgraph SHD["shadow layer"]
        direction TB
        S[".shadow<br/>(N·size, data)"]
        MS[".meta.shadow<br/>(N, nullBitset)"]
    end

    subgraph MAIN["main layer"]
        direction TB
        D["main file<br/>data"]
        M[".meta<br/>nullBitset"]
    end

    SHD ==>|"1. entry N exists"| RD["read(pos=N)<br/>data + nullBitset"]
    MAIN -->|"2. no entry N"| RD

Fig. 24. The relationship between an artifact’s write, modify, and read operations (DEFAULT and POSIXSHD types)

Fig. 24 shows the flow of append, update, and read operations through the storage layer, and their direct effect on the data file, .meta, .shadow, and .meta.shadow. The record index decides the kind of write: N equal to or greater than the record count is an append, a smaller one is an update. An entry in .shadow is keyed by a byte offset (N·size, relative to the segment when retention is used), an entry in .meta.shadow by the record index N. A record made up solely of null values outside the nullfill phase does not reach the main file - it leaves only a gap entry in .meta. The shadow layer exists only for the DEFAULT and POSIXSHD types; in the remaining types (POSIX, DIRECT, GENERIC, MEMORY) an update overwrites the record directly in the main file and in .meta.

Starting point - a binary file without metadata

The simplest possible way to record a time series is a sequence of raw values in a binary file: fixed record size, no header, no structure description. This approach has one advantage - minimal overhead - and a number of significant limitations:

• Interpreting the data requires knowledge external to the file (field names, types, order).
• No information about transmission gaps - continuity of the data is only apparent.
• Every modification of a historical record irreversibly destroys the original data.
• A change to the record structure invalidates the entire file.

RetractorDB records data from sensors operating in real time, where power interruptions, signal loss, and the need for retrospective data correction are normal operational occurrences, not exceptions. The five-file structure directly addresses each of these limitations.

What each file contributes

The descriptor (.desc) - self-description and independence from code

A binary data file is useless without knowledge of the record structure. The descriptor stores that knowledge alongside the data, which means:

• Data can be read and interpreted without access to the source code or configuration - the .desc file is enough.
• The xtrdb tool can analyze any artifact without additional parameters.
• Changes to a stream’s structure (adding a field, changing a type) are explicit and versionable.
• The TYPE field in the descriptor determines the storage strategy, allowing the same engine to handle durable artifacts, ephemeral ephemerides, and external data sources without changing the query logic.

The metadata file (.meta) - trustworthiness of the time series

A time series with gaps, treated as continuous, leads to incorrect time-window computations, incorrect aggregations, and false correlations. The .meta file provides:

• The ability to distinguish a record with a zero value from a record that is absent (null) - semantically completely different states.
• Recording of transmission gaps without inserting fake records into the data file - the binary file stays dense and positionally addressable.
• RLE compression - typical time series have long stretches without nulls, so the metadata cost is close to zero for good-quality data.
• The ability to reconstruct the exact recording schedule, including gap lengths, which is necessary when computing intervals in the stream algebra.

The shadow file (.shadow) - non-destructive data correction

In measurement systems, correcting faulty samples after the fact is a standard procedure. Overwriting the binary file is irreversible and destroys the evidence of the original measurement. The shadow file:

• Lets you correct any historical record without modifying the main file.
• Preserves the original measurement as the default - deleting the .shadow file fully restores the initial state.
• Allows merging (merge) corrections into the main file only when that is a deliberate decision by the operator, not a side effect of writing.
• Separates certified data (the main file) from working data (the shadow file), which matters in applications requiring auditability.

The index shadow file (.meta.shadow) - metadata consistency during correction

A correction to a record in the data shadow file must be reflected in the null index - otherwise getNullBitset() would return a stale pattern from the main .meta. The .meta.shadow file:

• Maintains consistency between the pairs: main file ↔ .meta and .shadow ↔ .meta.shadow.
• Lets getNullBitset() return the current null pattern for a corrected record without modifying the main index.
• Tracks the lifecycle of the data shadow file - merged and deleted exactly alongside .shadow.
• Enables full state recovery after a restart: overrides loaded from .meta.shadow are immediately available without re-scanning the data shadow file.

File Rotation Mechanism

By file rotation we mean the controlled closing of the current set of data and metadata files and moving them to historical versions (.old<N>), so that a new session can begin writing from a clean state without losing earlier measurements. This is done in order to separate successive acquisition sessions, preserve a full audit trail, and make it easier to diagnose problems over time. The goal of rotation is both to maintain operational tidiness (a current working set plus a session archive) and to make it possible to recover and compare historical data.

NOTE: The functionality described here is covered by the tests: rotation_test, retention, described in the appendix Integration Tests. The it_rotation_null and ut_rdb tests additionally check values and NULL bits in archives from successive sessions.

Default behavior (without the ROTATION directive)

Without the ROTATION directive in the RQL script, xretractor deletes artifact files (binary data, .desc, .meta) on every startup and begins recording from scratch.

Rotation and deletion do not apply to ephemerides (DECLARE). That does not mean an ephemeride has no file at all: its data source (a text file, a device) is external to the system and untouchable, and next to it a .desc descriptor describing the read schema is created - storage::attachDescriptor() writes one for every stream, declared ones included. What an ephemeride does not get is a .meta index: for declared sources the makeMetaIndex() factory injects an inert variant (metaData with an empty file path) that keeps null patterns in memory and performs no I/O. It is therefore an absence of metadata persistence, not an absence of the index object itself.

The ROTATION directive and the session counter

The ROTATION directive enables history-preservation mode. It takes the path to a file that stores a persistent session counter:

ROTATION 'rdb_counter'

The PersistentCounter object reads the value N from the file and writes N+1 in its constructor, reserving the next session number before archiving begins. getCount() still returns N, used in the current session’s suffixes. A missing file means first use and number 0; an existing empty or unreadable file, or one that does not contain a valid nonnegative integer, stops startup. A process crash can consume a number without creating a complete archive set, so gaps in the numbering are allowed. The counter value does not prove that the preceding rotation completed.

The counter is written through a temporary file: its contents are synchronized with fsync, and rename then replaces the destination file. Failure before that replacement completes stops startup. After replacement, the engine attempts to fsync the directory; failure is reported at ERROR level, but neither rolls back the reservation nor stops startup. The ut_persistentCounter::PersistentCounterTest.construction_reserves_next_value test checks the saved value while the object is still alive.

Control flow during rotation

At a clean shutdown of session N, the data file, metadata index, and existing shadow files receive the same .oldN suffix. The diagram shows the archival order for disk storage; MEMORY stores and DECLARE sources do not participate in this rotation.

%% pdf-width: 100%
sequenceDiagram
    participant RQL as xretractor
    participant D as data file
    participant M as .meta file
    participant Old as .oldN files

    Note over RQL: session N starts, percounter = N
    Note over RQL: PersistentCounter writes N+1 before archiving
    RQL->>D: open storage
    RQL->>M: prepare index
    Note over RQL: operation - writing records
    RQL->>D: append records
    RQL->>M: update RLE index
    Note over RQL: clean session shutdown
    RQL->>Old: archive .meta.shadow if present
    RQL->>M: flushCurrentEntry()
    RQL->>Old: rename .meta to .meta.oldN
    RQL->>Old: accessor destructor - data and shadow under .oldN

Fig. 25. File rotation sequence - session start and stop

storage::~storage() calls metaData::rotate(N, false): it flushes the pending RLE entry, archives the index, and detaches it from the file without creating a new active .meta. The storageShadow variant first archives an existing .meta.shadow. The accessor destructor then rotates the data and its shadow. Files with the same number belong to the same session and allow its values and NULL bits to be reconstructed.

If startup finds empty data but a nonempty index left by an older engine, detectStartupState() resets the orphaned index. It does not assign it the current session number. This also happens when gap detection is disabled. Shutdown archiving is not a transaction over the entire file family; interrupting the process during renames can leave an incomplete set.

Rotation failures and archive durability

Data, data-shadow, metadata, and metadata-shadow renames use rotateStorageFile. After a successful rename, the engine calls fsync on the containing directory; if the source and destination directories differ, it attempts to synchronize both. Failure to inspect a path, rename a file, open a directory, call fsync, or close the descriptor is reported at ERROR level, including in Release, with the path and cause. Overwriting an existing archive also produces an ERROR message, but is not blocked: its previous contents are lost.

Directory synchronization persists file-name entries. It does not replace fsync of the archived file’s contents or provide a transaction over the complete data and metadata set. If the rename succeeds but subsequent directory synchronization fails, the engine does not undo the rename. After a failure, check archive completeness and rotation diagnostics independently of the counter value.

Failed metadata rotation does not reset the unarchived index. With reopen=true, which prepares for further writing, it throws an exception instead of creating an apparently valid empty index. Storage shutdown uses reopen=false: it detaches persistence without throwing. If the metadata shadow stayed under its active name after a failed rotation, the main index also stays under its active name; if the shadow was renamed and only directory synchronization failed, the main index can be archived. Destructor errors do not by themselves change the process exit code, so a successful exit code does not confirm complete rotation. The ut_storageRotation test checks operation order, diagnostics, and failure paths.

What ends up in .old<N> files

The ROTATED FILES section of xtrdb -s groups files by their suffix number. For archives produced after fix #322, the .oldN and .meta.oldN pair belongs to the same session. Older archives are not automatically renumbered: they may retain the former one-session mismatch and require a provenance check before analysis.

Example: sequence of three sessions

After three completed sessions (0, 1, 2), and after writing begins in a fourth (3), an example set without shadow files looks like this:

measurement.old0         - data from session 0
measurement.meta.old0    - metadata from session 0
measurement.old1         - data from session 1
measurement.meta.old1    - metadata from session 1
measurement.old2         - data from session 2
measurement.meta.old2    - metadata from session 2
measurement              - current data (session 3)
measurement.meta         - current metadata (session 3)

xtrdb -s measurement groups the archives under [0], [1], and [2]. Group [3] appears only when the current session closes. This example illustrates names and their meaning without assuming fixed file sizes.

Opening a rotated file in xtrdb

Rotated files can be examined with the open command in xtrdb’s interactive mode. The open command automatically strips the base name (removes .old<N>) and looks for the descriptor <base_name>.desc:

$ xtrdb
. open measurement.old1
ok
. print
...

Inspection Tool: xtrdb -s

The command xtrdb -s <path> displays a complete picture of an artifact’s storage state - without starting the xretractor process, without entering interactive mode. Just point it at the base path (without extension), and the tool finds the associated files on its own: .desc, binary data, .meta, .shadow, cyclic segments, and rotated files.

NOTE: The functionality described here is covered by the test: issue153_storagemap_meta_cases, described in the appendix Integration Tests.

Purpose and use cases

The command is read-only - it does not modify any file. It can also be run while xretractor is not running.

What the map shows

The whole report is framed with box-drawing characters. The top part is a three-column overview map:

┌──────────────────────────────────────────────────────────────┐
│   Storage map: <name>                                        │
├──────────────────────────────────────────────────────────────┤
│ [shadow]   │ [binary data] │ [meta index]                    │
├────────────┼───────────────┼─────────────────────────────────┤
│ ...        │ ...           │ ...                             │
├────────────┴───────────────┴─────────────────────────────────┤
│   SECTION  ...                                               │
└──────────────────────────────────────────────────────────────┘

Each row of the map corresponds to one RLE segment or one data segment:

Below the map come further sections:

META bar legend

[====] - data with no null values
[----] - partial nulls (at least one field is null)
[~~~~] - all fields are null (nullfill)
[XXXX] - transmission gap

Example 1 - a simple artifact

Stream measurement with two fields, 100 records, no modifications, no gaps:

{
  INTEGER  ts
  FLOAT    value
  TYPE     DEFAULT
}

$ xtrdb -s measurement

┌──────────────────────────────────────────────────────────────┐
│   Storage map: measurement                                   │
├──────────────────────────────────────────────────────────────┤
│ [shadow]   │ [binary data] │ [meta index]                    │
├────────────┼───────────────┼─────────────────────────────────┤
│            │ 0-100         │ [====] 100 records, no nulls    │
├────────────┴───────────────┴─────────────────────────────────┤
│   DESCRIPTOR  measurement.desc                          43 B │
│   INTEGER  ts                                            4 B │
│   FLOAT  value                                           4 B │
│   Record size:                                           8 B │
├──────────────────────────────────────────────────────────────┤
│   DATA        measurement                              800 B │
│   Records: 100                                               │
├──────────────────────────────────────────────────────────────┤
│   META        measurement.meta                          26 B │
│   Segments: 1   Records: 100                                 │
│   [==========================100===========================] │
│   Legend: [====] data  [----] partial null                   │
│           [~~~~] nullfill  [XXXX] gap                        │
├──────────────────────────────────────────────────────────────┤
│   SHADOW      measurement.shadow (missing)               0 B │
└──────────────────────────────────────────────────────────────┘

Interpretation: one RLE segment, no gaps, no nulls, no shadow file present. The binary file is exactly 100 × 8 = 800 bytes.

Example 2 - an artifact with a transmission gap and a modification

Stream sensor with three fields. After 50 records there was a gap (10 interval units), then 30 records arrived with partial gaps in the pressure field. Two records were later modified (a shadow file is present):

{
  INTEGER  ts
  FLOAT    temp
  FLOAT    pressure
  TYPE     DEFAULT
}

$ xtrdb -s sensor

┌──────────────────────────────────────────────────────────────┐
│   Storage map: sensor                                        │
├──────────────────────────────────────────────────────────────┤
│ [shadow]   │ [binary data] │ [meta index]                    │
├────────────┼───────────────┼─────────────────────────────────┤
│            │ 0-50          │ [====] 50 records, no nulls     │
│            │               │ [XXXX] 10 records, gap          │
│ 2 updates  │ 50-80         │ [----] 30 records, some nulls   │
├────────────┴───────────────┴─────────────────────────────────┤
│   DESCRIPTOR  sensor.desc                               52 B │
│   INTEGER  ts                                            4 B │
│   FLOAT  temp                                            4 B │
│   FLOAT  pressure                                        4 B │
│   Record size:                                          12 B │
├──────────────────────────────────────────────────────────────┤
│   DATA        sensor                                   960 B │
│   Records: 80                                                │
├──────────────────────────────────────────────────────────────┤
│   META        sensor.meta                               60 B │
│   Segments: 3   Records: 80                                  │
│   [===========50===========][XXgap:10XX][-------30---------] │
│   Legend: [====] data  [----] partial null                   │
│           [~~~~] nullfill  [XXXX] gap                        │
├──────────────────────────────────────────────────────────────┤
│   SHADOW      sensor.shadow                             26 B │
│   Updates: 2                                                 │
└──────────────────────────────────────────────────────────────┘

Interpretation: the binary file contains 80 records (the gap takes no space in the data file); the gap is encoded solely in .meta. The [binary data] column shows an empty range for the gap segment - there is no binary data for it. The pressure field in records 50–79 has null values in some records ([----]).

Example 3 - an artifact with segmented retention

Stream buffer with cyclic retention: up to 10 segments of 100 records each (1000 records total). Currently 280 records have been written, across three segments:

{
  DOUBLE   value
  TYPE     DEFAULT
  RETENTION 1000 100
}

$ xtrdb -s buffer

┌──────────────────────────────────────────────────────────────┐
│   Storage map: buffer                                        │
├──────────────────────────────────────────────────────────────┤
│ [shadow]   │ [binary data] │ [meta index]                    │
├────────────┼───────────────┼─────────────────────────────────┤
│ s0         │ s0 0-100      │ [====] 100 records, no nulls    │
│ s1         │ s1 100-200    │ [====] 100 records, no nulls    │
│ s2         │ s2 200-280    │ [====] 80 records, no nulls     │
├────────────┴───────────────┴─────────────────────────────────┤
│   DESCRIPTOR  buffer.desc                               48 B │
│   DOUBLE  value                                          8 B │
│   Record size:                                           8 B │
├──────────────────────────────────────────────────────────────┤
│   DATA TOTAL  rec=280 src=0 seg=280                   2240 B │
│   Records: 280                                               │
│   Source: buffer   Segments: buffer_segment_*                │
│   Segmented data (RETENTION): 3                              │
│   Policy: segments=10 capacity=100                           │
│   Retention cap records: 1000                                │
│   Retention cap bytes: 8000                                  │
│   Total records: 280                                         │
│     current=0  segments=280                                  │
│   Total bytes: 2240                                          │
│     current=0  segments=2240                                 │
│     [0] buffer_segment_0 rec:100 range:0-100                 │
│     [1] buffer_segment_1 rec:100 range:100-200               │
│     [2] buffer_segment_2 rec:80 range:200-280                │
├──────────────────────────────────────────────────────────────┤
│   META        buffer.meta                               26 B │
│   Segments: 1   Records: 280                                 │
│   [=========================280===========================]  │
│   Legend: [====] data  [----] partial null                   │
│           [~~~~] nullfill  [XXXX] gap                        │
├──────────────────────────────────────────────────────────────┤
│   SHADOW      buffer.shadow (missing)                    0 B │
└──────────────────────────────────────────────────────────────┘

Interpretation: the [binary data] column shows each segment with its sN label and its global index range. The DATA TOTAL section gives a full breakdown: src=0 (no records outside the segments), seg=280 (all records within segments). Once the buffer fills up (10 segments × 100 = 1000 records), the oldest segment will be deleted and a new one appended.

Summary: Rationale for the Chosen Structure

This chapter draws together the conclusions from every part of the data-storage-format documentation and explains why the adopted file structure is minimal and sufficient for a real-time time-series recording system.

The file set and accessor types

Every artifact or substrate consists of up to five files - the binary data file, the .desc descriptor, the .meta index, the .shadow data shadow, and the .meta.shadow index shadow. The last two form a pair: the data shadow preserves the originally recorded content, and the index shadow preserves the null patterns that go with it, so correcting a record does not desynchronize data from metadata. The TYPE field in the descriptor selects the FileInterface implementation: DEFAULT (data + shadow + retention), MEMORY (RAM only, ephemerides), BINFILE / TEXTSOURCE / DEVICE (read-only external sources), and intermediate variants. The accessor is chosen once, when storage is initialized - the RQL query logic knows nothing about storage details.

Artifact files

The descriptor (.desc) defines the record schema in ANTLR4 grammar: field names, types (BYTE, INTEGER, FLOAT, DOUBLE, RATIONAL, STRING), array sizes, retention policy (RETENTION, RETMEMORY), and accessor type (TYPE). The record size R is the sum, in bytes, of all data fields - the meta-descriptor’s own fields take no space in the record. Having the descriptor alongside the data means self-description: the xtrdb tool, or any code, can interpret an artifact without access to the source code.

The binary data file is a flat sequence of fixed-length R-byte records with no header. Record i always sits at offset i × R. An append operation writes to the end; an update operation - when a .shadow file is present - goes to the shadow file, rather than overwriting the main file.

The metadata file (.meta) stores a compressed RLE index of null values and transmission gaps. Each RLE entry describes a run of consecutive records sharing an identical null pattern: an isGap flag, a recordCount, the bitset size, and the bitset itself. A transmission gap (gap) exists only in .meta - the binary file does not record it and stays dense. The managing class is rdb::metaData: it buffers the current segment in currentEntry_, writes a segment to disk only when the pattern changes, and the DiskTailState state (lazy overwrite of the last on-disk entry) ensures the file size does not grow under continuous, uniform data arrival. After a restart, loadIndex() restores the state and brings the last non-gap segment back into memory, allowing the RLE run to continue. The file I/O itself is handled by MetaIndexStore, and gap detection by GapDetector.

The shadow file (.shadow) collects record modifications as a sequence of (position, data) entries. Reading a record checks .shadow from the end (the most recent modification wins); if there’s no entry, it reads from the main file. Deleting .shadow fully restores the original state. The merge() operation writes the corrections back into the main file and clears the shadow file; it is available only through the API - neither the engine nor xtrdb invokes it on its own, so in normal operation corrections stay in .shadow.

The index shadow file (.meta.shadow) is the counterpart of .shadow at the null-pattern level. It appears for stores that maintain a data shadow: the makeMetaIndex() factory then injects a storageShadow object into storage instead of the base metaData, and that object routes updates to its metaShadow member. Without this file, correcting a record would change its null pattern in .meta even though the original content still sits untouched in the main file - the “data ↔ metadata” pair would drift apart on the first merge() or shadow discard.

The rotation mechanism

The ROTATION 'rdb_counter' directive turns on session-history preservation mode. PersistentCounter stores a monotonically increasing session number N. Rotation is a process spread out over time: at the start of session N, detectStartupState() detects an inconsistency (data file empty, .meta non-empty) and renames .meta to .meta.oldN; at session shutdown, the posixBinaryFile destructor renames the data file to .oldN and the shadow file to .shadow.oldN. As a consequence of this ordering there is an offset of 1: .meta.oldN contains the metadata for session N−1, while .oldN contains the data for session N. Without the ROTATION directive, artifact files are deleted on every startup.

The inspection tool xtrdb -s

The command xtrdb -s <path> is the only tool for inspecting storage state without starting xretractor. The report consists of an overview map (columns: shadow, binary data, meta index) and detailed sections: DESCRIPTOR, DATA (or DATA TOTAL for segmented retention), META with an RLE bar, SHADOW with the count of uncommitted modifications, and ROTATED FILES with the rotation history. The META bar uses four symbols: = (data, no nulls), - (partial nulls), ~ (nullfill), X (gap). The tool is read-only and works while the xretractor process is not running.

Comparison of approaches

Compilation and Plan Construction

The compilation process happens before every run of the xretractor process, provided a file with a sequence of commands and queries was given. That argument is required in -c mode (compile only) - without it there is nothing to compile; in processing mode, omitting it starts idle mode, where the compilation stage is skipped entirely. Based on the flow shown in Fig. 14, I prepared a description of the process in Fig. 26, showing the compilation process in development mode. Compilation itself can run independently of live instances. In execution mode, reusing the same instance name is rejected, while another name starts a separate plan unless the bus detects a collision in its streams, storage files, or rotation counter.

As an example file for compilation, we’ll use a file query.rql with the following content:

DECLARE a INTEGER STREAM core0, 0.1 BINFILE 'datafile1.dat'

SELECT str1[0]+1 STREAM str1 FROM core0>2

This is a very simple example of a file containing two directives. The first declares the existence of an ephemeris in the form of a binary data source containing 4-byte INTEGER values. Data from this file will be read at a rate of 10 times per second. And the name of this object is core0.

The second command creates an artifact named str1, taking ephemeral data shifted in time by two reads, i.e. 0.2 seconds. While building successive elements of the output stream, the data read from core0 is processed, and the value 1 is added to every value read.

To compile this file, the following command must be invoked:

$ xretractor -c query.rql

The following system response will be printed on the screen:

core0(1/10)	datafile1.dat
	a: INTEGER
str1(1/10)	origin=2
	:- PUSH_STREAM(core0)
	:- STREAM_TIMEMOVE(2)
	str1_0: INTEGER
		PUSH_ID(str1[0])
		PUSH_VAL(1)
		ADD

Omitting the -c parameter will cause the system to attempt compilation and immediately send the compiled query execution plan for execution. This will cause an error, since the data file datafile1.dat presumably hasn’t been prepared yet.

Besides the text view, we can also look at the compilation output in graphical form. To do this, invoke the following sequence of commands:

$ xretractor -c -d -f -t -s query.rql > out.dot && dot -Tsvg out.dot -o out.svg

Assuming you have the dot program from the graphviz package installed in your runtime environment, this command will generate an image file showing the system’s response in the form of a graph.

RetractorDB can generate an image in response to one of the requested data-processing chains. The graphical presentation is most suitable for creating and presenting data-processing graphs. Unfortunately, readability suffers for very complex schemas.

Fig. 27 shows the trivial query execution plan produced by compiling the two-line query.rql file. At the very top we see the object str1, producing artifacts at a rate of 10 records per second. Information about the artifact-creation rate does not appear in the query; it is computed based on the algebraic expression in the FROM clause of the SELECT query. We can also see how successive records of the str1 stream are produced. Here we have a typical stack-based data-processing algorithm. First, the ephemeral value produced by the algebraic expression is pushed onto the stack, then the value 1 is placed on the stack. The ADD instruction pops both values off the stack, leaving the sum on the stack. What remains on the stack - i.e. the result of the addition - is placed into the field of the record being created.

On the other side we see stream operations. Stream operations are carried out in a different domain. There, we process objects of one or two values. Operations act either on two streams, or on a single stream with an argument. The classic stack has no application for algebraic stream operations. For simplicity, the notation resembles stack operations somewhat. We see, in the attached example, that operations on current data are carried out by shifting the data in time by 2. I deliberately do not say that this is 2 seconds - here 2 denotes a relative value with respect to the arrival rate. For an arrival rate of 10 samples per second, the value 2 means a time shift of 0.2 seconds.

Complex algebraic expressions involving at least two stream operators give rise to the substrates mentioned in previous chapters. Every query whose FROM-clause algebraic expression contains more than one operator is broken down into interdependent two-argument operations. The substrate’s argument list is, by default, the full expansion of the schema.

Available xretractor flags

Different sets of flags are available in compile mode (-c) and in execution mode. Below are the compile-mode flags used for generating graphs:

Execution-mode flags (without -c):

ℹ️ Info

The -m N parameter counts iterations of the main loop, not seconds. For streams with a 0.1 s interval (10 Hz), -m 10 means ~1 second of processing.

⚠️ Warning

When receiving the results of a run limited by -m N through xqry, add -x (--xqrywait). Without this flag, the server may process the entire budget before the client connects. The gate is released after the first command has been handled: xqry --select registers its subscription before computation starts. Another client’s --dir or --hello also releases the gate, so it is not a readiness barrier for all receivers. When inspecting artifacts after the process has finished, -x is not needed and will hold up the run if no client command arrives.

A full list of all options with a description of each - including the --realtime option, which requires system privileges - can be found in Appendix A.

Data Processing and Distribution

Starting the data-processing process and analyzing the diagram shown in Fig. 14, we can identify the following flow - Fig. 28:

To carry out the processing, we’ll need to prepare data and build a data-processing chain. As input to this chain we’ll use a prepared query-plan file, and we’ll prepare a binary file with data. We’ll build a process that processes the data and displays the results.

We’ll change the source query.rql file to the following:

DECLARE a INTEGER STREAM core0, 0.1 TEXTFILE 'datafile1.txt'
DECLARE a BYTE STREAM core1, 0.2 DEVICE '/dev/urandom'

SELECT str1[0], str1[0] + str1[1]/20 STREAM str1 FROM core0 + core1

In this example we declare the existence of a text file containing text data. I suggest filling the file datafile1.txt with the following content:

$ seq 20 28 > datafile1.txt

20
21
22
23
24
25
26
27
28

The file will contain consecutive numbers from 20 to 28.

A look at the query execution plan gives us the picture in Fig. 29:

Once we’ve prepared the data file, we can start the compilation and data-processing process. We do this by running the following command:

$ xretractor query.rql

And here an important property of the system comes into play. The system should immediately begin executing the process. Any key pressed in the terminal will interrupt this process.

I suggest opening a second terminal window and continuing the session there. In the second terminal window we can run the following command:

$ xqry -d
name  | duration | size | count | location      | cap
------+----------+------+-------+---------------+----
str1  | 1/10     | 6912 | 864   |               | 0
core0 | 1/10     | -1   | 49    | datafile1.txt | 1
core1 | 1/5      | -1   | 25    | /dev/urandom  | 1

Something similar should appear. Of course, the counters for str1 should differ. It’s logical that with every read we’ll get larger values for the accumulated size of the str1 stream.

If we want to see, on screen, what’s happening inside the data-processing process right now, I suggest issuing the command below, and after a few lines appear on screen, pressing any key to interrupt the process:

$ xqry -s str1
20 26
21 33
22 34
23 27
24 28
25 35
26 36
27 28

The first column contains the sequence of numbers - exactly as we entered them into the datafile1.txt file. The second column contains the result of processing. A value taken from the pseudo-random number generator, divided by 20, is added - the second column flows along beneath the first.

How can we see this graphically? I suggest running the following command:

$ xqry -s str1 -p 50,50 | gnuplot

The following window will appear on screen, with data streaming in live:

In Fig. 30 we see what the data represented numerically looks like. The sawtooth shape is the first column; the irregular shape wrapping around the sawtooth is the second column. The figure shows a static snapshot - but in the actual window, this data streams in and the picture updates continuously.

A typical way to send data outside the machine on which xretractor and xqry are running is to use the command:

$ xqry -s str1 | nc -l 8888

on the second computer, you need to write:

$ nc server_name_or_ip 8888

ℹ️ Info

The -p flag in netcat (BSD syntax) is not supported by the GNU netcat available on modern Ubuntu/Debian systems. The correct syntax is nc -l 8888 (without -p).

Data transmission will take place over the network.

If we want to stop the xretractor process using the xqry command, we can run the following command:

$ xqry -k

After issuing this command, the xretractor process will shut down and interrupt the query plans being processed.

A recording of the process shown on screen (Fig. 31) looks as follows:

Artifact Analysis

Looking more broadly at the potential data paths in Fig. 14, the last undescribed path is the one involving the xtrdb tool.

While building the system, I needed a tool for accessing artifacts in order to run integration tests. To verify correctness, I had to compare processing results at various stages. Fig. 32 shows the complete data flow, including the role of the xtrdb tool.

To present the artifact-analysis process, the entire processing chain needs to be taken into account. We’ll use the same query as before. However, we’ll run our data-processing process a bit differently this time.

$ xretractor -m 10 query.rql

A query-processing run invoked this way will finish after 10 processing cycles. The -m parameter specifies the number of iterations of the main loop, not the number of seconds - the running time depends on the interval of the source streams. For streams with a 0.1 s interval (10 Hz), this means ~1 second of runtime. After it finishes, and we look at the directory in which we ran the query, we should see the following files:

$ ls -al
total 32
drwxr-xr-x  2 michal michal 4096 Oct  4 18:01 .
drwxr-xr-x 10 michal michal 4096 Oct  4 17:59 ..
-rw-r--r--  1 michal michal   51 Oct  4 18:01 core0.desc
-rw-r--r--  1 michal michal   43 Oct  4 18:01 core1.desc
-rw-r--r--  1 michal michal   27 Oct  4 17:59 datafile1.txt
-rw-r--r--  1 michal michal  180 Oct  4 18:00 query.rql
-rw-r--r--  1 michal michal   72 Oct  4 18:01 str1
-rw-r--r--  1 michal michal   34 Oct  4 18:01 str1.desc

As you can see, three .desc files were created, plus one file containing artifacts. If we look inside the str1 file, we’ll see fairly modest content:

$ hexdump str1
0000000 0014 0000 0015 0000 0015 0000 0016 0000
0000010 0016 0000 0017 0000 0017 0000 0018 0000
0000020 0018 0000 0019 0000 0019 0000 001a 0000
0000030 001a 0000 001b 0000 001b 0000 001c 0000
0000040 001c 0000 001d 0000
0000048

Alongside the artifact file, metadata files are also created. Their content describes the structure of the file.

$ cat str1.desc

{       INTEGER str1_0
        INTEGER str1_1
}

The descriptions of the ephemeris files are far more interesting. The description files for ephemeral data point to files in the Linux filesystem.

$ cat core0.desc

{       INTEGER a
        REF "datafile1.txt"
        TYPE TEXTSOURCE
}

$ cat core1.desc

{       BYTE a
        REF "/dev/urandom"
        TYPE DEVICE
}

Metadata description files are created automatically the moment an object is registered in RetractorDB. Remember to delete these descriptors if you modify the query.rql file.

Once the xtrdb program is started in a terminal, the tool displays a dot (.) as its prompt. This character is just a prompt - it is not part of the command. You can start interacting with the tool right away. Example session:

$ xtrdb
.open str1
ok
.desc
{       INTEGER str1_0
        INTEGER str1_1
}
.list 1
{ str1_0:20 str1_1:21 }
.quit

Working with this tool feels like working with a classic, old-school dbase database. There’s no state machine here, no loops or conditions - just reading and modifying binary files described by metadata.

The main goal of this tool was to support the creation of test scripts. RetractorDB is deterministic. The system has no race conditions - data that arrives on the input should always produce the same results on the output. Unless, of course, we mix in random data, as in the example shown here.

NOTE: The functionality described here is covered by the tests: issue113_meta_xtrdb, issue113_meta, issue113_null_txtsrc, Pattern5, described in the appendix Integration Tests.

A very useful feature of this tool is the list and rlist functions - listing the initial elements of a file, or the final elements of a file, respecting the structure described in the metadata.

.list 4
{ str1_0:20 str1_1:21 }
{ str1_0:21 str1_1:22 }
{ str1_0:22 str1_1:23 }
{ str1_0:23 str1_1:24 }
.rlist 4
{ str1_0:28 str1_1:29 }
{ str1_0:27 str1_1:28 }
{ str1_0:26 str1_1:27 }
{ str1_0:25 str1_1:26 }

I encourage you to experiment and browse the source of this tool. It’s one of the less complicated, yet very useful, parts of RetractorDB.

Inspecting null/gap metadata

Every artifact has an associated .meta index file, described in detail in the chapter on the storage format. Its content can be viewed directly in xtrdb with the meta command:

.open str1
ok
.meta
record 0: count=9 gap=false nullBitset=00

The gap=false entry means there is no gap in the data; nullBitset shows which fields contain null values (one bit per field). Data with no gaps at all forms a single entry count=N, where N is the total number of records.

Summary

In summarizing, it’s worth pointing out the scope of knowledge this chapter conveys. Here I wanted to show how the individual parts of the system can be run, and what the command sequences look like on which we build further functionality using RetractorDB.

I tried to reduce the number of potential commands to a minimum. At present I have effectively reduced the set to 3 commands. I believe a system designed this way will be maximally useful and reasonably efficient. Complexity is a separate matter. Explaining the processing itself - the new algebra, and why a plus sign doesn’t mean plus - is, in itself, difficult. I hope, though, that once a certain barrier of understanding is crossed, the rest becomes obvious. The decisions made were the result of reflection, trial, and error. I want to emphasize that, quite simply, I did not find a better method.

Query Compilation

An attentive reader will probably notice that, in the compiled query execution plans shown in the previous chapter, certain values don’t match what was written in the query.

The compiler, while building a query plan, carries out the process autonomously. Sometimes it feels like you ask for one thing and get something else - at first glance this behavior seems entirely counterintuitive. And as a user, I fundamentally have no control over it. Interestingly, the outcome of the query does correspond to what I asked for in the query. Perhaps the correct title for this chapter should be: Why does the compiler do things its own way, and claim to know better?

In this chapter I want to explain how I solved the syntactic problems I encountered while building the query language.

Compiler input and output

The .rql file

Compiler input - text in the RQL language containing DECLARE, SELECT, and RULE statements as well as configuration directives (e.g. :STORAGE). The ANTLR4 parser reads the file statement by statement.

The order of DECLARE and SELECT in the file does not matter: a query may refer to a stream defined further down, because dependencies between streams are resolved only by the compiler. RULE is the exception - the parser attaches a rule to a stream that has already been read, so a rule must come after the definition of its stream; otherwise the parser reports Rule '…' refers to stream '…', but no such stream is defined. A reference to a stream that does not exist anywhere in the file stops compilation with Referenced Stream in QUERY _not found_ in CORE TREE.

The ANTLR4 parser → qTree

The parser builds the internal representation qTree - a std::vector<query> - by appending one element for every DECLARE and SELECT statement and configuration directive, in file order and without sorting. A SELECT element carries the field schema with its stack programs and the FROM program that names the source streams. At this point the time interval (delta) is known only for DECLARE declarations; for SELECT queries the compiler determines it. A STREAM name[N] generator template is still a single element, and a RULE does not create an element of its own - it goes onto the rule list of its stream.

The order of the vector changes during compilation: interval resolution sorts it by delta, and the topological order (producer before consumer) is restored only by the last stage.

The 23 compilation stages

qTree passes through an ordered chain of transformations: from breaking down FROM expressions into two-argument operations, through determining deltas, simplifying expressions, and locating fields, all the way to semantic verification, buffer-size computation, and the final topological sort. Each stage assumes the previous one succeeded.

Execution plan → dataModel

At the output of compilation, every query in qTree has: a field schema with types and offsets, a delta, buffer sizes, and a ready instruction sequence. dataModel takes over this plan and executes it cyclically in real time.

The -c flag stops xretractor after this step and prints the plan to standard output - without starting processing.

Overview of topics covered in this chapter

The chapter is structured following the order of the compiler’s stages - from a description of the data structure and the chain of stages, through the individual transformations, to error handling.

Compilation Passes

Query compilation in RetractorDB proceeds through multiple stages. Each stage transforms the internal representation of the queries - the qTree tree - and passes the result to the next one. The order is strictly fixed: every stage assumes the previous one succeeded.

qTree is a std::vector<query> - the central data structure of the compiler and executor. Every element corresponds to one query (SELECT or DECLARE) and stores its field schema, stack-instruction sequence, time interval, startup tail, and references to source streams. Not every stage preserves vector order: interval resolution sorts it by rInterval. Compilation therefore ends with an unconditional topological sort, which guarantees that a producer precedes its consumer during execution.

Running example

Throughout the chapter we follow a single query - query.rql - through the successive stages:

DECLARE a BYTE, b INTEGER STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'
DECLARE e INTEGER STREAM core2, 0.3 TEXTFILE 'sensor_c.txt'

SELECT *                    STREAM merged FROM core0 + core1
SELECT merged[0], merged[2] STREAM result FROM merged

After passing through all the stages, xretractor -c query.rql prints:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
merged(1/10)	tail=1
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_ADD
	core0_0: BYTE
		PUSH_ID(merged[0])
	core0_1: INTEGER
		PUSH_ID(merged[1])
	core1_2: INTEGER
		PUSH_ID(merged[2])
	core1_3: FLOAT
		PUSH_ID(merged[3])
result(1/10)	tail=1
	:- PUSH_STREAM(merged)
	result_0: BYTE
		PUSH_ID(result[0])
	result_1: INTEGER
		PUSH_ID(result[2])
core2(3/10)	sensor_c.txt
	e: INTEGER

The plan is printed in the final topological order: the declarations core0 and core1 precede their consumer merged, which precedes the query result. The unused declaration core2 goes last. tail=1 is the startup tail determined by computeStartupLatency. PUSH_ID references point to positions in the query’s input record, written under the query’s own name: result[2] is the third field of the merged record, that is core1.c.

The field list of result refers only to the stream in its own FROM clause. Writing core1[0] there ends in the compilation error Stream 'result' refers to 'core1', which is not in its FROM clause: core1 is a source of merged, not of result - see Aliasing.

The subchapters on substrates and the _ symbol use extended variants of the same set of declarations. For how to interpret every element of this plan, see Compilation Debugging.

The chain of stages

The chain of twenty-five stages is defined by the compiler::compile() function:

The stages factorMatchedHashTimeMoves, deduplicateSubstrats, simplifyFieldExpressions, and shareEquivalentSelectComputations are optimizations that the RDB_OPT_* switches can disable. Disabling them does not change result values; at most it can lengthen the startup tail (see factorMatchedHashTimeMoves). All other stages always run.

checkFunctionCalls

Validates scalar-function names and arity against the single rqlFunctions.hpp table. Matching is case-insensitive and the canonical spelling is stored in the token. An unknown function or invalid width stops compilation through Check result: before generator expansion, so one template error is not multiplied N times.

checkStreamReducerFieldRefs

Rejects a stream reducer (MIN, MAX, AVG, SUMC without a window width) used in a SELECT field program or in a RULE condition. The grammar admits it in a scalar expression, but no execution mechanism evaluates it there: the query SELECT avg STREAM o FROM AVG(src) used to pass compilation and then never emitted a single record. A stream reducer belongs in the FROM clause; the working SELECT * FROM AVG(src) is not affected by this check. The stage sits next to checkFunctionCalls for the same reason - before generator expansion.

expandStreamGenerators

Expands every SELECT ... STREAM name[N] ... template into N ordinary queries named name$0…name$(N-1) and substitutes the instance ordinal for $ in fields, values, and FROM references. It is the first pass that rewrites the plan (only the checkFunctionCalls and checkStreamReducerFieldRefs checks precede it): everything after it receives a plan indistinguishable from hand-written queries. See SELECT Command for syntax and constraints.

Before copying a template it also checks the number of streams after expansion: at most 148. See Plan Size Limits for the other bounds.

snapshotNamedSourceRefs

Snapshots source references written by the user before substrates are created. Later field localization uses the snapshot to distinguish legal synthetic tokens from references to a component of #, whose identity is no longer preserved by the result.

extractIntermediateStreams

Reduces every FROM expression to at most a two-argument form. Complex expressions like (core0#core1)+core2, and chained notations without parentheses (core0+core1+core2, core0#core1#core2), require intermediate streams. Every query is reduced to a fixed point, so the stage also handles adjacent unary subexpressions such as (core0>2)#(core1>1). This stage automatically creates substrates - see Substrates.

expandSchemaWildcards

Expands both * in the SELECT clause and the [_] index. It replaces an asterisk with fields derived from the source schema. A formula containing x[_] is replicated according to the number of slots that x contributes to the record produced by the complete FROM clause, rather than the width of stream x itself. A one-field x under the window x@(1,5) therefore yields five elements. If the named contribution does not form a contiguous block of fields in FROM, compilation fails instead of assuming an arbitrary width.

At this stage, derived schemas expand a numeric T[N] entry into N scalar fields. A declaration descriptor still retains one array entry, while byte layout and flat-slot order remain unchanged. STRING[N] remains one text field. Stream operators, reducers, AGSE, and payloads therefore use the same indexing unit. See Asterisk Expansion and Underscore Symbol Processing.

resolveStreamIntervals (← loops are detected here)

Determines the time interval (delta) of every stream based on the algebraic operators and the intervals of the input streams. An iterative algorithm resolves as many streams as possible in each round. A record-history aggregate in the SELECT list does not change the interval and requires one plain stream reference in FROM; a compound clause is rejected here. The pass detects cyclic dependencies by stopping when the number of unresolved streams stops decreasing - see Interval Resolution and Loop Detection.

factorMatchedHashTimeMoves

Recognizes matched shifts of interleave arguments. When i·ΔA=k·ΔB, it rewrites (A>i)#(B>k) as (A#B)>(i+k), reducing two shift substrates to one interleave substrate. Unmatched cases and substrates shared with other consumers remain unchanged - see Substrates.

A shift moves silence into the logical origin rather than inserting prefix records. Equality of the physical shifts makes both sides of the rule carry the same emitted sequence and the same logical origin. The tails are not equal: the factored side reads content directly from the interleave, so it is ready no later - and usually earlier - than the side that reads components after their own shift. The rule is therefore a latency optimization, not a neutral rewrite; for the scope of theorem R1 and a counterexample see Formal foundations and proofs.

deduplicateSubstrats

An optimization: if two queries use the same intermediate operation (e.g. core0#core1), this stage points the second query at the substrate created by the first. It avoids duplicate computation - see the example in Substrates.

validateSubstratNameUniqueness

Checks that two substrates with the same name denote the same program. Names longer than 200 bytes are shortened deterministically by composeStreamName(), so this check turns an extremely unlikely 64-bit digest collision into a loud error instead of an ambiguous plan. It runs independently of optimizer switches and after deduplication, because identical duplicate names are a normal transient state before that point.

resolveFieldReferences

Turns references to fields from source schemas into flat indices in the output schema. It handles aliases after sum - turning core0[0] into str1[0], for example - and records the source to which a bare field name was resolved. Named references written by the user are tracked separately so a later pass does not confuse them with tokens synthesized by the compiler. A bare numeric-array name is rejected: a does not mean a[0]; an element must be selected. See Aliasing.

resolveWindowAggregates

Extracts the argument program of each window aggregate - MIN, MAX, AVG or SUMC(expression : W) - in the SELECT list into query::windowGroups. It validates positive width, numeric type, one history source, at least one field read, and the bans on nesting and RULE use. Identical source–expression–width triples share a group and one history scan. The aggregate token becomes a zero-argument operand that points to the computed group result.

inferFieldShapes

The only stage that establishes the public shape of a SELECT field: its type, length, and cardinality. The shape follows from the whole field program - the pass replays the runtime arithmetic on a stack of types, including BYTE promotion, explicit conversions in the middle of an expression, the result of a record-history aggregate, and the width of STRING. The stage replaced the earlier local rules (propagateCopiedFieldShapes, inferStringFieldTypes), which settled the shape only in selected cases - see Type Promotion.

The pass runs to a fixed point because the tree is still sorted by interval and a consumer may precede its producer. It covers only nodes that copy their operand’s schema; reducers and the @ window keep the schema built by their operator, and DECLARE declarations are left untouched. The stage precedes expression simplification: after constant folding, a field’s width would depend on an optimization switch.

checkRuleConditionShapes

Applies to RULE conditions the same computability check that inferFieldShapes applies to fields. A rule condition is executed by the same expression evaluator, so without this stage an invalid condition would bypass the check and silently produce a wrong value. The pass writes nothing into the plan - it only rejects conditions that cannot be computed.

simplifyFieldExpressions

Simplifies SELECT field programs, record-history aggregate arguments, and RULE conditions after references have been resolved but before equivalent computations are shared. The pass folds constant expressions, combines safe constant tails in integer arithmetic and STRING concatenation, and removes type-compatible neutral elements (E+0, E-0, E*1, E/1). With the separate aggressive_expr_optimization=ON switch it writes a repeated exact factor as a power, for example E*E*E as E^3; this rule is disabled by default.

The pass preserves NULL semantics and type promotion. It therefore does not simplify E*0, reassociate FLOAT or DOUBLE operations, or alter programs whose type or operation cannot be established safely. Repeated-factor folding is limited to types with exact multiplication (BYTE, INTEGER, UINT, and RATIONAL); it does not replace one FLOAT or DOUBLE multiplication with a call to pow.

Constant-tail reassociation (rule B) requires exact value equality, including NULL, with optimization enabled or disabled. For an INTEGER, UINT, or BYTE base and INTEGER constants, the guard computes the intervals of base values for which the intermediate result and the rewritten result fit their representation. A rewrite is allowed only when the rewritten result’s defined domain is contained in the intermediate result’s defined domain. For BYTE the guard uses the complete INTEGER range because a compound base, such as b+b, already produces INTEGER. It therefore retains the sequential forms of (i+1)-1 at INT_MAX, i*-1*-1 at INT_MIN, and u*-2*-3 and u+5-3 over UINT, preserving intermediate overflow as NULL.

Rule B refuses reassociation for RATIONAL and other unproved promotions; constant folding and removal of type-compatible neutral elements remain available. STRING concatenation remains allowed. The it_expr_corpus-value regression covers INTEGER/UINT boundaries, BYTE promotion, RATIONAL overflow, and the u+3-5 control; it checks values and descriptors under all-off as well.

shareEquivalentSelectComputations

Detects explicit SELECT queries with equivalent field programs and FROM trees containing STREAM_ADD. It orders only the two children of an individual STREAM_ADD node without changing the grouping of the complete tree. For each equivalence class it creates one STREAM_SELECT_* substrate and retains the public queries as lightweight projections with their own names, descriptors, rules, and storage. The pass runs before field-offset localization - see Substrates.

localizeFieldOffsets

Converts field references (b[x], c[y]) into positions in the query’s flattened input record, written under the query’s own name (result[z]). For sum +, the offset follows from the number of fields in the preceding components. For interleave #, both arguments share the same positions in one schema; component identity is no longer available through its name.

A position can be determined only for streams in the FROM clause and for sources reached through compiler-generated substrates. A reference to a source of an intermediate stream that is a user query - e.g. core1[0] with FROM merged - stops compilation with Stream '…' refers to '…', which is not in its FROM clause. Such a stream has its own interval and buffer, so the position of its sources in the consumer’s input record cannot be determined.

At this stage the compiler rejects user-written A[0], A.field, A[_], A.*, and bare field names if they refer to a component reached through #. The check also covers RULE conditions and sources hidden behind automatic substrates. References through the output stream name, an unqualified *, and explicit component recovery with & or % remain legal.

computeLogicalOrigin

Computes query::logicalOrigin, the index of the first record that exists at all. The difference from the tail is qualitative: the tail says “not yet”, the origin says “this record has no definition”. The origin originates from the @(k,L) window stamped by the interval end - its early records would reach before the start of the source - from a history aggregate, which adds W-1, and from the shift >N, whose record n carries record n-N. Every other operator merely propagates the origin, through the same index mapping it reads with.

For @ and >N the form is closed; for +, #, -, Theta and ~Theta the pass searches for the smallest index reaching the component threshold, by bisection over a non-decreasing mapping. The plan listing shows origin=.

computeStartupLatency

Computes query::startupLatency, the number of initial slots of the stream’s own interval in which an existing result is not yet ready. Sources have tail 0; >N gives max(0, W_src − N), because it reads a record older than the current one; interleave includes both input tails and its own look-ahead on the second argument; sum takes the maximum of both inputs’ availability bounds. Difference and both de-interleaves use exact phase bounds - left de-interleave does not unconditionally add one slot. AGSE uses the bound from the newest field in its window, and reductions and record-history aggregates add no own tail. The plan listing shows tail= and the runtime emits no record during the tail. The number of silent slots is origin + tail.

This pass runs after computeLogicalOrigin and before capacity computation: the tail depends on which slots are records, and retained history depends on the consumer’s first emission time.

computeRequiredCapacities

Computes required buffer capacities from the distance between the producer’s head and the index read by a consumer. For a >N shift, the backward distance is W_out-W_src+N, so the base capacity is W_out-W_src+N+1. If the source is a declaration, two look-ahead records are added: the record armed when storage is opened and the zero prefetch. The result is clamped to at least one record. History capacity is an execution requirement, not a result prefix.

A record-history aggregate requires at least W consecutive records of its named source. Capacity also accounts for logical origin, tail, and interval differences like every other history read; it is not selected as a local W alone.

validateConstraints

Verifies semantic correctness of the compiled plan: type and flat-width compatibility, window sizes, source availability, and operator constraints. Interleave # requires equal flat schemas whether an input was written as T[N] or as N scalar fields.

applyCapacitiesToStreams

Applies the computed capacities to the stream objects. A MEMORY store keeps the greater of RETENTION n and the plan’s need; declared sources take their capacity from consumer needs.

For an interleave, the compiler reduces \(\Delta_a/\Delta_b=p/q\) to coprime positive \(p,q\) and scans one full phase period \(p+q\). For each slot \(i\) of that period it determines which component the interleave selects and at which index \(j(i)\), then takes the maximum of the required latency:

\[ W_{\#} =\max_{0\le i<p+q}\left( \left\lceil\frac{\bigl(j(i)+1+W_{s(i)}\bigr)\Delta_{s(i)}}{\Delta_c}\right\rceil -1-i \right) \]

The scan result is exact - it neither undershoots nor overshoots the causal bound. The arithmetic runs in 64 bits, because the product \((j+1+W)\cdot\text{numerator}\cdot\text{denominator}\) exceeds int range even for moderate intervals. Above kHashPhaseScanLimit, HashStartupLatency() (SOperations.hpp) uses a safe bound without a phase scan:

\[ W_{\#,\mathrm{fallback}} =\max\left( \left\lceil\frac{W_a\Delta_a}{\Delta_c}\right\rceil, \left\lceil\frac{W_b\Delta_b}{\Delta_c}\right\rceil +\left\lceil\frac{p+q-1}{p}\right\rceil \right) \]

The first two terms convert the input tails into output slots; a zero tail contributes zero. The term \(\lceil(p+q-1)/p\rceil\) describes only the phase and is insufficient on its own for nonzero input tails. The complete bound is conservative: it does not release a record before its dependencies are ready, but it does not promise an excess of exactly one slot. The regression ut_soperations::xSOperations.hash_startup_latency_above_scan_limit_stays_safe compares it with an independent scan, including nonzero input tails.

Regressions cover ratios including \(3/5\), \(3/2\), \(7/11\), and \(160/147\), including periodic all-NULL records in the blocked, non-rewritten left-hand side of the R1 identity; the operator formula itself is guarded by ut_h10aGate.

checkHistoryMemory

Sums the history cost of DECLARE sources and MEMORY rings after their capacities are fixed. If it exceeds [limits] history_memory_mib, it returns an error with the byte count and the stream with the largest share. File stores are excluded.

applyDiskRetention

Applies [storage] default_retention to DEFAULT and DIRECT streams without explicit retention, including substrates. For a bounded segment count, it checks that the plan’s required history fits the shortest state just after rotation: (segments - 1) * capacity + 1 records. Otherwise compilation fails with the stream, retention, and required depth. segments = 0 means unbounded history and is exempt from this check.

topologicalSort

Unconditionally restores final producer–consumer order. This is part of execution correctness, not presentation: a # result has a smaller interval than its inputs, so earlier interval sorting can place the consumer before its producers.

Plan-rewriting passes are additionally wrapped in verifyUserFieldNamesPreserved(). Optimization may change or remove internal substrates, but it cannot change field names of a public stream, because those names enter the observable .desc descriptor.

Check and rewrite stages return "OK" or an error message - in which case compilation stops. snapshotNamedSourceRefs, computeRequiredCapacities (which returns the capacity map), and topologicalSort return no result of this kind. Some plan inconsistencies, such as a reference to a nonexistent stream, stop compilation with an exception instead of a message.

Plan Size Limits

RetractorDB rejects a plan whose dimensions exceed the safe range of the parser, descriptor, or history memory. These checks run at ordinary startup, in xretractor -c, for ad-hoc queries, and during xqry --reset. In the last case, rejection of the new plan leaves the running plan unchanged. src/include/rdb/sizeLimits.hpp is the shared source of numeric limits for the RQL and DESC parsers and the compiler.

Layer 1: individual literals

A storage RETENTION capacity must be positive. In its two-part form, the segment count may be 0, meaning no limit on disk segments. A literal outside its numeric type is a parser error; exceeding one of the bounds above produces a message such as AGSE step 65537 exceeds the limit 65536. to_string(x : 0) produces to_string width 0 must be greater than zero; it does not create a zero-width field.

Layer 2: dimensions after plan expansion

The 148-stream check after expansion applies to plans with a generator and runs before copying its instances. A plan without a generator may pass that stage, but the bus slot limit is checked when the plan is registered or replaced. Record and field sizes are checked before building potentially large descriptors.

The compiler names the stream and the exceeded dimension, for example Stream 'x' reads an input record of 1048577 bytes; the limit is 1048576, Plan needs 262145 record elements; the limit is 262144 (reached at stream 'x'), Stream 'x' has a logical origin of ... slots; the limit is 2147483647, or the corresponding startup latency message.

RAM history budget

[limits] history_memory_mib in retractor.toml sets the plan’s combined history budget, defaulting to 1024 MiB. For each DECLARE source and each MEMORY store, the compiler sums the number of retained records multiplied by record size plus rdb::payload overhead. A source’s capacity follows consumer needs; a MEMORY ring uses the greater of RETENTION n and the plan’s need. File-store history does not count toward this budget.

Exceeding the budget fails compilation with Plan keeps ... bytes of stream history in memory; the budget [limits] history_memory_mib = ... allows ..., which also identifies the stream with the largest share. The setting must be positive; 0 or a negative number logs a warning and restores the 1024 MiB default. This budget is not a process-wide memory limit or an IPC queue limit. See xretractor configuration and Storage Types.

Dependency Tree Construction

The dependency tree is the query execution plan in the form of a directed graph. It is a data structure built during compilation and modified when Ad Hoc queries are added. The roots of this graph are ephemeris declarations - declarations of every kind that create external objects, so-called data sources. Inside the graph lie artifacts and substrates. At the end of the processing chain sit the artifacts - as the chain’s final results.

Such a construction is a directed graph - a graph with multiple roots and multiple terminal vertices. Inside the graph there are connecting nodes. Every node lies on a path from a root to a terminal vertex. This is best visualized with an example.

Let’s start by considering the following trivial query:

DECLARE a UINT STREAM core0, 0.1 TEXTFILE 'datafile1.txt'
SELECT str1[0] STREAM str1 FROM core0

We can obtain a graph highlighting the dependencies between the individual objects as follows (Fig. 33):

$ xretractor -c query5.rql -d > out.dot && dot -Tsvg out.dot -o out.svg

For a full description of the -d -f -s flags and how to interpret the output - see Compilation Debugging.

Let’s make this graph a bit more complex by adding two ephemeris declarations and an additional artifact.

DECLARE a UINT STREAM core0, 0.1 TEXTFILE 'datafile1.txt'
DECLARE a UINT STREAM core1, 0.1 TEXTFILE 'datafile2.txt'
SELECT str1[0] STREAM str1 FROM core0
SELECT str2[0] STREAM str2 FROM core0 + core1

The dependency graph for the set of queries above looks as follows (Fig. 34):

Let’s build an additional node that depends on artifacts. The simplest way is to add the following query at the end:

SELECT str3[0] STREAM str3 FROM str1#str2

The graph changes shape:

As shown in Fig. 35, the str3 stream is not directly dependent on the data supplied by the core0 and core1 streams. Queries form a dependency graph, and the order in which they are invoked is well-defined. The interval value of streams grows toward the roots. This growth toward the roots follows from the interval-determination equations of the developed algebra.

Note that queries in the rql file are processed sequentially. Attempting to reference, in a query, an object that is not yet defined results in a compilation error.

Attaching the following query to the dependency tree produces an additional substrate.

SELECT str4[0] STREAM str4 FROM (core1+core0)>2

A query attached this way will modify the dependency tree as shown in Fig. 36.

The substrate is marked with a different color and an “Auto” label next to the time interval.

The dependency graph must be a directed acyclic graph (DAG). Attempting to define a stream that refers to its own results creates a cycle and results in a compilation error. The detection mechanism is described in the chapter Loop Detection in Compilation.

NOTE: The functionality described here is covered by the test: subquery, described in the appendix Integration Tests.

Substrates

I mentioned substrates, ephemerides, and artifacts in the chapter on system architecture. Here I’ll present an example.

First I’d like to draw attention to a certain property of the algebraic expressions introduced. In practice we can write any expression, compile it, and produce a formula for operations on individual elements of the time series that yields the desired result.

In practice, the system carries out only one- or two-argument operations. Examples of one-argument operations are the time shift or the Agse operation - there, the argument is a single data stream. The rest of the operations act on two data streams. During compilation, all algebraic expressions are broken down into ones with two arguments.

The parser accepts both the parenthesized form and unparenthesized chains, e.g. s1+s2+s3, s1#s2#s3, and s1+s2+s3+s4. Such notation is then reduced to a sequence of two-argument operations with automatic intermediate substrates.

The example uses the canonical declarations from the whole chapter - three streams with different types and intervals:

DECLARE a BYTE, b INTEGER STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'
DECLARE e INTEGER STREAM core2, 0.3 TEXTFILE 'sensor_c.txt'

SELECT merged[0] STREAM merged FROM (core0 # core1) + core2

Compilation:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
STREAM_HASH_core0_core1(1/15)	tail=2
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_HASH
	a: INTEGER
		PUSH_ID(STREAM_HASH_core0_core1[0])
	b: FLOAT
		PUSH_ID(STREAM_HASH_core0_core1[1])
core2(3/10)	sensor_c.txt
	e: INTEGER
merged(1/15)	tail=4
	:- PUSH_STREAM(STREAM_HASH_core0_core1)
	:- PUSH_STREAM(core2)
	:- STREAM_ADD
	merged_0: INTEGER
		PUSH_ID(merged[0])

An unannounced stream, STREAM_HASH_core0_core1, appeared - this is exactly a substrate. The compiler broke (core0 # core1) + core2 into two two-argument operations and inserted an intermediate stream. The substrate’s delta: Δ = (1/10 · 1/5) / (1/10 + 1/5) = 1/15.

What happens once we attach the query:

SELECT merged2[0] STREAM merged2 FROM (core0 # core1) > 2

Only one new query gets attached to the plan:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
STREAM_HASH_core0_core1(1/15)	tail=2
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_HASH
	a: INTEGER
		PUSH_ID(STREAM_HASH_core0_core1[0])
	b: FLOAT
		PUSH_ID(STREAM_HASH_core0_core1[1])
core2(3/10)	sensor_c.txt
	e: INTEGER
merged(1/15)	tail=4
	:- PUSH_STREAM(STREAM_HASH_core0_core1)
	:- PUSH_STREAM(core2)
	:- STREAM_ADD
	merged_0: INTEGER
		PUSH_ID(merged[0])
merged2(1/15)	origin=2
	:- PUSH_STREAM(STREAM_HASH_core0_core1)
	:- STREAM_TIMEMOVE(2)
	merged2_0: INTEGER
		PUSH_ID(merged2[0])

You’re probably wondering why only one, and not two again? The answer is optimization. We’re reusing the intermediate results from before. This is one of the unexpected benefits of using RetractorDB.

There’s one more important thing worth mentioning here. There is a SUBSTRAT directive, whose argument is a string in quotes. You can use the following types: ‘memory’, ‘default’, ‘direct’, ‘posix’, ‘posixshd’, ‘generic’, ‘device’, ‘textsource’. A full description of each type can be found in the chapter Storage Types. The default type, ‘default’, causes substrates to materialize entirely on disk. That’s not the desired behavior in a production system, but it is desired during development and debugging. A useful type is ‘memory’. Substrates of this type live only in memory. Their data never lands on disk - everything happens in memory, and there’s only as much data as is needed to execute the queries. The remaining types are currently untested and in development.

Adding a query with the same operations but a different name can trigger substrate deduplication. If the program, delta, and schema are equivalent, the compiler redirects the PUSH_STREAM references to the existing stream and removes the duplicate.

NOTE: The functionality described here is covered by the tests: issue96_no_substrat_reduction, issue96_substrat_reference, described in the appendix Integration Tests.

Substrate reduction

The compiler carries out an optimization called substrate reduction (the deduplicateSubstrats function). It works as follows: if the user has defined a query structurally identical to a generated substrate, the substrate is removed from the plan and its references are replaced with the user query’s name.

Conditions for reduction

Reduction of a substrate into a user query happens if and only if three conditions are simultaneously satisfied:

1. The same schema shape - the field count, types, byte sizes, and cardinalities are identical. Field names are not compared.
2. The same delta - the streams’ sampling rate is the same.
3. The same processing operations - the sequence of PUSH_STREAM / STREAM_TIMEMOVE / STREAM_HASH, etc. instructions is identical.

Reduction example

Consider a query with the canonical declarations:

DECLARE a BYTE, b INTEGER   STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT  STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'

SELECT merged[0]  STREAM merged  FROM (core0 > 2) + core1
SELECT shifted[0] STREAM shifted FROM core0 > 2

Without reduction, the compiler would generate three streams: the substrate STREAM_TIMEMOVE_core0, merged, and shifted. The substrate and shifted have an identical structure - the same source stream core0 and the same >2 operation. After reduction, the substrate is removed, and the reference PUSH_STREAM(STREAM_TIMEMOVE_core0) inside merged is replaced with PUSH_STREAM(shifted):

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
STREAM_TIMEMOVE_2_core0(1/10)	origin=2
	:- PUSH_STREAM(core0)
	:- STREAM_TIMEMOVE(2)
	a: BYTE
		PUSH_ID(STREAM_TIMEMOVE_2_core0[0])
	b: INTEGER
		PUSH_ID(STREAM_TIMEMOVE_2_core0[1])
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
merged(1/10)	tail=1	origin=2
	:- PUSH_STREAM(STREAM_TIMEMOVE_2_core0)
	:- PUSH_STREAM(core1)
	:- STREAM_ADD
	merged_0: BYTE
		PUSH_ID(merged[0])
shifted(1/10)	origin=2
	:- PUSH_STREAM(core0)
	:- STREAM_TIMEMOVE(2)
	shifted_0: BYTE
		PUSH_ID(shifted[0])

An important restriction: only substrates are reduced

Reduction applies exclusively to substrates generated by the compiler (isSubstrat = true). Queries explicitly defined by the user are never reduced, even if two of them have an identical structure.

Example - two user queries with the same operation:

DECLARE a BYTE, b INTEGER   STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'

SELECT shifted1[0] STREAM shifted1 FROM core0 > 2
SELECT shifted2[0] STREAM shifted2 FROM core0 > 2

The compilation result keeps both streams, with no reduction at all:

shifted1(1/10)
        :- PUSH_STREAM(core0)
        :- STREAM_TIMEMOVE(2)
        shifted1_0: BYTE
                PUSH_ID(shifted1[0])
shifted2(1/10)
        :- PUSH_STREAM(core0)
        :- STREAM_TIMEMOVE(2)
        shifted2_0: BYTE
                PUSH_ID(shifted2[0])
core0(1/10)     sensor_a.txt
        a: BYTE
        b: INTEGER

This semantic decision is deliberate: the user declared two separate output streams, and both are entitled to exist independently in the execution plan. The deduplicateSubstrats() pass removes neither of them. The compiler may, however, share their internal computation while retaining both public streams, as described in the next section.

Sharing equivalent SELECT computations

The shareEquivalentSelectComputations() pass detects explicit SELECT queries that execute the same field program over equivalent FROM trees containing STREAM_ADD. Instead of executing the expensive program separately for each query, the compiler creates one STREAM_SELECT_* substrate. The public streams remain in the plan as lightweight projections of that substrate.

Example:

SELECT a[_] * b[_] STREAM c1 FROM a+b
SELECT a[_] * b[_] STREAM c2 FROM b+a

After field references are resolved, both field programs read the same values from a and b, even though the stream + operator builds its input in a different order. The plan contains one shared computation, for example STREAM_SELECT_c1, and two public streams, c1 and c2, that read its fields.

Equivalence conditions

Two queries may share a computation only when:

1. they have the same result interval;
2. they have the same number and order of result fields;
3. corresponding fields have the same type, size, and cardinality;
4. after field references and [_] are expanded, the field programs read the same source fields and execute the same operations in the same order;
5. the FROM trees are equivalent while preserving their grouping.

The tree fingerprint canonically orders the two children of each individual STREAM_ADD node, so a+b may be equivalent to b+a. It does not flatten the tree or assume associativity. This matters for three sources with different intervals:

SELECT p[_] * q[_] + r[_] STREAM x1 FROM (p+q)+r
SELECT p[_] * q[_] + r[_] STREAM x2 FROM (q+p)+r
SELECT p[_] * q[_] + r[_] STREAM x3 FROM (r+q)+p

Queries x1 and x2 may share their computation because they swap only the children of the same inner node. Query x3 has different grouping and a different intermediate substrate; its execution cadence may differ, so it remains independent.

Input order is also observable through a full scan and through projection order. The following pairs must not be merged:

SELECT *          STREAM d1 FROM a+b
SELECT *          STREAM d2 FROM b+a
SELECT a[0], b[1] STREAM n1 FROM a+b
SELECT b[1], a[0] STREAM n2 FROM b+a

Preserving the public contract

The optimization shares only the internal computation. Every explicit stream retains its own name, schema and descriptor, rules, retention, storage policy, and artifacts. Automatically generated field names may therefore still differ between c1 and c2, even when their data is identical. This is not a full alias: no public stream disappears from the plan, IPC, or storage.

After creating the common STREAM_SELECT_*, the compiler removes orphaned substrates to a fixed point. During ad hoc import, analysis is restricted to new identifiers so recompilation cannot rewrite streams that have already been instantiated in the live plan.

The pass runs after resolveFieldReferences() and expandIndexWildcards(), but before localizeFieldOffsets(). This lets a field fingerprint compare the source identity and index instead of a local offset that depends on whether the input order is a+b or b+a.

The select_cse_commutative_add test checks both plan shape and execution. It covers equivalent indexed projections and explicit field lists, NULL values and their metadata, separate public descriptors, SELECT *, changed field order, and positive and negative three-source cases. The test compares equivalent pairs byte for byte and confirms that the counterexamples produce different results - see Integration Tests.

Elimination of duplicate substrates

When several queries use the same stream operation - e.g. core0 + core1 - the substrate-extraction phase (extractIntermediateStreams) creates a separate substrate for each of them. Without a subsequent repair phase, the graph would end up with parallel, identical intermediate nodes computing exactly the same value.

When a substrate is created

A substrate is generated for every query whose program contains more than one stream operator. This applies to the operators: STREAM_ADD, STREAM_SUBTRACT, STREAM_HASH, STREAM_DEHASH_DIV, STREAM_DEHASH_MOD, STREAM_TIMEMOVE, STREAM_AGSE. The condition is checked by the query::isReductionRequired() function.

The newly created substrate is given a name built from the operation symbol, its parameter, and the operand names, for example STREAM_ADD_core1_core0, STREAM_TIMEMOVE_2_core0, or STREAM_AGSE_1_10_core0 (the composeStreamName function in compiler.cpp). A parameter is part of node identity: two different windows over one source must not receive the same name. Characters unavailable in identifiers are encoded; a negative number uses N, for example, and a fraction slash becomes _.

A readable name grows with the complexity of the FROM clause and is also the substrate’s file name. Above 200 bytes the compiler keeps the operation name and replaces the remainder with a stable 16-digit FNV-1a digest, for example STREAM_ADD_x92741c15f69ba93f. This lets a wide expression stay below the system NAME_MAX; the same plan structure always receives the same name, while a different operand order receives a different digest. validateSubstratNameUniqueness() stops compilation if one digest were ever to denote two different programs.

In the parent query’s program, the operator token is replaced with a PUSH_STREAM token pointing at this substrate.

Matched interleave-shift factorization

After extracting substrates and resolving their intervals, the compiler applies the algebraic rewrite:

\[ (A > i) \mathbin{\#} (B > k) \longrightarrow (A \mathbin{\#} B) > (i+k), \qquad i\Delta_{a}=k\Delta_{b} \]

The condition \(i\Delta_{a}=k\Delta_{b}\) means that both interleave arguments are shifted by the same physical time. Without this condition the transformation is not equivalent, so the compiler keeps the original plan.

Let the reduced ratio \(\Delta_a/\Delta_b\) be \(p/q\). The interleave tail protects every phase of the period \(p+q\), because the compiler scans that period slot by slot and takes the maximum required latency - formula and justification in Formal Foundations and Proofs.

A shift delays a causal realization: it moves the logical origin O by N and sets its own tail to \(\max(0,W_S-N)\) - it does not change the record sequence or insert a prefix. For \(\Delta_c=\Delta_a\Delta_b/(\Delta_a+\Delta_b)\), the matching condition gives exactly:

\[ \frac{i\Delta_a}{\Delta_c} =\frac{k\Delta_b}{\Delta_c} =i+k \]

Shifting each input therefore corresponds to the same number i+k of output slots, and the logical origin of both sides is identical. The tails are not identical. The factored side reads content directly from the interleave, while the unfactored side reads it only after shifting its components, so it waits longer:

\[ W_{\mathrm{RHS}}=\max\left(0,;W_{\varphi(A,B)}-(i+k)\right)\le W_{\mathrm{LHS}} \]

The rule thus preserves the emitted sequence, the interval and origin=, and may decrease tail=. It is a latency optimization, not a neutral rewrite; for the full proof and a counterexample see Formal foundations and proofs.

Before optimization the plan contains two substrates:

STREAM_TIMEMOVE_i_A = A > i
STREAM_TIMEMOVE_k_B = B > k
result = STREAM_TIMEMOVE_i_A # STREAM_TIMEMOVE_k_B

After optimization only one remains:

STREAM_HASH_A_B = A # B
result = STREAM_HASH_A_B > (i + k)

The factorMatchedHashTimeMoves() pass does not remove explicit user streams or substrates used by other consumers. It runs before deduplication so that the exposed A # B substrate can subsequently be shared with another equivalent plan.

The issue202_hash_shift_e2e test executes both sides of the identity over independent copies of file-backed input streams. It compares the matched and CC artifacts byte for byte, compares their metadata after excluding the reserved header, checks the complete sequence against a reference derived from the B,A,A interleave period, and verifies equal tails (origin=3 with a zero tail - \(\tau_3\) over an interleave of tail 2 absorbs it entirely). Both sides are factored to the same shape here, so the comparison is exhaustive. Neither side emits placeholder records. Separately, computeRequiredCapacities() assigns N+1+2 history records to a declared source: N+1 for the read range itself and two for the declaration’s head lead, which logical-index addressing does not shorten.

The r1_identity_nulls test checks the same identity for \(\Delta_a/\Delta_b=3/2\), which requires the phase maximum \(H_{a,b}=2\) even though the first phase requires only one slot. It compares the rewritten plan, a left-hand side blocked from rewriting, and an explicit right-hand side. The rewritten plan and the explicit right-hand side are equal in full. The blocked left-hand side has the same logical origin and the same content but a strictly larger tail - the comparison therefore covers the common prefix of the payload and of the NULL map, with a separate assertion requiring the factored side to be strictly longer. A nonempty periodic all-NULL record prevents missing data from masking an incorrect tail. Compiler unit tests also cover the \(3/5\), \(7/11\), and \(160/147\) ratios.

The deduplication algorithm

After extracting substrates and determining time intervals, the compiler runs the deduplicateSubstrats() step. The algorithm works iteratively - a while(changed) loop repeats the search until no more duplicate pairs are found.

On every pass, for each pair of substrates (it, it2), five equivalence conditions are checked in turn:

1. Time interval – it->rInterval == it2->rInterval
2. Program length – the number of tokens in lProgram must be identical
3. Schema length – the number of fields in lSchema must be identical
4. Program content – every token is compared by instruction type (getCommandID()) and parameter value (getVT())
5. Schema content – every field is compared by type (rtype), size in bytes (rlen), and cardinality (rarray)

If all conditions hold, substrate it is considered a duplicate of substrate it2. The compiler walks through the entire coreInstance and, in every PUSH_STREAM token referring to the old name (it->id), substitutes the new name (it2->id). The duplicate is then removed from the query list (coreInstance.erase(it)), and the loop starts over.

Position in the compilation pipeline

Deduplication is the ninth of the twenty-three pipeline stages (the compiler::compile() function):

Matched interleave-shift factorization and deduplication must happen after interval resolution because both operations compare intervals. Deduplication follows the algebraic rewrite so that it can merge interleave substrates exposed by that rewrite.

SELECT computation sharing runs only after field references and [_] have been expanded because it compares completed field programs. It must still precede field-offset localization so equivalent sources do not look different merely because of their order in the local input buffer.

Every rewriting pass (factorMatchedHashTimeMoves, deduplicateSubstrats, and shareEquivalentSelectComputations) is wrapped in verifyUserFieldNamesPreserved(). Field names of public streams are part of the .desc descriptor and must not change because of optimization. The tail is computed only for the final plan. The final topological sort is unconditional because earlier interval sorting can place a faster # consumer before its producers.

Effect on the dependency graph

Consider the queries:

DECLARE a UINT STREAM core0, 0.1 TEXTFILE 'datafile1.txt'
DECLARE a UINT STREAM core1, 0.1 TEXTFILE 'datafile2.txt'
SELECT str4[0] STREAM str4 FROM (core0+core1)>2
SELECT str5[0] STREAM str5 FROM (core0+core1)>3

Both queries require the sum core0+core1 to be computed first.

The extractIntermediateStreams phase creates a separate substrate for each query, producing two identical intermediate nodes in the graph (Fig. 37):

Once deduplicateSubstrats() runs, one of the duplicates is removed and every PUSH_STREAM reference is repointed to the surviving node. A single shared substrate remains in the graph (Fig. 38):

The graph after deduplication is exactly what xretractor -c -d returns - the compiler always presents the result after all optimization phases.

Absorption of a substrate by an explicit stream

The inner loop in deduplicateSubstrats() does not check the isSubstrat flag for candidate it2 - that check exists only in the outer loop. This means an automatic substrate can be absorbed not only by another substrate, but by any stream with an identical program and schema - including a stream explicitly defined by the user.

Consider a query containing only a compound expression:

DECLARE a UINT STREAM core0, 0.1 TEXTFILE 'datafile1.txt'
DECLARE a UINT STREAM core1, 0.1 TEXTFILE 'datafile2.txt'
SELECT str4[0] STREAM str4 FROM (core0+core1)>2

Here, extractIntermediateStreams extracts a substrate STREAM_ADD_core0_core1 for the expression core0+core1. Artifact str4 depends on it (Fig. 39):

When the user adds an explicit stream declaration that is exactly the same sum:

SELECT * STREAM mysum FROM core0+core1

the substrate STREAM_ADD_core0_core1 satisfies every equivalence condition relative to mysum - identical interval, identical token program, identical field schema. The deduplicateSubstrats() phase removes the substrate and repoints every PUSH_STREAM reference to mysum. The substrate disappears from the graph entirely (Fig. 40):

A side effect: mysum becomes a shared node - it serves both its own consumers and those that previously used the automatic substrate. In exchange, the user gains an explicit name for the intermediate results and can query them via xqry.

Schema update after absorption

Simply repointing the PUSH_STREAM tokens is not enough. Every stream stores, in lSchema, a sequence of instructions describing how to build the output value of every field - including PUSH_ID(stream_name, N) tokens, which say: “take the N-th field from the input buffer named stream_name.” When a substrate is absorbed, these tokens still refer to the old, removed substrate name. The localizeFieldOffsets() step builds an offset map from the sources of the FROM clause - the PUSH_STREAM tokens in the program and the sources hidden behind compiler substrates - and uses it to turn every PUSH_ID(source, N) into a position in the stream’s own input buffer. A name missing from the map stops compilation with a fatal error, because its position cannot be determined.

Error scenario with a non-zero offset

Consider the query:

DECLARE a INTEGER STREAM s1, 1 BINFILE 'data1.dat'
DECLARE b INTEGER STREAM s2, 1 BINFILE 'data2.dat'
DECLARE c INTEGER STREAM s3, 1 BINFILE 'data3.dat'

SELECT * STREAM mysum  FROM s1+s2
SELECT * STREAM merged FROM s3+(s1+s2)

The compiler creates a substrate STREAM_ADD_s1_s2. Stream merged has two sources: s3 (offset 0) and the substrate STREAM_ADD_s1_s2 (offset 1, because s3 occupies position 0). For the fields that come from the substrate, the buildOutputSchema function writes the following tokens into merged.lSchema:

PUSH_ID(STREAM_ADD_s1_s2, 0)   ← field STREAM_ADD_s1_s2_1 (a from s1)
PUSH_ID(STREAM_ADD_s1_s2, 1)   ← field STREAM_ADD_s1_s2_2 (b from s2)

After absorption, deduplicateSubstrats() repoints PUSH_STREAM from STREAM_ADD_s1_s2 to mysum. Without updating lSchema, however, the PUSH_ID tokens would still carry the old name, which localizeFieldOffsets() cannot find in the offset map. Today this ends compilation with a fatal error. Until 2026-09-14 a missing key silently got offset 0, which is s3’s position - the fields from mysum were then read from offset 0 instead of offset 1, and the compiler gave no warning.

The fix: updating lSchema in deduplicateSubstrats

To avoid this discrepancy, after updating the PUSH_STREAM tokens, deduplicateSubstrats() performs an additional pass over the lSchema of every query and rewrites:

• PUSH_ID(old_name, N) tokens into PUSH_ID(new_name, N) - this covers the fields from buildOutputSchema for STREAM_ADD,
• PUSH_ID2("old_name[N]") tokens into PUSH_ID2("new_name[N]") - this covers the symbolic names created by buildOutputSchema for STREAM_TIMEMOVE, STREAM_HASH, STREAM_SUBTRACT.

After the fix, the compiler’s output (xretractor -c) for stream merged from the example above looks correct:

merged(1/1)
        :- PUSH_STREAM(s3)
        :- PUSH_STREAM(mysum)
        :- STREAM_ADD
        s3_0: INTEGER
                PUSH_ID(merged[0])
        STREAM_ADD_s1_s2_1: INTEGER
                PUSH_ID(merged[1])
        STREAM_ADD_s1_s2_2: INTEGER
                PUSH_ID(merged[2])

The fields that come from mysum start at offset 1 (merged[1], merged[2]), which matches mysum’s actual position in merged’s buffer - after field s3_0 from stream s3 at position 0. The fields keep the name of the absorbed substrate: the field names of user streams go into the .desc descriptor, so they are fixed before the optimizations, and the verifyUserFieldNamesPreserved() check makes sure deduplication does not change them.

Cascaded absorption

NOTE: The functionality described here is covered by the tests: issue167_dedup_cascaded, issue167_dedup_field_names, issue167_dedup_nonzero_offset, issue167_dedup_positive, issue167_triarg, described in the appendix Integration Tests.

deduplicateSubstrats() runs iteratively (while(changed)), which allows for multi-step absorption. In the example:

SELECT * STREAM mysum   FROM s1+s2
SELECT * STREAM shifted FROM (s1+s2)>1
SELECT * STREAM merged  FROM s3+((s1+s2)>1)

in the first round, mysum absorbs STREAM_ADD_s1_s2 and rewrites its names - including in the schema of the intermediate substrate STREAM_TIMEMOVE_1_STREAM_ADD_s1_s2. As a result, in the second round shifted can absorb this substrate (the program condition is now satisfied, because both point to mysum). After two rounds, no automatic substrate remains in the plan, and merged uses s3 and shifted directly.

Asterisk Expansion

Everyone who has written SQL knows the magic * character in that language. Invoking a SELECT command with this argument expands the argument list based on the schemas of the tables produced by relational joins. I wanted to achieve something similar in RQL.

The example uses the canonical declarations used throughout the chapter:

DECLARE a BYTE, b INTEGER STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'

SELECT *         STREAM merged FROM core0 + core1
SELECT merged[2] STREAM result FROM merged

Let’s compile it and see the effect:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
merged(1/10)	tail=1
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_ADD
	core0_0: BYTE
		PUSH_ID(merged[0])
	core0_1: INTEGER
		PUSH_ID(merged[1])
	core1_2: INTEGER
		PUSH_ID(merged[2])
	core1_3: FLOAT
		PUSH_ID(merged[3])
result(1/10)	tail=1
	:- PUSH_STREAM(merged)
	result_0: INTEGER
		PUSH_ID(result[2])

The * symbol turned into four fields: core0_0, core0_1, core1_2, core1_3. Naming convention: source stream name + absolute position in the output schema. Field types determine the order - core0 contributes BYTE and INTEGER at positions 0 and 1, core1 contributes INTEGER and FLOAT at positions 2 and 3. Referring to merged[2] in the result query gets us a field of type INTEGER - third in order, the first field from core1.

NOTE: The functionality described here is covered by the test: Pattern3, described in the appendix Integration Tests.

Interval Resolution

Every stream in RetractorDB has an assigned time interval - delta (Δ). The interval determines how often new values are produced. For declared streams (DECLARE), the interval is given by the user. For output streams (SELECT), the interval is determined by the compiler from the stream-algebra equations.

The examples in this chapter use the canonical declarations from the whole chapter: core0 (Δ=1/10), core1 (Δ=1/5), core2 (Δ=3/10).

Algorithm

The resolveStreamIntervals stage works iteratively:

prevUnresolved = ∞
loop:
    unresolvedCount = 0
    sort qTree topologically
    for every query:
        if the source streams' deltas are known:
            determine the output delta from the operator's equation
        otherwise:
            unresolvedCount++
    if unresolvedCount == 0: done (success)
    if unresolvedCount >= prevUnresolved: error (loop in the graph)
    prevUnresolved = unresolvedCount

Every round resolves at least one stream - because the graph is acyclic, and the topological sort guarantees sources are processed before outputs. If the number of unresolved streams stops decreasing, that indicates a cycle - see Loop Detection.

Operator equations

Stream sum (+, STREAM_ADD)

SELECT ... STREAM c FROM a + b

\[\Delta_c = \min(\Delta_a, \Delta_b)\]

The output stream produces values as often as the faster of the input streams.

Example: core0(Δ=1/10) + core1(Δ=1/5) → str1(Δ=1/10)

Stream synchronization (#, STREAM_HASH)

SELECT ... STREAM c FROM a # b

\[\Delta_c = \frac{\Delta_a \cdot \Delta_b}{\Delta_a + \Delta_b}\]

The result corresponds to the harmonic mean of the intervals - the stream only produces a value when both inputs are available at the same time.

Example: core0(Δ=1/10) # core1(Δ=1/5) → str1(Δ=1/15)

Time shift (>n, STREAM_TIMEMOVE)

SELECT ... STREAM c FROM a > n

\[\Delta_c = \Delta_a\]

A shift changes neither the stream’s rate nor its emitted record sequence, but it does change the index at which that sequence appears: record m carries the content of record m-n. It is a causal delay, but its carrier is the logical origin, not the tail - records with an index below n have no definition. The operator’s own tail is non-positive: it equals max(0, W_src − n), because record m-n is older than the current one and therefore all the more available. The plan listing shows both quantities as origin= and tail=; the silent slots are their sum and the runtime emits nothing in them.

Source history requires n+1 records for the read range itself, plus two more for a declared source’s head lead (the record armed when the storage is opened and the zero prefetch), which logical-index addressing does not shorten.

Stream reducers (MAX, MIN, AVG, SUMC)

\[\Delta_c = \Delta_a\]

Reducers operate on a complete stream expression, e.g. AVG(a@(1,10)). They reduce values within a record or a window, but the output stream’s interval stays the same as the source’s. The postfix forms .max, .min, .avg, and .sumc remain backward compatible but are deprecated.

The AGSE algorithm (@(step, window), STREAM_AGSE)

SELECT ... STREAM c FROM a @ (step, window)

\[\Delta_c = \frac{\Delta_a \cdot \text{step}}{\text{windowSize}}\]

AGSE (the Episode Series Generation Algorithm) generates sliding windows. The output interval depends on the step and the window size relative to the source.

De-hash operators (STREAM_DEHASH_DIV, STREAM_DEHASH_MOD)

The inverse operations of # - they determine what interval one of the input streams had, given the result’s interval and the other argument:

\[\Delta_a = \frac{\Delta_c \cdot \Delta_b}{\left|\Delta_c - \Delta_b\right|}\]

Why iteration?

In a query with multiple output streams, one stream may depend on another:

DECLARE a INTEGER STREAM core0, 0.1 BINFILE 'data.dat'
SELECT str1[0] STREAM str1 FROM core0
SELECT str2[0] STREAM str2 FROM str1

In the first iteration round, the compiler determines Δ_str1 = 1/10 (because Δ_core0 is known). In the second round - Δ_str2 = 1/10 (because Δ_str1 is now known). Without iteration, str2 would have to be declared before str1, which would limit the language’s expressiveness.

Loop Detection in Compilation

The query dependency graph must be a directed acyclic graph (DAG). If a query refers - directly or indirectly - to its own results, a cycle is created. The compiler detects this situation and aborts compilation with an error.

NOTE: The functionality described here is covered by the test: issue95_loopInCompile, described in the appendix Integration Tests.

Example of a loop

DECLARE a BYTE, b INTEGER STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'

SELECT merged[0]*10, merged[2]+10 STREAM merged FROM core0 + core1
SELECT *                          STREAM agg    FROM MAX(merged)
SELECT *                          STREAM broken FROM merged + broken

The last query defines broken as the result of the operation merged + broken - the stream depends on itself. The dependency graph contains a cycle (Fig. 41):

%% pdf-width: 85%
graph LR
    core0 --> merged
    core1 --> merged
    merged --> agg
    merged --> broken
    broken -->|cycle| broken
    style broken fill:#f66,color:#fff

Fig. 41. A cycle in the query dependency graph

Compilation result

Attempting to compile such a file ends with an error:

$ xretractor brokenQuery.rql -c 2>out.txt
$ echo $?
1
$ cat out.txt
[error] Circular dependency: stream interval resolution stalled with 1 
>> unresolved streams

The message "Circular dependency in stream definitions" appears when the resolveStreamIntervals stage detects that the number of unresolved streams has stopped decreasing. For how to run compilation and read error messages, see Compilation Debugging.

Detection mechanism

On every iteration round, the resolveStreamIntervals stage counts the streams for which an interval could not yet be determined (unresolvedCount). In a valid, acyclic graph, this number decreases every round - at least one stream always gets its delta determined. In a graph with a cycle, streams depend on each other mutually and none can obtain a value - unresolvedCount stalls.

if (unresolvedCount >= prevUnresolved) {
    SPDLOG_ERROR("Circular dependency: stream interval resolution stalled with
>> {} unresolved streams",
                 unresolvedCount);
    return std::string("Circular dependency in stream definitions");
}
prevUnresolved = unresolvedCount;

The >= condition (rather than >) guards against false positives: if the count doesn’t decrease by even one, progress is impossible.

How to fix it

Remove the stream’s reference to itself, or to a stream that depends on it. In the example above, the query:

SELECT * STREAM broken FROM merged + broken

should be replaced with a reference to a stream that exists independently of broken:

SELECT * STREAM broken FROM merged + core0

Aliasing

When we join two data streams with the sum operator, a new data schema appears. We can refer to the successive values of this schema through the name of the data stream, indexed sequentially from the start of the schema.

We can, however, also use the names the stream was built from. A value can be pointed to both by the output stream’s name, indexed from the start of the schema, and by the source stream’s name, shifted relative to its join position.

The example uses the canonical declarations used throughout the chapter:

DECLARE a BYTE, b INTEGER STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'

SELECT merged[0], merged[2], core0[0], core1[0] \
STREAM merged \
FROM core0 + core1

After compilation we get:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
merged(1/10)	tail=1
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_ADD
	merged_0: BYTE
		PUSH_ID(merged[0])
	merged_1: INTEGER
		PUSH_ID(merged[2])
	merged_2: BYTE
		PUSH_ID(merged[0])
	merged_3: INTEGER
		PUSH_ID(merged[2])

merged[0] and core0[0] both end up as PUSH_ID(merged[0]) - they are the same field. But core1[0] - the first field of core1’s schema - ends up as PUSH_ID(merged[2]), not merged[0]. The compiler translated the local index core1[0] into an absolute position in the combined schema: core0 occupies positions 0 and 1, so core1 starts at position 2.

A reference outside the FROM clause

A source alias works only when the sum stands directly in the query’s FROM clause. If the sum has been named by a separate query, the consumer’s field list sees only that named stream:

SELECT *                   STREAM merged FROM core0 + core1
SELECT merged[0], core1[0] STREAM result FROM merged

Compilation ends with the error:

Check result:Stream 'result' refers to 'core1', which is not in its FROM clause. A field list reads only the streams named in FROM: refer to the field by its position in the record of a stream in FROM, or move the reference to a query whose FROM names 'core1'.

merged is a user query with its own interval and buffer, so the compiler does not determine the position of its sources in the result record. The correct form addresses the field by its position in the merged record - core1 starts there at position 2:

SELECT merged[0], merged[2] STREAM result FROM merged

The restriction does not apply to substrates created automatically for a compound FROM clause, e.g. FROM (core0 + core1) > 1: source aliases still work through them.

Index out of range

The index in stream[k] must point to a slot the query actually reads. The compiler rejects an index outside that range instead of producing a plan that reads past the end of the input record. The bound depends on what the name refers to:

Windows and reducers change the slot count: core0@(1,3) contributes three slots although core0 has two fields, and SUMC(acc) contributes one. The same count drives the expansion of core0[_], so a hand-written index and the _ form share one range.

Example messages:

Check result:Stream 'merged': stream 'core1' has 2 element(s)
  in its FROM clause, so 'core1[2]' is out of range
Check result:Stream 'merged': the FROM record of 'merged'
  has 4 element(s), so 'merged[4]' is out of range
Check result:Stream 'merged': rule 'alarm' reads the record of 'merged',
  which has 4 element(s), so 'merged[4]' is out of range

An index folded from $ in a stream generator goes through the same check and produces the same message as a hand-written index.

Aliasing after sum and interleave

The source aliases described above apply to the stream sum operator +. Sum concatenates schemas, so it preserves the position and identity of every component: core0[0] and core1[0] point to different locations in the output record.

The interleave operator # behaves differently. Its two arguments must have schemas of equal cardinality, and the result has one shared schema. In each slot the interleave selects a record from one component, so position k of the left and right arguments becomes the same position k of the result. After A#B, the name A or B can no longer identify the source of the current record.

Comparing compilation for the core0 and core1 declarations above shows the difference without executing the query:

The second row corresponds to this query:

SELECT core0[0], core1[0] STREAM interleaved FROM core0#core1

The compiler stops with a message that core0 is an interleave component and that this reference cannot be distinguished from a reference to the other component. It does not create a plan that silently maps both fields to interleaved[0].

The compiler therefore rejects user-written named references that try to reach an interleave component through #. The restriction covers every form:

• numeric index: A[0];
• field name: A.field, and a bare field name resolved to A;
• index wildcard: A[_];
• qualified full scan: A.*;
• the same references in a RULE condition and through substrates generated for a compound FROM clause.

The correct form refers to the only schema that exists after the interleave:

SELECT result[0], result[1] STREAM result  FROM A#B
SELECT result2.*            STREAM result2 FROM A#B

An unqualified * also denotes the complete output schema and remains legal. If a later computation needs [_], name the interleave first and then use its result:

SELECT *                  STREAM interleaved FROM A#B
SELECT interleaved[_] * 2 STREAM scaled      FROM interleaved

When a particular component is needed again, recover it with the de-interleave operator & or % instead of using a source name through a # node.

NOTE: Aliasing after + is covered by the Pattern7 integration test, and rejection of a reference outside FROM by the field_ref_outside_from test. Rejection of named # components and positive controls for the result name are covered by ut_compiler unit tests.

Underscore Symbol Processing

The [_] index is syntactic sugar that replicates a field expression. One expression written in SELECT expands during compilation into multiple output fields, one for each compatible slot of the referenced streams.

The number of copies is not determined solely by a stream’s own schema. x[_] denotes all slots that x contributes to the record produced by the query’s complete FROM clause. This distinction matters when a stream operator changes the schema width, for example by creating a window.

The example uses the canonical declarations used throughout the chapter - core0 has two fields (BYTE, INTEGER), core1 has two fields (INTEGER, FLOAT), the schemas have equal cardinality:

DECLARE a BYTE, b INTEGER   STREAM core0, 0.1 TEXTFILE 'sensor_a.txt'
DECLARE c INTEGER, d FLOAT  STREAM core1, 0.2 TEXTFILE 'sensor_b.txt'

SELECT core0[_] * core1[_] STREAM scaled FROM core0 + core1

After compiling:

core0(1/10)	sensor_a.txt
	a: BYTE
	b: INTEGER
core1(1/5)	sensor_b.txt
	c: INTEGER
	d: FLOAT
scaled(1/10)	tail=1
	:- PUSH_STREAM(core0)
	:- PUSH_STREAM(core1)
	:- STREAM_ADD
	scaled_0: INTEGER
		PUSH_ID(scaled[0])
		PUSH_ID(scaled[2])
		MULTIPLY
	scaled_1: FLOAT
		PUSH_ID(scaled[1])
		PUSH_ID(scaled[3])
		MULTIPLY

The _ symbol expanded into two fields: scaled[0] * scaled[2] (i.e. a * c) and scaled[1] * scaled[3] (i.e. b * d). References to core0 and core1 were translated, via aliasing, into absolute positions in the combined schema. The resulting types are INTEGER (BYTE * INTEGER) and FLOAT (INTEGER * FLOAT) - the result of type promotion, described in a separate subchapter.

Width computed from the FROM clause

The one-field stream src contributes five slots when its window src@(1,5) appears in FROM. An FIR convolution can therefore be written without a separate named window stream:

DECLARE value INTEGER STREAM src, 1/500 TEXTFILE 'data.txt'
DECLARE coef INTEGER[5] STREAM filter, 1 TEXTFILE 'coef.txt'

SELECT src[_] * filter[_] STREAM products FROM src@(1,5)+filter
SELECT products[0]        STREAM output   FROM SUMC(products)

The first query expands into five products. It is equivalent to the longer form:

SELECT *                     STREAM window   FROM src@(1,5)
SELECT window[_] * filter[_] STREAM products FROM window+filter
SELECT products[0]           STREAM output   FROM SUMC(products)

In the shorter form, the compiler extracts the window from FROM as a substrate. Such a compiler-generated substrate is transparent when determining the width contributed by src. A user-named stream such as window, however, is a schema boundary, so the longer form refers to window[_], not src[_].

An operator in FROM can also reduce the width. A reducer collapses a window to one slot, so the following src[_] expands only once:

SELECT src[_] STREAM total FROM SUMC(src@(1,5))

If one expression contains several [_] indices, the compiler creates as many copies as the smallest determined width of their contributions. In a typical convolution, the window and the coefficient stream have the same width.

The compiler rejects a reference when the named stream does not occur in FROM, or when its fields do not form a contiguous block there. The latter occurs, for example, for src[_] under a window built over the concatenation (src+other)@(1,5): fields from both sources are repeated together, so no single width can be assigned to src without guessing. Name the subexpression in a separate query and apply [_] to that named result instead.

The _ symbol and interleave

Component aliases such as A[_] are valid for sum +, because sum preserves separate schema segments for both arguments. Do not use this form for a component reached through interleave #:

SELECT A[_] - B[_] STREAM difference FROM A#B

After interleaving, positions A[k] and B[k] are the same position in the shared schema, so this expression does not identify two different values. The compiler rejects the plan instead of silently calculating result[k]-result[k].

To process an interleaved record with _, name the interleave first and then refer to that result:

SELECT *                  STREAM interleaved FROM A#B
SELECT interleaved[_] * 2 STREAM scaled      FROM interleaved

Recovering a particular component requires the de-interleave operator & or %.

This functionality is mainly used in signal-filter algorithms that apply the same operations to corresponding elements of a window and a coefficient vector. It is not required to access RetractorDB’s complete functionality, but it makes such queries significantly shorter. See Signal Filter Implementation for a complete example.

Type Promotion

What happens when we multiply data of type BYTE with data of type INTEGER? RetractorDB follows strict type-promotion rules. Multiplying a BYTE-type field by a value of a field that is of type INTEGER produces a schema field of type INTEGER. This happens at compile time.

At present, RetractorDB supports the following data types:

STRING and RATIONAL are used in descriptors, conversions, and expressions; their representation and behavior are checked by ut_payload, ut_convertTypes, and integration scenarios. Complex numbers and rational Eisenstein complex numbers remain outside the current set of types.

An example of type promotion in practice - the scaled query from the chapter Underscore Symbol Processing:

SELECT core0[_] * core1[_] STREAM scaled FROM core0 + core1

core0 has fields BYTE and INTEGER, core1 has fields INTEGER and FLOAT. After expanding _, the compiler determines the output fields’ types:

Where the result field type comes from

The type, length, and multiplicity of a field are determined by a single compiler pass - compiler::inferFieldShapes() - which executes the field’s reverse-Polish program on a stack of types, exactly the way expressionEvaluator executes it on a stack of values. The pass runs after field references and window aggregates have been resolved, and before expression simplification, so the descriptor does not depend on any optimizer switch.

Until September 2026 the same question was answered by four local rules, none of which saw the whole expression. The parser started from INTEGER and recognized FLOAT or DOUBLE only when the cast was the last token of the program; a separate pass inferred STRING; the window reduction type was settled somewhere else again. That produced three results inconsistent with the value the engine wrote into the field: SELECT source[0] over a DOUBLE field yielded INTEGER, to_float('2.5') * 2 yielded INTEGER, and to_integer(AVG(x : 10)) + 1 fell back to RATIONAL.

Contract rules

A pure field read preserves the field’s type and length. Reading one element of a numeric array yields a single value, so multiplicity drops to one; STRING[N] is a single slot and keeps its width.

A binary operator (+, -, *, /, ^) yields the type that ranks higher in the order BYTE < INTEGER < UINT < RATIONAL < FLOAT < DOUBLE - with one exception: BYTE with BYTE yields INTEGER. This is not a design decision but a reflection of the language: uint8_t + uint8_t promotes to int in C++, and int is what ends up in the result. The same promotion applies to exact-type exponentiation, because a^k is computed by the same multiplication as the product written out.

A unary operator (-x, NOT x) preserves the argument’s type, except that NOT over a string yields an INTEGER logical result.

Numeric comparisons yield the operand type after normalization, without the BYTE promotion. String comparisons and NOT over a string yield INTEGER 1 or 0. AND and OR take their result type from the left operand, or from the right when the left is NULL; if the selected operand is a string, the result is INTEGER. These operators do not reach the SELECT list: they live in the RULE condition.

Functions share one policy:

sin, cos, and exp compute in double and return DOUBLE even for integer arguments. The other mathematical functions compute through double and cast the result back to the argument’s type: Ceil over a DOUBLE field yields DOUBLE, and Sqrt over INTEGER yields INTEGER. Explicit conversions determine the type of their result also when they sit in the middle of an expression: to_float('2.5') * 2 is FLOAT, and to_integer(AVG(x : 10)) + 1 is INTEGER.

Seven functions with an irrational range - Sqrt, sin, cos, exp, tan, log and log2 - do not compile over an argument of type RATIONAL: the compiler rejects the plan and requires an explicit to_double. This matters in practice, because the reducers MIN, MAX, AVG and SUMC yield RATIONAL for integer or rational inputs. The reason, the error message, the reach of the gate (it also covers a RULE ... WHEN condition), and the exception for the rounding functions are described in Field expressions and scalar functions; they are not repeated here, so that the two pages cannot drift apart on the next change.

A record-window aggregate takes its type from the whole program of its argument, passed through the same rule as the stream reducers: an arithmetic source (BYTE, INTEGER, UINT, RATIONAL) reduces to RATIONAL so an average does not lose precision, while FLOAT and DOUBLE stay themselves. Hence MIN(k : 4) over an INTEGER field yields RATIONAL, but MIN(to_double(k) : 4) yields DOUBLE.

NULL is not a type. A field has a type, and a missing value is a marker in the record metadata. An expression that evaluates to NULL on a given record does not thereby change the type of its field. null2zero(x) passes the argument’s type through, and the zero is stored in that very type.

Propagation through the plan

Operators that copy the operand schema - SELECT *, the shift >N, decimation -r, and the de-interleaves & and % - carry the producer’s field shape slot by slot. Stream sum + concatenates both input schemas. The type travels through an arbitrarily long chain of intermediate streams.

Interleave # reconciles both input schemas at each flat position. It selects the higher type, that type’s width for numeric positions, and the greater length for strings. Differing layouts are converted field by field; for example, RATIONAL combined with FLOAT yields FLOAT and can lose precision. Exact index selection by interleave and de-interleave does not reverse type conversion. Byte-for-byte recovery requires a common layout preserving both inputs’ representations.

Operators that synthesize a schema keep their own: the MIN/MAX/AVG/SUMC reducer in the FROM clause yields one field: RATIONAL for an integer or rational source, FLOAT for FLOAT, and DOUBLE for DOUBLE. The @(step, width) window yields fields of the widest type in the source record.

A DECLARE declaration is a contract with the source file and is not subject to inference - no compiler pass modifies it.

Artifact format change

Correct typing changes .desc and the record layout wherever INTEGER used to come out: DOUBLE occupies 8 bytes instead of 4, so it shifts the offsets of the following fields. A stream computed by an older engine version has an artifact with a different layout and will be rejected at startup as an incompatible schema - just as after any other change to the field list. There is no compatibility period: the descriptor now describes what the engine actually writes, whereas before it described something else.

Compilation Debugging

The compiler transforms an .rql file into an execution plan through several stages. The effect of each stage is visible through xretractor’s diagnostic flags. The tools described here let you answer questions like: why does the schema look different from what I wrote? where does this delta come from? why did a substrate appear?