julianhyde commented on a change in pull request #2080:
URL: https://github.com/apache/calcite/pull/2080#discussion_r460190920
##########
File path: core/src/test/java/org/apache/calcite/test/TopDownOptTest.java
##########
@@ -217,6 +217,16 @@
.check();
}
+ // test if limit and sort are replaced by a top-n heap sort
+ @Test void testSortLimit() {
+ final String sql = "select mgr from sales.emp\n"
+ + "union select mgr from sales.emp\n"
+ + "order by mgr limit 10 offset 5";
+ Query.create(sql)
+ .addRule(EnumerableRules.ENUMERABLE_TOPN_HEAP_SORT_RULE)
+ .check();
+ }
+
Review comment:
This should not be in `TopDownOptTest`. Should be in `RelOptRulesTest`.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
+ */
+public class EnumerableTopNHeapSort extends Sort implements EnumerableRel {
Review comment:
A better name would be `EnumerableHeapSort`. Top-N is one of its
capabilities, but not its defining identity.
##########
File path:
linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2636,6 +2636,56 @@ public static boolean isMergeJoinSupported(JoinType
joinType) {
return orderBy(source, keySelector, Collections.reverseOrder(comparator));
}
+ /**
+ * A sort implementation based on a heap (or priority queue).
Review comment:
I argue elsewhere that we should support HeapSort without offset and
fetch. But that heap sort is more efficient than order algorithms especially
when fetch is present. The comment should make that point.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
+ */
+public class EnumerableTopNHeapSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableTopNHeapSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableTopNHeapSort(
+ 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();
+ assert fetch != null;
+ }
+
+ /** Creates an EnumerableTopNHeapSort. */
+ public static EnumerableTopNHeapSort create(
+ RelNode child,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = child.getCluster();
+ final RelTraitSet traitSet =
cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableTopNHeapSort(cluster, traitSet, child, collation,
offset, fetch);
+ }
+
+ private static Expression getExpression(RexNode offset) {
+ if (offset instanceof RexDynamicParam) {
+ final RexDynamicParam param = (RexDynamicParam) offset;
+ return Expressions.convert_(
+ Expressions.call(
+ DataContext.ROOT,
+ BuiltInMethod.DATA_CONTEXT_GET.method,
+ Expressions.constant("?" + param.getIndex())), Integer.class);
+ } else {
+ return
Expressions.constant(Integer.valueOf(RexLiteral.intValue(offset)));
+ }
+ }
+
+ @Override public EnumerableTopNHeapSort copy(
+ RelTraitSet traitSet,
+ RelNode newInput,
+ RelCollation newCollation,
+ RexNode offset,
+ RexNode fetch) {
+ if (fetch == null) {
+ return null;
+ }
+
+ return new EnumerableTopNHeapSort(
+ 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))//
Review comment:
Remove '//' at end of line.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
Review comment:
'deals with' under-sells. The point is that with an offset it can be
much cheaper than other algorithms.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
+ */
+public class EnumerableTopNHeapSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableTopNHeapSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableTopNHeapSort(
+ 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();
+ assert fetch != null;
+ }
+
+ /** Creates an EnumerableTopNHeapSort. */
+ public static EnumerableTopNHeapSort create(
+ RelNode child,
+ RelCollation collation,
+ RexNode offset,
+ RexNode fetch) {
+ final RelOptCluster cluster = child.getCluster();
+ final RelTraitSet traitSet =
cluster.traitSetOf(EnumerableConvention.INSTANCE).replace(
+ collation);
+ return new EnumerableTopNHeapSort(cluster, traitSet, child, collation,
offset, fetch);
+ }
+
+ private static Expression getExpression(RexNode offset) {
Review comment:
You don't need to generate general expressions for `sort` and `offset`.
You can assume that they are literals, i.e. constant integers. `SortNode` uses
`((RexLiteral) rel.fetch).getValueAs(Integer.class)` (and similarly for
`offset`). You can too.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
+ */
+public class EnumerableTopNHeapSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableTopNHeapSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableTopNHeapSort(
+ 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();
+ assert fetch != null;
Review comment:
Related: can you add `Preconditions.checkArgument(fetch == null);` and
`Preconditions.checkArgument(offset == null);` in `EnumerableSort`'s
constructor. It is implicit but we've never bothered to check.
##########
File path:
core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableTopNHeapSort.java
##########
@@ -0,0 +1,162 @@
+/*
+ * 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.DataContext;
+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.RexDynamicParam;
+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 org.apache.calcite.util.Util;
+
+/**
+ * Implementation of {@link org.apache.calcite.rel.core.Sort} in
+ * {@link org.apache.calcite.adapter.enumerable.EnumerableConvention
enumerable calling convention}.
+ * It also deals with the offset and the limit.
+ */
+public class EnumerableTopNHeapSort extends Sort implements EnumerableRel {
+
+ /**
+ * Creates an EnumerableTopNHeapSort.
+ *
+ * <p>Use {@link #create} unless you know what you're doing.
+ */
+ public EnumerableTopNHeapSort(
+ 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();
+ assert fetch != null;
+ }
+
+ /** Creates an EnumerableTopNHeapSort. */
+ public static EnumerableTopNHeapSort create(
+ RelNode child,
Review comment:
Rename `child` to `input`; old code has `child` but we are using `input`
for new code.
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/TopNHeap.java
##########
@@ -0,0 +1,242 @@
+/*
+ * 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.linq4j;
+
+import org.apache.calcite.linq4j.function.Function1;
+
+import java.util.Comparator;
+
+/**
+ * Implementation of a stable binary heap with a fetch and an offset.
+ * Stable means that if two items are considered equal,
+ * they will appear in the same order as they were offered to the heap.
+ *
+ * @param <TSource> type of the element that will be added to the heap
+ * @param <TKey> type of the key, which the comparator will use for comparisons
+ */
+public class TopNHeap<TSource, TKey> {
+ static final int MAX_INIT_ARRAY_SIZE = 1024;
+ static final int ROOT = 1;
+
+ private final Function1<TSource, TKey> keyFn;
+ private final Comparator<TKey> cmp;
+ private final int fetch;
+ private final int offset;
+ private final int maxSize;
+
+ TKey headKey = null;
+ int size = 0;
+ int time = -Integer.MIN_VALUE;
+
+ /** Heap with 1-based index, heap[0] is not used */
+ TSource[] heap;
+ /** Stores the order of arrival of the elements in the heap */
+ int[] order;
Review comment:
I guess this field exists to ensure stability?
If so, you should state that stability is one of the goals of this class.
Also, add tests for stability.
Is there any other way to achieve stability? An extra array (and element
swaps at each stage) seems pretty expensive.
##########
File path: linq4j/src/main/java/org/apache/calcite/linq4j/TopNHeap.java
##########
@@ -0,0 +1,242 @@
+/*
+ * 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.linq4j;
+
+import org.apache.calcite.linq4j.function.Function1;
+
+import java.util.Comparator;
+
+/**
+ * Implementation of a stable binary heap with a fetch and an offset.
+ * Stable means that if two items are considered equal,
+ * they will appear in the same order as they were offered to the heap.
+ *
+ * @param <TSource> type of the element that will be added to the heap
+ * @param <TKey> type of the key, which the comparator will use for comparisons
+ */
+public class TopNHeap<TSource, TKey> {
Review comment:
Is this class necessary? Are there not heap implementations in the JDK
or Gauva?
`java.util.PriorityQueue` seems sufficient. Is there a good reason not to
use it? (Guava has a `MinMaxPriorityQueue`, but it maintains two heaps so I
expect it is more expensive.)
If not, can you explain in the doc what is the unfair advantage over those
algorithms. Maybe it is easier to maintain the 'max' element because you don't
have to deal with removals?
Is it possible to make this into a more conventional utility class by
providing just a Comparator and not a key-selector? The type parameters
'TSource, TKey' would be replaced by a simple type parameter 'E'.
##########
File path:
linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java
##########
@@ -2636,6 +2636,56 @@ public static boolean isMergeJoinSupported(JoinType
joinType) {
return orderBy(source, keySelector, Collections.reverseOrder(comparator));
}
+ /**
+ * A sort implementation based on a heap (or priority queue).
+ * @param fetch must be greater than 0
+ * @param offset must be greater than or equal to 0
Review comment:
minor quibble, but you should say what each parameter does, not just the
constraints on 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:
[email protected]
