QuantaStream
Back to home News FAQ Contact GitHub

Engineering white paper

Bitmap-Native Analytical SQL

Bitmap-Native Analytical SQL

Status: Working paper v0.2. Last updated: 2026-08-21

This paper is an engineering narrative for QuantaStream. It is not a legal analysis or patent claim chart. Its job is to preserve the architectural thesis and connect that thesis to the current validation work.

Executive Summary

QuantaStream is built around a simple idea:

Bitmap-native analytical SQL.

The database should accept familiar SQL, but the physical execution model should avoid treating SQL as an instruction to eagerly assemble rows. Instead, queries are lowered into constraints over compressed bitmap domains. Filters, joins, semi-joins, anti-joins, grouping inputs, and same-row comparisons become set operations over row-number domains, bit-sliced indexes, dictionaries, and relationship vectors. Rows are rehydrated only after the candidate sets have already been narrowed.

This is the core distinction: QuantaStream is not a row engine with bitmap indexes bolted on. It is a bitmap-domain execution engine with a SQL front end.

QuantaStream uses native bitmap and bit-sliced indexes whose storage and processing costs scale predictably with indexed cardinality and data volume. This design is particularly effective for filtering, aggregation, and set-oriented analysis common in streaming analytics. Unlike architectures centered on row lookup, compaction, or repeated column scans, QuantaStream can combine filters and relationships directly through bitmap algebra, defer row materialization until results are needed, and reuse the same indexed representation for ingestion and interactive queries.

That thesis is now backed by a more complete first-release posture: a single-node engine with a MySQL-compatible endpoint, descriptor-driven schemas, views, derived tables, temporary tables, CTAS materialization, prepared statement coverage, Workbench-friendly metadata, local WAL/backup/restore tooling, support bundles, and repeatable TPC-H validation at multiple scale factors.

Motivation

Traditional relational engines are extraordinarily capable, but their physical operators often revolve around moving, hashing, sorting, and materializing tuples. Modern column stores improve locality and compression, but many still pay substantial costs once a query shape requires joins, correlated membership, subqueries, grouped aggregates, or repeated domain translation between fact and dimension tables.

QuantaStream takes a different route. It tries to keep the query in compressed set form for as long as possible:

  • AND becomes bitmap intersection.
  • OR becomes bitmap union.
  • NOT, anti-join, and NOT IN become bitmap difference.
  • Equality and range predicates over numeric, time, and encoded string domains produce candidate bitmaps.
  • Join relationships are represented as vectors that translate candidate sets between row-number domains.
  • Aggregation operates after candidate reduction, materializing only the fields required for grouping, ordering, aggregate inputs, residual predicates, and final projection.

The result is an execution model where SQL becomes constraint propagation over compressed bitmap domains.

Core Vocabulary

QuantaStream needs crisp terms because bitmap engines and relational databases use similar words differently.

rownum : The tuple identifier within a table. This is the relational row identity used by the query engine. It is not the same as a bitmap "row id" in legacy naming.

bitmap : A compressed set of rownums, usually represented with Roaring bitmaps. A bitmap answers the question "which rows are currently candidates?"

standard bitmap : A bitmap attached to a discrete value. Low-cardinality enum values and boolean states naturally fit here.

multiplicity : The column cardinality model. scalar means one logical value per row. set means a row may belong to multiple value bitmaps for the same column.

BSI : A bit-sliced index. A BSI represents numeric, timestamp, or encoded string values in a way that supports equality, range, comparison, and aggregate-like operations without first rehydrating all original values.

StringEnum : A dictionary-backed low-cardinality string representation. Values map to stable dictionary ids, and each id can be represented as a standard bitmap.

backing string : A high-cardinality string representation where the bitmap/BSI path carries a compact comparable value and the original value is available through KVStore when rehydration is needed.

relationship vector : A BSI that maps rownums in one table domain to rownums in another table domain. In practice this is the engine's native representation for parent-child relationships.

seed bitmap : A first-class existence/candidate bitmap for a table or shard. A seed answers "what rows exist?" without synthesizing the answer through a large number of independent predicate fragments.

Data Representation

The core representation model is intentionally pluggable, but the primitives are few:

  • Low-cardinality strings and booleans are represented as standard bitmaps.
  • Numeric values are represented as numeric BSIs.
  • Timestamps are represented as timestamp BSIs with an explicit granularity.
  • High-cardinality strings can be represented through compact BSI/hash lookup plus backing storage.
  • Relationship columns are represented as vector BSIs.
  • Existence can be represented as a table or shard seed bitmap.

