Repository: gluesql/gluesql
Pull request #227 (2021-05-21 14:50:13)

Implement basic single expression index,
Add simple query planner module - plan.
Current index system can only handle Eq binary op between {index_expr} and {literal}.
e.g.
SELECT * FROM TableA WHERE id = 1;
SELECT * FROM TableA WHERE 320 = (id || name);

Remaining tasks for this PR
- [x] More index operators (Gt, Gte, Lt and Lte)
- [x] Accept more expressions for index value (currently it only supports `Expr::Literal`)
- [x] Merge shared codes in `evaluate_stateless` & `evaluate`
- [x] Additional `test_idx` macro to test query plan result


Patch:
diff --git a/.github/workflows/rust.yml b/.github/workflows/rust.yml
index 839b01f4..3f31291c 100644
--- a/.github/workflows/rust.yml
+++ b/.github/workflows/rust.yml
@@ -21,6 +21,8 @@ jobs:
       run: cargo clippy --no-default-features -- -D warnings
     - name: Clippy (alter-table)
       run: cargo clippy --features alter-table -- -D warnings
+    - name: Clippy (index)
+      run: cargo clippy --features index -- -D warnings
     - name: Clippy (sled-storage)
       run: cargo clippy --features sled-storage -- -D warnings
     - name: Clippy (all)
