This is an automated email from the ASF dual-hosted git repository.
jhyde pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/main by this push:
new 7b9660f150 [CALCITE-6024] A more efficient implementation of
SqlOperatorTable, backed by an immutable multi-map keyed by upper-case operator
name
7b9660f150 is described below
commit 7b9660f150e66c544ce8df47015978b39f40e7e4
Author: Julian Hyde <[email protected]>
AuthorDate: Sat Sep 23 15:16:35 2023 -0700
[CALCITE-6024] A more efficient implementation of SqlOperatorTable, backed
by an immutable multi-map keyed by upper-case operator name
ReflectiveSqlOperatorTable and ListSqlOperatorTable now have
a common base class, the new
class SqlOperatorTables.IndexedSqlOperatorTable,
which stores operators in a multi-map keyed by their
upper-case name. Because it is a multi-map it is OK if there
are several operators with the same name, same name an
different syntax, or the same name with different case. The
map is efficient because there are unlikely to be very many
such operators.
The multi-map is immutable. You can still add an operator to
a ListSqlOperatorTable, but it will rebuild the whole
multi-map, then assign the new map to the field, and so is
not very efficient. The 'register(SqlOperator)' method is now
deprecated, to remind people that tables are better created
in entirety, rather than incrementally.
Previously there were two maps, whose keys were case-sensitive
and case-insensitive names; the keys also inclued the syntax
of the operator. Now the syntax is filtered on retrieval,
which makes sense because the syntax of the call to an
operator does not precisely match the syntax of the operator
(e.g. I can call CURRENT_TIMESTAMP with no parentheses, with
empty parentheses, or with parentheses containing precision).
Different subclasses have slightly different policies for
matching syntax.
Singleton instances of SqlStdOperatorTable and
OracleSqlOperatorTable are now held in a memoizing supplier,
which is simpler than the prefious two-phase initialization.
Close apache/calcite#3483
---
.../apache/calcite/rel/externalize/RelJson.java | 2 +-
.../calcite/sql/fun/OracleSqlOperatorTable.java | 23 ++--
.../calcite/sql/fun/SqlStdOperatorTable.java | 28 +++--
.../calcite/sql/util/ListSqlOperatorTable.java | 55 +++++-----
.../sql/util/ReflectiveSqlOperatorTable.java | 122 +++++++--------------
.../apache/calcite/sql/util/SqlOperatorTables.java | 59 +++++++++-
6 files changed, 149 insertions(+), 140 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
b/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
index e128002849..e915917c91 100644
--- a/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
+++ b/core/src/main/java/org/apache/calcite/rel/externalize/RelJson.java
@@ -993,7 +993,7 @@ public class RelJson {
SqlSyntax sqlSyntax = SqlSyntax.valueOf(syntax);
List<SqlOperator> operators = new ArrayList<>();
operatorTable.lookupOperatorOverloads(
- new SqlIdentifier(name, new SqlParserPos(0, 0)),
+ new SqlIdentifier(name, SqlParserPos.ZERO),
null,
sqlSyntax,
operators,
diff --git
a/core/src/main/java/org/apache/calcite/sql/fun/OracleSqlOperatorTable.java
b/core/src/main/java/org/apache/calcite/sql/fun/OracleSqlOperatorTable.java
index dcd18608d5..d6f85a84c4 100644
--- a/core/src/main/java/org/apache/calcite/sql/fun/OracleSqlOperatorTable.java
+++ b/core/src/main/java/org/apache/calcite/sql/fun/OracleSqlOperatorTable.java
@@ -19,7 +19,9 @@ package org.apache.calcite.sql.fun;
import org.apache.calcite.sql.SqlFunction;
import org.apache.calcite.sql.util.ReflectiveSqlOperatorTable;
-import org.checkerframework.checker.nullness.qual.Nullable;
+import com.google.common.base.Suppliers;
+
+import java.util.function.Supplier;
/**
* Operator table that contains only Oracle-specific functions and operators.
@@ -33,9 +35,11 @@ public class OracleSqlOperatorTable extends
ReflectiveSqlOperatorTable {
//~ Static fields/initializers ---------------------------------------------
/**
- * The table of contains Oracle-specific operators.
+ * The table of Oracle-specific operators.
*/
- private static @Nullable OracleSqlOperatorTable instance;
+ private static final Supplier<OracleSqlOperatorTable> INSTANCE =
+ Suppliers.memoize(() ->
+ (OracleSqlOperatorTable) new OracleSqlOperatorTable().init());
@Deprecated // to be removed before 2.0
public static final SqlFunction DECODE = SqlLibraryOperators.DECODE;
@@ -64,16 +68,7 @@ public class OracleSqlOperatorTable extends
ReflectiveSqlOperatorTable {
/**
* Returns the Oracle operator table, creating it if necessary.
*/
- public static synchronized OracleSqlOperatorTable instance() {
- OracleSqlOperatorTable instance = OracleSqlOperatorTable.instance;
- if (instance == null) {
- // Creates and initializes the standard operator table.
- // Uses two-phase construction, because we can't initialize the
- // table until the constructor of the sub-class has completed.
- instance = new OracleSqlOperatorTable();
- instance.init();
- OracleSqlOperatorTable.instance = instance;
- }
- return instance;
+ public static OracleSqlOperatorTable instance() {
+ return INSTANCE.get();
}
}
diff --git
a/core/src/main/java/org/apache/calcite/sql/fun/SqlStdOperatorTable.java
b/core/src/main/java/org/apache/calcite/sql/fun/SqlStdOperatorTable.java
index 530368d278..e6ee9734e0 100644
--- a/core/src/main/java/org/apache/calcite/sql/fun/SqlStdOperatorTable.java
+++ b/core/src/main/java/org/apache/calcite/sql/fun/SqlStdOperatorTable.java
@@ -75,13 +75,15 @@ import org.apache.calcite.util.Litmus;
import org.apache.calcite.util.Optionality;
import org.apache.calcite.util.Pair;
+import com.google.common.base.Suppliers;
import com.google.common.collect.ImmutableList;
-import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.util.List;
import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
import static org.apache.calcite.linq4j.Nullness.castNonNull;
@@ -98,7 +100,9 @@ public class SqlStdOperatorTable extends
ReflectiveSqlOperatorTable {
/**
* The standard operator table.
*/
- private static @MonotonicNonNull SqlStdOperatorTable instance;
+ private static final Supplier<SqlStdOperatorTable> INSTANCE =
+ Suppliers.memoize(() ->
+ (SqlStdOperatorTable) new SqlStdOperatorTable().init());
//-------------------------------------------------------------
// SET OPERATORS
@@ -1364,6 +1368,7 @@ public class SqlStdOperatorTable extends
ReflectiveSqlOperatorTable {
/**
* The <code>UNNEST WITH ORDINALITY</code> operator.
*/
+ @LibraryOperator(libraries = {}) // do not include in index
public static final SqlUnnestOperator UNNEST_WITH_ORDINALITY =
new SqlUnnestOperator(true);
@@ -2540,15 +2545,16 @@ public class SqlStdOperatorTable extends
ReflectiveSqlOperatorTable {
/**
* Returns the standard operator table, creating it if necessary.
*/
- public static synchronized SqlStdOperatorTable instance() {
- if (instance == null) {
- // Creates and initializes the standard operator table.
- // Uses two-phase construction, because we can't initialize the
- // table until the constructor of the sub-class has completed.
- instance = new SqlStdOperatorTable();
- instance.init();
- }
- return instance;
+ public static SqlStdOperatorTable instance() {
+ return INSTANCE.get();
+ }
+
+ @Override protected void lookUpOperators(String name,
+ boolean caseSensitive, Consumer<SqlOperator> consumer) {
+ // Only UDFs are looked up using case-sensitive search.
+ // Always look up built-in operators case-insensitively. Even in sessions
+ // with unquotedCasing=UNCHANGED and caseSensitive=true.
+ super.lookUpOperators(name, false, consumer);
}
/** Returns the group function for which a given kind is an auxiliary
diff --git
a/core/src/main/java/org/apache/calcite/sql/util/ListSqlOperatorTable.java
b/core/src/main/java/org/apache/calcite/sql/util/ListSqlOperatorTable.java
index 3a6b29023b..05229e4eb5 100644
--- a/core/src/main/java/org/apache/calcite/sql/util/ListSqlOperatorTable.java
+++ b/core/src/main/java/org/apache/calcite/sql/util/ListSqlOperatorTable.java
@@ -16,6 +16,7 @@
*/
package org.apache.calcite.sql.util;
+import org.apache.calcite.runtime.ConsList;
import org.apache.calcite.sql.SqlFunction;
import org.apache.calcite.sql.SqlFunctionCategory;
import org.apache.calcite.sql.SqlIdentifier;
@@ -24,19 +25,19 @@ import org.apache.calcite.sql.SqlOperatorTable;
import org.apache.calcite.sql.SqlSyntax;
import org.apache.calcite.sql.validate.SqlNameMatcher;
+import com.google.common.collect.ImmutableSet;
+
import org.checkerframework.checker.nullness.qual.Nullable;
-import java.util.ArrayList;
import java.util.List;
/**
* Implementation of the {@link SqlOperatorTable} interface by using a list of
* {@link SqlOperator operators}.
*/
-public class ListSqlOperatorTable implements SqlOperatorTable {
- //~ Instance fields --------------------------------------------------------
-
- private final List<SqlOperator> operatorList;
+public class ListSqlOperatorTable
+ extends SqlOperatorTables.IndexedSqlOperatorTable
+ implements SqlOperatorTable {
//~ Constructors -----------------------------------------------------------
@@ -46,7 +47,7 @@ public class ListSqlOperatorTable implements SqlOperatorTable
{
* table. */
@Deprecated // to be removed before 2.0
public ListSqlOperatorTable() {
- this(new ArrayList<>(), false);
+ this(ImmutableSet.of());
}
/** Creates a mutable ListSqlOperatorTable backed by a given list.
@@ -55,12 +56,12 @@ public class ListSqlOperatorTable implements
SqlOperatorTable {
* table. */
@Deprecated // to be removed before 2.0
public ListSqlOperatorTable(List<SqlOperator> operatorList) {
- this(operatorList, false);
+ this((Iterable<SqlOperator>) operatorList);
}
// internal constructor
- ListSqlOperatorTable(List<SqlOperator> operatorList, boolean ignored) {
- this.operatorList = operatorList;
+ ListSqlOperatorTable(Iterable<? extends SqlOperator> operatorList) {
+ super(operatorList);
}
//~ Methods ----------------------------------------------------------------
@@ -71,7 +72,8 @@ public class ListSqlOperatorTable implements SqlOperatorTable
{
* table. */
@Deprecated // to be removed before 2.0
public void add(SqlOperator op) {
- operatorList.add(op);
+ // Rebuild the immutable collections with their current contents plus one.
+ setOperators(buildIndex(ConsList.of(op, getOperatorList())));
}
@Override public void lookupOperatorOverloads(SqlIdentifier opName,
@@ -79,25 +81,26 @@ public class ListSqlOperatorTable implements
SqlOperatorTable {
SqlSyntax syntax,
List<SqlOperator> operatorList,
SqlNameMatcher nameMatcher) {
- for (SqlOperator op : this.operatorList) {
- if (!opName.isSimple()
- || !nameMatcher.matches(op.getName(), opName.getSimple())) {
- continue;
+ if (!opName.isSimple()) {
+ return;
+ }
+ final String simpleName = opName.getSimple();
+ lookUpOperators(simpleName, nameMatcher.isCaseSensitive(), op -> {
+ if (op.getSyntax() != syntax
+ && op.getSyntax().family != syntax.family) {
+ // Allow retrieval on exact syntax or family; for example,
+ // CURRENT_DATETIME has FUNCTION_ID syntax but can also be called with
+ // both FUNCTION_ID and FUNCTION syntax (e.g. SELECT CURRENT_DATETIME,
+ // CURRENT_DATETIME('UTC')).
+ return;
}
if (category != null
&& category != category(op)
&& !category.isUserDefinedNotSpecificFunction()) {
- continue;
- }
- if (op.getSyntax() == syntax) {
- operatorList.add(op);
- } else if (syntax == SqlSyntax.FUNCTION
- && op instanceof SqlFunction) {
- // this special case is needed for operators like CAST,
- // which are treated as functions but have special syntax
- operatorList.add(op);
+ return;
}
- }
+ operatorList.add(op);
+ });
}
protected static SqlFunctionCategory category(SqlOperator operator) {
@@ -107,8 +110,4 @@ public class ListSqlOperatorTable implements
SqlOperatorTable {
return SqlFunctionCategory.SYSTEM;
}
}
-
- @Override public List<SqlOperator> getOperatorList() {
- return operatorList;
- }
}
diff --git
a/core/src/main/java/org/apache/calcite/sql/util/ReflectiveSqlOperatorTable.java
b/core/src/main/java/org/apache/calcite/sql/util/ReflectiveSqlOperatorTable.java
index aaf33c6582..545afc73ae 100644
---
a/core/src/main/java/org/apache/calcite/sql/util/ReflectiveSqlOperatorTable.java
+++
b/core/src/main/java/org/apache/calcite/sql/util/ReflectiveSqlOperatorTable.java
@@ -16,46 +16,44 @@
*/
package org.apache.calcite.sql.util;
+import org.apache.calcite.runtime.ConsList;
import org.apache.calcite.sql.SqlFunction;
import org.apache.calcite.sql.SqlFunctionCategory;
import org.apache.calcite.sql.SqlIdentifier;
import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.sql.SqlOperatorTable;
import org.apache.calcite.sql.SqlSyntax;
-import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.fun.LibraryOperator;
+import org.apache.calcite.sql.fun.SqlLibrary;
import org.apache.calcite.sql.validate.SqlNameMatcher;
-import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
-import com.google.common.collect.HashMultimap;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Multimap;
import org.checkerframework.checker.nullness.qual.Nullable;
import java.lang.reflect.Field;
-import java.util.Collection;
+import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
-import java.util.Locale;
/**
* ReflectiveSqlOperatorTable implements the {@link SqlOperatorTable} interface
* by reflecting the public fields of a subclass.
*/
-public abstract class ReflectiveSqlOperatorTable implements SqlOperatorTable {
+public abstract class ReflectiveSqlOperatorTable
+ extends SqlOperatorTables.IndexedSqlOperatorTable
+ implements SqlOperatorTable {
public static final String IS_NAME = "INFORMATION_SCHEMA";
//~ Instance fields --------------------------------------------------------
- private final Multimap<CaseSensitiveKey, SqlOperator> caseSensitiveOperators
=
- HashMultimap.create();
-
- private final Multimap<CaseInsensitiveKey, SqlOperator>
caseInsensitiveOperators =
- HashMultimap.create();
-
//~ Constructors -----------------------------------------------------------
protected ReflectiveSqlOperatorTable() {
+ // Initialize using an empty list of operators. After construction is
+ // complete we will call init() and set the true operator list.
+ super(ImmutableList.of());
}
//~ Methods ----------------------------------------------------------------
@@ -65,29 +63,34 @@ public abstract class ReflectiveSqlOperatorTable implements
SqlOperatorTable {
* be part of the constructor, because the subclass constructor needs to
* complete first.
*/
- public final void init() {
+ public final SqlOperatorTable init() {
// Use reflection to register the expressions stored in public fields.
+ final List<SqlOperator> list = new ArrayList<>();
for (Field field : getClass().getFields()) {
try {
- if (SqlFunction.class.isAssignableFrom(field.getType())) {
- SqlFunction op = (SqlFunction) field.get(this);
- if (op != null) {
- register(op);
- }
- } else if (
- SqlOperator.class.isAssignableFrom(field.getType())) {
- SqlOperator op = (SqlOperator) field.get(this);
- if (op != null) {
- register(op);
+ final Object o = field.get(this);
+ if (o instanceof SqlOperator) {
+ // Fields do not need the LibraryOperator tag, but if they have it,
+ // we index them only if they contain STANDARD library.
+ LibraryOperator libraryOperator =
+ field.getAnnotation(LibraryOperator.class);
+ if (libraryOperator != null) {
+ if (Arrays.stream(libraryOperator.libraries())
+ .noneMatch(library -> library == SqlLibrary.STANDARD)) {
+ continue;
+ }
}
+
+ list.add((SqlOperator) o);
}
} catch (IllegalArgumentException | IllegalAccessException e) {
throw Util.throwAsRuntime(Util.causeOrSelf(e));
}
}
+ setOperators(buildIndex(list));
+ return this;
}
- // implement SqlOperatorTable
@Override public void lookupOperatorOverloads(SqlIdentifier opName,
@Nullable SqlFunctionCategory category, SqlSyntax syntax,
List<SqlOperator> operatorList, SqlNameMatcher nameMatcher) {
@@ -105,12 +108,7 @@ public abstract class ReflectiveSqlOperatorTable
implements SqlOperatorTable {
simpleName = opName.getSimple();
}
- final Collection<SqlOperator> list =
- lookUpOperators(simpleName, syntax, nameMatcher);
- if (list.isEmpty()) {
- return;
- }
- for (SqlOperator op : list) {
+ lookUpOperators(simpleName, nameMatcher.isCaseSensitive(), op -> {
if (op.getSyntax() == syntax) {
operatorList.add(op);
} else if (syntax == SqlSyntax.FUNCTION
@@ -119,7 +117,7 @@ public abstract class ReflectiveSqlOperatorTable implements
SqlOperatorTable {
// which are treated as functions but have special syntax
operatorList.add(op);
}
- }
+ });
// REVIEW jvs 1-Jan-2005: why is this extra lookup required?
// Shouldn't it be covered by search above?
@@ -127,71 +125,27 @@ public abstract class ReflectiveSqlOperatorTable
implements SqlOperatorTable {
case BINARY:
case PREFIX:
case POSTFIX:
- for (SqlOperator extra
- : lookUpOperators(simpleName, syntax, nameMatcher)) {
+ lookUpOperators(simpleName, nameMatcher.isCaseSensitive(), extra -> {
// REVIEW: should only search operators added during this method?
if (extra != null && !operatorList.contains(extra)) {
operatorList.add(extra);
}
- }
+ });
break;
default:
break;
}
}
- /**
- * Look up operators based on case-sensitiveness.
- */
- private Collection<SqlOperator> lookUpOperators(String name, SqlSyntax
syntax,
- SqlNameMatcher nameMatcher) {
- // Case sensitive only works for UDFs.
- // Always look up built-in operators case-insensitively. Even in sessions
- // with unquotedCasing=UNCHANGED and caseSensitive=true.
- if (nameMatcher.isCaseSensitive()
- && !(this instanceof SqlStdOperatorTable)) {
- return caseSensitiveOperators.get(new CaseSensitiveKey(name, syntax));
- } else {
- return caseInsensitiveOperators.get(new CaseInsensitiveKey(name,
syntax));
- }
- }
-
/**
* Registers a function or operator in the table.
+ *
+ * @deprecated This table is designed to be initialized from the fields of
+ * a class, and adding operators is not efficient
*/
+ @Deprecated
public void register(SqlOperator op) {
- // Register both for case-sensitive and case-insensitive look up.
- caseSensitiveOperators.put(new CaseSensitiveKey(op.getName(),
op.getSyntax()), op);
- caseInsensitiveOperators.put(new CaseInsensitiveKey(op.getName(),
op.getSyntax()), op);
- }
-
- @Override public List<SqlOperator> getOperatorList() {
- return ImmutableList.copyOf(caseSensitiveOperators.values());
- }
-
- /** Key for looking up operators. The name is stored in upper-case because we
- * store case-insensitively, even in a case-sensitive session. */
- private static class CaseInsensitiveKey extends Pair<String, SqlSyntax> {
- CaseInsensitiveKey(String name, SqlSyntax syntax) {
- super(name.toUpperCase(Locale.ROOT), normalize(syntax));
- }
- }
-
- /** Key for looking up operators. The name kept as what it is to look up
case-sensitively. */
- private static class CaseSensitiveKey extends Pair<String, SqlSyntax> {
- CaseSensitiveKey(String name, SqlSyntax syntax) {
- super(name, normalize(syntax));
- }
- }
-
- private static SqlSyntax normalize(SqlSyntax syntax) {
- switch (syntax) {
- case BINARY:
- case PREFIX:
- case POSTFIX:
- return syntax;
- default:
- return SqlSyntax.FUNCTION;
- }
+ // Rebuild the immutable collections with their current contents plus one.
+ setOperators(buildIndex(ConsList.of(op, getOperatorList())));
}
}
diff --git
a/core/src/main/java/org/apache/calcite/sql/util/SqlOperatorTables.java
b/core/src/main/java/org/apache/calcite/sql/util/SqlOperatorTables.java
index 26d3fe9a5a..bd1182bffd 100644
--- a/core/src/main/java/org/apache/calcite/sql/util/SqlOperatorTables.java
+++ b/core/src/main/java/org/apache/calcite/sql/util/SqlOperatorTables.java
@@ -22,9 +22,13 @@ import org.apache.calcite.sql.SqlSpatialTypeOperatorTable;
import com.google.common.base.Suppliers;
import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMultimap;
+import com.google.common.collect.Multimap;
import java.util.ArrayList;
import java.util.List;
+import java.util.Locale;
+import java.util.function.Consumer;
import java.util.function.Supplier;
/**
@@ -89,8 +93,59 @@ public class SqlOperatorTables {
* Operators cannot be added or removed after creation. */
private static class ImmutableListSqlOperatorTable
extends ListSqlOperatorTable {
- ImmutableListSqlOperatorTable(ImmutableList<SqlOperator> operatorList) {
- super(operatorList, false);
+ ImmutableListSqlOperatorTable(Iterable<? extends SqlOperator> operators) {
+ super(operators);
+ }
+ }
+
+ /** Base class for implementations of {@link SqlOperatorTable} whose list of
+ * operators rarely changes. */
+ abstract static class IndexedSqlOperatorTable implements SqlOperatorTable {
+ /** Contains all (name, operator) pairs. Effectively a sorted immutable
+ * multimap.
+ *
+ * <p>There can be several operators with the same name (case-insensitive
or
+ * case-sensitive) and these operators will lie in a contiguous range which
+ * we can find efficiently using binary search. */
+ protected ImmutableMultimap<String, SqlOperator> operators;
+
+ protected IndexedSqlOperatorTable(Iterable<? extends SqlOperator> list) {
+ operators = buildIndex(list);
+ }
+
+ @Override public List<SqlOperator> getOperatorList() {
+ return operators.values().asList();
+ }
+
+ protected void setOperators(Multimap<String, SqlOperator> operators) {
+ this.operators = ImmutableMultimap.copyOf(operators);
+ }
+
+ /** Derives a value to be assigned to {@link #operators} from a given list
+ * of operators. */
+ protected static ImmutableMultimap<String, SqlOperator> buildIndex(
+ Iterable<? extends SqlOperator> operators) {
+ final ImmutableMultimap.Builder<String, SqlOperator> map =
+ ImmutableMultimap.builder();
+ operators.forEach(op ->
+ map.put(op.getName().toUpperCase(Locale.ROOT), op));
+ return map.build();
+ }
+
+ /** Looks up operators, optionally matching case-sensitively. */
+ protected void lookUpOperators(String name,
+ boolean caseSensitive, Consumer<SqlOperator> consumer) {
+ final String upperName = name.toUpperCase(Locale.ROOT);
+ if (caseSensitive) {
+ operators.get(upperName)
+ .forEach(operator -> {
+ if (operator.getName().equals(name)) {
+ consumer.accept(operator);
+ }
+ });
+ } else {
+ operators.get(upperName).forEach(consumer);
+ }
}
}
}
