Indexes for ADT branches?

[wkhan-figma]

Hi all, I was trying out Soufflé for some cross-domain graph reachability analysis. I was representing my nodes as e.g.

.type Node = CiJob { job : CiJob }
           | File { path : Path }
           /* ... */

and populated a relation like

.decl Dep(x : Node, y : Node)

But it seems like this relation is not indexed in the same way as if I had manually unpacked/flattened the ADT fields and passed them in. I got a substantial speedup by manually unpacking the relation like this:

.decl CiJobHasDep(job : CiJob, node : Node)
CiJobHasDep(job, node) :- HasDep($CiJob(job), node).

and then querying that relation instead when I wanted to know about CiJobs.

• In interpreted mode, this reduced the runtime from 80s to 4s when I added a couple of these indexes.
• Granted, it seems like this is not exactly equivalent to constructing an index on the original relation, because the original relation would still have a lot of tuples with cases other than $CiJob as the first element, but 80s seems like a substantial enough difference to suggest that it's not indexing at all?

Are ADTs branches indexed at present? Are there any other tricks to use here, so that I don't have to manually unpack each query I care about into its own "index" relation?

[quentin]

You are right, Soufflé currently does not index ADT or record fields. Manually unpacking relations is the simplest way to go.

adding @julienhenry

[arxanas]

Soufflé was great for rapid prototyping in many ways, but it was unfortunate for my goal because I have to do a bunch of work whenever I want to try out a different indexing strategy. For example, I was doing bipartite graph reachability, and it wasn't obvious which side would be better to "start" from for performance reasons, but switching between sides to test the required a bit of refactoring.

[arxanas]

(Different account)

For other readers: I ended up switching to ascent for my analysis (mostly a graph reachability problem).

• I suspect that it does index enum fields, based on the performance?
  • IIRC it traverses the AST to decide indexes, query plans, etc., so it seems plausible that it looks for pattern-matches on ADT cases.
• It requires values be Hash rather than Ord. Presumably this has an impact on performance somehow.
• It has a parallel mode.
  • I found the performance to be pretty variable even for repeats of the same analysis, ranging from 8–30 seconds. My guess is that it's non-determinism due to threading, but probably also Rust hash tables?
  • Performance was worse when I had smaller queries, going from like 10 seconds to 25 seconds, so presumably there's potential contention problems.
  • It's easy enough to switch between them.
• It has a few provided data structure to back transitive relation queries, but
  • I didn't find a convenient way to express "the transitive relation of only the subgraph starting/ending from these nodes".
  • They don't appear to support parallel mode.
• Pragmatically speaking, it's a lot easier for me to embed functionality with Ascent than Soufflé.
  • I had a great deal of difficulty getting the C++ compilation working on macOS (had to fiddle with the Cmake settings in Soufflé itself).
  • It seems a lot easier to do small functor stuff like string operations when you don't have to worry about FFI.
• Ascent doesn't seem to have a strong generic programming story, like Soufflé's comp.
  • There are macros in the Ascent DSL, but they can only stand in for expressions, not entire relations.
  • There are textual includes, but it doesn't look like they can be parametrized.
  • I don't know if you can directly use Rust macros.
  • There might be an encoding using Rust generics that I haven't thought of.
  • You can run arbitrary Rust code as part of the evaluation or a rule, so you could literally run another Ascent program, if that made sense for your use-case lol.
• Ascent doesn't seem to have choice-domain.
  • In my case, I just used the lattice feature to approximate it, and it seemed to perform fine for my use-case.
  • It might be possible to implement choice-domain on top of a custom data structure to back a relation.

Update 2025-09-20: Also posted this comment with more detail about Ascent: s-arash/ascent#70 (comment)

[arxanas]

Update: the Ascent authors clarify that it doesn't index ADTs either: s-arash/ascent#72 (comment). So the performance difference must be something else.

• I wonder if it's something incidental, like improved locality due to using a(n open-addressed?) hash table rather than a b-tree.
• It could just be that Ascent generates a better initial query plan than Soufflé. I recall that Soufflé's performance was significantly improved when I provided profiling information.
  • But the problem is that I can't get "partial" profiling information by terminating the slow run early (?), and I can't/don't want to wait for the slow run to complete, since it's an order of magnitude slower.
  • I vaguely recall that I tried applying the limit size directive to bound the runtime, but maybe Soufflé rejected the profile since it was generated with different options, or something like that?

Regardless, the "manual indexing" workaround in the original post does produce significant speedups, so still worth keeping in mind for anyone else who runs into the same problem.