asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [23/51] [partial] incubator-asterixdb-hyracks git commit: Change folder structure for Java repackage
Date Tue, 25 Aug 2015 16:41:36 GMT
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPlotter.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPlotter.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPlotter.java
new file mode 100644
index 0000000..85274de
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPlotter.java
@@ -0,0 +1,139 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.prettyprint;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.Random;
+
+import org.apache.commons.io.FileUtils;
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+
+public class PlanPlotter {
+
+    static Random randomGenerator = new Random();
+
+    public static void printLogicalPlan(ILogicalPlan plan) throws AlgebricksException {
+        int indent = 5;
+        StringBuilder out = new StringBuilder();
+        int randomInt = 10000 + randomGenerator.nextInt(100);
+        appendln(out, "digraph G {");
+        for (Mutable<ILogicalOperator> root : plan.getRoots()) {
+            printVisualizationGraph((AbstractLogicalOperator) root.getValue(), indent, out, "", randomInt);
+        }
+        appendln(out, "\n}\n}");
+        try {
+            File file = File.createTempFile("logicalPlan", ".txt");
+            FileUtils.writeStringToFile(file, out.toString());
+            file.deleteOnExit();
+        } catch (IOException e) {
+            e.printStackTrace();
+        }
+    }
+
+    public static void printOptimizedLogicalPlan(ILogicalPlan plan) throws AlgebricksException {
+        int indent = 5;
+        StringBuilder out = new StringBuilder();
+        int randomInt = 10000 + randomGenerator.nextInt(100);
+        appendln(out, "digraph G {");
+        for (Mutable<ILogicalOperator> root : plan.getRoots()) {
+            printVisualizationGraph((AbstractLogicalOperator) root.getValue(), indent, out, "", randomInt);
+        }
+        appendln(out, "\n}\n}");
+        try {
+            File file = File.createTempFile("logicalOptimizedPlan", ".txt");
+            FileUtils.writeStringToFile(file, out.toString());
+            file.deleteOnExit();
+        } catch (IOException e) {
+            e.printStackTrace();
+        }
+    }
+
+    /*
+     * DFS traversal function. Calls iteratively all children, and for each calls itself recursively
+     * Includes slim-maps only (no gathering of mappers to one)
+     */
+    public static void printVisualizationGraph(AbstractLogicalOperator op, int indent, StringBuilder out,
+            String current_supernode_name, int randomInt) {
+        if (!op.getInputs().isEmpty()) {
+            //String stringToVisualize = op.toStringForVisualizationGraph();
+            String stringToVisualize = op.getOperatorTag().name();
+            int firstOccurenceOf_ = stringToVisualize.indexOf("_");
+            String supernode_current = stringToVisualize.substring(firstOccurenceOf_ + 1, stringToVisualize.length());
+            if (current_supernode_name.isEmpty()) {
+                current_supernode_name = supernode_current;
+                appendln(out, new String("subgraph cluster_" + supernode_current + " {"));
+                pad(out, indent);
+                appendln(out, new String("node [style=filled, color = lightgray];"));
+                pad(out, indent);
+                appendln(out, new String("color=blue;"));
+                pad(out, indent);
+                String op_id = op.toString().substring(op.toString().indexOf("@") + 1, op.toString().length());
+                appendln(out, new String("label = \"" + supernode_current + "ID" + op_id + "\";"));
+                pad(out, indent);
+            }
+
+            for (Mutable<ILogicalOperator> i : op.getInputs()) {
+                String op_id = i.toString().substring(i.toString().indexOf("@") + 1, i.toString().length());
+                String logOpStr = ((AbstractLogicalOperator) i.getValue()).getOperatorTag().name() + "ID" + op_id;
+                firstOccurenceOf_ = logOpStr.indexOf("_");
+                String supernode_child = logOpStr.substring(firstOccurenceOf_ + 1, logOpStr.length());
+                if (!supernode_current.equals(supernode_child)) {
+                    appendln(out, new String("node [style=filled, color = lightgray];"));
+                    pad(out, indent);
+                    appendln(out, new String("color=blue"));
+                    pad(out, indent);
+                    appendln(out, new String("label = \"" + supernode_child + "\";"));
+                    pad(out, indent);
+                }
+
+                op_id = op.toString().substring(op.toString().indexOf("@") + 1, op.toString().length());
+                appendln(out, stringToVisualize + "ID" + op_id + "[style = filled]");
+                AbstractLogicalOperator child = (AbstractLogicalOperator) i.getValue();
+
+                pad(out, indent);
+                String op_id1 = op.toString().substring(op.toString().indexOf("@") + 1, op.toString().length());
+                append(out, op.getOperatorTag().name() + "ID" + op_id1 + " -> ");
+                String opc_id = child.toString()
+                        .substring(child.toString().indexOf("@") + 1, child.toString().length());
+                appendln(out, child.getOperatorTag().name() + "ID" + opc_id);
+
+                printVisualizationGraph(child, indent, out, supernode_current, (randomGenerator.nextInt(100) + 10000));
+
+            }
+        }
+
+    }
+
+    private static void appendln(StringBuilder buf, String s) {
+        buf.append(s);
+        buf.append("\n");
+    }
+
+    private static void append(StringBuilder buf, String s) {
+        buf.append(s);
+    }
+
+    private static void pad(StringBuilder buf, int indent) {
+        for (int i = 0; i < indent; ++i) {
+            buf.append(' ');
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPrettyPrinter.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPrettyPrinter.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPrettyPrinter.java
new file mode 100644
index 0000000..33c106b
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/prettyprint/PlanPrettyPrinter.java
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.prettyprint;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IPhysicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractOperatorWithNestedPlans;
+
+public class PlanPrettyPrinter {
+    public static void printPlan(ILogicalPlan plan, StringBuilder out, LogicalOperatorPrettyPrintVisitor pvisitor,
+            int indent) throws AlgebricksException {
+        for (Mutable<ILogicalOperator> root : plan.getRoots()) {
+            printOperator((AbstractLogicalOperator) root.getValue(), out, pvisitor, indent);
+        }
+    }
+
+    public static void printPhysicalOps(ILogicalPlan plan, StringBuilder out, int indent) {
+        for (Mutable<ILogicalOperator> root : plan.getRoots()) {
+            printPhysicalOperator((AbstractLogicalOperator) root.getValue(), indent, out);
+        }
+    }
+
+    public static void printOperator(AbstractLogicalOperator op, StringBuilder out,
+            LogicalOperatorPrettyPrintVisitor pvisitor, int indent) throws AlgebricksException {
+        out.append(op.accept(pvisitor, indent));
+        IPhysicalOperator pOp = op.getPhysicalOperator();
+
+        if (pOp != null) {
+            out.append("\n");
+            pad(out, indent);
+            appendln(out, "-- " + pOp.toString() + "  |" + op.getExecutionMode() + "|");
+        } else {
+            appendln(out, " -- |" + op.getExecutionMode() + "|");
+        }
+
+        for (Mutable<ILogicalOperator> i : op.getInputs()) {
+            printOperator((AbstractLogicalOperator) i.getValue(), out, pvisitor, indent + 2);
+        }
+
+    }
+
+    public static void printPhysicalOperator(AbstractLogicalOperator op, int indent, StringBuilder out) {
+        IPhysicalOperator pOp = op.getPhysicalOperator();
+        pad(out, indent);
+        appendln(out, "-- " + pOp.toString() + "  |" + op.getExecutionMode() + "|");
+        if (op.hasNestedPlans()) {
+            AbstractOperatorWithNestedPlans opNest = (AbstractOperatorWithNestedPlans) op;
+            for (ILogicalPlan p : opNest.getNestedPlans()) {
+                pad(out, indent + 8);
+                appendln(out, "{");
+                printPhysicalOps(p, out, indent + 10);
+                pad(out, indent + 8);
+                appendln(out, "}");
+            }
+        }
+
+        for (Mutable<ILogicalOperator> i : op.getInputs()) {
+            printPhysicalOperator((AbstractLogicalOperator) i.getValue(), indent + 2, out);
+        }
+
+    }
+
+    private static void appendln(StringBuilder buf, String s) {
+        buf.append(s);
+        buf.append("\n");
+    }
+
+    private static void pad(StringBuilder buf, int indent) {
+        for (int i = 0; i < indent; ++i) {
+            buf.append(' ');
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
new file mode 100644
index 0000000..b757bbb
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public abstract class AbstractGroupingProperty {
+    protected Set<LogicalVariable> columnSet;
+
+    public AbstractGroupingProperty(Set<LogicalVariable> columnSet) {
+        this.columnSet = columnSet;
+    }
+
+    public Set<LogicalVariable> getColumnSet() {
+        return columnSet;
+    }
+
+    public final void normalizeGroupingColumns(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+            List<FunctionalDependency> fds) {
+        replaceGroupingColumnsByEqClasses(equivalenceClasses);
+        applyFDsToGroupingColumns(fds);
+    }
+
+    private void replaceGroupingColumnsByEqClasses(Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+        if (equivalenceClasses == null || equivalenceClasses.isEmpty()) {
+            return;
+        }
+        Set<LogicalVariable> norm = new ListSet<LogicalVariable>();
+        for (LogicalVariable v : columnSet) {
+            EquivalenceClass ec = equivalenceClasses.get(v);
+            if (ec == null) {
+                norm.add(v);
+            } else {
+                if (ec.representativeIsConst()) {
+                    // trivially satisfied, so the var. can be removed
+                } else {
+                    norm.add(ec.getVariableRepresentative());
+                }
+            }
+        }
+        columnSet = norm;
+    }
+
+    private void applyFDsToGroupingColumns(List<FunctionalDependency> fds) {
+        // the set of vars. is unordered
+        // so we try all FDs on all variables (incomplete algo?)
+        if (fds == null || fds.isEmpty()) {
+            return;
+        }
+        Set<LogicalVariable> norm = new ListSet<LogicalVariable>();
+        for (LogicalVariable v : columnSet) {
+            boolean isImpliedByAnFD = false;
+            for (FunctionalDependency fdep : fds) {
+                if (columnSet.containsAll(fdep.getHead()) && fdep.getTail().contains(v)) {
+                    isImpliedByAnFD = true;
+                    norm.addAll(fdep.getHead());
+                    break;
+                }
+
+            }
+            if (!isImpliedByAnFD) {
+                norm.add(v);
+            }
+        }
+        columnSet = norm;
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/BroadcastPartitioningProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/BroadcastPartitioningProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/BroadcastPartitioningProperty.java
new file mode 100644
index 0000000..53aea68
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/BroadcastPartitioningProperty.java
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public class BroadcastPartitioningProperty implements IPartitioningProperty {
+
+    private INodeDomain domain;
+
+    public BroadcastPartitioningProperty(INodeDomain domain) {
+        this.domain = domain;
+    }
+
+    @Override
+    public PartitioningType getPartitioningType() {
+        return PartitioningType.BROADCAST;
+    }
+
+    @Override
+    public void normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+        // do nothing
+    }
+
+    @Override
+    public void getColumns(Collection<LogicalVariable> columns) {
+    }
+
+    @Override
+    public INodeDomain getNodeDomain() {
+        return domain;
+    }
+
+    @Override
+    public void setNodeDomain(INodeDomain domain) {
+        this.domain = domain;
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/DefaultNodeGroupDomain.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/DefaultNodeGroupDomain.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/DefaultNodeGroupDomain.java
new file mode 100644
index 0000000..226f02c
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/DefaultNodeGroupDomain.java
@@ -0,0 +1,39 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public class DefaultNodeGroupDomain implements INodeDomain {
+
+    private String groupName;
+
+    public DefaultNodeGroupDomain(String groupName) {
+        this.groupName = groupName;
+    }
+
+    @Override
+    public boolean sameAs(INodeDomain domain) {
+        return true;
+    }
+
+    @Override
+    public String toString() {
+        return "AsterixDomain(" + groupName + ")";
+    }
+
+    @Override
+    public Integer cardinality() {
+        return null;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FileSplitDomain.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FileSplitDomain.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FileSplitDomain.java
new file mode 100644
index 0000000..5fbcdb9
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FileSplitDomain.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import edu.uci.ics.hyracks.dataflow.std.file.FileSplit;
+
+public class FileSplitDomain implements INodeDomain {
+
+    private FileSplit[] splits;
+
+    public FileSplitDomain(FileSplit[] splits) {
+        this.splits = splits;
+    }
+
+    @Override
+    public Integer cardinality() {
+        return splits.length;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder();
+        sb.append("FileSplitDomain[");
+        boolean fst = true;
+        for (FileSplit fs : splits) {
+            if (fst) {
+                fst = false;
+            } else {
+                sb.append(", ");
+            }
+            sb.append(fs.getNodeName() + ":" + fs.getLocalFile());
+        }
+        sb.append(']');
+        return sb.toString();
+    }
+
+    @Override
+    public boolean sameAs(INodeDomain domain) {
+        if (!(domain instanceof FileSplitDomain)) {
+            return false;
+        }
+        FileSplitDomain fsd = (FileSplitDomain) domain;
+        if (fsd.splits.length != splits.length) {
+            return false;
+        }
+        // conservative approach...
+        for (int i = 0; i < splits.length; i++) {
+            if (!ncEq(splits[i], fsd.splits[i])) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    private boolean ncEq(FileSplit fs1, FileSplit fs2) {
+        return fs1.getNodeName().equals(fs2.getNodeName());
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FilteredVariablePropagationPolicy.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FilteredVariablePropagationPolicy.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FilteredVariablePropagationPolicy.java
new file mode 100644
index 0000000..822cdc3
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FilteredVariablePropagationPolicy.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.List;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.IOperatorSchema;
+
+public class FilteredVariablePropagationPolicy extends VariablePropagationPolicy {
+
+    List<LogicalVariable> toPropagate;
+
+    public FilteredVariablePropagationPolicy(List<LogicalVariable> varList) {
+        toPropagate = varList;
+    }
+
+    @Override
+    public void propagateVariables(IOperatorSchema target, IOperatorSchema... sources) {
+        for (LogicalVariable v : toPropagate) {
+            target.addVariable(v);
+        }
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FunctionalDependency.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FunctionalDependency.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FunctionalDependency.java
new file mode 100644
index 0000000..5bf4637
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/FunctionalDependency.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.List;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public final class FunctionalDependency {
+    private List<LogicalVariable> head;
+    private List<LogicalVariable> tail;
+
+    public FunctionalDependency(List<LogicalVariable> head, List<LogicalVariable> tail) {
+        this.head = head;
+        this.tail = tail;
+    }
+
+    public List<LogicalVariable> getHead() {
+        return head;
+    }
+
+    public List<LogicalVariable> getTail() {
+        return tail;
+    }
+
+    @Override
+    public String toString() {
+        return head + "->" + tail;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (!(obj instanceof FunctionalDependency)) {
+            return false;
+        } else {
+            FunctionalDependency fd = (FunctionalDependency) obj;
+            return fd.getHead().equals(this.head) && fd.getTail().equals(this.tail);
+        }
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
new file mode 100644
index 0000000..c32fd67
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
@@ -0,0 +1,50 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public interface ILocalStructuralProperty extends IStructuralProperty {
+    public enum PropertyType {
+        LOCAL_GROUPING_PROPERTY,
+        LOCAL_ORDER_PROPERTY
+    }
+
+    public void getVariables(Collection<LogicalVariable> variables);
+
+    public PropertyType getPropertyType();
+
+    /**
+     * Returns the retained property regarding to a collection of variables,
+     * e.g., some variables used in the property may not exist in the input
+     * collection and hence the data property changes.
+     * 
+     * @param vars
+     *            , an input collection of variables
+     * @return the retained data property.
+     */
+    public ILocalStructuralProperty retainVariables(Collection<LogicalVariable> vars);
+
+    /**
+     * Returns the additional data property within each group, which is dictated by the group keys.
+     * 
+     * @param vars
+     *            , group keys.
+     * @return the additional data property within each group.
+     */
+    public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys);
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILogicalPropertiesVector.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILogicalPropertiesVector.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILogicalPropertiesVector.java
new file mode 100644
index 0000000..175f041
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILogicalPropertiesVector.java
@@ -0,0 +1,21 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public interface ILogicalPropertiesVector {
+    public Integer getNumberOfTuples();
+
+    public Integer getMaxOutputFrames();
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/INodeDomain.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/INodeDomain.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/INodeDomain.java
new file mode 100644
index 0000000..17e97ec
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/INodeDomain.java
@@ -0,0 +1,22 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public interface INodeDomain {
+    public boolean sameAs(INodeDomain domain);
+
+    /** @return the number of nodes in that domain or null if unknown */
+    public Integer cardinality();
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
new file mode 100644
index 0000000..bb8cfe2
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public interface IPartitioningProperty extends IStructuralProperty {
+    public enum PartitioningType {
+        UNPARTITIONED, RANDOM, BROADCAST, UNORDERED_PARTITIONED, ORDERED_PARTITIONED
+    }
+
+    static final INodeDomain DOMAIN_FOR_UNPARTITIONED_DATA = new INodeDomain() {
+        @Override
+        public boolean sameAs(INodeDomain domain) {
+            return domain == this;
+        }
+
+        @Override
+        public Integer cardinality() {
+            return null;
+        }
+    };
+
+    public static final IPartitioningProperty UNPARTITIONED = new IPartitioningProperty() {
+
+        @Override
+        public PartitioningType getPartitioningType() {
+            return PartitioningType.UNPARTITIONED;
+        }
+
+        @Override
+        public void normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+            // do nothing
+        }
+
+        @Override
+        public void getColumns(Collection<LogicalVariable> columns) {
+        }
+
+        @Override
+        public INodeDomain getNodeDomain() {
+            return DOMAIN_FOR_UNPARTITIONED_DATA;
+        }
+
+        @Override
+        public String toString() {
+            return getPartitioningType().toString();
+        }
+
+        @Override
+        public void setNodeDomain(INodeDomain domain) {
+            throw new IllegalStateException();
+        }
+    };
+
+    public abstract PartitioningType getPartitioningType();
+
+    public abstract void normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+            List<FunctionalDependency> fds);
+
+    public abstract INodeDomain getNodeDomain();
+
+    public abstract void setNodeDomain(INodeDomain domain);
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningRequirementsCoordinator.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningRequirementsCoordinator.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningRequirementsCoordinator.java
new file mode 100644
index 0000000..cd9eb96
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningRequirementsCoordinator.java
@@ -0,0 +1,98 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Map;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.NotImplementedException;
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+/**
+ * Implements constraints in between requirements for the children of the same
+ * operator.
+ */
+
+public interface IPartitioningRequirementsCoordinator {
+
+    public static IPartitioningRequirementsCoordinator NO_COORDINATION = new IPartitioningRequirementsCoordinator() {
+
+        @Override
+        public Pair<Boolean, IPartitioningProperty> coordinateRequirements(IPartitioningProperty requirements,
+                IPartitioningProperty firstDeliveredPartitioning, ILogicalOperator op, IOptimizationContext context) {
+            return new Pair<Boolean, IPartitioningProperty>(true, requirements);
+        }
+    };
+
+    public static IPartitioningRequirementsCoordinator EQCLASS_PARTITIONING_COORDINATOR = new IPartitioningRequirementsCoordinator() {
+
+        @Override
+        public Pair<Boolean, IPartitioningProperty> coordinateRequirements(IPartitioningProperty rqdpp,
+                IPartitioningProperty firstDeliveredPartitioning, ILogicalOperator op, IOptimizationContext context)
+                throws AlgebricksException {
+            if (firstDeliveredPartitioning != null
+                    && firstDeliveredPartitioning.getPartitioningType() == rqdpp.getPartitioningType()) {
+                switch (rqdpp.getPartitioningType()) {
+                    case UNORDERED_PARTITIONED: {
+                        UnorderedPartitionedProperty upp1 = (UnorderedPartitionedProperty) firstDeliveredPartitioning;
+                        Set<LogicalVariable> set1 = upp1.getColumnSet();
+                        UnorderedPartitionedProperty uppreq = (UnorderedPartitionedProperty) rqdpp;
+                        Set<LogicalVariable> modifuppreq = new ListSet<LogicalVariable>();
+                        Map<LogicalVariable, EquivalenceClass> eqmap = context.getEquivalenceClassMap(op);
+                        Set<LogicalVariable> covered = new ListSet<LogicalVariable>();
+
+                        // coordinate from an existing partition property
+                        // (firstDeliveredPartitioning)
+                        for (LogicalVariable v : set1) {
+                            EquivalenceClass ecFirst = eqmap.get(v);
+                            for (LogicalVariable r : uppreq.getColumnSet()) {
+                                EquivalenceClass ec = eqmap.get(r);
+                                if (ecFirst == ec) {
+                                    covered.add(v);
+                                    modifuppreq.add(r);
+                                    break;
+                                }
+                            }
+                        }
+
+                        if (!covered.equals(set1)) {
+                            throw new AlgebricksException("Could not modify " + rqdpp
+                                    + " to agree with partitioning property " + firstDeliveredPartitioning
+                                    + " delivered by previous input operator.");
+                        }
+                        UnorderedPartitionedProperty upp2 = new UnorderedPartitionedProperty(modifuppreq,
+                                rqdpp.getNodeDomain());
+                        return new Pair<Boolean, IPartitioningProperty>(false, upp2);
+                    }
+                    case ORDERED_PARTITIONED: {
+                        throw new NotImplementedException();
+                    }
+                }
+            }
+            return new Pair<Boolean, IPartitioningProperty>(true, rqdpp);
+        }
+
+    };
+
+    public Pair<Boolean, IPartitioningProperty> coordinateRequirements(IPartitioningProperty requirements,
+            IPartitioningProperty firstDeliveredPartitioning, ILogicalOperator op, IOptimizationContext context)
+            throws AlgebricksException;
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPhysicalPropertiesVector.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPhysicalPropertiesVector.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPhysicalPropertiesVector.java
new file mode 100644
index 0000000..45bf1ec
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPhysicalPropertiesVector.java
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.List;
+import java.util.Map;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public interface IPhysicalPropertiesVector {
+
+    public IPartitioningProperty getPartitioningProperty();
+
+    public List<ILocalStructuralProperty> getLocalProperties();
+
+    /**
+     * 
+     * @param reqd
+     *            vector of required properties
+     * @param equivalenceClasses
+     * @param fds
+     * @return a vector of properties from pvector that are not delivered by the
+     *         current vector or null if none
+     */
+    public IPhysicalPropertiesVector getUnsatisfiedPropertiesFrom(IPhysicalPropertiesVector reqd,
+            boolean mayExpandProperties, Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+            List<FunctionalDependency> fds);
+
+    public IPhysicalPropertiesVector clone();
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPropertiesComputer.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPropertiesComputer.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPropertiesComputer.java
new file mode 100644
index 0000000..716b459
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPropertiesComputer.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+
+public interface IPropertiesComputer {
+
+    // can return null
+    public IPartitioningProperty computePartitioningProperty(ILogicalExpression expr);
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IStructuralProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IStructuralProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IStructuralProperty.java
new file mode 100644
index 0000000..bf8aaa5
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IStructuralProperty.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public interface IStructuralProperty {
+    public void getColumns(Collection<LogicalVariable> columns);
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
new file mode 100644
index 0000000..c267364
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public class LocalGroupingProperty extends AbstractGroupingProperty implements ILocalStructuralProperty {
+
+    // preferredOrderEnforcer, if not null, is guaranteed to enforce grouping on
+    // columnSet
+    private List<LogicalVariable> preferredOrderEnforcer;
+
+    public LocalGroupingProperty(Set<LogicalVariable> columnSet) {
+        super(columnSet);
+    }
+
+    public LocalGroupingProperty(Set<LogicalVariable> columnSet, List<LogicalVariable> preferredOrderEnforcer) {
+        this(columnSet);
+        this.preferredOrderEnforcer = preferredOrderEnforcer;
+    }
+
+    @Override
+    public PropertyType getPropertyType() {
+        return PropertyType.LOCAL_GROUPING_PROPERTY;
+    }
+
+    @Override
+    public void getColumns(Collection<LogicalVariable> columns) {
+        columns.addAll(columnSet);
+    }
+
+    @Override
+    public String toString() {
+        return columnSet.toString();
+    }
+
+    @Override
+    public void getVariables(Collection<LogicalVariable> variables) {
+        variables.addAll(columnSet);
+    }
+
+    public List<LogicalVariable> getPreferredOrderEnforcer() {
+        return preferredOrderEnforcer;
+    }
+
+    @Override
+    public ILocalStructuralProperty retainVariables(Collection<LogicalVariable> vars) {
+        Set<LogicalVariable> newVars = new ListSet<LogicalVariable>();
+        newVars.addAll(vars);
+        newVars.retainAll(columnSet);
+        if (columnSet.equals(newVars)) {
+            return new LocalGroupingProperty(columnSet, preferredOrderEnforcer);
+        }
+        // Column set for the retained grouping property
+        Set<LogicalVariable> newColumns = new ListSet<LogicalVariable>();
+        // Matches the prefix of the original column set.
+        for (LogicalVariable v : columnSet) {
+            if (newVars.contains(v)) {
+                newColumns.add(v);
+            } else {
+                break;
+            }
+        }
+        if (newColumns.size() > 0) {
+            return new LocalGroupingProperty(newColumns, preferredOrderEnforcer.subList(0, newColumns.size()));
+        } else {
+            return null;
+        }
+    }
+
+    @Override
+    public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys) {
+        Set<LogicalVariable> newColumns = new ListSet<LogicalVariable>();
+        for (LogicalVariable v : columnSet) {
+            if (!groupKeys.contains(v)) {
+                newColumns.add(v);
+            }
+        }
+        if (newColumns.size() > 0) {
+            return new LocalGroupingProperty(newColumns, preferredOrderEnforcer.subList(groupKeys.size(),
+                    newColumns.size()));
+        } else {
+            return null;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
new file mode 100644
index 0000000..6d568f4
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
@@ -0,0 +1,210 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder.OrderKind;
+
+public final class LocalOrderProperty implements ILocalStructuralProperty {
+
+    private List<OrderColumn> orderColumns;
+
+    public LocalOrderProperty(List<OrderColumn> orderColumn) {
+        this.orderColumns = orderColumn;
+    }
+
+    public List<OrderColumn> getOrderColumns() {
+        return orderColumns;
+    }
+
+    public void setOrderColumns(List<OrderColumn> orderColumn) {
+        this.orderColumns = orderColumn;
+    }
+
+    public List<LogicalVariable> getColumns() {
+        List<LogicalVariable> orderVars = new ArrayList<LogicalVariable>();
+        for (OrderColumn oc : orderColumns) {
+            orderVars.add(oc.getColumn());
+        }
+        return orderVars;
+    }
+
+    public List<OrderKind> getOrders() {
+        List<OrderKind> orderKinds = new ArrayList<OrderKind>();
+        for (OrderColumn oc : orderColumns) {
+            orderKinds.add(oc.getOrder());
+        }
+        return orderKinds;
+    }
+
+    @Override
+    public PropertyType getPropertyType() {
+        return PropertyType.LOCAL_ORDER_PROPERTY;
+    }
+
+    @Override
+    public void getColumns(Collection<LogicalVariable> columns) {
+        columns.addAll(getColumns());
+    }
+
+    @Override
+    public String toString() {
+        return orderColumns.toString();
+    }
+
+    @Override
+    public void getVariables(Collection<LogicalVariable> variables) {
+        variables.addAll(getColumns());
+    }
+
+    @Override
+    public boolean equals(Object object) {
+        LocalOrderProperty lop = (LocalOrderProperty) object;
+        return orderColumns.equals(lop.orderColumns);
+    }
+
+    /**
+     * Whether current property implies the required property
+     * 
+     * @param required
+     *            , a required property
+     * @return true if the current property satisfies the required property; otherwise false.
+     */
+    public final boolean implies(ILocalStructuralProperty required) {
+        if (required.getPropertyType() != PropertyType.LOCAL_ORDER_PROPERTY) {
+            return false;
+        }
+        LocalOrderProperty requiredOrderProperty = (LocalOrderProperty) required;
+        Iterator<OrderColumn> requiredColumnIterator = requiredOrderProperty.getOrderColumns().iterator();
+        Iterator<OrderColumn> currentColumnIterator = orderColumns.iterator();
+
+        // Returns true if requiredColumnIterator is a prefix of currentColumnIterator.
+        return isPrefixOf(requiredColumnIterator, currentColumnIterator);
+    }
+
+    private <T> boolean isPrefixOf(Iterator<T> requiredColumnIterator, Iterator<T> currentColumnIterator) {
+        while (requiredColumnIterator.hasNext()) {
+            T oc = requiredColumnIterator.next();
+            if (!currentColumnIterator.hasNext()) {
+                return false;
+            }
+            if (!oc.equals(currentColumnIterator.next())) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public final void normalizeOrderingColumns(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+            List<FunctionalDependency> fds) {
+        replaceOrderingColumnsByEqClasses(equivalenceClasses);
+        applyFDsToOrderingColumns(fds);
+    }
+
+    private void replaceOrderingColumnsByEqClasses(Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+        if (equivalenceClasses == null || equivalenceClasses.isEmpty()) {
+            return;
+        }
+        List<OrderColumn> norm = new ArrayList<OrderColumn>();
+        for (OrderColumn oc : orderColumns) {
+            LogicalVariable v = oc.getColumn();
+            EquivalenceClass ec = equivalenceClasses.get(v);
+            if (ec == null) {
+                norm.add(new OrderColumn(v, oc.getOrder()));
+            } else {
+                if (ec.representativeIsConst()) {
+                    // trivially satisfied, so the var. can be removed
+                } else {
+                    norm.add(new OrderColumn(ec.getVariableRepresentative(), oc.getOrder()));
+                }
+            }
+        }
+        orderColumns = norm;
+    }
+
+    private void applyFDsToOrderingColumns(List<FunctionalDependency> fds) {
+        if (fds == null || fds.isEmpty()) {
+            return;
+        }
+        Set<LogicalVariable> norm = new ListSet<LogicalVariable>();
+        List<LogicalVariable> columns = getColumns();
+        for (LogicalVariable v : columns) {
+            boolean isImpliedByAnFD = false;
+            for (FunctionalDependency fdep : fds) {
+                if (columns.containsAll(fdep.getHead()) && fdep.getTail().contains(v)) {
+                    isImpliedByAnFD = true;
+                    norm.addAll(fdep.getHead());
+                    break;
+                }
+
+            }
+            if (!isImpliedByAnFD) {
+                norm.add(v);
+            }
+        }
+        Set<OrderColumn> impliedColumns = new ListSet<OrderColumn>();
+        for (OrderColumn oc : orderColumns) {
+            if (!norm.contains(oc.getColumn())) {
+                impliedColumns.add(oc);
+            }
+        }
+        orderColumns.removeAll(impliedColumns);
+    }
+
+    @Override
+    public ILocalStructuralProperty retainVariables(Collection<LogicalVariable> vars) {
+        List<LogicalVariable> columns = getColumns();
+        List<LogicalVariable> newVars = new ArrayList<LogicalVariable>();
+        newVars.addAll(vars);
+        newVars.retainAll(columns);
+        List<OrderColumn> newColumns = new ArrayList<OrderColumn>();
+        for (OrderColumn oc : orderColumns) {
+            if (newVars.contains(oc.getColumn())) {
+                newColumns.add(oc);
+            } else {
+                break;
+            }
+        }
+        if (newColumns.size() > 0) {
+            return new LocalOrderProperty(newColumns);
+        } else {
+            return null;
+        }
+    }
+
+    @Override
+    public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys) {
+        List<OrderColumn> newColumns = new ArrayList<OrderColumn>();
+        for (OrderColumn oc : orderColumns) {
+            if (!groupKeys.contains(oc.getColumn())) {
+                newColumns.add(oc);
+            }
+        }
+        if (newColumns.size() > 0) {
+            return new LocalOrderProperty(newColumns);
+        } else {
+            return null;
+        }
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LogicalPropertiesVectorImpl.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LogicalPropertiesVectorImpl.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LogicalPropertiesVectorImpl.java
new file mode 100644
index 0000000..848c86e
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LogicalPropertiesVectorImpl.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public class LogicalPropertiesVectorImpl implements ILogicalPropertiesVector {
+
+    private Integer numTuples, maxOutputFrames;
+
+    @Override
+    public String toString() {
+        return "LogicalPropertiesVector [ num.tuples: " + numTuples + ", maxOutputFrames: " + maxOutputFrames + " ]";
+    }
+
+    @Override
+    public Integer getNumberOfTuples() {
+        return numTuples;
+    }
+
+    public void setNumberOfTuples(Integer numTuples) {
+        this.numTuples = numTuples;
+    }
+
+    @Override
+    public Integer getMaxOutputFrames() {
+        return maxOutputFrames;
+    }
+
+    public void setMaxOutputFrames(Integer maxOutputFrames) {
+        this.maxOutputFrames = maxOutputFrames;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderColumn.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderColumn.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderColumn.java
new file mode 100644
index 0000000..a0e76d1
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderColumn.java
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder.OrderKind;
+
+public final class OrderColumn {
+
+    private LogicalVariable column;
+    private OrderKind order;
+
+    public OrderColumn(LogicalVariable column, OrderKind order) {
+        this.column = column;
+        this.order = order;
+    }
+
+    public LogicalVariable getColumn() {
+        return column;
+    }
+
+    public OrderKind getOrder() {
+        return order;
+    }
+
+    public void setColumn(LogicalVariable column) {
+        this.column = column;
+    }
+
+    public void setOrder(OrderKind order) {
+        this.order = order;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (!(obj instanceof OrderColumn)) {
+            return false;
+        } else {
+            OrderColumn oc = (OrderColumn) obj;
+            return column.equals(oc.getColumn()) && order == oc.getOrder();
+        }
+    }
+
+    @Override
+    public String toString() {
+        return column.toString() + "(" + order + ")";
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderedPartitionedProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderedPartitionedProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderedPartitionedProperty.java
new file mode 100644
index 0000000..6f88933
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/OrderedPartitionedProperty.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public class OrderedPartitionedProperty implements IPartitioningProperty {
+
+    private ArrayList<OrderColumn> orderColumns;
+    private INodeDomain domain;
+
+    public OrderedPartitionedProperty(ArrayList<OrderColumn> orderColumns, INodeDomain domain) {
+        this.domain = domain;
+        this.orderColumns = orderColumns;
+    }
+
+    public ArrayList<OrderColumn> getOrderColumns() {
+        return orderColumns;
+    }
+
+    public ArrayList<LogicalVariable> getColumns() {
+        ArrayList<LogicalVariable> cols = new ArrayList<LogicalVariable>(orderColumns.size());
+        for (OrderColumn oc : orderColumns) {
+            cols.add(oc.getColumn());
+        }
+        return cols;
+    }
+
+    @Override
+    public PartitioningType getPartitioningType() {
+        return PartitioningType.ORDERED_PARTITIONED;
+    }
+
+    @Override
+    public String toString() {
+        return getPartitioningType().toString() + orderColumns;
+    }
+
+    @Override
+    public void normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+        orderColumns = PropertiesUtil.replaceOrderColumnsByEqClasses(orderColumns, equivalenceClasses);
+        orderColumns = PropertiesUtil.applyFDsToOrderColumns(orderColumns, fds);
+    }
+
+    @Override
+    public void getColumns(Collection<LogicalVariable> columns) {
+        for (OrderColumn oc : orderColumns) {
+            columns.add(oc.getColumn());
+        }
+    }
+
+    @Override
+    public INodeDomain getNodeDomain() {
+        return domain;
+    }
+
+    @Override
+    public void setNodeDomain(INodeDomain domain) {
+        this.domain = domain;
+    }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PhysicalRequirements.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PhysicalRequirements.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PhysicalRequirements.java
new file mode 100644
index 0000000..ce0907f
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PhysicalRequirements.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public class PhysicalRequirements {
+    private final IPhysicalPropertiesVector[] requiredProperties;
+    private final IPartitioningRequirementsCoordinator partitioningCoordinator;
+
+    public PhysicalRequirements(IPhysicalPropertiesVector[] requiredProperties,
+            IPartitioningRequirementsCoordinator partitioningCoordinator) {
+        this.requiredProperties = requiredProperties;
+        this.partitioningCoordinator = partitioningCoordinator;
+    }
+
+    public IPhysicalPropertiesVector[] getRequiredProperties() {
+        return requiredProperties;
+    }
+
+    public IPartitioningRequirementsCoordinator getPartitioningCoordinator() {
+        return partitioningCoordinator;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
new file mode 100644
index 0000000..b651e59
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
@@ -0,0 +1,320 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.algebricks.common.utils.ListSet;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.properties.ILocalStructuralProperty.PropertyType;
+
+public class PropertiesUtil {
+
+    public Set<LogicalVariable> closureUnderFDs(Collection<LogicalVariable> vars, List<FunctionalDependency> fdList) {
+        Set<LogicalVariable> k = new ListSet<LogicalVariable>(vars);
+        boolean change;
+        do {
+            change = false;
+            for (FunctionalDependency fd : fdList) {
+                List<LogicalVariable> h = fd.getHead();
+                if (k.containsAll(h)) {
+                    List<LogicalVariable> t = fd.getTail();
+                    for (LogicalVariable v : t) {
+                        if (!(k.contains(v))) {
+                            k.add(v);
+                            change = true;
+                        }
+                    }
+                }
+            }
+        } while (change);
+        return k;
+    }
+
+    public static boolean matchLocalProperties(List<ILocalStructuralProperty> reqd,
+            List<ILocalStructuralProperty> dlvd, Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+            List<FunctionalDependency> fds) {
+        if (reqd == null) {
+            return true;
+        }
+        if (dlvd == null) {
+            return false;
+        }
+        normalizeLocals(reqd, equivalenceClasses, fds);
+        normalizeLocals(dlvd, equivalenceClasses, fds);
+
+        ListIterator<ILocalStructuralProperty> dlvdIter = dlvd.listIterator();
+
+        Set<LogicalVariable> rqdCols = new ListSet<LogicalVariable>();
+        Set<LogicalVariable> dlvdCols = new ListSet<LogicalVariable>();
+        for (ILocalStructuralProperty r : reqd) {
+            if (r.getPropertyType() == PropertyType.LOCAL_GROUPING_PROPERTY) {
+                rqdCols.clear();
+                r.getVariables(rqdCols);
+            }
+            boolean implied = false;
+            while (!implied && dlvdIter.hasNext()) {
+                ILocalStructuralProperty d = dlvdIter.next();
+                switch (r.getPropertyType()) {
+                    case LOCAL_ORDER_PROPERTY: {
+                        if (d.getPropertyType() != PropertyType.LOCAL_ORDER_PROPERTY) {
+                            return false;
+                        }
+                        LocalOrderProperty lop = (LocalOrderProperty) d;
+                        if (lop.implies(r)) {
+                            implied = true;
+                        } else {
+                            return false;
+                        }
+                        break;
+                    }
+                    case LOCAL_GROUPING_PROPERTY: {
+                        dlvdCols.clear();
+                        d.getColumns(dlvdCols);
+                        if (d.getPropertyType() == PropertyType.LOCAL_ORDER_PROPERTY) {
+                            implied = isPrefixOf(rqdCols.iterator(), dlvdCols.iterator());
+                        } else {
+                            implied = rqdCols.equals(dlvdCols) || isPrefixOf(rqdCols.iterator(), dlvdCols.iterator());
+                        }
+                        break;
+                    }
+                    default: {
+                        throw new IllegalStateException();
+                    }
+                }
+            }
+            if (!implied) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public static boolean matchPartitioningProps(IPartitioningProperty reqd, IPartitioningProperty dlvd,
+            boolean mayExpandProperties) {
+        INodeDomain dom1 = reqd.getNodeDomain();
+        INodeDomain dom2 = dlvd.getNodeDomain();
+        if (dom1 != null && dom2 != null && !dom1.sameAs(dom2)) {
+            return false;
+        }
+
+        switch (reqd.getPartitioningType()) {
+            case RANDOM: {
+                // anything matches RANDOM
+                return true;
+            }
+            case UNORDERED_PARTITIONED: {
+                switch (dlvd.getPartitioningType()) {
+                    case UNORDERED_PARTITIONED: {
+                        UnorderedPartitionedProperty ur = (UnorderedPartitionedProperty) reqd;
+                        UnorderedPartitionedProperty ud = (UnorderedPartitionedProperty) dlvd;
+                        if (mayExpandProperties) {
+                            return isPrefixOf(ud.getColumnSet().iterator(), ur.getColumnSet().iterator());
+                        } else {
+                            return ur.getColumnSet().equals(ud.getColumnSet());
+                        }
+                    }
+                    case ORDERED_PARTITIONED: {
+                        UnorderedPartitionedProperty ur = (UnorderedPartitionedProperty) reqd;
+                        OrderedPartitionedProperty od = (OrderedPartitionedProperty) dlvd;
+                        if (mayExpandProperties) {
+                            List<LogicalVariable> dlvdSortColumns = orderColumnsToVariables(od.getOrderColumns());
+                            return isPrefixOf(dlvdSortColumns.iterator(), ur.getColumnSet().iterator());
+                        } else {
+                            return ur.getColumnSet().containsAll(od.getOrderColumns())
+                                    && od.getOrderColumns().containsAll(ur.getColumnSet());
+                        }
+                    }
+                    default: {
+                        return false;
+                    }
+                }
+            }
+            case ORDERED_PARTITIONED: {
+                switch (dlvd.getPartitioningType()) {
+                    case ORDERED_PARTITIONED: {
+                        OrderedPartitionedProperty or = (OrderedPartitionedProperty) reqd;
+                        OrderedPartitionedProperty od = (OrderedPartitionedProperty) dlvd;
+                        if (mayExpandProperties) {
+                            return isPrefixOf(od.getOrderColumns().iterator(), or.getOrderColumns().iterator());
+                        } else {
+                            return od.getOrderColumns().equals(or.getOrderColumns());
+                        }
+                    }
+                    default: {
+                        return false;
+                    }
+                }
+            }
+            default: {
+                return (dlvd.getPartitioningType() == reqd.getPartitioningType());
+            }
+        }
+    }
+
+    /**
+     * Converts a list of OrderColumns to a list of LogicalVariables.
+     * 
+     * @param orderColumns
+     *            , a list of OrderColumns
+     * @return the list of LogicalVariables
+     */
+    private static List<LogicalVariable> orderColumnsToVariables(List<OrderColumn> orderColumns) {
+        List<LogicalVariable> columns = new ArrayList<LogicalVariable>();
+        for (OrderColumn oc : orderColumns) {
+            columns.add(oc.getColumn());
+        }
+        return columns;
+    }
+
+    /**
+     * @param pref
+     * @param target
+     * @return true iff pref is a prefix of target
+     */
+    private static <T> boolean isPrefixOf(Iterator<T> pref, Iterator<T> target) {
+        while (pref.hasNext()) {
+            T v = pref.next();
+            if (!target.hasNext()) {
+                return false;
+            }
+            if (!v.equals(target.next())) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public static ArrayList<OrderColumn> applyFDsToOrderColumns(ArrayList<OrderColumn> orderColumns,
+            List<FunctionalDependency> fds) {
+        // the set of vars. is ordered
+        // so we try the variables in order from last to first
+        if (fds == null || fds.isEmpty()) {
+            return orderColumns;
+        }
+
+        int deleted = 0;
+        for (int i = orderColumns.size() - 1; i >= 0; i--) {
+            for (FunctionalDependency fdep : fds) {
+                if (impliedByPrefix(orderColumns, i, fdep)) {
+                    orderColumns.set(i, null);
+                    deleted++;
+                    break;
+                }
+            }
+        }
+        ArrayList<OrderColumn> norm = new ArrayList<OrderColumn>(orderColumns.size() - deleted);
+        for (OrderColumn oc : orderColumns) {
+            if (oc != null) {
+                norm.add(oc);
+            }
+        }
+        return norm;
+    }
+
+    public static ArrayList<OrderColumn> replaceOrderColumnsByEqClasses(ArrayList<OrderColumn> orderColumns,
+            Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+        if (equivalenceClasses == null || equivalenceClasses.isEmpty()) {
+            return orderColumns;
+        }
+        ArrayList<OrderColumn> norm = new ArrayList<OrderColumn>();
+        for (OrderColumn v : orderColumns) {
+            EquivalenceClass ec = equivalenceClasses.get(v.getColumn());
+            if (ec == null) {
+                norm.add(v);
+            } else {
+                if (ec.representativeIsConst()) {
+                    // trivially satisfied, so the var. can be removed
+                } else {
+                    norm.add(new OrderColumn(ec.getVariableRepresentative(), v.getOrder()));
+                }
+            }
+        }
+        return norm;
+    }
+
+    private static boolean impliedByPrefix(ArrayList<OrderColumn> vars, int i, FunctionalDependency fdep) {
+        if (!fdep.getTail().contains(vars.get(i).getColumn())) {
+            return false;
+        }
+        boolean fdSat = true;
+        for (LogicalVariable pv : fdep.getHead()) {
+            boolean isInPrefix = false;
+            for (int j = 0; j < i; j++) {
+                if (vars.get(j).getColumn().equals(pv)) {
+                    isInPrefix = true;
+                    break;
+                }
+            }
+            if (!isInPrefix) {
+                fdSat = false;
+                break;
+            }
+        }
+        return fdSat;
+    }
+
+    private static void normalizeLocals(List<ILocalStructuralProperty> props,
+            Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+        ListIterator<ILocalStructuralProperty> propIter = props.listIterator();
+        int pos = -1;
+        while (propIter.hasNext()) {
+            ILocalStructuralProperty p = propIter.next();
+            if (p.getPropertyType() == PropertyType.LOCAL_GROUPING_PROPERTY) {
+                ((LocalGroupingProperty) p).normalizeGroupingColumns(equivalenceClasses, fds);
+                pos++;
+            } else {
+                ((LocalOrderProperty) p).normalizeOrderingColumns(equivalenceClasses, fds);
+                pos++;
+            }
+        }
+
+        if (pos < 1) {
+            return;
+        }
+
+        while (propIter.hasPrevious()) {
+            ILocalStructuralProperty p = propIter.previous();
+            ListIterator<ILocalStructuralProperty> secondIter = props.listIterator(pos);
+            pos--;
+            Set<LogicalVariable> cols = new ListSet<LogicalVariable>();
+            while (secondIter.hasPrevious()) {
+                secondIter.previous().getColumns(cols);
+            }
+            secondIter = null;
+            for (FunctionalDependency fdep : fds) {
+                LinkedList<LogicalVariable> columnsOfP = new LinkedList<LogicalVariable>();
+                p.getColumns(columnsOfP);
+                if (impliedByPrefix(columnsOfP, cols, fdep)) {
+                    propIter.remove();
+                    break;
+                }
+            }
+        }
+    }
+
+    private static boolean impliedByPrefix(List<LogicalVariable> colsOfProp, Set<LogicalVariable> colsOfPrefix,
+            FunctionalDependency fdep) {
+        return fdep.getTail().containsAll(colsOfProp) && colsOfPrefix.containsAll(fdep.getHead());
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/RandomPartitioningProperty.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/RandomPartitioningProperty.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/RandomPartitioningProperty.java
new file mode 100644
index 0000000..06008a6
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/RandomPartitioningProperty.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.EquivalenceClass;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+
+public class RandomPartitioningProperty implements IPartitioningProperty {
+
+    private INodeDomain domain;
+
+    public RandomPartitioningProperty(INodeDomain domain) {
+        this.domain = domain;
+    }
+
+    @Override
+    public PartitioningType getPartitioningType() {
+        return PartitioningType.RANDOM;
+    }
+
+    @Override
+    public String toString() {
+        return getPartitioningType() + " domain:" + domain;
+    }
+
+    @Override
+    public void normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+        // do nothing
+    }
+
+    @Override
+    public void getColumns(Collection<LogicalVariable> columns) {
+    }
+
+    @Override
+    public INodeDomain getNodeDomain() {
+        return domain;
+    }
+
+    @Override
+    public void setNodeDomain(INodeDomain domain) {
+        this.domain = domain;
+    }
+
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb-hyracks/blob/9939b48e/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ResultSetDomain.java
----------------------------------------------------------------------
diff --git a/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ResultSetDomain.java b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ResultSetDomain.java
new file mode 100644
index 0000000..688523b
--- /dev/null
+++ b/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ResultSetDomain.java
@@ -0,0 +1,27 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.hyracks.algebricks.core.algebra.properties;
+
+public class ResultSetDomain implements INodeDomain {
+    @Override
+    public boolean sameAs(INodeDomain domain) {
+        return true;
+    }
+
+    @Override
+    public Integer cardinality() {
+        return 0;
+    }
+}



Mime
View raw message