[CALCITE-2102] Ignore duplicate ORDER BY keys, and ensure RelCollation contains no duplicates (John Fang)
Now, a RelCollation is guaranteed to have unique fields, via a precondition. SqlToRelConverter and RelBuilder eliminate duplicates, so users should not receive an error. Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/01ee7235 Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/01ee7235 Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/01ee7235 Branch: refs/heads/master Commit: 01ee7235b76f8d0111d43ab9d46655c3804777c0 Parents: ac5cce7 Author: xiaojian.fxj <[email protected]> Authored: Wed Dec 20 15:09:30 2017 +0800 Committer: Julian Hyde <[email protected]> Committed: Sun Dec 24 14:39:49 2017 -0800 ---------------------------------------------------------------------- .../enumerable/EnumerableMergeJoinRule.java | 3 +- .../apache/calcite/rel/RelCollationImpl.java | 4 ++ .../org/apache/calcite/rel/RelCollations.java | 35 ++++++++++++++-- .../calcite/sql2rel/SqlToRelConverter.java | 5 +-- .../org/apache/calcite/tools/RelBuilder.java | 8 +++- .../main/java/org/apache/calcite/util/Util.java | 34 ++++++++++++++++ .../apache/calcite/rel/RelCollationTest.java | 43 ++++++++++++++++---- .../org/apache/calcite/test/RelBuilderTest.java | 21 ++++++++++ .../calcite/test/SqlToRelConverterTest.java | 17 +++++++- .../java/org/apache/calcite/util/UtilTest.java | 31 ++++++++++++++ .../calcite/test/SqlToRelConverterTest.xml | 14 ++++++- core/src/test/resources/sql/sort.iq | 21 ++++++++++ 12 files changed, 214 insertions(+), 22 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMergeJoinRule.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMergeJoinRule.java b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMergeJoinRule.java index 222111c..d4748ef 100644 --- a/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMergeJoinRule.java +++ b/core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableMergeJoinRule.java @@ -71,8 +71,7 @@ class EnumerableMergeJoinRule extends ConverterRule { final List<RelFieldCollation> fieldCollations = Lists.newArrayList(); for (int key : info.keys().get(ord.i)) { fieldCollations.add( - new RelFieldCollation(key, - RelFieldCollation.Direction.ASCENDING, + new RelFieldCollation(key, RelFieldCollation.Direction.ASCENDING, RelFieldCollation.NullDirection.LAST)); } final RelCollation collation = RelCollations.of(fieldCollations); http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/rel/RelCollationImpl.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/RelCollationImpl.java b/core/src/main/java/org/apache/calcite/rel/RelCollationImpl.java index df4fcbc..e27046a 100644 --- a/core/src/main/java/org/apache/calcite/rel/RelCollationImpl.java +++ b/core/src/main/java/org/apache/calcite/rel/RelCollationImpl.java @@ -24,6 +24,7 @@ import org.apache.calcite.rel.type.RelDataType; import org.apache.calcite.runtime.Utilities; import org.apache.calcite.util.Util; +import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.UnmodifiableIterator; @@ -51,6 +52,9 @@ public class RelCollationImpl implements RelCollation { protected RelCollationImpl(ImmutableList<RelFieldCollation> fieldCollations) { this.fieldCollations = fieldCollations; + Preconditions.checkArgument( + Util.isDistinct(RelCollations.ordinals(fieldCollations)), + "fields must be distinct"); } @Deprecated // to be removed before 2.0 http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/rel/RelCollations.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/rel/RelCollations.java b/core/src/main/java/org/apache/calcite/rel/RelCollations.java index 1b8d1a0..fecf514 100644 --- a/core/src/main/java/org/apache/calcite/rel/RelCollations.java +++ b/core/src/main/java/org/apache/calcite/rel/RelCollations.java @@ -18,13 +18,16 @@ package org.apache.calcite.rel; import org.apache.calcite.rel.type.RelDataType; import org.apache.calcite.util.ImmutableIntList; +import org.apache.calcite.util.Util; import com.google.common.base.Function; import com.google.common.collect.ImmutableList; import com.google.common.collect.Lists; +import java.util.HashSet; import java.util.Iterator; import java.util.List; +import java.util.Set; /** * Utilities concerning {@link org.apache.calcite.rel.RelCollation} @@ -56,11 +59,23 @@ public class RelCollations { private RelCollations() {} public static RelCollation of(RelFieldCollation... fieldCollations) { - return new RelCollationImpl(ImmutableList.copyOf(fieldCollations)); + return of(ImmutableList.copyOf(fieldCollations)); } public static RelCollation of(List<RelFieldCollation> fieldCollations) { - return new RelCollationImpl(ImmutableList.copyOf(fieldCollations)); + if (Util.isDistinct(ordinals(fieldCollations))) { + return new RelCollationImpl(ImmutableList.copyOf(fieldCollations)); + } + // Remove field collations whose field has already been seen + final ImmutableList.Builder<RelFieldCollation> builder = + ImmutableList.builder(); + final Set<Integer> set = new HashSet<>(); + for (RelFieldCollation fieldCollation : fieldCollations) { + if (set.add(fieldCollation.getFieldIndex())) { + builder.add(fieldCollation); + } + } + return new RelCollationImpl(builder.build()); } /** @@ -110,7 +125,13 @@ public class RelCollations { /** Returns the indexes of the field collations in a given collation. */ public static List<Integer> ordinals(RelCollation collation) { - return Lists.transform(collation.getFieldCollations(), + return ordinals(collation.getFieldCollations()); + } + + /** Returns the indexes of the fields in a list of field collations. */ + public static List<Integer> ordinals( + List<RelFieldCollation> fieldCollations) { + return Lists.transform(fieldCollations, new Function<RelFieldCollation, Integer>() { public Integer apply(RelFieldCollation input) { return input.getFieldIndex(); @@ -127,6 +148,11 @@ public class RelCollations { */ public static boolean contains(RelCollation collation, Iterable<Integer> keys) { + return contains(collation, Util.distinctList(keys)); + } + + private static boolean contains(RelCollation collation, + List<Integer> keys) { final int n = collation.getFieldCollations().size(); final Iterator<Integer> iterator = keys.iterator(); for (int i = 0; i < n; i++) { @@ -146,8 +172,9 @@ public class RelCollations { * is sorted on the given list of keys. */ public static boolean contains(List<RelCollation> collations, ImmutableIntList keys) { + final List<Integer> distinctKeys = Util.distinctList(keys); for (RelCollation collation : collations) { - if (contains(collation, keys)) { + if (contains(collation, distinctKeys)) { return true; } } http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java index 80f9145..cc6d815 100644 --- a/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java +++ b/core/src/main/java/org/apache/calcite/sql2rel/SqlToRelConverter.java @@ -2939,10 +2939,7 @@ public class SqlToRelConverter { } for (SqlNode orderItem : orderList) { collationList.add( - convertOrderItem( - select, - orderItem, - extraOrderExprs, + convertOrderItem(select, orderItem, extraOrderExprs, RelFieldCollation.Direction.ASCENDING, RelFieldCollation.NullDirection.UNSPECIFIED)); } http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/tools/RelBuilder.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java index 0b871f9..b4340f8 100644 --- a/core/src/main/java/org/apache/calcite/tools/RelBuilder.java +++ b/core/src/main/java/org/apache/calcite/tools/RelBuilder.java @@ -1708,9 +1708,13 @@ public class RelBuilder { final List<RexNode> originalExtraNodes = fields(); final List<RexNode> extraNodes = new ArrayList<>(originalExtraNodes); for (RexNode node : nodes) { - fieldCollations.add( + final RelFieldCollation collation = collation(node, RelFieldCollation.Direction.ASCENDING, null, - extraNodes)); + extraNodes); + if (!RelCollations.ordinals(fieldCollations) + .contains(collation.getFieldIndex())) { + fieldCollations.add(collation); + } } final RexNode offsetNode = offset <= 0 ? null : literal(offset); final RexNode fetchNode = fetch < 0 ? null : literal(fetch); http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/main/java/org/apache/calcite/util/Util.java ---------------------------------------------------------------------- diff --git a/core/src/main/java/org/apache/calcite/util/Util.java b/core/src/main/java/org/apache/calcite/util/Util.java index ae9286f..201fe2b 100644 --- a/core/src/main/java/org/apache/calcite/util/Util.java +++ b/core/src/main/java/org/apache/calcite/util/Util.java @@ -38,6 +38,7 @@ import com.google.common.cache.LoadingCache; import com.google.common.collect.Collections2; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; +import com.google.common.collect.Sets; import org.slf4j.Logger; @@ -84,6 +85,7 @@ import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.LinkedHashMap; +import java.util.LinkedHashSet; import java.util.List; import java.util.Locale; import java.util.Map; @@ -2003,6 +2005,38 @@ public class Util { return -1; } + /** Converts a list into a list with unique elements. + * + * <p>The order is preserved; the second and subsequent occurrences are + * removed. + * + * <p>If the list is already unique it is returned unchanged. */ + public static <E> List<E> distinctList(List<E> list) { + if (isDistinct(list)) { + return list; + } + return ImmutableList.copyOf(new LinkedHashSet<>(list)); + } + + /** Converts an iterable into a list with unique elements. + * + * <p>The order is preserved; the second and subsequent occurrences are + * removed. + * + * <p>If {@code iterable} is a unique list it is returned unchanged. */ + public static <E> List<E> distinctList(Iterable<E> keys) { + if (keys instanceof Set) { + return ImmutableList.copyOf(keys); + } + if (keys instanceof List) { + @SuppressWarnings("unchecked") final List<E> list = (List) keys; + if (isDistinct(list)) { + return list; + } + } + return ImmutableList.copyOf(Sets.newLinkedHashSet(keys)); + } + /** Returns whether two collections have any elements in common. */ public static <E> boolean intersects(Collection<E> c0, Collection<E> c1) { for (E e : c1) { http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/java/org/apache/calcite/rel/RelCollationTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/rel/RelCollationTest.java b/core/src/test/java/org/apache/calcite/rel/RelCollationTest.java index 5486e42..84c816b 100644 --- a/core/src/test/java/org/apache/calcite/rel/RelCollationTest.java +++ b/core/src/test/java/org/apache/calcite/rel/RelCollationTest.java @@ -32,21 +32,48 @@ import static org.junit.Assert.assertThat; */ public class RelCollationTest { /** Unit test for {@link RelCollations#contains}. */ + @SuppressWarnings("ArraysAsListWithZeroOrOneArgument") @Test public void testCollationContains() { - final RelCollation collation = + final RelCollation collation21 = RelCollations.of( new RelFieldCollation(2, RelFieldCollation.Direction.ASCENDING), new RelFieldCollation(1, RelFieldCollation.Direction.DESCENDING)); - assertThat(RelCollations.contains(collation, Arrays.asList(2)), is(true)); - assertThat(RelCollations.contains(collation, Arrays.asList(1)), is(false)); - assertThat(RelCollations.contains(collation, Arrays.asList(0)), is(false)); - assertThat(RelCollations.contains(collation, Arrays.asList(2, 1)), + assertThat(RelCollations.contains(collation21, Arrays.asList(2)), is(true)); + assertThat(RelCollations.contains(collation21, Arrays.asList(1)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.asList(0)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 1)), + is(true)); + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 0)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 1, 3)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.<Integer>asList()), + is(true)); + + // if there are duplicates in keys, later occurrences are ignored + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 1, 2)), + is(true)); + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 1, 1)), + is(true)); + assertThat(RelCollations.contains(collation21, Arrays.asList(1, 2, 1)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.asList(1, 1)), + is(false)); + assertThat(RelCollations.contains(collation21, Arrays.asList(2, 2)), + is(true)); + + final RelCollation collation1 = + RelCollations.of( + new RelFieldCollation(1, RelFieldCollation.Direction.DESCENDING)); + assertThat(RelCollations.contains(collation1, Arrays.asList(1, 1)), is(true)); - assertThat(RelCollations.contains(collation, Arrays.asList(2, 0)), + assertThat(RelCollations.contains(collation1, Arrays.asList(2, 2)), is(false)); - assertThat(RelCollations.contains(collation, Arrays.asList(2, 1, 3)), + assertThat(RelCollations.contains(collation1, Arrays.asList(1, 2, 1)), is(false)); - assertThat(RelCollations.contains(collation, Arrays.<Integer>asList()), + assertThat(RelCollations.contains(collation1, Arrays.<Integer>asList()), is(true)); } http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java index 115f9ff..ab6ea1e 100644 --- a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java +++ b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java @@ -1672,6 +1672,27 @@ public class RelBuilderTest { assertThat(str(root), is(expected)); } + @Test public void testSortDuplicate() { + // Equivalent SQL: + // SELECT * + // FROM emp + // ORDER BY empno DESC, deptno, empno ASC, hiredate + // + // The sort key "empno ASC" is unnecessary and is ignored. + final RelBuilder builder = RelBuilder.create(config().build()); + final RelNode root = + builder.scan("EMP") + .sort(builder.desc(builder.field("EMPNO")), + builder.field("DEPTNO"), + builder.field("EMPNO"), + builder.field("HIREDATE")) + .build(); + final String expected = "LogicalSort(sort0=[$0], sort1=[$7], sort2=[$4], " + + "dir0=[DESC], dir1=[ASC], dir2=[ASC])\n" + + " LogicalTableScan(table=[[scott, EMP]])\n"; + assertThat(str(root), is(expected)); + } + @Test public void testSortByExpression() { // Equivalent SQL: // SELECT * http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java b/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java index 6c3651a..d9eb8c5 100644 --- a/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java +++ b/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java @@ -541,6 +541,21 @@ public class SqlToRelConverterTest extends SqlToRelTestBase { @Test public void testOrder() { final String sql = "select empno from emp order by empno"; sql(sql).ok(); + + // duplicate field is dropped, so plan is same + final String sql2 = "select empno from emp order by empno, empno asc"; + sql(sql2).ok(); + + // ditto + final String sql3 = "select empno from emp order by empno, empno desc"; + sql(sql3).ok(); + } + + /** Tests that if a column occurs twice in ORDER BY, only the first key is + * kept. */ + @Test public void testOrderBasedRepeatFields() { + final String sql = "select empno from emp order by empno DESC, empno ASC"; + sql(sql).ok(); } @Test public void testOrderDescNullsLast() { @@ -632,7 +647,7 @@ public class SqlToRelConverterTest extends SqlToRelTestBase { @Test public void testOrderBySameExpr() { final String sql = "select empno from emp, dept\n" - + "order by sal + empno desc, sal * empno, sal + empno"; + + "order by sal + empno desc, sal * empno, sal + empno desc"; sql(sql).ok(); } http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/java/org/apache/calcite/util/UtilTest.java ---------------------------------------------------------------------- diff --git a/core/src/test/java/org/apache/calcite/util/UtilTest.java b/core/src/test/java/org/apache/calcite/util/UtilTest.java index 1fe2d22..dc3b6f8 100644 --- a/core/src/test/java/org/apache/calcite/util/UtilTest.java +++ b/core/src/test/java/org/apache/calcite/util/UtilTest.java @@ -59,12 +59,14 @@ import java.text.MessageFormat; import java.util.ArrayList; import java.util.Arrays; import java.util.BitSet; +import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashMap; +import java.util.LinkedHashSet; import java.util.List; import java.util.Locale; import java.util.Map; @@ -1459,6 +1461,35 @@ public class UtilTest { } } + /** Unit test for {@link Util#distinctList(List)} + * and {@link Util#distinctList(Iterable)}. */ + @Test public void testDistinctList() { + assertThat(Util.distinctList(Arrays.asList(1, 2)), is(Arrays.asList(1, 2))); + assertThat(Util.distinctList(Arrays.asList(1, 2, 1)), + is(Arrays.asList(1, 2))); + try { + List<Object> o = Util.distinctList(null); + fail("expected exception, got " + o); + } catch (NullPointerException ignore) { + } + final List<Integer> empty = ImmutableList.of(); + assertThat(Util.distinctList(empty), sameInstance(empty)); + final Iterable<Integer> emptyIterable = empty; + assertThat(Util.distinctList(emptyIterable), sameInstance(emptyIterable)); + final List<Integer> empty2 = ImmutableList.of(); + assertThat(Util.distinctList(empty2), sameInstance(empty2)); + final List<String> abc = ImmutableList.of("a", "b", "c"); + assertThat(Util.distinctList(abc), sameInstance(abc)); + final List<String> a = ImmutableList.of("a"); + assertThat(Util.distinctList(a), sameInstance(a)); + final List<String> cbca = ImmutableList.of("c", "b", "c", "a"); + assertThat(Util.distinctList(cbca), not(sameInstance(cbca))); + assertThat(Util.distinctList(cbca), is(Arrays.asList("c", "b", "a"))); + final Collection<String> cbcaC = new LinkedHashSet<>(cbca); + assertThat(Util.distinctList(cbcaC), not(sameInstance(cbca))); + assertThat(Util.distinctList(cbcaC), is(Arrays.asList("c", "b", "a"))); + } + /** Unit test for {@link Utilities#hashCode(double)}. */ @Test public void testHash() { checkHash(0d); http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml ---------------------------------------------------------------------- diff --git a/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml b/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml index de4a0c1..abce49c 100644 --- a/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml +++ b/core/src/test/resources/org/apache/calcite/test/SqlToRelConverterTest.xml @@ -902,6 +902,18 @@ LogicalSort(sort0=[$0], dir0=[DESC-nulls-last]) ]]> </Resource> </TestCase> + <TestCase name="testOrderBasedRepeatFields"> + <Resource name="sql"> + <![CDATA[select empno from emp order by empno DESC, empno ASC]]> + </Resource> + <Resource name="plan"> + <![CDATA[ +LogicalSort(sort0=[$0], dir0=[DESC]) + LogicalProject(EMPNO=[$0]) + LogicalTableScan(table=[[CATALOG, SALES, EMP]]) +]]> + </Resource> + </TestCase> <TestCase name="testOrderByAlias"> <Resource name="sql"> <![CDATA[select empno + 1 as x, empno - 2 as y from emp order by y]]> @@ -1086,7 +1098,7 @@ order by sal + empno desc, sal * empno, sal + empno]]> <Resource name="plan"> <![CDATA[ LogicalProject(EMPNO=[$0]) - LogicalSort(sort0=[$1], sort1=[$2], sort2=[$1], dir0=[DESC], dir1=[ASC], dir2=[ASC]) + LogicalSort(sort0=[$1], sort1=[$2], dir0=[DESC], dir1=[ASC]) LogicalProject(EMPNO=[$0], EXPR$1=[+($5, $0)], EXPR$2=[*($5, $0)]) LogicalJoin(condition=[true], joinType=[inner]) LogicalTableScan(table=[[CATALOG, SALES, EMP]]) http://git-wip-us.apache.org/repos/asf/calcite/blob/01ee7235/core/src/test/resources/sql/sort.iq ---------------------------------------------------------------------- diff --git a/core/src/test/resources/sql/sort.iq b/core/src/test/resources/sql/sort.iq index 417fc96..33e2875 100644 --- a/core/src/test/resources/sql/sort.iq +++ b/core/src/test/resources/sql/sort.iq @@ -117,6 +117,27 @@ order by "florist", 2; !ok +!use scott + +# [CALCITE-2102] Ignore duplicate ORDER BY keys +select * +from "scott".DEPT +order by deptno desc, dname, deptno; ++--------+------------+----------+ +| DEPTNO | DNAME | LOC | ++--------+------------+----------+ +| 40 | OPERATIONS | BOSTON | +| 30 | SALES | CHICAGO | +| 20 | RESEARCH | DALLAS | +| 10 | ACCOUNTING | NEW YORK | ++--------+------------+----------+ +(4 rows) + +!ok +EnumerableSort(sort0=[$0], sort1=[$1], dir0=[DESC], dir1=[ASC]) + EnumerableTableScan(table=[[scott, DEPT]]) +!plan + !use post # [CALCITE-603] WITH ... ORDER BY cannot find table
