Yingyi Bu has submitted this change and it was merged. Change subject: ASTERIXDB-1531: fix ORDER BY with primary keys as non-prefix sort keys. ......................................................................
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 <[email protected]> Integration-Tests: Jenkins <[email protected]> Reviewed-by: Yingyi Bu <[email protected]> --- A asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.aql A asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.aql A asterixdb/asterix-app/src/test/resources/runtimets/queries/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.aql A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.1.ddl.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.2.update.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.query.sqlpp A asterixdb/asterix-app/src/test/resources/runtimets/results/misc/query-ASTERIXDB-1531/query-ASTERIXDB-1531.3.adm M asterixdb/asterix-app/src/test/resources/runtimets/results/types/opentype_orderby_01/opentype_orderby_01.1.adm M asterixdb/asterix-app/src/test/resources/runtimets/testsuite.xml M asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/logical/visitors/FDsAndEquivClassesVisitor.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/AbstractPreclusteredGroupByPOperator.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/operators/physical/NestedTupleSourcePOperator.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/AbstractGroupingProperty.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/ILocalStructuralProperty.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/IPartitioningProperty.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalGroupingProperty.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/LocalOrderProperty.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/PropertiesUtil.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/StructuralPropertiesVector.java M hyracks-fullstack/algebricks/algebricks-core/src/main/java/org/apache/hyracks/algebricks/core/algebra/properties/UnorderedPartitionedProperty.java 21 files changed, 495 insertions(+), 312 deletions(-) Approvals: Yingyi Bu: Looks good to me, approved Jenkins: Verified; Verified 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 -- To view, visit https://asterix-gerrit.ics.uci.edu/1022 To unsubscribe, visit https://asterix-gerrit.ics.uci.edu/settings Gerrit-MessageType: merged Gerrit-Change-Id: Iee7fcdd6eb1279e8ee14ba75ee31ac118b00c806 Gerrit-PatchSet: 6 Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Owner: Yingyi Bu <[email protected]> Gerrit-Reviewer: Jenkins <[email protected]> Gerrit-Reviewer: Till Westmann <[email protected]> Gerrit-Reviewer: Yingyi Bu <[email protected]>
