git.iko.soy/project-m36
on 18f736a help sign in
project-m36/src/lib/ProjectM36/StaticOptimizer.hs
453 lines 24 kB history raw
1module ProjectM36.StaticOptimizer where
2import ProjectM36.Base
3import ProjectM36.RelationalExpression
4import ProjectM36.Relation
5import ProjectM36.Error
6import qualified ProjectM36.Attribute as A
7import qualified ProjectM36.AttributeNames as AS
8import ProjectM36.TupleSet
9import Control.Monad.State
10import Data.Either (rights, lefts)
11import Control.Monad.Trans.Reader
12import qualified Data.Map as M
13import qualified Data.Set as S
15-- the static optimizer performs optimizations which need not take any specific-relation statistics into account
16optimizeRelationalExpr :: DatabaseContext -> RelationalExpr -> Either RelationalError RelationalExpr
17optimizeRelationalExpr context expr = runReader (optimizeRelationalExprReader expr) (mkRelationalExprState context)
19optimizeRelationalExprReader :: RelationalExpr -> RelationalExprState (Either RelationalError RelationalExpr)
20optimizeRelationalExprReader expr = do
21 eOptExpr <- applyStaticRelationalOptimization expr
22 case eOptExpr of
23 Left err -> pure (Left err)
24 Right optExpr ->
25 applyStaticJoinElimination (applyStaticRestrictionPushdown (applyStaticRestrictionCollapse optExpr))
27optimizeDatabaseContextExpr :: DatabaseContext -> DatabaseContextExpr -> Either RelationalError DatabaseContextExpr
28optimizeDatabaseContextExpr context dbExpr = evalState (applyStaticDatabaseOptimization dbExpr) (freshDatabaseState context)
29-- apply optimizations which merely remove steps to become no-ops: example: projection of a relation across all of its attributes => original relation
31--should optimizations offer the possibility to pure errors? If they perform the up-front type-checking, maybe so
32applyStaticRelationalOptimization :: RelationalExpr -> RelationalExprState (Either RelationalError RelationalExpr)
33applyStaticRelationalOptimization e@(MakeStaticRelation _ _) = pure $ Right e
35applyStaticRelationalOptimization e@(MakeRelationFromExprs _ _) = pure $ Right e
37applyStaticRelationalOptimization e@(ExistingRelation _) = pure $ Right e
39applyStaticRelationalOptimization e@(RelationVariable _ _) = pure $ Right e
41--remove project of attributes which removes no attributes
42applyStaticRelationalOptimization (Project attrNameSet expr) = do
43 relType <- typeForRelationalExpr expr
44 case relType of
45 Left err -> pure $ Left err
46 Right relType2
47 | AS.all == attrNameSet ->
48 applyStaticRelationalOptimization expr
49 | AttributeNames (attributeNames relType2) == attrNameSet ->
50 applyStaticRelationalOptimization expr
51 | otherwise -> do
52 optimizedSubExpression <- applyStaticRelationalOptimization expr
53 case optimizedSubExpression of
54 Left err -> pure $ Left err
55 Right optSubExpr -> pure (Right (Project attrNameSet optSubExpr))
57applyStaticRelationalOptimization (Union exprA exprB) = do
58 eOptExprA <- applyStaticRelationalOptimization exprA
59 eOptExprB <- applyStaticRelationalOptimization exprB
60 case eOptExprA of
61 Left err -> pure $ Left err
62 Right optExprA -> case eOptExprB of
63 Left err -> pure $ Left err
64 Right optExprB -> -- (x where pred1) union (x where pred2) -> (x where pred1 or pred2)
65 case (optExprA, optExprB) of
66 (Restrict predA (RelationVariable nameA ()),
67 Restrict predB (RelationVariable nameB ())) | nameA == nameB -> pure (Right (Restrict (AndPredicate predA predB) (RelationVariable nameA ())))
68 _ -> if optExprA == optExprB then
69 pure (Right optExprA)
70 else
71 pure $ Right $ Union optExprA optExprB
73applyStaticRelationalOptimization (Join exprA exprB) = do
74 eOptExprA <- applyStaticRelationalOptimization exprA
75 eOptExprB <- applyStaticRelationalOptimization exprB
76 case eOptExprA of
77 Left err -> pure $ Left err
78 Right optExprA -> case eOptExprB of
79 Left err -> pure $ Left err
80 Right optExprB ->
81 -- if the relvars to join are the same but with predicates, then just AndPredicate the predicates
82 case (optExprA, optExprB) of
83 (Restrict predA (RelationVariable nameA ()),
84 Restrict predB (RelationVariable nameB ())) | nameA == nameB -> pure (Right (Restrict (AndPredicate predA predB) (RelationVariable nameA ())))
85 _ -> if optExprA == optExprB then --A join A == A
86 pure (Right optExprA)
87 else
88 pure (Right (Join optExprA optExprB))
90applyStaticRelationalOptimization (Difference exprA exprB) = do
91 optExprA <- applyStaticRelationalOptimization exprA
92 optExprB <- applyStaticRelationalOptimization exprB
93 case optExprA of
94 Left err -> pure $ Left err
95 Right optExprA2 -> case optExprB of
96 Left err -> pure $ Left err
97 Right optExprB2 -> if optExprA == optExprB then do --A difference A == A where false
98 eEmptyRel <- typeForRelationalExpr optExprA2
99 case eEmptyRel of
100 Left err -> pure (Left err)
101 Right emptyRel -> pure (Right (ExistingRelation emptyRel))
102 else
103 pure $ Right (Difference optExprA2 optExprB2)
105applyStaticRelationalOptimization e@Rename{} = pure $ Right e
107applyStaticRelationalOptimization (Group oldAttrNames newAttrName expr) =
108 pure $ Right $ Group oldAttrNames newAttrName expr
110applyStaticRelationalOptimization (Ungroup attrName expr) =
111 pure $ Right $ Ungroup attrName expr
113--remove restriction of nothing
114applyStaticRelationalOptimization (Restrict predicate expr) = do
115 optimizedPredicate <- applyStaticPredicateOptimization predicate
116 case optimizedPredicate of
117 Left err -> pure $ Left err
118 Right optimizedPredicate2
119 | isTrueExpr optimizedPredicate2 -> applyStaticRelationalOptimization expr -- remove predicate entirely
120 | isFalseExpr optimizedPredicate2 -> do -- replace where false predicate with empty relation with attributes from relexpr
121 attributesRel <- typeForRelationalExpr expr
122 case attributesRel of
123 Left err -> pure $ Left err
124 Right attributesRelA -> pure $ Right $ MakeStaticRelation (attributes attributesRelA) emptyTupleSet
125 | otherwise -> do
126 optimizedSubExpression <- applyStaticRelationalOptimization expr
127 case optimizedSubExpression of
128 Left err -> pure $ Left err
129 Right optSubExpr -> pure $ Right $ Restrict optimizedPredicate2 optSubExpr
131applyStaticRelationalOptimization e@(Equals _ _) = pure $ Right e
133applyStaticRelationalOptimization e@(NotEquals _ _) = pure $ Right e
135applyStaticRelationalOptimization e@(Extend _ _) = pure $ Right e
137applyStaticDatabaseOptimization :: DatabaseContextExpr -> DatabaseState (Either RelationalError DatabaseContextExpr)
138applyStaticDatabaseOptimization x@NoOperation = pure $ Right x
139applyStaticDatabaseOptimization x@(Define _ _) = pure $ Right x
141applyStaticDatabaseOptimization x@(Undefine _) = pure $ Right x
143applyStaticDatabaseOptimization (Assign name expr) = do
144 context <- getStateContext
145 let optimizedExpr = optimizeRelationalExpr context expr
146 case optimizedExpr of
147 Left err -> pure $ Left err
148 Right optimizedExpr2 -> pure $ Right (Assign name optimizedExpr2)
150applyStaticDatabaseOptimization (Insert targetName expr) = do
151 context <- getStateContext
152 let optimizedExpr = optimizeRelationalExpr context expr
153 case optimizedExpr of
154 Left err -> pure $ Left err
155 Right optimizedExpr2 -> if isEmptyRelationExpr optimizedExpr2 then -- if we are trying to insert an empty relation, do nothing
156 pure (Right NoOperation)
157 else
158 case optimizedExpr2 of
159 -- if the target relvar and the insert relvar are the same, there is nothing to do
160 -- insert s s -> NoOperation
161 RelationVariable insName () | insName == targetName -> pure (Right NoOperation)
162 _ -> pure $ Right (Insert targetName optimizedExpr2)
164applyStaticDatabaseOptimization (Delete name predicate) = do
165 context <- getStateContext
166 let optimizedPredicate = runReader (applyStaticPredicateOptimization predicate) (RelationalExprStateElems context)
167 case optimizedPredicate of
168 Left err -> pure $ Left err
169 Right optimizedPredicate2 -> pure $ Right (Delete name optimizedPredicate2)
171applyStaticDatabaseOptimization (Update name upmap predicate) = do
172 context <- getStateContext
173 let optimizedPredicate = runReader (applyStaticPredicateOptimization predicate) (RelationalExprStateElems context)
174 case optimizedPredicate of
175 Left err -> pure $ Left err
176 Right optimizedPredicate2 -> pure $ Right (Update name upmap optimizedPredicate2)
178applyStaticDatabaseOptimization dep@(AddInclusionDependency _ _) = pure $ Right dep
180applyStaticDatabaseOptimization (RemoveInclusionDependency name) = pure $ Right (RemoveInclusionDependency name)
182applyStaticDatabaseOptimization (AddNotification name triggerExpr resultOldExpr resultNewExpr) = do
183 context <- getStateContext
184 let eTriggerExprOpt = optimizeRelationalExpr context triggerExpr
185 case eTriggerExprOpt of
186 Left err -> pure $ Left err
187 Right triggerExprOpt -> --it doesn't make sense to optimize queries when we don't have their proper contexts
188 pure (Right (AddNotification name triggerExprOpt resultOldExpr resultNewExpr))
190applyStaticDatabaseOptimization notif@(RemoveNotification _) = pure (Right notif)
192applyStaticDatabaseOptimization c@(AddTypeConstructor _ _) = pure (Right c)
193applyStaticDatabaseOptimization c@(RemoveTypeConstructor _) = pure (Right c)
194applyStaticDatabaseOptimization c@(RemoveAtomFunction _) = pure (Right c)
195applyStaticDatabaseOptimization c@(RemoveDatabaseContextFunction _) = pure (Right c)
196applyStaticDatabaseOptimization c@(ExecuteDatabaseContextFunction _ _) = pure (Right c)
198--optimization: from pgsql lists- check for join condition referencing foreign key- if join projection project away the referenced table, then it does not need to be scanned
200--applyStaticDatabaseOptimization (MultipleExpr exprs) = pure $ Right $ MultipleExpr exprs
201--for multiple expressions, we must evaluate
202applyStaticDatabaseOptimization (MultipleExpr exprs) = do
203 context <- getStateContext
204 let optExprs = evalState substateRunner (contextWithEmptyTupleSets context, M.empty, False)
205 let errors = lefts optExprs
206 if not (null errors) then
207 pure $ Left (head errors)
208 else
209 pure $ Right $ MultipleExpr (rights optExprs)
210 where
211 substateRunner = forM exprs $ \expr -> do
212 --a previous expression could create a relvar, we don't want to miss it, so we clear the tuples and execute the expression to get an empty relation in the relvar
213 _ <- evalDatabaseContextExpr expr
214 applyStaticDatabaseOptimization expr
215 --this error handling could be improved with some lifting presumably
216 --restore original context
218applyStaticPredicateOptimization :: RestrictionPredicateExpr -> RelationalExprState (Either RelationalError RestrictionPredicateExpr)
219applyStaticPredicateOptimization predi = do
220 eOptPred <- case predi of
221-- where x and x => where x
222 AndPredicate pred1 pred2 -> do
223 eOptPred1 <- applyStaticPredicateOptimization pred1
224 case eOptPred1 of
225 Left err -> pure (Left err)
226 Right optPred1 -> do
227 eOptPred2 <- applyStaticPredicateOptimization pred2
228 case eOptPred2 of
229 Left err -> pure (Left err)
230 Right optPred2 ->
231 if optPred1 == optPred2 then
232 pure (Right optPred1)
233 else
234 pure (Right (AndPredicate optPred1 optPred2))
235-- where x or x => where x
236 OrPredicate pred1 pred2 -> do
237 eOptPred1 <- applyStaticPredicateOptimization pred1
238 case eOptPred1 of
239 Left err -> pure (Left err)
240 Right optPred1 -> do
241 eOptPred2 <- applyStaticPredicateOptimization pred2
242 case eOptPred2 of
243 Left err -> pure (Left err)
244 Right optPred2 | optPred1 == optPred2 -> pure (Right optPred1)
245 | isTrueExpr optPred1 -> pure (Right optPred1) -- True or x -> True
246 | isTrueExpr optPred2 -> pure (Right optPred2)
247 | otherwise -> pure (Right (OrPredicate optPred1 optPred2))
248 AttributeEqualityPredicate attrNameA (AttributeAtomExpr attrNameB) ->
249 if attrNameA == attrNameB then
250 pure (Right TruePredicate)
251 else
252 pure (Right predi)
253 AttributeEqualityPredicate{} -> pure (Right predi)
254 TruePredicate -> pure $ Right predi
255 NotPredicate{} -> pure $ Right predi
256 RelationalExprPredicate{} -> pure (Right predi)
257 AtomExprPredicate{} -> pure (Right predi)
258 case eOptPred of
259 Left err -> pure (Left err)
260 Right optPred ->
261 let attrMap = findStaticRestrictionPredicates optPred in
262 pure (Right (replaceStaticAtomExprs optPred attrMap))
264--determines if an atom expression is tautologically true
265isTrueExpr :: RestrictionPredicateExpr -> Bool
266isTrueExpr TruePredicate = True
267isTrueExpr (AtomExprPredicate (NakedAtomExpr (BoolAtom True))) = True
268isTrueExpr _ = False
270--determines if an atom expression is tautologically false
271isFalseExpr :: RestrictionPredicateExpr -> Bool
272isFalseExpr (NotPredicate expr) = isTrueExpr expr
273isFalseExpr (AtomExprPredicate (NakedAtomExpr (BoolAtom False))) = True
274isFalseExpr _ = False
276-- determine if the created relation can statically be determined to be empty
277isEmptyRelationExpr :: RelationalExpr -> Bool
278isEmptyRelationExpr (MakeRelationFromExprs _ []) = True
279isEmptyRelationExpr (MakeStaticRelation _ tupSet) = null (asList tupSet)
280isEmptyRelationExpr (ExistingRelation rel) = rel == emptyRelationWithAttrs (attributes rel)
281isEmptyRelationExpr _ = False
283--transitive static variable optimization
284replaceStaticAtomExprs :: RestrictionPredicateExpr -> M.Map AttributeName AtomExpr -> RestrictionPredicateExpr
285replaceStaticAtomExprs predIn replaceMap = case predIn of
286 AttributeEqualityPredicate newAttrName (AttributeAtomExpr matchName) -> case M.lookup matchName replaceMap of
287 Nothing -> predIn
288 Just newVal -> AttributeEqualityPredicate newAttrName newVal
289 AttributeEqualityPredicate{} -> predIn
290 AndPredicate pred1 pred2 -> AndPredicate (replaceStaticAtomExprs pred1 replaceMap) (replaceStaticAtomExprs pred2 replaceMap)
291 OrPredicate pred1 pred2 -> OrPredicate (replaceStaticAtomExprs pred1 replaceMap) (replaceStaticAtomExprs pred2 replaceMap)
292 NotPredicate pred1 -> NotPredicate (replaceStaticAtomExprs pred1 replaceMap)
293 TruePredicate -> predIn
294 RelationalExprPredicate{} -> predIn
295 AtomExprPredicate{} -> predIn
296-- used for transitive attribute optimization- only works on statically-determined atoms for now- in the future, this could work for all AtomExprs which don't reference attributes
297findStaticRestrictionPredicates :: RestrictionPredicateExpr -> M.Map AttributeName AtomExpr
298findStaticRestrictionPredicates (AttributeEqualityPredicate attrName atomExpr) =
299 case atomExpr of
300 val@NakedAtomExpr{} -> M.singleton attrName val
301 val@ConstructedAtomExpr{} -> M.singleton attrName val
302 _ -> M.empty
304findStaticRestrictionPredicates (AndPredicate pred1 pred2) =
305 M.union (findStaticRestrictionPredicates pred1) (findStaticRestrictionPredicates pred2)
306findStaticRestrictionPredicates (OrPredicate pred1 pred2) =
307 M.union (findStaticRestrictionPredicates pred1) (findStaticRestrictionPredicates pred2)
308findStaticRestrictionPredicates (NotPredicate predi) = findStaticRestrictionPredicates predi
309findStaticRestrictionPredicates TruePredicate = M.empty
310findStaticRestrictionPredicates RelationalExprPredicate{} = M.empty
311findStaticRestrictionPredicates AtomExprPredicate{} = M.empty
313isStaticAtomExpr :: AtomExpr -> Bool
314isStaticAtomExpr NakedAtomExpr{} = True
315isStaticAtomExpr ConstructedAtomExpr{} = True
316isStaticAtomExpr AttributeAtomExpr{} = False
317isStaticAtomExpr FunctionAtomExpr{} = False
318isStaticAtomExpr RelationAtomExpr{} = False
320--if the projection of a join only uses the attributes from one of the expressions and there is a foreign key relationship between the expressions, we know that the join is inconsequential and can be removed
321applyStaticJoinElimination :: RelationalExpr -> RelationalExprState (Either RelationalError RelationalExpr)
322applyStaticJoinElimination expr@(Project attrNameSet (Join exprA exprB)) = do
323 relState <- ask
324 eProjType <- typeForRelationalExpr expr
325 eTypeA <- typeForRelationalExpr exprA
326 eTypeB <- typeForRelationalExpr exprB
327 case eProjType of
328 Left err -> pure (Left err)
329 Right projType ->
330 case eTypeA of
331 Left err -> pure (Left err)
332 Right typeA ->
333 case eTypeB of
334 Left err -> pure (Left err)
335 Right typeB -> do
336 let matchesProjectionAttributes
337 | attrNames projType `S.isSubsetOf` attrNames typeA =
338 Just ((exprA, typeA), (exprB, typeB))
339 | attrNames projType `S.isSubsetOf` attrNames typeB =
340 Just ((exprB, typeB), (exprA, typeA))
341 | otherwise =
342 Nothing
343 attrNames = A.attributeNameSet . attributes
344 case matchesProjectionAttributes of
345 Nothing -> -- this optimization does not apply
346 pure (Right expr)
347 Just ((joinedExpr, joinedType), (unjoinedExpr, _)) -> do
348 --scan inclusion dependencies for a foreign key relationship
349 incDeps <- inclusionDependencies . stateElemsContext <$> ask
350 let fkConstraint = foldM isFkConstraint False incDeps
351 --search for matching fk constraint
352 isFkConstraint acc (InclusionDependency (Project subattrNames subrv) (Project _ superrv)) =
353 case runReader (evalAttributeNames subattrNames expr) relState of
354 Left _ -> pure acc
355 Right subAttrNameSet ->
356 pure (acc || (joinedExpr == subrv &&
357 unjoinedExpr == superrv &&
358 -- the fk attribute is one of the projection attributes
359 A.attributeNamesContained subAttrNameSet (A.attributeNameSet (attributes joinedType))
360 ))
361 isFkConstraint acc _ = pure acc
362 case fkConstraint of
363 Right True -> --join elimination optimization applies
364 applyStaticRelationalOptimization (Project attrNameSet joinedExpr)
365 Right False -> --join elimination optimization does not apply
366 pure (Right expr)
367 Left err ->
368 pure (Left err)
370applyStaticJoinElimination expr = pure (Right expr)
372--restriction collapse converts chained restrictions into (Restrict (And pred1 pred2 pred3...))
373 --this optimization should be fairly uncontroversial- performing a tuple scan once is cheaper than twice- parallelization can still take place
374applyStaticRestrictionCollapse :: RelationalExpr -> RelationalExpr
375applyStaticRestrictionCollapse expr =
376 case expr of
377 MakeRelationFromExprs _ _ -> expr
378 MakeStaticRelation _ _ -> expr
379 ExistingRelation _ -> expr
380 RelationVariable _ _ -> expr
381 Project attrs subexpr ->
382 Project attrs (applyStaticRestrictionCollapse subexpr)
383 Union sub1 sub2 ->
384 Union (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
385 Join sub1 sub2 ->
386 Join (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
387 Rename n1 n2 sub ->
388 Rename n1 n2 (applyStaticRestrictionCollapse sub)
389 Difference sub1 sub2 ->
390 Difference (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
391 Group n1 n2 sub ->
392 Group n1 n2 (applyStaticRestrictionCollapse sub)
393 Ungroup n1 sub ->
394 Ungroup n1 (applyStaticRestrictionCollapse sub)
395 Equals sub1 sub2 ->
396 Equals (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
397 NotEquals sub1 sub2 ->
398 NotEquals (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
399 Extend n sub ->
400 Extend n (applyStaticRestrictionCollapse sub)
401 Restrict firstPred _ ->
402 let restrictions = sequentialRestrictions expr
403 finalExpr = last restrictions
404 optFinalExpr = case finalExpr of
405 Restrict _ subexpr -> applyStaticRestrictionCollapse subexpr
406 otherExpr -> otherExpr
407 andPreds = foldr (\(Restrict subpred _) acc -> AndPredicate acc subpred) firstPred (tail restrictions) in
408 Restrict andPreds optFinalExpr
410sequentialRestrictions :: RelationalExpr -> [RelationalExpr]
411sequentialRestrictions expr@(Restrict _ subexpr) = expr:sequentialRestrictions subexpr
412sequentialRestrictions _ = []
414--restriction pushdown only really makes sense for tuple-oriented storage schemes where performing a restriction before projection can cut down on the intermediate storage needed to store the data before the projection
415-- x{proj} where c1 -> (x where c1){proj} #project on fewer tuples
416-- (x union y) where c -> (x where c) union (y where c) #with a selective restriction, fewer tuples will need to be joined
417applyStaticRestrictionPushdown :: RelationalExpr -> RelationalExpr
418applyStaticRestrictionPushdown expr = case expr of
419 MakeRelationFromExprs _ _ -> expr
420 MakeStaticRelation _ _ -> expr
421 ExistingRelation _ -> expr
422 RelationVariable _ _ -> expr
423 Project _ _ -> expr
424 --this transformation cannot be inverted because the projection attributes might not exist in the inverted version
425 Restrict restrictAttrs (Project projAttrs subexpr) ->
426 Project projAttrs (Restrict restrictAttrs (applyStaticRestrictionPushdown subexpr))
427 Restrict restrictAttrs (Union subexpr1 subexpr2) ->
428 let optSub1 = applyStaticRestrictionPushdown subexpr1
429 optSub2 = applyStaticRestrictionPushdown subexpr2 in
430 Union (Restrict restrictAttrs optSub1) (Restrict restrictAttrs optSub2)
431 Restrict attrs subexpr ->
432 Restrict attrs (applyStaticRestrictionPushdown subexpr)
434 Union sub1 sub2 ->
435 Union (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
436 Join sub1 sub2 ->
437 Join (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
438 Rename n1 n2 sub ->
439 Rename n1 n2 (applyStaticRestrictionPushdown sub)
440 Difference sub1 sub2 ->
441 Difference (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
442 Group n1 n2 sub ->
443 Group n1 n2 (applyStaticRestrictionPushdown sub)
444 Ungroup n1 sub ->
445 Ungroup n1 (applyStaticRestrictionPushdown sub)
446 Equals sub1 sub2 ->
447 Equals (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
448 NotEquals sub1 sub2 ->
449 NotEquals (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
450 Extend n sub ->
451 Extend n (applyStaticRestrictionPushdown sub)