Add an example of a planner rule.
diff --git a/TUTORIAL.md b/TUTORIAL.md
index 453dabe..16053b3 100644
--- a/TUTORIAL.md
+++ b/TUTORIAL.md
@@ -183,7 +183,7 @@
<a href="https://github.com/julianhyde/optiq-csv/blob/master/src/main/java/net/hydromatic/optiq/impl/csv/CsvTable.java">CsvTable</a>.
Here is the relevant code from <code>CsvSchema</code>, overriding the
-<code><a href="http://www.hydromatic.net/optiq/apidocs/net/hydromatic/optiq/impl/java/MapSchema.html#initialTables()">initialTables</a></code>
+<code><a href="http://www.hydromatic.net/optiq/apidocs/net/hydromatic/optiq/impl/java/MapSchema.html#initialTables()">initialTables()</a></code>
method in the <code>MapSchema</code> base class.
```java
@@ -371,6 +371,157 @@
needs to specify each table and its file explicitly) but also give the author
more control (say, providing different parameters for each table).
+## Optimizing queries using planner rules
+
+The table implementations we have seen so far are fine as long as the tables
+don't contain a great deal of data. But if your customer table has, say, a
+hundred columns and a million rows, you would rather that the system did not
+retrieve all of the data for every query. You would like Optiq to negotiate
+with the adapter and find a more efficient way of accessing the data.
+
+This negotiation is a simple form of query optimization. Optiq supports query
+optimization by adding <i>planner rules</i>. Planner rules operate by
+looking for patterns in the query parse tree (for instance a project on top
+of a certain kind of table), and
+
+Planner rules are also extensible, like schemas and tables. So, if you have a
+data store that you want to access via SQL, you first define a custom table or
+schema, and then you define some rules to make the access efficient.
+
+To see this in action, let's use a planner rule to access
+a subset of columns from a CSV file. Let's run the same query against two very
+similar schemas:
+
+```sql
+sqlline> !connect jdbc:optiq:model=target/test-classes/model.json admin admin
+sqlline> explain plan for select name from emps;
++-----------------------------------------------------+
+| PLAN |
++-----------------------------------------------------+
+| EnumerableCalcRel(expr#0..9=[{inputs}], NAME=[$t1]) |
+| EnumerableTableAccessRel(table=[[SALES, EMPS]]) |
++-----------------------------------------------------+
+sqlline> !connect jdbc:optiq:model=target/test-classes/smart.json admin admin
+sqlline> explain plan for select name from emps;
++-----------------------------------------------------+
+| PLAN |
++-----------------------------------------------------+
+| EnumerableCalcRel(expr#0..9=[{inputs}], NAME=[$t1]) |
+| CsvTableScan(table=[[SALES, EMPS]]) |
++-----------------------------------------------------+
+```
+
+What causes the difference in plan? Let's follow the trail of evidence. In the
+<code>smart.json</code> model file, there is just one extra line:
+
+```json
+smart: true
+```
+
+This causes <code>CsvSchema</code> to be created with <code>smart = true</code>,
+and its <code>createTable</code> method creates instances of
+<a href="https://github.com/julianhyde/optiq-csv/blob/master/src/main/java/net/hydromatic/optiq/impl/csv/CsvSmartTable.java">CsvSmartTable</a>
+rather than a <code>CsvTable</code>.
+
+<code>CsvSmartTable</code> overrides the
+<code><a href="http://www.hydromatic.net/optiq/apidocs/net/hydromatic/optiq/TranslatableTable#toRel()">TranslatableTable.toRel()</a></code>
+method to create
+<a href="https://github.com/julianhyde/optiq-csv/blob/master/src/main/java/net/hydromatic/optiq/impl/csv/CsvTableScan.java">CsvTableScan</a>.
+Table scans are the leaves of a query operator tree.
+The usual implementation is
+<code><a href="http://www.hydromatic.net/optiq/apidocs/net/hydromatic/optiq/impl/java/JavaRules.EnumerableTableAccessRel.html">EnumerableTableAccessRel</a></code>,
+but we have created a distinctive sub-type that will cause rules to fire.
+
+Here is the rule in its entirety:
+
+```java
+public class CsvPushProjectOntoTableRule extends RelOptRule {
+ public static final CsvPushProjectOntoTableRule INSTANCE =
+ new CsvPushProjectOntoTableRule();
+
+ private CsvPushProjectOntoTableRule() {
+ super(
+ new RelOptRuleOperand(
+ ProjectRel.class,
+ new RelOptRuleOperand(
+ CsvTableScan.class)),
+ "CsvPushProjectOntoTableRule");
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ final ProjectRel project = (ProjectRel) call.getRels()[0];
+ final CsvTableScan scan = (CsvTableScan) call.getRels()[1];
+ int[] fields = getProjectFields(project.getProjectExps());
+ if (fields == null) {
+ // Project contains expressions more complex than just field references.
+ return;
+ }
+ call.transformTo(
+ new CsvTableScan(
+ scan.getCluster(),
+ scan.getTable(),
+ scan.csvTable,
+ fields));
+ }
+
+ private int[] getProjectFields(RexNode[] exps) {
+ final int[] fields = new int[exps.length];
+ for (int i = 0; i < exps.length; i++) {
+ final RexNode exp = exps[i];
+ if (exp instanceof RexInputRef) {
+ fields[i] = ((RexInputRef) exp).getIndex();
+ } else {
+ return null; // not a simple projection
+ }
+ }
+ return fields;
+ }
+}
+```
+
+The constructor declares the pattern of relational expressions that will cause
+the rule to file.
+
+The <code>onMatch</code> method generates a new relational expression and calls
+<code><a href="http://www.hydromatic.net/optiq/apidocs/org/eigenbase/relopt/RelOptRuleCall.html#transformTo(org.eigenbase.rel.RelNode)">RelOptRuleCall.transformTo()</a></code>
+to indicate that the rule has fired successfully.
+
+## The query optimization process
+
+There's a lot to say about how clever Optiq's query planner is, but we won't say
+it here. The cleverness is designed to take the burden off you, the writer of
+planner rules.
+
+First, Optiq doesn't fire rules in a prescribed order. The query optimization process
+follows many branches of a branching tree, just like a chess playing program
+examines many possible sequences of moves. If rules A and B both match a given
+section of the query operator tree, then Optiq can fire both.
+
+Second, Optiq uses cost in choosing between plans, but the cost model doesn't
+prevent rules from firing which may seem to be more expensive in the short term.
+
+Many optimizers have a linear optimization scheme. Faced with a choice between
+rule A and rule B, as above, such an optimizer needs to choose immediately. It
+might have a policy such as "apply rule A to the whole tree, then apply rule B
+to the whole tree", or apply a cost-based policy, applying the rule that
+produces the cheaper result.
+
+Optiq doesn't require such compromises.
+This makes it simple to combine various sets of rules.
+If, say you want to combine rules to recognize materialized views with rules to
+read from CSV and JDBC source systems, you just give Optiq the set of all rules
+and tell it to go at it.
+
+Optiq does use a cost model. The cost model decides which plan to ultimately use,
+and sometimes to prune the search tree to prevent the search space from
+exploding, but it never forces you to choose between rule A and rule B. This is
+important, because it avoids falling into local minima in the search space that
+are not actually optimal.
+
+Also (you guessed it) the cost model is pluggable, as are the table and query
+operator statistics it is based upon. But that can be a subject for later.
+
## JDBC adapter
The JDBC adapter maps a schema in a JDBC data source as an Optiq schema.
@@ -404,7 +555,7 @@
installation instructions</a>.)
<b>Current limitations</b>: The JDBC adapter currently only pushes
-down table scan operations; all other processing (filting, joins,
+down table scan operations; all other processing (filtering, joins,
aggregations and so forth) occurs within Optiq. Our goal is to push
down as much processing as possible to the source system, translating
syntax, data types and built-in functions as we go. If an Optiq query
diff --git a/src/main/java/net/hydromatic/optiq/impl/csv/CsvEnumerator.java b/src/main/java/net/hydromatic/optiq/impl/csv/CsvEnumerator.java
index f177b71..8e66618 100644
--- a/src/main/java/net/hydromatic/optiq/impl/csv/CsvEnumerator.java
+++ b/src/main/java/net/hydromatic/optiq/impl/csv/CsvEnumerator.java
@@ -27,10 +27,16 @@
class CsvEnumerator implements Enumerator<Object[]> {
private final CSVReader reader;
private final CsvFieldType[] fieldTypes;
+ private final int[] fields;
private Object[] current;
public CsvEnumerator(File file, CsvFieldType[] fieldTypes) {
+ this(file, fieldTypes, identityList(fieldTypes.length));
+ }
+
+ public CsvEnumerator(File file, CsvFieldType[] fieldTypes, int[] fields) {
this.fieldTypes = fieldTypes;
+ this.fields = fields;
try {
this.reader = new CSVReader(new FileReader(file));
this.reader.readNext(); // skip header row
@@ -59,9 +65,10 @@
}
private Object[] convertRow(String[] strings) {
- final Object[] objects = new Object[fieldTypes.length];
- for (int i = 0; i < fieldTypes.length; i++) {
- objects[i] = convert(fieldTypes[i], strings[i]);
+ final Object[] objects = new Object[fields.length];
+ for (int i = 0; i < fields.length; i++) {
+ int field = fields[i];
+ objects[i] = convert(fieldTypes[field], strings[field]);
}
return objects;
}
@@ -115,4 +122,15 @@
public void reset() {
throw new UnsupportedOperationException();
}
+
+ /** Returns an array of integers {0, ..., n - 1}. */
+ static int[] identityList(int n) {
+ int[] integers = new int[n];
+ for (int i = 0; i < n; i++) {
+ integers[i] = i;
+ }
+ return integers;
+ }
}
+
+// End CsvEnumerator.java
diff --git a/src/main/java/net/hydromatic/optiq/impl/csv/CsvPushProjectOntoTableRule.java b/src/main/java/net/hydromatic/optiq/impl/csv/CsvPushProjectOntoTableRule.java
new file mode 100644
index 0000000..fd559ac
--- /dev/null
+++ b/src/main/java/net/hydromatic/optiq/impl/csv/CsvPushProjectOntoTableRule.java
@@ -0,0 +1,76 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde 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 net.hydromatic.optiq.impl.csv;
+
+import org.eigenbase.rel.ProjectRel;
+import org.eigenbase.relopt.RelOptRule;
+import org.eigenbase.relopt.RelOptRuleCall;
+import org.eigenbase.relopt.RelOptRuleOperand;
+import org.eigenbase.rex.RexInputRef;
+import org.eigenbase.rex.RexNode;
+
+/**
+ * Planner rule that projects from a {@link CsvTableScan} scan just the columns
+ * needed to satisfy a projection. If the projection's expressions are trivial,
+ * the projection is removed.
+ */
+public class CsvPushProjectOntoTableRule extends RelOptRule {
+ public static final CsvPushProjectOntoTableRule INSTANCE =
+ new CsvPushProjectOntoTableRule();
+
+ private CsvPushProjectOntoTableRule() {
+ super(
+ new RelOptRuleOperand(
+ ProjectRel.class,
+ new RelOptRuleOperand(
+ CsvTableScan.class)),
+ "CsvPushProjectOntoTableRule");
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ final ProjectRel project = (ProjectRel) call.getRels()[0];
+ final CsvTableScan scan = (CsvTableScan) call.getRels()[1];
+ int[] fields = getProjectFields(project.getProjectExps());
+ if (fields == null) {
+ // Project contains expressions more complex than just field references.
+ return;
+ }
+ call.transformTo(
+ new CsvTableScan(
+ scan.getCluster(),
+ scan.getTable(),
+ scan.csvTable,
+ fields));
+ }
+
+ private int[] getProjectFields(RexNode[] exps) {
+ final int[] fields = new int[exps.length];
+ for (int i = 0; i < exps.length; i++) {
+ final RexNode exp = exps[i];
+ if (exp instanceof RexInputRef) {
+ fields[i] = ((RexInputRef) exp).getIndex();
+ } else {
+ return null; // not a simple projection
+ }
+ }
+ return fields;
+ }
+}
+
+// End CsvPushProjectOntoTableRule.java
diff --git a/src/main/java/net/hydromatic/optiq/impl/csv/CsvSmartTable.java b/src/main/java/net/hydromatic/optiq/impl/csv/CsvSmartTable.java
index b6abbee..e0ef384 100644
--- a/src/main/java/net/hydromatic/optiq/impl/csv/CsvSmartTable.java
+++ b/src/main/java/net/hydromatic/optiq/impl/csv/CsvSmartTable.java
@@ -19,7 +19,6 @@
import org.eigenbase.rel.RelNode;
import org.eigenbase.relopt.RelOptTable;
-import org.eigenbase.relopt.RelOptUtil;
import org.eigenbase.reltype.RelDataType;
import java.io.File;
@@ -40,11 +39,10 @@
RelOptTable.ToRelContext context,
RelOptTable relOptTable)
{
- return new CsvTableScan(
- context.getCluster(),
- relOptTable,
- this,
- RelOptUtil.getFieldNameList(relOptTable.getRowType()));
+ // Request all fields.
+ final int fieldCount = relOptTable.getRowType().getFieldCount();
+ final int[] fields = CsvEnumerator.identityList(fieldCount);
+ return new CsvTableScan(context.getCluster(), relOptTable, this, fields);
}
}
diff --git a/src/main/java/net/hydromatic/optiq/impl/csv/CsvTable.java b/src/main/java/net/hydromatic/optiq/impl/csv/CsvTable.java
index 213a369..aaa8101 100644
--- a/src/main/java/net/hydromatic/optiq/impl/csv/CsvTable.java
+++ b/src/main/java/net/hydromatic/optiq/impl/csv/CsvTable.java
@@ -38,8 +38,7 @@
/**
* Table based on a CSV file.
*/
-class CsvTable
- extends AbstractQueryable<Object[]>
+public class CsvTable extends AbstractQueryable<Object[]>
implements TranslatableTable<Object[]> {
private final Schema schema;
private final String tableName;
@@ -85,12 +84,10 @@
}
public Expression getExpression() {
- return Expressions.call(
- schema.getExpression(),
+ return Expressions.convert_(Expressions.call(schema.getExpression(),
"getTable",
- Expressions.<Expression>list()
- .append(Expressions.constant(tableName))
- .append(Expressions.constant(getElementType())));
+ Expressions.<Expression>list().append(Expressions.constant(tableName)).append(
+ Expressions.constant(getElementType()))), CsvTable.class);
}
public Iterator<Object[]> iterator() {
@@ -98,20 +95,30 @@
}
public Enumerator<Object[]> enumerator() {
- return new CsvEnumerator(
- file, fieldTypes.toArray(new CsvFieldType[fieldTypes.size()]));
+ return new CsvEnumerator(file,
+ fieldTypes.toArray(new CsvFieldType[fieldTypes.size()]));
+ }
+
+ /** Returns an enumerable over a given projection of the fields. */
+ public Enumerable<Object[]> project(final int[] fields) {
+ return new AbstractEnumerable<Object[]>() {
+ public Enumerator<Object[]> enumerator() {
+ return new CsvEnumerator(file,
+ fieldTypes.toArray(new CsvFieldType[fieldTypes.size()]), fields);
+ }
+ };
}
public RelNode toRel(
RelOptTable.ToRelContext context,
RelOptTable relOptTable)
{
- return new JavaRules.EnumerableTableAccessRel(
- context.getCluster(),
- context.getCluster().traitSetOf(EnumerableConvention.ARRAY),
- relOptTable,
- getExpression(),
- getElementType());
+ return new JavaRules.EnumerableTableAccessRel(
+ context.getCluster(),
+ context.getCluster().traitSetOf(EnumerableConvention.ARRAY),
+ relOptTable,
+ getExpression(),
+ getElementType());
}
/** Deduces the names and types of a table's columns by reading the first line
diff --git a/src/main/java/net/hydromatic/optiq/impl/csv/CsvTableScan.java b/src/main/java/net/hydromatic/optiq/impl/csv/CsvTableScan.java
index 73427cf..94e1073 100644
--- a/src/main/java/net/hydromatic/optiq/impl/csv/CsvTableScan.java
+++ b/src/main/java/net/hydromatic/optiq/impl/csv/CsvTableScan.java
@@ -26,7 +26,6 @@
import org.eigenbase.relopt.*;
import org.eigenbase.reltype.RelDataType;
import org.eigenbase.reltype.RelDataTypeFactory;
-import org.eigenbase.util.Pair;
import java.util.*;
@@ -37,14 +36,14 @@
*/
public class CsvTableScan extends TableAccessRelBase implements EnumerableRel {
final CsvTable csvTable;
- final List<String> fieldList;
+ final int[] fields;
final PhysType physType;
protected CsvTableScan(RelOptCluster cluster, RelOptTable table,
- CsvTable csvTable, List<String> fieldList) {
+ CsvTable csvTable, int[] fields) {
super(cluster, cluster.traitSetOf(EnumerableConvention.ARRAY), table);
this.csvTable = csvTable;
- this.fieldList = fieldList;
+ this.fields = fields;
this.physType =
PhysTypeImpl.of(
(JavaTypeFactory) cluster.getTypeFactory(),
@@ -61,28 +60,34 @@
@Override
public RelNode copy(RelTraitSet traitSet, List<RelNode> inputs) {
assert inputs.isEmpty();
- return new CsvTableScan(getCluster(), table, csvTable, fieldList);
+ return new CsvTableScan(getCluster(), table, csvTable, fields);
}
@Override
- public void explain(RelOptPlanWriter pw) {
- pw.explain(this, Collections.singletonList(
- Pair.<String, Object>of("table",
- Arrays.asList(table.getQualifiedName()))));
+ public RelOptPlanWriter explainTerms(RelOptPlanWriter pw) {
+ return super.explainTerms(pw)
+ .item("fields", Primitive.asList(fields));
}
@Override
public RelDataType deriveRowType() {
final RelDataTypeFactory.FieldInfoBuilder builder =
new RelDataTypeFactory.FieldInfoBuilder();
- for (String field : fieldList) {
- builder.add(table.getRowType().getField(field));
+ for (int field : fields) {
+ builder.add(table.getRowType().getFieldList().get(field));
}
return getCluster().getTypeFactory().createStructType(builder);
}
+ @Override
+ public void register(RelOptPlanner planner) {
+ planner.addRule(CsvPushProjectOntoTableRule.INSTANCE);
+ }
+
public BlockExpression implement(EnumerableRelImplementor implementor) {
- return Blocks.toBlock(csvTable.getExpression());
+ return Blocks.toBlock(
+ Expressions.call(csvTable.getExpression(), "project",
+ Expressions.constant(fields)));
}
}
diff --git a/src/test/java/net/hydromatic/optiq/test/CsvTest.java b/src/test/java/net/hydromatic/optiq/test/CsvTest.java
index 744ca11..b83c43b 100644
--- a/src/test/java/net/hydromatic/optiq/test/CsvTest.java
+++ b/src/test/java/net/hydromatic/optiq/test/CsvTest.java
@@ -18,6 +18,7 @@
package net.hydromatic.optiq.test;
import junit.framework.TestCase;
+import net.hydromatic.linq4j.function.Function1;
import java.io.PrintStream;
import java.sql.*;
@@ -69,14 +70,70 @@
* Reads from a table.
*/
public void testSelect() throws SQLException {
- checkSql("select * from EMPS", "model");
+ checkSql("model", "select * from EMPS");
}
public void testCustomTable() throws SQLException {
- checkSql("select * from CUSTOM_TABLE.EMPS", "model-with-custom-table");
+ checkSql("model-with-custom-table", "select * from CUSTOM_TABLE.EMPS");
}
- private void checkSql(String sql, String model) throws SQLException {
+ public void testPushDownProjectDumb() throws SQLException {
+ // rule does not fire, because we're using 'dumb' tables in simple model
+ checkSql("model", "explain plan for select * from EMPS",
+ "PLAN=EnumerableCalcRel(expr#0..9=[{inputs}], proj#0..9=[{exprs}])\n"
+ + " EnumerableTableAccessRel(table=[[SALES, EMPS]])\n"
+ + "\n");
+ }
+
+ public void testPushDownProject() throws SQLException {
+ checkSql("smart", "explain plan for select * from EMPS",
+ "PLAN=CsvTableScan(table=[[SALES, EMPS]], fields=[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]])\n"
+ + "\n");
+ }
+
+ public void testPushDownProject2() throws SQLException {
+ checkSql("smart", "explain plan for select name, empno from EMPS",
+ "PLAN=CsvTableScan(table=[[SALES, EMPS]], fields=[[1, 0]])\n"
+ + "\n");
+ // make sure that it works...
+ checkSql("smart", "select name, empno from EMPS",
+ "NAME=Fred; EMPNO=100\n"
+ + "NAME=Eric; EMPNO=110\n"
+ + "NAME=John; EMPNO=110\n"
+ + "NAME=Wilma; EMPNO=120\n"
+ + "NAME=Alice; EMPNO=130\n");
+ }
+
+ private void checkSql(String model, String sql) throws SQLException {
+ checkSql(sql, model, new Function1<ResultSet, Void>() {
+ public Void apply(ResultSet resultSet) {
+ try {
+ output(resultSet, System.out);
+ } catch (SQLException e) {
+ throw new RuntimeException(e);
+ }
+ return null;
+ }
+ });
+ }
+
+ private void checkSql(String model, String sql, final String expected)
+ throws SQLException {
+ checkSql(sql, model, new Function1<ResultSet, Void>() {
+ public Void apply(ResultSet resultSet) {
+ try {
+ String actual = CsvTest.toString(resultSet);
+ assertEquals(expected, actual);
+ } catch (SQLException e) {
+ throw new RuntimeException(e);
+ }
+ return null;
+ }
+ });
+ }
+
+ private void checkSql(String sql, String model, Function1<ResultSet, Void> fn)
+ throws SQLException {
Connection connection = null;
Statement statement = null;
try {
@@ -87,12 +144,29 @@
final ResultSet resultSet =
statement.executeQuery(
sql);
- output(resultSet, System.out);
+ fn.apply(resultSet);
} finally {
close(connection, statement);
}
}
+ private static String toString(ResultSet resultSet) throws SQLException {
+ StringBuilder buf = new StringBuilder();
+ while (resultSet.next()) {
+ int n = resultSet.getMetaData().getColumnCount();
+ String sep = "";
+ for (int i = 1; i <= n; i++) {
+ buf.append(sep)
+ .append(resultSet.getMetaData().getColumnLabel(i))
+ .append("=")
+ .append(resultSet.getObject(i));
+ sep = "; ";
+ }
+ buf.append("\n");
+ }
+ return buf.toString();
+ }
+
private void output(ResultSet resultSet, PrintStream out)
throws SQLException {
final ResultSetMetaData metaData = resultSet.getMetaData();
