It's all about efficient range reads and seek operations. You can compute set operations pretty efficiently using sorted indices that support a "find next or gr

It's all about efficient range reads and seek operations. You can compute set operations pretty efficiently using sorted indices that support a "find next or greater" operation. For intersection, take the first value from the first set as the smallest candidate of the output set, then call call candidate := next(candidate) on each set, updating the candidate with the next smallest possible value, and adding it to the output set when a candidate was returned by all sets. The algorithm is worst case optimal up to a log factor, and can even be extended to perform generic constraint programming and multiway joins as a subset of that. Fascinatingly it's related to the DPLL algorithm for sat solving. http://erikdemaine.org/papers/SODA2000/ http://erikdemaine.org/papers/SODA2000/ https://arxiv.org/abs/1404.0703 https://arxiv.org/abs/1404.0703 https://arxiv.org/abs/1310.3314 https://arxiv.org/abs/1310.3314 https://arxiv.org/abs/1203.1952 https://arxiv.org/abs/1203.1952 https://arxiv.org/abs/1803.09930 https://arxiv.org/abs/1803.09930