Introduction

Welcome to the QBICE (Query-Based Incremental Computation Engine) book! This guide will teach you how to build efficient incremental computation systems using QBICE.

What is QBICE?

QBICE is a high-performance, asynchronous incremental computation framework for Rust. It allows you to define computations as a graph of queries, where changes to inputs automatically propagate through the system—recomputing only what’s necessary.

Why Incremental Computation?

Consider a compiler that needs to type-check a large codebase. When a developer changes a single file, recompiling everything from scratch would be wasteful. Instead, an incremental system:

Tracks dependencies - Knows which computations depend on the changed file
Invalidates selectively - Marks only affected computations as needing updates
Recomputes minimally - Recalculates only what’s necessary

This approach can reduce compilation times from minutes to seconds.

Key Benefits

Automatic Dependency Tracking - QBICE automatically records which queries depend on which others
Minimal Recomputation - Only recomputes queries whose inputs have changed
Async-First - Built on Tokio for efficient concurrent execution
Persistent - Query results survive program restarts

Use Cases

QBICE is ideal for scenarios where:

Computations are expensive relative to cache lookups
Inputs change incrementally
You want to avoid redundant recomputation
You need fine-grained dependency tracking

Common applications include:

Compilers - Incremental compilation and analysis
Build Systems - Smart rebuilding of artifacts
IDEs - Real-time code analysis and diagnostics

Prior Art

QBICE builds on decades of research and practical work in incremental computation. Understanding these foundational systems helps appreciate QBICE’s design choices.

Adapton

Adapton is a pioneering research that introduced many core concepts used in QBICE:

Demanded Computation Graphs (DCG) - The idea that computations form a graph where dependencies are tracked automatically
Dirty Propagation - Marking dependency edges as dirty when inputs change

The SafeDivide example in the tutorial is adapted from Adapton’s classic examples, demonstrating how incremental computation handles error cases elegantly.

Salsa

Salsa is a Rust framework for incremental computation used in rust-analyzer. It provides:

Query-based incremental computation
Automatic dependency tracking

QBICE shares similar goals but differs in:

Fine-Grained Invalidation: Salsa uses timestamp based to determine whether the query needs to be reverified, while QBICE uses fine-grained dirty propagation through dependency edges.
Optimizations: Salsa achieves optimized graph traversal through the conceopt of durability, while QBICE provides firewall and projection queries to optimize dirty propagation and recomputation.

How This Book Is Organized

This book is divided into three main sections:

Tutorial

A hands-on guide that walks you through building your first QBICE application. You’ll learn the fundamentals by creating a simple calculator that performs incremental computation.

Advanced Topics

Deep dives into optimization techniques like firewall queries, projection queries, and performance tuning strategies.

Prerequisites

This book assumes you’re familiar with:

Rust - Basic to intermediate knowledge
Async/Await - Understanding of async Rust and Tokio
Traits - How Rust traits work

If you’re new to these topics, we recommend:

Getting Help

API Documentation - docs.rs/qbice
GitHub - github.com/Simmypeet/qbice
Issues - Report bugs or request features on GitHub

Let’s get started!

Getting Started

In this tutorial, we’ll build a simple incremental calculator that can compute arithmetic expressions. This will teach you the fundamentals of QBICE: queries, executors, and the engine.

Project Setup

First, create a new Rust project:

cargo new qbice-calculator
cd qbice-calculator

Add QBICE to your Cargo.toml:

[dependencies]
qbice = "0.2.0"
tokio = { version = "1", features = ["full"] }
tempfile = "3"

What We’ll Build

Our calculator will support:

Variables - Named numeric values (A and B)
Division - Dividing two values (with assertion that denominator != 0)
Safe Division - Division that returns None for division by zero

The key feature: when we change a variable’s value, only dependent computations will be recalculated. Plus, we’ll see how queries can depend on other queries (SafeDivide depends on Divide).

The Problem

Imagine we have these computations:

fn Divide(Variable::A, Variable::B) -> i32 {
    let a = read Variable::A;
    let b = read Variable::B;

    panic if b == 0;

    a / b
}

fn SafeDivide(Variable::A, Variable::B) -> Option<i32> {
    let b = read Variable::B;

    if b == 0 {
        return None;
    }

    Some(
        Divide(Variable::A, Variable::B)
    )
}

If we start with A = 42 and B = 2, and compute SafeDivide(A, B), we get Some(21).

Now, if we change B to 0 and recompute SafeDivide(A, B), we should get None.

Notice how SafeDivide depends on Divide, which in turn depends on Variable::A and Variable::B.

Finally, if we change B back to 2 and recompute, we should get Some(21) again but without re-executing Divide since its result was cached.

QBICE automatically tracks these dependencies and handles the incremental updates.

Project Structure

We’ll build this in stages:

Define Queries - Create types representing our computations
Implement Executors - Write the logic for each computation
Set Up the Engine - Configure QBICE to manage our queries
Execute Queries - Run computations and see results
Update Inputs - Change values and observe incremental updates

Let’s start by defining our queries!

Defining Queries

A query in QBICE represents a computation with an input (the query key) and an output (the query value). Let’s define the queries for our calculator.

Required Traits

Every query type must implement several traits:

Query - The main trait defining the output type
StableHash - For consistent hashing across runs
Identifiable - For stable type identification
Encode / Decode - For persistence
Debug, Clone, PartialEq, Eq, Hash - Standard Rust traits

Fortunately, most of these can be derived automatically!

Variable Query

First, let’s define a query for variables. Variables are inputs to our system—they don’t compute anything, they just hold values. We’ll use an enum for simplicity:

#![allow(unused)]
fn main() {
use qbice::{
    Decode, Encode, Identifiable, Query, StableHash,
};

#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub enum Variable {
    A,
    B,
}

impl Query for Variable {
    type Value = i32;
}
}

Let’s break this down:

The Enum

#![allow(unused)]
fn main() {
pub enum Variable {
    A,
    B,
}
}

The enum itself is the query key. Different variants represent different queries. Variable::A and Variable::B are distinct queries. Using an enum is simpler than using strings for our example.

The Derives

#![allow(unused)]
fn main() {
#[derive(
    Debug,              // For error messages
    Clone,              // Queries must be cloneable
    Copy,               // Cheap to copy (for enums)
    PartialEq, Eq,      // For comparing queries
    PartialOrd, Ord,    // For ordering (useful for sorted collections)
    Hash,               // For hash maps
    StableHash,         // For consistent hashing
    Identifiable,       // For type identification
    Encode, Decode,     // For persistence
)]
}

These derived traits enable QBICE to:

Store queries in hash maps
Generate stable identifiers
Persist results to disk
Display debug information

The Query Trait