diff --git a/Cargo.toml b/Cargo.toml
index 456e1199..88bfdcd7 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -14,12 +14,15 @@ keywords = ["sql-database", "sql", "functional", "no-mut-in-the-middle", "webass
 all-features = true
 
 [features]
-default = ["sled-storage", "alter-table"]
+default = ["sled-storage", "alter-table", "index"]
 
 # ALTER TABLE is optional.
 # You can include whether ALTER TABLE support or not for your custom database implementation.
 alter-table = []
 
+# INDEX is also optional.
+index = []
+
 # Who wants to make a custom storage engine,
 # default storage engine sled-storage is not required.
 sled-storage = ["sled", "bincode"]
@@ -28,6 +31,7 @@ sled-storage = ["sled", "bincode"]
 async-trait = "0.1.41"
 async-recursion = "0.3.1"
 boolinator = "2.4.0"
+cfg-if = "1"
 chrono = { version = "0.4", features = ["serde", "wasmbind"] }
 rust_decimal = "1.13"
 futures = "0.3"
diff --git a/src/ast/mod.rs b/src/ast/mod.rs
index 296bac8f..e1b02576 100644
--- a/src/ast/mod.rs
+++ b/src/ast/mod.rs
@@ -11,7 +11,7 @@ pub use data_type::DataType;
 pub use ddl::*;
 pub use expr::Expr;
 pub use function::{Function, FunctionArg};
-pub use operator::{BinaryOperator, UnaryOperator};
+pub use operator::*;
 pub use query::*;
 
 use serde::{Deserialize, Serialize};
@@ -63,13 +63,26 @@ pub enum Statement {
         name: ObjectName,
         operation: AlterTableOperation,
     },
-    /// DROP
+    /// DROP TABLE
     DropTable {
         /// An optional `IF EXISTS` clause. (Non-standard.)
         if_exists: bool,
         /// One or more objects to drop. (ANSI SQL requires exactly one.)
         names: Vec<ObjectName>,
     },
+    /// CREATE INDEX
+    #[cfg(feature = "index")]
+    CreateIndex {
+        name: ObjectName,
+        table_name: ObjectName,
+        column: Expr,
+    },
+    /// DROP INDEX
+    #[cfg(feature = "index")]
+    DropIndex {
+        name: ObjectName,
+        table_name: ObjectName,
+    },
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
diff --git a/src/ast/operator.rs b/src/ast/operator.rs
index 852fd0c5..062ef135 100644
--- a/src/ast/operator.rs
+++ b/src/ast/operator.rs
@@ -23,3 +23,38 @@ pub enum BinaryOperator {
     And,
     Or,
 }
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
+pub enum IndexOperator {
+    Gt,
+    Lt,
+    GtEq,
+    LtEq,
+    Eq,
+}
+
+impl IndexOperator {
+    pub fn reverse(self) -> Self {
+        use IndexOperator::*;
+
+        match self {
+            Gt => Lt,
+            Lt => Gt,
+            GtEq => LtEq,
+            LtEq => GtEq,
+            Eq => Eq,
+        }
+    }
+}
+
+impl From<IndexOperator> for BinaryOperator {
+    fn from(index_op: IndexOperator) -> Self {
+        match index_op {
+            IndexOperator::Gt => BinaryOperator::Gt,
+            IndexOperator::Lt => BinaryOperator::Lt,
+            IndexOperator::GtEq => BinaryOperator::GtEq,
+            IndexOperator::LtEq => BinaryOperator::LtEq,
+            IndexOperator::Eq => BinaryOperator::Eq,
+        }
+    }
+}
diff --git a/src/ast/query.rs b/src/ast/query.rs
index 27df510b..6ccf04c1 100644
--- a/src/ast/query.rs
+++ b/src/ast/query.rs
@@ -1,5 +1,5 @@
 use {
-    super::{Expr, ObjectName},
+    super::{Expr, IndexOperator, ObjectName},
     serde::{Deserialize, Serialize},
 };
 
@@ -19,7 +19,7 @@ pub enum SetExpr {
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub struct Select {
     pub projection: Vec<SelectItem>,
-    pub from: Vec<TableWithJoins>,
+    pub from: TableWithJoins,
     /// WHERE
     pub selection: Option<Expr>,
     pub group_by: Vec<Expr>,
@@ -42,11 +42,20 @@ pub struct TableWithJoins {
     pub joins: Vec<Join>,
 }
 
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
+pub struct IndexItem {
+    pub name: String,
+    pub op: IndexOperator,
+    pub value_expr: Expr,
+}
+
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub enum TableFactor {
     Table {
         name: ObjectName,
         alias: Option<TableAlias>,
+        /// Query planner result
+        index: Option<IndexItem>,
     },
 }
 
diff --git a/src/data/schema.rs b/src/data/schema.rs
index 9c28b36e..22d1759f 100644
--- a/src/data/schema.rs
+++ b/src/data/schema.rs
@@ -7,6 +7,7 @@ use {
 pub struct Schema {
     pub table_name: String,
     pub column_defs: Vec<ColumnDef>,
+    pub indexes: Vec<(String, Expr)>,
 }
 
 pub trait ColumnDefExt {
diff --git a/src/data/table.rs b/src/data/table.rs
index 5ce36ef7..b5f3f80c 100644
--- a/src/data/table.rs
+++ b/src/data/table.rs
@@ -1,6 +1,6 @@
 use {
     crate::{
-        ast::{ObjectName, TableAlias, TableFactor},
+        ast::{IndexItem, ObjectName, TableAlias, TableFactor},
         result::Result,
     },
     serde::Serialize,
@@ -17,16 +17,18 @@ pub enum TableError {
 pub struct Table<'a> {
     name: &'a String,
     alias: Option<&'a String>,
+    index: Option<&'a IndexItem>,
 }
 
 impl<'a> Table<'a> {
     pub fn new(table_factor: &'a TableFactor) -> Result<Self> {
         match table_factor {
-            TableFactor::Table { name, alias } => {
+            TableFactor::Table { name, alias, index } => {
                 let name = get_name(name)?;
                 let alias = alias.as_ref().map(|TableAlias { name, .. }| name);
+                let index = index.as_ref();
 
-                Ok(Self { name, alias })
+                Ok(Self { name, alias, index })
             }
         }
     }
@@ -41,6 +43,10 @@ impl<'a> Table<'a> {
             None => self.name,
         }
     }
+
+    pub fn get_index(&self) -> Option<&'a IndexItem> {
+        self.index
+    }
 }
 
 pub fn get_name(table_name: &ObjectName) -> Result<&String> {
diff --git a/src/data/value/big_edian.rs b/src/data/value/big_edian.rs
new file mode 100644
index 00000000..4dd0c2ff
--- /dev/null
+++ b/src/data/value/big_edian.rs
@@ -0,0 +1,189 @@
+use {
+    super::Value,
+    crate::data::Interval,
+    chrono::{Datelike, Timelike},
+};
+
+const VALUE: u8 = 0;
+const NULL: u8 = 1;
+
+impl Value {
+    pub fn to_be_bytes(&self) -> Vec<u8> {
+        match self {
+            Value::Bool(v) => {
+                if *v {
+                    vec![VALUE, 1]
+                } else {
+                    vec![VALUE, 0]
+                }
+            }
+            Value::I64(v) => [VALUE]
+                .iter()
+                .chain(v.to_be_bytes().iter())
+                .copied()
+                .collect::<Vec<_>>(),
+            Value::F64(v) => [VALUE]
+                .iter()
+                .chain(v.to_be_bytes().iter())
+                .copied()
+                .collect::<Vec<_>>(),
+            Value::Str(v) => [VALUE]
+                .iter()
+                .chain(v.as_bytes().iter())
+                .copied()
+                .collect::<Vec<_>>(),
+            Value::Date(date) => [VALUE]
+                .iter()
+                .chain(date.num_days_from_ce().to_be_bytes().iter())
+                .copied()
+                .collect::<Vec<_>>(),
+            Value::Time(time) => {
+                let secs = time.num_seconds_from_midnight();
+                let frac = time.nanosecond();
+
+                [VALUE]
+                    .iter()
+                    .chain(secs.to_be_bytes().iter())
+                    .chain(frac.to_be_bytes().iter())
+                    .copied()
+                    .collect::<Vec<_>>()
+            }
+            Value::Timestamp(datetime) => {
+                let date = datetime.num_days_from_ce();
+                let secs = datetime.num_seconds_from_midnight();
+                let frac = datetime.nanosecond();
+
+                [VALUE]
+                    .iter()
+                    .chain(date.to_be_bytes().iter())
+                    .chain(secs.to_be_bytes().iter())
+                    .chain(frac.to_be_bytes().iter())
+                    .copied()
+                    .collect::<Vec<_>>()
+            }
+            Value::Interval(interval) => {
+                let (month, microsec) = match interval {
+                    Interval::Month(month) => (*month, 0),
+                    Interval::Microsecond(microsec) => (0, *microsec),
+                };
+
+                [VALUE]
+                    .iter()
+                    .chain(month.to_be_bytes().iter())
+                    .chain(microsec.to_be_bytes().iter())
+                    .copied()
+                    .collect::<Vec<_>>()
+            }
+            Value::Null => vec![NULL],
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::cmp::Ordering;
+
+    fn cmp(ls: &[u8], rs: &[u8]) -> Ordering {
+        for (l, r) in ls.iter().zip(rs.iter()) {
+            if l > r {
+                return Ordering::Greater;
+            } else if l < r {
+                return Ordering::Less;
+            }
+        }
+
+        let size_l = ls.len();
+        let size_r = rs.len();
+
+        if size_l == size_r {
+            return Ordering::Equal;
+        } else if size_l > size_r {
+            return Ordering::Greater;
+        } else {
+            return Ordering::Less;
+        }
+    }
+
+    #[test]
+    fn cmp_big_edian() {
+        use crate::{
+            chrono::{NaiveDate, NaiveTime},
+            data::{Interval as I, Value::*},
+        };
+
+        let null = Null.to_be_bytes();
+
+        let n1 = Bool(true).to_be_bytes();
+        let n2 = Bool(false).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Greater);
+        assert_eq!(cmp(&n2, &n1), Ordering::Less);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = I64(3).to_be_bytes();
+        let n2 = I64(20).to_be_bytes();
+        let n3 = I64(100).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Less);
+        assert_eq!(cmp(&n3, &n1), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = F64(3.0).to_be_bytes();
+        let n2 = F64(100.0).to_be_bytes();
+        let n3 = F64(1324.0).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Less);
+        assert_eq!(cmp(&n3, &n1), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = Str("a".to_owned()).to_be_bytes();
+        let n2 = Str("ab".to_owned()).to_be_bytes();
+        let n3 = Str("aaa".to_owned()).to_be_bytes();
+        let n4 = Str("aaz".to_owned()).to_be_bytes();
+        let n5 = Str("c".to_owned()).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Less);
+        assert_eq!(cmp(&n3, &n1), Ordering::Greater);
+        assert_eq!(cmp(&n2, &n3), Ordering::Greater);
+        assert_eq!(cmp(&n3, &n4), Ordering::Less);
+        assert_eq!(cmp(&n5, &n4), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = Date(NaiveDate::from_ymd(2021, 1, 1)).to_be_bytes();
+        let n2 = Date(NaiveDate::from_ymd(1989, 3, 20)).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = Time(NaiveTime::from_hms_milli(20, 1, 9, 100)).to_be_bytes();
+        let n2 = Time(NaiveTime::from_hms_milli(3, 10, 30, 0)).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = Timestamp(NaiveDate::from_ymd(2021, 1, 1).and_hms_milli(1, 2, 3, 0)).to_be_bytes();
+        let n2 =
+            Timestamp(NaiveDate::from_ymd(1989, 3, 20).and_hms_milli(10, 0, 0, 1000)).to_be_bytes();
+
+        assert_eq!(cmp(&n2, &n2), Ordering::Equal);
+        assert_eq!(cmp(&n1, &n2), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+
+        let n1 = Interval(I::Month(30)).to_be_bytes();
+        let n2 = Interval(I::Month(2)).to_be_bytes();
+        let n3 = Interval(I::Microsecond(1000)).to_be_bytes();
+        let n4 = Interval(I::Microsecond(30)).to_be_bytes();
+
+        assert_eq!(cmp(&n1, &n1), Ordering::Equal);
+        assert_eq!(cmp(&n2, &n1), Ordering::Less);
+        assert_eq!(cmp(&n2, &n3), Ordering::Greater);
+        assert_eq!(cmp(&n3, &n4), Ordering::Greater);
+        assert_eq!(cmp(&n1, &null), Ordering::Less);
+    }
+}
diff --git a/src/data/value/mod.rs b/src/data/value/mod.rs
index 56c5703a..9b68a450 100644
--- a/src/data/value/mod.rs
+++ b/src/data/value/mod.rs
@@ -14,6 +14,7 @@ use {
     },
 };
 
+mod big_edian;
 mod error;
 mod group_key;
 mod into;
diff --git a/src/executor/aggregate/mod.rs b/src/executor/aggregate/mod.rs
index 3032c60d..9b816be4 100644
--- a/src/executor/aggregate/mod.rs
+++ b/src/executor/aggregate/mod.rs
@@ -13,7 +13,7 @@ use {
         ast::{Expr, Function, FunctionArg, SelectItem},
         data::{get_name, Value},
         result::{Error, Result},
-        store::Store,
+        store::GStore,
     },
     boolinator::Boolinator,
     futures::stream::{self, StreamExt, TryStream, TryStreamExt},
@@ -23,7 +23,7 @@ use {
 pub use {error::AggregateError, hash::GroupKey};
 
 pub struct Aggregate<'a, T: 'static + Debug> {
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     fields: &'a [SelectItem],
     group_by: &'a [Expr],
     having: Option<&'a Expr>,
@@ -35,7 +35,7 @@ type Applied<'a> = dyn TryStream<Ok = AggregateContext<'a>, Error = Error, Item
 
 impl<'a, T: 'static + Debug> Aggregate<'a, T> {
     pub fn new(
-        storage: &'a dyn Store<T>,
+        storage: &'a dyn GStore<T>,
         fields: &'a [SelectItem],
         group_by: &'a [Expr],
         having: Option<&'a Expr>,
diff --git a/src/executor/alter/create_table.rs b/src/executor/alter/create_table.rs
index 6714d156..1812f4c3 100644
--- a/src/executor/alter/create_table.rs
+++ b/src/executor/alter/create_table.rs
@@ -4,12 +4,12 @@ use {
         ast::{ColumnDef, ObjectName},
         data::{get_name, Schema},
         result::MutResult,
-        store::{AlterTable, Store, StoreMut},
+        store::{GStore, GStoreMut},
     },
     std::fmt::Debug,
 };
 
-pub async fn create_table<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
+pub async fn create_table<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
     storage: U,
     name: &ObjectName,
     column_defs: &[ColumnDef],
@@ -19,6 +19,7 @@ pub async fn create_table<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterT
         let schema = Schema {
             table_name: get_name(name)?.to_string(),
             column_defs: column_defs.to_vec(),
+            indexes: vec![],
         };
 
         for column_def in &schema.column_defs {
diff --git a/src/executor/alter/drop.rs b/src/executor/alter/drop.rs
index eeea16ef..8dfb7f84 100644
--- a/src/executor/alter/drop.rs
+++ b/src/executor/alter/drop.rs
@@ -4,13 +4,13 @@ use {
         ast::ObjectName,
         data::get_name,
         result::MutResult,
-        store::{AlterTable, Store, StoreMut},
+        store::{GStore, GStoreMut},
     },
     futures::stream::{self, TryStreamExt},
     std::fmt::Debug,
 };
 
-pub async fn drop<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
+pub async fn drop<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
     storage: U,
     names: &[ObjectName],
     if_exists: bool,
diff --git a/src/executor/blend.rs b/src/executor/blend.rs
index 14e02c58..1d9b8ba6 100644
--- a/src/executor/blend.rs
+++ b/src/executor/blend.rs
@@ -7,7 +7,7 @@ use {
         ast::{Function, SelectItem},
         data::{get_name, Row, Value},
         result::{Error, Result},
-        store::Store,
+        store::GStore,
     },
     futures::stream::{self, StreamExt, TryStreamExt},
     im_rc::HashMap,
@@ -24,12 +24,12 @@ pub enum BlendError {
 }
 
 pub struct Blend<'a, T: 'static + Debug> {
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     fields: &'a [SelectItem],
 }
 
 impl<'a, T: 'static + Debug> Blend<'a, T> {
-    pub fn new(storage: &'a dyn Store<T>, fields: &'a [SelectItem]) -> Self {
+    pub fn new(storage: &'a dyn GStore<T>, fields: &'a [SelectItem]) -> Self {
         Self { storage, fields }
     }
 
diff --git a/src/executor/evaluate/error.rs b/src/executor/evaluate/error.rs
index 6249aca2..c01fb09b 100644
--- a/src/executor/evaluate/error.rs
+++ b/src/executor/evaluate/error.rs
@@ -36,8 +36,11 @@ pub enum EvaluateError {
     #[error("unsupported compound identifier {0}")]
     UnsupportedCompoundIdentifier(String),
 
-    #[error("unimplemented")]
-    Unimplemented,
+    #[error("unreachable wildcard expression")]
+    UnreachableWildcardExpr,
+
+    #[error("unsupported stateless expression: {0}")]
+    UnsupportedStatelessExpr(String),
 
     #[error("unreachable empty context")]
     UnreachableEmptyContext,
diff --git a/src/executor/evaluate/expr.rs b/src/executor/evaluate/expr.rs
new file mode 100644
index 00000000..ef6d7b05
--- /dev/null
+++ b/src/executor/evaluate/expr.rs
@@ -0,0 +1,80 @@
+use {
+    super::Evaluated,
+    crate::{
+        ast::{AstLiteral, BinaryOperator, DataType, UnaryOperator},
+        data::{Literal, Value},
+        result::Result,
+    },
+    std::{
+        borrow::Cow,
+        convert::{TryFrom, TryInto},
+    },
+};
+
+pub fn literal(ast_literal: &AstLiteral) -> Result<Evaluated<'_>> {
+    Literal::try_from(ast_literal).map(Evaluated::Literal)
+}
+
+pub fn typed_string<'a>(data_type: &'a DataType, value: Cow<'a, String>) -> Result<Evaluated<'a>> {
+    let literal = Literal::Text(value);
+
+    Value::try_from_literal(&data_type, &literal).map(Evaluated::from)
+}
+
+pub fn binary_op<'a>(
+    op: &BinaryOperator,
+    l: Evaluated<'a>,
+    r: Evaluated<'a>,
+) -> Result<Evaluated<'a>> {
+    macro_rules! cmp {
+        ($expr: expr) => {
+            Ok(Evaluated::from(Value::Bool($expr)))
+        };
+    }
+
+    macro_rules! cond {
+        (l $op: tt r) => {{
+            let l: bool = l.try_into()?;
+            let r: bool = r.try_into()?;
+            let v = l $op r;
+
+            Ok(Evaluated::from(Value::Bool(v)))
+        }};
+    }
+
+    match op {
+        BinaryOperator::Plus => l.add(&r),
+        BinaryOperator::Minus => l.subtract(&r),
+        BinaryOperator::Multiply => l.multiply(&r),
+        BinaryOperator::Divide => l.divide(&r),
+        BinaryOperator::StringConcat => l.concat(r),
+        BinaryOperator::Eq => cmp!(l == r),
+        BinaryOperator::NotEq => cmp!(l != r),
+        BinaryOperator::Lt => cmp!(l < r),
+        BinaryOperator::LtEq => cmp!(l <= r),
+        BinaryOperator::Gt => cmp!(l > r),
+        BinaryOperator::GtEq => cmp!(l >= r),
+        BinaryOperator::And => cond!(l && r),
+        BinaryOperator::Or => cond!(l || r),
+    }
+}
+
+pub fn unary_op<'a>(op: &UnaryOperator, v: Evaluated<'a>) -> Result<Evaluated<'a>> {
+    match op {
+        UnaryOperator::Plus => v.unary_plus(),
+        UnaryOperator::Minus => v.unary_minus(),
+        UnaryOperator::Not => v.try_into().map(|v: bool| Evaluated::from(Value::Bool(!v))),
+    }
+}
+
+pub fn between<'a>(
+    target: Evaluated<'a>,
+    negated: bool,
+    low: Evaluated<'a>,
+    high: Evaluated<'a>,
+) -> Result<Evaluated<'a>> {
+    let v = low <= target && target <= high;
+    let v = negated ^ v;
+
+    Ok(Evaluated::from(Value::Bool(v)))
+}
diff --git a/src/executor/evaluate/mod.rs b/src/executor/evaluate/mod.rs
index 496bb0a5..615bfe30 100644
--- a/src/executor/evaluate/mod.rs
+++ b/src/executor/evaluate/mod.rs
@@ -1,13 +1,15 @@
 mod error;
 mod evaluated;
+mod expr;
+mod stateless;
 
 use {
     super::{context::FilterContext, select::select},
     crate::{
-        ast::{BinaryOperator, Expr, Function, FunctionArg, UnaryOperator},
-        data::{get_name, Literal, Value},
+        ast::{Expr, Function, FunctionArg},
+        data::{get_name, Value},
         result::Result,
-        store::Store,
+        store::GStore,
     },
     async_recursion::async_recursion,
     boolinator::Boolinator,
@@ -21,11 +23,11 @@ use {
     },
 };
 
-pub use {error::EvaluateError, evaluated::Evaluated};
+pub use {error::EvaluateError, evaluated::Evaluated, stateless::evaluate_stateless};
 
 #[async_recursion(?Send)]
 pub async fn evaluate<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     context: Option<Rc<FilterContext<'a>>>,
     aggregated: Option<Rc<HashMap<&'a Function, Value>>>,
     expr: &'a Expr,
@@ -39,11 +41,9 @@ pub async fn evaluate<'a, T: 'static + Debug>(
     };
 
     match expr {
-        Expr::Literal(ast_literal) => Literal::try_from(ast_literal).map(Evaluated::Literal),
+        Expr::Literal(ast_literal) => expr::literal(ast_literal),
         Expr::TypedString { data_type, value } => {
-            let literal = Literal::Text(Cow::Borrowed(value));
-
-            Value::try_from_literal(&data_type, &literal).map(Evaluated::from)
+            expr::typed_string(data_type, Cow::Borrowed(&value))
         }
         Expr::Identifier(ident) => {
             let context = context.ok_or(EvaluateError::UnreachableEmptyContext)?;
@@ -84,49 +84,15 @@ pub async fn evaluate<'a, T: 'static + Debug>(
             .next()
             .unwrap_or_else(|| Err(EvaluateError::NestedSelectRowNotFound.into()))?,
         Expr::BinaryOp { op, left, right } => {
-            let l = eval(left).await?;
-            let r = eval(right).await?;
-
-            macro_rules! cmp {
-                ($expr: expr) => {
-                    Ok(Evaluated::from(Value::Bool($expr)))
-                };
-            }
-
-            macro_rules! cond {
-                (l $op: tt r) => {{
-                    let l: bool = l.try_into()?;
-                    let r: bool = r.try_into()?;
-                    let v = l $op r;
-
-                    Ok(Evaluated::from(Value::Bool(v)))
-                }};
-            }
+            let left = eval(left).await?;
+            let right = eval(right).await?;
 
-            match op {
-                BinaryOperator::Plus => l.add(&r),
-                BinaryOperator::Minus => l.subtract(&r),
-                BinaryOperator::Multiply => l.multiply(&r),
-                BinaryOperator::Divide => l.divide(&r),
-                BinaryOperator::StringConcat => l.concat(r),
-                BinaryOperator::Eq => cmp!(l == r),
-                BinaryOperator::NotEq => cmp!(l != r),
-                BinaryOperator::Lt => cmp!(l < r),
-                BinaryOperator::LtEq => cmp!(l <= r),
-                BinaryOperator::Gt => cmp!(l > r),
-                BinaryOperator::GtEq => cmp!(l >= r),
-                BinaryOperator::And => cond!(l && r),
-                BinaryOperator::Or => cond!(l || r),
-            }
+            expr::binary_op(op, left, right)
         }
         Expr::UnaryOp { op, expr } => {
             let v = eval(expr).await?;
 
-            match op {
-                UnaryOperator::Plus => v.unary_plus(),
-                UnaryOperator::Minus => v.unary_minus(),
-                UnaryOperator::Not => v.try_into().map(|v: bool| Evaluated::from(Value::Bool(!v))),
-            }
+            expr::unary_op(op, v)
         }
         Expr::Function(func) => match aggregated.as_ref().map(|aggr| aggr.get(func)).flatten() {
             Some(value) => Ok(Evaluated::from(value.clone())),
@@ -201,13 +167,11 @@ pub async fn evaluate<'a, T: 'static + Debug>(
             low,
             high,
         } => {
-            let negated = *negated;
             let target = eval(expr).await?;
+            let low = eval(low).await?;
+            let high = eval(high).await?;
 
-            let v = eval(low).await? <= target && target <= eval(high).await?;
-            let v = negated ^ v;
-
-            Ok(Evaluated::from(Value::Bool(v)))
+            expr::between(target, *negated, low, high)
         }
         Expr::Exists(query) => {
             let v = select(storage, query, context)
@@ -231,12 +195,14 @@ pub async fn evaluate<'a, T: 'static + Debug>(
 
             Ok(Evaluated::from(Value::Bool(!v)))
         }
-        _ => Err(EvaluateError::Unimplemented.into()),
+        Expr::Wildcard | Expr::QualifiedWildcard(_) => {
+            Err(EvaluateError::UnreachableWildcardExpr.into())
+        }
     }
 }
 
 async fn evaluate_function<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     context: Option<Rc<FilterContext<'a>>>,
     aggregated: Option<Rc<HashMap<&'a Function, Value>>>,
     func: &'a Function,
diff --git a/src/executor/evaluate/shared.rs b/src/executor/evaluate/shared.rs
new file mode 100644
index 00000000..e69de29b
diff --git a/src/executor/evaluate/stateless.rs b/src/executor/evaluate/stateless.rs
new file mode 100644
index 00000000..050b4ac1
--- /dev/null
+++ b/src/executor/evaluate/stateless.rs
@@ -0,0 +1,110 @@
+use {
+    super::{expr, EvaluateError, Evaluated},
+    crate::{
+        ast::Expr,
+        data::{Row, Value},
+        result::Result,
+    },
+    boolinator::Boolinator,
+    std::borrow::Cow,
+};
+
+type Columns<'a> = &'a [String];
+
+pub fn evaluate_stateless<'a>(
+    context: Option<(Columns, &'a Row)>,
+    expr: &'a Expr,
+) -> Result<Evaluated<'a>> {
+    let eval = |expr| evaluate_stateless(context, expr);
+
+    match expr {
+        Expr::Literal(ast_literal) => expr::literal(ast_literal),
+        Expr::TypedString { data_type, value } => {
+            expr::typed_string(data_type, Cow::Borrowed(&value))
+        }
+        Expr::Identifier(ident) => {
+            let (columns, row) = match context {
+                Some(context) => context,
+                None => {
+                    return Err(EvaluateError::ValueNotFound(ident.to_owned()).into());
+                }
+            };
+
+            let value = columns
+                .iter()
+                .position(|column| column == ident)
+                .map(|index| row.get_value(index))
+                .flatten();
+
+            match value {
+                Some(value) => Ok(value.clone()),
+                None => Err(EvaluateError::ValueNotFound(ident.to_owned()).into()),
+            }
+            .map(Evaluated::from)
+        }
+        Expr::Nested(expr) => eval(&expr),
+        Expr::BinaryOp { op, left, right } => {
+            let left = eval(left)?;
+            let right = eval(right)?;
+
+            expr::binary_op(op, left, right)
+        }
+        Expr::UnaryOp { op, expr } => {
+            let v = eval(expr)?;
+
+            expr::unary_op(op, v)
+        }
+        Expr::Cast { expr, data_type } => eval(expr)?.cast(data_type),
+        Expr::InList {
+            expr,
+            list,
+            negated,
+        } => {
+            let negated = *negated;
+            let target = eval(expr)?;
+
+            list.iter()
+                .filter_map(|expr| {
+                    let target = &target;
+
+                    eval(expr).map_or_else(
+                        |error| Some(Err(error)),
+                        |evaluated| (target == &evaluated).as_some(Ok(!negated)),
+                    )
+                })
+                .take(1)
+                .collect::<Vec<_>>()
+                .into_iter()
+                .next()
+                .unwrap_or(Ok(negated))
+                .map(Value::Bool)
+                .map(Evaluated::from)
+        }
+        Expr::Between {
+            expr,
+            negated,
+            low,
+            high,
+        } => {
+            let target = eval(expr)?;
+            let low = eval(low)?;
+            let high = eval(high)?;
+
+            expr::between(target, *negated, low, high)
+        }
+        Expr::IsNull(expr) => {
+            let v = eval(expr)?.is_null();
+
+            Ok(Evaluated::from(Value::Bool(v)))
+        }
+        Expr::IsNotNull(expr) => {
+            let v = eval(expr)?.is_null();
+
+            Ok(Evaluated::from(Value::Bool(!v)))
+        }
+        Expr::Wildcard | Expr::QualifiedWildcard(_) => {
+            Err(EvaluateError::UnreachableWildcardExpr.into())
+        }
+        _ => Err(EvaluateError::UnsupportedStatelessExpr(format!("{:#?}", expr)).into()),
+    }
+}
diff --git a/src/executor/execute.rs b/src/executor/execute.rs
index da65363d..1293d9f4 100644
--- a/src/executor/execute.rs
+++ b/src/executor/execute.rs
@@ -10,7 +10,7 @@ use {
         ast::{Query, SetExpr, Statement, Values},
         data::{get_name, Row, Schema},
         result::{MutResult, Result},
-        store::{AlterTable, Store, StoreMut},
+        store::{GStore, GStoreMut},
     },
     futures::stream::TryStreamExt,
     serde::Serialize,
@@ -41,9 +41,15 @@ pub enum Payload {
 
     #[cfg(feature = "alter-table")]
     AlterTable,
+
+    #[cfg(feature = "index")]
+    CreateIndex,
+
+    #[cfg(feature = "index")]
+    DropIndex,
 }
 
-pub async fn execute<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
+pub async fn execute<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
     storage: U,
     statement: &Statement,
 ) -> MutResult<U, Payload> {
@@ -78,7 +84,38 @@ pub async fn execute<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>
         Statement::AlterTable { name, operation } => alter_table(storage, name, operation)
             .await
             .map(|(storage, _)| (storage, Payload::AlterTable)),
+        #[cfg(feature = "index")]
+        Statement::CreateIndex {
+            name,
+            table_name,
+            column,
+        } => {
+            let (table_name, index_name) = try_block!(storage, {
+                let index_name = get_name(name)?;
+                let table_name = get_name(table_name)?;
+
+                Ok((table_name, index_name))
+            });
+
+            storage
+                .create_index(table_name, index_name, column)
+                .await
+                .map(|(storage, _)| (storage, Payload::CreateIndex))
+        }
+        #[cfg(feature = "index")]
+        Statement::DropIndex { name, table_name } => {
+            let (table_name, index_name) = try_block!(storage, {
+                let index_name = get_name(name)?;
+                let table_name = get_name(table_name)?;
+
+                Ok((table_name, index_name))
+            });
 
+            storage
+                .drop_index(table_name, index_name)
+                .await
+                .map(|(storage, _)| (storage, Payload::DropIndex))
+        }
         //-- Rows
         Statement::Insert {
             table_name,
@@ -140,7 +177,7 @@ pub async fn execute<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>
             selection,
             assignments,
         } => {
-            let rows = try_block!(storage, {
+            let (table_name, rows) = try_block!(storage, {
                 let table_name = get_name(table_name)?;
                 let Schema { column_defs, .. } = storage
                     .fetch_schema(table_name)
@@ -174,11 +211,13 @@ pub async fn execute<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>
                 )
                 .await?;
 
-                Ok(rows)
+                Ok((table_name, rows))
             });
+
             let num_rows = rows.len();
+
             storage
-                .update_data(rows)
+                .update_data(table_name, rows)
                 .await
                 .map(|(storage, _)| (storage, Payload::Update(num_rows)))
         }
@@ -186,21 +225,23 @@ pub async fn execute<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>
             table_name,
             selection,
         } => {
-            let keys = try_block!(storage, {
+            let (table_name, keys) = try_block!(storage, {
                 let table_name = get_name(&table_name)?;
                 let columns = Rc::from(fetch_columns(&storage, table_name).await?);
 
-                fetch(&storage, table_name, columns, selection.as_ref())
+                let keys = fetch(&storage, table_name, columns, selection.as_ref())
                     .await?
                     .map_ok(|(_, key, _)| key)
                     .try_collect::<Vec<_>>()
-                    .await
+                    .await?;
+
+                Ok((table_name, keys))
             });
 
             let num_keys = keys.len();
 
             storage
-                .delete_data(keys)
+                .delete_data(table_name, keys)
                 .await
                 .map(|(storage, _)| (storage, Payload::Delete(num_keys)))
         }
diff --git a/src/executor/fetch.rs b/src/executor/fetch.rs
index 85093a08..5a644f69 100644
--- a/src/executor/fetch.rs
+++ b/src/executor/fetch.rs
@@ -4,7 +4,7 @@ use {
         ast::{ColumnDef, Expr},
         data::Row,
         result::{Error, Result},
-        store::Store,
+        store::GStore,
     },
     boolinator::Boolinator,
     futures::stream::{self, TryStream, TryStreamExt},
@@ -20,7 +20,7 @@ pub enum FetchError {
 }
 
 pub async fn fetch_columns<T: 'static + Debug>(
-    storage: &dyn Store<T>,
+    storage: &dyn GStore<T>,
     table_name: &str,
 ) -> Result<Vec<String>> {
     Ok(storage
@@ -34,7 +34,7 @@ pub async fn fetch_columns<T: 'static + Debug>(
 }
 
 pub async fn fetch<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     table_name: &'a str,
     columns: Rc<[String]>,
     where_clause: Option<&'a Expr>,
diff --git a/src/executor/filter.rs b/src/executor/filter.rs
index e2707262..95f2cfe9 100644
--- a/src/executor/filter.rs
+++ b/src/executor/filter.rs
@@ -7,14 +7,14 @@ use {
         ast::{Expr, Function},
         data::Value,
         result::Result,
-        store::Store,
+        store::GStore,
     },
     im_rc::HashMap,
     std::{convert::TryInto, fmt::Debug, rc::Rc},
 };
 
 pub struct Filter<'a, T: 'static + Debug> {
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     where_clause: Option<&'a Expr>,
     context: Option<Rc<FilterContext<'a>>>,
     aggregated: Option<Rc<HashMap<&'a Function, Value>>>,
@@ -22,7 +22,7 @@ pub struct Filter<'a, T: 'static + Debug> {
 
 impl<'a, T: 'static + Debug> Filter<'a, T> {
     pub fn new(
-        storage: &'a dyn Store<T>,
+        storage: &'a dyn GStore<T>,
         where_clause: Option<&'a Expr>,
         context: Option<Rc<FilterContext<'a>>>,
         aggregated: Option<Rc<HashMap<&'a Function, Value>>>,
@@ -51,7 +51,7 @@ impl<'a, T: 'static + Debug> Filter<'a, T> {
 }
 
 pub async fn check_expr<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     context: Option<Rc<FilterContext<'a>>>,
     aggregated: Option<Rc<HashMap<&'a Function, Value>>>,
     expr: &'a Expr,
diff --git a/src/executor/join.rs b/src/executor/join.rs
index e5498acb..5ca6d266 100644
--- a/src/executor/join.rs
+++ b/src/executor/join.rs
@@ -7,7 +7,7 @@ use {
         ast::{Join as AstJoin, JoinConstraint, JoinOperator},
         data::Table,
         result::{Error, Result},
-        store::Store,
+        store::GStore,
         utils::OrStream,
     },
     boolinator::Boolinator,
@@ -16,7 +16,7 @@ use {
 };
 
 pub struct Join<'a, T: 'static + Debug> {
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     join_clauses: &'a [AstJoin],
     filter_context: Option<Rc<FilterContext<'a>>>,
 }
@@ -27,7 +27,7 @@ type Joined<'a> =
 
 impl<'a, T: 'static + Debug> Join<'a, T> {
     pub fn new(
-        storage: &'a dyn Store<T>,
+        storage: &'a dyn GStore<T>,
         join_clauses: &'a [AstJoin],
         filter_context: Option<Rc<FilterContext<'a>>>,
     ) -> Self {
@@ -83,7 +83,7 @@ impl<'a, T: 'static + Debug> Join<'a, T> {
 }
 
 async fn join<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     filter_context: Option<Rc<FilterContext<'a>>>,
     ast_join: &'a AstJoin,
     columns: Rc<[String]>,
@@ -133,7 +133,7 @@ async fn join<'a, T: 'static + Debug>(
 }
 
 async fn fetch_joined<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     table_name: &'a str,
     table_alias: &'a str,
     columns: Rc<[String]>,
diff --git a/src/executor/mod.rs b/src/executor/mod.rs
index 4e4c1441..cad581c8 100644
--- a/src/executor/mod.rs
+++ b/src/executor/mod.rs
@@ -15,7 +15,7 @@ mod validate;
 pub use aggregate::{AggregateError, GroupKey};
 pub use alter::AlterError;
 pub use blend::BlendError;
-pub use evaluate::EvaluateError;
+pub use evaluate::{evaluate_stateless, EvaluateError};
 pub use execute::{execute, ExecuteError, Payload};
 pub use fetch::FetchError;
 pub use limit::LimitError;
diff --git a/src/executor/select.rs b/src/executor/select.rs
index 8fb0eb4d..096771ce 100644
--- a/src/executor/select.rs
+++ b/src/executor/select.rs
@@ -12,7 +12,7 @@ use {
         ast::{Query, SelectItem, SetExpr, TableWithJoins},
         data::{get_name, Row, Table},
         result::{Error, Result},
-        store::Store,
+        store::GStore,
     },
     boolinator::Boolinator,
     futures::stream::{self, Stream, StreamExt, TryStream, TryStreamExt},
@@ -22,11 +22,15 @@ use {
     thiserror::Error as ThisError,
 };
 
+#[cfg(feature = "index")]
+use {
+    super::evaluate::evaluate,
+    crate::{ast::IndexItem, data::Value},
+    std::convert::TryInto,
+};
+
 #[derive(ThisError, Serialize, Debug, PartialEq)]
 pub enum SelectError {
-    #[error("unimplemented! select on two or more than tables are not supported")]
-    TooManyTables,
-
     #[error("table alias not found: {0}")]
     TableAliasNotFound(String),
 
@@ -35,11 +39,41 @@ pub enum SelectError {
 }
 
 async fn fetch_blended<'a, T: 'static + Debug>(
-    storage: &dyn Store<T>,
+    storage: &dyn GStore<T>,
     table: Table<'a>,
     columns: Rc<[String]>,
 ) -> Result<impl Stream<Item = Result<BlendContext<'a>>> + 'a> {
-    let rows = storage.scan_data(table.get_name()).await?.map(move |data| {
+    let table_name = table.get_name();
+
+    #[cfg(feature = "index")]
+    let rows = {
+        #[derive(Iterator)]
+        enum Rows<I1, I2> {
+            FullScan(I1),
+            Indexed(I2),
+        }
+
+        match table.get_index() {
+            Some(IndexItem {
+                name: index_name,
+                op: index_op,
+                value_expr,
+            }) => {
+                let evaluated = evaluate(storage, None, None, value_expr, false).await?;
+                let index_value: Value = evaluated.try_into()?;
+
+                storage
+                    .scan_indexed_data(table_name, index_name, index_op, index_value)
+                    .await
+                    .map(Rows::Indexed)?
+            }
+            None => storage.scan_data(table_name).await.map(Rows::FullScan)?,
+        }
+    };
+    #[cfg(not(feature = "index"))]
+    let rows = storage.scan_data(table_name).await?;
+
+    let rows = rows.map(move |data| {
         let (_, row) = data?;
         let row = Some(row);
         let columns = Rc::clone(&columns);
@@ -116,7 +150,7 @@ fn get_labels<'a>(
 }
 
 pub async fn select_with_labels<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     query: &'a Query,
     filter_context: Option<Rc<FilterContext<'a>>>,
     with_labels: bool,
@@ -128,22 +162,13 @@ pub async fn select_with_labels<'a, T: 'static + Debug>(
     }
 
     let (table_with_joins, where_clause, projection, group_by, having) = match &query.body {
-        SetExpr::Select(statement) => {
-            let tables = &statement.from;
-            let table_with_joins = match tables.len() {
-                1 => &tables[0],
-                0 => err!(SelectError::Unreachable),
-                _ => err!(SelectError::TooManyTables),
-            };
-
-            (
-                table_with_joins,
-                statement.selection.as_ref(),
-                statement.projection.as_ref(),
-                &statement.group_by,
-                statement.having.as_ref(),
-            )
-        }
+        SetExpr::Select(statement) => (
+            &statement.from,
+            statement.selection.as_ref(),
+            statement.projection.as_ref(),
+            &statement.group_by,
+            statement.having.as_ref(),
+        ),
         _ => err!(SelectError::Unreachable),
     };
 
@@ -235,7 +260,7 @@ pub async fn select_with_labels<'a, T: 'static + Debug>(
 }
 
 pub async fn select<'a, T: 'static + Debug>(
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     query: &'a Query,
     filter_context: Option<Rc<FilterContext<'a>>>,
 ) -> Result<impl TryStream<Ok = Row, Error = Error> + 'a> {
diff --git a/src/executor/update.rs b/src/executor/update.rs
index a23e05ca..b3209917 100644
--- a/src/executor/update.rs
+++ b/src/executor/update.rs
@@ -7,7 +7,7 @@ use {
         ast::{Assignment, ColumnDef},
         data::{schema::ColumnDefExt, Row, Value},
         result::Result,
-        store::Store,
+        store::GStore,
     },
     futures::stream::{self, TryStreamExt},
     serde::Serialize,
@@ -25,7 +25,7 @@ pub enum UpdateError {
 }
 
 pub struct Update<'a, T: 'static + Debug> {
-    storage: &'a dyn Store<T>,
+    storage: &'a dyn GStore<T>,
     table_name: &'a str,
     fields: &'a [Assignment],
     column_defs: &'a [ColumnDef],
@@ -33,7 +33,7 @@ pub struct Update<'a, T: 'static + Debug> {
 
 impl<'a, T: 'static + Debug> Update<'a, T> {
     pub fn new(
-        storage: &'a dyn Store<T>,
+        storage: &'a dyn GStore<T>,
         table_name: &'a str,
         fields: &'a [Assignment],
         column_defs: &'a [ColumnDef],
diff --git a/src/lib.rs b/src/lib.rs
index 7b340c02..799b4214 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -71,6 +71,7 @@ mod utils;
 
 pub mod ast;
 pub mod data;
+pub mod plan;
 pub mod result;
 pub mod store;
 pub mod tests;
@@ -79,6 +80,7 @@ pub mod translate;
 pub use data::*;
 pub use executor::*;
 pub use parse_sql::*;
+pub use plan::*;
 pub use result::*;
 pub use store::*;
 pub use translate::*;
diff --git a/src/parse_sql.rs b/src/parse_sql.rs
index 08945eeb..4fc644db 100644
--- a/src/parse_sql.rs
+++ b/src/parse_sql.rs
@@ -1,6 +1,11 @@
 use {
     crate::result::{Error, Result},
-    sqlparser::{ast::Statement as SqlStatement, dialect::GenericDialect, parser::Parser},
+    sqlparser::{
+        ast::{Expr as SqlExpr, Statement as SqlStatement},
+        dialect::GenericDialect,
+        parser::Parser,
+        tokenizer::Tokenizer,
+    },
 };
 
 pub fn parse(sql: &str) -> Result<Vec<SqlStatement>> {
@@ -8,3 +13,14 @@ pub fn parse(sql: &str) -> Result<Vec<SqlStatement>> {
 
     Parser::parse_sql(&dialect, sql).map_err(|e| Error::Parser(format!("{:#?}", e)))
 }
+
+pub fn parse_expr(sql_expr: &str) -> Result<SqlExpr> {
+    let dialect = GenericDialect {};
+    let tokens = Tokenizer::new(&dialect, &sql_expr)
+        .tokenize()
+        .map_err(|e| Error::Parser(format!("{:#?}", e)))?;
+
+    Parser::new(tokens, &dialect)
+        .parse_expr()
+        .map_err(|e| Error::Parser(format!("{:#?}", e)))
+}
diff --git a/src/plan.rs b/src/plan.rs
new file mode 100644
index 00000000..d296234e
--- /dev/null
+++ b/src/plan.rs
@@ -0,0 +1,332 @@
+use {
+    crate::{
+        ast::{
+            AstLiteral, BinaryOperator, Expr, IndexItem, IndexOperator, Query, Select, SetExpr,
+            Statement, TableFactor, TableWithJoins,
+        },
+        data::{get_name, Schema},
+        result::Result,
+        store::Store,
+    },
+    boolinator::Boolinator,
+    std::fmt::Debug,
+};
+
+pub async fn plan<T: 'static + Debug>(
+    storage: &dyn Store<T>,
+    statement: Statement,
+) -> Result<Statement> {
+    match statement {
+        Statement::Query(query) => plan_query(storage, *query)
+            .await
+            .map(Box::new)
+            .map(Statement::Query),
+        _ => Ok(statement),
+    }
+}
+
+async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) -> Result<Query> {
+    let Query {
+        body,
+        limit,
+        offset,
+    } = query;
+
+    let select = match body {
+        SetExpr::Select(select) => plan_select(storage, *select).await.map(Box::new)?,
+        SetExpr::Values(_) => {
+            return Ok(Query {
+                body,
+                limit,
+                offset,
+            });
+        }
+    };
+
+    let body = SetExpr::Select(select);
+    let query = Query {
+        body,
+        limit,
+        offset,
+    };
+
+    Ok(query)
+}
+
+struct Indexes(Vec<(String, Expr)>);
+
+impl Indexes {
+    fn find(&self, target: &Expr) -> Option<String> {
+        self.0
+            .iter()
+            .find(|(_, expr)| expr == target)
+            .map(|(index_name, _)| index_name.to_owned())
+    }
+}
+
+async fn plan_select<T: 'static + Debug>(storage: &dyn Store<T>, select: Select) -> Result<Select> {
+    let Select {
+        projection,
+        from,
+        selection,
+        group_by,
+        having,
+    } = select;
+
+    let TableWithJoins { relation, .. } = &from;
+
+    let table_name = match relation {
+        TableFactor::Table { name, .. } => name,
+    };
+    let table_name = get_name(table_name)?;
+
+    let indexes = match storage.fetch_schema(table_name).await? {
+        Some(Schema { indexes, .. }) => Indexes(indexes),
+        None => {
+            return Ok(Select {
+                projection,
+                from,
+                selection,
+                group_by,
+                having,
+            });
+        }
+    };
+
+    let selection = match selection {
+        Some(expr) => expr,
+        None => {
+            return Ok(Select {
+                projection,
+                from,
+                selection,
+                group_by,
+                having,
+            });
+        }
+    };
+
+    match search_index(&indexes, selection) {
+        Searched::NotFound(selection) => Ok(Select {
+            projection,
+            from,
+            selection: Some(selection),
+            group_by,
+            having,
+        }),
+        Searched::Found {
+            index_name,
+            index_op,
+            index_value_expr,
+            selection,
+        } => {
+            let TableWithJoins { relation, joins } = from;
+            let (name, alias) = match relation {
+                TableFactor::Table { name, alias, .. } => (name, alias),
+            };
+
+            let index = Some(IndexItem {
+                name: index_name,
+                op: index_op,
+                value_expr: index_value_expr,
+            });
+            let from = TableWithJoins {
+                relation: TableFactor::Table { name, alias, index },
+                joins,
+            };
+
+            Ok(Select {
+                projection,
+                from,
+                selection,
+                group_by,
+                having,
+            })
+        }
+    }
+}
+
+enum Searched {
+    Found {
+        index_name: String,
+        index_op: IndexOperator,
+        index_value_expr: Expr,
+        selection: Option<Expr>,
+    },
+    NotFound(Expr),
+}
+
+fn search_index(indexes: &Indexes, selection: Expr) -> Searched {
+    match selection {
+        Expr::Nested(expr) => search_index(indexes, *expr),
+        Expr::IsNull(expr) => search_is_null(indexes, true, expr),
+        Expr::IsNotNull(expr) => search_is_null(indexes, false, expr),
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::And,
+            right,
+        } => {
+            let left = match search_index(indexes, *left) {
+                Searched::NotFound(selection) => selection,
+                Searched::Found {
+                    index_name,
+                    index_value_expr,
+                    index_op,
+                    selection,
+                } => {
+                    let selection = match selection {
+                        Some(expr) => Expr::BinaryOp {
+                            left: Box::new(expr),
+                            op: BinaryOperator::And,
+                            right,
+                        },
+                        None => *right,
+                    };
+
+                    return Searched::Found {
+                        index_name,
+                        index_op,
+                        index_value_expr,
+                        selection: Some(selection),
+                    };
+                }
+            };
+
+            match search_index(indexes, *right) {
+                Searched::NotFound(expr) => Searched::NotFound(Expr::BinaryOp {
+                    left: Box::new(left),
+                    op: BinaryOperator::And,
+                    right: Box::new(expr),
+                }),
+                Searched::Found {
+                    index_name,
+                    index_op,
+                    index_value_expr,
+                    selection,
+                } => {
+                    let selection = match selection {
+                        Some(expr) => Expr::BinaryOp {
+                            left: Box::new(left),
+                            op: BinaryOperator::And,
+                            right: Box::new(expr),
+                        },
+                        None => left,
+                    };
+
+                    Searched::Found {
+                        index_name,
+                        index_value_expr,
+                        index_op,
+                        selection: Some(selection),
+                    }
+                }
+            }
+        }
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::Gt,
+            right,
+        } => search_index_op(indexes, IndexOperator::Gt, left, right),
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::Lt,
+            right,
+        } => search_index_op(indexes, IndexOperator::Lt, left, right),
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::GtEq,
+            right,
+        } => search_index_op(indexes, IndexOperator::GtEq, left, right),
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::LtEq,
+            right,
+        } => search_index_op(indexes, IndexOperator::LtEq, left, right),
+        Expr::BinaryOp {
+            left,
+            op: BinaryOperator::Eq,
+            right,
+        } => search_index_op(indexes, IndexOperator::Eq, left, right),
+        _ => Searched::NotFound(selection),
+    }
+}
+
+fn search_is_null(indexes: &Indexes, null: bool, expr: Box<Expr>) -> Searched {
+    match indexes.find(expr.as_ref()) {
+        Some(index_name) => {
+            let index_op = if null {
+                IndexOperator::Eq
+            } else {
+                IndexOperator::Lt
+            };
+
+            Searched::Found {
+                index_name,
+                index_op,
+                index_value_expr: Expr::Literal(AstLiteral::Null),
+                selection: None,
+            }
+        }
+        None => {
+            let expr = if null {
+                Expr::IsNull(expr)
+            } else {
+                Expr::IsNotNull(expr)
+            };
+
+            Searched::NotFound(expr)
+        }
+    }
+}
+
+fn search_index_op(
+    indexes: &Indexes,
+    index_op: IndexOperator,
+    left: Box<Expr>,
+    right: Box<Expr>,
+) -> Searched {
+    if let Some(index_name) = indexes
+        .find(left.as_ref())
+        .and_then(|index_name| is_stateless(right.as_ref()).as_some(index_name))
+    {
+        Searched::Found {
+            index_name,
+            index_op,
+            index_value_expr: *right,
+            selection: None,
+        }
+    } else if let Some(index_name) = indexes
+        .find(right.as_ref())
+        .and_then(|index_name| is_stateless(left.as_ref()).as_some(index_name))
+    {
+        Searched::Found {
+            index_name,
+            index_op: index_op.reverse(),
+            index_value_expr: *left,
+            selection: None,
+        }
+    } else {
+        Searched::NotFound(Expr::BinaryOp {
+            left,
+            op: index_op.into(),
+            right,
+        })
+    }
+}
+
+fn is_stateless(expr: &Expr) -> bool {
+    match expr {
+        Expr::Literal(AstLiteral::Null) => false,
+        Expr::Literal(_) => true,
+        Expr::TypedString { .. } => true,
+        Expr::IsNull(expr)
+        | Expr::IsNotNull(expr)
+        | Expr::UnaryOp { expr, .. }
+        | Expr::Cast { expr, .. }
+        | Expr::Nested(expr) => is_stateless(expr.as_ref()),
+        Expr::BinaryOp { left, right, .. } => {
+            is_stateless(left.as_ref()) && is_stateless(right.as_ref())
+        }
+        _ => false,
+    }
+}
diff --git a/src/result.rs b/src/result.rs
index 7938d77a..5b4b131a 100644
--- a/src/result.rs
+++ b/src/result.rs
@@ -14,6 +14,9 @@ use {
 #[cfg(feature = "alter-table")]
 use crate::store::AlterTableError;
 
+#[cfg(feature = "index")]
+use crate::store::IndexError;
+
 #[derive(ThisError, Serialize, Debug)]
 pub enum Error {
     #[error(transparent)]
@@ -30,6 +33,10 @@ pub enum Error {
     #[error(transparent)]
     AlterTable(#[from] AlterTableError),
 
+    #[cfg(feature = "index")]
+    #[error(transparent)]
+    Index(#[from] IndexError),
+
     #[error(transparent)]
     Execute(#[from] ExecuteError),
     #[error(transparent)]
@@ -74,6 +81,8 @@ impl PartialEq for Error {
             (Translate(e), Translate(e2)) => e == e2,
             #[cfg(feature = "alter-table")]
             (AlterTable(e), AlterTable(e2)) => e == e2,
+            #[cfg(feature = "index")]
+            (Index(e), Index(e2)) => e == e2,
             (Execute(e), Execute(e2)) => e == e2,
             (Alter(e), Alter(e2)) => e == e2,
             (Fetch(e), Fetch(e2)) => e == e2,
diff --git a/src/storages/sled_storage/alter_table.rs b/src/storages/sled_storage/alter_table.rs
index a287b6b0..5392c6d2 100644
--- a/src/storages/sled_storage/alter_table.rs
+++ b/src/storages/sled_storage/alter_table.rs
@@ -43,10 +43,18 @@ macro_rules! fetch_schema {
 #[async_trait(?Send)]
 impl AlterTable for SledStorage {
     async fn rename_schema(self, table_name: &str, new_table_name: &str) -> MutResult<Self, ()> {
-        let (_, Schema { column_defs, .. }) = fetch_schema!(self, &self.tree, table_name);
+        let (
+            _,
+            Schema {
+                column_defs,
+                indexes,
+                ..
+            },
+        ) = fetch_schema!(self, &self.tree, table_name);
         let schema = Schema {
             table_name: new_table_name.to_string(),
             column_defs,
+            indexes,
         };
 
         let tree = &self.tree;
@@ -83,7 +91,14 @@ impl AlterTable for SledStorage {
         old_column_name: &str,
         new_column_name: &str,
     ) -> MutResult<Self, ()> {
-        let (key, Schema { column_defs, .. }) = fetch_schema!(self, &self.tree, table_name);
+        let (
+            key,
+            Schema {
+                column_defs,
+                indexes,
+                ..
+            },
+        ) = fetch_schema!(self, &self.tree, table_name);
 
         let i = column_defs
             .iter()
@@ -105,6 +120,7 @@ impl AlterTable for SledStorage {
         let schema = Schema {
             table_name: table_name.to_string(),
             column_defs,
+            indexes,
         };
         let value = try_into!(self, bincode::serialize(&schema));
         try_into!(self, self.tree.insert(key, value));
@@ -118,6 +134,7 @@ impl AlterTable for SledStorage {
             Schema {
                 table_name,
                 column_defs,
+                indexes,
             },
         ) = fetch_schema!(self, &self.tree, table_name);
 
@@ -168,6 +185,7 @@ impl AlterTable for SledStorage {
         let schema = Schema {
             table_name,
             column_defs,
+            indexes,
         };
         let schema_value = try_into!(self, bincode::serialize(&schema));
         try_into!(self, self.tree.insert(key, schema_value));
@@ -186,6 +204,7 @@ impl AlterTable for SledStorage {
             Schema {
                 table_name,
                 column_defs,
+                indexes,
             },
         ) = fetch_schema!(self, &self.tree, table_name);
 
@@ -233,6 +252,7 @@ impl AlterTable for SledStorage {
         let schema = Schema {
             table_name,
             column_defs,
+            indexes,
         };
         let schema_value = try_into!(self, bincode::serialize(&schema));
         try_into!(self, self.tree.insert(key, schema_value));
diff --git a/src/storages/sled_storage/error.rs b/src/storages/sled_storage/error.rs
index e005c0f1..380f77d7 100644
--- a/src/storages/sled_storage/error.rs
+++ b/src/storages/sled_storage/error.rs
@@ -3,6 +3,10 @@ use thiserror::Error as ThisError;
 
 #[cfg(feature = "alter-table")]
 use crate::AlterTableError;
+
+#[cfg(feature = "index")]
+use crate::IndexError;
+
 use crate::Error;
 
 #[derive(ThisError, Debug)]
@@ -11,6 +15,10 @@ pub enum StorageError {
     #[error(transparent)]
     AlterTable(#[from] AlterTableError),
 
+    #[cfg(feature = "index")]
+    #[error(transparent)]
+    Index(#[from] IndexError),
+
     #[error(transparent)]
     Sled(#[from] sled::Error),
     #[error(transparent)]
@@ -30,6 +38,9 @@ impl From<StorageError> for Error {
 
             #[cfg(feature = "alter-table")]
             AlterTable(e) => e.into(),
+
+            #[cfg(feature = "index")]
+            Index(e) => e.into(),
         }
     }
 }
diff --git a/src/storages/sled_storage/index.rs b/src/storages/sled_storage/index.rs
new file mode 100644
index 00000000..b83ef6a8
--- /dev/null
+++ b/src/storages/sled_storage/index.rs
@@ -0,0 +1,117 @@
+#![cfg(feature = "index")]
+
+use {
+    super::{
+        err_into,
+        index_sync::{build_index_key, build_index_key_prefix},
+        SledStorage,
+    },
+    crate::{
+        ast::IndexOperator,
+        result::Result,
+        store::{Index, RowIter},
+        utils::Vector,
+        IndexError, Value,
+    },
+    async_trait::async_trait,
+    iter_enum::Iterator,
+    sled::IVec,
+    std::iter::{empty, once},
+};
+
+#[async_trait(?Send)]
+impl Index<IVec> for SledStorage {
+    async fn scan_indexed_data(
+        &self,
+        table_name: &str,
+        index_name: &str,
+        op: &IndexOperator,
+        value: Value,
+    ) -> Result<RowIter<IVec>> {
+        let index_data_ids = {
+            #[derive(Iterator)]
+            enum DataIds<I1, I2, I3, I4> {
+                Empty(I1),
+                Once(I2),
+                RangeGt(I3),
+                Range(I4),
+            }
+
+            let map = |item: std::result::Result<_, _>| item.map(|(_, v)| v);
+            let lower = || build_index_key_prefix(table_name, index_name);
+            let upper = || {
+                build_index_key_prefix(table_name, index_name)
+                    .into_iter()
+                    .rev()
+                    .fold((false, Vector::new()), |(added, upper), v| {
+                        match (added, v) {
+                            (true, _) => (added, upper.push(v)),
+                            (false, u8::MAX) => (added, upper.push(v)),
+                            (false, _) => (true, upper.push(v + 1)),
+                        }
+                    })
+                    .1
+                    .reverse()
+                    .into()
+            };
+            let key = build_index_key(table_name, index_name, value);
+
+            match op {
+                IndexOperator::Eq => match self.tree.get(&key).transpose() {
+                    Some(v) => DataIds::Once(once(v)),
+                    None => DataIds::Empty(empty()),
+                },
+                IndexOperator::Gt => {
+                    DataIds::RangeGt(self.tree.range(key..upper()).skip(1).map(map))
+                }
+                IndexOperator::GtEq => DataIds::Range(self.tree.range(key..upper()).map(map)),
+                IndexOperator::Lt => DataIds::Range(self.tree.range(lower()..key).map(map)),
+                IndexOperator::LtEq => DataIds::Range(self.tree.range(lower()..=key).map(map)),
+            }
+        };
+
+        let tree = self.tree.clone();
+        let rows = index_data_ids.map(|v| v.map_err(err_into)).flat_map(
+            move |index_data_id: Result<IVec>| {
+                #[derive(Iterator)]
+                enum Rows<I1, I2> {
+                    Ok(I1),
+                    Err(I2),
+                }
+
+                let index_data_id: IVec = match index_data_id {
+                    Ok(id) => id,
+                    Err(e) => {
+                        return Rows::Err(once(Err(e)));
+                    }
+                };
+
+                let bytes = "indexdata/"
+                    .to_owned()
+                    .into_bytes()
+                    .into_iter()
+                    .chain(index_data_id.iter().copied())
+                    .collect::<Vec<_>>();
+                let index_data_prefix = IVec::from(bytes);
+
+                let tree2 = tree.clone();
+                let rows = tree
+                    .scan_prefix(&index_data_prefix)
+                    .map(move |item| -> Result<_> {
+                        let (_, data_key) = item.map_err(err_into)?;
+                        let value = tree2
+                            .get(&data_key)
+                            .map_err(err_into)?
+                            .ok_or(IndexError::ConflictOnEmptyIndexValueScan)?;
+                        let value = bincode::deserialize(&value).map_err(err_into)?;
+
+                        Ok((data_key, value))
+                    });
+
+                Rows::Ok(rows)
+            },
+        );
+
+        Ok(Box::new(rows))
+    }
+}
diff --git a/src/storages/sled_storage/index_mut.rs b/src/storages/sled_storage/index_mut.rs
new file mode 100644
index 00000000..ebbf5bba
--- /dev/null
+++ b/src/storages/sled_storage/index_mut.rs
@@ -0,0 +1,164 @@
+#![cfg(feature = "index")]
+
+use {
+    super::{
+        err_into, error::StorageError, fetch_schema, index_sync::IndexSync, scan_data, SledStorage,
+    },
+    crate::{
+        ast::Expr,
+        data::Schema,
+        result::{MutResult, Result},
+        store::IndexMut,
+        IndexError,
+    },
+    async_trait::async_trait,
+    sled::{
+        transaction::{ConflictableTransactionError, TransactionError},
+        IVec,
+    },
+    std::iter::once,
+};
+
+macro_rules! try_self {
+    ($self: expr, $expr: expr) => {
+        match $expr {
+            Err(e) => {
+                return Err(($self, e.into()));
+            }
+            Ok(v) => v,
+        }
+    };
+}
+
+macro_rules! try_into {
+    ($self: expr, $expr: expr) => {
+        match $expr.map_err(err_into) {
+            Err(e) => {
+                return Err(($self, e));
+            }
+            Ok(v) => v,
+        }
+    };
+}
+
+macro_rules! transaction {
+    ($self: expr, $expr: expr) => {{
+        let result = $self.tree.transaction($expr).map_err(|e| match e {
+            TransactionError::Abort(e) => e,
+            TransactionError::Storage(e) => StorageError::Sled(e).into(),
+        });
+
+        match result {
+            Ok(_) => Ok(($self, ())),
+            Err(e) => Err(($self, e)),
+        }
+    }};
+}
+
+#[async_trait(?Send)]
+impl IndexMut<IVec> for SledStorage {
+    async fn create_index(
+        self,
+        table_name: &str,
+        index_name: &str,
+        index_expr: &Expr,
+    ) -> MutResult<Self, ()> {
+        let (schema_key, schema) = try_self!(self, fetch_schema(&self.tree, table_name));
+        let Schema {
+            column_defs,
+            indexes,
+            ..
+        } = try_into!(
+            self,
+            schema.ok_or_else(|| IndexError::TableNotFound(table_name.to_owned()))
+        );
+
+        if indexes.iter().any(|(name, _)| name == index_name) {
+            return Err((
+                self,
+                IndexError::IndexNameAlreadyExists(index_name.to_owned()).into(),
+            ));
+        }
+
+        let indexes = indexes
+            .into_iter()
+            .chain(once((index_name.to_owned(), index_expr.clone())))
+            .collect::<Vec<_>>();
+
+        let schema = Schema {
+            table_name: table_name.to_owned(),
+            column_defs,
+            indexes,
+        };
+
+        let rows = try_self!(
+            self,
+            scan_data(&self.tree, table_name).collect::<Result<Vec<_>>>()
+        );
+        let index_sync = IndexSync::from(&schema);
+
+        transaction!(self, |tree| {
+            let schema_value = bincode::serialize(&schema)
+                .map_err(err_into)
+                .map_err(ConflictableTransactionError::Abort)?;
+
+            tree.insert(schema_key.as_bytes(), schema_value)?;
+
+            for (data_key, row) in rows.iter() {
+                index_sync.insert(&tree, data_key, row)?;
+            }
+
+            Ok(())
+        })
+    }
+
+    async fn drop_index(self, table_name: &str, index_name: &str) -> MutResult<Self, ()> {
+        let (schema_key, schema) = try_self!(self, fetch_schema(&self.tree, table_name));
+        let Schema {
+            column_defs,
+            indexes,
+            ..
+        } = try_into!(
+            self,
+            schema.ok_or_else(|| IndexError::TableNotFound(table_name.to_owned()))
+        );
+
+        if indexes.iter().all(|(name, _)| name != index_name) {
+            return Err((
+                self,
+                IndexError::IndexNameDoesNotExist(index_name.to_owned()).into(),
+            ));
+        }
+
+        let indexes = indexes
+            .into_iter()
+            .filter(|(name, _)| name != index_name)
+            .collect::<Vec<_>>();
+
+        let schema = Schema {
+            table_name: table_name.to_owned(),
+            column_defs,
+            indexes,
+        };
+
+        let rows = try_self!(
+            self,
+            scan_data(&self.tree, table_name).collect::<Result<Vec<_>>>()
+        );
+        let index_sync = IndexSync::from(&schema);
+
+        transaction!(self, |tree| {
+            let schema_value = bincode::serialize(&schema)
+                .map_err(err_into)
+                .map_err(ConflictableTransactionError::Abort)?;
+
+            tree.insert(schema_key.as_bytes(), schema_value)?;
+
+            for (data_key, row) in rows.iter() {
+                index_sync.delete(&tree, data_key, row)?;
+            }
+
+            Ok(())
+        })
+    }
+}
diff --git a/src/storages/sled_storage/index_sync.rs b/src/storages/sled_storage/index_sync.rs
new file mode 100644
index 00000000..e55b08f2
--- /dev/null
+++ b/src/storages/sled_storage/index_sync.rs
@@ -0,0 +1,213 @@
+#![cfg(feature = "index")]
+
+use {
+    super::fetch_schema,
+    crate::{ast::Expr, evaluate_stateless, Error, IndexError, Result, Row, Schema, Value},
+    sled::{
+        transaction::{
+            ConflictableTransactionError, ConflictableTransactionResult, TransactionalTree,
+        },
+        Db, IVec,
+    },
+    std::{borrow::Cow, convert::TryInto},
+};
+
+pub struct IndexSync<'a> {
+    table_name: &'a str,
+    columns: Vec<String>,
+    indexes: Cow<'a, Vec<(String, Expr)>>,
+}
+
+impl<'a> From<&'a Schema> for IndexSync<'a> {
+    fn from(schema: &'a Schema) -> Self {
+        let Schema {
+            table_name,
+            column_defs,
+            indexes,
+            ..
+        } = schema;
+
+        let columns = column_defs
+            .iter()
+            .map(|column_def| column_def.name.to_owned())
+            .collect::<Vec<_>>();
+
+        let indexes = Cow::Borrowed(indexes);
+
+        Self {
+            table_name,
+            columns,
+            indexes,
+        }
+    }
+}
+
+impl<'a> IndexSync<'a> {
+    pub fn new(tree: &Db, table_name: &'a str) -> Result<Self> {
+        let (_, schema) = fetch_schema(tree, table_name)?;
+        let Schema {
+            column_defs,
+            indexes,
+            ..
+        } = schema.ok_or_else(|| IndexError::TableNotFound(table_name.to_owned()))?;
+
+        let columns = column_defs
+            .into_iter()
+            .map(|column_def| column_def.name)
+            .collect::<Vec<_>>();
+
+        Ok(Self {
+            table_name,
+            columns,
+            indexes: Cow::Owned(indexes),
+        })
+    }
+
+    pub fn insert(
+        &self,
+        tree: &TransactionalTree,
+        data_key: &IVec,
+        row: &Row,
+    ) -> ConflictableTransactionResult<(), Error> {
+        for (index_name, index_expr) in self.indexes.iter() {
+            let index_key =
+                &evaluate_index_key(self.table_name, index_name, index_expr, &self.columns, row)?;
+
+            insert_index_data(tree, self.table_name, &index_key, &data_key)?;
+        }
+
+        Ok(())
+    }
+
+    pub fn update(
+        &self,
+        tree: &TransactionalTree,
+        data_key: &IVec,
+        old_row: &Row,
+        new_row: &Row,
+    ) -> ConflictableTransactionResult<(), Error> {
+        for (index_name, index_expr) in self.indexes.iter() {
+            let old_index_key = &evaluate_index_key(
+                self.table_name,
+                index_name,
+                index_expr,
+                &self.columns,
+                &old_row,
+            )?;
+
+            let new_index_key = &evaluate_index_key(
+                self.table_name,
+                index_name,
+                index_expr,
+                &self.columns,
+                &new_row,
+            )?;
+
+            delete_index_data(tree, self.table_name, &old_index_key, &data_key)?;
+            insert_index_data(tree, self.table_name, &new_index_key, &data_key)?;
+        }
+
+        Ok(())
+    }
+
+    pub fn delete(
+        &self,
+        tree: &TransactionalTree,
+        data_key: &IVec,
+        row: &Row,
+    ) -> ConflictableTransactionResult<(), Error> {
+        for (index_name, index_expr) in self.indexes.iter() {
+            let index_key =
+                &evaluate_index_key(self.table_name, index_name, index_expr, &self.columns, row)?;
+
+            delete_index_data(tree, self.table_name, &index_key, &data_key)?;
+        }
+
+        Ok(())
+    }
+}
+
+fn insert_index_data(
+    tree: &TransactionalTree,
+    table_name: &str,
+    index_key: &[u8],
+    data_key: &IVec,
+) -> ConflictableTransactionResult<(), Error> {
+    let index_data_id = {
+        if let Some(id) = tree.get(&index_key)? {
+            id
+        } else {
+            let id = tree.generate_id()?.to_be_bytes();
+            let id = IVec::from(&id);
+
+            tree.insert(index_key, &id)?;
+
+            id
+        }
+    };
+
+    let index_data_key = make_index_data_key(table_name, &index_data_id, data_key);
+
+    tree.insert(index_data_key, data_key)?;
+
+    Ok(())
+}
+
+fn delete_index_data(
+    tree: &TransactionalTree,
+    table_name: &str,
+    index_key: &[u8],
+    data_key: &IVec,
+) -> ConflictableTransactionResult<(), Error> {
+    let index_data_id = tree
+        .get(&index_key)?
+        .ok_or_else(|| IndexError::ConflictOnIndexDataDeleteSync.into())
+        .map_err(ConflictableTransactionError::Abort)?;
+
+    let index_data_key = make_index_data_key(table_name, &index_data_id, data_key);
+
+    tree.remove(index_data_key)?;
+
+    Ok(())
+}
+
+fn make_index_data_key(table_name: &str, index_data_id: &IVec, data_key: &IVec) -> IVec {
+    let data_prefix_len = "data/".as_bytes().len() + table_name.as_bytes().len();
+    let data_key = data_key.subslice(data_prefix_len, data_key.as_ref().len() - data_prefix_len);
+    let bytes = "indexdata/"
+        .to_owned()
+        .into_bytes()
+        .into_iter()
+        .chain(index_data_id.iter().copied())
+        .chain(data_key.iter().copied())
+        .collect::<Vec<_>>();
+
+    IVec::from(bytes)
+}
+
+fn evaluate_index_key(
+    table_name: &str,
+    index_name: &str,
+    index_expr: &Expr,
+    columns: &[String],
+    row: &Row,
+) -> ConflictableTransactionResult<Vec<u8>, Error> {
+    let evaluated = evaluate_stateless(Some((columns, row)), index_expr)
+        .map_err(ConflictableTransactionError::Abort)?;
+    let value: Value = evaluated
+        .try_into()
+        .map_err(ConflictableTransactionError::Abort)?;
+
+    Ok(build_index_key(table_name, index_name, value))
+}
+
+pub fn build_index_key_prefix(table_name: &str, index_name: &str) -> Vec<u8> {
+    format!("index/{}/{}/", table_name, index_name).into_bytes()
+}
+
+pub fn build_index_key(table_name: &str, index_name: &str, value: Value) -> Vec<u8> {
+    build_index_key_prefix(table_name, index_name)
+        .into_iter()
+        .chain(value.to_be_bytes().into_iter())
+        .collect::<Vec<_>>()
+}
diff --git a/src/storages/sled_storage/mod.rs b/src/storages/sled_storage/mod.rs
index d7818247..1409ee93 100644
--- a/src/storages/sled_storage/mod.rs
+++ b/src/storages/sled_storage/mod.rs
@@ -1,14 +1,18 @@
 mod alter_table;
 mod error;
+mod index;
+mod index_mut;
+mod index_sync;
 mod store;
 mod store_mut;
-#[cfg(not(feature = "alter-table"))]
-impl crate::AlterTable for SledStorage {}
 
 use {
-    crate::{Error, Result, Schema},
+    crate::{
+        store::{GStore, GStoreMut},
+        Error, Result, RowIter, Schema,
+    },
     error::err_into,
-    sled::{self, Config, Db},
+    sled::{self, Config, Db, IVec},
     std::convert::TryFrom,
 };
 
@@ -45,3 +49,19 @@ fn fetch_schema(tree: &Db, table_name: &str) -> Result<(String, Option<Schema>)>
 
     Ok((key, schema))
 }
+
+fn scan_data(tree: &Db, table_name: &str) -> RowIter<IVec> {
+    let prefix = format!("data/{}/", table_name);
+
+    let result_set = tree.scan_prefix(prefix.as_bytes()).map(move |item| {
+        let (key, value) = item.map_err(err_into)?;
+        let value = bincode::deserialize(&value).map_err(err_into)?;
+
+        Ok((key, value))
+    });
+
+    Box::new(result_set)
+}
+
+impl GStore<IVec> for SledStorage {}
+impl GStoreMut<IVec> for SledStorage {}
diff --git a/src/storages/sled_storage/store.rs b/src/storages/sled_storage/store.rs
index 29ed5708..c0aab965 100644
--- a/src/storages/sled_storage/store.rs
+++ b/src/storages/sled_storage/store.rs
@@ -1,5 +1,5 @@
 use {
-    super::{err_into, fetch_schema, SledStorage},
+    super::{fetch_schema, scan_data, SledStorage},
     crate::{Result, RowIter, Schema, Store},
     async_trait::async_trait,
     sled::IVec,
@@ -12,15 +12,6 @@ impl Store<IVec> for SledStorage {
     }
 
     async fn scan_data(&self, table_name: &str) -> Result<RowIter<IVec>> {
-        let prefix = format!("data/{}/", table_name);
-
-        let result_set = self.tree.scan_prefix(prefix.as_bytes()).map(move |item| {
-            let (key, value) = item.map_err(err_into)?;
-            let value = bincode::deserialize(&value).map_err(err_into)?;
-
-            Ok((key, value))
-        });
-
-        Ok(Box::new(result_set))
+        Ok(scan_data(&self.tree, table_name))
     }
 }
diff --git a/src/storages/sled_storage/store_mut.rs b/src/storages/sled_storage/store_mut.rs
index 596bb8dc..9c903043 100644
--- a/src/storages/sled_storage/store_mut.rs
+++ b/src/storages/sled_storage/store_mut.rs
@@ -8,6 +8,21 @@ use {
     },
 };
 
+#[cfg(feature = "index")]
+use {super::index_sync::IndexSync, crate::IndexError};
+
+#[cfg(feature = "index")]
+macro_rules! try_self {
+    ($self: expr, $expr: expr) => {
+        match $expr {
+            Err(e) => {
+                return Err(($self, e.into()));
+            }
+            Ok(v) => v,
+        }
+    };
+}
+
 macro_rules! try_into {
     ($self: expr, $expr: expr) => {
         match $expr.map_err(err_into) {
@@ -62,7 +77,10 @@ impl StoreMut<IVec> for SledStorage {
     }
 
     async fn insert_data(self, table_name: &str, rows: Vec<Row>) -> MutResult<Self, ()> {
-        transaction!(self, |tree| {
+        #[cfg(feature = "index")]
+        let index_sync = try_self!(self, IndexSync::new(&self.tree, table_name));
+
+        transaction!(self, move |tree| {
             for row in rows.iter() {
                 let id = tree.generate_id()?;
                 let id = id.to_be_bytes();
@@ -79,6 +97,9 @@ impl StoreMut<IVec> for SledStorage {
                     .map_err(err_into)
                     .map_err(ConflictableTransactionError::Abort)?;
 
+                #[cfg(feature = "index")]
+                index_sync.insert(&tree, &key, row)?;
+
                 tree.insert(key, value)?;
             }
 
@@ -86,7 +107,8 @@ impl StoreMut<IVec> for SledStorage {
         })
     }
 
-    async fn update_data(self, rows: Vec<(IVec, Row)>) -> MutResult<Self, ()> {
+    #[cfg(not(feature = "index"))]
+    async fn update_data(self, _: &str, rows: Vec<(IVec, Row)>) -> MutResult<Self, ()> {
         transaction!(self, |tree| {
             for (key, row) in rows.iter() {
                 let value = bincode::serialize(row)
@@ -100,7 +122,34 @@ impl StoreMut<IVec> for SledStorage {
         })
     }
 
-    async fn delete_data(self, keys: Vec<IVec>) -> MutResult<Self, ()> {
+    #[cfg(feature = "index")]
+    async fn update_data(self, table_name: &str, rows: Vec<(IVec, Row)>) -> MutResult<Self, ()> {
+        let index_sync = try_self!(self, IndexSync::new(&self.tree, table_name));
+
+        transaction!(self, |tree| {
+            for (key, new_row) in rows.iter() {
+                let new_value = bincode::serialize(new_row)
+                    .map_err(err_into)
+                    .map_err(ConflictableTransactionError::Abort)?;
+
+                let old_value = tree
+                    .insert(key, new_value)?
+                    .ok_or_else(|| IndexError::ConflictOnEmptyIndexValueUpdate.into())
+                    .map_err(ConflictableTransactionError::Abort)?;
+
+                let old_row = bincode::deserialize(&old_value)
+                    .map_err(err_into)
+                    .map_err(ConflictableTransactionError::Abort)?;
+
+                index_sync.update(&tree, &key, &old_row, new_row)?;
+            }
+
+            Ok(())
+        })
+    }
+
+    #[cfg(not(feature = "index"))]
+    async fn delete_data(self, _: &str, keys: Vec<IVec>) -> MutResult<Self, ()> {
         transaction!(self, |tree| {
             for key in keys.iter() {
                 tree.remove(key)?;
@@ -109,4 +158,26 @@ impl StoreMut<IVec> for SledStorage {
             Ok(())
         })
     }
+
+    #[cfg(feature = "index")]
+    async fn delete_data(self, table_name: &str, keys: Vec<IVec>) -> MutResult<Self, ()> {
+        let index_sync = try_self!(self, IndexSync::new(&self.tree, table_name));
+
+        transaction!(self, |tree| {
+            for key in keys.iter() {
+                let value = tree
+                    .remove(key)?
+                    .ok_or_else(|| IndexError::ConflictOnEmptyIndexValueDelete.into())
+                    .map_err(ConflictableTransactionError::Abort)?;
+
+                let row = bincode::deserialize(&value)
+                    .map_err(err_into)
+                    .map_err(ConflictableTransactionError::Abort)?;
+
+                index_sync.delete(&tree, &key, &row)?;
+            }
+
+            Ok(())
+        })
+    }
 }
diff --git a/src/store/index.rs b/src/store/index.rs
new file mode 100644
index 00000000..32da01fc
--- /dev/null
+++ b/src/store/index.rs
@@ -0,0 +1,62 @@
+use {
+    super::RowIter,
+    crate::{
+        ast::{Expr, IndexOperator},
+        data::Value,
+        result::{MutResult, Result},
+    },
+    async_trait::async_trait,
+    serde::Serialize,
+    std::fmt::Debug,
+    thiserror::Error,
+};
+
+#[derive(Error, Serialize, Debug, PartialEq)]
+pub enum IndexError {
+    #[error("table not found: {0}")]
+    TableNotFound(String),
+
+    #[error("index name already exists: {0}")]
+    IndexNameAlreadyExists(String),
+
+    #[error("index name does not exist: {0}")]
+    IndexNameDoesNotExist(String),
+
+    #[error("conflict - update failed - index value")]
+    ConflictOnEmptyIndexValueUpdate,
+
+    #[error("conflict - delete failed - index value")]
+    ConflictOnEmptyIndexValueDelete,
+
+    #[error("conflict - scan failed - index value")]
+    ConflictOnEmptyIndexValueScan,
+
+    #[error("conflict - index sync - delete index data")]
+    ConflictOnIndexDataDeleteSync,
+}
+
+#[async_trait(?Send)]
+pub trait Index<T: Debug> {
+    async fn scan_indexed_data(
+        &self,
+        table_name: &str,
+        index_name: &str,
+        op: &IndexOperator,
+        value: Value,
+    ) -> Result<RowIter<T>>;
+}
+
+#[async_trait(?Send)]
+pub trait IndexMut<T: Debug>
+where
+    Self: Sized,
+{
+    async fn create_index(
+        self,
+        table_name: &str,
+        index_name: &str,
+        column: &Expr,
+    ) -> MutResult<Self, ()>;
+
+    async fn drop_index(self, table_name: &str, index_name: &str) -> MutResult<Self, ()>;
+}
diff --git a/src/store/mod.rs b/src/store/mod.rs
index 2a1e23d3..89aedda9 100644
--- a/src/store/mod.rs
+++ b/src/store/mod.rs
@@ -1,9 +1,38 @@
-#[cfg(feature = "alter-table")]
-mod alter_table;
-#[cfg(feature = "alter-table")]
-pub use alter_table::*;
-#[cfg(not(feature = "alter-table"))]
-pub trait AlterTable {}
+use cfg_if::cfg_if;
+
+cfg_if! {
+    if #[cfg(feature = "alter-table")] {
+        mod alter_table;
+        pub use alter_table::{AlterTable, AlterTableError};
+    }
+}
+
+cfg_if! {
+    if #[cfg(feature = "index")] {
+        mod index;
+        pub use index::{Index, IndexError, IndexMut};
+    }
+}
+
+cfg_if! {
+    if #[cfg(feature = "index")] {
+        pub trait GStore<T: Debug>: Store<T> + Index<T> {}
+    } else {
+        pub trait GStore<T: Debug>: Store<T> {}
+    }
+}
+
+cfg_if! {
+    if #[cfg(all(feature = "alter-table", feature = "index"))] {
+        pub trait GStoreMut<T: Debug>: StoreMut<T> + IndexMut<T> + AlterTable {}
+    } else if #[cfg(feature = "alter-table")] {
+        pub trait GStoreMut<T: Debug>: StoreMut<T> + AlterTable {}
+    } else if #[cfg(feature = "index")] {
+        pub trait GStoreMut<T: Debug>: StoreMut<T> + IndexMut<T> {}
+    } else {
+        pub trait GStoreMut<T: Debug>: Store<T> + StoreMut<T> {}
+    }
+}
 
 use {
     crate::{
@@ -11,12 +40,12 @@ use {
         result::{MutResult, Result},
     },
     async_trait::async_trait,
-    std::{fmt::Debug, marker::Sized},
+    std::fmt::Debug,
 };
 
 pub type RowIter<T> = Box<dyn Iterator<Item = Result<(T, Row)>>>;
 
-/// By implementing `Store` trait, you can run `SELECT` queries.
+/// By implementing `Store` trait, you can run `SELECT` query.
 #[async_trait(?Send)]
 pub trait Store<T: Debug> {
     async fn fetch_schema(&self, table_name: &str) -> Result<Option<Schema>>;
@@ -24,8 +53,8 @@ pub trait Store<T: Debug> {
     async fn scan_data(&self, table_name: &str) -> Result<RowIter<T>>;
 }
 
-/// `StoreMut` takes role of mutation, related to `INSERT`, `CREATE`, `DELETE`, `DROP` and
-/// `UPDATE`.
+/// By implementing `StoreMut` trait,
+/// you can run `INSERT`, `CREATE TABLE`, `DELETE`, `UPDATE` and `DROP TABLE` queries.
 #[async_trait(?Send)]
 pub trait StoreMut<T: Debug>
 where
@@ -37,7 +66,7 @@ where
 
     async fn insert_data(self, table_name: &str, rows: Vec<Row>) -> MutResult<Self, ()>;
 
-    async fn update_data(self, rows: Vec<(T, Row)>) -> MutResult<Self, ()>;
+    async fn update_data(self, table_name: &str, rows: Vec<(T, Row)>) -> MutResult<Self, ()>;
 
-    async fn delete_data(self, keys: Vec<T>) -> MutResult<Self, ()>;
+    async fn delete_data(self, table_name: &str, keys: Vec<T>) -> MutResult<Self, ()>;
 }
diff --git a/src/translate/error.rs b/src/translate/error.rs
index 52fa937a..131206c1 100644
--- a/src/translate/error.rs
+++ b/src/translate/error.rs
@@ -2,6 +2,18 @@ use {serde::Serialize, std::fmt::Debug, thiserror::Error};
 
 #[derive(Error, Serialize, Debug, PartialEq)]
 pub enum TranslateError {
+    #[error("unimplemented - select query without table is not supported")]
+    LackOfTable,
+
+    #[error("unimplemented - select on two or more than tables are not supported")]
+    TooManyTables,
+
+    #[error("unimplemented - composite index is not supported")]
+    CompositeIndexNotSupported,
+
+    #[error("too many params in drop index")]
+    TooManyParamsInDropIndex,
+
     #[error("unsupported statement: {0}")]
     UnsupportedStatement(String),
 
diff --git a/src/translate/mod.rs b/src/translate/mod.rs
index 38c90046..8732c2e8 100644
--- a/src/translate/mod.rs
+++ b/src/translate/mod.rs
@@ -7,13 +7,13 @@ mod function;
 mod operator;
 mod query;
 
-pub use error::TranslateError;
+pub use self::{error::TranslateError, expr::translate_expr};
 
 #[cfg(feature = "alter-table")]
 use ddl::translate_alter_table_operation;
 
 use {
-    self::{ddl::translate_column_def, expr::translate_expr, query::translate_query},
+    self::{ddl::translate_column_def, query::translate_query},
     crate::{
         ast::{Assignment, ObjectName, Statement},
         result::Result,
@@ -86,6 +86,40 @@ pub fn translate(sql_statement: &SqlStatement) -> Result<Statement> {
             if_exists: *if_exists,
             names: names.iter().map(translate_object_name).collect(),
         }),
+        #[cfg(feature = "index")]
+        SqlStatement::CreateIndex {
+            name,
+            table_name,
+            columns,
+            ..
+        } => {
+            if columns.len() > 1 {
+                return Err(TranslateError::CompositeIndexNotSupported.into());
+            }
+
+            Ok(Statement::CreateIndex {
+                name: translate_object_name(name),
+                table_name: translate_object_name(table_name),
+                column: translate_expr(&columns[0].expr)?,
+            })
+        }
+        #[cfg(feature = "index")]
+        SqlStatement::Drop {
+            object_type: SqlObjectType::Index,
+            names,
+            ..
+        } => {
+            if names.len() > 1 {
+                return Err(TranslateError::TooManyParamsInDropIndex.into());
+            }
+
+            let object_name: &Vec<SqlIdent> = &names[0].0;
+
+            let table_name = ObjectName(vec![object_name[0].value.to_owned()]);
+            let name = ObjectName(vec![object_name[1].value.to_owned()]);
+
+            Ok(Statement::DropIndex { name, table_name })
+        }
         _ => Err(TranslateError::UnsupportedStatement(sql_statement.to_string()).into()),
     }
 }
diff --git a/src/translate/query.rs b/src/translate/query.rs
index bfd141bb..24907a5a 100644
--- a/src/translate/query.rs
+++ b/src/translate/query.rs
@@ -61,6 +61,10 @@ fn translate_select(sql_select: &SqlSelect) -> Result<Select> {
         ..
     } = sql_select;
 
+    if from.len() > 1 {
+        return Err(TranslateError::TooManyTables.into());
+    }
+
     Ok(Select {
         projection: projection
             .iter()
@@ -69,7 +73,8 @@ fn translate_select(sql_select: &SqlSelect) -> Result<Select> {
         from: from
             .iter()
             .map(translate_table_with_joins)
-            .collect::<Result<_>>()?,
+            .next()
+            .ok_or(TranslateError::LackOfTable)??,
         selection: selection.as_ref().map(translate_expr).transpose()?,
         group_by: group_by.iter().map(translate_expr).collect::<Result<_>>()?,
         having: having.as_ref().map(translate_expr).transpose()?,
@@ -124,6 +129,7 @@ fn translate_table_factor(sql_table_factor: &SqlTableFactor) -> Result<TableFact
                     name: name.value.to_owned(),
                     columns: translate_idents(columns),
                 }),
+            index: None, // query execution plan
         }),
         _ => Err(TranslateError::UnsupportedQueryTableFactor(sql_table_factor.to_string()).into()),
     }
diff --git a/src/utils/vector.rs b/src/utils/vector.rs
index abc244e3..71237f97 100644
--- a/src/utils/vector.rs
+++ b/src/utils/vector.rs
@@ -21,6 +21,13 @@ impl<T> Vector<T> {
         self
     }
 
+    #[cfg(all(feature = "index", feature = "sled-storage"))]
+    pub fn reverse(mut self) -> Self {
+        self.0.reverse();
+
+        self
+    }
+
     pub fn get(&self, i: usize) -> Option<&T> {
         self.0.get(i)
     }


Test patch:
diff --git a/src/tests/alter_table.rs b/src/tests/alter_table.rs
index 85c5d56b..b0a905d6 100644
--- a/src/tests/alter_table.rs
+++ b/src/tests/alter_table.rs
@@ -97,13 +97,14 @@ test_case!(add_drop, async move {
                             expr: Expr::Identifier("id".to_owned()),
                             label: "id".to_owned(),
                         }],
-                        from: vec![TableWithJoins {
+                        from: TableWithJoins {
                             relation: TableFactor::Table {
                                 name: ObjectName(vec!["Bar".to_owned()]),
                                 alias: None,
+                                index: None,
                             },
                             joins: vec![],
-                        }],
+                        },
                         selection: None,
                         group_by: vec![],
                         having: None,
diff --git a/src/tests/error.rs b/src/tests/error.rs
index 52a7d31d..558c3dfd 100644
--- a/src/tests/error.rs
+++ b/src/tests/error.rs
@@ -49,9 +49,10 @@ test_case!(error, async move {
             "SELECT * FROM Nothing;",
         ),
         (
-            SelectError::TooManyTables.into(),
+            TranslateError::TooManyTables.into(),
             "SELECT * FROM TableA, TableB",
         ),
+        (TranslateError::LackOfTable.into(), "SELECT 1;"),
         (
             TranslateError::UnsupportedQueryTableFactor(
                 "(SELECT * FROM TableB) AS TableC".to_owned(),
diff --git a/src/tests/index/and.rs b/src/tests/index/and.rs
new file mode 100644
index 00000000..21f21f7b
--- /dev/null
+++ b/src/tests/index/and.rs
@@ -0,0 +1,138 @@
+use crate::*;
+
+test_case!(and, async move {
+    run!(
+        r#"
+CREATE TABLE NullIdx (
+    id INTEGER,
+    date DATE,
+    flag BOOLEAN
+)"#
+    );
+
+    run!(
+        r#"
+        INSERT INTO NullIdx
+            (id, date, flag)
+        VALUES
+            (1, "2020-03-20", True),
+            (2, "2021-01-01", True),
+            (3, "1989-02-01", False),
+            (4, "2002-06-11", True),
+            (5, "2030-03-01", False);
+    "#
+    );
+
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_id ON NullIdx (id)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_date ON NullIdx (date)"
+    );
+
+    use ast::IndexOperator::*;
+    use Value::*;
+
+    macro_rules! date {
+        ($date: expr) => {
+            $date.parse().unwrap()
+        };
+    }
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false;
+            5     date!("2030-03-01")   false
+        )),
+        idx!(idx_date, Lt, r#"DATE "2040-12-24""#),
+        r#"
+        SELECT id, date, flag FROM NullIdx
+        WHERE
+            date < DATE "2040-12-24"
+            AND flag = false
+        "#
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false
+        )),
+        idx!(idx_date, Lt, r#"DATE "2020-12-24""#),
+        r#"
+        SELECT * FROM NullIdx
+        WHERE
+            flag = False
+            AND date < DATE "2020-12-24"
+        "#
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false;
+            5     date!("2030-03-01")   false
+        )),
+        idx!(idx_date, Lt, r#"DATE "2030-11-24""#),
+        r#"
+        SELECT * FROM NullIdx
+        WHERE
+            flag = False
+            AND DATE "2030-11-24" > date
+            AND id > 1
+        "#
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false;
+            5     date!("2030-03-01")   false
+        )),
+        idx!(idx_id, Gt, "1"),
+        r#"
+        SELECT * FROM NullIdx
+        WHERE
+            flag = False
+            AND id > 1
+            AND DATE "2030-11-24" > date
+        "#
+    );
+
+    test!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            5     date!("2030-03-01")   false
+        )),
+        r#"
+        SELECT * FROM NullIdx
+        WHERE
+            flag = False
+            AND id * 2 > 6
+        "#
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            5     date!("2030-03-01")   false
+        )),
+        idx!(idx_date, Eq, r#"DATE "2030-03-01""#),
+        r#"
+        SELECT * FROM NullIdx
+        WHERE
+            flag = False
+            AND id * 2 > 6
+            AND (date = DATE "2030-03-01" AND flag != True);
+        "#
+    );
+});
diff --git a/src/tests/index/basic.rs b/src/tests/index/basic.rs
new file mode 100644
index 00000000..7d42da49
--- /dev/null
+++ b/src/tests/index/basic.rs
@@ -0,0 +1,297 @@
+use crate::*;
+
+test_case!(basic, async move {
+    run!(
+        r#"
+CREATE TABLE Test (
+    id INTEGER,
+    num INTEGER,
+    name TEXT
+)"#
+    );
+
+    run!(
+        r#"
+        INSERT INTO Test
+            (id, num, name)
+        VALUES
+            (1, 2, "Hello"),
+            (1, 17, "World"),
+            (11, 7, "Great"),
+            (4, 7, "Job");
+    "#
+    );
+
+    test!(Ok(Payload::CreateIndex), "CREATE INDEX idx_id ON Test (id)");
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_name ON Test (name)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_id2 ON Test (id + num)"
+    );
+
+    use ast::IndexOperator::*;
+    use Value::*;
+
+    test!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            11    7     "Great".to_owned();
+            4     7     "Job".to_owned()
+        )),
+        "SELECT id, num, name FROM Test"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            4     7     "Job".to_owned();
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, Lt, "20"),
+        "SELECT id, num, name FROM Test WHERE id < 20"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            4     7     "Job".to_owned();
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, Lt, "20"),
+        "SELECT id, num, name FROM Test WHERE 20 > id"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            4     7     "Job".to_owned()
+        )),
+        idx!(idx_id, LtEq, "4"),
+        "SELECT id, num, name FROM Test WHERE id <= 4"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            4     7     "Job".to_owned()
+        )),
+        idx!(idx_id, LtEq, "4"),
+        "SELECT id, num, name FROM Test WHERE 4 >= id"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            4     7     "Job".to_owned();
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, GtEq, "4"),
+        "SELECT id, num, name FROM Test WHERE id >= 4"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            4     7     "Job".to_owned();
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, GtEq, "4"),
+        "SELECT id, num, name FROM Test WHERE 4 <= id"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, Gt, "4"),
+        "SELECT id, num, name FROM Test WHERE id > 4"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id, Gt, "4"),
+        "SELECT id, num, name FROM Test WHERE 4 < id"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned()
+        )),
+        idx!(idx_id, Eq, "1"),
+        "SELECT id, num, name FROM Test WHERE id = 1"
+    );
+
+    test!(
+        Ok(Payload::Insert(1)),
+        "INSERT INTO Test (id, num, name) VALUES (1, 30, \"New one\")"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned();
+            1     17    "World".to_owned();
+            1     30    "New one".to_owned()
+        )),
+        idx!(idx_id, Eq, "1"),
+        "SELECT id, num, name FROM Test WHERE 1 = id"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     30    "New one".to_owned()
+        )),
+        idx!(idx_name, Eq, r#""New one""#),
+        r#"SELECT id, num, name FROM Test WHERE name = "New one""#
+    );
+
+    test_idx!(
+        Ok(Payload::Select {
+            labels: vec!["id".to_owned(), "num".to_owned(), "name".to_owned()],
+            rows: vec![]
+        }),
+        idx!(idx_id2, Eq, "10"),
+        "SELECT id, num, name FROM Test WHERE id + num = 10"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned()
+        )),
+        idx!(idx_id2, Lt, "11"),
+        "SELECT id, num, name FROM Test WHERE id + num < 11"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned()
+        )),
+        idx!(idx_id2, Lt, "11"),
+        "SELECT id, num, name FROM Test WHERE 11 > id + num"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     17    "World".to_owned();
+            11    7     "Great".to_owned()
+        )),
+        idx!(idx_id2, Eq, "18"),
+        "SELECT id, num, name FROM Test WHERE id + num = 18"
+    );
+
+    test!(Ok(Payload::Delete(1)), "DELETE FROM Test WHERE id = 11");
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            1     2     "Hello".to_owned()
+        )),
+        idx!(idx_id2, Eq, "3"),
+        "SELECT id, num, name FROM Test WHERE id + num = 3"
+    );
+
+    test!(
+        Ok(Payload::Update(3)),
+        "UPDATE Test SET id = id + 1 WHERE id = 1;"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            2     17    "World".to_owned()
+        )),
+        idx!(idx_id2, Eq, "19"),
+        "SELECT * FROM Test WHERE 19 = id + num"
+    );
+
+    test!(Ok(Payload::DropIndex), "DROP INDEX Test.idx_id2;");
+    test!(
+        Ok(select!(
+            id  | num | name
+            I64 | I64 | Str;
+            2     17    "World".to_owned()
+        )),
+        "SELECT * FROM Test WHERE id + num = 19"
+    );
+
+    test!(
+        Ok(Payload::Select {
+            labels: vec!["id".to_owned()],
+            rows: vec![],
+        }),
+        "SELECT id FROM Test WHERE id + num = id"
+    );
+
+    test!(
+        Err(TranslateError::CompositeIndexNotSupported.into()),
+        "CREATE INDEX idx_com ON Test (id, num)"
+    );
+
+    test!(
+        Err(TranslateError::TooManyParamsInDropIndex.into()),
+        "DROP INDEX Test.idx_id, Test.idx_id2"
+    );
+
+    test!(
+        Err(EvaluateError::UnsupportedStatelessExpr(format!(
+            "{:#?}",
+            ast::Expr::CompoundIdentifier(vec!["a".to_owned(), "b".to_owned()])
+        ))
+        .into()),
+        "CREATE INDEX idx_wow On Test (a.b)"
+    );
+
+    test!(
+        Err(IndexError::TableNotFound("Abc".to_owned()).into()),
+        "CREATE INDEX idx_wow ON Abc (name)"
+    );
+
+    test!(
+        Err(IndexError::IndexNameAlreadyExists("idx_name".to_owned()).into()),
+        "CREATE INDEX idx_name ON Test (name || id)"
+    );
+
+    test!(
+        Err(IndexError::IndexNameDoesNotExist("idx_aaa".to_owned()).into()),
+        "DROP INDEX Test.idx_aaa"
+    );
+});
diff --git a/src/tests/index/mod.rs b/src/tests/index/mod.rs
new file mode 100644
index 00000000..218fb761
--- /dev/null
+++ b/src/tests/index/mod.rs
@@ -0,0 +1,9 @@
+mod and;
+mod basic;
+mod null;
+mod value;
+
+pub use and::and;
+pub use basic::basic;
+pub use null::null;
+pub use value::value;
diff --git a/src/tests/index/null.rs b/src/tests/index/null.rs
new file mode 100644
index 00000000..60089493
--- /dev/null
+++ b/src/tests/index/null.rs
@@ -0,0 +1,119 @@
+use crate::*;
+
+test_case!(null, async move {
+    run!(
+        r#"
+CREATE TABLE NullIdx (
+    id INTEGER NULL,
+    date DATE NULL,
+    flag BOOLEAN NULL
+)"#
+    );
+
+    run!(
+        r#"
+        INSERT INTO NullIdx
+            (id, date, flag)
+        VALUES
+            (NULL, NULL,         True),
+            (1,    "2020-03-20", True),
+            (2,    NULL,         NULL),
+            (3,    "1989-02-01", False),
+            (4,    NULL,         True);
+    "#
+    );
+
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_id ON NullIdx (id)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_date ON NullIdx (date)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_flag ON NullIdx (flag)"
+    );
+
+    use ast::IndexOperator::*;
+    use Value::*;
+
+    macro_rules! date {
+        ($date: expr) => {
+            $date.parse().unwrap()
+        };
+    }
+
+    test_idx!(
+        Ok(select!(
+            id  | date                | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false;
+            1     date!("2020-03-20")   true
+        )),
+        idx!(idx_date, Lt, r#"DATE "2040-12-24""#),
+        r#"SELECT id, date, flag FROM NullIdx WHERE date < DATE "2040-12-24""#
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | date | flag;
+            Null     Null   Bool(true);
+            I64(2)   Null   Null;
+            I64(4)   Null   Bool(true)
+        )),
+        idx!(idx_date, GtEq, r#"DATE "2040-12-24""#),
+        r#"SELECT id, date, flag FROM NullIdx WHERE date >= DATE "2040-12-24""#
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | date                      | flag;
+            Null     Null                        Bool(true);
+            I64(1)   Date(date!("2020-03-20"))   Bool(true);
+            I64(4)   Null                        Bool(true)
+        )),
+        idx!(idx_flag, Eq, "True"),
+        "SELECT * FROM NullIdx WHERE flag = True"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | date                      | flag;
+            I64(3)   Date(date!("1989-02-01"))   Bool(false);
+            I64(4)   Null                        Bool(true);
+            Null     Null                        Bool(true)
+        )),
+        idx!(idx_id, Gt, "2"),
+        "SELECT * FROM NullIdx WHERE id > 2"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id   | date | flag;
+            Null   Null   Bool(true)
+        )),
+        idx!(idx_id, Eq, "NULL"),
+        "SELECT * FROM NullIdx WHERE id IS NULL"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id     | date | flag
+            I64 | Date                | Bool;
+            3     date!("1989-02-01")   false;
+            1     date!("2020-03-20")   true
+        )),
+        idx!(idx_date, Lt, "NULL"),
+        "SELECT id, date, flag FROM NullIdx WHERE date IS NOT NULL"
+    );
+
+    test!(
+        Ok(Payload::Select {
+            labels: vec!["id".to_owned(), "date".to_owned(), "flag".to_owned()],
+            rows: vec![],
+        }),
+        "SELECT * FROM NullIdx WHERE id = NULL"
+    );
+});
diff --git a/src/tests/index/value.rs b/src/tests/index/value.rs
new file mode 100644
index 00000000..1ef74748
--- /dev/null
+++ b/src/tests/index/value.rs
@@ -0,0 +1,129 @@
+use crate::*;
+
+test_case!(value, async move {
+    run!(
+        r#"
+CREATE TABLE IdxValue (
+    id INTEGER NULL,
+    time TIME NULL,
+    flag BOOLEAN
+)"#
+    );
+
+    run!(
+        r#"
+        INSERT INTO IdxValue
+        VALUES
+            (NULL, "01:30 PM", True),
+            (1,    "12:10 AM", False),
+            (2,    NULL,       True);
+    "#
+    );
+
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_id ON IdxValue (id)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_time ON IdxValue (time)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_flag ON IdxValue (flag)"
+    );
+
+    use ast::IndexOperator::*;
+    use chrono::NaiveTime;
+    use Value::*;
+
+    let t = |h, m| NaiveTime::from_hms(h, m, 0);
+
+    test_idx!(
+        Ok(select!(
+            id  | time     | flag
+            I64 | Time     | Bool;
+            1     t(0, 10)    false
+        )),
+        idx!(idx_id, Eq, "1"),
+        "SELECT * FROM IdxValue WHERE id = 1"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | time            | flag;
+            I64(1)   Time(t(0, 10))    Bool(false);
+            Null     Time(t(13, 30))   Bool(true)
+        )),
+        idx!(idx_time, LtEq, r#"TIME "13:30:00""#),
+        r#"SELECT * FROM IdxValue WHERE time <= TIME "13:30:00""#
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | time           | flag;
+            I64(1)   Time(t(0, 10))   Bool(false)
+        )),
+        idx!(idx_flag, Eq, r#"("ABC" IS NULL)"#),
+        r#"SELECT * FROM IdxValue WHERE flag = ("ABC" IS NULL)"#
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | time            | flag;
+            Null     Time(t(13, 30))   Bool(true);
+            I64(2)   Null              Bool(true)
+        )),
+        idx!(idx_flag, Eq, "(100 IS NOT NULL)"),
+        "SELECT * FROM IdxValue WHERE flag = (100 IS NOT NULL)"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | time     | flag
+            I64 | Time     | Bool;
+            1     t(0, 10)   false
+        )),
+        idx!(idx_id, Eq, "+1"),
+        "SELECT * FROM IdxValue WHERE id = +1"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | time      | flag
+            I64 | Time      | Bool;
+            1     t(0, 10)    false
+        )),
+        idx!(idx_id, Eq, r#"CAST("1" AS INTEGER)"#),
+        r#"SELECT * FROM IdxValue WHERE id = CAST("1" AS INTEGER)"#
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | time      | flag
+            I64 | Time      | Bool;
+            1     t(0, 10)    false
+        )),
+        idx!(idx_id, Eq, "(1)"),
+        "SELECT * FROM IdxValue WHERE id = (1)"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | time | flag;
+            I64(2)   Null   Bool(true)
+        )),
+        idx!(idx_id, Eq, "1 + 1 * 5 / 5"),
+        "SELECT * FROM IdxValue WHERE id = 1 + 1 * 5 / 5"
+    );
+
+    test_idx!(
+        Ok(select!(
+            id  | time     | flag
+            I64 | Time     | Bool;
+            1     t(0, 10)   false
+        )),
+        idx!(idx_flag, Eq, "(True AND False)"),
+        "SELECT * FROM IdxValue WHERE flag = (True AND False)"
+    );
+});
diff --git a/src/tests/macros.rs b/src/tests/macros.rs
index 3c16b046..4657952b 100644
--- a/src/tests/macros.rs
+++ b/src/tests/macros.rs
@@ -5,6 +5,17 @@ macro_rules! row {
     )
 }
 
