1module ProjectM36.StaticOptimizer where
3import ProjectM36.RelationalExpression
4import ProjectM36.Relation
6import qualified ProjectM36.AttributeNames as AS
7import ProjectM36.TupleSet
8import Control.Monad.State hiding (join)
9import Data.Either (rights, lefts)
11-- the static optimizer performs optimizations which need not take any specific-relation statistics into account
12-- apply optimizations which merely remove steps to become no-ops: example: projection of a relation across all of its attributes => original relation
14--should optimizations offer the possibility to return errors? If they perform the up-front type-checking, maybe so
15applyStaticRelationalOptimization :: RelationalExpr -> DatabaseState (Either RelationalError RelationalExpr)
16applyStaticRelationalOptimization e@(MakeStaticRelation _ _) = return $ Right e
18applyStaticRelationalOptimization e@(ExistingRelation _) = return $ Right e
20applyStaticRelationalOptimization e@(RelationVariable _) = return $ Right e
22--remove project of attributes which removes no attributes
23applyStaticRelationalOptimization (Project attrNameSet expr) = do
24 relType <- typeForRelationalExpr expr
26 Left err -> return $ Left err
27 Right relType2 -> if attributeNames relType2 == AS.attributeNameSet attrNameSet then
28 applyStaticRelationalOptimization expr
30 optimizedSubExpression <- applyStaticRelationalOptimization expr
31 case optimizedSubExpression of
32 Left err -> return $ Left err
33 Right optSubExpr -> return $ Right $ Project attrNameSet optSubExpr
35applyStaticRelationalOptimization (Union exprA exprB) = do
36 optExprA <- applyStaticRelationalOptimization exprA
37 optExprB <- applyStaticRelationalOptimization exprB
39 Left err -> return $ Left err
40 Right optExprAx -> case optExprB of
41 Left err -> return $ Left err
42 Right optExprBx -> if optExprAx == optExprBx then
43 return (Right optExprAx)
45 return $ Right $ Union optExprAx optExprBx
47applyStaticRelationalOptimization (Join exprA exprB) = do
48 optExprA <- applyStaticRelationalOptimization exprA
49 optExprB <- applyStaticRelationalOptimization exprB
51 Left err -> return $ Left err
52 Right optExprA2 -> case optExprB of
53 Left err -> return $ Left err
54 Right optExprB2 -> if optExprA == optExprB then --A join A == A
57 return $ Right (Join optExprA2 optExprB2)
59applyStaticRelationalOptimization e@(Rename _ _ _) = return $ Right e
61applyStaticRelationalOptimization (Group oldAttrNames newAttrName expr) = do
62 return $ Right $ Group oldAttrNames newAttrName expr
64applyStaticRelationalOptimization (Ungroup attrName expr) = do
65 return $ Right $ Ungroup attrName expr
67--remove restriction of nothing
68applyStaticRelationalOptimization (Restrict predicate expr) = do
69 optimizedPredicate <- applyStaticPredicateOptimization predicate
70 case optimizedPredicate of
71 Left err -> return $ Left err
72 Right optimizedPredicate2 -> if optimizedPredicate2 == TruePredicate then
73 applyStaticRelationalOptimization expr
74 else if optimizedPredicate2 == NotPredicate TruePredicate then do
75 attributesRel <- typeForRelationalExpr expr
77 Left err -> return $ Left err
78 Right attributesRelA -> return $ Right $ MakeStaticRelation (attributes attributesRelA) emptyTupleSet
80 optimizedSubExpression <- applyStaticRelationalOptimization expr
81 case optimizedSubExpression of
82 Left err -> return $ Left err
83 Right optSubExpr -> return $ Right $ Restrict optimizedPredicate2 optSubExpr
85applyStaticRelationalOptimization e@(Equals _ _) = return $ Right e
87applyStaticRelationalOptimization e@(NotEquals _ _) = return $ Right e
89applyStaticRelationalOptimization e@(Extend _ _) = return $ Right e
91applyStaticDatabaseOptimization :: DatabaseExpr -> DatabaseState (Either RelationalError DatabaseExpr)
92applyStaticDatabaseOptimization (Define name attrs) = return $ Right (Define name attrs)
94applyStaticDatabaseOptimization (Undefine name) = return $ Right (Undefine name)
96applyStaticDatabaseOptimization (Assign name expr) = do
97 optimizedExpr <- applyStaticRelationalOptimization expr
99 Left err -> return $ Left err
100 Right optimizedExpr2 -> return $ Right (Assign name optimizedExpr2)
102applyStaticDatabaseOptimization (Insert name expr) = do
103 optimizedExpr <- applyStaticRelationalOptimization expr
104 case optimizedExpr of
105 Left err -> return $ Left err
106 Right optimizedExpr2 -> return $ Right (Insert name optimizedExpr2)
108applyStaticDatabaseOptimization (Delete name predicate) = do
109 optimizedPredicate <- applyStaticPredicateOptimization predicate
110 case optimizedPredicate of
111 Left err -> return $ Left err
112 Right optimizedPredicate2 -> return $ Right (Delete name optimizedPredicate2)
114applyStaticDatabaseOptimization (Update name upmap predicate) = do
115 optimizedPredicate <- applyStaticPredicateOptimization predicate
116 case optimizedPredicate of
117 Left err -> return $ Left err
118 Right optimizedPredicate2 -> return $ Right (Update name upmap optimizedPredicate2)
120applyStaticDatabaseOptimization dep@(AddInclusionDependency _ _) = return $ Right dep
122applyStaticDatabaseOptimization (RemoveInclusionDependency name) = return $ Right (RemoveInclusionDependency name)
124--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
126--applyStaticDatabaseOptimization (MultipleExpr exprs) = return $ Right $ MultipleExpr exprs
127--for multiple expressions, we must evaluate
128applyStaticDatabaseOptimization (MultipleExpr exprs) = do
130 let optExprs = evalState substateRunner (contextWithEmptyTupleSets context)
131 let errors = lefts optExprs
132 if length errors > 0 then
133 return $ Left (head errors)
135 return $ Right $ MultipleExpr (rights optExprs)
137 substateRunner = forM exprs $ \expr -> do
138 --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
139 _ <- evalContextExpr expr
140 applyStaticDatabaseOptimization expr
141 --this error handling could be improved with some lifting presumably
142 --restore original context
144applyStaticPredicateOptimization :: RestrictionPredicateExpr -> DatabaseState (Either RelationalError RestrictionPredicateExpr)
145applyStaticPredicateOptimization predicate = return $ Right predicate
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list