#![allow(unused)]
fn main() {
impl Query for Variable {
    type Value = i32;
}
}

The Value associated type defines what this query produces. Variables produce i32 values.

Divide Query

Now let’s define a query that divides two variables:

#![allow(unused)]
fn main() {
#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub struct Divide {
    pub numerator: Variable,
    pub denominator: Variable,
}

impl Query for Divide {
    type Value = i32;
}
}

The Divide query takes two variables and produces their quotient. The key insight: Divide doesn’t actually perform the division—that’s the executor’s job. The query just describes what to compute.

Note: This version will panic if the denominator is zero (we’ll handle that with SafeDivide).

SafeDivide Query

Now for the safe version that handles division by zero:

#![allow(unused)]
fn main() {
#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub struct SafeDivide {
    pub numerator: Variable,
    pub denominator: Variable,
}

impl Query for SafeDivide {
    type Value = Option<i32>;  // Returns None for division by zero!
}
}

Notice that SafeDivide returns Option<i32> instead of i32. This allows us to return None when dividing by zero, making our computation safe and preventing panics.

Why Separate Queries from Execution?

You might wonder: why not just put the computation logic in the query itself?

The separation provides several benefits:

Decoupling: This might sound cliche, but separating the what (query) from the how (executor) can sometime be beneficial. For example, in a large scale query system if you want to do unit testing, you can mock out executors without changing the query definitions.
External Effects: Sometimes you can perform some side-effects in the executor like logging, metrics, etc. NOTE: Be careful with side-effects in executors, some side-effects that doesn’t influence the output value are usually okay, but anything that influences the output value will definitely break the semantics of incremental computation.

Complete Code

Here’s our complete query module:

#![allow(unused)]
fn main() {
use qbice::{
    Decode, Encode, Identifiable, Query, StableHash,
};

#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub enum Variable {
    A,
    B,
}

impl Query for Variable {
    type Value = i32;
}

#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub struct Divide {
    pub numerator: Variable,
    pub denominator: Variable,
}

impl Query for Divide {
    type Value = i32;
}

#[derive(
    Debug,
    Clone,
    Copy,
    PartialEq,
    Eq,
    PartialOrd,
    Ord,
    Hash,
    StableHash,
    Identifiable,
    Encode,
    Decode,
)]
pub struct SafeDivide {
    pub numerator: Variable,
    pub denominator: Variable,
}

impl Query for SafeDivide {
    type Value = Option<i32>;
}
}

Key Takeaways

Queries define what to compute, not how
Query types are the keys; the associated Value type is the result
Most required traits can be derived automatically
Each unique query instance (different field values) represents a distinct computation

Next, we’ll implement the executors that actually perform these computations!

Implementing Executors

Now that we’ve defined our queries, let’s implement the executors that actually perform the computations. Executors implement the Executor trait, which defines how to compute a value for a specific query type.

The Executor Trait

The Executor trait has one required method:

#![allow(unused)]
fn main() {
pub trait Executor<Q: Query, C: Config>: Send + Sync {
    async fn execute(
        &self,
        query: &Q,
        engine: &TrackedEngine<C>,
    ) -> Q::Value;
}
}

Let’s break this down:

&self - The executor instance (you can store state here)
query: &Q - The specific query being executed
engine: &TrackedEngine<C> - Used to query other dependencies
Returns Q::Value - The computed result

Divide Executor

Let’s start with the Divide executor:

#![allow(unused)]
fn main() {
pub struct DivideExecutor;

impl<C: Config> Executor<Divide, C> for DivideExecutor {
    async fn execute(
        &self,
        query: &Divide,
        engine: &TrackedEngine<C>,
    ) -> i32 {
        // Query the numerator
        let num = engine.query(&query.numerator).await;

        // Query the denominator
        let denom = engine.query(&query.denominator).await;

        // Assert denominator is not zero
        assert!(denom != 0, "denominator should not be zero");

        // Return the quotient
        num / denom
    }
}
}

This is where QBICE’s magic happens! Notice:

We query other queries - engine.query() executes dependencies
Dependencies are tracked automatically - QBICE records that Divide depends on two Variable queries
It’s async - We can await other queries without blocking
We assert safety - This version panics if denominator is zero

SafeDivide Executor

Now for the safe version that handles division by zero:

#![allow(unused)]
fn main() {
pub struct SafeDivideExecutor;

impl<C: Config> Executor<SafeDivide, C> for SafeDivideExecutor {
    async fn execute(
        &self,
        query: &SafeDivide,
        engine: &TrackedEngine<C>,
    ) -> Option<i32> {
        // Query the denominator first
        let denom = engine.query(&query.denominator).await;

        // Check for division by zero
        if denom == 0 {
            return None;
        }

        // Safe to divide - delegate to Divide query
        Some(
            engine.query(&Divide {
                numerator: query.numerator,
                denominator: query.denominator,
            }).await
        )
    }
}
}

This executor demonstrates an important pattern:

Early return - We check for division by zero first
Query composition - SafeDivide depends on Divide
Error handling - Returns None instead of panicking

Adding State to Executors

Executors can maintain state. This is useful for tracking metrics, like call counts. Maintaining state is ok as long as it doesn’t affect the correctness of computations.

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};

pub struct DivideExecutor {
    call_count: AtomicUsize,
}

impl DivideExecutor {
    pub fn new() -> Self {
        Self {
            call_count: AtomicUsize::new(0),
        }
    }

    pub fn call_count(&self) -> usize {
        self.call_count.load(Ordering::SeqCst)
    }
}

impl<C: Config> Executor<Divide, C> for DivideExecutor {
    async fn execute(
        &self,
        query: &Divide,
        engine: &TrackedEngine<C>,
    ) -> i32 {
        // Increment counter
        self.call_count.fetch_add(1, Ordering::SeqCst);

        let num = engine.query(&query.numerator).await;
        let denom = engine.query(&query.denominator).await;

        assert!(denom != 0, "denominator should not be zero");

        num / denom
    }
}
}

Now we can verify that QBICE is actually performing incremental computation by checking how many times each executor was called!

Complete Code

Here’s our complete executor module:

