QuantaStream
Back to home

Engineering white paper

Bitmap-Native Analytical SQL

Bitmap-Native Analytical SQL

Status: Draft v0.1, internal working paper Last updated: 2026-07-19

This paper is an engineering narrative for QuantaStream. It is not a legal analysis, patent claim chart, benchmark report, or final public positioning document. Its job is to preserve the architectural thesis while the engine is still moving quickly.

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.

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 local work has shown that these query shapes can be represented by the new SQL, planner, runtime, relationship-vector, and materialization stack. That is not yet a benchmark claim. It is an important correctness and architecture signal: the engine is beginning to answer real analytical shapes through the bitmap-native path.

The next proof point should be larger scale-factor data on controlled hardware, with reproducible MySQL and QuantaStream baselines.

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, but the work is not done.

  • The cost optimizer is still early.
  • SQL support is broadening, but not complete.
  • Full MySQL compatibility is a goal, not a completed claim.
  • Larger scale-factor TPC-H and compatibility benchmarks are still needed.
  • The batch and streaming load paths need substantial work.
  • Startup time and shard manifest handling need continued hardening.
  • Future 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 query suite green in both direct and standard modes.
  2. Run reproducible MySQL versus QuantaStream compatibility and benchmark labs.
  3. Add larger scale-factor data on controlled hardware.
  4. Finish BSI comparison work with upstream-quality tests and benchmarks.
  5. Improve load-path throughput before relying on larger public demos.
  6. Continue reducing materialization where a bitmap or BSI primitive can answer directly.
  7. Start cost-based optimization from table cardinality, predicate selectivity, and relationship-vector reduction cost.

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