You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by GitBox <gi...@apache.org> on 2020/08/13 10:23:31 UTC
[GitHub] [calcite] thomasrebele opened a new pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
thomasrebele opened a new pull request #2109:
URL: https://github.com/apache/calcite/pull/2109
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472141447
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
Review comment:
Since the limit parameter is "optional" (it can take `Integer.MAX_VALUE` if `fetch` is null in `EnumerableLimitSort`, I think the current method name is ok.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472859765
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
I've added an explanation at the beginning and more comments in the actual code to make the algorithm easier to understand.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#issuecomment-673711722
Thanks Thomas!
I will also give a code review soon.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472135871
##########
File path: core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
##########
@@ -1039,6 +1039,54 @@ private void basePushFilterPastAggWithGroupingSets(boolean unchanged) {
.check();
}
+ /**
+ * Test if limit and sort are replaced by a limit sort.
+ * Test case for
+ * <a href="https://issues.apache.org/jira/browse/CALCITE-3920">[CALCITE-3920]
+ * Improve ORDER BY computation in Enumerable convention by exploiting LIMIT</a>.
+ */
+ @Test void testLimitSort() {
+ final String sql = "select mgr from sales.emp\n"
+ + "union select mgr from sales.emp\n"
+ + "order by mgr limit 10 offset 5";
+
+ VolcanoPlanner planner = new VolcanoPlanner(null, null);
+ planner.addRelTraitDef(ConventionTraitDef.INSTANCE);
+ RelOptUtil.registerDefaultRules(planner, false, false);
+ planner.addRule(EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE);
+
+ Tester tester = createTester().withDecorrelation(true)
+ .withClusterFactory(
+ relOptCluster -> RelOptCluster.create(planner, relOptCluster.getRexBuilder()));
+
+ RelRoot root = tester.convertSqlToRel(sql);
+
+ String planBefore = NL + RelOptUtil.toString(root.rel);
+ getDiffRepos().assertEquals("planBefore", "${planBefore}", planBefore);
+
+ RuleSet ruleSet =
+ RuleSets.ofList(
+ EnumerableRules.ENUMERABLE_SORT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE,
Review comment:
Yes, to check whether the new operator is chosen correctly. A plan with EnumerableLimit(EnumerableSort(...)) should have a higher cost.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r470268938
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSortRule.java
##########
@@ -0,0 +1,60 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.logical.LogicalSort;
+
+/**
+ * Rule to convert an {@link EnumerableLimit} of on
+ * {@link EnumerableSort} into an {@link EnumerableLimitSort}.
+ */
+public class EnumerableLimitSortRule extends RelRule<EnumerableLimitSortRule.Config> {
+
+ /**
+ * Creates a EnumerableLimitSortRule.
+ */
+ public EnumerableLimitSortRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ final LogicalSort sort = call.rel(0);
+ RelNode input = sort.getInput();
+ final Sort o = EnumerableLimitSort.create(//
Review comment:
remove the extra `//`
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableLimitSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableLimitSort(
+ RelOptCluster cluster,
+ RelTraitSet traitSet,
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ super(cluster, traitSet, input, collation, offset, fetch);
+ assert this.getConvention() instanceof EnumerableConvention;
+ assert this.getConvention() == input.getConvention();
+ }
+
+ /** Creates an EnumerableLimitSort. */
+ public static EnumerableLimitSort create(
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = input.getCluster();
+ final RelTraitSet traitSet = cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableLimitSort(cluster, traitSet, input, collation, offset, fetch);
+ }
+
+ @Override public EnumerableLimitSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ return new EnumerableLimitSort(
+ this.getCluster(),
+ traitSet,
+ newInput,
+ newCollation,
+ offset,
+ fetch);
+ }
+
+ @Override public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
+ final BlockBuilder builder = new BlockBuilder();
+ final EnumerableRel child = (EnumerableRel) this.getInput();
+ final Result result = implementor.visitChild(this, 0, child, pref);
+ final PhysType physType = PhysTypeImpl.of(
+ implementor.getTypeFactory(),
+ this.getRowType(),
+ result.format);
+ Expression childExp = builder.append("child", result.block);
+
+ PhysType inputPhysType = result.physType;
+ final Pair<Expression, Expression> pair =
+ inputPhysType.generateCollationKey(this.collation.getFieldCollations());
+
+ Expression fetchVal;
+ if (this.fetch == null) {
+ fetchVal = Expressions.constant(Integer.valueOf(Integer.MAX_VALUE));
+ } else {
+ fetchVal = getExpression(this.fetch);
+ }
+
+ Expression offsetVal = this.offset == null ? Expressions.constant(Integer.valueOf(0))
+ : getExpression(this.offset);
+
+ builder.add(
+ Expressions.return_(
+ null, Expressions.call(
+ BuiltInMethod.ORDER_BY_WITH_FETCH_AND_OFFSET.method, Expressions.list(
+ childExp,
+ builder.append("keySelector", pair.left))
+ .appendIfNotNull(builder.appendIfNotNull("comparator", pair.right))
+ .appendIfNotNull(
+ builder.appendIfNotNull("offset",
+ Expressions.constant(offsetVal)))
+ .appendIfNotNull(
+ builder.appendIfNotNull("fetch",
+ Expressions.constant(fetchVal)))
+ )));
+ return implementor.result(physType, builder.toBlock());
+ }
+
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner, RelMetadataQuery mq) {
+ final double rowCount = mq.getRowCount(this.input).doubleValue();
+ double toSort = this.fetch == null ? rowCount : RexLiteral.intValue(this.fetch);
+ if (this.offset != null) {
+ toSort += RexLiteral.intValue(this.offset);
+ }
+ toSort = Math.min(rowCount, toSort);
Review comment:
Why not use `max`?
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
Review comment:
Does it make sense to name this function as `topNOrderBy` or `topNSortLimit`?
##########
File path: core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
##########
@@ -1039,6 +1039,54 @@ private void basePushFilterPastAggWithGroupingSets(boolean unchanged) {
.check();
}
+ /**
+ * Test if limit and sort are replaced by a limit sort.
+ * Test case for
+ * <a href="https://issues.apache.org/jira/browse/CALCITE-3920">[CALCITE-3920]
+ * Improve ORDER BY computation in Enumerable convention by exploiting LIMIT</a>.
+ */
+ @Test void testLimitSort() {
+ final String sql = "select mgr from sales.emp\n"
+ + "union select mgr from sales.emp\n"
+ + "order by mgr limit 10 offset 5";
+
+ VolcanoPlanner planner = new VolcanoPlanner(null, null);
+ planner.addRelTraitDef(ConventionTraitDef.INSTANCE);
+ RelOptUtil.registerDefaultRules(planner, false, false);
+ planner.addRule(EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE);
+
+ Tester tester = createTester().withDecorrelation(true)
+ .withClusterFactory(
+ relOptCluster -> RelOptCluster.create(planner, relOptCluster.getRexBuilder()));
+
+ RelRoot root = tester.convertSqlToRel(sql);
+
+ String planBefore = NL + RelOptUtil.toString(root.rel);
+ getDiffRepos().assertEquals("planBefore", "${planBefore}", planBefore);
+
+ RuleSet ruleSet =
+ RuleSets.ofList(
+ EnumerableRules.ENUMERABLE_SORT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE,
Review comment:
Do you need
```
EnumerableRules.ENUMERABLE_SORT_RULE,
EnumerableRules.ENUMERABLE_LIMIT_RULE,
```
as you have listed `EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE` in the list?
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
Review comment:
Out of curiosity: why do you decide to extend `Sort`?
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
+1. I was also looking for some comments to explain the algorithm briefly.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472661909
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
Yes.
Or you can link the JIRA but update the JIRA with the final detailed algorithm you have chosen.
I found the JIRA has many discussions so was confused on which algorithm you finally chose, until I read the implementation here :). Something to help people understand the implementation directly in the future will be very helpful.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r469934497
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableLimitSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableLimitSort(
+ RelOptCluster cluster,
+ RelTraitSet traitSet,
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ super(cluster, traitSet, input, collation, offset, fetch);
+ assert this.getConvention() instanceof EnumerableConvention;
+ assert this.getConvention() == input.getConvention();
+ }
+
+ /** Creates an EnumerableLimitSort. */
+ public static EnumerableLimitSort create(
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = input.getCluster();
+ final RelTraitSet traitSet = cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableLimitSort(cluster, traitSet, input, collation, offset, fetch);
+ }
+
+ @Override public EnumerableLimitSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ return new EnumerableLimitSort(
+ this.getCluster(),
+ traitSet,
+ newInput,
+ newCollation,
+ offset,
+ fetch);
+ }
+
+ @Override public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
+ final BlockBuilder builder = new BlockBuilder();
+ final EnumerableRel child = (EnumerableRel) this.getInput();
+ final Result result = implementor.visitChild(this, 0, child, pref);
+ final PhysType physType = PhysTypeImpl.of(
+ implementor.getTypeFactory(),
+ this.getRowType(),
+ result.format);
+ Expression childExp = builder.append("child", result.block);
Review comment:
minor: for consistency reasons inside this method, please declare all variables as "final" (if they are effectively final)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#issuecomment-675903441
@zabetak @julianhyde if you want to take a look at the new PR created by @thomasrebele , I think it is overall in a good shape
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r469942516
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
+ }
+ if (l.size() == 1) {
+ l = new ArrayList<>(l);
+ }
+ l.add(o);
+ return l;
+ });
+ size++;
+ }
+ }
+
+ if (offset > 0) {
+ // search until which key we have to remove entries from the map
+ int skipped = 0;
+ TKey until = null;
+ for (Map.Entry<TKey, List<TSource>> e : map.entrySet()) {
+ skipped += e.getValue().size();
+
+ if (skipped > offset) {
+ // we might need to remove entries from the list
+ List<TSource> l = e.getValue();
+ int toKeep = skipped - offset;
+ if (toKeep < l.size()) {
+ l.subList(0, l.size() - toKeep).clear();
+ }
+
+ until = e.getKey();
+ break;
+ }
+ }
+ if (until == null) {
+ return Linq4j.emptyEnumerator();
+ } else if (until != null) {
Review comment:
this if condition looks wrong/useless
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada merged pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada merged pull request #2109:
URL: https://github.com/apache/calcite/pull/2109
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r469938024
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableLimitSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableLimitSort(
+ RelOptCluster cluster,
+ RelTraitSet traitSet,
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ super(cluster, traitSet, input, collation, offset, fetch);
+ assert this.getConvention() instanceof EnumerableConvention;
+ assert this.getConvention() == input.getConvention();
+ }
+
+ /** Creates an EnumerableLimitSort. */
+ public static EnumerableLimitSort create(
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = input.getCluster();
+ final RelTraitSet traitSet = cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableLimitSort(cluster, traitSet, input, collation, offset, fetch);
+ }
+
+ @Override public EnumerableLimitSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ return new EnumerableLimitSort(
+ this.getCluster(),
+ traitSet,
+ newInput,
+ newCollation,
+ offset,
+ fetch);
+ }
+
+ @Override public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
+ final BlockBuilder builder = new BlockBuilder();
+ final EnumerableRel child = (EnumerableRel) this.getInput();
+ final Result result = implementor.visitChild(this, 0, child, pref);
+ final PhysType physType = PhysTypeImpl.of(
+ implementor.getTypeFactory(),
+ this.getRowType(),
+ result.format);
+ Expression childExp = builder.append("child", result.block);
+
+ PhysType inputPhysType = result.physType;
+ final Pair<Expression, Expression> pair =
+ inputPhysType.generateCollationKey(this.collation.getFieldCollations());
+
+ Expression fetchVal;
+ if (this.fetch == null) {
+ fetchVal = Expressions.constant(Integer.valueOf(Integer.MAX_VALUE));
+ } else {
+ fetchVal = getExpression(this.fetch);
+ }
+
+ Expression offsetVal = this.offset == null ? Expressions.constant(Integer.valueOf(0))
+ : getExpression(this.offset);
+
+ builder.add(
+ Expressions.return_(
+ null, Expressions.call(
+ BuiltInMethod.ORDER_BY_WITH_FETCH_AND_OFFSET.method, Expressions.list(
+ childExp,
+ builder.append("keySelector", pair.left))
+ .appendIfNotNull(builder.appendIfNotNull("comparator", pair.right))
+ .appendIfNotNull(
+ builder.appendIfNotNull("offset",
+ Expressions.constant(offsetVal)))
+ .appendIfNotNull(
+ builder.appendIfNotNull("fetch",
+ Expressions.constant(fetchVal)))
+ )));
+ return implementor.result(physType, builder.toBlock());
+ }
+
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner, RelMetadataQuery mq) {
+ final double rowCount = mq.getRowCount(this.input).doubleValue();
+ double toSort = this.fetch == null ? rowCount : RexLiteral.intValue(this.fetch);
Review comment:
Inside `implement` method you allow `this.fetch` to be a dynamic parameter; however here (`computeSelfCost`) you assume it will be a `RexLiteral` (I have the impression that arriving at this point with a `RexDynamicParam` will throw an exception).
Either we modify cost computation (but it will be impossible to give a precise cost in case of dynamic parameter); or to simplify things we could decide that `EnumerableLimitSort` only supports fetch (and offset) in the form of `RexLiteral` (and adapt `EnumerableLimitSortRule` accordingly).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472661909
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
Yes.
Or you can link the JIRA but update the JIRA with the final detailed algorithm you have chosen.
I found the JIRA has many discussions so was confused on which algorithm you finally chose, until I read the implementation here :). Something to help people understand the implementation in the future will be very helpful.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#issuecomment-686301247
@amaliujia @zabetak if you want to take a final look, please go ahead.
The PR LGTM, I plan to merge it in the next 24h unless somebody has further comments about it.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r469952249
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
minor: maybe adding here the same comment that we have in `toLookup_` to explain the choice of List implementation?
`// for first entry, use a singleton list to save space`
`// when we go from 1 to 2 elements, switch to array list`
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472663346
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
Review comment:
I see. That makes sense.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472135224
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
Review comment:
For the same reason that EnumerableSort extends Sort. I guess it is because both classes provide an implementation of a Sort algorithm.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472132673
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableLimitSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableLimitSort(
+ RelOptCluster cluster,
+ RelTraitSet traitSet,
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ super(cluster, traitSet, input, collation, offset, fetch);
+ assert this.getConvention() instanceof EnumerableConvention;
+ assert this.getConvention() == input.getConvention();
+ }
+
+ /** Creates an EnumerableLimitSort. */
+ public static EnumerableLimitSort create(
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = input.getCluster();
+ final RelTraitSet traitSet = cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableLimitSort(cluster, traitSet, input, collation, offset, fetch);
+ }
+
+ @Override public EnumerableLimitSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ return new EnumerableLimitSort(
+ this.getCluster(),
+ traitSet,
+ newInput,
+ newCollation,
+ offset,
+ fetch);
+ }
+
+ @Override public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
+ final BlockBuilder builder = new BlockBuilder();
+ final EnumerableRel child = (EnumerableRel) this.getInput();
+ final Result result = implementor.visitChild(this, 0, child, pref);
+ final PhysType physType = PhysTypeImpl.of(
+ implementor.getTypeFactory(),
+ this.getRowType(),
+ result.format);
+ Expression childExp = builder.append("child", result.block);
+
+ PhysType inputPhysType = result.physType;
+ final Pair<Expression, Expression> pair =
+ inputPhysType.generateCollationKey(this.collation.getFieldCollations());
+
+ Expression fetchVal;
+ if (this.fetch == null) {
+ fetchVal = Expressions.constant(Integer.valueOf(Integer.MAX_VALUE));
+ } else {
+ fetchVal = getExpression(this.fetch);
+ }
+
+ Expression offsetVal = this.offset == null ? Expressions.constant(Integer.valueOf(0))
+ : getExpression(this.offset);
+
+ builder.add(
+ Expressions.return_(
+ null, Expressions.call(
+ BuiltInMethod.ORDER_BY_WITH_FETCH_AND_OFFSET.method, Expressions.list(
+ childExp,
+ builder.append("keySelector", pair.left))
+ .appendIfNotNull(builder.appendIfNotNull("comparator", pair.right))
+ .appendIfNotNull(
+ builder.appendIfNotNull("offset",
+ Expressions.constant(offsetVal)))
+ .appendIfNotNull(
+ builder.appendIfNotNull("fetch",
+ Expressions.constant(fetchVal)))
+ )));
+ return implementor.result(physType, builder.toBlock());
+ }
+
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner, RelMetadataQuery mq) {
+ final double rowCount = mq.getRowCount(this.input).doubleValue();
+ double toSort = this.fetch == null ? rowCount : RexLiteral.intValue(this.fetch);
Review comment:
I've modified the cost, so that it falls back to the row count if there are dynamic parameters
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472661909
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
Yes.
Or you can link the JIRA but update the JIRA with the final detailed algorithm you have chosen.
I found the JIRA has many discussions so was confused on which algorithm you finally chose, until I read the implementation here :). Something help people easy to understand the implementation in the future will be very helpful.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472134016
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
Review comment:
@amaliujia, do you mean that I should add some comments that explain the implementation of the new orderBy method.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472663111
##########
File path: core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java
##########
@@ -1039,6 +1039,54 @@ private void basePushFilterPastAggWithGroupingSets(boolean unchanged) {
.check();
}
+ /**
+ * Test if limit and sort are replaced by a limit sort.
+ * Test case for
+ * <a href="https://issues.apache.org/jira/browse/CALCITE-3920">[CALCITE-3920]
+ * Improve ORDER BY computation in Enumerable convention by exploiting LIMIT</a>.
+ */
+ @Test void testLimitSort() {
+ final String sql = "select mgr from sales.emp\n"
+ + "union select mgr from sales.emp\n"
+ + "order by mgr limit 10 offset 5";
+
+ VolcanoPlanner planner = new VolcanoPlanner(null, null);
+ planner.addRelTraitDef(ConventionTraitDef.INSTANCE);
+ RelOptUtil.registerDefaultRules(planner, false, false);
+ planner.addRule(EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE);
+
+ Tester tester = createTester().withDecorrelation(true)
+ .withClusterFactory(
+ relOptCluster -> RelOptCluster.create(planner, relOptCluster.getRexBuilder()));
+
+ RelRoot root = tester.convertSqlToRel(sql);
+
+ String planBefore = NL + RelOptUtil.toString(root.rel);
+ getDiffRepos().assertEquals("planBefore", "${planBefore}", planBefore);
+
+ RuleSet ruleSet =
+ RuleSets.ofList(
+ EnumerableRules.ENUMERABLE_SORT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_RULE,
+ EnumerableRules.ENUMERABLE_LIMIT_SORT_RULE,
Review comment:
Thanks for your clarification!
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] amaliujia commented on pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
amaliujia commented on pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#issuecomment-686304651
LGTM thanks!
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] rubenada commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
rubenada commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r469949470
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
+ Enumerable<TSource> source,
+ Function1<TSource, TKey> keySelector,
+ Comparator<TKey> comparator,
+ int offset, int fetch) {
+ return new AbstractEnumerable<TSource>() {
+ @Override public Enumerator<TSource> enumerator() {
+ TreeMap<TKey, List<TSource>> map = new TreeMap<>(comparator);
+ long size = 0;
+ long needed = fetch + offset;
+
+ try (Enumerator<TSource> os = source.enumerator()) {
+ while (os.moveNext()) {
+ TSource o = os.current();
+ TKey key = keySelector.apply(o);
+ if (needed >= 0 && size >= needed) {
+ if (comparator.compare(key, map.lastKey()) >= 0) {
+ continue;
+ }
+ // remove last entry from tree map
+ List<TSource> l = map.get(map.lastKey());
+ if (l.size() == 1) {
+ map.remove(map.lastKey());
+ } else {
+ l.remove(l.size() - 1);
+ }
+ size--;
+ }
+ map.compute(key, (k, l) -> {
+ if (l == null) {
+ return Collections.singletonList(o);
+ }
+ if (l.size() == 1) {
+ l = new ArrayList<>(l);
+ }
+ l.add(o);
+ return l;
+ });
+ size++;
+ }
+ }
+
+ if (offset > 0) {
+ // search until which key we have to remove entries from the map
+ int skipped = 0;
+ TKey until = null;
+ for (Map.Entry<TKey, List<TSource>> e : map.entrySet()) {
+ skipped += e.getValue().size();
+
+ if (skipped > offset) {
+ // we might need to remove entries from the list
+ List<TSource> l = e.getValue();
+ int toKeep = skipped - offset;
+ if (toKeep < l.size()) {
+ l.subList(0, l.size() - toKeep).clear();
+ }
+
+ until = e.getKey();
+ break;
+ }
+ }
+ if (until == null) {
+ return Linq4j.emptyEnumerator();
+ } else if (until != null) {
Review comment:
also, since we have a return inside the previous `if`, I think we could just remove the `else`
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472136559
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2624,6 +2624,86 @@ public static boolean isMergeJoinSupported(JoinType joinType) {
};
}
+
+ /**
+ * A sort implementation optimized for a sort with a fetch size (LIMIT).
+ * @param offset how many rows are skipped from the sorted output.
+ * Must be greater than or equal to 0.
+ * @param fetch how many rows are retrieved. Must be greater than 0.
+ */
+ public static <TSource, TKey> Enumerable<TSource> orderBy(
Review comment:
Might make sense, I'm not yet familiar how the Calcite project chooses names.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on a change in pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on a change in pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#discussion_r472138299
##########
File path: core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableLimitSort.java
##########
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+package org.apache.calcite.adapter.enumerable;
+
+import org.apache.calcite.linq4j.tree.BlockBuilder;
+import org.apache.calcite.linq4j.tree.Expression;
+import org.apache.calcite.linq4j.tree.Expressions;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.plan.RelOptPlanner;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.RelCollation;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Sort;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexLiteral;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.util.BuiltInMethod;
+import org.apache.calcite.util.Pair;
+
+import static org.apache.calcite.adapter.enumerable.EnumerableLimit.getExpression;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention enumerable calling convention}.
+ * It optimizes sorts that have a limit and an optional offset.
+ */
+public class EnumerableLimitSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableLimitSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableLimitSort(
+ RelOptCluster cluster,
+ RelTraitSet traitSet,
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ super(cluster, traitSet, input, collation, offset, fetch);
+ assert this.getConvention() instanceof EnumerableConvention;
+ assert this.getConvention() == input.getConvention();
+ }
+
+ /** Creates an EnumerableLimitSort. */
+ public static EnumerableLimitSort create(
+ RelNode input,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = input.getCluster();
+ final RelTraitSet traitSet = cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableLimitSort(cluster, traitSet, input, collation, offset, fetch);
+ }
+
+ @Override public EnumerableLimitSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ return new EnumerableLimitSort(
+ this.getCluster(),
+ traitSet,
+ newInput,
+ newCollation,
+ offset,
+ fetch);
+ }
+
+ @Override public Result implement(EnumerableRelImplementor implementor, Prefer pref) {
+ final BlockBuilder builder = new BlockBuilder();
+ final EnumerableRel child = (EnumerableRel) this.getInput();
+ final Result result = implementor.visitChild(this, 0, child, pref);
+ final PhysType physType = PhysTypeImpl.of(
+ implementor.getTypeFactory(),
+ this.getRowType(),
+ result.format);
+ Expression childExp = builder.append("child", result.block);
+
+ PhysType inputPhysType = result.physType;
+ final Pair<Expression, Expression> pair =
+ inputPhysType.generateCollationKey(this.collation.getFieldCollations());
+
+ Expression fetchVal;
+ if (this.fetch == null) {
+ fetchVal = Expressions.constant(Integer.valueOf(Integer.MAX_VALUE));
+ } else {
+ fetchVal = getExpression(this.fetch);
+ }
+
+ Expression offsetVal = this.offset == null ? Expressions.constant(Integer.valueOf(0))
+ : getExpression(this.offset);
+
+ builder.add(
+ Expressions.return_(
+ null, Expressions.call(
+ BuiltInMethod.ORDER_BY_WITH_FETCH_AND_OFFSET.method, Expressions.list(
+ childExp,
+ builder.append("keySelector", pair.left))
+ .appendIfNotNull(builder.appendIfNotNull("comparator", pair.right))
+ .appendIfNotNull(
+ builder.appendIfNotNull("offset",
+ Expressions.constant(offsetVal)))
+ .appendIfNotNull(
+ builder.appendIfNotNull("fetch",
+ Expressions.constant(fetchVal)))
+ )));
+ return implementor.result(physType, builder.toBlock());
+ }
+
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner, RelMetadataQuery mq) {
+ final double rowCount = mq.getRowCount(this.input).doubleValue();
+ double toSort = this.fetch == null ? rowCount : RexLiteral.intValue(this.fetch);
+ if (this.offset != null) {
+ toSort += RexLiteral.intValue(this.offset);
+ }
+ toSort = Math.min(rowCount, toSort);
Review comment:
If there are only rowCount rows, we only need to sort that many. E.g., if fetch is 100, but there are only 10 rows in the input, we only need to do lookups for the 10 rows.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [calcite] thomasrebele commented on pull request #2109: [CALCITE-3920] Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
Posted by GitBox <gi...@apache.org>.
thomasrebele commented on pull request #2109:
URL: https://github.com/apache/calcite/pull/2109#issuecomment-685530090
I've added a check for fetch=0, so that a dynamic fetch size might be set to 0.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org