I'm still stuck on this, so any advice would be helpful. As best as I can tell, there's some kind of combinatorial explosion going on in the compiler. A single one of my test cases, minimized as much as possible, is sitting at 160GB memory usage and 2+ hours of compile time at the moment (It hasn't yet completed).
I've tried a few things over the course of the past week:
- I streamlined the type-level algorithms that are getting used most, writing them by hand instead of going through the type-system lisp interpreter
- I reduced the number of columns that need to be considered to 5 at most, which is an upper bound on the length of my HLists (except for those that represent Lisp code)
- I tried to implement the set algebra routines in const generics instead of the type system; It mostly worked except for an ICE when I tried to integrate it into the rest of the system (part of
const_evaluatable_checked threw an "Unimplemented" error)
- I rented a huge-memory cloud server to try and brute-force the compilation through. (As part of this, I cleaned up the build process. Everything's in the
codd repo above now.)
I've also come up with a minimal change that triggers the problems. The unit test suite that includes the code below compiles in less than 2 minutes on my laptop, but adding the commented stanza runs into the OOM killer after 7+ minutes. The same result occurs if I use BTrees instead of vectors for the underlying data, which have a more complex query planner.
I suspect the trait solver is going into a wild goose chase that it shouldn't need to. There's presumably ways to prune its search tree by strategically adding explicit bounds. Without knowing how it really works, though, I'm just making blind changes and hoping for the best.
#[test]
fn test_peer_join() {
use crate::relation::{OpaqueRel,Insert};
use tylisp::sexpr_val;
col!{A: usize}
col!{B: usize}
col!{C: usize}
col!{D: usize}
col!{E: usize}
let mut left: OpaqueRel<Vec<sexpr!{A,B}>> = Default::default();
let mut right: OpaqueRel<Vec<sexpr!{C,B,D}>> = Default::default();
let mut lr: OpaqueRel<Vec<sexpr!{A,B,C,D}>> = Default::default();
let mut third: OpaqueRel<Vec<sexpr!{C,E}>> = Default::default();
left.insert(sexpr_val!{A(1),B(1),C(3)}).unwrap();
left.insert(sexpr_val!{A(2),B(2),C(7)}).unwrap();
left.insert(sexpr_val!{A(3),B(5),C(7)}).unwrap();
right.insert(sexpr_val!{D(1),B(1),C(3)}).unwrap();
right.insert(sexpr_val!{D(2),B(2),C(7)}).unwrap();
right.insert(sexpr_val!{D(3),B(5),C(7)}).unwrap();
third.insert(sexpr_val!{C(7),E(2)}).unwrap();
third.insert(sexpr_val!{C(3),E(3)}).unwrap();
let join = PeerJoin::<_,_,B>{
left: left.as_ref(),
right: right.as_ref(),
phantom: PhantomData
};
/*
let join = PeerJoin::<_,_,C>{
left: join.as_ref(),
right: third.as_ref(),
phantom: PhantomData
};
*/
assert_eq!(join.iter_all().count(), 3);
}