#![allow(unused)]
fn main() {
use std::sync::atomic::{AtomicUsize, Ordering};
use qbice::{Config, Executor, TrackedEngine};

// Import our query types
use crate::{Divide, SafeDivide};

pub struct DivideExecutor {
    pub call_count: AtomicUsize,
}

impl DivideExecutor {
    pub fn new() -> Self {
        Self {
            call_count: AtomicUsize::new(0),
        }
    }
}

impl<C: Config> Executor<Divide, C> for DivideExecutor {
    async fn execute(
        &self,
        query: &Divide,
        engine: &TrackedEngine<C>,
    ) -> i32 {
        self.call_count.fetch_add(1, Ordering::SeqCst);

        let num = engine.query(&query.numerator).await;
        let denom = engine.query(&query.denominator).await;

        assert!(denom != 0, "denominator should not be zero");

        num / denom
    }
}

pub struct SafeDivideExecutor {
    pub call_count: AtomicUsize,
}

impl SafeDivideExecutor {
    pub fn new() -> Self {
        Self {
            call_count: AtomicUsize::new(0),
        }
    }
}

impl<C: Config> Executor<SafeDivide, C> for SafeDivideExecutor {
    async fn execute(
        &self,
        query: &SafeDivide,
        engine: &TrackedEngine<C>,
    ) -> Option<i32> {
        self.call_count.fetch_add(1, Ordering::SeqCst);

        let denom = engine.query(&query.denominator).await;
        if denom == 0 {
            return None;
        }

        Some(
            engine.query(&Divide {
                numerator: query.numerator,
                denominator: query.denominator,
            }).await
        )
    }
}
}

Key Takeaways

Executors define how to compute query results
Use engine.query() to depend on other queries
Dependencies are tracked automatically by QBICE
Executors can maintain state (like metrics) if it doesn’t affect correctness

Next, we’ll set up the engine and register these executors!

Setting Up the Engine

Now that we have queries and executors, let’s create and configure the QBICE engine. The engine is the central component that manages query execution, caching, and dependency tracking.

Creating an Engine

The basic setup requires three components:

Plugin - For serialization/deserialization
Database Factory - For persistent storage
Hasher Builder - For stable hashing

Here’s a simple setup:

use std::sync::Arc;
use qbice::{
    Engine, DefaultConfig,
    serialize::Plugin,
    stable_hash::{SeededStableHasherBuilder, Sip128Hasher},
    storage::kv_database::rocksdb::RocksDB,
};

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create a temporary directory for the database
    let temp_dir = tempfile::tempdir()?;

    // Create the engine
    let mut engine = Engine::<DefaultConfig>::new_with(
        Plugin::default(),
        RocksDB::factory(temp_dir.path()),
        SeededStableHasherBuilder::<Sip128Hasher>::new(0),
    )?;

    // Engine is ready to use!
    Ok(())
}

Let’s examine each component:

Plugin - Serialization

#![allow(unused)]
fn main() {
Plugin::default()
}

The plugin handles serialization and deserialization of query keys and values. For custom serialization needs, you can create your own plugin.

Database Factory - Persistence

#![allow(unused)]
fn main() {
RocksDB::factory(temp_dir.path())
}

QBICE supports pluggable storage backends. RocksDB is the default and recommended choice for production use. The factory creates a database instance at the specified path.

Available backends:

RocksDB (default) - Production-ready, embedded database
fjall - Alternative key-value store

#![allow(unused)]
fn main() {
// Using RocksDB (requires "rocksdb" feature)
use qbice::storage::kv_database::rocksdb::RocksDB;
let factory = RocksDB::factory("/path/to/db");

// Using fjall (requires "fjall" feature)
use qbice::storage::kv_database::fjall::Fjall;
let factory = Fjall::factory("/path/to/db");
}

Hasher Builder - Stable Hashing

#![allow(unused)]
fn main() {
SeededStableHasherBuilder::<Sip128Hasher>::new(0)
}

The hasher generates stable 128-bit hashes for queries. The seed (0 in this example) should be consistent across runs for the same project.

Important: Use the same seed when reloading a database, or cached results won’t match!

Registering Executors

After creating the engine, register all your executors:

#![allow(unused)]
fn main() {
use std::sync::Arc;

// Create executor instances
let divide_executor = Arc::new(DivideExecutor::new());
let safe_divide_executor = Arc::new(SafeDivideExecutor::new());

// Register with the engine
engine.register_executor(divide_executor.clone());
engine.register_executor(safe_divide_executor.clone());
}

A few important notes:

Executors must be wrapped in Arc for shared ownership
Each query type needs exactly one executor
Registering the same query type twice will overwrite the first executor
You can keep Arc clones to access executor state (like call counters)
There’s no executor for Variable since it’s an input query
It’s expected to register the same executors again after reloading an engine from disk

Creating a TrackedEngine

To actually execute queries and set inputs, first convert the engine to an Arc:

#![allow(unused)]
fn main() {
// Move engine into Arc for shared ownership
let engine = Arc::new(engine);
}

The Arc (Atomic Reference Count) enables shared ownership of the engine, which is required for both input sessions and query execution.

Setting Input Values

Before querying, set the initial values for input queries:

#![allow(unused)]
fn main() {
// Create an input session (requires &Arc<Engine>)
{
    let mut input_session = engine.input_session();

    // Set variable values
    input_session.set_input(Variable::A, 42);
    input_session.set_input(Variable::B, 2);

} // Session is committed when dropped
}

The input session is a transaction-like mechanism:

Changes are batched
Dirty propagation happens when the session is dropped
You can set many inputs efficiently

Executing Queries

Create a TrackedEngine to execute queries:

#![allow(unused)]
fn main() {
// Create a tracked engine for querying
let tracked = engine.tracked();

// Now you can execute queries!
let result = tracked.query(&SafeDivide {
    numerator: Variable::A,
    denominator: Variable::B,
}).await;

assert_eq!(result, Some(21));
}

The TrackedEngine is a lightweight wrapper that:

Tracks dependencies during query execution
Provides the query() method
Can be cloned cheaply

Each TrackedEngine is tied to a specific timestamp of the engine’s state when it’s created.

Every time you update inputs, the engine’s timestamp advances leaving the old TrackedEngine stale.

Calling stale tracked engines will return a future that never resolves, forcing you to drop the future.

Complete Setup Example

Here’s everything together:

use std::sync::Arc;
use qbice::{
    Engine, DefaultConfig,
    serialize::Plugin,
    stable_hash::{SeededStableHasherBuilder, Sip128Hasher},
    storage::kv_database::rocksdb::RocksDB,
};

// Import our types
use crate::{
    Variable, Divide, SafeDivide,
    VariableExecutor, DivideExecutor, SafeDivideExecutor,
};

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    // 1. Create the engine
    let temp_dir = tempfile::tempdir()?;
    let mut engine = Engine::<DefaultConfig>::new_with(
        Plugin::default(),
        RocksDB::factory(temp_dir.path()),
        SeededStableHasherBuilder::<Sip128Hasher>::new(0),
    )?;

    // 2. Register executors
    let divide_executor = Arc::new(DivideExecutor::new());
    let safe_divide_executor = Arc::new(SafeDivideExecutor::new());

    engine.register_executor(divide_executor.clone());
    engine.register_executor(safe_divide_executor.clone());

    // 3. Wrap in Arc for shared ownership
    let engine = Arc::new(engine);

    // 4. Set input values
    {
        let mut input_session = engine.input_session();
        input_session.set_input(Variable::A, 42);
        input_session.set_input(Variable::B, 2);
    }

    // 5. Create tracked engine for querying
    let tracked = engine.tracked();

    // 6. Ready to execute queries!
    println!("Setup complete!");

    Ok(())
}