The goal is to reduce one-off physical types. A schema should describe the semantics of a column and the data representation choices: cardinality, multiplicity, time granularity, numeric precision, prefix length, max length, searchability, dictionary behavior, and rehydration policy.

That lets the planner reason about a column in terms of capabilities:

  • Can this column produce an equality bitmap?
  • Can it produce a range bitmap?
  • Can it participate in prefix matching?
  • Can it perform same-row BSI comparisons?
  • Does it require dictionary lookup for original values?
  • Does it need KVStore rehydration?
  • Can it be used as a relationship vector?

The optimizer should make decisions from capabilities, not from historical type names.

Selection Algebra

A single-table predicate lowers into a bitmap expression:

where age >= 30 and status in ('ACTIVE', 'TRIAL')

becomes:

INTERSECT(
  BSI_RANGE(age, 30, +inf),
  UNION(
    BITMAP(status = 'ACTIVE'),
    BITMAP(status = 'TRIAL')
  )
)

The result is a candidate rownum bitmap. No rows need to exist yet. The engine can also represent !=, NOT IN, and anti-membership as differences from a seed:

DIFFERENCE(
  SEED(customers),
  BITMAP(status = 'DELETED')
)

This is important because absence and negation are not afterthoughts. They are native set operations.

Boolean Algebra

Boolean predicate lowering should preserve SQL semantics while favoring bitmap algebra:

  • A AND B -> INTERSECT(A, B)
  • A OR B -> UNION(A, B)
  • NOT A -> DIFFERENCE(seed, A)
  • A AND NOT B -> DIFFERENCE(A, B)

The planner must respect parentheses, three-valued SQL semantics where applicable, and NULL behavior. The physical target, however, remains simple: produce candidate bitmaps and combine them with set algebra.

This gives the optimizer a useful freedom: it can order selective bitmap reductions before expensive residual scans, and it can avoid materializing columns that only exist to reduce candidate sets.

BSI Algebra

BSIs extend bitmap selection beyond discrete value membership.

For a single BSI column:

  • Equality produces a bitmap of rows whose encoded value equals a literal.
  • Range produces a bitmap of rows inside a lower/upper bound.
  • Greater-than and less-than variants produce directional candidate bitmaps.
  • Batch equality can combine many equality probes into one membership result.

For two BSI columns in the same rownum domain:

where l_receiptdate > l_commitdate

should become:

BSI_COMPARE_GT(l_receiptdate, l_commitdate)

That returns a bitmap directly. The important point is that same-row field comparison should not require materializing both values for every candidate row and comparing them in Go. That is temporary implementation scaffolding, not the desired algebra.

This is one reason the Roaring BSI work matters. APIs such as BSI-to-BSI comparison let QuantaStream express query intent at the correct physical level.

Join Algebra

The join model is the heart of QuantaStream.

In a conventional relational execution plan, a join often constructs joined tuples or a hash structure over one side and probes from the other. In QuantaStream, the preferred physical operation is relationship-vector constraint propagation.

This is the direct architectural descendant of the bitmap-join patent work. The patent is not merely background IP; it is the foundation for treating joins as vector-based translation between bitmap rownum domains rather than tuple assembly. QuantaStream's relationship-vector execution model is the modern engineering expression of that idea.

For a parent-child relationship:

orders.o_orderkey -> lineitem.l_orderkey

QuantaStream can store a relationship vector BSI:

lineitem rownum -> orders rownum

This gives the planner two directions of movement:

  • Parent-to-child: apply an orders candidate set to the lineitem relationship vector and produce matching lineitem rownums.
  • Child-to-parent: transpose or reduce a lineitem candidate set through the relationship vector and produce matching orders rownums.

That means join execution can be viewed as repeatedly tightening candidate sets for each table role:

candidates(customer) -> relationship vector -> candidates(orders)
candidates(orders) -> relationship vector -> candidates(lineitem)
candidates(lineitem) -> relationship vector -> candidates(orders)

Each table role keeps its own rownum domain. The planner must know when a set crosses rownum domains, and it must translate explicitly through a relationship vector. A bitmap from one table is never casually compared to a bitmap from another table.

Semi-Joins and Anti-Joins

Semi-joins and anti-joins fall naturally out of bitmap algebra.

EXISTS is membership:

outer candidates INTERSECT rows_with_matching_inner

NOT EXISTS is difference:

outer candidates DIFFERENCE rows_with_matching_inner

This is strategically important. SQL subqueries, IN, NOT IN, EXISTS, NOT EXISTS, and certain anti-join forms can all be routed toward the same small set of bitmap primitives rather than building separate execution paths for every SQL surface form.

