7. Query Optimization

In Section 3 we described a straight-forward algorithm that employs exhaustive search to submit every possible mutation of a query to every checklet in the checklet coop. Obviously, with dozens of transformations and maybe hundreds of checklets this procedure will be prohibitively expensive.

In this section we will examine a more sophisticated search algorithm that explores the fact that queries, checklets, and transformations are all typed. To see how type-analysis can help us speed up the search, consider a situation where we have two checklets

where FloatExp checks for real exponentiation and FloatAdd checks for real addition, and two transformations

where Int2Float promotes an integer to a real and FlipPair commutes a pair.

Suppose the input query is $\ulcorner\hspace*{-2pt}$ (2.0,2)==>4.0 $\hspace*{-2pt}\urcorner$. This input has a signature of Map(Pair(Float,Int),Float), and therefore can be tested immediately against the FloatExp checklet. Similarly, by applying the Int2Float transformation, the query can be transformed into $\ulcorner\hspace*{-2pt}$ (2.0,2.0)==>4.0 $\hspace*{-2pt}\urcorner$, which matches the signature of FloatAdd, and therefore can be submitted to that checklet.

It is a simple observation that a query $\ulcorner\hspace*{-2pt}$ true==>1 $\hspace*{-2pt}\urcorner$(which has the type Map(Bool,Int)) can never match any of the checklets, regardless of which transformations are applied. Still, the algorithm in Section 3 would apply all possible combinations of transformations to $\ulcorner\hspace*{-2pt}$ true==>1 $\hspace*{-2pt}\urcorner$ and submit any generated query mutation to every checklet in the coop.

We will next show how precomputation can speed up searching by eliminating any such useless transformations.