You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by im...@apache.org on 2015/08/25 18:41:36 UTC
[23/51] [partial] incubator-asterixdb-hyracks git commit: Change
folder structure for Java repackage
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;
+ }
+}