kermit_algos/
lib.rs

1//! Join algorithms for Kermit's relational algebra engine.
2//!
3//! Implements the [Leapfrog Triejoin](https://arxiv.org/abs/1210.0481) algorithm,
4//! which performs worst-case optimal multi-way joins over trie-structured
5//! relations. The algorithm is generic over any data structure that implements
6//! [`TrieIterable`](kermit_iters::TrieIterable).
7#![deny(missing_docs)]
8
9mod const_rewrite;
10mod hash_singleton;
11mod hash_trie_iter_kind;
12mod hash_triejoin;
13mod join_algo;
14mod leapfrog_join;
15mod leapfrog_triejoin;
16mod singleton;
17mod trie_iter_kind;
18
19use {clap::ValueEnum, std::str::FromStr};
20pub use {
21    const_rewrite::{rewrite_atoms, ConstSpec, RewriteError},
22    hash_singleton::SingletonHashTrieIter,
23    hash_trie_iter_kind::HashTrieIterKind,
24    hash_triejoin::HashTriejoin,
25    join_algo::JoinAlgo,
26    kermit_parser::JoinQuery,
27    leapfrog_triejoin::LeapfrogTriejoin,
28    singleton::SingletonTrieIter,
29    trie_iter_kind::TrieIterKind,
30};
31
32/// The available join algorithm implementations.
33///
34/// Used as a CLI argument to select which algorithm to run.
35#[derive(Copy, Clone, PartialEq, Eq, Debug, ValueEnum)]
36pub enum JoinAlgorithm {
37    /// The Hash Trie Join algorithm (SIGMOD 2020); see [`HashTriejoin`].
38    HashTriejoin,
39    /// The [Leapfrog Triejoin](https://arxiv.org/abs/1210.0481) algorithm;
40    /// see [`LeapfrogTriejoin`].
41    LeapfrogTriejoin,
42}
43
44impl FromStr for JoinAlgorithm {
45    type Err = String;
46
47    fn from_str(s: &str) -> Result<Self, Self::Err> {
48        match s {
49            | "hash_triejoin" => Ok(Self::HashTriejoin),
50            | "leapfrog_triejoin" => Ok(Self::LeapfrogTriejoin),
51            | _ => Err(format!("Invalid join algorithm: {}", s)),
52        }
53    }
54}
kermit_algos/lib.rs

kermit_algos/
lib.rs