Configuration Options

QBICE supports custom configurations via the Config trait. We have provided a sensible default configuration called DefaultConfig.

#![allow(unused)]
fn main() {
use qbice::DefaultConfig;
let mut engine = Engine::<DefaultConfig>::new_with(...)?;
}

For advanced use cases, you can implement your own Config type to customize behavior.

Lifetime Management

Key points about engine lifetime:

Engine - Owns the database and executor registry
Arc<Engine> - Shared ownership, can be cloned and passed around
TrackedEngine - Lightweight wrapper, cheap to clone
New TrackedEngine - Create a new one after updating inputs

Typical pattern:

#![allow(unused)]
fn main() {
// The engine is wrapped in Arc, so no mutable access is needed
{
    let tracked = engine.tracked();
    // Use tracked for queries...
} // Drop tracked

// Create a new input session to update inputs
{
    let mut input_session = engine.input_session();
    // Update inputs...
}
}

Key Takeaways

The engine requires a plugin, database factory, and hasher builder
Register executors with register_executor()
Set input values via input_session()
Convert to Arc<Engine> and call tracked() to execute queries
TrackedEngine has an associated timestamp; create a new one after input updates

Next, we’ll execute some queries and see incremental computation in action!

Executing Queries

Now that we’ve set up the engine, let’s execute some queries and see QBICE’s incremental computation in action!

Basic Query Execution

Executing a query is straightforward—call query() on a TrackedEngine:

#![allow(unused)]
fn main() {
let tracked = engine.tracked();

let result = tracked.query(&SafeDivide {
    numerator: Variable::A,
    denominator: Variable::B,
}).await;

println!("SafeDivide(A, B) = {:?}", result); // Output: SafeDivide(A, B) = Some(21)
}

Remember, we set Variable::A = 42 and Variable::B = 2 in our input session, so 42 / 2 = 21.

Verifying Incremental Computation

Let’s prove QBICE is actually caching results. Remember we added call counters to our executors:

#![allow(unused)]
fn main() {
// Execute some queries
let tracked = engine.tracked();

tracked.query(&Divide {
    numerator: Variable::A,
    denominator: Variable::B,
}).await;

tracked.query(&SafeDivide {
    numerator: Variable::A,
    denominator: Variable::B,
}).await;

// Check call counts
println!("Divide called: {} times", divide_executor.call_count.load(Ordering::SeqCst));
println!("SafeDivide called: {} times", safe_divide_executor.call_count.load(Ordering::SeqCst));
}

Expected output:

Divide called: 1 times
SafeDivide called: 1 times

The counts didn’t increase! QBICE returned cached results because nothing changed.

Querying with Different Keys

Each unique query key is tracked separately:

#![allow(unused)]
fn main() {
let tracked = engine.tracked();

// These are different queries (different keys)
let ab = tracked.query(&Divide {
    numerator: Variable::A,
    denominator: Variable::B,
}).await;

let aa = tracked.query(&Divide {
    numerator: Variable::A,
    denominator: Variable::A,
}).await;

println!("Divide(A, B) = {}", ab); // 21
println!("Divide(A, A) = {}", aa); // 1

// Both queries were executed (check the call count)
println!("Divide called: {} times", divide_executor.call_count.load(Ordering::SeqCst));
}

Expected output:

Divide called: 2 times

QBICE distinguishes between Divide { numerator: A, denominator: A } and Divide { numerator: A, denominator: B } because they have different keys.

Async Concurrent Execution

Since queries are async, you can execute multiple independent queries concurrently:

#![allow(unused)]
fn main() {
use tokio::join;

let tracked = engine.tracked();

// Execute multiple queries in parallel
let (result1, result2) = join!(
    tracked.query(&Divide { numerator: Variable::A, denominator: Variable::B }),
    tracked.query(&SafeDivide { numerator: Variable::A, denominator: Variable::B }),
);

println!("Divide(A, B) = {}", result1);     // 21
println!("SafeDivide(A, B) = {:?}", result2); // Some(21)
}

QBICE can safely execute these in parallel, handling any shared dependencies automatically.

Complete Example

Here’s a complete example putting it all together:

use std::sync::Arc;
use std::sync::atomic::Ordering;
use qbice::{
    Engine, DefaultConfig,
    serialize::Plugin,
    stable_hash::{SeededStableHasherBuilder, Sip128Hasher},
    storage::kv_database::rocksdb::RocksDB,
};

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let temp_dir = tempfile::tempdir()?;
    let mut engine = Engine::<DefaultConfig>::new_with(
        Plugin::default(),
        RocksDB::factory(temp_dir.path()),
        SeededStableHasherBuilder::<Sip128Hasher>::new(0),
    )?;

    let divide_executor = Arc::new(DivideExecutor::new());
    let safe_divide_executor = Arc::new(SafeDivideExecutor::new());

    engine.register_executor(Arc::new(VariableExecutor));
    engine.register_executor(divide_executor.clone());
    engine.register_executor(safe_divide_executor.clone());

    // Wrap engine in Arc
    let engine = Arc::new(engine);

    // Set initial values
    {
        let mut input_session = engine.input_session();
        input_session.set_input(Variable::A, 42);
        input_session.set_input(Variable::B, 2);
    }

    let tracked = engine.tracked();

    // Execute queries
    println!("=== First Execution ===");
    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;
    println!("SafeDivide(A, B) = {:?}", result);
    println!("Divide called: {} times", divide_executor.call_count.load(Ordering::SeqCst));
    println!("SafeDivide called: {} times", safe_divide_executor.call_count.load(Ordering::SeqCst));

    // Execute again (should use cache)
    println!("\n=== Second Execution (cached) ===");
    let result2 = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;
    println!("SafeDivide(A, B) = {:?}", result2);
    println!("Divide called: {} times", divide_executor.call_count.load(Ordering::SeqCst));
    println!("SafeDivide called: {} times", safe_divide_executor.call_count.load(Ordering::SeqCst));

    Ok(())
}

Expected output:

=== First Execution ===
SafeDivide(A, B) = Some(21)
Divide called: 1 times
SafeDivide called: 1 times

=== Second Execution (cached) ===
SafeDivide(A, B) = Some(21)
Divide called: 1 times
SafeDivide called: 1 times

Key Takeaways

