Jitabug

From brrr to BRRRRR

About

Jitabug is a query engine built to support fast execution of common execution stages typically found within search engines.
In particular, Jitabug currently focuses on posting lists which are large sequencies of monotonically increasing u32 document IDs.

At its core, Jitabug is a tracing JIT compiler built to be extremely low overhead and producing highly optimised SIMD assembly, and then automatically tune kernels and execution internals to the host machine's performance characteristics and overheads to maximise the performance.

Unlike what is typically done within search engines like Lucene and Tantivy, Jitabug has the concept of a query planner system which will pick different strategies based on the input structure and sizes itself meaning that even very complex queries become relatively cheap to materialize.

use jitabug::program::ProgramBuilder;
use jitabug::{Input, Jit};

fn main() {
    // Build the engine once for the host CPU. It detects CPU features and tunes
    // the SIMD kernels to the machine. `doc_space` tells the cost model how large
    // the corpus is so it can estimate input density and pick a backend. Tiny
    // inputs are interpreted directly, skipping the ~1us kernel compile that is
    // otherwise hard to amortize.
    let mut jit = Jit::builder().doc_space(63).build();

    // Posting lists: sorted, strictly increasing doc ids, one per search term.
    let rust = [1, 4, 5, 9, 12, 20, 33, 41];
    let systems = [4, 5, 7, 12, 15, 20, 41, 55];
    let archived = [9, 20, 33, 60];

    // Describe the query as a small DAG of set operations over the inputs.
    // Query: (rust AND systems) AND NOT archived
    let mut builder = ProgramBuilder::new();
    let rust_in = builder.input();
    let systems_in = builder.input();
    let archived_in = builder.input();
    let both = builder.and(rust_in, systems_in);
    let not_archived = builder.not(archived_in);
    let root = builder.and(both, not_archived);
    let program = builder.build(root).expect("valid query");

    // The engine optimises the query, picks a backend from the input shapes,
    // compiles it to native SIMD code (or interprets tiny inputs) and runs it. The
    // result is read back without materializing a doc id list up front.
    let outcome = jit
        .execute(
            &program,
            &[
                Input::List(&rust),
                Input::List(&systems),
                Input::List(&archived),
            ],
        )
        .expect("input count matches the program");

    println!("matches: {}", outcome.count());
    println!("doc ids: {:?}", outcome.doc_ids().collect::<Vec<_>>());
    // matches: 4
    // doc ids: [4, 5, 12, 41]
}