Aggregation and Late Materialization

Aggregation should happen after candidate reduction.

For a grouped aggregate:

select l_orderkey, sum(l_extendedprice)
from lineitem
where l_shipdate < date '1995-03-15'
group by l_orderkey

the physical path should be:

  1. Produce a candidate bitmap from the date predicate.
  2. Materialize only l_orderkey and l_extendedprice for those candidates.
  3. Accumulate grouped state.
  4. Materialize only final output fields.

The same model applies across joins. Relationship vectors reduce the graph first; grouping fields, aggregate inputs, residual predicate fields, and final projection fields are hydrated afterward.

That is the discipline: use bitmaps to decide which rows matter, then hydrate only the values needed to answer the query.

Optimizer Direction

The optimizer's long-term job is to choose a reduction order over a graph of bitmap domains.

For star and snowflake schemas, small dimension filters can produce compact candidate sets. Relationship vectors can then push those sets into the fact table domain before fact table materialization. In the other direction, a selective time range or fact predicate can shrink the fact table and then pull constraints back toward dimensions.

The optimizer should eventually reason about:

  • Cardinality of each table role.
  • Selectivity of predicates.
  • Cost of relationship-vector projection.
  • Cost of BSI range and comparison operations.
  • Cost of materialization by representation type.
  • Cost of residual predicates.
  • Time-shard and node locality.
  • Whether a seed bitmap is already cached.
  • Whether a candidate set is cheap enough to pass to a node.
  • Whether a broad node-side seed or shard-local filter is cheaper.

This is where QuantaStream may become genuinely distinct. The optimizer is not just choosing join order. It is choosing the order in which compressed constraints should flow through a graph.

TPC-H as an Architectural Microcosm

TPC-H is useful because it contains many of the shapes QuantaStream cares about:

  • A large fact-like table: lineitem.
  • Header/fact relationship: orders.
  • Dimensions: customer, supplier, part, nation, region.
  • A bridge-like table: partsupp.
  • Date ranges, string dictionaries, numeric BSIs, grouped aggregates, correlated membership, same-row comparisons, and multi-hop joins.

The current work has shown that these query shapes can be represented by the SQL, planner, runtime, relationship-vector, and materialization stack. This is no longer only a local smoke-test signal: the same query families have been loaded, profiled, and compared across single-node and distributed runs.

Benchmark Checkpoint

The latest AWS distributed checkpoint was captured on 2026-08-15 using three r7i.4xlarge data nodes plus a bench-runner, SQLRunner direct cluster RPC, 12 loader workers, and load batch size 1000.

TPC-H SF1, SF2, and SF3 all loaded and passed the read-only and profile suites. lineitem load elapsed times were:

Scalelineitem rowsLoad elapsed
SF16,001,215419s
SF211,997,996777s
SF317,996,6091302s

Representative profile medians from the same distributed checkpoint:

Query shapeSF1SF2SF3
Q3 grouped revenue with order fields1.936s3.791s5.465s
Q5 same-nation combined graph count3.252s5.633s8.355s
Q19 formal discounted revenue0.375s0.467s0.586s

The single-node MySQL compatibility lane also has an SF1 comparison against a 16-vCPU MySQL reference host. The important signal is not that every query shape is faster. It is that bitmap-native execution is already strong on the analytical shapes that match the architecture: broad grouping, selective bitmap reduction, and star-style relationship traversal. In that checkpoint, QuantaStream's single-node endpoint ran the compact Q5 combined graph count in 1.710s versus MySQL at 10.996s, Q3 grouped revenue limit in 2.228s versus 6.315s, Q1 grouped lineitem shape in 0.288s versus 2.293s, and Q6 discounted revenue in 0.475s versus 1.384s.

These numbers are checkpoints, not permanent claims. Their value is that they are reproducible, tied to SQLRunner reports, and specific enough to protect the top-line performance baseline while compatibility work continues.

Patent Context

The project has prior IP context around bitmap representation and bitmap-based query processing.

The granted Disney patent US11392606, "System and method for converting user data from disparate sources to bitmap data," describes converting data from multiple sources into a conformed data set and then into bitmap-oriented representation. The public patent record lists Dakshinamurthi Rajavel, Guy Molinari, Ryan J. Junk, and Rajagopal Baskaran as inventors.

The related Disney join patent is US12086136, "Techniques for Executing Join Operations Using Bitmap Indices." The public record lists Guy Molinari as the inventor, Disney Enterprises, Inc. as the assignee, a February 4, 2020 filing date, and a September 10, 2024 grant date. This patent is critical because it is the foundation of vector-based joins: join processing can be expressed by producing child or parent result bitmaps and translating those sets through BSI-backed relationship structures.