Use tracked.query(&query_key) to execute queries
Results are automatically cached
Same query keys return cached results without re-execution
Different query keys are tracked separately
Async execution allows for concurrent query processing
Dependencies are tracked automatically

Next, we’ll learn how to update inputs and observe incremental recomputation!

Updating Inputs

The real power of incremental computation shines when inputs change. QBICE automatically determines what needs to be recomputed and what can remain cached. Let’s see how this works!

Updating Input Values

To update inputs, create a new input session. Note that the engine must be wrapped in Arc to call input_session():

#![allow(unused)]
fn main() {
// First execution
{
    let tracked = engine.tracked();
    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;
    println!("SafeDivide(A, B) = {:?}", result); // Some(21)
} // Drop tracked

// Update input (engine is already in Arc)
{
    let mut input_session = engine.input_session();
    input_session.set_input(Variable::A, 84); // Changed from 42 to 84
} // Changes committed when dropped

// Query again
{
    let tracked = engine.tracked();
    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;
    println!("SafeDivide(A, B) = {:?}", result); // Some(42)
}
}

Observing Incremental Recomputation

Let’s verify QBICE’s incremental computation with an interesting example that tracks executor call counts.

#![allow(unused)]
fn main() {
use std::sync::atomic::Ordering;

// Reset call counters
divide_executor.call_count.store(0, Ordering::SeqCst);
safe_divide_executor.call_count.store(0, Ordering::SeqCst);

// Wrap engine in Arc (required for input_session)
let engine = Arc::new(engine);

// Set up initial state: A=42, B=2
{
    let mut input_session = engine.input_session();
    input_session.set_input(Variable::A, 42);
    input_session.set_input(Variable::B, 2);
}

// Execute SafeDivide query
{
    let tracked = engine.tracked();

    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;

    println!("SafeDivide(A, B) = {:?}", result); // Some(21)
}

println!("Initial execution (A=42, B=2):");
println!("  Divide called: {}", divide_executor.call_count.load(Ordering::SeqCst));
println!("  SafeDivide called: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));
// Output: Divide: 1, SafeDivide: 1
}

Now let’s change B to 0 to trigger division by zero:

#![allow(unused)]
fn main() {
// Change B to 0 (engine is already in Arc)
{
    let mut input_session = engine.input_session();
    input_session.set_input(Variable::B, 0);
}

// Query again
{
    let tracked = engine.tracked();

    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;

    println!("SafeDivide(A, B) = {:?}", result); // None
}

println!("After changing B to 0:");
println!("  Divide called: {}", divide_executor.call_count.load(Ordering::SeqCst));
println!("  SafeDivide called: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));
// Output: Divide: 1, SafeDivide: 2
}

Notice that:

SafeDivide was executed again (count increased from 1 to 2)
Divide was NOT executed (count stayed at 1)
This is because SafeDivide returns early when denominator is 0

Now let’s change B back to 2:

#![allow(unused)]
fn main() {
// Change B back to 2
{
    let mut input_session = engine.input_session();
    input_session.set_input(Variable::B, 2);
}

// Query again
{
    let tracked = engine.tracked();

    let result = tracked.query(&SafeDivide {
        numerator: Variable::A,
        denominator: Variable::B,
    }).await;

    println!("SafeDivide(A, B) = {:?}", result); // Some(21)
}

println!("After changing B back to 2:");
println!("  Divide called: {}", divide_executor.call_count.load(Ordering::SeqCst));
println!("  SafeDivide called: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));
// Output: Divide: 1, SafeDivide: 3
}

This demonstrates QBICE’s incremental recomputation:

SafeDivide executed again (count: 2 → 3)
Divide still didn’t execute (count stayed at 1)
Even though B changed, its value is back to 2, same as the original
Divide’s cached result from the first execution is still valid!
QBICE detects this via fingerprint comparison and reuses the cached value

Understanding Dirty Propagation

When you change an input, QBICE performs dirty propagation:

The changed input is marked dirty
All queries that depend on it are marked dirty (transitively)
When a dirty query is requested, it checks its dependencies
If a dependency’s value hasn’t actually changed (via fingerprint comparison), recomputation may stop

In our example above, when we changed B from 0 back to 2:

B was marked dirty
Divide(A, B) was marked dirty (depends on B)
SafeDivide(A, B) was marked dirty (depends on Divide)
When SafeDivide executed, it sees that Divide is dirty
Divides checks its dependencies with what they were before:
- Variable::A is unchanged (42)
- Variable::B is unchanged (2)
Since both inputs are the same as before, Divide reuses its cached result
Thus, Divide’s call count remains at 1 throughout

Batched Updates

You can update multiple inputs at once:

#![allow(unused)]
fn main() {
{
    let mut input_session = engine.input_session();
    input_session.set_input(Variable::A, 100);
    input_session.set_input(Variable::B, 5);
} // All changes committed atomically
}

Complete Incremental Example

Here’s a complete example demonstrating incremental computation:

use std::sync::Arc;
use std::sync::atomic::Ordering;

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let temp_dir = tempfile::tempdir()?;
    let mut engine = Engine::<DefaultConfig>::new_with(
        Plugin::default(),
        RocksDB::factory(temp_dir.path()),
        SeededStableHasherBuilder::<Sip128Hasher>::new(0),
    )?;

    let divide_executor = Arc::new(DivideExecutor::new());
    let safe_divide_executor = Arc::new(SafeDivideExecutor::new());

    engine.register_executor(Arc::new(VariableExecutor));
    engine.register_executor(divide_executor.clone());
    engine.register_executor(safe_divide_executor.clone());

    // Wrap engine in Arc
    let engine = Arc::new(engine);

    // Initial setup
    {
        let mut input_session = engine.input_session();
        input_session.set_input(Variable::A, 42);
        input_session.set_input(Variable::B, 2);
    }

    // Computation 1: Initial A=42, B=2
    println!("=== Initial Computation (A=42, B=2) ===");
    {
        let tracked = engine.tracked();
        let result = tracked.query(&SafeDivide {
            numerator: Variable::A,
            denominator: Variable::B,
        }).await;
        println!("SafeDivide(A, B) = {:?}", result);
    }
    println!("Divide executions: {}", divide_executor.call_count.load(Ordering::SeqCst));
    println!("SafeDivide executions: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));

    // Update B to 0 (division by zero!)
    println!("\n=== Update B to 0 ===");
    {
        let mut input_session = engine.input_session();
        input_session.set_input(Variable::B, 0);
    }

    // Computation 2: SafeDivide returns None
    {
        let tracked = engine.tracked();
        let result = tracked.query(&SafeDivide {
            numerator: Variable::A,
            denominator: Variable::B,
        }).await;
        println!("SafeDivide(A, B) = {:?}", result);
    }
    println!("Divide executions: {}", divide_executor.call_count.load(Ordering::SeqCst));
    println!("SafeDivide executions: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));

    // Update B back to 2 (original value!)
    println!("\n=== Update B back to 2 ===");
    {
        let mut input_session = engine.input_session();
        input_session.set_input(Variable::B, 2);
    }

    // Computation 3: SafeDivide returns Some(21) again
    {
        let tracked = engine.tracked();
        let result = tracked.query(&SafeDivide {
            numerator: Variable::A,
            denominator: Variable::B,
        }).await;
        println!("SafeDivide(A, B) = {:?}", result);
    }
    println!("Divide executions: {}", divide_executor.call_count.load(Ordering::SeqCst));
    println!("SafeDivide executions: {}", safe_divide_executor.call_count.load(Ordering::SeqCst));

    Ok(())
}

Expected output:

=== Initial Computation (A=42, B=2) ===
SafeDivide(A, B) = Some(21)
Divide executions: 1
SafeDivide executions: 1

=== Update B to 0 ===
SafeDivide(A, B) = None
Divide executions: 1
SafeDivide executions: 2

=== Update B back to 2 ===
SafeDivide(A, B) = Some(21)
Divide executions: 1
SafeDivide executions: 3

Graph Illustration

To illustrate, this is how compoutation graph looks like on the first run:

                  Some(21)
                     |
               SafeDivide(A, B)---------+
                     |                  |
                     21                 2
                     |                  |
           +-----Divide(A, B)------+    |
           |                       |    |
           42                      2    |
           |                       |    |
        Variable::A             Variable::B
           |                         |
           42                        2

Note that each edge represents a dependency and it records the value that it saw at that time.

Next, when we change B to 0:

                  Some(21)
                     |
               SafeDivide(A, B)---------+
                     |                  |
                     21*                2*
                     |                  |
           +-----Divide(A, B)------+    |
           |                       |    |
           42                      2*   |
           |                       |    |
        Variable::A             Variable::B
           |                         |
           42                        0

Here we mark the dirtied edges with a *. When we changed B to 0, all transitive edges were marked dirty.

Here when we query for SafeDivide(A, B), it sees that its dependency Divide(A, B) and Variable::B are dirty, so it recomputes.

                   None
                     |
               SafeDivide(A, B)---------+
                                        |
                                        0
                                        |
           +-----Divide(A, B)------+    |
           |                       |    |
           42                      2*   |
           |                       |    |
        Variable::A             Variable::B
           |                         |
           42                        0

Here, SafeDivide returns early because denominator is 0, so Divide is never executed. Note that the edge from Divide(A, B) to Variable::B remains dirty.

Finally, when we change B back to 2:

                  Some(21)
                     |
               SafeDivide(A, B)---------+
                                        |
                                        2*
                                        |
           +-----Divide(A, B)------+    |
           |                       |    |
           42                      2*   |
           |                       |    |
        Variable::A             Variable::B
           |                         |
           42                        2

When SafeDivide executes, it sees that Variable::B is dirty, so it recomputes, which means Divide is also invoked.

However, according to above graph, the last time Divide executed, both its inputs (Variable::A and Variable::B) had the same values (42 and 2 respectively). Since nothing has changed, Divide reuses its cached result and does not execute again.

Resulting in the final graph:

                  Some(21)
                     |
               SafeDivide(A, B)---------+
                     |                  |
                     21*                2*
                     |                  |
           +-----Divide(A, B)------+    |
           |                       |    |
           42                      2*   |
           |                       |    |
        Variable::A             Variable::B
           |                         |
           42                        2

Key Takeaways

Drop the old TrackedEngine and create a new one after updating inputs
Create a new input session to update values
QBICE automatically tracks which queries are affected
Only queries that depend on changed inputs are recomputed
Fingerprint-based comparison prevents unnecessary recomputation
Multiple inputs can be updated in a single session

What’s Next?

You’ve completed the tutorial! You now know how to:

Define queries and implement executors
Set up the engine and register components
Execute queries and build dependency graphs
Update inputs and leverage incremental computation

For deeper understanding, continue to the Reference section to learn about each component in detail, or explore Advanced Topics for optimization techniques like firewall and projection queries.

Firewall and Projection Queries

Firewall queries and projection queries are advanced optimization techniques that work together to provide fine-grained change detection and prevent unnecessary dirty propagation in dense dependency graphs. They’re particularly useful for expensive global analysis queries that have many dependents.

The Problem: Chokepoints

Consider a compiler that performs global type analysis. This analysis:

Depends on many input files
Produces a large type table
Is depended upon by hundreds of downstream queries

When any input file changes:

The global analysis is marked dirty
All downstream queries are marked dirty (transitively)
On next execution, hundreds of queries need verification

This creates a chokepoint where a single change causes excessive dirty propagation.

The Solution: Firewalls

A firewall query acts as a boundary that limits dirty propagation:

Input Changes
    ↓
Firewall Query (checked first)
    ↓ (only if result changed)
Downstream Queries

When an input changes:

Dirty propagation stops at the firewall
When the firewall is requested, it’s recomputed
Only if the firewall’s output changes does dirty propagation continue

Defining a Firewall Query

Mark a query as a firewall by overriding execution_style():

#![allow(unused)]
fn main() {
use qbice::{Query, ExecutionStyle};

#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GlobalTypeAnalysis {
    // Input parameters
}

impl Query for GlobalTypeAnalysis {
    type Value = TypeTable;  // Large result

    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Firewall
    }
}
}

How Firewalls Work

Without Firewall

Input → Analysis → [100 downstream queries all marked dirty]

When input changes:

Analysis marked dirty
100 queries marked dirty
On next query, must verify all 100 queries

With Firewall

Input → Analysis [FIREWALL] → [100 downstream queries]

When input changes:

Analysis marked dirty
Downstream queries NOT marked dirty
On next query:
1. Analysis is recomputed
2. If result unchanged, return cached value
3. Downstream queries remain clean!

Example: Global Analysis

#![allow(unused)]
fn main() {
use std::collections::HashMap;

#[derive(Debug, Clone, StableHash)]
pub struct TypeTable {
    pub types: HashMap<ID, Type>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GlobalTypeAnalysis;

impl Query for GlobalTypeAnalysis {
    type Value = Arc<TypeTable>;

    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Firewall
    }
}

pub struct GlobalTypeAnalysisExecutor;

impl<C: Config> Executor<GlobalTypeAnalysis, C> for GlobalTypeAnalysisExecutor {
    async fn execute(
        &self,
        _query: &GlobalTypeAnalysis,
        engine: &TrackedEngine<C>,
    ) -> TypeTable {
        // This is expensive and depends on many inputs
        let files = engine.query(&GetAllSourceFiles).await;

        let mut types = HashMap::new();
        for file in files {
            let file_types = engine.query(&ParseFile {
                path: file.path.clone(),
            }).await;
            types.extend(file_types);
        }

        TypeTable { types }
    }
}
}

Downstream Query

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetFunctionType {
    pub function_name: ID,
}

impl Query for GetFunctionType {
    type Value = Option<Type>;
}

impl<C: Config> Executor<GetFunctionType, C> for GetFunctionTypeExecutor {
    async fn execute(
        &self,
        query: &GetFunctionType,
        engine: &TrackedEngine<C>,
    ) -> Option<Type> {
        // Depends on the firewall
        let table = engine.query(&GlobalTypeAnalysis).await;
        table.types.get(&query.function_name).cloned()
    }
}
}

Transitive Firewall Edges

Queries that transitively depend on a firewall maintain special transitive firewall edges:

Firewall
    ↓
  Query A
    ↓
  Query B  ← has transitive edge to Firewall

When Query B is requested:

It first checks the Firewall directly
If Firewall changed, dirty flags propagate from Firewall → A → B
Then normal verification continues

This ensures correctness while limiting dirty propagation.

When to Use Firewalls

Firewall is best when there are many dependents on the firewall query, making dirty propagation traversing large portions of the graph costly.

When NOT to Use Firewalls

Avoid firewalls when:

Too much firewalls - Extra memory overhead for maintaining firewall edges
Few dependents - No chokepoint exists

Trade-offs

Benefits

Reduced dirty propagation - Potentially thousands of queries stay clean
Fewer verifications - Less work during repairation

Costs

Increased complexity - More complex dependency tracking
Memory overhead - Transitive firewall edges stored

Projection Queries

Projection queries work together with firewall queries to provide fine-grained change detection. They solve the over-invalidation problem by reading specific slices of large firewall results.

The Problem: Over-Invalidation

Consider a firewall query that produces a large result:

#![allow(unused)]
fn main() {
impl Query for GlobalTypeTable {
    type Value = Arc<HashMap<ID, Type>>;  // 1000+ entries
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Firewall
    }
}
}

