[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