Fixpoint3.Phase.IndexSelection

Creates indexes for each RelSym in program, places them in memory and propagates the positions to Query operations. To create the appropriate indexes for a RelSym, it first collects the set of PrimitiveSearch for each RelSym in program and computes the minimal set of Searches needed for RelSym.

A Search (not to be confused with RamStmt.Search) describes the order in which entries in a tuple are ordered. These are used by indexes to store tuples for efficient retrieval in range queries. A search is represented a Vector[Int32] where the order is left-to-right in the vector.

In the example for PrimitiveSearch a naive algorithm would create an index for each primitive search occuring in the program. A better solution, due to Subotić, Pavle, et al. (Automatic Index Selection for Large-Scale Datalog Computation), is to find the minimal set of indexes needed for a relation. This is implemented in AutomaticIndexSelection. Thus, the program consisting of the 3 rules could produce the minimal set of searches to query relation B as {0 < 1 < 2, 0 < 2}.

Note: for relation A, since it has no body atoms with bound variables, no particular search should be created for it, and the single search 0 < 1 < 2 covers all its cases.

The searches returned by minIndex are expanded to encompass the whole tuple size of the relation. I.e., the search 0 < 2 gets expanded to 0 < 2 < 1.

Returns a new RamProgram where Search, Query and similar statements have been augmented with the memory position that the index they depend on will be placed.

For details about memory positions see lookupIndex.