Downstream queries typically read just one entry:

#![allow(unused)]
fn main() {
impl<C: Config> Executor<GetFunctionType, C> for GetFunctionTypeExecutor {
    async fn execute(&self, query: &GetFunctionType, engine: &TrackedEngine<C>) -> Option<Type> {
        let table = engine.query(&GlobalTypeTable).await;
        table.get(&query.function_name).cloned()  // Only reads ONE entry!
    }
}
}

The problem:

A change affects one entry in the table
The firewall result “changed” (different hash)
All downstream queries are marked dirty
In reality, only small subset of downstream queries are actually affected

The Solution: Projections

Projection queries extract specific data from firewall/projection results:

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetFunctionType {
    pub function_name: ID,
}

impl Query for GetFunctionType {
    type Value = Option<Type>;

    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection  // Mark as projection!
    }
}
}

Key properties:

Must only depend on Firewall
Should be very fast (memory access, hash lookup, field access)
Extracts a small piece of a larger result

How Projections Work

Normal Flow (Without Projection)

Input changes
  ↓
Firewall recomputes (hash changes)
  ↓
All downstream marked dirty

With Projection

Input changes
  ↓
Firewall recomputes (hash changes)
  ↓
Projection recomputes (checks specific slice)
  ↓
Only if projection's result changed → mark downstream dirty

