git.iko.soy/project-m36
on 52182bc help sign in
project-m36/src/lib/ProjectM36/StaticOptimizer.hs
457 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
137applyStaticRelationalOptimization e@(With _ _) = pure $ Right e
139applyStaticDatabaseOptimization :: DatabaseContextExpr -> DatabaseState (Either RelationalError DatabaseContextExpr)
140applyStaticDatabaseOptimization x@NoOperation = pure $ Right x
141applyStaticDatabaseOptimization x@(Define _ _) = pure $ Right x
143applyStaticDatabaseOptimization x@(Undefine _) = pure $ Right x
145applyStaticDatabaseOptimization (Assign name expr) = do
146 context <- getStateContext
147 let optimizedExpr = optimizeRelationalExpr context expr
148 case optimizedExpr of
149 Left err -> pure $ Left err
150 Right optimizedExpr2 -> pure $ Right (Assign name optimizedExpr2)
152applyStaticDatabaseOptimization (Insert targetName expr) = do
153 context <- getStateContext
154 let optimizedExpr = optimizeRelationalExpr context expr
155 case optimizedExpr of
156 Left err -> pure $ Left err
157 Right optimizedExpr2 -> if isEmptyRelationExpr optimizedExpr2 then -- if we are trying to insert an empty relation, do nothing
158 pure (Right NoOperation)
159 else
160 case optimizedExpr2 of
161 -- if the target relvar and the insert relvar are the same, there is nothing to do
162 -- insert s s -> NoOperation
163 RelationVariable insName () | insName == targetName -> pure (Right NoOperation)
164 _ -> pure $ Right (Insert targetName optimizedExpr2)
166applyStaticDatabaseOptimization (Delete name predicate) = do
167 context <- getStateContext
168 let optimizedPredicate = runReader (applyStaticPredicateOptimization predicate) (RelationalExprStateElems context)
169 case optimizedPredicate of
170 Left err -> pure $ Left err
171 Right optimizedPredicate2 -> pure $ Right (Delete name optimizedPredicate2)
173applyStaticDatabaseOptimization (Update name upmap predicate) = do
174 context <- getStateContext
175 let optimizedPredicate = runReader (applyStaticPredicateOptimization predicate) (RelationalExprStateElems context)
176 case optimizedPredicate of
177 Left err -> pure $ Left err
178 Right optimizedPredicate2 -> pure $ Right (Update name upmap optimizedPredicate2)
180applyStaticDatabaseOptimization dep@(AddInclusionDependency _ _) = pure $ Right dep
182applyStaticDatabaseOptimization (RemoveInclusionDependency name) = pure $ Right (RemoveInclusionDependency name)
184applyStaticDatabaseOptimization (AddNotification name triggerExpr resultOldExpr resultNewExpr) = do
185 context <- getStateContext
186 let eTriggerExprOpt = optimizeRelationalExpr context triggerExpr
187 case eTriggerExprOpt of
188 Left err -> pure $ Left err
189 Right triggerExprOpt -> --it doesn't make sense to optimize queries when we don't have their proper contexts
190 pure (Right (AddNotification name triggerExprOpt resultOldExpr resultNewExpr))
192applyStaticDatabaseOptimization notif@(RemoveNotification _) = pure (Right notif)
194applyStaticDatabaseOptimization c@(AddTypeConstructor _ _) = pure (Right c)
195applyStaticDatabaseOptimization c@(RemoveTypeConstructor _) = pure (Right c)
196applyStaticDatabaseOptimization c@(RemoveAtomFunction _) = pure (Right c)
197applyStaticDatabaseOptimization c@(RemoveDatabaseContextFunction _) = pure (Right c)
198applyStaticDatabaseOptimization c@(ExecuteDatabaseContextFunction _ _) = pure (Right c)
200--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
202--applyStaticDatabaseOptimization (MultipleExpr exprs) = pure $ Right $ MultipleExpr exprs
203--for multiple expressions, we must evaluate
204applyStaticDatabaseOptimization (MultipleExpr exprs) = do
205 context <- getStateContext
206 let optExprs = evalState substateRunner (contextWithEmptyTupleSets context, M.empty, False)
207 let errors = lefts optExprs
208 if not (null errors) then
209 pure $ Left (head errors)
210 else
211 pure $ Right $ MultipleExpr (rights optExprs)
212 where
213 substateRunner = forM exprs $ \expr -> do
214 --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
215 _ <- evalDatabaseContextExpr expr
216 applyStaticDatabaseOptimization expr
217 --this error handling could be improved with some lifting presumably
218 --restore original context
220applyStaticPredicateOptimization :: RestrictionPredicateExpr -> RelationalExprState (Either RelationalError RestrictionPredicateExpr)
221applyStaticPredicateOptimization predi = do
222 eOptPred <- case predi of
223-- where x and x => where x
224 AndPredicate pred1 pred2 -> do
225 eOptPred1 <- applyStaticPredicateOptimization pred1
226 case eOptPred1 of
227 Left err -> pure (Left err)
228 Right optPred1 -> do
229 eOptPred2 <- applyStaticPredicateOptimization pred2
230 case eOptPred2 of
231 Left err -> pure (Left err)
232 Right optPred2 ->
233 if optPred1 == optPred2 then
234 pure (Right optPred1)
235 else
236 pure (Right (AndPredicate optPred1 optPred2))
237-- where x or x => where x
238 OrPredicate pred1 pred2 -> do
239 eOptPred1 <- applyStaticPredicateOptimization pred1
240 case eOptPred1 of
241 Left err -> pure (Left err)
242 Right optPred1 -> do
243 eOptPred2 <- applyStaticPredicateOptimization pred2
244 case eOptPred2 of
245 Left err -> pure (Left err)
246 Right optPred2 | optPred1 == optPred2 -> pure (Right optPred1)
247 | isTrueExpr optPred1 -> pure (Right optPred1) -- True or x -> True
248 | isTrueExpr optPred2 -> pure (Right optPred2)
249 | otherwise -> pure (Right (OrPredicate optPred1 optPred2))
250 AttributeEqualityPredicate attrNameA (AttributeAtomExpr attrNameB) ->
251 if attrNameA == attrNameB then
252 pure (Right TruePredicate)
253 else
254 pure (Right predi)
255 AttributeEqualityPredicate{} -> pure (Right predi)
256 TruePredicate -> pure $ Right predi
257 NotPredicate{} -> pure $ Right predi
258 RelationalExprPredicate{} -> pure (Right predi)
259 AtomExprPredicate{} -> pure (Right predi)
260 case eOptPred of
261 Left err -> pure (Left err)
262 Right optPred ->
263 let attrMap = findStaticRestrictionPredicates optPred in
264 pure (Right (replaceStaticAtomExprs optPred attrMap))
266--determines if an atom expression is tautologically true
267isTrueExpr :: RestrictionPredicateExpr -> Bool
268isTrueExpr TruePredicate = True
269isTrueExpr (AtomExprPredicate (NakedAtomExpr (BoolAtom True))) = True
270isTrueExpr _ = False
272--determines if an atom expression is tautologically false
273isFalseExpr :: RestrictionPredicateExpr -> Bool
274isFalseExpr (NotPredicate expr) = isTrueExpr expr
275isFalseExpr (AtomExprPredicate (NakedAtomExpr (BoolAtom False))) = True
276isFalseExpr _ = False
278-- determine if the created relation can statically be determined to be empty
279isEmptyRelationExpr :: RelationalExpr -> Bool
280isEmptyRelationExpr (MakeRelationFromExprs _ []) = True
281isEmptyRelationExpr (MakeStaticRelation _ tupSet) = null (asList tupSet)
282isEmptyRelationExpr (ExistingRelation rel) = rel == emptyRelationWithAttrs (attributes rel)
283isEmptyRelationExpr _ = False
285--transitive static variable optimization
286replaceStaticAtomExprs :: RestrictionPredicateExpr -> M.Map AttributeName AtomExpr -> RestrictionPredicateExpr
287replaceStaticAtomExprs predIn replaceMap = case predIn of
288 AttributeEqualityPredicate newAttrName (AttributeAtomExpr matchName) -> case M.lookup matchName replaceMap of
289 Nothing -> predIn
290 Just newVal -> AttributeEqualityPredicate newAttrName newVal
291 AttributeEqualityPredicate{} -> predIn
292 AndPredicate pred1 pred2 -> AndPredicate (replaceStaticAtomExprs pred1 replaceMap) (replaceStaticAtomExprs pred2 replaceMap)
293 OrPredicate pred1 pred2 -> OrPredicate (replaceStaticAtomExprs pred1 replaceMap) (replaceStaticAtomExprs pred2 replaceMap)
294 NotPredicate pred1 -> NotPredicate (replaceStaticAtomExprs pred1 replaceMap)
295 TruePredicate -> predIn
296 RelationalExprPredicate{} -> predIn
297 AtomExprPredicate{} -> predIn
298-- 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
299findStaticRestrictionPredicates :: RestrictionPredicateExpr -> M.Map AttributeName AtomExpr
300findStaticRestrictionPredicates (AttributeEqualityPredicate attrName atomExpr) =
301 case atomExpr of
302 val@NakedAtomExpr{} -> M.singleton attrName val
303 val@ConstructedAtomExpr{} -> M.singleton attrName val
304 _ -> M.empty
306findStaticRestrictionPredicates (AndPredicate pred1 pred2) =
307 M.union (findStaticRestrictionPredicates pred1) (findStaticRestrictionPredicates pred2)
308findStaticRestrictionPredicates (OrPredicate pred1 pred2) =
309 M.union (findStaticRestrictionPredicates pred1) (findStaticRestrictionPredicates pred2)
310findStaticRestrictionPredicates (NotPredicate predi) = findStaticRestrictionPredicates predi
311findStaticRestrictionPredicates TruePredicate = M.empty
312findStaticRestrictionPredicates RelationalExprPredicate{} = M.empty
313findStaticRestrictionPredicates AtomExprPredicate{} = M.empty
315isStaticAtomExpr :: AtomExpr -> Bool
316isStaticAtomExpr NakedAtomExpr{} = True
317isStaticAtomExpr ConstructedAtomExpr{} = True
318isStaticAtomExpr AttributeAtomExpr{} = False
319isStaticAtomExpr FunctionAtomExpr{} = False
320isStaticAtomExpr RelationAtomExpr{} = False
322--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
323applyStaticJoinElimination :: RelationalExpr -> RelationalExprState (Either RelationalError RelationalExpr)
324applyStaticJoinElimination expr@(Project attrNameSet (Join exprA exprB)) = do
325 relState <- ask
326 eProjType <- typeForRelationalExpr expr
327 eTypeA <- typeForRelationalExpr exprA
328 eTypeB <- typeForRelationalExpr exprB
329 case eProjType of
330 Left err -> pure (Left err)
331 Right projType ->
332 case eTypeA of
333 Left err -> pure (Left err)
334 Right typeA ->
335 case eTypeB of
336 Left err -> pure (Left err)
337 Right typeB -> do
338 let matchesProjectionAttributes
339 | attrNames projType `S.isSubsetOf` attrNames typeA =
340 Just ((exprA, typeA), (exprB, typeB))
341 | attrNames projType `S.isSubsetOf` attrNames typeB =
342 Just ((exprB, typeB), (exprA, typeA))
343 | otherwise =
344 Nothing
345 attrNames = A.attributeNameSet . attributes
346 case matchesProjectionAttributes of
347 Nothing -> -- this optimization does not apply
348 pure (Right expr)
349 Just ((joinedExpr, joinedType), (unjoinedExpr, _)) -> do
350 --scan inclusion dependencies for a foreign key relationship
351 incDeps <- inclusionDependencies . stateElemsContext <$> ask
352 let fkConstraint = foldM isFkConstraint False incDeps
353 --search for matching fk constraint
354 isFkConstraint acc (InclusionDependency (Project subattrNames subrv) (Project _ superrv)) =
355 case runReader (evalAttributeNames subattrNames expr) relState of
356 Left _ -> pure acc
357 Right subAttrNameSet ->
358 pure (acc || (joinedExpr == subrv &&
359 unjoinedExpr == superrv &&
360 -- the fk attribute is one of the projection attributes
361 A.attributeNamesContained subAttrNameSet (A.attributeNameSet (attributes joinedType))
362 ))
363 isFkConstraint acc _ = pure acc
364 case fkConstraint of
365 Right True -> --join elimination optimization applies
366 applyStaticRelationalOptimization (Project attrNameSet joinedExpr)
367 Right False -> --join elimination optimization does not apply
368 pure (Right expr)
369 Left err ->
370 pure (Left err)
372applyStaticJoinElimination expr = pure (Right expr)
374--restriction collapse converts chained restrictions into (Restrict (And pred1 pred2 pred3...))
375 --this optimization should be fairly uncontroversial- performing a tuple scan once is cheaper than twice- parallelization can still take place
376applyStaticRestrictionCollapse :: RelationalExpr -> RelationalExpr
377applyStaticRestrictionCollapse expr =
378 case expr of
379 MakeRelationFromExprs _ _ -> expr
380 MakeStaticRelation _ _ -> expr
381 ExistingRelation _ -> expr
382 RelationVariable _ _ -> expr
383 With _ _ -> expr
384 Project attrs subexpr ->
385 Project attrs (applyStaticRestrictionCollapse subexpr)
386 Union sub1 sub2 ->
387 Union (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
388 Join sub1 sub2 ->
389 Join (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
390 Rename n1 n2 sub ->
391 Rename n1 n2 (applyStaticRestrictionCollapse sub)
392 Difference sub1 sub2 ->
393 Difference (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
394 Group n1 n2 sub ->
395 Group n1 n2 (applyStaticRestrictionCollapse sub)
396 Ungroup n1 sub ->
397 Ungroup n1 (applyStaticRestrictionCollapse sub)
398 Equals sub1 sub2 ->
399 Equals (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
400 NotEquals sub1 sub2 ->
401 NotEquals (applyStaticRestrictionCollapse sub1) (applyStaticRestrictionCollapse sub2)
402 Extend n sub ->
403 Extend n (applyStaticRestrictionCollapse sub)
404 Restrict firstPred _ ->
405 let restrictions = sequentialRestrictions expr
406 finalExpr = last restrictions
407 optFinalExpr = case finalExpr of
408 Restrict _ subexpr -> applyStaticRestrictionCollapse subexpr
409 otherExpr -> otherExpr
410 andPreds = foldr (\(Restrict subpred _) acc -> AndPredicate acc subpred) firstPred (tail restrictions) in
411 Restrict andPreds optFinalExpr
413sequentialRestrictions :: RelationalExpr -> [RelationalExpr]
414sequentialRestrictions expr@(Restrict _ subexpr) = expr:sequentialRestrictions subexpr
415sequentialRestrictions _ = []
417--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
418-- x{proj} where c1 -> (x where c1){proj} #project on fewer tuples
419-- (x union y) where c -> (x where c) union (y where c) #with a selective restriction, fewer tuples will need to be joined
420applyStaticRestrictionPushdown :: RelationalExpr -> RelationalExpr
421applyStaticRestrictionPushdown expr = case expr of
422 MakeRelationFromExprs _ _ -> expr
423 MakeStaticRelation _ _ -> expr
424 ExistingRelation _ -> expr
425 RelationVariable _ _ -> expr
426 With _ _ -> expr
427 Project _ _ -> expr
428 --this transformation cannot be inverted because the projection attributes might not exist in the inverted version
429 Restrict restrictAttrs (Project projAttrs subexpr) ->
430 Project projAttrs (Restrict restrictAttrs (applyStaticRestrictionPushdown subexpr))
431 Restrict restrictAttrs (Union subexpr1 subexpr2) ->
432 let optSub1 = applyStaticRestrictionPushdown subexpr1
433 optSub2 = applyStaticRestrictionPushdown subexpr2 in
434 Union (Restrict restrictAttrs optSub1) (Restrict restrictAttrs optSub2)
435 Restrict attrs subexpr ->
436 Restrict attrs (applyStaticRestrictionPushdown subexpr)
438 Union sub1 sub2 ->
439 Union (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
440 Join sub1 sub2 ->
441 Join (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
442 Rename n1 n2 sub ->
443 Rename n1 n2 (applyStaticRestrictionPushdown sub)
444 Difference sub1 sub2 ->
445 Difference (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
446 Group n1 n2 sub ->
447 Group n1 n2 (applyStaticRestrictionPushdown sub)
448 Ungroup n1 sub ->
449 Ungroup n1 (applyStaticRestrictionPushdown sub)
450 Equals sub1 sub2 ->
451 Equals (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
452 NotEquals sub1 sub2 ->
453 NotEquals (applyStaticRestrictionPushdown sub1) (applyStaticRestrictionPushdown sub2)
454 Extend n sub ->
455 Extend n (applyStaticRestrictionPushdown sub)