These references should be treated as historical and strategic context. They do not define the full QuantaStream design, and this paper does not attempt to interpret patent scope. The current QuantaStream architecture adds a concrete SQL compatibility surface, relationship-vector execution, late materialization, native runtime inspection, direct and standard deployment modes, and an implementation path built around modern Roaring bitmap/BSI primitives.

Relationship to Roaring Bitmaps

Roaring bitmaps are the practical compression foundation. They provide a well-known compressed bitmap representation with fast set operations, and the Roaring ecosystem is the right place for core BSI improvements that are generally useful beyond QuantaStream.

QuantaStream should avoid private forks of fundamental bitmap algorithms where possible. When the BSI library needs better primitives, the ideal path is to produce polished, benchmark-backed contributions upstream. That includes:

  • Faster BatchEqual-style membership operations.
  • BSI-to-BSI comparison operators.
  • More professional BSI tests and benchmarks.
  • Clear documentation of where 64-bit BSI behavior differs from 32-bit BSI behavior.

The database and the bitmap library should evolve together, but with clean boundaries. QuantaStream should express database intent. Roaring should expose correct, efficient bitmap and BSI primitives.

What Makes This Different

The differentiator is not simply "uses bitmaps." Many systems use bitmap indexes.

The differentiator is that QuantaStream treats compressed bitmap domains as the native query execution substrate:

  • SQL is parsed and planned into bitmap-capable intermediate forms.
  • Table roles remain separate rownum domains until explicitly translated.
  • Relationship vectors perform domain translation.
  • Boolean logic is lowered into set algebra.
  • Same-row comparisons are intended to be BSI comparisons, not row scans.
  • Semi-joins and anti-joins become membership and difference.
  • Aggregation is fed by reduced candidate sets.
  • Materialization is late and field-specific.
  • Runtime inspection exposes the physical algebra used to answer a query.

The guiding line is worth preserving:

QuantaStream does not move rows through joins; it moves constraints through compressed bitmap domains until only the necessary rows remain.

Current Limits

The architecture is promising, and the current product surface is much more concrete than the first draft of this paper. The remaining limits are now release gates and follow-on engineering tracks:

  • The cost optimizer is still early, even though several star-query reduction and relationship-artifact improvements are already validated.
  • QuantaStream supports a focused MySQL-compatible SQL surface, not a full MySQL clone.
  • TPC-H SF1/SF2/SF3 benchmarks are repeatable, but each release candidate still needs a clean performance pass before public numbers are refreshed.
  • Batch loading is validated at SF1-SF3; live streaming ingest needs its own product-grade demo and recovery story.
  • Local WAL, backup, restore, support bundles, and operator preflights are now part of the 1.0 posture; distributed backup barriers and cloud storage adapters remain follow-on work.
  • BSI library work remains an optimization frontier, but the current same-row comparison path is available from the selected Roaring dependency.
  • High-cardinality string representation still needs the StringLexBSI design to mature.
  • Global cross-session query caching remains a future feature, not a crutch the current engine requires.

These limits are healthy. They keep the project honest.

Near-Term Proof Points

The most useful next proof points are:

  1. Keep the TPC-H SF1/SF2/SF3 benchmark lane repeatable across release candidates.
  2. Finish release-grade WAL, backup, restore, and startup replay validation.
  3. Keep the binary artifact, getting-started runbook, support bundle, and doctor local path boring and repeatable.
  4. Expand MySQL client compatibility with Java/JDBC, Node.js, and Tableau-style metadata coverage.
  5. Build the first streaming ingest demo around real insert/update pressure and recovery semantics.
  6. Continue reducing materialization where a bitmap or BSI primitive can answer directly.
  7. Continue cost-based optimization from table cardinality, predicate selectivity, relationship-vector reduction cost, and node locality.

Conclusion

QuantaStream's core algebra is compact:

selection      -> bitmap production
AND            -> intersection
OR             -> union
NOT            -> difference
range/equality -> BSI or dictionary bitmap
same-row cmp   -> BSI-to-BSI comparison
join           -> relationship-vector domain translation
EXISTS         -> membership
NOT EXISTS     -> difference
aggregation    -> reduced candidates plus late materialization

That compact algebra is the project.

The product expression is SQL. The execution expression is bitmap algebra. The engineering challenge is to make those two worlds line up cleanly enough that a user can write ordinary analytical SQL while the engine quietly does something unusually powerful underneath.

References