The projection is re-executed immediately when the firewall changes. If the projection’s specific slice hasn’t changed, dirty propagation stops.

Example: Type Table

Firewall Query

#![allow(unused)]
fn main() {
use std::collections::HashMap;

#[derive(Debug, Clone, StableHash)]
pub struct TypeTable {
    pub types: HashMap<ID, Type>,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GlobalTypeTable;

impl Query for GlobalTypeTable {
    type Value = Arc<TypeTable>;  // Use Arc for cheap cloning

    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Firewall
    }
}
}

Projection Query

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetFunctionType {
    pub function_name: ID,
}

impl Query for GetFunctionType {
    type Value = Option<Type>;

    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

impl<C: Config> Executor<GetFunctionType, C> for GetFunctionTypeExecutor {
    async fn execute(
        &self,
        query: &GetFunctionType,
        engine: &TrackedEngine<C>,
    ) -> Option<Type> {
        // Very fast: just a hash lookup
        let table = engine.query(&GlobalTypeTable).await;
        table.types.get(&query.function_name).cloned()
    }
}
}

Downstream Query

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct TypeCheckFunction {
    pub function_name: ID,
}

impl Query for TypeCheckFunction {
    type Value = Result<(), TypeError>;
}

impl<C: Config> Executor<TypeCheckFunction, C> for TypeCheckFunctionExecutor {
    async fn execute(
        &self,
        query: &TypeCheckFunction,
        engine: &TrackedEngine<C>,
    ) -> Result<(), TypeError> {
        // Depends on projection
        let function_type = engine.query(&GetFunctionType {
            function_name: query.function_name.clone(),
        }).await;

        // Type check using the function's type
        type_check(function_type)
    }
}
}

Behavior

When a source file changes:

GlobalTypeTable (firewall) recomputes
Only functions in that file have new types
GetFunctionType (projection) re-executes for each dependent
If a specific function’s type didn’t change, its projection returns the same value
Most of the downstream TypeCheckFunction queries remain clean

Result: Only functions with changed types are re-checked.

Projection Rules

1. Only Depend on Firewall

#![allow(unused)]
fn main() {
// ✓ GOOD - depends on firewall
impl<C: Config> Executor<MyProjection, C> for MyProjectionExecutor {
    async fn execute(&self, query: &MyProjection, engine: &TrackedEngine<C>) -> Value {
        let firewall_result = engine.query(&MyFirewall).await;
        firewall_result.get_field()
    }
}

// ✗ BAD - depends on normal query
impl<C: Config> Executor<BadProjection, C> for BadProjectionExecutor {
    async fn execute(&self, query: &BadProjection, engine: &TrackedEngine<C>) -> Value {
        let normal = engine.query(&NormalQuery).await;  // NOT ALLOWED!
        normal.field
    }
}
}

2. Keep Projections Fast

Projections are re-executed during dirty propagation, so they must be very fast:

