Repository: gluesql/gluesql
Pull request #244 (2021-06-22 07:20:21)

Implement ORDER BY {expr} index support
Now, Index can be applied to `ORDER BY` clause.
Query planner can catch index in `ORDER BY`.

e.g.
```sql
SELECT * FROM Test ORDER BY id DESC;

SELECT * FROM Test ORDER BY name || id ASC:
SELECT * FROM Test ORDER BY name || id;
```



Patch:
diff --git a/src/ast/mod.rs b/src/ast/mod.rs
index af125b04..6081d858 100644
--- a/src/ast/mod.rs
+++ b/src/ast/mod.rs
@@ -75,7 +75,7 @@ pub enum Statement {
     CreateIndex {
         name: ObjectName,
         table_name: ObjectName,
-        column: Expr,
+        column: OrderByExpr,
     },
     /// DROP INDEX
     #[cfg(feature = "index")]
diff --git a/src/ast/query.rs b/src/ast/query.rs
index 29b4bb83..d7b50043 100644
--- a/src/ast/query.rs
+++ b/src/ast/query.rs
@@ -46,8 +46,8 @@ pub struct TableWithJoins {
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub struct IndexItem {
     pub name: String,
-    pub op: IndexOperator,
-    pub value_expr: Expr,
+    pub asc: Option<bool>,
+    pub cmp_expr: Option<(IndexOperator, Expr)>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
@@ -87,7 +87,7 @@ pub enum JoinConstraint {
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub struct OrderByExpr {
     pub expr: Expr,
-    pub asc: bool,
+    pub asc: Option<bool>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
diff --git a/src/data/mod.rs b/src/data/mod.rs
index 3321bc10..2836af55 100644
--- a/src/data/mod.rs
+++ b/src/data/mod.rs
@@ -10,7 +10,7 @@ pub use {
     interval::{Interval, IntervalError},
     literal::{Literal, LiteralError},
     row::{Row, RowError},
-    schema::Schema,
+    schema::{Schema, SchemaIndex, SchemaIndexOrd},
     table::{get_name, Table, TableError},
     value::{Value, ValueError},
 };
diff --git a/src/data/schema.rs b/src/data/schema.rs
index 22d1759f..6f4b927d 100644
--- a/src/data/schema.rs
+++ b/src/data/schema.rs
@@ -3,11 +3,25 @@ use {
     serde::{Deserialize, Serialize},
 };
 
+#[derive(Clone, Copy, Serialize, Deserialize)]
+pub enum SchemaIndexOrd {
+    Asc,
+    Desc,
+    Both,
+}
+
+#[derive(Clone, Serialize, Deserialize)]
+pub struct SchemaIndex {
+    pub name: String,
+    pub expr: Expr,
+    pub order: SchemaIndexOrd,
+}
+
 #[derive(Clone, Serialize, Deserialize)]
 pub struct Schema {
     pub table_name: String,
     pub column_defs: Vec<ColumnDef>,
-    pub indexes: Vec<(String, Expr)>,
+    pub indexes: Vec<SchemaIndex>,
 }
 
 pub trait ColumnDefExt {
diff --git a/src/executor/alter/alter_table.rs b/src/executor/alter/alter_table.rs
index 575e6e5b..490bd946 100644
--- a/src/executor/alter/alter_table.rs
+++ b/src/executor/alter/alter_table.rs
@@ -4,7 +4,7 @@ use {
     super::validate,
     crate::{
         ast::{AlterTableOperation, ObjectName},
-        data::get_name,
+        data::{get_name, SchemaIndex},
         result::MutResult,
         store::{GStore, GStoreMut},
     },
@@ -78,13 +78,13 @@ pub async fn alter_table<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
 
                 let indexes = indexes
                     .iter()
-                    .filter(|(_, expr)| find_column(expr, column_name))
+                    .filter(|SchemaIndex { expr, .. }| find_column(expr, column_name))
                     .map(Ok);
 
                 stream::iter(indexes)
-                    .try_fold(storage, |storage, (index_name, _)| async move {
+                    .try_fold(storage, |storage, SchemaIndex { name, .. }| async move {
                         storage
-                            .drop_index(table_name, index_name)
+                            .drop_index(table_name, name)
                             .await
                             .map(|(storage, _)| storage)
                     })
diff --git a/src/executor/alter/index.rs b/src/executor/alter/index.rs
index 243034de..3b612ea4 100644
--- a/src/executor/alter/index.rs
+++ b/src/executor/alter/index.rs
@@ -3,7 +3,7 @@
 use {
     super::AlterError,
     crate::{
-        ast::{ColumnDef, Expr, ObjectName},
+        ast::{ColumnDef, Expr, ObjectName, OrderByExpr},
         data::{get_name, Schema},
         result::MutResult,
         store::{GStore, GStoreMut},
@@ -15,11 +15,12 @@ pub async fn create_index<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
     storage: U,
     table_name: &ObjectName,
     index_name: &ObjectName,
-    expr: &Expr,
+    column: &OrderByExpr,
 ) -> MutResult<U, ()> {
     let names = (|| async {
         let table_name = get_name(table_name)?;
         let index_name = get_name(index_name)?;
+        let expr = &column.expr;
         let Schema { column_defs, .. } = storage
             .fetch_schema(table_name)
             .await?
@@ -47,7 +48,7 @@ pub async fn create_index<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
         }
     };
 
-    storage.create_index(table_name, index_name, expr).await
+    storage.create_index(table_name, index_name, column).await
 }
 
 fn validate_index_expr(columns: &[String], expr: &Expr) -> (bool, bool) {
diff --git a/src/executor/select/mod.rs b/src/executor/select/mod.rs
index e92fc754..667b2108 100644
--- a/src/executor/select/mod.rs
+++ b/src/executor/select/mod.rs
@@ -27,11 +27,7 @@ use {
 };
 
 #[cfg(feature = "index")]
-use {
-    super::evaluate::evaluate,
-    crate::{ast::IndexItem, data::Value},
-    std::convert::TryInto,
-};
+use {super::evaluate::evaluate, crate::ast::IndexItem, std::convert::TryInto};
 
 async fn fetch_blended<'a, T: 'static + Debug>(
     storage: &dyn GStore<T>,
@@ -51,14 +47,20 @@ async fn fetch_blended<'a, T: 'static + Debug>(
         match table.get_index() {
             Some(IndexItem {
                 name: index_name,
-                op: index_op,
-                value_expr,
+                asc,
+                cmp_expr,
             }) => {
-                let evaluated = evaluate(storage, None, None, value_expr).await?;
-                let index_value: Value = evaluated.try_into()?;
+                let cmp_value = match cmp_expr {
+                    Some((op, expr)) => {
+                        let evaluated = evaluate(storage, None, None, expr).await?;
+
+                        Some((op, evaluated.try_into()?))
+                    }
+                    None => None,
+                };
 
                 storage
-                    .scan_indexed_data(table_name, index_name, index_op, index_value)
+                    .scan_indexed_data(table_name, index_name, *asc, cmp_value)
                     .await
                     .map(Rows::Indexed)?
             }
diff --git a/src/executor/sort.rs b/src/executor/sort.rs
index 4a0722c9..19cb0a61 100644
--- a/src/executor/sort.rs
+++ b/src/executor/sort.rs
@@ -87,10 +87,10 @@ impl<'a, T: 'static + Debug> Sort<'a, T> {
                     .iter()
                     .map(|(a, _)| a)
                     .zip(values_b.iter())
-                    .map(|(a, (b, asc))| (a, b, asc));
+                    .map(|(a, (b, asc))| (a, b, asc.unwrap_or(true)));
 
                 for (value_a, value_b, asc) in pairs {
-                    let apply_asc = |ord: Ordering| if *asc { ord } else { ord.reverse() };
+                    let apply_asc = |ord: Ordering| if asc { ord } else { ord.reverse() };
 
                     match (value_a, value_b) {
                         (Value::Null, Value::Null) => {}
diff --git a/src/plan.rs b/src/plan.rs
index 62a539d0..b10da725 100644
--- a/src/plan.rs
+++ b/src/plan.rs
@@ -1,10 +1,10 @@
 use {
     crate::{
         ast::{
-            AstLiteral, BinaryOperator, Expr, IndexItem, IndexOperator, Query, Select, SetExpr,
-            Statement, TableFactor, TableWithJoins,
+            AstLiteral, BinaryOperator, Expr, IndexItem, IndexOperator, OrderByExpr, Query, Select,
+            SetExpr, Statement, TableFactor, TableWithJoins,
         },
-        data::{get_name, Schema},
+        data::{get_name, Schema, SchemaIndex, SchemaIndexOrd},
         result::Result,
         store::Store,
     },
@@ -25,6 +25,36 @@ pub async fn plan<T: 'static + Debug>(
     }
 }
 
+struct Indexes(Vec<SchemaIndex>);
+
+impl Indexes {
+    fn find(&self, target: &Expr) -> Option<String> {
+        self.0
+            .iter()
+            .find(|SchemaIndex { expr, .. }| expr == target)
+            .map(|SchemaIndex { name, .. }| name.to_owned())
+    }
+
+    fn find_ordered(&self, target: &OrderByExpr) -> Option<String> {
+        self.0
+            .iter()
+            .find(|SchemaIndex { expr, order, .. }| {
+                if expr != &target.expr {
+                    return false;
+                }
+
+                matches!(
+                    (target.asc, order),
+                    (_, SchemaIndexOrd::Both)
+                        | (Some(true), SchemaIndexOrd::Asc)
+                        | (None, SchemaIndexOrd::Asc)
+                        | (Some(false), SchemaIndexOrd::Desc)
+                )
+            })
+            .map(|SchemaIndex { name, .. }| name.to_owned())
+    }
+}
+
 async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) -> Result<Query> {
     let Query {
         body,
@@ -34,7 +64,7 @@ async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) ->
     } = query;
 
     let select = match body {
-        SetExpr::Select(select) => plan_select(storage, *select).await.map(Box::new)?,
+        SetExpr::Select(select) => select,
         SetExpr::Values(_) => {
             return Ok(Query {
                 body,
@@ -45,29 +75,82 @@ async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) ->
         }
     };
 
-    let body = SetExpr::Select(select);
-    let query = Query {
-        body,
-        order_by,
-        limit,
-        offset,
+    let TableWithJoins { relation, .. } = &select.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(Query {
+                body: SetExpr::Select(select),
+                order_by,
+                limit,
+                offset,
+            });
+        }
     };
 
-    Ok(query)
-}
+    let index = order_by.get(0).and_then(|value_expr| {
+        indexes.find_ordered(&value_expr).map(|name| IndexItem {
+            name,
+            asc: value_expr.asc,
+            cmp_expr: None,
+        })
+    });
 
-struct Indexes(Vec<(String, Expr)>);
+    match (order_by.len(), index) {
+        (1, index) if index.is_some() => {
+            let Select {
+                projection,
+                from,
+                selection,
+                group_by,
+                having,
+            } = *select;
 
-impl Indexes {
-    fn find(&self, target: &Expr) -> Option<String> {
-        self.0
-            .iter()
-            .find(|(_, expr)| expr == target)
-            .map(|(index_name, _)| index_name.to_owned())
+            let TableWithJoins { relation, joins } = from;
+            let (name, alias) = match relation {
+                TableFactor::Table { name, alias, .. } => (name, alias),
+            };
+
+            let from = TableWithJoins {
+                relation: TableFactor::Table { name, alias, index },
+                joins,
+            };
+
+            let select = Select {
+                projection,
+                from,
+                selection,
+                group_by,
+                having,
+            };
+
+            Ok(Query {
+                body: SetExpr::Select(Box::new(select)),
+                order_by: vec![],
+                limit,
+                offset,
+            })
+        }
+        _ => {
+            let select = plan_select(&indexes, *select).await?;
+            let body = SetExpr::Select(Box::new(select));
+            let query = Query {
+                body,
+                order_by,
+                limit,
+                offset,
+            };
+
+            Ok(query)
+        }
     }
 }
 
-async fn plan_select<T: 'static + Debug>(storage: &dyn Store<T>, select: Select) -> Result<Select> {
+async fn plan_select(indexes: &Indexes, select: Select) -> Result<Select> {
     let Select {
         projection,
         from,
@@ -76,26 +159,6 @@ async fn plan_select<T: 'static + Debug>(storage: &dyn Store<T>, select: Select)
         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 => {
@@ -130,8 +193,8 @@ async fn plan_select<T: 'static + Debug>(storage: &dyn Store<T>, select: Select)
 
             let index = Some(IndexItem {
                 name: index_name,
-                op: index_op,
-                value_expr: index_value_expr,
+                asc: None,
+                cmp_expr: Some((index_op, index_value_expr)),
             });
             let from = TableWithJoins {
                 relation: TableFactor::Table { name, alias, index },
diff --git a/src/storages/sled_storage/index.rs b/src/storages/sled_storage/index.rs
index ca8f572e..c2a8d3f6 100644
--- a/src/storages/sled_storage/index.rs
+++ b/src/storages/sled_storage/index.rs
@@ -14,7 +14,7 @@ use {
         IndexError, Value,
     },
     async_trait::async_trait,
-    iter_enum::Iterator,
+    iter_enum::{DoubleEndedIterator, Iterator},
     sled::IVec,
     std::iter::{empty, once},
 };
@@ -25,90 +25,110 @@ impl Index<IVec> for SledStorage {
         &self,
         table_name: &str,
         index_name: &str,
-        op: &IndexOperator,
-        value: Value,
+        asc: Option<bool>,
+        cmp_value: Option<(&IndexOperator, Value)>,
     ) -> Result<RowIter<IVec>> {
         let index_data_ids = {
-            #[derive(Iterator)]
-            enum DataIds<I1, I2, I3> {
+            #[derive(Iterator, DoubleEndedIterator)]
+            enum DataIds<I1, I2, I3, I4> {
                 Empty(I1),
                 Once(I2),
                 Range(I3),
+                Full(I4),
             }
 
             let map = |item: std::result::Result<_, _>| item.map(|(_, v)| v);
-            let incr = |key: Vec<u8>| {
-                key.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 lower = || build_index_key_prefix(table_name, index_name);
-            let upper = || incr(build_index_key_prefix(table_name, index_name));
-            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::Range(self.tree.range(incr(key)..upper()).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)),
+            match cmp_value {
+                None => {
+                    let prefix = build_index_key_prefix(table_name, index_name);
+
+                    DataIds::Full(self.tree.scan_prefix(prefix).map(map))
+                }
+                Some((op, value)) => {
+                    let incr = |key: Vec<u8>| {
+                        key.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 lower = || build_index_key_prefix(table_name, index_name);
+                    let upper = || incr(build_index_key_prefix(table_name, index_name));
+                    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::Range(self.tree.range(incr(key)..upper()).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 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 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 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)?;
 
-                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))
+                });
 
-                        Ok((data_key, value))
-                    });
+            Rows::Ok(rows)
+        };
 
-                Rows::Ok(rows)
-            },
-        );
+        let index_data_ids = index_data_ids.map(|v| v.map_err(err_into));
 
-        Ok(Box::new(rows))
+        Ok(match asc {
+            Some(true) | None => Box::new(index_data_ids.flat_map(flat_map)),
+            Some(false) => Box::new(index_data_ids.rev().flat_map(flat_map)),
+        })
     }
 }
diff --git a/src/storages/sled_storage/index_mut.rs b/src/storages/sled_storage/index_mut.rs
index c58b7495..6dcdf852 100644
--- a/src/storages/sled_storage/index_mut.rs
+++ b/src/storages/sled_storage/index_mut.rs
@@ -5,8 +5,8 @@ use {
         err_into, error::StorageError, fetch_schema, index_sync::IndexSync, scan_data, SledStorage,
     },
     crate::{
-        ast::Expr,
-        data::Schema,
+        ast::OrderByExpr,
+        data::{Schema, SchemaIndex, SchemaIndexOrd},
         result::{MutResult, Result},
         store::IndexMut,
         IndexError,
@@ -61,8 +61,9 @@ impl IndexMut<IVec> for SledStorage {
         self,
         table_name: &str,
         index_name: &str,
-        index_expr: &Expr,
+        column: &OrderByExpr,
     ) -> MutResult<Self, ()> {
+        let index_expr = &column.expr;
         let (schema_key, schema) = try_self!(self, fetch_schema(&self.tree, table_name));
         let Schema {
             column_defs,
@@ -73,7 +74,7 @@ impl IndexMut<IVec> for SledStorage {
             schema.ok_or_else(|| IndexError::ConflictTableNotFound(table_name.to_owned()))
         );
 
-        if indexes.iter().any(|(name, _)| name == index_name) {
+        if indexes.iter().any(|index| index.name == index_name) {
             return Err((
                 self,
                 IndexError::IndexNameAlreadyExists(index_name.to_owned()).into(),
@@ -82,7 +83,11 @@ impl IndexMut<IVec> for SledStorage {
 
         let indexes = indexes
             .into_iter()
-            .chain(once((index_name.to_owned(), index_expr.clone())))
+            .chain(once(SchemaIndex {
+                name: index_name.to_owned(),
+                expr: index_expr.clone(),
+                order: SchemaIndexOrd::Both,
+            }))
             .collect::<Vec<_>>();
 
         let schema = Schema {
@@ -123,7 +128,7 @@ impl IndexMut<IVec> for SledStorage {
             schema.ok_or_else(|| IndexError::TableNotFound(table_name.to_owned()))
         );
 
-        if indexes.iter().all(|(name, _)| name != index_name) {
+        if indexes.iter().all(|index| index.name != index_name) {
             return Err((
                 self,
                 IndexError::IndexNameDoesNotExist(index_name.to_owned()).into(),
@@ -132,7 +137,7 @@ impl IndexMut<IVec> for SledStorage {
 
         let indexes = indexes
             .into_iter()
-            .filter(|(name, _)| name != index_name)
+            .filter(|index| index.name != index_name)
             .collect::<Vec<_>>();
 
         let schema = Schema {
diff --git a/src/storages/sled_storage/index_sync.rs b/src/storages/sled_storage/index_sync.rs
index e627169a..c978e6f8 100644
--- a/src/storages/sled_storage/index_sync.rs
+++ b/src/storages/sled_storage/index_sync.rs
@@ -2,7 +2,9 @@
 
 use {
     super::fetch_schema,
-    crate::{ast::Expr, evaluate_stateless, Error, IndexError, Result, Row, Schema, Value},
+    crate::{
+        ast::Expr, evaluate_stateless, Error, IndexError, Result, Row, Schema, SchemaIndex, Value,
+    },
     sled::{
         transaction::{
             ConflictableTransactionError, ConflictableTransactionResult, TransactionalTree,
@@ -15,7 +17,7 @@ use {
 pub struct IndexSync<'a> {
     table_name: &'a str,
     columns: Vec<String>,
-    indexes: Cow<'a, Vec<(String, Expr)>>,
+    indexes: Cow<'a, Vec<SchemaIndex>>,
 }
 
 impl<'a> From<&'a Schema> for IndexSync<'a> {
@@ -69,7 +71,13 @@ impl<'a> IndexSync<'a> {
         data_key: &IVec,
         row: &Row,
     ) -> ConflictableTransactionResult<(), Error> {
-        for (index_name, index_expr) in self.indexes.iter() {
+        for index in self.indexes.iter() {
+            let SchemaIndex {
+                name: index_name,
+                expr: index_expr,
+                ..
+            } = index;
+
             let index_key =
                 &evaluate_index_key(self.table_name, index_name, index_expr, &self.columns, row)?;
 
@@ -86,7 +94,13 @@ impl<'a> IndexSync<'a> {
         old_row: &Row,
         new_row: &Row,
     ) -> ConflictableTransactionResult<(), Error> {
-        for (index_name, index_expr) in self.indexes.iter() {
+        for index in self.indexes.iter() {
+            let SchemaIndex {
+                name: index_name,
+                expr: index_expr,
+                ..
+            } = index;
+
             let old_index_key = &evaluate_index_key(
                 self.table_name,
                 index_name,
@@ -116,7 +130,13 @@ impl<'a> IndexSync<'a> {
         data_key: &IVec,
         row: &Row,
     ) -> ConflictableTransactionResult<(), Error> {
-        for (index_name, index_expr) in self.indexes.iter() {
+        for index in self.indexes.iter() {
+            let SchemaIndex {
+                name: index_name,
+                expr: index_expr,
+                ..
+            } = index;
+
             let index_key =
                 &evaluate_index_key(self.table_name, index_name, index_expr, &self.columns, row)?;
 
diff --git a/src/store/index.rs b/src/store/index.rs
index fae57eaf..da7da31e 100644
--- a/src/store/index.rs
+++ b/src/store/index.rs
@@ -1,7 +1,7 @@
 use {
     super::RowIter,
     crate::{
-        ast::{Expr, IndexOperator},
+        ast::{IndexOperator, OrderByExpr},
         data::Value,
         result::{MutResult, Result},
     },
@@ -44,8 +44,8 @@ pub trait Index<T: Debug> {
         &self,
         table_name: &str,
         index_name: &str,
-        op: &IndexOperator,
-        value: Value,
+        asc: Option<bool>,
+        cmp_value: Option<(&IndexOperator, Value)>,
     ) -> Result<RowIter<T>>;
 }
 
@@ -58,7 +58,7 @@ where
         self,
         table_name: &str,
         index_name: &str,
-        column: &Expr,
+        column: &OrderByExpr,
     ) -> MutResult<Self, ()>;
 
     async fn drop_index(self, table_name: &str, index_name: &str) -> MutResult<Self, ()>;
diff --git a/src/translate/expr.rs b/src/translate/expr.rs
index b484a18e..f4d56a6a 100644
--- a/src/translate/expr.rs
+++ b/src/translate/expr.rs
@@ -7,10 +7,10 @@ use {
         translate_idents, translate_query, TranslateError,
     },
     crate::{
-        ast::{AstLiteral, Expr},
+        ast::{AstLiteral, Expr, OrderByExpr},
         result::Result,
     },
-    sqlparser::ast::Expr as SqlExpr,
+    sqlparser::ast::{Expr as SqlExpr, OrderByExpr as SqlOrderByExpr},
 };
 
 pub fn translate_expr(sql_expr: &SqlExpr) -> Result<Expr> {
@@ -82,3 +82,20 @@ pub fn translate_expr(sql_expr: &SqlExpr) -> Result<Expr> {
         _ => Err(TranslateError::UnsupportedExpr(sql_expr.to_string()).into()),
     }
 }
+
+pub fn translate_order_by_expr(sql_order_by_expr: &SqlOrderByExpr) -> Result<OrderByExpr> {
+    let SqlOrderByExpr {
+        expr,
+        asc,
+        nulls_first,
+    } = sql_order_by_expr;
+
+    if matches!(nulls_first, Some(_)) {
+        return Err(TranslateError::OrderByNullsFirstOrLastNotSupported.into());
+    }
+
+    Ok(OrderByExpr {
+        expr: translate_expr(expr)?,
+        asc: *asc,
+    })
+}
diff --git a/src/translate/mod.rs b/src/translate/mod.rs
index 8732c2e8..cb443435 100644
--- a/src/translate/mod.rs
+++ b/src/translate/mod.rs
@@ -7,7 +7,10 @@ mod function;
 mod operator;
 mod query;
 
-pub use self::{error::TranslateError, expr::translate_expr};
+pub use self::{
+    error::TranslateError,
+    expr::{translate_expr, translate_order_by_expr},
+};
 
 #[cfg(feature = "alter-table")]
 use ddl::translate_alter_table_operation;
@@ -100,7 +103,7 @@ pub fn translate(sql_statement: &SqlStatement) -> Result<Statement> {
             Ok(Statement::CreateIndex {
                 name: translate_object_name(name),
                 table_name: translate_object_name(table_name),
-                column: translate_expr(&columns[0].expr)?,
+                column: translate_order_by_expr(&columns[0])?,
             })
         }
         #[cfg(feature = "index")]
diff --git a/src/translate/query.rs b/src/translate/query.rs
index 64b503bc..e6a37c58 100644
--- a/src/translate/query.rs
+++ b/src/translate/query.rs
@@ -1,18 +1,20 @@
 use {
-    super::{expr::translate_expr, translate_idents, translate_object_name, TranslateError},
+    super::{
+        translate_expr, translate_idents, translate_object_name, translate_order_by_expr,
+        TranslateError,
+    },
     crate::{
         ast::{
-            Join, JoinConstraint, JoinOperator, OrderByExpr, Query, Select, SelectItem, SetExpr,
-            TableAlias, TableFactor, TableWithJoins, Values,
+            Join, JoinConstraint, JoinOperator, Query, Select, SelectItem, SetExpr, TableAlias,
+            TableFactor, TableWithJoins, Values,
         },
         result::Result,
     },
     sqlparser::ast::{
         Expr as SqlExpr, Join as SqlJoin, JoinConstraint as SqlJoinConstraint,
-        JoinOperator as SqlJoinOperator, OrderByExpr as SqlOrderByExpr, Query as SqlQuery,
-        Select as SqlSelect, SelectItem as SqlSelectItem, SetExpr as SqlSetExpr,
-        TableAlias as SqlTableAlias, TableFactor as SqlTableFactor,
-        TableWithJoins as SqlTableWithJoins,
+        JoinOperator as SqlJoinOperator, Query as SqlQuery, Select as SqlSelect,
+        SelectItem as SqlSelectItem, SetExpr as SqlSetExpr, TableAlias as SqlTableAlias,
+        TableFactor as SqlTableFactor, TableWithJoins as SqlTableWithJoins,
     },
 };
 
@@ -28,22 +30,7 @@ pub fn translate_query(sql_query: &SqlQuery) -> Result<Query> {
     let body = translate_set_expr(body)?;
     let order_by = order_by
         .iter()
-        .map(|order_by| {
-            let SqlOrderByExpr {
-                expr,
-                asc,
-                nulls_first,
-            } = order_by;
-
-            if matches!(nulls_first, Some(_)) {
-                return Err(TranslateError::OrderByNullsFirstOrLastNotSupported.into());
-            }
-
-            Ok(OrderByExpr {
-                expr: translate_expr(expr)?,
-                asc: asc.unwrap_or(true),
-            })
-        })
+        .map(translate_order_by_expr)
         .collect::<Result<_>>()?;
 
     let limit = limit.as_ref().map(translate_expr).transpose()?;


Test patch:
diff --git a/src/tests/index/mod.rs b/src/tests/index/mod.rs
index ce9da5ef..8c191d76 100644
--- a/src/tests/index/mod.rs
+++ b/src/tests/index/mod.rs
@@ -4,10 +4,12 @@ mod and;
 mod basic;
 mod expr;
 mod null;
+mod order_by;
 mod value;
 
 pub use and::and;
 pub use basic::basic;
 pub use expr::expr;
 pub use null::null;
+pub use order_by::order_by;
 pub use value::value;
diff --git a/src/tests/index/order_by.rs b/src/tests/index/order_by.rs
new file mode 100644
index 00000000..11ed4e8c
--- /dev/null
+++ b/src/tests/index/order_by.rs
@@ -0,0 +1,90 @@
+use crate::*;
+
+test_case!(order_by, async move {
+    run!(
+        r#"
+CREATE TABLE Test (
+    id INTEGER,
+    num INTEGER NULL,
+    name TEXT,
+)"#
+    );
+    run!(
+        r#"
+        INSERT INTO Test (id, num, name)
+        VALUES
+            (1, 2,    "Hello"),
+            (1, 9,    "Wild"),
+            (3, NULL, "World"),
+            (4, 7,    "Monday");
+    "#
+    );
+
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_name ON Test (name)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_id_num_asc ON Test (id + num ASC)"
+    );
+    test!(
+        Ok(Payload::CreateIndex),
+        "CREATE INDEX idx_num_desc ON Test (num DESC)"
+    );
+
+    use Value::*;
+
+    macro_rules! s {
+        ($v: literal) => {
+            Str($v.to_owned())
+        };
+    }
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(2)   s!("Hello");
+            I64(4)   I64(7)   s!("Monday");
+            I64(1)   I64(9)   s!("Wild");
+            I64(3)   Null     s!("World")
+        )),
+        idx!(idx_name),
+        "SELECT * FROM Test ORDER BY name"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(2)   s!("Hello");
+            I64(1)   I64(9)   s!("Wild");
+            I64(4)   I64(7)   s!("Monday");
+            I64(3)   Null     s!("World")
+        )),
+        idx!(idx_id_num_asc),
+        "SELECT * FROM Test ORDER BY id + num"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(2)   s!("Hello");
+            I64(1)   I64(9)   s!("Wild");
+            I64(4)   I64(7)   s!("Monday");
+            I64(3)   Null     s!("World")
+        )),
+        idx!(idx_id_num_asc, ASC),
+        "SELECT * FROM Test ORDER BY id + num ASC"
+    );
+
+    test_idx!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(3)   Null     s!("World");
+            I64(1)   I64(9)   s!("Wild");
+            I64(1)   I64(2)   s!("Hello")
+        )),
+        idx!(idx_num_desc, DESC),
+        "SELECT * FROM Test where id < 4 ORDER BY num DESC"
+    );
+});
diff --git a/src/tests/macros.rs b/src/tests/macros.rs
index f0b3ffc9..0f11becd 100644
--- a/src/tests/macros.rs
+++ b/src/tests/macros.rs
@@ -13,8 +13,32 @@ 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(),
+            asc: None,
+            cmp_expr: Some((
+                $op,
+                translate_expr(&parse_expr($sql_expr).unwrap()).unwrap(),
+            )),
+        }]
+    };
+    ($name: path) => {
+        vec![ast::IndexItem {
+            name: stringify!($name).to_owned(),
+            asc: None,
+            cmp_expr: None,
+        }]
+    };
+    ($name: path, ASC) => {
+        vec![ast::IndexItem {
+            name: stringify!($name).to_owned(),
+            asc: Some(true),
+            cmp_expr: None,
+        }]
+    };
+    ($name: path, DESC) => {
+        vec![ast::IndexItem {
+            name: stringify!($name).to_owned(),
+            asc: Some(false),
+            cmp_expr: None,
         }]
     };
 }
diff --git a/src/tests/mod.rs b/src/tests/mod.rs
index 95e91ca3..dfb95586 100644
--- a/src/tests/mod.rs
+++ b/src/tests/mod.rs
@@ -83,6 +83,7 @@ macro_rules! generate_tests {
                 glue!(index_null, index::null);
                 glue!(index_expr, index::expr);
                 glue!(index_value, index::value);
+                glue!(index_order_by, index::order_by);
             };
         }
 
diff --git a/src/tests/order_by.rs b/src/tests/order_by.rs
index d41d9f9f..4689ddab 100644
--- a/src/tests/order_by.rs
+++ b/src/tests/order_by.rs
@@ -162,7 +162,7 @@ test_case!(order_by, async move {
         Err(
             SelectError::OrderByOnNonIndexedExprNotSupported(vec![OrderByExpr {
                 expr: Expr::Identifier("id".to_owned()),
-                asc: false,
+                asc: Some(false),
             }])
             .into()
         ),