Merge lp:~jamesh/storm/bug-242813 into lp:storm

[James Henstridge]

[James Henstridge (jamesh)]

Flatten nested set expressions as they are built so that we are less likely to hit Python's recursion limit when compiling the expression to SQL.

This relies on the left associativity of all the set expressions. (i.e. that Union(Union(a, b), c) is equivalent to Union(a, b, c)).

[Jamu Kakar (jkakar)]

Nice and simple, +1.

review: Approve

[GabrielGrant (gabrielgrant)]

The tests pass, and this fixes a problem I've run into, so I'm eager to see this pushed into mainline.

A few questions:

Should there be a test to explicitly check that heterogeneous set expressions are not flattened? (ie exercising the negative branch of the second if statement)

Is it necessary to skip expressions containing an order_by? If the order_by is the same on each expr, shouldn't the result of the nested and un-nested expressions be equivalent? (I may very well be totally wrong about this, but I can't seem to cook up a counter-example at the moment)

It appears that in addition to addressing https://bugs.edge.launchpad.net/storm/+bug/242813 this patch also should fix some of https://bugs.edge.launchpad.net/storm/+bug/309276 (which is a problem I'm having), however I don't think it addresses it fully. The proposed solution doesn't tackle heterogeneous nested set queries, which will still fail on MySQL. http://bugs.mysql.com/bug.php?id=3347 http://bugs.mysql.com/bug.php?id=2435 and http://bugs.mysql.com/bug.php?id=7360 seem to imply that there is a problem with MySQL that basically makes some such nested queries impossible to express, however simpler ones like (SELECT ...) UNION (SELECT ...) INTERSECT (SELECT ...) are supported in MySQL, but (I believe) can't be achieved through Storm itself.

