Cottonwood Graph Query Engine

Christopher Besch, Fabian Tolksdorf, Leon Bruns, Thomas Hädicke • 4th September 2025

Cottonwood

Management

Week 1:
1. Design application architecture
2. Define inter-team interfaces
3. Define intra-team interfaces
4. Implement correctly
Week 2-4: Optimize

General Implementation Approach

Simple, fix interfaces
- Independent development
- Free to optimize implementation
Tests, debug_asserts,
no unsafe
- Rapid iteration
- Bugs easier to find

Focus on correctness
Focus on general optimizations (not edge cases)

Architecture Structure

DFA

(A) [-B-> (C)]{2,-} (D)

DFA Squashing

 (A) [-B-> (C)]{1,-} (C)
                            [-B-> (C)]{1,-} (D)

(A) [-B-> (C)]{2,-} (D)

Heuristic & Start Everwhere

() -->{1,-} () --> (A)
                        -B->{1,-} ()

Insight: Not all start positions equal
Heuristic

Idea: many restrictions at start
Approach: use DFA and rarity of labels
Restrictions: graph structure unkown

DFS uses startposition and turns arround

BFS and when to use it

() -->{1,-} ()
(A) -B->{1,-} (C)
(A) -B->{1,7} (C)
(A) [-B-> (M)]{1,-} (C)
... --> (A) [-B-> (M)]{1,-} (C)
not: (A) -B->{3,-} (C)

Optimization Benchmarks

Custom Memplus Benchmark

PAIRS ()-->()-->()-->()--> ...

memplus graph with query:

PAIRS ()--> ()-->()-->()-->(Champion)-->(Communicator)
                                [-->(Student)-->(Helper)-->()]{1,2} (Explorer)-->() -FEEDS->{4,6} ()-->()
                                [-FEEDS->()-->(Entrepreneur)]{4,-} ()

memplus: good to start at front, this query: added randomness to front → shows heuristic is good
other optimizations don't work with this query

Lessons learned

Getting work done in parallel & Test driven is fast
Great interfaces are great
Designing Heuristics is hard
Rust Ownership is challenging but
- Rust has great tooling
- Iterators are cool
- no UB; easier debugging