Automatic Index Selection for Large-Scale Datalog Computation

Created on 2022-01-29T20:02:09-06:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

Works on Datalog compilers that work in different compilation passes.

Adds an analysis pass that looks at the loops generated by the compiler and propose indexes that would make those searches faster.

Detecting which indices to make to efficiently search relationships by using "chain coverage."

tl;dr optimal search involves indexes that make it fast to rule out mismatches and orienting the loops so the smallest loop comes first. there is a bunch of math to determine this.