ASTERIXDB-1531: fix ORDER BY with primary keys as non-prefix sort keys.
- clean up the local property inference implemenation;
- avoid side-effects for data properties during property matching.
Change-Id: Iee7fcdd6eb1279e8ee14ba75ee31ac118b00c806
Reviewed-on: https://asterix-gerrit.ics.uci.edu/1022
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Integration-Tests: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Yingyi Bu <buyingyi@gmail.com>
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.aql b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.aql
new file mode 100644
index 0000000..9e27dcc
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.aql
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+drop dataverse TinySocial if exists;
+create dataverse TinySocial;
+
+use dataverse TinySocial;
+
+create type TweetMessageType as {
+ tweetid : string
+}
+
+create dataset TweetMessages(TweetMessageType) primary key tweetid;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.aql b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.aql
new file mode 100644
index 0000000..fe79fd7
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.aql
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+use dataverse TinySocial;
+
+load dataset TweetMessages using localfs (("path"="asterix_nc1://data/tinysocial/twm.adm"),("format"="adm"));
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.aql b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.aql
new file mode 100644
index 0000000..4975a4e
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.aql
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+use dataverse TinySocial;
+
+
+from $tm in dataset TweetMessages
+order by $tm.user.screen-name, $tm.tweetid
+return $tm;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.sqlpp
new file mode 100644
index 0000000..8aed101
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.sqlpp
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+drop database TinySocial if exists;
+create database TinySocial;
+
+use TinySocial;
+
+create type TweetMessageType as {
+ tweetid : string
+}
+
+create table TweetMessages(TweetMessageType) primary key tweetid;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.sqlpp
new file mode 100644
index 0000000..d00863f
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+use TinySocial;
+
+load table TweetMessages using localfs (("path"="asterix_nc1://data/tinysocial/twm.adm"),("format"="adm"));
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.sqlpp
new file mode 100644
index 0000000..ec62431
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.sqlpp
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you 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 at
+ *
+ * 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.
+ */
+
+USE TinySocial;
+
+
+FROM TweetMessages tm
+SELECT VALUE tm
+ORDER BY tm.user.`screen-name`, tm.tweetid;
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.adm
new file mode 100644
index 0000000..9dbec6e
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.adm
@@ -0,0 +1,12 @@
+{ "tweetid": "7", "user": { "screen-name": "ChangEwing_573", "lang": "en", "friends_count": 182, "statuses_count": 394, "name": "Chang Ewing", "followers_count": 32136 }, "sender-location": point("36.21,72.6"), "send-time": datetime("2011-08-25T10:10:00.000Z"), "referred-topics": {{ "samsung", "platform" }}, "message-text": " like samsung the platform is good" }
+{ "tweetid": "10", "user": { "screen-name": "ColineGeyer@63", "lang": "en", "friends_count": 121, "statuses_count": 362, "name": "Coline Geyer", "followers_count": 17159 }, "sender-location": point("29.15,76.53"), "send-time": datetime("2008-01-26T10:10:00.000Z"), "referred-topics": {{ "verizon", "voice-clarity" }}, "message-text": " hate verizon its voice-clarity is OMG:(" }
+{ "tweetid": "2", "user": { "screen-name": "ColineGeyer@63", "lang": "en", "friends_count": 121, "statuses_count": 362, "name": "Coline Geyer", "followers_count": 17159 }, "sender-location": point("32.84,67.14"), "send-time": datetime("2010-05-13T10:10:00.000Z"), "referred-topics": {{ "verizon", "shortcut-menu" }}, "message-text": " like verizon its shortcut-menu is awesome:)" }
+{ "tweetid": "6", "user": { "screen-name": "ColineGeyer@63", "lang": "en", "friends_count": 121, "statuses_count": 362, "name": "Coline Geyer", "followers_count": 17159 }, "sender-location": point("47.51,83.99"), "send-time": datetime("2010-05-07T10:10:00.000Z"), "referred-topics": {{ "iphone", "voice-clarity" }}, "message-text": " like iphone the voice-clarity is good:)" }
+{ "tweetid": "1", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("47.44,80.65"), "send-time": datetime("2008-04-26T10:10:00.000Z"), "referred-topics": {{ "t-mobile", "customization" }}, "message-text": " love t-mobile its customization is good:)" }
+{ "tweetid": "3", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("29.72,75.8"), "send-time": datetime("2006-11-04T10:10:00.000Z"), "referred-topics": {{ "motorola", "speed" }}, "message-text": " like motorola the speed is good:)" }
+{ "tweetid": "4", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("39.28,70.48"), "send-time": datetime("2011-12-26T10:10:00.000Z"), "referred-topics": {{ "sprint", "voice-command" }}, "message-text": " like sprint the voice-command is mind-blowing:)" }
+{ "tweetid": "5", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("40.09,92.69"), "send-time": datetime("2006-08-04T10:10:00.000Z"), "referred-topics": {{ "motorola", "speed" }}, "message-text": " can't stand motorola its speed is terrible:(" }
+{ "tweetid": "8", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("46.05,93.34"), "send-time": datetime("2005-10-14T10:10:00.000Z"), "referred-topics": {{ "t-mobile", "shortcut-menu" }}, "message-text": " like t-mobile the shortcut-menu is awesome:)" }
+{ "tweetid": "9", "user": { "screen-name": "NathanGiesen@211", "lang": "en", "friends_count": 39339, "statuses_count": 473, "name": "Nathan Giesen", "followers_count": 49416 }, "sender-location": point("36.86,74.62"), "send-time": datetime("2012-07-21T10:10:00.000Z"), "referred-topics": {{ "verizon", "voicemail-service" }}, "message-text": " love verizon its voicemail-service is awesome" }
+{ "tweetid": "11", "user": { "screen-name": "NilaMilliron_tw", "lang": "en", "friends_count": 445, "statuses_count": 164, "name": "Nila Milliron", "followers_count": 22649 }, "sender-location": point("37.59,68.42"), "send-time": datetime("2008-03-09T10:10:00.000Z"), "referred-topics": {{ "iphone", "platform" }}, "message-text": " can't stand iphone its platform is terrible" }
+{ "tweetid": "12", "user": { "screen-name": "OliJackson_512", "lang": "en", "friends_count": 445, "statuses_count": 164, "name": "Oli Jackson", "followers_count": 22649 }, "sender-location": point("24.82,94.63"), "send-time": datetime("2010-02-13T10:10:00.000Z"), "referred-topics": {{ "samsung", "voice-command" }}, "message-text": " like samsung the voice-command is amazing:)" }
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/types/opentype_orderby_01/opentype_orderby_01.1.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/types/opentype_orderby_01/opentype_orderby_01.1.adm
index 3f091ba..0c76235 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/results/types/opentype_orderby_01/opentype_orderby_01.1.adm
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/types/opentype_orderby_01/opentype_orderby_01.1.adm
@@ -1,55 +1,55 @@
{ "emp.id": 1 }
+{ "emp.id": 6 }
+{ "emp.id": 11 }
+{ "emp.id": 16 }
+{ "emp.id": 21 }
+{ "emp.id": 26 }
+{ "emp.id": 31 }
+{ "emp.id": 36 }
+{ "emp.id": 41 }
+{ "emp.id": 46 }
{ "emp.id": 2, "emp.supvrid": 1 }
{ "emp.id": 3, "emp.supvrid": 1 }
-{ "emp.id": 4, "emp.supvrid": "1" }
{ "emp.id": 5, "emp.supvrid": 1.0 }
-{ "emp.id": 6 }
{ "emp.id": 7, "emp.supvrid": 2 }
{ "emp.id": 8, "emp.supvrid": 2 }
-{ "emp.id": 9, "emp.supvrid": "2" }
{ "emp.id": 10, "emp.supvrid": 2.0 }
-{ "emp.id": 11 }
{ "emp.id": 12, "emp.supvrid": 3 }
{ "emp.id": 13, "emp.supvrid": 3 }
-{ "emp.id": 14, "emp.supvrid": "3" }
{ "emp.id": 15, "emp.supvrid": 3.0 }
-{ "emp.id": 16 }
{ "emp.id": 17, "emp.supvrid": 4 }
{ "emp.id": 18, "emp.supvrid": 4 }
-{ "emp.id": 19, "emp.supvrid": "4" }
{ "emp.id": 20, "emp.supvrid": 4.0 }
-{ "emp.id": 21 }
{ "emp.id": 22, "emp.supvrid": 5 }
{ "emp.id": 23, "emp.supvrid": 5 }
-{ "emp.id": 24, "emp.supvrid": "5" }
{ "emp.id": 25, "emp.supvrid": 5.0 }
-{ "emp.id": 26 }
{ "emp.id": 27, "emp.supvrid": 6 }
{ "emp.id": 28, "emp.supvrid": 6 }
-{ "emp.id": 29, "emp.supvrid": "6" }
{ "emp.id": 30, "emp.supvrid": 6.0 }
-{ "emp.id": 31 }
{ "emp.id": 32, "emp.supvrid": 7 }
{ "emp.id": 33, "emp.supvrid": 7 }
-{ "emp.id": 34, "emp.supvrid": "7" }
{ "emp.id": 35, "emp.supvrid": 7.0 }
-{ "emp.id": 36 }
{ "emp.id": 37, "emp.supvrid": 8 }
{ "emp.id": 38, "emp.supvrid": 8 }
-{ "emp.id": 39, "emp.supvrid": "8" }
{ "emp.id": 40, "emp.supvrid": 8.0 }
-{ "emp.id": 41 }
{ "emp.id": 42, "emp.supvrid": 9 }
{ "emp.id": 43, "emp.supvrid": 9 }
-{ "emp.id": 44, "emp.supvrid": "9" }
{ "emp.id": 45, "emp.supvrid": 9.0 }
-{ "emp.id": 46 }
{ "emp.id": 47, "emp.supvrid": 10 }
{ "emp.id": 48, "emp.supvrid": 10 }
-{ "emp.id": 49, "emp.supvrid": "10" }
{ "emp.id": 50, "emp.supvrid": 10.0 }
-{ "emp.id": 51, "emp.supvrid": point("80.1,-1000000.0") }
-{ "emp.id": 52, "emp.supvrid": point("5.1E-10,-1000000.0") }
-{ "emp.id": 53, "emp.supvrid": circle("10.1234,1.11 0.102") }
+{ "emp.id": 4, "emp.supvrid": "1" }
+{ "emp.id": 49, "emp.supvrid": "10" }
+{ "emp.id": 9, "emp.supvrid": "2" }
+{ "emp.id": 14, "emp.supvrid": "3" }
+{ "emp.id": 19, "emp.supvrid": "4" }
+{ "emp.id": 24, "emp.supvrid": "5" }
+{ "emp.id": 29, "emp.supvrid": "6" }
+{ "emp.id": 34, "emp.supvrid": "7" }
+{ "emp.id": 39, "emp.supvrid": "8" }
+{ "emp.id": 44, "emp.supvrid": "9" }
{ "emp.id": 54, "emp.supvrid": time("12:54:54.039Z") }
{ "emp.id": 55, "emp.supvrid": duration("P101YT12M") }
+{ "emp.id": 52, "emp.supvrid": point("5.1E-10,-1000000.0") }
+{ "emp.id": 51, "emp.supvrid": point("80.1,-1000000.0") }
+{ "emp.id": 53, "emp.supvrid": circle("10.1234,1.11 0.102") }
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite.xml b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite.xml
index 619b378..41514f3 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite.xml
@@ -3239,6 +3239,11 @@
<output-dir compare="Text">query-ASTERIXDB-819-2</output-dir>
</compilation-unit>
</test-case>
+ <test-case FilePath="misc">
+ <compilation-unit name="query-ASTERIXDB-1531">
+ <output-dir compare="Text">query-ASTERIXDB-1531</output-dir>
+ </compilation-unit>
+ </test-case>
</test-group>
<test-group name="open-index-enforced">
<test-group name="open-index-enforced/error-checking">
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
index 1465ca7..83c2ef6 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
@@ -2973,6 +2973,11 @@
<output-dir compare="Text">prefix-search</output-dir>
</compilation-unit>
</test-case>
+ <test-case FilePath="misc">
+ <compilation-unit name="query-ASTERIXDB-1531">
+ <output-dir compare="Text">query-ASTERIXDB-1531</output-dir>
+ </compilation-unit>
+ </test-case>
</test-group>
<test-group name="open-index-enforced">
<test-group FilePath="open-index-enforced/error-checking">
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/FDsAndEquivClassesVisitor.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/FDsAndEquivClassesVisitor.java
index 85c55ec..5e2a041 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/FDsAndEquivClassesVisitor.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/FDsAndEquivClassesVisitor.java
@@ -31,6 +31,7 @@
import org.apache.commons.lang3.mutable.Mutable;
import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
import org.apache.hyracks.algebricks.common.exceptions.NotImplementedException;
+import org.apache.hyracks.algebricks.common.utils.ListSet;
import org.apache.hyracks.algebricks.common.utils.Pair;
import org.apache.hyracks.algebricks.core.algebra.base.EquivalenceClass;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
@@ -81,6 +82,7 @@
import org.apache.hyracks.algebricks.core.algebra.operators.logical.WriteOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.WriteResultOperator;
import org.apache.hyracks.algebricks.core.algebra.properties.FunctionalDependency;
+import org.apache.hyracks.algebricks.core.algebra.properties.ILocalStructuralProperty;
import org.apache.hyracks.algebricks.core.algebra.properties.LocalGroupingProperty;
import org.apache.hyracks.algebricks.core.algebra.visitors.ILogicalOperatorVisitor;
import org.apache.hyracks.algebricks.core.config.AlgebricksConfig;
@@ -177,8 +179,9 @@
Map<LogicalVariable, EquivalenceClass> equivalenceClasses = getOrComputeEqClasses(op0, ctx);
ctx.putEquivalenceClassMap(op, equivalenceClasses);
- lgp.normalizeGroupingColumns(equivalenceClasses, functionalDependencies);
- Set<LogicalVariable> normSet = lgp.getColumnSet();
+ ILocalStructuralProperty normalizedLgp = lgp.normalize(equivalenceClasses, functionalDependencies);
+ Set<LogicalVariable> normSet = new ListSet<>();
+ normalizedLgp.getColumns(normSet);
List<Mutable<ILogicalExpression>> newDistinctByList = new ArrayList<Mutable<ILogicalExpression>>();
for (Mutable<ILogicalExpression> p2Ref : expressions) {
ILogicalExpression p2 = p2Ref.getValue();
@@ -285,9 +288,10 @@
}
}
LocalGroupingProperty lgp = new LocalGroupingProperty(gbySet);
- lgp.normalizeGroupingColumns(inheritedEcs, inheritedFDs);
- Set<LogicalVariable> normSet = lgp.getColumnSet();
- List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> newGbyList = new ArrayList<Pair<LogicalVariable, Mutable<ILogicalExpression>>>();
+ ILocalStructuralProperty normalizedLgp = lgp.normalize(inheritedEcs, inheritedFDs);
+ Set<LogicalVariable> normSet = new ListSet<>();
+ normalizedLgp.getColumns(normSet);
+ List<Pair<LogicalVariable, Mutable<ILogicalExpression>>> newGbyList = new ArrayList<>();
boolean changed = false;
for (Pair<LogicalVariable, Mutable<ILogicalExpression>> p : gByList) {
ILogicalExpression expr = p.second.getValue();
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/AbstractPreclusteredGroupByPOperator.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/AbstractPreclusteredGroupByPOperator.java
index 2d00e4c..c0bdcb4 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/AbstractPreclusteredGroupByPOperator.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/AbstractPreclusteredGroupByPOperator.java
@@ -21,7 +21,6 @@
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
-import java.util.LinkedList;
import java.util.List;
import java.util.Set;
@@ -82,55 +81,20 @@
// are func. dep. on the group-by variables.
@Override
public void computeDeliveredProperties(ILogicalOperator op, IOptimizationContext context) {
- List<ILocalStructuralProperty> propsLocal = new LinkedList<ILocalStructuralProperty>();
+ List<ILocalStructuralProperty> propsLocal = new ArrayList<>();
GroupByOperator gby = (GroupByOperator) op;
ILogicalOperator op2 = gby.getInputs().get(0).getValue();
IPhysicalPropertiesVector childProp = op2.getDeliveredPhysicalProperties();
IPartitioningProperty pp = childProp.getPartitioningProperty();
List<ILocalStructuralProperty> childLocals = childProp.getLocalProperties();
- if (childLocals != null) {
- for (ILocalStructuralProperty lsp : childLocals) {
- boolean failed = false;
- switch (lsp.getPropertyType()) {
- case LOCAL_GROUPING_PROPERTY: {
- LocalGroupingProperty lgp = (LocalGroupingProperty) lsp;
- Set<LogicalVariable> colSet = new ListSet<LogicalVariable>();
- for (LogicalVariable v : lgp.getColumnSet()) {
- LogicalVariable v2 = getLhsGbyVar(gby, v);
- if (v2 != null) {
- colSet.add(v2);
- } else {
- failed = true;
- }
- }
- if (!failed) {
- propsLocal.add(new LocalGroupingProperty(colSet));
- }
- break;
- }
- case LOCAL_ORDER_PROPERTY: {
- LocalOrderProperty lop = (LocalOrderProperty) lsp;
- List<OrderColumn> orderColumns = new ArrayList<OrderColumn>();
- for (OrderColumn oc : lop.getOrderColumns()) {
- LogicalVariable v2 = getLhsGbyVar(gby, oc.getColumn());
- if (v2 != null) {
- orderColumns.add(new OrderColumn(v2, oc.getOrder()));
- } else {
- failed = true;
- }
- }
- if (!failed) {
- propsLocal.add(new LocalOrderProperty(orderColumns));
- }
- break;
- }
- default: {
- throw new IllegalStateException();
- }
- }
- if (failed) {
- break;
- }
+ if (childLocals == null) {
+ deliveredProperties = new StructuralPropertiesVector(pp, propsLocal);
+ return;
+ }
+ for (ILocalStructuralProperty lsp : childLocals) {
+ ILocalStructuralProperty propagatedLsp = getPropagatedProperty(lsp, gby);
+ if (propagatedLsp != null) {
+ propsLocal.add(propagatedLsp);
}
}
deliveredProperties = new StructuralPropertiesVector(pp, propsLocal);
@@ -140,10 +104,8 @@
public PhysicalRequirements getRequiredPropertiesForChildren(ILogicalOperator op,
IPhysicalPropertiesVector reqdByParent, IOptimizationContext context) {
StructuralPropertiesVector[] pv = new StructuralPropertiesVector[1];
- List<ILocalStructuralProperty> localProps = null;
-
- localProps = new ArrayList<ILocalStructuralProperty>(1);
- Set<LogicalVariable> gbvars = new ListSet<LogicalVariable>(columnList);
+ List<ILocalStructuralProperty> localProps = new ArrayList<>();
+ Set<LogicalVariable> gbvars = new ListSet<>(columnList);
LocalGroupingProperty groupProp = new LocalGroupingProperty(gbvars, new ArrayList<LogicalVariable>(columnList));
GroupByOperator gby = (GroupByOperator) op;
@@ -157,8 +119,8 @@
AbstractLogicalOperator op2 = (AbstractLogicalOperator) op1.getInputs().get(0).getValue();
IPhysicalOperator pop2 = op2.getPhysicalOperator();
if (pop2 instanceof AbstractPreclusteredGroupByPOperator) {
- List<LogicalVariable> gbyColumns = ((AbstractPreclusteredGroupByPOperator) pop2)
- .getGbyColumns();
+ List<LogicalVariable> gbyColumns =
+ ((AbstractPreclusteredGroupByPOperator) pop2).getGbyColumns();
List<LogicalVariable> sndOrder = new ArrayList<>();
sndOrder.addAll(gbyColumns);
Set<LogicalVariable> freeVars = new HashSet<>();
@@ -188,14 +150,14 @@
List<ILocalStructuralProperty> lpPar = reqdByParent.getLocalProperties();
if (lpPar != null) {
boolean allOk = true;
- List<ILocalStructuralProperty> props = new ArrayList<ILocalStructuralProperty>(lpPar.size());
+ List<ILocalStructuralProperty> props = new ArrayList<>(lpPar.size());
for (ILocalStructuralProperty prop : lpPar) {
if (prop.getPropertyType() != PropertyType.LOCAL_ORDER_PROPERTY) {
allOk = false;
break;
}
LocalOrderProperty lop = (LocalOrderProperty) prop;
- List<OrderColumn> orderColumns = new ArrayList<OrderColumn>();
+ List<OrderColumn> orderColumns = new ArrayList<>();
List<OrderColumn> ords = lop.getOrderColumns();
for (OrderColumn ord : ords) {
Pair<LogicalVariable, Mutable<ILogicalExpression>> p = getGbyPairByRhsVar(gby, ord.getColumn());
@@ -216,10 +178,10 @@
}
props.add(new LocalOrderProperty(orderColumns));
}
- List<FunctionalDependency> fdList = new ArrayList<FunctionalDependency>();
+ List<FunctionalDependency> fdList = new ArrayList<>();
for (Pair<LogicalVariable, Mutable<ILogicalExpression>> decorPair : gby.getDecorList()) {
List<LogicalVariable> hd = gby.getGbyVarList();
- List<LogicalVariable> tl = new ArrayList<LogicalVariable>(1);
+ List<LogicalVariable> tl = new ArrayList<>();
tl.add(((VariableReferenceExpression) decorPair.second.getValue()).getVariableReference());
fdList.add(new FunctionalDependency(hd, tl));
}
@@ -268,7 +230,7 @@
"Right hand side of group by assignment should have been normalized to a variable reference.");
}
LogicalVariable v = ((VariableReferenceExpression) e).getVariableReference();
- if (v == var) {
+ if (v.equals(var)) {
return ve.first;
}
}
@@ -279,4 +241,28 @@
public boolean expensiveThanMaterialization() {
return true;
}
+
+ // Returns the local structure property that is propagated from an input local structure property
+ // through a pre-clustered GROUP BY physical operator.
+ private ILocalStructuralProperty getPropagatedProperty(ILocalStructuralProperty lsp, GroupByOperator gby) {
+ PropertyType propertyType = lsp.getPropertyType();
+ if (propertyType == PropertyType.LOCAL_GROUPING_PROPERTY) {
+ // A new grouping property is generated.
+ return new LocalGroupingProperty(new ListSet<>(gby.getGbyVarList()));
+ } else {
+ LocalOrderProperty lop = (LocalOrderProperty) lsp;
+ List<OrderColumn> orderColumns = new ArrayList<>();
+ for (OrderColumn oc : lop.getOrderColumns()) {
+ LogicalVariable v2 = getLhsGbyVar(gby, oc.getColumn());
+ if (v2 != null) {
+ orderColumns.add(new OrderColumn(v2, oc.getOrder()));
+ } else {
+ break;
+ }
+ }
+ // Only the prefix (regarding to the pre-clustered GROUP BY keys) of the ordering property can be
+ // maintained.
+ return orderColumns.isEmpty() ? null : new LocalOrderProperty(orderColumns);
+ }
+ }
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/NestedTupleSourcePOperator.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/NestedTupleSourcePOperator.java
index e8cc05f..179bb73 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/NestedTupleSourcePOperator.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/NestedTupleSourcePOperator.java
@@ -22,7 +22,6 @@
import java.util.List;
import org.apache.commons.lang3.mutable.Mutable;
-
import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
import org.apache.hyracks.algebricks.core.algebra.base.IHyracksJobBuilder;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
@@ -63,28 +62,28 @@
AbstractLogicalOperator op2 = (AbstractLogicalOperator) dataSource.getValue().getInputs().get(0).getValue();
IPhysicalPropertiesVector inheritedProps = op2.getDeliveredPhysicalProperties();
AbstractLogicalOperator parent = (AbstractLogicalOperator) dataSource.getValue();
- if (parent.getOperatorTag() == LogicalOperatorTag.GROUP) {
- // The following part computes the data property regarding to each particular group.
- // TODO(buyingyi): we need to add the original data property as well. But currently
- // there are places assuming there is only one LocalOrderProperty and one
- // LocalGroupingProperty delivered by an operator.
- GroupByOperator gby = (GroupByOperator) parent;
- List<ILocalStructuralProperty> originalLocalProperties = inheritedProps.getLocalProperties();
- List<ILocalStructuralProperty> newLocalProperties = null;
- if (originalLocalProperties != null) {
- newLocalProperties = new ArrayList<ILocalStructuralProperty>();
- for (ILocalStructuralProperty lsp : inheritedProps.getLocalProperties()) {
- ILocalStructuralProperty newLsp = lsp.regardToGroup(gby.getGbyVarList());
- if (newLsp != null) {
- newLocalProperties.add(newLsp);
- }
+ if (parent.getOperatorTag() != LogicalOperatorTag.GROUP) {
+ deliveredProperties = inheritedProps.clone();
+ return;
+ }
+ GroupByOperator gby = (GroupByOperator) parent;
+ List<ILocalStructuralProperty> originalLocalProperties = inheritedProps.getLocalProperties();
+ List<ILocalStructuralProperty> newLocalProperties = null;
+ if (originalLocalProperties != null) {
+ newLocalProperties = new ArrayList<>();
+ for (ILocalStructuralProperty lsp : originalLocalProperties) {
+ ILocalStructuralProperty groupLocalLsp = lsp.regardToGroup(gby.getGbyVarList());
+ if (groupLocalLsp != null) {
+ // Adds the property that is satisfied in the context of a particular group.
+ newLocalProperties.add(groupLocalLsp);
}
}
- deliveredProperties = new StructuralPropertiesVector(inheritedProps.getPartitioningProperty(),
- newLocalProperties);
- } else {
- deliveredProperties = inheritedProps.clone();
+ // Adds the original local properties as they are still maintained.
+ // The optimizer should be able to process multiple delivered local order/grouping properties.
+ newLocalProperties.addAll(originalLocalProperties);
}
+ deliveredProperties =
+ new StructuralPropertiesVector(inheritedProps.getPartitioningProperty(), newLocalProperties);
}
@Override
@@ -99,8 +98,8 @@
throws AlgebricksException {
propagatedSchema.addAllVariables(outerPlanSchema);
NestedTupleSourceRuntimeFactory runtime = new NestedTupleSourceRuntimeFactory();
- RecordDescriptor recDesc = JobGenHelper.mkRecordDescriptor(context.getTypeEnvironment(op), propagatedSchema,
- context);
+ RecordDescriptor recDesc =
+ JobGenHelper.mkRecordDescriptor(context.getTypeEnvironment(op), propagatedSchema, context);
builder.contributeMicroOperator(op, runtime, recDesc);
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
index d12f0af..0d8d911 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java
@@ -37,39 +37,48 @@
return columnSet;
}
- public final void normalizeGroupingColumns(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
- List<FunctionalDependency> fds) {
- replaceGroupingColumnsByEqClasses(equivalenceClasses);
- applyFDsToGroupingColumns(fds);
+ // Returns normalized and concise columns from an input column set, by considering
+ // equivalence classes and functional dependencies.
+ protected Set<LogicalVariable> normalizeAndReduceGroupingColumns(Set<LogicalVariable> columns,
+ Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
+ Set<LogicalVariable> normalizedColumnSet =
+ getNormalizedColumnsAccordingToEqClasses(columns, equivalenceClasses);
+ reduceGroupingColumns(normalizedColumnSet, fds);
+ return normalizedColumnSet;
}
- private void replaceGroupingColumnsByEqClasses(Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+ // Gets normalized columns, where each column variable is a representative variable of its equivalence class,
+ // therefore, the matching of properties will can consider equivalence classes.
+ private Set<LogicalVariable> getNormalizedColumnsAccordingToEqClasses(Set<LogicalVariable> columns,
+ Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+ Set<LogicalVariable> normalizedColumns = new ListSet<>();
if (equivalenceClasses == null || equivalenceClasses.isEmpty()) {
- return;
+ normalizedColumns.addAll(columns);
+ return normalizedColumns;
}
- Set<LogicalVariable> norm = new ListSet<LogicalVariable>();
- for (LogicalVariable v : columnSet) {
+ for (LogicalVariable v : columns) {
EquivalenceClass ec = equivalenceClasses.get(v);
if (ec == null) {
- norm.add(v);
+ normalizedColumns.add(v);
} else {
if (ec.representativeIsConst()) {
// trivially satisfied, so the var. can be removed
} else {
- norm.add(ec.getVariableRepresentative());
+ normalizedColumns.add(ec.getVariableRepresentative());
}
}
}
- columnSet = norm;
+ return normalizedColumns;
}
- private void applyFDsToGroupingColumns(List<FunctionalDependency> fds) {
+ // Using functional dependencies to eliminate unnecessary columns.
+ private void reduceGroupingColumns(Set<LogicalVariable> columnSet, 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>();
+ Set<LogicalVariable> norm = new ListSet<>();
for (LogicalVariable v : columnSet) {
boolean isImpliedByAnFD = false;
for (FunctionalDependency fdep : fds) {
@@ -84,7 +93,7 @@
norm.add(v);
}
}
- columnSet = norm;
+ columnSet.retainAll(norm);
}
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
index af29994..1542ccb 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java
@@ -19,7 +19,10 @@
package org.apache.hyracks.algebricks.core.algebra.properties;
import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import org.apache.hyracks.algebricks.core.algebra.base.EquivalenceClass;
import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
public interface ILocalStructuralProperty extends IStructuralProperty {
@@ -28,8 +31,19 @@
LOCAL_ORDER_PROPERTY
}
+ /**
+ * Gets the variables that are used in the local property
+ *
+ * @param variables,
+ * variables that are used in the local property will be added into the argument collection.
+ */
public void getVariables(Collection<LogicalVariable> variables);
+ /**
+ * Get the type of the local property.
+ *
+ * @return either LOCAL_GROUPING_PROPERTY or LOCAL_ORDER_PROPERTY.
+ */
public PropertyType getPropertyType();
/**
@@ -51,4 +65,16 @@
* @return the additional data property within each group.
*/
public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys);
+
+ /**
+ * Returns a new, normalized local structural property representation.
+ *
+ * @param equivalenceClasses,
+ * maps that mapping variables to equivalence classes.
+ * @param fds,
+ * a list of functional dependencies.
+ * @return a new normalized local structural property.
+ */
+ public ILocalStructuralProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+ List<FunctionalDependency> fds);
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
index 20e6215..f41d197 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java
@@ -65,42 +65,7 @@
}
};
- IPartitioningProperty UNPARTITIONED = new IPartitioningProperty() {
-
- @Override
- public PartitioningType getPartitioningType() {
- return PartitioningType.UNPARTITIONED;
- }
-
- @Override
- public IPartitioningProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
- List<FunctionalDependency> fds) {
- return UNPARTITIONED;
- }
-
- @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();
- }
-
- @Override
- public void substituteColumnVars(Map<LogicalVariable, LogicalVariable> variableMap) {
- }
- };
+ IPartitioningProperty UNPARTITIONED = new UnpartitionedProperty();
PartitioningType getPartitioningType();
@@ -113,3 +78,42 @@
void substituteColumnVars(Map<LogicalVariable, LogicalVariable> varMap);
}
+
+class UnpartitionedProperty implements IPartitioningProperty {
+
+ @Override
+ public PartitioningType getPartitioningType() {
+ return PartitioningType.UNPARTITIONED;
+ }
+
+ @Override
+ public IPartitioningProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+ List<FunctionalDependency> fds) {
+ return UNPARTITIONED;
+ }
+
+ @Override
+ public void getColumns(Collection<LogicalVariable> columns) {
+ // No partitioning columns for UNPARTITIONED.
+ }
+
+ @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();
+ }
+
+ @Override
+ public void substituteColumnVars(Map<LogicalVariable, LogicalVariable> variableMap) {
+ // No partition columns are maintained for UNPARTITIONED.
+ }
+}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
index df2db32..6f4c296 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java
@@ -20,9 +20,11 @@
import java.util.Collection;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import org.apache.hyracks.algebricks.common.utils.ListSet;
+import org.apache.hyracks.algebricks.core.algebra.base.EquivalenceClass;
import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
public class LocalGroupingProperty extends AbstractGroupingProperty implements ILocalStructuralProperty {
@@ -66,14 +68,14 @@
@Override
public ILocalStructuralProperty retainVariables(Collection<LogicalVariable> vars) {
- Set<LogicalVariable> newVars = new ListSet<LogicalVariable>();
+ Set<LogicalVariable> newVars = new ListSet<>();
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>();
+ Set<LogicalVariable> newColumns = new ListSet<>();
// Matches the prefix of the original column set.
for (LogicalVariable v : columnSet) {
if (newVars.contains(v)) {
@@ -82,7 +84,7 @@
break;
}
}
- if (newColumns.size() > 0) {
+ if (!newColumns.isEmpty()) {
return new LocalGroupingProperty(newColumns, preferredOrderEnforcer.subList(0, newColumns.size()));
} else {
return null;
@@ -91,17 +93,25 @@
@Override
public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys) {
- Set<LogicalVariable> newColumns = new ListSet<LogicalVariable>();
+ Set<LogicalVariable> newColumns = new ListSet<>();
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()));
+ if (!newColumns.isEmpty()) {
+ return new LocalGroupingProperty(newColumns,
+ preferredOrderEnforcer.subList(groupKeys.size(), newColumns.size()));
} else {
return null;
}
}
+
+ @Override
+ public ILocalStructuralProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+ List<FunctionalDependency> fds) {
+ Set<LogicalVariable> normalizedColumnSet =
+ normalizeAndReduceGroupingColumns(columnSet, equivalenceClasses, fds);
+ return new LocalGroupingProperty(normalizedColumnSet, preferredOrderEnforcer);
+ }
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
index 6b39a8d..e7e98a5 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java
@@ -20,12 +20,12 @@
import java.util.ArrayList;
import java.util.Collection;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
-import org.apache.hyracks.algebricks.common.utils.ListSet;
import org.apache.hyracks.algebricks.core.algebra.base.EquivalenceClass;
import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder.OrderKind;
@@ -47,7 +47,7 @@
}
public List<LogicalVariable> getColumns() {
- List<LogicalVariable> orderVars = new ArrayList<LogicalVariable>();
+ List<LogicalVariable> orderVars = new ArrayList<>();
for (OrderColumn oc : orderColumns) {
orderVars.add(oc.getColumn());
}
@@ -55,7 +55,7 @@
}
public List<OrderKind> getOrders() {
- List<OrderKind> orderKinds = new ArrayList<OrderKind>();
+ List<OrderKind> orderKinds = new ArrayList<>();
for (OrderColumn oc : orderColumns) {
orderKinds.add(oc.getOrder());
}
@@ -83,6 +83,11 @@
}
@Override
+ public int hashCode() {
+ return orderColumns.hashCode();
+ }
+
+ @Override
public boolean equals(Object object) {
if (object instanceof LocalOrderProperty) {
LocalOrderProperty lop = (LocalOrderProperty) object;
@@ -92,6 +97,14 @@
}
}
+ @Override
+ public ILocalStructuralProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
+ List<FunctionalDependency> fds) {
+ List<OrderColumn> normalizedOrderColumns = normalizeOrderingColumns(orderColumns, equivalenceClasses);
+ reduceOrderingColumns(normalizedOrderColumns, fds);
+ return new LocalOrderProperty(normalizedOrderColumns);
+ }
+
/**
* Whether current property implies the required property
*
@@ -99,7 +112,7 @@
* , a required property
* @return true if the current property satisfies the required property; otherwise false.
*/
- public final boolean implies(ILocalStructuralProperty required) {
+ public boolean implies(ILocalStructuralProperty required) {
if (required.getPropertyType() != PropertyType.LOCAL_ORDER_PROPERTY) {
return false;
}
@@ -124,69 +137,59 @@
return true;
}
- public final void normalizeOrderingColumns(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
- List<FunctionalDependency> fds) {
- replaceOrderingColumnsByEqClasses(equivalenceClasses);
- applyFDsToOrderingColumns(fds);
- }
-
- private void replaceOrderingColumnsByEqClasses(Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+ // Gets normalized ordering columns, where each column variable is a representative variable of its equivalence
+ // class, therefore, the matching of properties will can consider equivalence classes.
+ private List<OrderColumn> normalizeOrderingColumns(List<OrderColumn> inputOrderColumns,
+ Map<LogicalVariable, EquivalenceClass> equivalenceClasses) {
+ List<OrderColumn> newOrderColumns = new ArrayList<>();
if (equivalenceClasses == null || equivalenceClasses.isEmpty()) {
- return;
+ newOrderColumns.addAll(inputOrderColumns);
+ return newOrderColumns;
}
- List<OrderColumn> norm = new ArrayList<OrderColumn>();
- for (OrderColumn oc : orderColumns) {
+ for (OrderColumn oc : inputOrderColumns) {
LogicalVariable v = oc.getColumn();
EquivalenceClass ec = equivalenceClasses.get(v);
if (ec == null) {
- norm.add(new OrderColumn(v, oc.getOrder()));
+ newOrderColumns.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()));
+ newOrderColumns.add(new OrderColumn(ec.getVariableRepresentative(), oc.getOrder()));
}
}
}
- orderColumns = norm;
+ return newOrderColumns;
}
- private void applyFDsToOrderingColumns(List<FunctionalDependency> fds) {
+ // Using functional dependencies to eliminate unnecessary ordering columns.
+ private void reduceOrderingColumns(List<OrderColumn> inputOrderColumns, 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;
+ Set<OrderColumn> impliedColumns = new HashSet<>();
+ Set<LogicalVariable> currentPrefix = new HashSet<>();
+ for (OrderColumn orderColumn : inputOrderColumns) {
+ LogicalVariable orderVariable = orderColumn.getColumn();
for (FunctionalDependency fdep : fds) {
- if (columns.containsAll(fdep.getHead()) && fdep.getTail().contains(v)) {
- isImpliedByAnFD = true;
- norm.addAll(fdep.getHead());
+ // Checks if the current ordering variable is implied by the prefix order columns.
+ if (currentPrefix.containsAll(fdep.getHead()) && fdep.getTail().contains(orderVariable)) {
+ impliedColumns.add(orderColumn);
break;
}
-
}
- if (!isImpliedByAnFD) {
- norm.add(v);
- }
+ currentPrefix.add(orderVariable);
}
- Set<OrderColumn> impliedColumns = new ListSet<OrderColumn>();
- for (OrderColumn oc : orderColumns) {
- if (!norm.contains(oc.getColumn())) {
- impliedColumns.add(oc);
- }
- }
- orderColumns.removeAll(impliedColumns);
+ inputOrderColumns.removeAll(impliedColumns);
}
@Override
public ILocalStructuralProperty retainVariables(Collection<LogicalVariable> vars) {
List<LogicalVariable> columns = getColumns();
- List<LogicalVariable> newVars = new ArrayList<LogicalVariable>();
+ List<LogicalVariable> newVars = new ArrayList<>();
newVars.addAll(vars);
newVars.retainAll(columns);
- List<OrderColumn> newColumns = new ArrayList<OrderColumn>();
+ List<OrderColumn> newColumns = new ArrayList<>();
for (OrderColumn oc : orderColumns) {
if (newVars.contains(oc.getColumn())) {
newColumns.add(oc);
@@ -194,7 +197,7 @@
break;
}
}
- if (newColumns.size() > 0) {
+ if (!newColumns.isEmpty()) {
return new LocalOrderProperty(newColumns);
} else {
return null;
@@ -203,13 +206,13 @@
@Override
public ILocalStructuralProperty regardToGroup(Collection<LogicalVariable> groupKeys) {
- List<OrderColumn> newColumns = new ArrayList<OrderColumn>();
+ List<OrderColumn> newColumns = new ArrayList<>();
for (OrderColumn oc : orderColumns) {
if (!groupKeys.contains(oc.getColumn())) {
newColumns.add(oc);
}
}
- if (newColumns.size() > 0) {
+ if (!newColumns.isEmpty()) {
return new LocalOrderProperty(newColumns);
} else {
return null;
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
index f2e4bde..f2fed13 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java
@@ -21,9 +21,7 @@
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;
@@ -35,19 +33,20 @@
public class PropertiesUtil {
public Set<LogicalVariable> closureUnderFDs(Collection<LogicalVariable> vars, List<FunctionalDependency> fdList) {
- Set<LogicalVariable> k = new ListSet<LogicalVariable>(vars);
+ Set<LogicalVariable> k = new ListSet<>(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;
- }
+ if (!k.containsAll(h)) {
+ continue;
+ }
+ List<LogicalVariable> t = fd.getTail();
+ for (LogicalVariable v : t) {
+ if (!(k.contains(v))) {
+ k.add(v);
+ change = true;
}
}
}
@@ -55,6 +54,21 @@
return k;
}
+ /**
+ * Checks whether delivered properties can satisfy required properties, considering equivalence class and
+ * functional dependencies.
+ *
+ * @param reqd,
+ * the required property list.
+ * @param dlvd,
+ * the delivered property list.
+ * @param equivalenceClasses,
+ * a map from variables to their equivalence classes.
+ * @param fds,
+ * a list of functional dependencies.
+ * @return true if the delivered property list can satisfy the required property list;
+ * false otherwise.
+ */
public static boolean matchLocalProperties(List<ILocalStructuralProperty> reqd, List<ILocalStructuralProperty> dlvd,
Map<LogicalVariable, EquivalenceClass> equivalenceClasses, List<FunctionalDependency> fds) {
if (reqd == null) {
@@ -63,54 +77,45 @@
if (dlvd == null) {
return false;
}
- normalizeLocals(reqd, equivalenceClasses, fds);
- normalizeLocals(dlvd, equivalenceClasses, fds);
+ return matchNormalizedLocalProperties(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();
- }
+ // Checks whether normalized delivered properties can satisfy normalized required property.
+ private static boolean matchNormalizedLocalProperties(List<ILocalStructuralProperty> reqs,
+ List<ILocalStructuralProperty> dlvds) {
+ boolean hasOrderPropertyInReq = false;
+ boolean hasGroupingPropertyInReq = false;
+ boolean orderPropertyMet = false;
+ boolean groupingPropertyMet = false;
+ for (ILocalStructuralProperty req : reqs) {
+ PropertyType reqType = req.getPropertyType();
+ hasOrderPropertyInReq |= reqType == PropertyType.LOCAL_ORDER_PROPERTY;
+ hasGroupingPropertyInReq |= reqType == PropertyType.LOCAL_GROUPING_PROPERTY;
+ for (ILocalStructuralProperty dlvd : dlvds) {
+ PropertyType dlvdType = dlvd.getPropertyType();
+ if (reqType == PropertyType.LOCAL_ORDER_PROPERTY && dlvdType != PropertyType.LOCAL_ORDER_PROPERTY) {
+ // A grouping property cannot meet an order property, but an order property can meet a grouping
+ // property.
+ continue;
+ }
+ if (reqType == PropertyType.LOCAL_ORDER_PROPERTY) {
+ LocalOrderProperty lop = (LocalOrderProperty) dlvd;
+ // It is enough that one required ordering property is met.
+ orderPropertyMet |= lop.implies(req);
+ } else {
+ Set<LogicalVariable> reqdCols = new ListSet<>();
+ Set<LogicalVariable> dlvdCols = new ListSet<>();
+ req.getColumns(reqdCols);
+ dlvd.getColumns(dlvdCols);
+ // It is enough that one required grouping property is met.
+ groupingPropertyMet |= isPrefixOf(reqdCols.iterator(), dlvdCols.iterator());
}
}
- if (!implied) {
- return false;
- }
}
- return true;
+ // Delivered properties satisfy required properties if one of required order properties is
+ // satisfied and one of required grouping properties is satisfied.
+ return (!hasOrderPropertyInReq || orderPropertyMet) && (!hasGroupingPropertyInReq || groupingPropertyMet);
}
public static boolean matchPartitioningProps(IPartitioningProperty reqd, IPartitioningProperty dlvd,
@@ -183,7 +188,7 @@
* @return the list of LogicalVariables
*/
private static List<LogicalVariable> orderColumnsToVariables(List<OrderColumn> orderColumns) {
- List<LogicalVariable> columns = new ArrayList<LogicalVariable>();
+ List<LogicalVariable> columns = new ArrayList<>();
for (OrderColumn oc : orderColumns) {
columns.add(oc.getColumn());
}
@@ -277,47 +282,13 @@
return fdSat;
}
- private static void normalizeLocals(List<ILocalStructuralProperty> props,
+ // Gets normalized local structural properties according to equivalence classes and functional dependencies.
+ private static List<ILocalStructuralProperty> 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++;
- }
+ List<ILocalStructuralProperty> normalizedLocalProperties = new ArrayList<>();
+ for (ILocalStructuralProperty prop : props) {
+ normalizedLocalProperties.add(prop.normalize(equivalenceClasses, fds));
}
-
- 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());
+ return normalizedLocalProperties;
}
}
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/StructuralPropertiesVector.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/StructuralPropertiesVector.java
index 233c4a6..ca101b7 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/StructuralPropertiesVector.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/StructuralPropertiesVector.java
@@ -30,8 +30,8 @@
private List<ILocalStructuralProperty> propsLocal;
private IPartitioningProperty propPartitioning;
- public static final StructuralPropertiesVector EMPTY_PROPERTIES_VECTOR = new StructuralPropertiesVector(null,
- new ArrayList<ILocalStructuralProperty>());
+ public static final StructuralPropertiesVector EMPTY_PROPERTIES_VECTOR =
+ new StructuralPropertiesVector(null, new ArrayList<ILocalStructuralProperty>());
public StructuralPropertiesVector(IPartitioningProperty propPartitioning,
List<ILocalStructuralProperty> propsLocal) {
@@ -56,7 +56,7 @@
@Override
public IPhysicalPropertiesVector clone() {
- List<ILocalStructuralProperty> propsCopy = new LinkedList<ILocalStructuralProperty>();
+ List<ILocalStructuralProperty> propsCopy = new LinkedList<>();
if (propsLocal != null) {
propsCopy.addAll(propsLocal);
}
@@ -75,18 +75,17 @@
List<FunctionalDependency> fds) {
List<ILocalStructuralProperty> plist = reqd.getLocalProperties();
List<ILocalStructuralProperty> diffLocals = null;
- if (plist != null && !plist.isEmpty()) {
- if (!PropertiesUtil.matchLocalProperties(plist, propsLocal, equivalenceClasses, fds)) {
- diffLocals = plist;
- }
+ if (plist != null && !plist.isEmpty()
+ && !PropertiesUtil.matchLocalProperties(plist, propsLocal, equivalenceClasses, fds)) {
+ diffLocals = plist;
}
IPartitioningProperty diffPart = null;
IPartitioningProperty reqdPart = reqd.getPartitioningProperty();
if (reqdPart != null) {
- IPartitioningProperty normalizedReqPart = reqdPart.normalize(equivalenceClasses,
- mayExpandProperties ? fds : null);
+ IPartitioningProperty normalizedReqPart =
+ reqdPart.normalize(equivalenceClasses, mayExpandProperties ? fds : null);
IPartitioningProperty normalizedPropPart = propPartitioning.normalize(equivalenceClasses, fds);
if (!PropertiesUtil.matchPartitioningProps(normalizedReqPart, normalizedPropPart, mayExpandProperties)) {
diffPart = reqdPart;
diff --git a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/UnorderedPartitionedProperty.java b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/UnorderedPartitionedProperty.java
index 7d0d4cf..641557c 100644
--- a/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/UnorderedPartitionedProperty.java
+++ b/hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/UnorderedPartitionedProperty.java
@@ -23,7 +23,6 @@
import java.util.Map;
import java.util.Set;
-import org.apache.hyracks.algebricks.common.utils.ListSet;
import org.apache.hyracks.algebricks.core.algebra.base.EquivalenceClass;
import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
@@ -44,10 +43,9 @@
@Override
public IPartitioningProperty normalize(Map<LogicalVariable, EquivalenceClass> equivalenceClasses,
List<FunctionalDependency> fds) {
- UnorderedPartitionedProperty partitioningProperty = new UnorderedPartitionedProperty(new ListSet<>(columnSet),
- domain);
- partitioningProperty.normalizeGroupingColumns(equivalenceClasses, fds);
- return partitioningProperty;
+ Set<LogicalVariable> normalizedColumnSet =
+ normalizeAndReduceGroupingColumns(columnSet, equivalenceClasses, fds);
+ return new UnorderedPartitionedProperty(normalizedColumnSet, domain);
}
@Override