Could/should there be a more graceful failure for these cases than a MySQL parse error? (Sorry if this is too far off track. Perhaps this discussion would be better continued on the appropriate bug? I've subscribed myself)

Cheers!

[James Henstridge (jamesh)]

> The tests pass, and this fixes a problem I've run into, so I'm eager to see
> this pushed into mainline.
>
> A few questions:
>
> Should there be a test to explicitly check that heterogeneous set expressions
> are not flattened? (ie exercising the negative branch of the second if
> statement)

Yep. There should be a test for that.

> Is it necessary to skip expressions containing an order_by? If the order_by is
> the same on each expr, shouldn't the result of the nested and un-nested
> expressions be equivalent? (I may very well be totally wrong about this, but I
> can't seem to cook up a counter-example at the moment)

I guess I wrote the code that way to be on the safe side: except in the case of MySQL's broken query parser, this branch is mainly designed to improve performance.

That said, the test can probably go. If the outer set expression has an order, then the inner set expression's ordering doesn't matter. If the outer expression has no order, then there is no guarantee on the ordering so we should be able to ignore it in that case too.

I'll remove the check.

> It appears that in addition to addressing
> https://bugs.edge.launchpad.net/storm/+bug/242813 this patch also should fix
> some of https://bugs.edge.launchpad.net/storm/+bug/309276 (which is a problem
> I'm having), however I don't think it addresses it fully. The proposed
> solution doesn't tackle heterogeneous nested set queries, which will still
> fail on MySQL. http://bugs.mysql.com/bug.php?id=3347
> http://bugs.mysql.com/bug.php?id=2435 and
> http://bugs.mysql.com/bug.php?id=7360 seem to imply that there is a problem
> with MySQL that basically makes some such nested queries impossible to
> express, however simpler ones like (SELECT ...) UNION (SELECT ...) INTERSECT
> (SELECT ...) are supported in MySQL, but (I believe) can't be achieved through
> Storm itself.

It might be possible to fix up that sort of chaining by playing with the operator precedences in the expression compiler.

> Could/should there be a more graceful failure for these cases than a MySQL
> parse error? (Sorry if this is too far off track. Perhaps this discussion
> would be better continued on the appropriate bug? I've subscribed myself)

I don't think it is worth the trouble. Writing code to detect expressions that will cause the MySQL query parser trouble is probably as much work as adjusting our expression generators to make expressions that don't trigger bugs in the MySQL query parser.

[lp:~jamesh/storm/bug-242813]

331. By James Henstridge on 2009-10-21

Collapse set expressions with order_by set, and add some extra tests.

=== modified file 'storm/expr.py'
--- storm/expr.py	2009-07-31 01:53:08 +0000
+++ storm/expr.py	2009-10-21 09:48:13 +0000
@@ -1099,6 +1099,16 @@
         self.order_by = kwargs.get("order_by", Undef)
         self.limit = kwargs.get("limit", Undef)
         self.offset = kwargs.get("offset", Undef)
+        # If the first expression is of a compatible type, directly
+        # include its sub expressions.
+        if len(self.exprs) > 0:
+            first = self.exprs[0]
+            if (isinstance(first, self.__class__) and
+                first.all == self.all and
+                first.limit is Undef and
+                first.offset is Undef):
+                self.exprs = first.exprs + self.exprs[1:]
+
 
 @compile.when(SetExpr)
 def compile_set_expr(compile, expr, state):

=== modified file 'tests/expr.py'
--- tests/expr.py	2009-07-23 22:47:10 +0000
+++ tests/expr.py	2009-10-21 09:48:13 +0000
@@ -275,6 +275,35 @@
         self.assertEquals(expr.limit, 1)
         self.assertEquals(expr.offset, 2)
 
+    def test_union_collapse(self):
+        expr = Union(Union(elem1, elem2), elem3)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Only first expression is collapsed.
+        expr = Union(elem1, Union(elem2, elem3))
+        self.assertEquals(expr.exprs[0], elem1)
+        self.assertTrue(isinstance(expr.exprs[1], Union))
+
+        # Don't collapse if all is different.
+        expr = Union(Union(elem1, elem2, all=True), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+        expr = Union(Union(elem1, elem2), elem3, all=True)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+        expr = Union(Union(elem1, elem2, all=True), elem3, all=True)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Don't collapse if limit or offset are set.
+        expr = Union(Union(elem1, elem2, limit=1), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+        expr = Union(Union(elem1, elem2, offset=3), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+
+        # Don't collapse other set expressions.
+        expr = Union(Except(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+        expr = Union(Intersect(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+
     def test_except(self):
         expr = Except(elem1, elem2, elem3)
         self.assertEquals(expr.exprs, (elem1, elem2, elem3))
@@ -287,6 +316,35 @@
         self.assertEquals(expr.limit, 1)
         self.assertEquals(expr.offset, 2)
 
+    def test_except_collapse(self):
+        expr = Except(Except(elem1, elem2), elem3)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Only first expression is collapsed.
+        expr = Except(elem1, Except(elem2, elem3))
+        self.assertEquals(expr.exprs[0], elem1)
+        self.assertTrue(isinstance(expr.exprs[1], Except))
+
+        # Don't collapse if all is different.
+        expr = Except(Except(elem1, elem2, all=True), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+        expr = Except(Except(elem1, elem2), elem3, all=True)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+        expr = Except(Except(elem1, elem2, all=True), elem3, all=True)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Don't collapse if limit or offset are set.
+        expr = Except(Except(elem1, elem2, limit=1), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+        expr = Except(Except(elem1, elem2, offset=3), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+
+        # Don't collapse other set expressions.
+        expr = Except(Union(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+        expr = Except(Intersect(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+
     def test_intersect(self):
         expr = Intersect(elem1, elem2, elem3)
         self.assertEquals(expr.exprs, (elem1, elem2, elem3))
@@ -300,6 +358,35 @@
         self.assertEquals(expr.limit, 1)
         self.assertEquals(expr.offset, 2)
 
+    def test_intersect_collapse(self):
+        expr = Intersect(Intersect(elem1, elem2), elem3)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Only first expression is collapsed.
+        expr = Intersect(elem1, Intersect(elem2, elem3))
+        self.assertEquals(expr.exprs[0], elem1)
+        self.assertTrue(isinstance(expr.exprs[1], Intersect))
+
+        # Don't collapse if all is different.
+        expr = Intersect(Intersect(elem1, elem2, all=True), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+        expr = Intersect(Intersect(elem1, elem2), elem3, all=True)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+        expr = Intersect(Intersect(elem1, elem2, all=True), elem3, all=True)
+        self.assertEquals(expr.exprs, (elem1, elem2, elem3))
+
+        # Don't collapse if limit or offset are set.
+        expr = Intersect(Intersect(elem1, elem2, limit=1), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+        expr = Intersect(Intersect(elem1, elem2, offset=3), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Intersect))
+
+        # Don't collapse other set expressions.
+        expr = Intersect(Union(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Union))
+        expr = Intersect(Except(elem1, elem2), elem3)
+        self.assertTrue(isinstance(expr.exprs[0], Except))
+
     def test_auto_tables(self):
         expr = AutoTables(elem1, [elem2])
         self.assertEquals(expr.expr, elem1)