Specifically, the linked paper models indexes on a table as sets of n-dimensional volumes showing where rows aren't. It then gives a join algorithm that is asym

Specifically, the linked paper models indexes on a table as sets of n-dimensional volumes showing where rows aren't. It then gives a join algorithm that is asymptotically instance-optimal (up to a poly-log factor) ie better than any previous result. Unfortunately it relies on efficiently representing and querying the set of volumes built up during the query process and the data structure used in the paper is ridiculously impractical. I haven't seen an implementation yet that managed to tame the constant factors. Perhaps seeing how the OP models volumes/constraints would help.