[Checkins]
SVN: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/
changes for basic algebra tree optimization by changing a
pattern in the algebra tree
Charith Paranaliyanage
paranaliyanage at gmail.com
Sat Jul 19 13:47:27 EDT 2008
Log message for revision 88611:
changes for basic algebra tree optimization by changing a pattern in the algebra tree
Changed:
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer.py
A Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer_new.txt
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/tests.py
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/compiler/compiler.py
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/database/metadata.py
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/algebra.py
U Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/interfaces.py
-=-
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -8,6 +8,7 @@
from collections import deque
from zope.component import adapts
from zope.interface import implements
+from zope.location import locate
#from zope.security.proxy import removeSecurityProxy
from zope.interface import directlyProvidedBy
from zope.interface import directlyProvides
@@ -16,54 +17,62 @@
from ocql.interfaces import IAlgebraObjectHead
from ocql.interfaces import IOptimizedAlgebraObject
-from ocql.rewriter.algebra import BaseAlgebra, If, Single, Make, Binary, Iter, Lambda
+from ocql.rewriter.algebra import *
-class FindResults(object):
- def __init__(self):
- self.level = 0
- self.parent = dict()
+def bfsFind(tree):
+ """Breadth-first search to find a Iter Algebra object."""
+ visited = set()
+ queue = [tree]
+ while len(queue):
+ curr_node = queue.pop(0)
+ if isinstance(curr_node, Iter):
+ return curr_node
+ if isinstance(curr_node, BaseAlgebra):
+ visited.add(curr_node)
+ queue.extend(c for c in curr_node.children
+ if c not in visited and c not in queue)
-def find(tree, algebra, startlevel=0):
- results = FindResults()
- bfs_list = deque()
- bfs_list.append(tree.tree)
- results.parent[algebra] = None
- results.level = 0
-
- while len(bfs_list):
- v = bfs_list.popleft()
- if isinstance(v, algebra) and startlevel < results.level:
- return results
- for child in v.children:
- if child not in results.parent:
- results.parent[str(child.__class__)] = v
- results.level += 1
- bfs_list.append(child)
+def findItrTreePattern(tree):
+ """Checks whole Iter tree pattern exists stating from the Iter algebra object"""
+ iter_obj = bfsFind(tree)
+ if iter_obj is not None:
+ #need to check If and Make objects present
+ if (isinstance(iter_obj.func, Lambda) and isinstance(iter_obj.coll, Make)):
+ if isinstance(iter_obj.func.expr, If):
+ if isinstance(iter_obj.func.expr.cond , Binary):
+ return iter_obj
return None
-def findItrPattern(tree, algebra):
-#this has If and Make algebra objects
- itr_reslts = find(tree, algebra)
- if itr_reslts is not None:
- #find for If and Make
- for child in itr_reslts.parent.values():
- if isinstance(child, Iter):
- r_iter = child
- break
- boolean_if = boolean_make = False
- print r_iter
- for i in r_iter.children:
- if isinstance(i, Lambda):
- boolean_lambda = True
- if isinstance(i, Make):
- boolean_make = True
-
- if boolean_lambda and boolean_make:
- return r_iter
+def iterPatternMatcher(tree):
+ """Replaces the identified Iter tree pattern """
+ coll = tree.klass
+ single = tree.func.expr.expr1
+ interface = tree.coll.expr1.name
+ cond = tree.func.expr.cond.left.name
+ operator = tree.func.expr.cond.op.op
+ if isinstance(tree.func.expr.cond.right, Constant):
+ value = tree.func.expr.cond.right.value
+ elif isinstance(tree.func.expr.cond.right, Identifier):
+ value = tree.func.expr.cond.right.name
+ else:
+ return tree
+ #new algebra objects
+ if operator == '==':
+ makeFromIndex = MakeFromIndex(coll , coll, interface, cond.split(".")[1], value, value)
+ elif operator == '>' or operator == '>=':
+ makeFromIndex = MakeFromIndex(coll , coll, interface, cond.split(".")[1], lowerbound=value)
+ elif operator == '<' or operator == '<=':
+ makeFromIndex = MakeFromIndex(coll , coll, interface, cond.split(".")[1], upperbound=value)
+ else:
+ return tree
+
+ newTree = Iter(coll, single, makeFromIndex)
+ parent = tree.__parent__
+ locate(newTree, parent, 'iter')
+ return newTree
- return None
def addMarkerIF(obj, marker):
#obj = removeSecurityProxy(obj)
@@ -80,7 +89,9 @@
def __call__(self, metadata):
addMarkerIF(self.context, IOptimizedAlgebraObject)
- results = findItrPattern(self.context, Iter)
+ results = findItrTreePattern(self.context.tree)
if results is not None:
- print results
+ newTree = iterPatternMatcher(results)
+ #return newTree
+
return self.context
Added: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer_new.txt
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer_new.txt (rev 0)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/aoptimizer_new.txt 2008-07-19 17:47:26 UTC (rev 88611)
@@ -0,0 +1,56 @@
+
+Queries in the rewriter.txt are extended to AlgebraOptimization
+
+ >>> from ocql.aoptimizer.aoptimizer import AlgebraOptimizer
+ >>> from ocql.interfaces import IOptimizedAlgebraObject
+ >>> from ocql.parser.queryparser import QueryParser
+ >>> from ocql.qoptimizer.qoptimizer import QueryOptimizer
+ >>> from ocql.rewriter.rewriter import Rewriter
+
+ >>> from ocql.testing.database import TestMetadata
+
+
+ >>> qo = QueryParser("set [ | 1 ]")(TestMetadata())
+ >>> opt = QueryOptimizer(qo)()
+ >>> alg = Rewriter(opt)()
+ >>> out = AlgebraOptimizer(alg)(None)
+ >>> print str(out)
+ Single(<type 'set'>, `1`)
+
+
+
+ >>> qo = QueryParser("set [ | 1 ] union set [|2]")(TestMetadata())
+ >>> opt = QueryOptimizer(qo)()
+ >>> alg = Rewriter(opt)()
+ >>> out = AlgebraOptimizer(alg)(None)
+ >>> print str(out)
+ Union(<type 'set'>, Single(<type 'set'>, `1`), Single(<type 'set'>, `2`))
+
+ #Differ not implemented
+ #>>> qo = QueryParser("set [ | 1 ] differ set [|2]")(TestMetadata())
+ #>>> opt = QueryOptimizer(qo)()
+ #>>> alg = Rewriter(opt)()
+ #>>> print str(alg)
+ #Union(<type 'set'>, Single(<type 'set'>, `1`), Single(<type 'set'>, `2`))
+
+
+ >>> qo = QueryParser("set [ i in ICourse | i ]")(TestMetadata())
+ >>> opt = QueryOptimizer(qo)()
+ >>> alg = Rewriter(opt)()
+ >>> out = AlgebraOptimizer(alg)(None)
+ >>> print str(out)
+ Iter(<type 'set'>, Lambda i: Single(<type 'set'>, i), Make(<type 'set'>, <type 'set'>, ICourse))
+
+ >>> qo = QueryParser("set [ c in ICourse; c.credits>3 | c.code ]")(TestMetadata())
+ >>> opt = QueryOptimizer(qo)()
+ >>> alg = Rewriter(opt)()
+ >>> out = AlgebraOptimizer(alg)(None)
+ >>> print str(out)
+ Iter(<type 'set'>, Lambda c: If(c.credits>`3`, Single(<type 'set'>, c.code), Empty(<type 'set'>)), Make(<type 'set'>, <type 'set'>, ICourse))
+
+ #bag not implemented
+ #>>> qo = QueryParser("size set [ i in ICourse | i ]")(TestMetadata())
+ #>>> opt = QueryOptimizer(qo)()
+ #>>> alg = Rewriter(opt)()
+ #>>> print str(alg)
+ #Iter(<type 'set'>, Lambda i: Single(<type 'set'>, i), Make(<type 'set'>, <type 'set'>, ICourse))
\ No newline at end of file
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/tests.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/tests.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/aoptimizer/tests.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -6,8 +6,9 @@
flags = doctest.NORMALIZE_WHITESPACE|doctest.ELLIPSIS
return unittest.TestSuite((
# avoid this tests for convenient while adding new implementation to the algebra optimizer
-# DocFileSuite('aoptimizer.txt',
-# optionflags=flags),
+#need to add aoptimizer.txt
+ DocFileSuite('aoptimizer_new.txt',
+ optionflags=flags),
))
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/compiler/compiler.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/compiler/compiler.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/compiler/compiler.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -164,6 +164,19 @@
IAlgebraCompiler(self.context.expr1)())
+class MakeFromIndexCompiler(BaseCompiler):
+ implements(IAlgebraCompiler)
+ adapts(IMakeFromIndex)
+
+ def __call__(self):
+ return '%s(metadata.getFromIndex("%s", "%s", "%s", "%s", "%s"))' % (
+ self.context.coll1.__name__,
+ self.context.expr1,
+ self.context.expr2,
+ self.context.lowerbound,
+ self.context.upperbound)
+
+
class IfCompiler(BaseCompiler):
implements(IAlgebraCompiler)
adapts(IIf)
@@ -240,6 +253,7 @@
provideAdapter(ReduceCompiler)
provideAdapter(RangeCompiler)
provideAdapter(MakeCompiler)
+ provideAdapter(MakeFromIndexCompiler)
provideAdapter(IfCompiler)
provideAdapter(LambdaCompiler)
provideAdapter(ConstantCompiler)
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/database/metadata.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/database/metadata.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/database/metadata.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -106,6 +106,9 @@
results = catalog.apply({iname:(lowerbound, upperbound)})
obj_list = [intids.getObject(result) for result in results]
return obj_list
+ #I could check whether property has an index by hasPropertyIndex.
+ #But by this approach this always returns IF objects
+ return self.getAll(klass)
def hasPropertyIndex(self, klass, property):
catalogs = getUtilitiesFor(ICatalog)
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/algebra.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/algebra.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/algebra.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -24,6 +24,7 @@
def __init__(self, tree):
name = 'head'
self.tree = tree
+ locate(tree, self, 'tree')
def __repr__(self):
return ('%s') % (self.tree)
@@ -182,6 +183,24 @@
return "Make(%s, %s, %s)" %(self.coll1, self.coll2, self.expr1)
+class MakeFromIndex(BaseAlgebra):
+
+ implements(IMakeFromIndex)
+
+ def __init__(self, coll1, coll2, expr1, expr2, lowerbound='A', upperbound='Z'):
+ BaseAlgebra.__init__(self)
+ self.setProp('expr1', expr1)
+ self.setProp('expr2', expr2)
+ self.setProp('coll1', coll1)
+ self.setProp('coll2', coll2)
+ self.setProp('lowerbound', lowerbound)
+ self.setProp('upperbound', upperbound)
+
+ def __repr__(self):
+ return "MakeFromIndex(%s, %s, %s, %s, %s, %s)" % (
+ self.coll1, self.coll2, self.expr1, self.expr2, self.lowerbound, self.upperbound)
+
+
#class And:
#class Being:
Modified: Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/interfaces.py
===================================================================
--- Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/interfaces.py 2008-07-19 17:23:32 UTC (rev 88610)
+++ Sandbox/adamg/ocql/branches/optimize-with-index/src/ocql/rewriter/interfaces.py 2008-07-19 17:47:26 UTC (rev 88611)
@@ -81,6 +81,18 @@
coll2 = Attribute('second collection')
+class IMakeFromIndex(IAlgebraObject):
+ """Objects providing this interface represent the
+ MakeFromIndex Algebra object
+ """
+ expr1 = Attribute('expression1')
+ expr2 = Attribute('expression2')
+ coll1 = Attribute('first collection')
+ coll2 = Attribute('second collection')
+ lowerbound = Attribute('lower bound of the query')
+ upperbound = Attribute('upper bound of the query')
+
+
class IIf(IAlgebraObject):
"""Objects providing this interface represent the
If Algebra object
More information about the Checkins
mailing list