+#[macro_export]
+macro_rules! idx {
+    ($name: path, $op: path, $sql_expr: literal) => {
+        vec![ast::IndexItem {
+            name: stringify!($name).to_owned(),
+            op: $op,
+            value_expr: translate_expr(&parse_expr($sql_expr).unwrap()).unwrap(),
+        }]
+    };
+}
+
 #[macro_export]
 macro_rules! select {
     ( $( $c: tt )|+ $( ; )? $( $t: path )|+ ; $( $v: expr )+ ; $( $( $v2: expr )+ );+) => ({
diff --git a/src/tests/mod.rs b/src/tests/mod.rs
index 66952317..e9d17ae7 100644
--- a/src/tests/mod.rs
+++ b/src/tests/mod.rs
@@ -12,6 +12,8 @@ pub mod drop_table;
 pub mod error;
 pub mod filter;
 pub mod function;
+#[cfg(feature = "index")]
+pub mod index;
 pub mod join;
 pub mod migrate;
 pub mod nested_select;
@@ -26,21 +28,6 @@ pub mod macros;
 
 pub use tester::*;
 
-#[cfg(feature = "alter-table")]
-#[macro_export]
-macro_rules! generate_alter_table_tests {
-    () => {
-        glue!(alter_table_rename, alter_table::rename);
-        glue!(alter_table_add_drop, alter_table::add_drop);
-    };
-}
-
-#[cfg(not(feature = "alter-table"))]
-#[macro_export]
-macro_rules! generate_alter_table_tests {
-    () => {};
-}
-
 #[macro_export]
 macro_rules! generate_tests {
     ($test: meta, $storage: ident) => {
@@ -88,6 +75,27 @@ macro_rules! generate_tests {
         glue!(validate_unique, validate::unique::unique);
         glue!(validate_types, validate::types::types);
 
-        generate_alter_table_tests!();
+        #[cfg(feature = "index")]
+        macro_rules! glue_index {
+            () => {
+                glue!(index_basic, index::basic);
+                glue!(index_and, index::and);
+                glue!(index_null, index::null);
+                glue!(index_value, index::value);
+            };
+        }
+
+        #[cfg(feature = "alter-table")]
+        macro_rules! glue_alter_table {
+            () => {
+                glue!(alter_table_rename, alter_table::rename);
+                glue!(alter_table_add_drop, alter_table::add_drop);
+            };
+        }
+
+        #[cfg(feature = "index")]
+        glue_index!();
+        #[cfg(feature = "alter-table")]
+        glue_alter_table!();
     };
 }
diff --git a/src/tests/tester.rs b/src/tests/tester.rs
index aceb0fc3..3505ce24 100644
--- a/src/tests/tester.rs
+++ b/src/tests/tester.rs
@@ -1,18 +1,21 @@
 use {
     crate::{
+        ast::IndexItem,
         executor::{execute, Payload},
         parse_sql::parse,
+        plan::plan,
         result::Result,
-        store::{AlterTable, Store, StoreMut},
+        store::{GStore, GStoreMut},
         translate::translate,
     },
     async_trait::async_trait,
     std::{cell::RefCell, fmt::Debug, rc::Rc},
 };
 
-pub async fn run<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
+pub async fn run<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
     cell: Rc<RefCell<Option<U>>>,
     sql: &str,
+    indexes: Option<Vec<IndexItem>>,
 ) -> Result<Payload> {
     let storage = cell.replace(None).unwrap();
 
@@ -31,6 +34,18 @@ pub async fn run<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
 
     let parsed = try_run!(parse(sql));
     let statement = try_run!(translate(&parsed[0]));
+    let statement = try_run!(plan(&storage, statement).await);
+
+    if let Some(indexes) = indexes {
+        let statement = format!("{:?}", statement);
+        let indexes = indexes.into_iter().map(|v| format!("{:?}", v));
+
+        for index in indexes {
+            if !statement.contains(&index) {
+                panic!("index does not exist: {}", index);
+            }
+        }
+    }
 
     match execute(storage, &statement).await {
         Ok((storage, payload)) => {
@@ -55,7 +70,7 @@ pub async fn run<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable>(
 /// Actual test cases are in [/src/tests/](https://github.com/gluesql/gluesql/blob/main/src/tests/),
 /// not in `/tests/`.
 #[async_trait]
-pub trait Tester<T: 'static + Debug, U: Store<T> + StoreMut<T> + AlterTable> {
+pub trait Tester<T: 'static + Debug, U: GStore<T> + GStoreMut<T>> {
     fn new(namespace: &str) -> Self;
 
     fn get_cell(&mut self) -> Rc<RefCell<Option<U>>>;
@@ -67,7 +82,7 @@ macro_rules! test_case {
         pub async fn $name<T, U>(mut tester: impl tests::Tester<T, U>)
         where
             T: 'static + std::fmt::Debug,
-            U: Store<T> + StoreMut<T> + AlterTable,
+            U: GStore<T> + GStoreMut<T>,
         {
             use std::rc::Rc;
 
@@ -76,14 +91,14 @@ macro_rules! test_case {
             #[allow(unused_macros)]
             macro_rules! run {
                 ($sql: expr) => {
-                    tests::run(Rc::clone(&cell), $sql).await.unwrap()
+                    tests::run(Rc::clone(&cell), $sql, None).await.unwrap()
                 };
             }
 
             #[allow(unused_macros)]
             macro_rules! count {
                 ($count: expr, $sql: expr) => {
-                    match tests::run(Rc::clone(&cell), $sql).await.unwrap() {
+                    match tests::run(Rc::clone(&cell), $sql, None).await.unwrap() {
                         Payload::Select { rows, .. } => assert_eq!($count, rows.len()),
                         Payload::Delete(num) => assert_eq!($count, num),
                         Payload::Update(num) => assert_eq!($count, num),
@@ -95,7 +110,16 @@ macro_rules! test_case {
             #[allow(unused_macros)]
             macro_rules! test {
                 ($expected: expr, $sql: expr) => {
-                    let found = tests::run(Rc::clone(&cell), $sql).await;
+                    let found = tests::run(Rc::clone(&cell), $sql, None).await;
+
+                    test($expected, found);
+                };
+            }
+
+            #[allow(unused_macros)]
+            macro_rules! test_idx {
+                ($expected: expr, $indexes: expr, $sql: expr) => {
+                    let found = tests::run(Rc::clone(&cell), $sql, Some($indexes)).await;
 
                     test($expected, found);
                 };
diff --git a/tests/sled_storage.rs b/tests/sled_storage.rs
index 7f4648a2..d3ffbb19 100644
--- a/tests/sled_storage.rs
+++ b/tests/sled_storage.rs
@@ -3,7 +3,7 @@
 use sled::IVec;
 use std::{cell::RefCell, convert::TryFrom, rc::Rc};
 
-use gluesql::{generate_alter_table_tests, generate_tests, sled, tests::*, SledStorage};
+use gluesql::{generate_tests, sled, tests::*, SledStorage};
 
 struct SledTester {
     storage: Rc<RefCell<Option<SledStorage>>>,