#![allow(unused)]
fn main() {
// ✓ GOOD - O(1) lookup
impl<C: Config> Executor<FastProjection, C> for FastProjectionExecutor {
    async fn execute(&self, query: &FastProjection, engine: &TrackedEngine<C>) -> Value {
        let table = engine.query(&FirewallTable).await;
        table.get(&query.key).cloned()  // Hash lookup
    }
}

// ✓ GOOD - field access
impl<C: Config> Executor<FieldProjection, C> for FieldProjectionExecutor {
    async fn execute(&self, query: &FieldProjection, engine: &TrackedEngine<C>) -> Value {
        let data = engine.query(&FirewallData).await;
        data.field.clone()  // Direct field access
    }
}

// ✗ BAD - expensive operation
impl<C: Config> Executor<ExpensiveProjection, C> for ExpensiveProjectionExecutor {
    async fn execute(&self, query: &ExpensiveProjection, engine: &TrackedEngine<C>) -> Value {
        let data = engine.query(&FirewallData).await;
        data.items.iter()
            .filter(|item| expensive_check(item))  // TOO SLOW!
            .collect()
    }
}
}

3. Extract Small Slices

Projections should return small portions of the firewall result:

#![allow(unused)]
fn main() {
// ✓ GOOD - returns one item
impl Query for GetItem {
    type Value = Option<Item>;
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

// ✓ GOOD - returns small subset
impl Query for GetItemSubset {
    type Value = Vec<Item>;  // Small vec
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

// ✗ BAD - returns entire result
impl Query for GetAllItems {
    type Value = Vec<Item>;  // Entire table!
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection  // Pointless!
    }
}
}

Common Patterns

Map Lookup

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetValue {
    pub key: ID,
}

impl Query for GetValue {
    type Value = Option<Value>;
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

impl<C: Config> Executor<GetValue, C> for GetValueExecutor {
    async fn execute(&self, query: &GetValue, engine: &TrackedEngine<C>) -> Option<Value> {
        let map = engine.query(&GlobalMap).await;
        map.get(&query.key).cloned()
    }
}
}

Field Access

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetConfig {
    pub field: ConfigField,
}

impl Query for GetConfig {
    type Value = ConfigValue;
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

impl<C: Config> Executor<GetConfig, C> for GetConfigExecutor {
    async fn execute(&self, query: &GetConfig, engine: &TrackedEngine<C>) -> ConfigValue {
        let config = engine.query(&GlobalConfig).await;
        match query.field {
            ConfigField::Timeout => config.timeout,
            ConfigField::MaxRetries => config.max_retries,
            // ...
        }
    }
}
}

Index Access

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq, Eq, Hash, StableHash, Identifiable, Encode, Decode)]
pub struct GetArrayElement {
    pub index: usize,
}

impl Query for GetArrayElement {
    type Value = Option<Element>;
    fn execution_style() -> ExecutionStyle {
        ExecutionStyle::Projection
    }
}

impl<C: Config> Executor<GetArrayElement, C> for GetArrayElementExecutor {
    async fn execute(&self, query: &GetArrayElement, engine: &TrackedEngine<C>) -> Option<Element> {
        let array = engine.query(&GlobalArray).await;
        array.get(query.index).cloned()
    }
}
}

Performance Trade-offs

Benefits

Fine-grained invalidation - Only truly affected queries recompute
Reduced recomputation - Could save thousands of verifications
Composable - Build chains of projections

Costs

Extra executions - Projections run during dirty propagation
More queries - Need projection queries in addition to normal queries
Increased complexity - More query types to manage

The trade-off is worth it when:

Cost of projection re-execution < Cost of recomputing downstream queries

Persistence

QBICE automatically persists query results to disk, allowing computation state to survive across program restarts. This chapter explains how persistence works and how to use it effectively.

How It Works

When you execute a query, QBICE:

Computes the result
Serializes the key and value
Stores them in the database
Records metadata (fingerprint, timestamp, etc.)

On subsequent runs:

Engine loads existing data from the database
Cached results are available immediately
Only changed queries need recomputation

Database Backends

QBICE supports pluggable storage backends:

RocksDB (Recommended)

Production-ready embedded database with excellent performance:

#![allow(unused)]
fn main() {
use qbice::storage::kv_database::rocksdb::RocksDB;

let mut engine = Engine::<DefaultConfig>::new_with(
    Plugin::default(),
    RocksDB::factory("/path/to/db"),
    hasher,
)?;
}

Pros:

Battle-tested in production
Excellent performance
Good compression
ACID guarantees

Cons:

Larger binary size
C++ dependency

fjall

Rust-native alternative:

#![allow(unused)]
fn main() {
use qbice::storage::kv_database::fjall::Fjall;

let mut engine = Engine::<DefaultConfig>::new_with(
    Plugin::default(),
    Fjall::factory("/path/to/db"),
    hasher,
)?;
}

Pros:

Pure Rust
Smaller binary
Simpler dependencies

Cons:

Less mature
Potentially lower performance (Could be tuned to this use case, if you are interested in helping please reach out :D )

Database Location

Development

Use temporary directories for testing:

#![allow(unused)]
fn main() {
use tempfile::tempdir;

let temp_dir = tempdir()?;
let mut engine = Engine::<DefaultConfig>::new_with(
    Plugin::default(),
    RocksDB::factory(temp_dir.path()),
    hasher,
)?;

// Database deleted when temp_dir is dropped
}

Serialization

Query keys and values must implement Encode and Decode:

#![allow(unused)]
fn main() {
use qbice::{Encode, Decode};

#[derive(
    Debug, Clone, PartialEq, Eq, Hash,
    StableHash, Identifiable,
    Encode, Decode,  // Required for persistence
)]
pub struct MyQuery {
    pub id: u64,
    pub name: String,
}

#[derive(Debug, Clone, StableHash, Encode, Decode)]
pub struct MyValue {
    pub result: String,
    pub metadata: Metadata,
}
}

Custom Serialization

For types that don’t implement Encode/Decode, wrap them or use newtype pattern:

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, StableHash)]
pub struct MyValue {
    pub data: ThirdPartyType,  // Doesn't implement Encode/Decode
}

// Implement manual serialization
impl Encode for MyValue {
    fn encode<E: Encoder + ?Sized>(
        &self,
        encoder: &mut E,
        plugin: &Plugin,
        session: &mut Session,
    ) -> std::io::Result<()> {
        // Custom encoding logic
    }
}

impl Decode for MyValue {
    fn decode<D: Decoder + ?Sized>(
        decoder: &mut D,
        plugin: &Plugin,
        session: &mut Session,
    ) -> std::io::Result<Self> {
        // Custom decoding logic
    }
}
}

Schema Evolution

Generally, we provide no guarantees for schema between versions at all. If you change the structure of your queries or values, you must clear the database to avoid runtime panics.

Garbage Collection

Currently, QBICE still doesn’t provide built-in garbage collection for the database. We plan to add this feature in the future.

We imagine that users will specify nodes where you normally use it, and QBICE will periodically clean up unreachable entries from the database.

Keyboard shortcuts

QBICE - Query-Based Incremental Computation Engine