tajo-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jihoon...@apache.org
Subject [2/5] tajo git commit: TAJO-838: Improve query planner to utilize index. (jihoon)
Date Thu, 08 Jan 2015 16:14:49 GMT
http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/engine/query/TestCreateIndex.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/engine/query/TestCreateIndex.java b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestCreateIndex.java
index 2a66909..83e33b7 100644
--- a/tajo-core/src/test/java/org/apache/tajo/engine/query/TestCreateIndex.java
+++ b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestCreateIndex.java
@@ -23,6 +23,7 @@ import org.apache.hadoop.fs.Path;
 import org.apache.tajo.IntegrationTest;
 import org.apache.tajo.QueryTestCaseBase;
 import org.apache.tajo.TajoConstants;
+import org.apache.tajo.catalog.IndexDesc;
 import org.apache.tajo.conf.TajoConf.ConfVars;
 import org.junit.Test;
 import org.junit.experimental.categories.Category;
@@ -38,35 +39,60 @@ public class TestCreateIndex extends QueryTestCaseBase {
     super(TajoConstants.DEFAULT_DATABASE_NAME);
   }
 
-  private static void assertIndexExist(String indexName) throws IOException {
-    Path indexPath = new Path(conf.getVar(ConfVars.WAREHOUSE_DIR), "default/" + indexName);
+  private static void assertIndexNotExist(String databaseName, String indexName) throws IOException {
+    Path indexPath = new Path(conf.getVar(ConfVars.WAREHOUSE_DIR), databaseName + "/" + indexName);
     FileSystem fs = indexPath.getFileSystem(conf);
-    assertTrue(fs.exists(indexPath));
-    assertEquals(2, fs.listStatus(indexPath).length);
-    fs.deleteOnExit(indexPath);
+    if (fs.exists(indexPath)) {
+      fs.deleteOnExit(indexPath);
+      assertFalse("Index is not deleted from the file system.", true);
+    }
   }
 
   @Test
   public final void testCreateIndex() throws Exception {
     executeQuery();
-    assertIndexExist("l_orderkey_idx");
+    assertTrue(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_idx"));
+    assertTrue(catalog.existIndexByColumnNames(getCurrentDatabase(), "lineitem", new String[]{"l_orderkey"}));
+    executeString("drop index l_orderkey_idx");
+    assertFalse(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_idx"));
+    assertIndexNotExist(getCurrentDatabase(), "l_orderkey_idx");
   }
 
   @Test
   public final void testCreateIndexOnMultiAttrs() throws Exception {
     executeQuery();
-    assertIndexExist("l_orderkey_partkey_idx");
+    assertTrue(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_partkey_idx"));
+    assertTrue(catalog.existIndexByColumnNames(getCurrentDatabase(), "lineitem", new String[]{"l_orderkey", "l_partkey"}));
+    executeString("drop index l_orderkey_partkey_idx");
+    assertFalse(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_partkey_idx"));
+    assertIndexNotExist(getCurrentDatabase(), "l_orderkey_partkey_idx");
   }
 
   @Test
   public final void testCreateIndexWithCondition() throws Exception {
     executeQuery();
-    assertIndexExist("l_orderkey_partkey_lt10_idx");
+    assertTrue(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_partkey_lt10_idx"));
+    assertTrue(catalog.existIndexByColumnNames(getCurrentDatabase(), "lineitem", new String[]{"l_orderkey", "l_partkey"}));
+    executeString("drop index l_orderkey_partkey_lt10_idx");
+    assertFalse(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_partkey_lt10_idx"));
+    assertIndexNotExist(getCurrentDatabase(), "l_orderkey_partkey_lt10_idx");
   }
 
   @Test
   public final void testCreateIndexOnExpression() throws Exception {
     executeQuery();
-    assertIndexExist("l_orderkey_100_lt10_idx");
+    assertTrue(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_100_lt10_idx"));
+    executeString("drop index l_orderkey_100_lt10_idx");
+    assertFalse(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_100_lt10_idx"));
+    assertIndexNotExist(getCurrentDatabase(), "l_orderkey_100_lt10_idx");
+  }
+
+  @Test
+  public final void testCreateIndexOnMultiExprs() throws Exception {
+    executeQuery();
+    assertTrue(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_100_l_linenumber_10_lt10_idx"));
+    executeString("drop index l_orderkey_100_l_linenumber_10_lt10_idx");
+    assertFalse(catalog.existIndexByName(getCurrentDatabase(), "l_orderkey_100_l_linenumber_10_lt10_idx"));
+    assertIndexNotExist(getCurrentDatabase(), "l_orderkey_100_l_linenumber_10_lt10_idx");
   }
 }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/engine/query/TestIndexScan.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/engine/query/TestIndexScan.java b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestIndexScan.java
new file mode 100644
index 0000000..f94a3b5
--- /dev/null
+++ b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestIndexScan.java
@@ -0,0 +1,119 @@
+/*
+ * 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.tajo.engine.query;
+
+import com.google.protobuf.ServiceException;
+import org.apache.tajo.IntegrationTest;
+import org.apache.tajo.QueryTestCaseBase;
+import org.apache.tajo.SessionVars;
+import org.apache.tajo.TajoConstants;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+import java.sql.ResultSet;
+import java.util.HashMap;
+import java.util.Map;
+
+@Category(IntegrationTest.class)
+public class TestIndexScan extends QueryTestCaseBase {
+
+  public TestIndexScan() throws ServiceException {
+    super(TajoConstants.DEFAULT_DATABASE_NAME);
+    Map<String,String> sessionVars = new HashMap<String, String>();
+    sessionVars.put(SessionVars.INDEX_ENABLED.keyname(), "true");
+    sessionVars.put(SessionVars.INDEX_SELECTIVITY_THRESHOLD.keyname(), "0.01f");
+    client.updateSessionVariables(sessionVars);
+  }
+
+  @Test
+  public final void testOnSortedNonUniqueKeys() throws Exception {
+    executeString("create index l_orderkey_idx on lineitem (l_orderkey)");
+    ResultSet res = executeString("select * from lineitem where l_orderkey = 1;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_orderkey_idx");
+  }
+
+  @Test
+  public final void testOnUnsortedTextKeys() throws Exception {
+    executeString("create index l_shipdate_idx on lineitem (l_shipdate)");
+    ResultSet res = executeString("select l_orderkey, l_shipdate, l_comment from lineitem where l_shipdate = '1997-01-28';");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_shipdate_idx");
+  }
+
+  @Test
+  public final void testOnMultipleKeys() throws Exception {
+    executeString("create index multikey_idx on lineitem (l_shipdate asc null last, l_tax desc null first, l_shipmode, l_linenumber desc null last)");
+    ResultSet res = executeString("select l_orderkey, l_shipdate, l_comment from lineitem " +
+        "where l_shipdate = '1997-01-28' and l_tax = 0.05 and l_shipmode = 'RAIL' and l_linenumber = 1;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index multikey_idx");
+  }
+
+  @Test
+  public final void testOnMultipleKeys2() throws Exception {
+    executeString("create index multikey_idx on lineitem (l_shipdate asc null last, l_tax desc null first)");
+    ResultSet res = executeString("select l_orderkey, l_shipdate, l_comment from lineitem " +
+        "where l_shipdate = '1997-01-28' and l_tax = 0.05 and l_shipmode = 'RAIL' and l_linenumber = 1;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index multikey_idx");
+  }
+
+  @Test
+  public final void testOnMultipleExprs() throws Exception {
+    executeString("create index l_orderkey_100_l_linenumber_10_idx on lineitem (l_orderkey*100-l_linenumber*10 asc null first);");
+    ResultSet res = executeString("select l_orderkey, l_linenumber from lineitem where l_orderkey*100-l_linenumber*10 = 280");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_orderkey_100_l_linenumber_10_idx");
+  }
+
+  @Test
+  public final void testWithGroupBy() throws Exception {
+    executeString("create index l_shipdate_idx on lineitem (l_shipdate)");
+    ResultSet res = executeString("select l_shipdate, count(*) from lineitem where l_shipdate = '1997-01-28' group by l_shipdate;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_shipdate_idx");
+  }
+
+  @Test
+  public final void testWithSort() throws Exception {
+    executeString("create index l_orderkey_idx on lineitem (l_orderkey)");
+    ResultSet res = executeString("select l_shipdate from lineitem where l_orderkey = 1 order by l_shipdate;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_orderkey_idx");
+  }
+
+  @Test
+  public final void testWithJoin() throws Exception {
+    executeString("create index l_orderkey_idx on lineitem (l_orderkey)");
+    executeString("create index o_orderkey_idx on orders (o_orderkey)");
+    ResultSet res = executeString("select l_shipdate, o_orderstatus from lineitem, orders where l_orderkey = o_orderkey and l_orderkey = 1 and o_orderkey = 1;");
+    assertResultSet(res);
+    cleanupQuery(res);
+    executeString("drop index l_orderkey_idx");
+    executeString("drop index o_orderkey_idx");
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/engine/query/TestTablePartitions.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/engine/query/TestTablePartitions.java b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestTablePartitions.java
index 3400752..0bfcb09 100644
--- a/tajo-core/src/test/java/org/apache/tajo/engine/query/TestTablePartitions.java
+++ b/tajo-core/src/test/java/org/apache/tajo/engine/query/TestTablePartitions.java
@@ -766,8 +766,8 @@ public class TestTablePartitions extends QueryTestCaseBase {
     ClientProtos.SubmitQueryResponse response = client.executeQuery("insert overwrite into " + tableName
         + " select l_orderkey, l_partkey from lineitem");
 
-    assertTrue(response.hasErrorMessage());
-    assertEquals(response.getErrorMessage(), "INSERT has smaller expressions than target columns\n");
+    assertTrue(response.getResult().hasErrorMessage());
+    assertEquals(response.getResult().getErrorMessage(), "INSERT has smaller expressions than target columns\n");
 
     res = executeFile("case14.sql");
     assertResultSet(res, "case14.result");
@@ -786,8 +786,8 @@ public class TestTablePartitions extends QueryTestCaseBase {
     ClientProtos.SubmitQueryResponse response = client.executeQuery("insert overwrite into " + tableName
         + " select l_returnflag , l_orderkey, l_partkey from lineitem");
 
-    assertTrue(response.hasErrorMessage());
-    assertEquals(response.getErrorMessage(), "INSERT has smaller expressions than target columns\n");
+    assertTrue(response.getResult().hasErrorMessage());
+    assertEquals(response.getResult().getErrorMessage(), "INSERT has smaller expressions than target columns\n");
 
     res = executeFile("case15.sql");
     assertResultSet(res, "case15.result");

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java b/tajo-core/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java
index 712243b..760cb4c 100644
--- a/tajo-core/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java
+++ b/tajo-core/src/test/java/org/apache/tajo/master/TestExecutionBlockCursor.java
@@ -80,7 +80,7 @@ public class TestExecutionBlockCursor {
 
     analyzer = new SQLAnalyzer();
     logicalPlanner = new LogicalPlanner(catalog);
-    optimizer = new LogicalOptimizer(conf);
+    optimizer = new LogicalOptimizer(conf, catalog);
 
     StorageManager sm  = StorageManager.getFileStorageManager(conf);
     dispatcher = new AsyncDispatcher();

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/master/TestGlobalPlanner.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/master/TestGlobalPlanner.java b/tajo-core/src/test/java/org/apache/tajo/master/TestGlobalPlanner.java
index d0f7cf4..e2f3417 100644
--- a/tajo-core/src/test/java/org/apache/tajo/master/TestGlobalPlanner.java
+++ b/tajo-core/src/test/java/org/apache/tajo/master/TestGlobalPlanner.java
@@ -115,7 +115,7 @@ public class TestGlobalPlanner {
 
     sqlAnalyzer = new SQLAnalyzer();
     planner = new LogicalPlanner(catalog);
-    optimizer = new LogicalOptimizer(util.getConfiguration());
+    optimizer = new LogicalOptimizer(util.getConfiguration(), catalog);
     globalPlanner = new GlobalPlanner(util.getConfiguration(), catalog);
   }
 

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/master/querymaster/TestKillQuery.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/master/querymaster/TestKillQuery.java b/tajo-core/src/test/java/org/apache/tajo/master/querymaster/TestKillQuery.java
index 8ca4cff..e728207 100644
--- a/tajo-core/src/test/java/org/apache/tajo/master/querymaster/TestKillQuery.java
+++ b/tajo-core/src/test/java/org/apache/tajo/master/querymaster/TestKillQuery.java
@@ -76,7 +76,7 @@ public class TestKillQuery {
     String query = "select l_orderkey, l_partkey from lineitem group by l_orderkey, l_partkey order by l_orderkey";
 
     LogicalPlanner planner = new LogicalPlanner(catalog);
-    LogicalOptimizer optimizer = new LogicalOptimizer(conf);
+    LogicalOptimizer optimizer = new LogicalOptimizer(conf, catalog);
     Expr expr =  analyzer.parse(query);
     LogicalPlan plan = planner.createPlan(defaultContext, expr);
 

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/java/org/apache/tajo/worker/TestRangeRetrieverHandler.java
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/java/org/apache/tajo/worker/TestRangeRetrieverHandler.java b/tajo-core/src/test/java/org/apache/tajo/worker/TestRangeRetrieverHandler.java
index 200ba31..2eecd4d 100644
--- a/tajo-core/src/test/java/org/apache/tajo/worker/TestRangeRetrieverHandler.java
+++ b/tajo-core/src/test/java/org/apache/tajo/worker/TestRangeRetrieverHandler.java
@@ -94,7 +94,7 @@ public class TestRangeRetrieverHandler {
 
     analyzer = new SQLAnalyzer();
     planner = new LogicalPlanner(catalog);
-    optimizer = new LogicalOptimizer(conf);
+    optimizer = new LogicalOptimizer(conf, catalog);
 
     schema = new Schema();
     schema.addColumn("empid", Type.INT4);

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/queries/TestCreateIndex/testCreateIndexOnMultiExprs.sql
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/queries/TestCreateIndex/testCreateIndexOnMultiExprs.sql b/tajo-core/src/test/resources/queries/TestCreateIndex/testCreateIndexOnMultiExprs.sql
new file mode 100644
index 0000000..7938005
--- /dev/null
+++ b/tajo-core/src/test/resources/queries/TestCreateIndex/testCreateIndexOnMultiExprs.sql
@@ -0,0 +1 @@
+create index l_orderkey_100_l_linenumber_10_lt10_idx on lineitem (l_orderkey*100-l_linenumber*10 asc null first) where l_orderkey*100 > 10;
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleExprs.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleExprs.result b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleExprs.result
new file mode 100644
index 0000000..bcb645d
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleExprs.result
@@ -0,0 +1,3 @@
+l_orderkey,l_linenumber
+-------------------------------
+3,2
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys.result b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys.result
new file mode 100644
index 0000000..86d468e
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys.result
@@ -0,0 +1,3 @@
+l_orderkey,l_shipdate,l_comment
+-------------------------------
+2,1997-01-28,ven requests. deposits breach a
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys2.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys2.result b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys2.result
new file mode 100644
index 0000000..86d468e
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testOnMultipleKeys2.result
@@ -0,0 +1,3 @@
+l_orderkey,l_shipdate,l_comment
+-------------------------------
+2,1997-01-28,ven requests. deposits breach a
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testOnSortedNonUniqueKeys.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testOnSortedNonUniqueKeys.result b/tajo-core/src/test/resources/results/TestIndexScan/testOnSortedNonUniqueKeys.result
new file mode 100644
index 0000000..fb8a4c2
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testOnSortedNonUniqueKeys.result
@@ -0,0 +1,4 @@
+l_orderkey,l_partkey,l_suppkey,l_linenumber,l_quantity,l_extendedprice,l_discount,l_tax,l_returnflag,l_linestatus,l_shipdate,l_commitdate,l_receiptdate,l_shipinstruct,l_shipmode,l_comment
+-------------------------------
+1,1,7706,1,17.0,21168.23,0.04,0.02,N,O,1996-03-13,1996-02-12,1996-03-22,DELIVER IN PERSON,TRUCK,egular courts above the
+1,1,7311,2,36.0,45983.16,0.09,0.06,N,O,1996-04-12,1996-02-28,1996-04-20,TAKE BACK RETURN,MAIL,ly final dependencies: slyly bold
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testOnUnsortedTextKeys.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testOnUnsortedTextKeys.result b/tajo-core/src/test/resources/results/TestIndexScan/testOnUnsortedTextKeys.result
new file mode 100644
index 0000000..86d468e
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testOnUnsortedTextKeys.result
@@ -0,0 +1,3 @@
+l_orderkey,l_shipdate,l_comment
+-------------------------------
+2,1997-01-28,ven requests. deposits breach a
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testWithGroupBy.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testWithGroupBy.result b/tajo-core/src/test/resources/results/TestIndexScan/testWithGroupBy.result
new file mode 100644
index 0000000..2d1d12e
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testWithGroupBy.result
@@ -0,0 +1,3 @@
+l_shipdate,?count
+-------------------------------
+1997-01-28,1
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testWithJoin.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testWithJoin.result b/tajo-core/src/test/resources/results/TestIndexScan/testWithJoin.result
new file mode 100644
index 0000000..d119969
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testWithJoin.result
@@ -0,0 +1,4 @@
+l_shipdate,o_orderstatus
+-------------------------------
+1996-03-13,O
+1996-04-12,O
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestIndexScan/testWithSort.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestIndexScan/testWithSort.result b/tajo-core/src/test/resources/results/TestIndexScan/testWithSort.result
new file mode 100644
index 0000000..774a411
--- /dev/null
+++ b/tajo-core/src/test/resources/results/TestIndexScan/testWithSort.result
@@ -0,0 +1,4 @@
+l_shipdate
+-------------------------------
+1996-03-13
+1996-04-12
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-core/src/test/resources/results/TestTajoCli/testHelpSessionVars.result
----------------------------------------------------------------------
diff --git a/tajo-core/src/test/resources/results/TestTajoCli/testHelpSessionVars.result b/tajo-core/src/test/resources/results/TestTajoCli/testHelpSessionVars.result
index b5b7c22..90f948e 100644
--- a/tajo-core/src/test/resources/results/TestTajoCli/testHelpSessionVars.result
+++ b/tajo-core/src/test/resources/results/TestTajoCli/testHelpSessionVars.result
@@ -34,6 +34,8 @@ Available Session Variables:
 \set MAX_OUTPUT_FILE_SIZE [int value] - Maximum per-output file size (mb). 0 means infinite.
 \set NULL_CHAR [text value] - null char of text file output
 \set CODEGEN [true or false] - Runtime code generation enabled (experiment)
+\set INDEX_ENABLED [true or false] - index scan enabled
+\set INDEX_SELECTIVITY_THRESHOLD [real value] - the selectivity threshold for index scan
 \set ARITHABORT [true or false] - If true, a running query will be terminated when an overflow or divide-by-zero occurs.
 \set FETCH_ROWNUM [int value] - Sets the number of rows at a time from Master
 \set DEBUG_ENABLED [true or false] - (debug only) debug mode enabled
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/index.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/index.rst b/tajo-docs/src/main/sphinx/index.rst
index 80cd842..667f270 100644
--- a/tajo-docs/src/main/sphinx/index.rst
+++ b/tajo-docs/src/main/sphinx/index.rst
@@ -37,6 +37,7 @@ Table of Contents:
    functions
    table_management
    table_partitioning
+   index_overview
    backup_and_restore
    hcatalog_integration
    jdbc_driver   

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/index/future_work.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/index/future_work.rst b/tajo-docs/src/main/sphinx/index/future_work.rst
new file mode 100644
index 0000000..c6ec47d
--- /dev/null
+++ b/tajo-docs/src/main/sphinx/index/future_work.rst
@@ -0,0 +1,8 @@
+*************************************
+Future Works
+*************************************
+
+* Providing more index types, such as bitmap and HBase index
+* Supporting index on partitioned tables
+* Supporting the backup and restore feature
+* Cost-based query optimization by estimating the query selectivity
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/index/how_to_use.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/index/how_to_use.rst b/tajo-docs/src/main/sphinx/index/how_to_use.rst
new file mode 100644
index 0000000..82a8bc9
--- /dev/null
+++ b/tajo-docs/src/main/sphinx/index/how_to_use.rst
@@ -0,0 +1,69 @@
+*************************************
+How to use index?
+*************************************
+
+-------------------------------------
+1. Create index
+-------------------------------------
+
+The first step for utilizing index is index creation. You can create index using SQL (:doc:`/sql_language/ddl`) or Tajo API (:doc:`/tajo_client_api`). For example, you can create a BST index on the lineitem table by submitting the following SQL to Tajo.
+
+.. code-block:: sql
+
+     create index l_orderkey_idx on lineitem (l_orderkey);
+
+If the index is created successfully, you can see the information about that index as follows: ::
+
+  default> \d lineitem
+
+  table name: default.lineitem
+  table path: hdfs://localhost:7020/tpch/lineitem
+  store type: CSV
+  number of rows: unknown
+  volume: 753.9 MB
+  Options:
+  	'text.delimiter'='|'
+
+  schema:
+  l_orderkey	INT8
+  l_partkey	INT8
+  l_suppkey	INT8
+  l_linenumber	INT8
+  l_quantity	FLOAT4
+  l_extendedprice	FLOAT4
+  l_discount	FLOAT4
+  l_tax	FLOAT4
+  l_returnflag	TEXT
+  l_linestatus	TEXT
+  l_shipdate	DATE
+  l_commitdate	DATE
+  l_receiptdate	DATE
+  l_shipinstruct	TEXT
+  l_shipmode	TEXT
+  l_comment	TEXT
+
+
+  Indexes:
+  "l_orderkey_idx" TWO_LEVEL_BIN_TREE (l_orderkey ASC NULLS LAST )
+
+For more information about index creation, please refer to the above links.
+
+-------------------------------------
+2. Enable/disable index scans
+-------------------------------------
+
+When an index is successfully created, you must enable the index scan feature as follows:
+
+.. code-block:: sql
+
+     \set INDEX_ENABLED true
+
+If you don't want to use the index scan feature anymore, you can simply disable it as follows:
+
+.. code-block:: sql
+
+     \set INDEX_ENABLED false
+
+.. note::
+
+     If the index scan feature is enabled, Tajo currently always performs index scan regardless of its efficiency. You should set this option when the expected number of retrieved tuples is sufficiently small.
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/index/types.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/index/types.rst b/tajo-docs/src/main/sphinx/index/types.rst
new file mode 100644
index 0000000..457f453
--- /dev/null
+++ b/tajo-docs/src/main/sphinx/index/types.rst
@@ -0,0 +1,7 @@
+*************************************
+Index Types
+*************************************
+
+Currently, Tajo supports only one type of index, ``TWO_LEVEL_BIN_TREE``, shortly ``BST``. The BST index is a kind of binary search tree which is extended to be permanently stored on disk. It consists of two levels of nodes; a leaf node indexes the keys with the positions of data in an HDFS block and a root node indexes the keys with the leaf node indices.
+
+When an index scan is started, the query engine first reads the root node and finds the search key. If it finds a leaf node corresponding to the search key, it subsequently finds the search key in that leaf node. Finally, it directly reads a tuple corresponding to the search key from HDFS.
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/index_overview.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/index_overview.rst b/tajo-docs/src/main/sphinx/index_overview.rst
new file mode 100644
index 0000000..78ecb49
--- /dev/null
+++ b/tajo-docs/src/main/sphinx/index_overview.rst
@@ -0,0 +1,20 @@
+***********************
+Index (Experimental Feature)
+***********************
+
+An index is a data structure that is used for efficient query processing. Using an index, the Tajo query engine can directly retrieve search values.
+
+This is still an experimental feature. In order to use indexes, you must check out the source code of the ``index_support`` branch::
+
+  git clone -b index_support https://git-wip-us.apache.org/repos/asf/tajo.git tajo-index
+
+For the source code build, please refer to :doc:`getting_started`.
+
+The following sections describe the supported index types, the query execution with an index, and the future works.
+
+.. toctree::
+      :maxdepth: 1
+
+      index/types
+      index/how_to_use
+      index/future_work
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-docs/src/main/sphinx/sql_language/ddl.rst
----------------------------------------------------------------------
diff --git a/tajo-docs/src/main/sphinx/sql_language/ddl.rst b/tajo-docs/src/main/sphinx/sql_language/ddl.rst
index 3fba6be..60b7190 100644
--- a/tajo-docs/src/main/sphinx/sql_language/ddl.rst
+++ b/tajo-docs/src/main/sphinx/sql_language/ddl.rst
@@ -75,4 +75,35 @@ If you want to add an external table that contains compressed data, you should g
 
   DROP TABLE [IF EXISTS] <table_name> [PURGE]
 
-``IF EXISTS`` allows ``DROP DATABASE`` statement to avoid an error which occurs when the database does not exist. ``DROP TABLE`` statement removes a table from Tajo catalog, but it does not remove the contents. If ``PURGE`` option is given, ``DROP TABLE`` statement will eliminate the entry in the catalog as well as the contents.
\ No newline at end of file
+``IF EXISTS`` allows ``DROP DATABASE`` statement to avoid an error which occurs when the database does not exist. ``DROP TABLE`` statement removes a table from Tajo catalog, but it does not remove the contents. If ``PURGE`` option is given, ``DROP TABLE`` statement will eliminate the entry in the catalog as well as the contents.
+
+========================
+ CREATE INDEX
+========================
+
+*Synopsis*
+
+.. code-block:: sql
+
+  CREATE INDEX [ name ] ON table_name [ USING method ]
+  ( { column_name | ( expression ) } [ ASC | DESC ] [ NULLS { FIRST | LAST } ] [, ...] )
+  [ WHERE predicate ]
+
+------------------------
+ Index method
+------------------------
+
+Currently, Tajo supports only one type of index.
+
+Index methods:
+  * TWO_LEVEL_BIN_TREE: This method is used by default in Tajo. For more information about its structure, please refer to :doc:`/index/types`.
+
+========================
+ DROP INDEX
+========================
+
+*Synopsis*
+
+.. code-block:: sql
+
+  DROP INDEX name
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalOptimizer.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalOptimizer.java b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalOptimizer.java
index 18a8859..ed16f82 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalOptimizer.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalOptimizer.java
@@ -28,6 +28,7 @@ import org.apache.tajo.ConfigKey;
 import org.apache.tajo.OverridableConf;
 import org.apache.tajo.SessionVars;
 import org.apache.tajo.algebra.JoinType;
+import org.apache.tajo.catalog.CatalogService;
 import org.apache.tajo.conf.TajoConf;
 import org.apache.tajo.conf.TajoConf.ConfVars;
 import org.apache.tajo.util.ReflectionUtil;
@@ -39,6 +40,10 @@ import org.apache.tajo.plan.joinorder.GreedyHeuristicJoinOrderAlgorithm;
 import org.apache.tajo.plan.joinorder.JoinGraph;
 import org.apache.tajo.plan.joinorder.JoinOrderAlgorithm;
 import org.apache.tajo.plan.logical.*;
+import org.apache.tajo.plan.rewrite.rules.AccessPathRewriter;
+import org.apache.tajo.plan.rewrite.rules.FilterPushDownRule;
+import org.apache.tajo.plan.rewrite.rules.PartitionedTableRewriter;
+import org.apache.tajo.plan.rewrite.rules.ProjectionPushDownRule;
 import org.apache.tajo.plan.rewrite.*;
 import org.apache.tajo.plan.util.PlannerUtil;
 import org.apache.tajo.plan.visitor.BasicLogicalPlanVisitor;
@@ -57,12 +62,15 @@ import static org.apache.tajo.plan.joinorder.GreedyHeuristicJoinOrderAlgorithm.g
 public class LogicalOptimizer {
   private static final Log LOG = LogFactory.getLog(LogicalOptimizer.class.getName());
 
+  private CatalogService catalog;
   private BaseLogicalPlanRewriteEngine rulesBeforeJoinOpt;
   private BaseLogicalPlanRewriteEngine rulesAfterToJoinOpt;
   private JoinOrderAlgorithm joinOrderAlgorithm = new GreedyHeuristicJoinOrderAlgorithm();
 
-  public LogicalOptimizer(TajoConf conf) {
+  public LogicalOptimizer(TajoConf conf, CatalogService catalog) {
 
+    this.catalog = catalog;
+    // TODO: set the catalog instance to FilterPushdownRule
     Class clazz = conf.getClassVar(ConfVars.LOGICAL_PLAN_REWRITE_RULE_PROVIDER_CLASS);
     LogicalPlanRewriteRuleProvider provider = (LogicalPlanRewriteRuleProvider) ReflectionUtil.newInstance(clazz, conf);
 
@@ -86,7 +94,7 @@ public class LogicalOptimizer {
   }
 
   public LogicalNode optimize(OverridableConf context, LogicalPlan plan) throws PlanningException {
-    rulesBeforeJoinOpt.rewrite(context, plan);
+    rulesBeforeJoinOpt.rewrite(new LogicalPlanRewriteRuleContext(context, plan, catalog));
 
     DirectedGraphCursor<String, BlockEdge> blockCursor =
         new DirectedGraphCursor<String, BlockEdge>(plan.getQueryBlockGraph(), plan.getRootBlock().getName());
@@ -99,7 +107,7 @@ public class LogicalOptimizer {
     } else {
       LOG.info("Skip Join Optimized.");
     }
-    rulesAfterToJoinOpt.rewrite(context, plan);
+    rulesAfterToJoinOpt.rewrite(new LogicalPlanRewriteRuleContext(context, plan, catalog));
     return plan.getRootBlock().getRoot();
   }
 

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlan.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlan.java b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlan.java
index 3baf61d..1535882 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlan.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlan.java
@@ -25,6 +25,8 @@ import org.apache.tajo.algebra.*;
 import org.apache.tajo.annotation.NotThreadSafe;
 import org.apache.tajo.catalog.Column;
 import org.apache.tajo.catalog.Schema;
+import org.apache.tajo.plan.expr.AlgebraicUtil.IdentifiableNameBuilder;
+import org.apache.tajo.plan.rewrite.rules.AccessPathInfo;
 import org.apache.tajo.util.graph.DirectedGraphCursor;
 import org.apache.tajo.util.graph.SimpleDirectedGraph;
 import org.apache.tajo.plan.expr.ConstEval;
@@ -150,6 +152,8 @@ public class LogicalPlan {
   /**
    * It generates an unique column name from Expr. It is usually used for an expression or predicate without
    * a specified name (i.e., alias).
+   * Here, some expressions require to be identified with their names in the future.
+   * For example, expressions must be identifiable with their names when getting targets in {@link LogicalPlanner#visitCreateIndex}.
    */
   public String generateUniqueColumnName(Expr expr) {
     String generatedName;
@@ -161,6 +165,11 @@ public class LogicalPlan {
     return generatedName;
   }
 
+  private String generateUniqueIdentifiableColumnName(Expr expr) {
+    IdentifiableNameBuilder nameBuilder = new IdentifiableNameBuilder(expr);
+    return nameBuilder.build();
+  }
+
   /**
    * It attaches a generated column name with a sequence id. It always keeps generated names unique.
    */
@@ -408,6 +417,7 @@ public class LogicalPlan {
     private final Map<String, String> columnAliasMap = TUtil.newHashMap();
     private final Map<OpType, List<Expr>> operatorToExprMap = TUtil.newHashMap();
     private final List<RelationNode> relationList = TUtil.newList();
+    private final Map<Integer, List<AccessPathInfo>> relNodePidAccessPathMap = TUtil.newHashMap();
     private boolean hasWindowFunction = false;
     private final Map<String, ConstEval> constantPoolByRef = Maps.newHashMap();
     private final Map<Expr, String> constantPool = Maps.newHashMap();
@@ -496,12 +506,30 @@ public class LogicalPlan {
       }
       canonicalNameToRelationMap.put(relation.getCanonicalName(), relation);
       relationList.add(relation);
+      relNodePidAccessPathMap.put(relation.getPID(), new ArrayList<AccessPathInfo>());
+    }
+
+    public void addRelation(RelationNode relation, List<AccessPathInfo> accessPathInfos) {
+      if (relation.hasAlias()) {
+        TUtil.putToNestedList(relationAliasMap, relation.getTableName(), relation.getCanonicalName());
+      }
+      canonicalNameToRelationMap.put(relation.getCanonicalName(), relation);
+      relationList.add(relation);
+      relNodePidAccessPathMap.put(relation.getPID(), new ArrayList<AccessPathInfo>());
+    }
+
+    public void addAccessPath(RelationNode relation, AccessPathInfo accessPathInfo) {
+      relNodePidAccessPathMap.get(relation.getPID()).add(accessPathInfo);
     }
 
     public Collection<RelationNode> getRelations() {
       return Collections.unmodifiableList(relationList);
     }
 
+    public List<AccessPathInfo> getAccessInfos(RelationNode relation) {
+      return Collections.unmodifiableList(relNodePidAccessPathMap.get(relation.getPID()));
+    }
+
     public boolean hasTableExpression() {
       return this.canonicalNameToRelationMap.size() > 0;
     }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanPreprocessor.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanPreprocessor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanPreprocessor.java
index 6e2b59a..76a32a2 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanPreprocessor.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanPreprocessor.java
@@ -231,7 +231,8 @@ public class LogicalPlanPreprocessor extends BaseAlgebraVisitor<LogicalPlanner.P
     return projectionNode;
   }
 
-  private Target [] buildTargets(LogicalPlanner.PlanContext context, NamedExpr [] exprs) throws PlanningException {
+  private Target [] buildTargets(LogicalPlanner.PlanContext context, NamedExpr [] exprs)
+      throws PlanningException {
     Target [] targets = new Target[exprs.length];
     for (int i = 0; i < exprs.length; i++) {
       NamedExpr namedExpr = exprs[i];
@@ -480,6 +481,11 @@ public class LogicalPlanPreprocessor extends BaseAlgebraVisitor<LogicalPlanner.P
     return createIndex;
   }
 
+  @Override
+  public LogicalNode visitDropIndex(LogicalPlanner.PlanContext ctx, Stack<Expr> stack, DropIndex expr) {
+    return ctx.plan.createNode(DropIndexNode.class);
+  }
+
   public LogicalNode visitTruncateTable(LogicalPlanner.PlanContext ctx, Stack<Expr> stack, TruncateTable expr)
       throws PlanningException {
     TruncateTableNode truncateTableNode = ctx.plan.createNode(TruncateTableNode.class);

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanner.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanner.java b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanner.java
index 3604e06..b50ef78 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanner.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/LogicalPlanner.java
@@ -41,7 +41,6 @@ import org.apache.tajo.catalog.proto.CatalogProtos.IndexMethod;
 import org.apache.tajo.catalog.proto.CatalogProtos.StoreType;
 import org.apache.tajo.common.TajoDataTypes;
 import org.apache.tajo.conf.TajoConf;
-import org.apache.tajo.conf.TajoConf.ConfVars;
 import org.apache.tajo.datum.NullDatum;
 import org.apache.tajo.plan.LogicalPlan.QueryBlock;
 import org.apache.tajo.plan.algebra.BaseAlgebraVisitor;
@@ -52,12 +51,12 @@ import org.apache.tajo.plan.nameresolver.NameResolvingMode;
 import org.apache.tajo.plan.rewrite.rules.ProjectionPushDownRule;
 import org.apache.tajo.plan.util.ExprFinder;
 import org.apache.tajo.plan.util.PlannerUtil;
-import org.apache.tajo.catalog.SchemaUtil;
 import org.apache.tajo.plan.verifier.VerifyException;
 import org.apache.tajo.util.KeyValueSet;
 import org.apache.tajo.util.Pair;
 import org.apache.tajo.util.TUtil;
 
+import java.net.URI;
 import java.util.*;
 
 import static org.apache.tajo.algebra.CreateTable.PartitionType;
@@ -1930,9 +1929,9 @@ public class LogicalPlanner extends BaseAlgebraVisitor<LogicalPlanner.PlanContex
     return alterTableNode;
   }
 
-  private static Path getIndexPath(PlanContext context, String databaseName, String indexName) {
+  private static URI getIndexPath(PlanContext context, String databaseName, String indexName) {
     return new Path(TajoConf.getWarehouseDir(context.queryContext.getConf()),
-        databaseName + "/" + indexName + "/");
+        databaseName + "/" + indexName + "/").toUri();
   }
 
   @Override
@@ -1960,15 +1959,20 @@ public class LogicalPlanner extends BaseAlgebraVisitor<LogicalPlanner.PlanContex
       normalizedExprList[i] = normalizer.normalize(context, sortSpecs[i].getKey());
     }
     for (int i = 0; i < sortKeyNum; i++) {
+      // even if base expressions don't have their name,
+      // reference names should be identifiable for the later sort spec creation.
       referNames[i] = block.namedExprsMgr.addExpr(normalizedExprList[i].baseExpr);
       block.namedExprsMgr.addNamedExprArray(normalizedExprList[i].aggExprs);
       block.namedExprsMgr.addNamedExprArray(normalizedExprList[i].scalarExprs);
     }
 
-    createIndexNode.setSortSpecs(annotateSortSpecs(block, referNames, sortSpecs));
-    createIndexNode.setIndexType(IndexMethod.valueOf(createIndex.getMethodSpec().getName().toUpperCase()));
-    createIndexNode.setIndexPath(getIndexPath(context, context.queryContext.get(SessionVars.CURRENT_DATABASE),
-        createIndex.getIndexName()));
+    Collection<RelationNode> relations = block.getRelations();
+    assert relations.size() == 1;
+    createIndexNode.setKeySortSpecs(relations.iterator().next().getLogicalSchema(),
+        annotateSortSpecs(block, referNames, sortSpecs));
+    createIndexNode.setIndexMethod(IndexMethod.valueOf(createIndex.getMethodSpec().getName().toUpperCase()));
+    createIndexNode.setIndexPath(
+        getIndexPath(context, context.queryContext.get(SessionVars.CURRENT_DATABASE), createIndex.getIndexName()));
 
     if (createIndex.getParams() != null) {
       KeyValueSet keyValueSet = new KeyValueSet();
@@ -1981,6 +1985,13 @@ public class LogicalPlanner extends BaseAlgebraVisitor<LogicalPlanner.PlanContex
   }
 
   @Override
+  public LogicalNode visitDropIndex(PlanContext context, Stack<Expr> stack, DropIndex dropIndex) {
+    DropIndexNode dropIndexNode = context.queryBlock.getNodeFromExpr(dropIndex);
+    dropIndexNode.setIndexName(dropIndex.getIndexName());
+    return dropIndexNode;
+  }
+
+  @Override
   public LogicalNode visitTruncateTable(PlanContext context, Stack<Expr> stack, TruncateTable truncateTable)
       throws PlanningException {
     TruncateTableNode truncateTableNode = context.queryBlock.getNodeFromExpr(truncateTable);

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/NamedExprsManager.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/NamedExprsManager.java b/tajo-plan/src/main/java/org/apache/tajo/plan/NamedExprsManager.java
index 991860f..63c10ae 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/NamedExprsManager.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/NamedExprsManager.java
@@ -141,6 +141,7 @@ public class NamedExprsManager {
 
   /**
    * Adds an expression and returns a reference name.
+   * @param expr added expression
    */
   public String addExpr(Expr expr) throws PlanningException {
     if (idToExprBiMap.inverse().containsKey(expr)) {
@@ -205,7 +206,8 @@ public class NamedExprsManager {
    * Adds a list of expressions and returns a list of reference names.
    * If some NamedExpr has an alias, NamedExprsManager specifies the alias for the NamedExpr.
    */
-  public String [] addNamedExprArray(@Nullable Collection<NamedExpr> namedExprs) throws PlanningException {
+  public String [] addNamedExprArray(@Nullable Collection<NamedExpr> namedExprs)
+      throws PlanningException {
     if (namedExprs != null && namedExprs.size() > 0) {
       String [] names = new String[namedExprs.size()];
       int i = 0;

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/AlgebraVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/AlgebraVisitor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/AlgebraVisitor.java
index 6e7a514..d818249 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/AlgebraVisitor.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/AlgebraVisitor.java
@@ -53,6 +53,7 @@ public interface AlgebraVisitor<CONTEXT, RESULT> {
   RESULT visitAlterTablespace(CONTEXT ctx, Stack<Expr> stack, AlterTablespace expr) throws PlanningException;
   RESULT visitAlterTable(CONTEXT ctx, Stack<Expr> stack, AlterTable expr) throws PlanningException;
   RESULT visitCreateIndex(CONTEXT ctx, Stack<Expr> stack, CreateIndex expr) throws PlanningException;
+  RESULT visitDropIndex(CONTEXT ctx, Stack<Expr> stack, DropIndex expr) throws PlanningException;
   RESULT visitTruncateTable(CONTEXT ctx, Stack<Expr> stack, TruncateTable expr) throws PlanningException;
 
     // Insert or Update

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/BaseAlgebraVisitor.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/BaseAlgebraVisitor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/BaseAlgebraVisitor.java
index ffaf713..664dd80 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/BaseAlgebraVisitor.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/algebra/BaseAlgebraVisitor.java
@@ -128,6 +128,9 @@ public class BaseAlgebraVisitor<CONTEXT, RESULT> implements AlgebraVisitor<CONTE
     case TruncateTable:
       current = visitTruncateTable(ctx, stack, (TruncateTable)expr);
       break;
+    case DropIndex:
+      current = visitDropIndex(ctx, stack, (DropIndex) expr);
+      break;
 
     case Insert:
       current = visitInsert(ctx, stack, (Insert) expr);
@@ -488,6 +491,11 @@ public class BaseAlgebraVisitor<CONTEXT, RESULT> implements AlgebraVisitor<CONTE
   }
 
   @Override
+  public RESULT visitDropIndex(CONTEXT ctx, Stack<Expr> stack, DropIndex expr) {
+    return null;
+  }
+
+  @Override
   public RESULT visitTruncateTable(CONTEXT ctx, Stack<Expr> stack, TruncateTable expr) throws PlanningException {
     return null;
   }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
index 84352f0..9e6d78f 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/AlgebraicUtil.java
@@ -18,7 +18,10 @@
 
 package org.apache.tajo.plan.expr;
 
+import org.apache.tajo.algebra.*;
 import org.apache.tajo.catalog.Column;
+import org.apache.tajo.plan.PlanningException;
+import org.apache.tajo.plan.visitor.SimpleAlgebraVisitor;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -414,4 +417,70 @@ public class AlgebraicUtil {
       found.add(node);
     }
   }
+
+  public static class IdentifiableNameBuilder extends SimpleAlgebraVisitor<Object, Object> {
+    private Expr expr;
+    private StringBuilder nameBuilder = new StringBuilder();
+
+    public IdentifiableNameBuilder(Expr expr) {
+      this.expr = expr;
+    }
+
+    public String build() {
+      Stack<Expr> stack = new Stack<Expr>();
+      stack.push(expr);
+      try {
+        this.visit(null, stack, expr);
+      } catch (PlanningException e) {
+
+      }
+      return nameBuilder.deleteCharAt(nameBuilder.length()-1).toString();
+    }
+
+    @Override
+    public Object visitBinaryOperator(Object ctx, Stack<Expr> stack, BinaryOperator expr) throws PlanningException {
+      addIntermExpr(expr);
+      return super.visitBinaryOperator(ctx, stack, expr);
+    }
+
+    private void append(String str) {
+      nameBuilder.append(str).append("_");
+    }
+
+    private void addIntermExpr(Expr expr) {
+      this.append(expr.getType().name());
+    }
+
+    @Override
+    public Object visitColumnReference(Object ctx, Stack<Expr> stack, ColumnReferenceExpr expr)
+        throws PlanningException {
+      this.append(expr.getName());
+      return super.visitColumnReference(ctx, stack, expr);
+    }
+
+    @Override
+    public Object visitLiteral(Object ctx, Stack<Expr> stack, LiteralValue expr) throws PlanningException {
+      this.append(expr.getValue());
+      return super.visitLiteral(ctx, stack, expr);
+    }
+
+    @Override
+    public Object visitNullLiteral(Object ctx, Stack<Expr> stack, NullLiteral expr) throws PlanningException {
+      this.append("null");
+      return super.visitNullLiteral(ctx, stack, expr);
+    }
+
+    @Override
+    public Object visitTimestampLiteral(Object ctx, Stack<Expr> stack, TimestampLiteral expr) throws PlanningException {
+      this.append(expr.getDate().toString());
+      this.append(expr.getTime().toString());
+      return super.visitTimestampLiteral(ctx, stack, expr);
+    }
+
+    @Override
+    public Object visitTimeLiteral(Object ctx, Stack<Expr> stack, TimeLiteral expr) throws PlanningException {
+      this.append(expr.getTime().toString());
+      return super.visitTimeLiteral(ctx, stack, expr);
+    }
+  }
 }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
index f5c2cbd..5b6ebc7 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/expr/EvalTreeUtil.java
@@ -382,7 +382,7 @@ public class EvalTreeUtil {
     return !leftQualifier.equals(rightQualifier);
   }
 
-  static boolean isSingleColumn(EvalNode evalNode) {
+  public static boolean isSingleColumn(EvalNode evalNode) {
     return EvalTreeUtil.findUniqueColumns(evalNode).size() == 1;
   }
   
@@ -517,6 +517,10 @@ public class EvalTreeUtil {
 
       return evalNode;
     }
+
+    public List<EvalNode> getEvalNodes() {
+      return evalNodes;
+    }
   }
 
   public static class OuterJoinSensitiveEvalFinder extends BasicEvalNodeVisitor<Object, Object> {

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/logical/CreateIndexNode.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/CreateIndexNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/CreateIndexNode.java
index a8d364f..fcedf48 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/CreateIndexNode.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/CreateIndexNode.java
@@ -18,91 +18,99 @@
 
 package org.apache.tajo.plan.logical;
 
-import com.google.common.base.Objects;
 import com.google.gson.annotations.Expose;
-import org.apache.hadoop.fs.Path;
+import org.apache.tajo.catalog.IndexMeta;
+import org.apache.tajo.catalog.Schema;
 import org.apache.tajo.catalog.SortSpec;
 import org.apache.tajo.plan.PlanString;
 import org.apache.tajo.util.KeyValueSet;
-import org.apache.tajo.util.TUtil;
+
+import java.net.URI;
 
 import static org.apache.tajo.catalog.proto.CatalogProtos.IndexMethod;
 
 public class CreateIndexNode extends UnaryNode implements Cloneable {
-  @Expose private boolean isUnique;
-  @Expose private String indexName;
-  @Expose private Path indexPath;
-  @Expose private SortSpec[] sortSpecs;
-  @Expose private IndexMethod indexType = IndexMethod.TWO_LEVEL_BIN_TREE;
-  @Expose private KeyValueSet options;
+  @Expose private IndexMeta indexMeta;
 
   public CreateIndexNode(int pid) {
     super(pid, NodeType.CREATE_INDEX);
+    this.indexMeta = new IndexMeta();
   }
 
   public void setUnique(boolean unique) {
-    this.isUnique = unique;
+    indexMeta.setUnique(unique);
   }
 
   public boolean isUnique() {
-    return isUnique;
+    return indexMeta.isUnique();
   }
 
   public void setIndexName(String indexName) {
-    this.indexName = indexName;
+    indexMeta.setIndexName(indexName);
   }
 
   public String getIndexName() {
-    return this.indexName;
+    return indexMeta.getIndexName();
   }
 
-  public void setIndexPath(Path indexPath) {
-    this.indexPath = indexPath;
+  public void setIndexPath(URI indexPath) {
+    indexMeta.setIndexPath(indexPath);
   }
 
-  public Path getIndexPath() {
-    return this.indexPath;
+  public URI getIndexPath() {
+    return indexMeta.getIndexPath();
   }
 
-  public void setSortSpecs(SortSpec[] sortSpecs) {
-    this.sortSpecs = sortSpecs;
+  public void setKeySortSpecs(Schema targetRelationSchema, SortSpec[] sortSpecs) {
+    indexMeta.setKeySortSpecs(targetRelationSchema, sortSpecs);
   }
 
-  public SortSpec[] getSortSpecs() {
-    return this.sortSpecs;
+  public SortSpec[] getKeySortSpecs() {
+    return indexMeta.getKeySortSpecs();
   }
 
-  public void setIndexType(IndexMethod indexType) {
-    this.indexType = indexType;
+  public void setIndexMethod(IndexMethod indexType) {
+    indexMeta.setIndexMethod(indexType);
   }
 
-  public IndexMethod getIndexType() {
-    return this.indexType;
+  public IndexMethod getIndexMethod() {
+    return indexMeta.getIndexMethod();
   }
 
   public void setOptions(KeyValueSet options) {
-    this.options = options;
+    indexMeta.setOptions(options);
   }
 
   public KeyValueSet getOptions() {
-    return this.options;
+    return indexMeta.getOptions();
+  }
+
+  public Schema getTargetRelationSchema() {
+    return indexMeta.getTargetRelationSchema();
+  }
+
+  public boolean hasOptions() {
+    return indexMeta.getOptions() != null;
+  }
+
+  public void setClustered(boolean clustered) {
+    indexMeta.setClustered(clustered);
+  }
+
+  public boolean isClustered() {
+    return indexMeta.isClustered();
   }
 
   @Override
   public int hashCode() {
-    return Objects.hashCode(isUnique, indexName, indexPath, sortSpecs, indexType, options);
+    return indexMeta.hashCode();
   }
 
   @Override
   public boolean equals(Object obj) {
     if (obj instanceof CreateIndexNode) {
       CreateIndexNode other = (CreateIndexNode) obj;
-      return this.isUnique == other.isUnique &&
-          TUtil.checkEquals(this.indexName, other.indexName) &&
-          TUtil.checkEquals(this.indexPath, other.indexPath) &&
-          TUtil.checkEquals(this.sortSpecs, other.sortSpecs) &&
-          this.indexType.equals(other.indexType) &&
-          TUtil.checkEquals(this.options, other.options);
+      return this.indexMeta.equals(other.indexMeta);
     }
     return false;
   }
@@ -110,17 +118,13 @@ public class CreateIndexNode extends UnaryNode implements Cloneable {
   @Override
   public Object clone() throws CloneNotSupportedException {
     CreateIndexNode createIndexNode = (CreateIndexNode) super.clone();
-    createIndexNode.isUnique = isUnique;
-    createIndexNode.indexName = indexName;
-    createIndexNode.indexPath = indexPath;
-    createIndexNode.sortSpecs = sortSpecs.clone();
-    createIndexNode.indexType = indexType;
-    createIndexNode.options = (KeyValueSet) (options != null ? options.clone() : null);
+    createIndexNode.indexMeta = (IndexMeta) this.indexMeta.clone();
     return createIndexNode;
   }
 
   private String getSortSpecString() {
     StringBuilder sb = new StringBuilder("Column [key= ");
+    SortSpec[] sortSpecs = indexMeta.getKeySortSpecs();
     for (int i = 0; i < sortSpecs.length; i++) {
       sb.append(sortSpecs[i].getSortKey().getQualifiedName()).append(" ")
           .append(sortSpecs[i].isAscending() ? "asc" : "desc");
@@ -134,8 +138,9 @@ public class CreateIndexNode extends UnaryNode implements Cloneable {
 
   @Override
   public String toString() {
-    return "CreateIndex (indexName=" + indexName + ", indexPath=" + indexPath + ", type=" + indexType.name() +
-        ", isUnique=" + isUnique + ", " + getSortSpecString() + ")";
+    return "CreateIndex (indexName=" + indexMeta.getIndexName() + ", indexPath=" + indexMeta.getIndexPath() +
+        ", type=" + indexMeta.getIndexMethod().name() +
+        ", isUnique=" + indexMeta.isUnique() + ", " + getSortSpecString() + ")";
   }
 
   @Override

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/logical/DropIndexNode.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/DropIndexNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/DropIndexNode.java
new file mode 100644
index 0000000..da7018a
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/DropIndexNode.java
@@ -0,0 +1,92 @@
+/*
+ * 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.tajo.plan.logical;
+
+import com.google.common.base.Objects;
+import org.apache.tajo.plan.PlanString;
+
+public class DropIndexNode extends LogicalNode implements Cloneable {
+  private String indexName;
+
+  public DropIndexNode(int pid) {
+    super(pid, NodeType.DROP_INDEX);
+  }
+
+  public void init(String indexName) {
+    this.indexName = indexName;
+  }
+
+  public int hashCode() {
+    return Objects.hashCode(indexName);
+  }
+
+  @Override
+  public int childNum() {
+    return 0;
+  }
+
+  @Override
+  public LogicalNode getChild(int idx) {
+    return null;
+  }
+
+  public boolean equals(Object obj) {
+    if (obj instanceof DropIndexNode) {
+      DropIndexNode other = (DropIndexNode) obj;
+      return super.equals(other) &&
+          this.indexName.equals(other.indexName);
+    }
+    return false;
+  }
+
+  @Override
+  public void preOrder(LogicalNodeVisitor visitor) {
+    visitor.visit(this);
+  }
+
+  @Override
+  public void postOrder(LogicalNodeVisitor visitor) {
+    visitor.visit(this);
+  }
+
+  @Override
+  public PlanString getPlanString() {
+    return new PlanString(this);
+  }
+
+  @Override
+  public Object clone() throws CloneNotSupportedException {
+    DropIndexNode clone = (DropIndexNode) super.clone();
+    clone.indexName = this.indexName;
+    return clone;
+  }
+
+  @Override
+  public String toString() {
+    return "DROP INDEX " + indexName;
+  }
+
+  public void setIndexName(String indexName) {
+    this.indexName = indexName;
+  }
+
+  public String getIndexName() {
+    return indexName;
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/logical/IndexScanNode.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/IndexScanNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/IndexScanNode.java
index 0d59733..a36e982 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/IndexScanNode.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/IndexScanNode.java
@@ -21,56 +21,54 @@ package org.apache.tajo.plan.logical;
 import com.google.gson.Gson;
 import com.google.gson.annotations.Expose;
 import org.apache.tajo.catalog.Schema;
-import org.apache.tajo.catalog.SortSpec;
-import org.apache.tajo.datum.Datum;
+import org.apache.tajo.plan.rewrite.rules.IndexScanInfo.SimplePredicate;
 import org.apache.tajo.plan.serder.PlanGsonHelper;
+import org.apache.tajo.util.TUtil;
+
+import java.net.URI;
 
 public class IndexScanNode extends ScanNode {
-  @Expose private SortSpec [] sortKeys;
   @Expose private Schema keySchema = null;
-  @Expose private Datum[] datum = null;
+  @Expose private URI indexPath = null;
+  @Expose private SimplePredicate[] predicates = null;
+
+  public IndexScanNode(int pid) {
+    super(pid);
+    setType(NodeType.INDEX_SCAN);
+  }
   
   public IndexScanNode(int pid, ScanNode scanNode ,
-      Schema keySchema , Datum[] datum, SortSpec[] sortKeys ) {
-    super(pid);
+      Schema keySchema , SimplePredicate[] predicates, URI indexPath) {
+    this(pid);
     init(scanNode.getTableDesc());
     setQual(scanNode.getQual());
     setInSchema(scanNode.getInSchema());
     setTargets(scanNode.getTargets());
-    setType(NodeType.BST_INDEX_SCAN);
-    this.sortKeys = sortKeys;
-    this.keySchema = keySchema;
-    this.datum = datum;
+    this.set(keySchema, predicates, indexPath);
   }
-  
-  public SortSpec[] getSortKeys() {
-    return this.sortKeys;
+
+  public void set(Schema keySchema, SimplePredicate[] predicates, URI indexPath) {
+    this.keySchema = keySchema;
+    this.indexPath = indexPath;
+    this.predicates = predicates;
   }
   
   public Schema getKeySchema() {
     return this.keySchema;
   }
-  
-  public Datum[] getDatum() {
-    return this.datum;
-  }
-  
-  public void setSortKeys(SortSpec[] sortKeys) {
-    this.sortKeys = sortKeys;
+
+  public SimplePredicate[] getPredicates() {
+    return predicates;
   }
   
-  public void setKeySchema( Schema keySchema ) {
-    this.keySchema = keySchema;
-  }
-
   @Override
   public String toString() {
     Gson gson = PlanGsonHelper.getInstance();
     StringBuilder builder = new StringBuilder();
     builder.append("IndexScanNode : {\n");
+    builder.append("  \"indexPath\" : \"" + gson.toJson(this.indexPath) + "\"\n");
     builder.append("  \"keySchema\" : \"" + gson.toJson(this.keySchema) + "\"\n");
-    builder.append("  \"sortKeys\" : \"" + gson.toJson(this.sortKeys) + " \"\n");
-    builder.append("  \"datums\" : \"" + gson.toJson(this.datum) + "\"\n");
+    builder.append("  \"keySortSpecs\" : \"" + gson.toJson(predicates) + " \"\n");
     builder.append("      <<\"superClass\" : " + super.toString());
     builder.append(">>}");
     builder.append("}");
@@ -81,25 +79,12 @@ public class IndexScanNode extends ScanNode {
   public boolean equals(Object obj) {
     if (obj instanceof IndexScanNode) {
       IndexScanNode other = (IndexScanNode) obj;
-      
       boolean eq = super.equals(other);
-      eq = eq && this.sortKeys.length == other.sortKeys.length;
-      if(eq) {
-        for(int i = 0 ; i < this.sortKeys.length ; i ++) {
-          eq = eq && this.sortKeys[i].getSortKey().equals(
-              other.sortKeys[i].getSortKey());
-          eq = eq && this.sortKeys[i].isAscending()
-              == other.sortKeys[i].isAscending();
-          eq = eq && this.sortKeys[i].isNullFirst()
-              == other.sortKeys[i].isNullFirst();
-        }
-      }
-      if(eq) {
-        for(int i = 0 ; i < this.datum.length ; i ++ ) {
-          eq = eq && this.datum[i].equals(other.datum[i]);
-        }
-      }
-     return eq;
+      eq &= this.indexPath.equals(other.indexPath);
+      eq &= TUtil.checkEquals(this.predicates, other.predicates);
+      eq &= this.keySchema.equals(other.keySchema);
+
+      return eq;
     }   
     return false;
   } 
@@ -108,15 +93,16 @@ public class IndexScanNode extends ScanNode {
   public Object clone() throws CloneNotSupportedException {
     IndexScanNode indexNode = (IndexScanNode) super.clone();
     indexNode.keySchema = (Schema) this.keySchema.clone();
-    indexNode.sortKeys = new SortSpec[this.sortKeys.length];
-    for(int i = 0 ; i < sortKeys.length ; i ++ )
-      indexNode.sortKeys[i] = (SortSpec) this.sortKeys[i].clone();
-    indexNode.datum = new Datum[this.datum.length];
-    for(int i = 0 ; i < datum.length ; i ++ ) {
-      indexNode.datum[i] = this.datum[i];
-    }
+    indexNode.predicates = new SimplePredicate[this.predicates.length];
+    for(int i = 0 ; i < this.predicates.length ; i ++ )
+      indexNode.predicates[i] = (SimplePredicate) this.predicates[i].clone();
+    indexNode.indexPath = this.indexPath;
     return indexNode;
   }
+
+  public URI getIndexPath() {
+    return indexPath;
+  }
 }
 
 

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/logical/NodeType.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/NodeType.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/NodeType.java
index c1ff7e1..1ebea8b 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/NodeType.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/NodeType.java
@@ -45,7 +45,7 @@ public enum NodeType {
   TABLE_SUBQUERY(TableSubQueryNode.class),
   SCAN(ScanNode.class),
   PARTITIONS_SCAN(PartitionedTableScanNode.class),
-  BST_INDEX_SCAN(IndexScanNode.class),
+  INDEX_SCAN(IndexScanNode.class),
   STORE(StoreTableNode.class),
   INSERT(InsertNode.class),
 
@@ -56,6 +56,7 @@ public enum NodeType {
   ALTER_TABLESPACE (AlterTablespaceNode.class),
   ALTER_TABLE (AlterTableNode.class),
   CREATE_INDEX(CreateIndexNode.class),
+  DROP_INDEX(DropIndexNode.class),
   TRUNCATE_TABLE (TruncateTableNode.class);
 
   private final Class<? extends LogicalNode> baseClass;

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteEngine.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteEngine.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteEngine.java
index 19c254b..6b7e32c 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteEngine.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteEngine.java
@@ -20,7 +20,6 @@ package org.apache.tajo.plan.rewrite;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
-import org.apache.tajo.OverridableConf;
 import org.apache.tajo.plan.LogicalPlan;
 import org.apache.tajo.plan.PlanningException;
 
@@ -69,18 +68,19 @@ public class BaseLogicalPlanRewriteEngine implements LogicalPlanRewriteEngine {
   /**
    * Rewrite a logical plan with all query rewrite rules added to this engine.
    *
-   * @param plan The plan to be rewritten with all query rewrite rule.
+   * @param context
    * @return The rewritten plan.
    */
-  public LogicalPlan rewrite(OverridableConf queryContext, LogicalPlan plan) throws PlanningException {
+  public LogicalPlan rewrite(LogicalPlanRewriteRuleContext context) throws PlanningException {
     LogicalPlanRewriteRule rule;
+    LogicalPlan plan = null;
     for (Entry<String, LogicalPlanRewriteRule> rewriteRule : rewriteRules.entrySet()) {
       rule = rewriteRule.getValue();
-      if (rule.isEligible(queryContext, plan)) {
-        plan = rule.rewrite(queryContext, plan);
+      if (rule.isEligible(context)) {
         if (LOG.isDebugEnabled()) {
           LOG.debug("The rule \"" + rule.getName() + " \" rewrites the query.");
         }
+        plan = rule.rewrite(context);
       }
     }
 

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteRuleProvider.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteRuleProvider.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteRuleProvider.java
index eb96149..dcfd6bf 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteRuleProvider.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/BaseLogicalPlanRewriteRuleProvider.java
@@ -19,6 +19,7 @@
 package org.apache.tajo.plan.rewrite;
 
 import org.apache.tajo.conf.TajoConf;
+import org.apache.tajo.plan.rewrite.rules.AccessPathRewriter;
 import org.apache.tajo.plan.rewrite.rules.FilterPushDownRule;
 import org.apache.tajo.plan.rewrite.rules.PartitionedTableRewriter;
 import org.apache.tajo.plan.rewrite.rules.ProjectionPushDownRule;
@@ -52,7 +53,8 @@ public class BaseLogicalPlanRewriteRuleProvider extends LogicalPlanRewriteRulePr
   public Collection<Class<? extends LogicalPlanRewriteRule>> getPostRules() {
     List<Class<? extends LogicalPlanRewriteRule>> rules = TUtil.newList(
         ProjectionPushDownRule.class,
-        PartitionedTableRewriter.class
+        PartitionedTableRewriter.class,
+        AccessPathRewriter.class
     );
     return rules;
   }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteEngine.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteEngine.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteEngine.java
index 267d651..f264977 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteEngine.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteEngine.java
@@ -18,7 +18,6 @@
 
 package org.apache.tajo.plan.rewrite;
 
-import org.apache.tajo.OverridableConf;
 import org.apache.tajo.plan.LogicalPlan;
 import org.apache.tajo.plan.PlanningException;
 
@@ -29,5 +28,5 @@ public interface LogicalPlanRewriteEngine {
    * @param plan The plan to be rewritten with all query rewrite rule.
    * @return The rewritten plan.
    */
-  LogicalPlan rewrite(OverridableConf queryContext, LogicalPlan plan) throws PlanningException;
+  LogicalPlan rewrite(LogicalPlanRewriteRuleContext context) throws PlanningException;
 }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRule.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRule.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRule.java
index 2f0652b..1569a07 100644
--- a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRule.java
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRule.java
@@ -18,7 +18,6 @@
 
 package org.apache.tajo.plan.rewrite;
 
-import org.apache.tajo.OverridableConf;
 import org.apache.tajo.plan.LogicalPlan;
 import org.apache.tajo.plan.PlanningException;
 
@@ -43,7 +42,7 @@ public interface LogicalPlanRewriteRule {
    * @param plan The plan to be checked
    * @return True if this rule can be applied to a given plan. Otherwise, false.
    */
-  boolean isEligible(OverridableConf queryContext, LogicalPlan plan);
+  boolean isEligible(LogicalPlanRewriteRuleContext context);
 
   /**
    * Updates a logical plan and returns an updated logical plan rewritten by this rule.
@@ -53,5 +52,5 @@ public interface LogicalPlanRewriteRule {
    * @param plan Input logical plan. It will not be modified.
    * @return The rewritten logical plan.
    */
-  LogicalPlan rewrite(OverridableConf queryContext, LogicalPlan plan) throws PlanningException;
+  LogicalPlan rewrite(LogicalPlanRewriteRuleContext context) throws PlanningException;
 }

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRuleContext.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRuleContext.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRuleContext.java
new file mode 100644
index 0000000..6c43112
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/LogicalPlanRewriteRuleContext.java
@@ -0,0 +1,65 @@
+/**
+ * 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.tajo.plan.rewrite;
+
+import org.apache.tajo.OverridableConf;
+import org.apache.tajo.catalog.CatalogService;
+import org.apache.tajo.plan.LogicalPlan;
+
+public class LogicalPlanRewriteRuleContext {
+
+  private OverridableConf queryContext;
+  private LogicalPlan plan;
+  private CatalogService catalog;
+
+  public LogicalPlanRewriteRuleContext(OverridableConf queryContext, LogicalPlan plan) {
+    setQueryContext(queryContext);
+    setPlan(plan);
+  }
+
+  public LogicalPlanRewriteRuleContext(OverridableConf queryContext, LogicalPlan plan, CatalogService catalog) {
+    setQueryContext(queryContext);
+    setPlan(plan);
+    setCatalog(catalog);
+  }
+
+  public void setCatalog(CatalogService catalog) {
+    this.catalog = catalog;
+  }
+
+  public CatalogService getCatalog() {
+    return catalog;
+  }
+
+  public OverridableConf getQueryContext() {
+    return queryContext;
+  }
+
+  public void setQueryContext(OverridableConf queryContext) {
+    this.queryContext = queryContext;
+  }
+
+  public LogicalPlan getPlan() {
+    return plan;
+  }
+
+  public void setPlan(LogicalPlan plan) {
+    this.plan = plan;
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathInfo.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathInfo.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathInfo.java
new file mode 100644
index 0000000..477ccaf
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathInfo.java
@@ -0,0 +1,52 @@
+/*
+ * 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.tajo.plan.rewrite.rules;
+
+import org.apache.tajo.catalog.statistics.TableStats;
+
+public abstract class AccessPathInfo {
+  public enum ScanTypeControl {
+    INDEX_SCAN,
+    SEQ_SCAN
+  }
+
+  private ScanTypeControl scanType;
+  private TableStats tableStats;
+
+  public AccessPathInfo(ScanTypeControl scanType, TableStats tableStats) {
+    this.scanType = scanType;
+    this.tableStats = tableStats;
+  }
+
+  public ScanTypeControl getScanType() {
+    return scanType;
+  }
+
+  public TableStats getTableStats() {
+    return tableStats;
+  }
+
+  public void setTableStats(TableStats tableStats) {
+    this.tableStats = tableStats;
+  }
+
+  public boolean hasTableStats() {
+    return this.tableStats != null;
+  }
+}

http://git-wip-us.apache.org/repos/asf/tajo/blob/071c5d05/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathRewriter.java
----------------------------------------------------------------------
diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathRewriter.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathRewriter.java
new file mode 100644
index 0000000..bfa8d04
--- /dev/null
+++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/AccessPathRewriter.java
@@ -0,0 +1,129 @@
+/*
+ * 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.tajo.plan.rewrite.rules;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+import org.apache.tajo.OverridableConf;
+import org.apache.tajo.SessionVars;
+import org.apache.tajo.plan.LogicalPlan;
+import org.apache.tajo.plan.PlanningException;
+import org.apache.tajo.plan.logical.IndexScanNode;
+import org.apache.tajo.plan.logical.LogicalNode;
+import org.apache.tajo.plan.logical.RelationNode;
+import org.apache.tajo.plan.logical.ScanNode;
+import org.apache.tajo.plan.rewrite.LogicalPlanRewriteRule;
+import org.apache.tajo.plan.rewrite.LogicalPlanRewriteRuleContext;
+import org.apache.tajo.plan.util.PlannerUtil;
+import org.apache.tajo.plan.visitor.BasicLogicalPlanVisitor;
+
+import java.util.List;
+import java.util.Stack;
+
+public class AccessPathRewriter implements LogicalPlanRewriteRule {
+  private static final Log LOG = LogFactory.getLog(AccessPathRewriter.class);
+
+  private static final String NAME = "Access Path Rewriter";
+  private Rewriter rewriter = new Rewriter();
+
+  @Override
+  public String getName() {
+    return NAME;
+  }
+
+  @Override
+  public boolean isEligible(LogicalPlanRewriteRuleContext context) {
+    if (context.getQueryContext().getBool(SessionVars.INDEX_ENABLED)) {
+      for (LogicalPlan.QueryBlock block : context.getPlan().getQueryBlocks()) {
+        for (RelationNode relationNode : block.getRelations()) {
+          List<AccessPathInfo> accessPathInfos = block.getAccessInfos(relationNode);
+          // If there are any alternative access paths
+          if (accessPathInfos.size() > 1) {
+            for (AccessPathInfo accessPathInfo : accessPathInfos) {
+              if (accessPathInfo.getScanType() == AccessPathInfo.ScanTypeControl.INDEX_SCAN) {
+                return true;
+              }
+            }
+          }
+        }
+      }
+    }
+    return false;
+  }
+
+  @Override
+  public LogicalPlan rewrite(LogicalPlanRewriteRuleContext context) throws PlanningException {
+    LogicalPlan plan = context.getPlan();
+    LogicalPlan.QueryBlock rootBlock = plan.getRootBlock();
+    rewriter.init(context.getQueryContext());
+    rewriter.visit(rootBlock, plan, rootBlock, rootBlock.getRoot(), new Stack<LogicalNode>());
+    return plan;
+  }
+
+  private final class Rewriter extends BasicLogicalPlanVisitor<Object, Object> {
+
+    private OverridableConf conf;
+
+    public void init(OverridableConf conf) {
+      this.conf = conf;
+    }
+
+    @Override
+    public Object visitScan(Object object, LogicalPlan plan, LogicalPlan.QueryBlock block, ScanNode scanNode,
+                            Stack<LogicalNode> stack) throws PlanningException {
+      List<AccessPathInfo> accessPaths = block.getAccessInfos(scanNode);
+      AccessPathInfo optimalPath = null;
+      // initialize
+      for (AccessPathInfo accessPath : accessPaths) {
+        if (accessPath.getScanType() == AccessPathInfo.ScanTypeControl.SEQ_SCAN) {
+          optimalPath = accessPath;
+          break;
+        }
+      }
+      // find the optimal path
+      for (AccessPathInfo accessPath : accessPaths) {
+        if (accessPath.getScanType() == AccessPathInfo.ScanTypeControl.INDEX_SCAN) {
+          // estimation selectivity and choose the better path
+          // TODO: improve the selectivity estimation
+          double estimateSelectivity = 0.001;
+          double selectivityThreshold = conf.getFloat(SessionVars.INDEX_SELECTIVITY_THRESHOLD);
+          LOG.info("Selectivity threshold: " + selectivityThreshold);
+          LOG.info("Estimated selectivity: " + estimateSelectivity);
+          if (estimateSelectivity < selectivityThreshold) {
+            // if the estimated selectivity is greater than threshold, use the index scan
+            optimalPath = accessPath;
+          }
+        }
+      }
+
+      if (optimalPath != null && optimalPath.getScanType() == AccessPathInfo.ScanTypeControl.INDEX_SCAN) {
+        IndexScanInfo indexScanInfo = (IndexScanInfo) optimalPath;
+        plan.addHistory("AccessPathRewriter chooses the index scan for " + scanNode.getTableName());
+        IndexScanNode indexScanNode = new IndexScanNode(plan.newPID(), scanNode, indexScanInfo.getKeySchema(),
+            indexScanInfo.getPredicates(), indexScanInfo.getIndexPath());
+        if (stack.empty() || block.getRoot().equals(scanNode)) {
+          block.setRoot(indexScanNode);
+        } else {
+          PlannerUtil.replaceNode(plan, stack.peek(), scanNode, indexScanNode);
+        }
+      }
+      return null;
+    }
+  }
+}


Mime
View raw message