Merge lp:~mmcm/akiban-server/sql-subquery-aggregate-bound-tables into lp:~akiban-technologies/akiban-server/trunk

[Mike McMahon]

Don't try to remap a column after an aggregate if it comes from a table bound by an outer query.

See new test or query in associated bug. But note that these kinds of queries where this issues arises may not be executed very efficiently in cases where join ordering decides to execute the subquery repeatedly.

[Thomas Jones-Low (tjoneslo)]

As described

review: Approve

=== modified file 'src/main/java/com/akiban/sql/optimizer/rule/AggregateMapper.java'
--- src/main/java/com/akiban/sql/optimizer/rule/AggregateMapper.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/AggregateMapper.java	2013-07-22 18:00:43 +0000
@@ -48,53 +48,49 @@
 
     @Override
     public void apply(PlanContext plan) {
-        List<AggregateSource> sources = new AggregateSourceFinder().find(plan.getPlan());
-        for (AggregateSource source : sources) {
-            Mapper m = new Mapper(plan.getRulesContext(), source);
-            m.remap(source);
+        List<AggregateSourceState> sources = new AggregateSourceFinder(plan).find();
+        for (AggregateSourceState source : sources) {
+            Mapper m = new Mapper(plan.getRulesContext(), source.aggregateSource, source.containingQuery);
+            m.remap(source.aggregateSource);
         }
     }
 
-    static class AggregateSourceFinder implements PlanVisitor, ExpressionVisitor {
-        List<AggregateSource> result = new ArrayList<>();
-
-        public List<AggregateSource> find(PlanNode root) {
-            root.accept(this);
+    static class AggregateSourceFinder extends SubqueryBoundTablesTracker {
+        List<AggregateSourceState> result = new ArrayList<>();
+
+        public AggregateSourceFinder(PlanContext planContext) {
+            super(planContext);
+        }
+
+        public List<AggregateSourceState> find() {
+            run();
             return result;
         }
 
         @Override
-        public boolean visitEnter(PlanNode n) {
-            return visit(n);
-        }
-        @Override
-        public boolean visitLeave(PlanNode n) {
-            return true;
-        }
-        @Override
         public boolean visit(PlanNode n) {
+            super.visit(n);
             if (n instanceof AggregateSource)
-                result.add((AggregateSource)n);
-            return true;
-        }
-
-        @Override
-        public boolean visitEnter(ExpressionNode n) {
-            return visit(n);
-        }
-        @Override
-        public boolean visitLeave(ExpressionNode n) {
-            return true;
-        }
-        @Override
-        public boolean visit(ExpressionNode n) {
-            return true;
+                result.add(new AggregateSourceState((AggregateSource)n, currentQuery()));
+            return true;
+        }
+    }
+
+    static class AggregateSourceState {
+        AggregateSource aggregateSource;
+        BaseQuery containingQuery;
+
+        public AggregateSourceState(AggregateSource aggregateSource, 
+                                    BaseQuery containingQuery) {
+            this.aggregateSource = aggregateSource;
+            this.containingQuery = containingQuery;
         }
     }
 
     static class Mapper implements ExpressionRewriteVisitor {
         private RulesContext rulesContext;
         private AggregateSource source;
+        private BaseQuery query;
         private Set<ColumnSource> aggregated = new HashSet<>();
         private Map<ExpressionNode,ExpressionNode> map = 
             new HashMap<>();
@@ -119,9 +115,10 @@
             return implicitAggregateSetting;
         }
 
-        public Mapper(RulesContext rulesContext, AggregateSource source) {
+        public Mapper(RulesContext rulesContext, AggregateSource source, BaseQuery query) {
             this.rulesContext = rulesContext;
             this.source = source;
+            this.query = query;
             aggregated.add(source);
             // Map all the group by expressions at the start.
             // This means that if you GROUP BY x+1, you can ORDER BY
@@ -184,7 +181,9 @@
             }
             if (expr instanceof ColumnExpression) {
                 ColumnExpression column = (ColumnExpression)expr;
-                if (!aggregated.contains(column.getTable())) {
+                ColumnSource table = column.getTable();
+                if (!aggregated.contains(table) &&
+                    !query.getOuterTables().contains(table)) {
                     return nonAggregate(column);
                 }
             }

=== modified file 'src/main/java/com/akiban/sql/optimizer/rule/AggregateSplitter.java'
--- src/main/java/com/akiban/sql/optimizer/rule/AggregateSplitter.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/AggregateSplitter.java	2013-07-22 18:00:43 +0000
@@ -18,6 +18,7 @@
 package com.akiban.sql.optimizer.rule;
 
 import com.akiban.sql.optimizer.rule.AggregateMapper.AggregateSourceFinder;
+import com.akiban.sql.optimizer.rule.AggregateMapper.AggregateSourceState;
 
 import com.akiban.server.error.UnsupportedSQLException;
 
@@ -43,9 +44,9 @@
 
     @Override
     public void apply(PlanContext plan) {
-        List<AggregateSource> sources = new AggregateSourceFinder().find(plan.getPlan());
-        for (AggregateSource source : sources) {
-            split(source);
+        List<AggregateSourceState> sources = new AggregateSourceFinder(plan).find();
+        for (AggregateSourceState source : sources) {
+            split(source.aggregateSource);
         }
     }
 

=== modified file 'src/main/java/com/akiban/sql/optimizer/rule/JoinAndIndexPicker.java'
--- src/main/java/com/akiban/sql/optimizer/rule/JoinAndIndexPicker.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/JoinAndIndexPicker.java	2013-07-22 18:00:43 +0000
@@ -47,10 +47,7 @@
 
     @Override
     public void apply(PlanContext planContext) {
-        BaseQuery query = (BaseQuery)planContext.getPlan();
-        List<Picker> pickers = 
-            new JoinsFinder(planContext)
-            .find(query);
+        List<Picker> pickers = new JoinsFinder(planContext).find();
         for (Picker picker : pickers) {
             picker.apply();
         }
@@ -943,73 +940,39 @@
         }
     }
     
-    // Purpose is twofold: 
     // Find top-level joins and note what query they come from; 
-    // Annotate subqueries with their outer table references.
     // Top-level queries and those used in expressions are returned directly.
     // Derived tables are deferred, since they need to be planned in
     // the context of various join orders to allow for join predicated
     // to be pushed "inside." So they are stored in a Map accessible
     // to other Pickers.
-    static class JoinsFinder implements PlanVisitor, ExpressionVisitor {
+    static class JoinsFinder extends SubqueryBoundTablesTracker {
         List<Picker> result;
         Map<SubquerySource,Picker> subpickers;
-        BaseQuery rootQuery;
-        Deque<SubqueryState> subqueries = new ArrayDeque<>();
-        PlanContext planContext;
 
         public JoinsFinder(PlanContext planContext) {
-            this.planContext = planContext;
+            super(planContext);
         }
 
-        public List<Picker> find(BaseQuery query) {
+        public List<Picker> find() {
             result = new ArrayList<>();
             subpickers = new HashMap<>();
-            rootQuery = query;
-            query.accept(this);
+            run();
             result.removeAll(subpickers.values()); // Do these in context.
             return result;
         }
 
         @Override
-        public boolean visitEnter(PlanNode n) {
-            if (n instanceof Subquery) {
-                subqueries.push(new SubqueryState((Subquery)n));
-                return true;
-            }
-            return visit(n);
-        }
-
-        @Override
-        public boolean visitLeave(PlanNode n) {
-            if (n instanceof Subquery) {
-                SubqueryState s = subqueries.pop();
-                Set<ColumnSource> outerTables = s.getTablesReferencedButNotDefined();
-                s.subquery.setOuterTables(outerTables);
-                if (!subqueries.isEmpty())
-                    subqueries.peek().tablesReferenced.addAll(outerTables);
-            }
-            return true;
-        }
-
-        @Override
         public boolean visit(PlanNode n) {
-            if (!subqueries.isEmpty() &&
-                (n instanceof ColumnSource)) {
-                boolean added = subqueries.peek().tablesDefined.add((ColumnSource)n);
-                assert added : "Table defined more than once";
-            }
+            super.visit(n);
             if ((n instanceof Joinable) && !(n instanceof TableSource)) {
                 Joinable j = (Joinable)n;
                 while (j.getOutput() instanceof Joinable)
                     j = (Joinable)j.getOutput();
-                BaseQuery query = rootQuery;
+                BaseQuery query = currentQuery();
                 SubquerySource subquerySource = null;
-                if (!subqueries.isEmpty()) {
-                    query = subqueries.peek().subquery;
-                    if (query.getOutput() instanceof SubquerySource)
-                        subquerySource = (SubquerySource)query.getOutput();
-                }
+                if (query.getOutput() instanceof SubquerySource)
+                    subquerySource = (SubquerySource)query.getOutput();
                 for (Picker picker : result) {
                     if (picker.joinable == j)
                         // Already have another set of joins to same root join.
@@ -1022,40 +985,5 @@
             }
             return true;
         }
-
-        @Override
-        public boolean visitEnter(ExpressionNode n) {
-            return visit(n);
-        }
-
-        @Override
-        public boolean visitLeave(ExpressionNode n) {
-            return true;
-        }
-
-        @Override
-        public boolean visit(ExpressionNode n) {
-            if (!subqueries.isEmpty() &&
-                (n instanceof ColumnExpression)) {
-                subqueries.peek().tablesReferenced.add(((ColumnExpression)n).getTable());
-            }
-            return true;
-        }
-    }
-
-    static class SubqueryState {
-        Subquery subquery;
-        Set<ColumnSource> tablesReferenced = new HashSet<>();
-        Set<ColumnSource> tablesDefined = new HashSet<>();
-
-        public SubqueryState(Subquery subquery) {
-            this.subquery = subquery;
-        }
-
-        public Set<ColumnSource> getTablesReferencedButNotDefined() {
-            tablesReferenced.removeAll(tablesDefined);
-            return tablesReferenced;
-        }
-    }
-
+    }
 }

=== added file 'src/main/java/com/akiban/sql/optimizer/rule/SubqueryBoundTablesTracker.java'
--- src/main/java/com/akiban/sql/optimizer/rule/SubqueryBoundTablesTracker.java	1970-01-01 00:00:00 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/SubqueryBoundTablesTracker.java	2013-07-22 18:00:43 +0000
@@ -0,0 +1,112 @@
+/**
+ * Copyright (C) 2009-2013 Akiban Technologies, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+package com.akiban.sql.optimizer.rule;
+
+import com.akiban.sql.optimizer.plan.*;
+
+import java.util.*;
+
+/** Annotate subqueries with their outer table references. */
+public abstract class SubqueryBoundTablesTracker implements PlanVisitor, ExpressionVisitor {
+    protected PlanContext planContext;
+    protected BaseQuery rootQuery;
+    protected Deque<SubqueryState> subqueries = new ArrayDeque<>();
+
+    protected SubqueryBoundTablesTracker(PlanContext planContext) {
+        this.planContext = planContext;
+    }
+
+    protected void run() {
+        rootQuery = (BaseQuery)planContext.getPlan();
+        rootQuery.accept(this);
+    }
+
+    @Override
+    public boolean visitEnter(PlanNode n) {
+        if (n instanceof Subquery) {
+            subqueries.push(new SubqueryState((Subquery)n));
+            return true;
+        }
+        return visit(n);
+    }
+    
+    @Override
+    public boolean visitLeave(PlanNode n) {
+        if (n instanceof Subquery) {
+            SubqueryState s = subqueries.pop();
+            Set<ColumnSource> outerTables = s.getTablesReferencedButNotDefined();
+            s.subquery.setOuterTables(outerTables);
+            if (!subqueries.isEmpty())
+                subqueries.peek().tablesReferenced.addAll(outerTables);
+        }
+        return true;
+    }
+
+    @Override
+    public boolean visit(PlanNode n) {
+        if (!subqueries.isEmpty() &&
+            (n instanceof ColumnSource)) {
+            boolean added = subqueries.peek().tablesDefined.add((ColumnSource)n);
+            assert added : "Table defined more than once";
+        }
+        return true;
+    }
+
+    @Override
+    public boolean visitEnter(ExpressionNode n) {
+        return visit(n);
+    }
+
+    @Override
+    public boolean visitLeave(ExpressionNode n) {
+        return true;
+    }
+
+    @Override
+    public boolean visit(ExpressionNode n) {
+        if (!subqueries.isEmpty() &&
+            (n instanceof ColumnExpression)) {
+            subqueries.peek().tablesReferenced.add(((ColumnExpression)n).getTable());
+        }
+        return true;
+    }
+
+    protected BaseQuery currentQuery() {
+        if (subqueries.isEmpty()) {
+            return rootQuery;
+        }
+        else {
+            return subqueries.peek().subquery;
+        }
+    }
+
+    static class SubqueryState {
+        Subquery subquery;
+        Set<ColumnSource> tablesReferenced = new HashSet<>();
+        Set<ColumnSource> tablesDefined = new HashSet<>();
+
+        public SubqueryState(Subquery subquery) {
+            this.subquery = subquery;
+        }
+
+        public Set<ColumnSource> getTablesReferencedButNotDefined() {
+            tablesReferenced.removeAll(tablesDefined);
+            return tablesReferenced;
+        }
+    }
+}

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/aggregate/README.txt'
--- src/test/resources/com/akiban/sql/optimizer/rule/aggregate/README.txt	2013-01-10 22:09:09 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/aggregate/README.txt	2013-07-22 18:00:43 +0000
@@ -26,6 +26,8 @@
 
 order-by-distinct: ORDER BY expression also DISTINCT
 
+subquery-1: a subquery with outer table comparison
+
 sum-all: aggregate without GROUP BY
 
 update: UPDATE to aggregate subexpression

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.expected	2013-07-22 18:00:43 +0000
@@ -0,0 +1,14 @@
+SelectQuery@56686e67
+  ResultSet@62285882[name]
+    Project@46caf126[customers.name]
+      Select@359e1a19[ANY(Subquery@1ec37acf)]
+        TableSource@b1de02c(customers)
+
+Subquery@1ec37acf
+  Project@3b31a09c[customers.cid == GROUP[0]]
+    Select@33b3bbd0[]
+      AggregateSource@37278020([orders.cid, orders.order_date],[])
+        Select@5cef6f34[items.sku == 1234]
+          JoinNode@6b6dee96(INNER[orders.oid == items.oid])
+            TableSource@24cd12a(orders)
+            TableSource@1381d94(items)
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/aggregate/subquery-1.sql	2013-07-22 18:00:43 +0000
@@ -0,0 +1,4 @@
+SELECT name FROM customers 
+ WHERE cid IN (SELECT orders.cid FROM orders INNER JOIN items USING (oid) 
+                WHERE sku = '1234'
+                GROUP BY orders.cid, orders.order_date)
\ No newline at end of file