lattices/ght/
colt.rs

1//! COLT from Wang/Willsey/Suciu
2
3use std::hash::Hash;
4
5use variadics::variadic_collections::VariadicCollection;
6use variadics::{PartialEqVariadic, SplitBySuffix, VariadicExt, var_expr, var_type};
7
8use crate::ght::{GeneralizedHashTrieNode, GhtGet, GhtInner, GhtLeaf};
9
10/// Data structure design for our COLT is unique.
11///
12/// In the paper, the COLT is an unbalanced trie that "grows upward" from leaves lazily
13/// on access via the `force` method.
14/// Unfortunately, unbalanced tries break our types: a node's type to be defined via the
15/// type of its children, recursively -- meaning all paths need to be the same type (and length)!
16///
17/// To work around this, our COLT is a variadic *list* GHTs (a forest) of increasing height,
18/// starting with a trie of height 0 and continuing until a trie of height |key| - 1.
19/// Our `force` method does not add a node above a leaf L as in the paper. Instead
20/// it `take`s L from the current trie and merges it into the next trie to the right which is 1 taller.
21//
22/// The following trait provides the behavior we need from the nodes in a COLT forest. Every
23/// `ColtForestNode` is a `GeneralizedHashTrieNode` with some extra methods.
24pub trait ColtForestNode: GeneralizedHashTrieNode {
25    /// result of `force`ing a node
26    type Force: GeneralizedHashTrieNode;
27
28    /// Force the generation of a parent node, as in the Wang/Willsey/Suciu COLT structure,
29    /// to be merged into the next trie to the right.
30    fn force(self) -> Option<Self::Force>;
31
32    /// Force the generation of a parent node but retain ref to this node
33    fn force_drain(&mut self) -> Option<Self::Force>;
34}
35
36// Force only acts on leaves
37impl<Head, Node> ColtForestNode for GhtInner<Head, Node>
38where
39    Head: 'static + Hash + Eq + Clone,
40    Node: 'static + ColtForestNode,
41    <Node as GeneralizedHashTrieNode>::Schema:
42        SplitBySuffix<var_type!(Head,  ...<Node as GeneralizedHashTrieNode>::SuffixSchema)>,
43{
44    type Force = Node; // where Node:GeneralizedHashTrieNode;
45    fn force(self) -> Option<Self::Force> {
46        None
47    }
48
49    fn force_drain(&mut self) -> Option<Self::Force> {
50        None
51    }
52}
53
54// Leaf case
55impl<Schema, Head, Rest, Storage> ColtForestNode
56    for GhtLeaf<Schema, var_type!(Head, ...Rest), Storage>
57where
58    Head: 'static + Clone + Hash + Eq,
59    Rest: 'static + Clone + Hash + Eq + VariadicExt + PartialEqVariadic,
60    Schema: 'static
61        + Hash
62        + Eq
63        + Clone
64        + VariadicExt
65        + PartialEqVariadic
66        + SplitBySuffix<var_type!(Head, ...Rest)>
67        + SplitBySuffix<Rest>,
68    <Schema as SplitBySuffix<(Head, Rest)>>::Prefix: Eq + Hash + Clone,
69    <Schema as SplitBySuffix<Rest>>::Prefix: Eq + Hash + Clone,
70    Storage: VariadicCollection<Schema = Schema> + Default + IntoIterator<Item = Schema>,
71    GhtLeaf<Schema, Rest, Storage>: GeneralizedHashTrieNode<Schema = Schema, Storage = Storage>,
72    GhtInner<Head, GhtLeaf<Schema, Rest, Storage>>:
73        GeneralizedHashTrieNode<Schema = Schema, Storage = Storage>,
74{
75    type Force = GhtInner<Head, GhtLeaf<Schema, Rest, Storage>>;
76    fn force(mut self) -> Option<Self::Force> {
77        let mut retval = Self::Force::default();
78        self.forced = true;
79        for row in self.into_iter().unwrap() {
80            retval.insert(row);
81        }
82        Some(retval)
83    }
84
85    fn force_drain(&mut self) -> Option<GhtInner<Head, GhtLeaf<Schema, Rest, Storage>>> {
86        let mut retval = Self::Force::default();
87        self.forced = true;
88        for row in self.elements.drain() {
89            retval.insert(row);
90        }
91        Some(retval)
92    }
93}
94
95/// Emulate the `get` and `iter` functions for a single Ght node
96/// [`GhtGet`] across a forest of `ColtForestNode`s.
97///
98/// The "current" `ColtGet` node (corresponding to the "current" `GhtGet` node) at depth
99/// d from the root is a variadic list of nodes, each at depth d in its their
100/// respective trie in the forest, Tries of height d or smaller are omitted,
101/// hence the first element in any `ColtGet` is a `GhtLeaf`.
102pub trait ColtGet {
103    /// Schema variadic: the schema of the relation stored in this COLT.
104    /// This type is the same in all Tries and nodes of the COLT.
105    type Schema: VariadicExt + Eq + Hash + Clone;
106    /// The type of Storage
107    /// This type is the same in all Tries and nodes of the COLT
108    type Storage: VariadicCollection;
109    /// `SuffixSchema` variadic: the suffix of the schema *from this node of the trie
110    /// downward*. The first entry in this variadic is of type Head.
111    /// This type is the same in all Tries of the COLT (but changes as we traverse downward)
112    type SuffixSchema: VariadicExt + Eq + Hash + Clone;
113    /// The type of the first column in the `SuffixSchema`
114    /// This type is the same in all Tries of the COLT (but changes as we traverse downward)
115    type Head: Eq + Hash;
116
117    /// Type returned by [`Self::get`].
118    type Get;
119
120    /// Following the spec in Wang/Willsey/Suciu, on an Inner node this retrieves the value
121    /// (child) associated with the given "head" key. It returns an `Option` containing a
122    /// reference to the value if found, or `None` if not found.
123    /// On a Leaf node, returns None.
124    fn get(self, head: &Self::Head) -> Self::Get;
125
126    /// Iterator for the "head" keys (from inner nodes) or nothing (from leaf nodes).
127    fn iter(&self) -> impl Iterator<Item = Self::Head>;
128}
129
130/// `ColtGet` without the first (head) trie.
131pub trait ColtGetTail<InnerToMerge>: ColtGet {
132    /// merge an inner node into the head of this tail of the forest
133    fn merge(&mut self, inner_to_merge: InnerToMerge);
134}
135
136impl<'a, Rest, Schema, SuffixSchema, Storage> ColtGet for var_type!(&'a mut GhtLeaf<Schema, SuffixSchema, Storage>, ...Rest)
137where
138    Rest: ColtGetTail<
139            <GhtLeaf<Schema, SuffixSchema, Storage> as ColtForestNode>::Force,
140            Storage = Storage,
141        >,
142    <Rest as ColtGet>::SuffixSchema: 'a,
143    GhtLeaf<Schema, SuffixSchema, Storage>: ColtForestNode,
144    Schema: Clone + Hash + Eq + VariadicExt,
145    SuffixSchema: Clone + Hash + Eq + VariadicExt,
146    Storage: VariadicCollection<Schema = Schema>,
147{
148    type Schema = Schema;
149    type Head = Rest::Head;
150    type SuffixSchema = SuffixSchema;
151    type Get = Rest::Get;
152    type Storage = Rest::Storage;
153
154    fn get(self, head: &Self::Head) -> Self::Get {
155        let (first, mut rest) = self;
156        let forced = first.force_drain().unwrap();
157        ColtGetTail::merge(&mut rest, forced);
158        Rest::get(rest, head)
159    }
160
161    fn iter(&self) -> impl Iterator<Item = Self::Head> {
162        std::iter::empty()
163    }
164}
165
166// we only merge in GhtInner<Head, GhtLeaf<_>> nodes, so this
167// should never be called.
168impl<'a, Rest, Schema, SuffixSchema, T, Storage> ColtGetTail<T> for var_type!(&'a mut GhtLeaf<Schema, SuffixSchema, Storage>, ...Rest)
169where
170    Rest: ColtGetTail<
171            <GhtLeaf<Schema, SuffixSchema, Storage> as ColtForestNode>::Force,
172            Storage = Storage,
173        >,
174    <Rest as ColtGet>::SuffixSchema: 'a,
175    GhtLeaf<Schema, SuffixSchema, Storage>: ColtForestNode,
176    Schema: Clone + Hash + Eq + VariadicExt,
177    SuffixSchema: Clone + Hash + Eq + VariadicExt,
178    Storage: VariadicCollection<Schema = Schema>,
179{
180    fn merge(&mut self, _inner_to_merge: T) {
181        panic!();
182    }
183}
184
185impl<'a, Head, Head2, Rest, Node> ColtGet for var_type!(&'a mut GhtInner<Head, GhtInner<Head2, Node>>, ...Rest)
186where
187    Rest: ColtGet<Head = Head>,
188    Head: Eq + Hash + Clone,
189    Head2: Eq + Hash + Clone,
190    Node: GeneralizedHashTrieNode,
191    GhtInner<Head, GhtInner<Head2, Node>>: GeneralizedHashTrieNode<
192            Head = Rest::Head,
193            SuffixSchema = Rest::SuffixSchema,
194            Schema = Rest::Schema,
195            Storage = Rest::Storage,
196        >,
197    GhtInner<Head2, Node>: GeneralizedHashTrieNode<Schema = Rest::Schema, Storage = Rest::Storage>,
198{
199    type Schema = Rest::Schema;
200    type Head = Rest::Head;
201    type SuffixSchema = Rest::SuffixSchema;
202    type Get = var_type!(&'a mut GhtInner<Head2, Node>, ...Rest::Get);
203    type Storage = Rest::Storage;
204
205    fn get(self, head: &Self::Head) -> Self::Get {
206        let (first, rest) = self;
207        // create a child entry here for this get, to absorb future forces
208        // TODO(mingwei): extra clone here if entry already exists.
209        let child = first.children.entry(head.clone()).or_default();
210        var_expr!(child, ...Rest::get(rest, head))
211    }
212
213    fn iter(&self) -> impl Iterator<Item = Self::Head> {
214        #[expect(
215            clippy::disallowed_methods,
216            reason = "nondeterministic iteration order, TODO(mingwei)"
217        )]
218        self.0.children.keys().cloned().chain(Rest::iter(&self.1))
219    }
220}
221
222impl<'a, Head, Rest, Schema, ValType, Storage> ColtGet for var_type!(&'a mut GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>, ...Rest)
223where
224    Rest: ColtGet<Head = Head>,
225    Head: Eq + Hash + Clone,
226    Schema: 'static + Eq + VariadicExt + Hash + Clone + SplitBySuffix<ValType> + PartialEqVariadic,
227    ValType: Eq + Hash + Clone + PartialEqVariadic,
228    Storage: VariadicCollection<Schema = Schema>,
229    <Schema as SplitBySuffix<ValType>>::Prefix: Eq + Hash + Clone,
230    GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>: GeneralizedHashTrieNode<Head = Head>
231        + GeneralizedHashTrieNode<Head = Rest::Head, Schema = Rest::Schema, Storage = Rest::Storage>
232        + GhtGet,
233    GhtLeaf<Schema, ValType, Storage>:
234        GeneralizedHashTrieNode<Schema = Rest::Schema, Storage = Rest::Storage> + GhtGet,
235{
236    type Schema = Rest::Schema;
237    type Head = Rest::Head;
238    type SuffixSchema = Rest::SuffixSchema;
239    type Get = var_type!(&'a mut GhtLeaf<Schema, ValType, Storage>, ...Rest::Get);
240    type Storage = Rest::Storage;
241
242    fn get(self, head: &Self::Head) -> Self::Get {
243        let (first, rest) = self;
244        let child = first.children.entry(head.clone()).or_default();
245        var_expr!(child, ...Rest::get(rest, head))
246    }
247
248    fn iter(&self) -> impl Iterator<Item = Self::Head> {
249        #[expect(
250            clippy::disallowed_methods,
251            reason = "nondeterministic iteration order, TODO(mingwei)"
252        )]
253        self.0.children.keys().cloned().chain(Rest::iter(&self.1))
254    }
255}
256
257impl<'a, Head, Rest, Schema, ValType, Storage>
258    ColtGetTail<GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>> for var_type!(&'a mut GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>, ...Rest)
259where
260    Rest: ColtGet<Head = Head, Schema = Schema, Storage = Storage>,
261    Head: Eq + Hash + Clone,
262    Schema: Eq + Hash + Clone + PartialEqVariadic,
263    ValType: Eq + Hash + Clone + PartialEqVariadic,
264    Storage: VariadicCollection<Schema = Schema>,
265    var_type!(&'a mut GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>, ...Rest):
266        ColtGet<Head = Head, Schema = Schema, Storage = Storage>,
267    GhtLeaf<Schema, ValType, Storage>: GeneralizedHashTrieNode<Schema = Schema>,
268    Schema: 'static + Eq + VariadicExt + Hash + Clone + SplitBySuffix<ValType> + PartialEqVariadic,
269    <Schema as SplitBySuffix<ValType>>::Prefix: Eq + Hash + Clone,
270    GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>:
271        GeneralizedHashTrieNode<Head = Head, Schema = Schema, Storage = Storage> + GhtGet,
272{
273    fn merge(&mut self, inner_to_merge: GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>) {
274        let (head, _rest) = self;
275        // can't use Merge with COLT bc columnstore is not a lattice!!
276        head.merge_node(inner_to_merge);
277    }
278}
279
280impl<'a, Head, Node> ColtGet for var_type!(&'a mut GhtInner<Head, Node>)
281where
282    GhtInner<Head, Node>: GeneralizedHashTrieNode,
283    Head: Clone + Eq + Hash,
284    Node: GeneralizedHashTrieNode,
285{
286    type Schema = <GhtInner<Head, Node> as GeneralizedHashTrieNode>::Schema;
287    type SuffixSchema = <GhtInner<Head, Node> as GeneralizedHashTrieNode>::SuffixSchema;
288    type Head = Head;
289    type Get = var_type!(&'a mut Node);
290    type Storage = Node::Storage;
291
292    fn get(self, head: &Self::Head) -> Self::Get {
293        let child = self.0.children.entry(head.clone()).or_default();
294        var_expr!(child)
295    }
296
297    fn iter(&self) -> impl Iterator<Item = Self::Head> {
298        #[expect(
299            clippy::disallowed_methods,
300            reason = "nondeterministic iteration order, TODO(mingwei)"
301        )]
302        self.0.children.keys().cloned()
303    }
304}
305impl<Head, Schema, ValType, Storage> ColtGetTail<GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>> for var_type!(&mut GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>)
306where
307    GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>:
308        GeneralizedHashTrieNode<Head = Head> + GhtGet,
309    GhtLeaf<Schema, ValType, Storage>: GeneralizedHashTrieNode<Schema = Schema, Storage = Storage>,
310    Head: Clone + Eq + Hash,
311    Schema: Clone + Eq + Hash + VariadicExt,
312    Storage: VariadicCollection<Schema = Schema>,
313{
314    fn merge(&mut self, inner_to_merge: GhtInner<Head, GhtLeaf<Schema, ValType, Storage>>) {
315        let (head, _rest) = self;
316        // can't use Merge with COLT bc columnstore is not a lattice!!
317        head.merge_node(inner_to_merge);
318    }
319}
lattices/ght/colt.rs

lattices/ght/
colt.rs
