Repository: gluesql/gluesql
Pull request #243 (2021-06-17 11:16:25)

ORDER BY support
Implement ORDER BY support

This is supported by an optional feature `sorter`.
`sorter` will work well for most of use cases.
However, it is not a good idea to use this `sorter` for handling big data because `sorter` basically evaluates the entire data stream and load all to the memory.

Related to #78 
e.g.
```sql
SELECT id, num, name FROM Test ORDER BY id + num ASC;

SELECT * FROM Test WHERE id > 2 ORDER BY id DESC, num ASC;
```



Patch:
diff --git a/Cargo.toml b/Cargo.toml
index c2db9e98..df4ddc3d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -14,16 +14,20 @@ keywords = ["sql-database", "sql", "functional", "no-mut-in-the-middle", "webass
 all-features = true
 
 [features]
-default = ["sled-storage", "alter-table", "index"]
+default = ["sled-storage", "alter-table", "index", "sorter"]
 
-# ALTER TABLE is optional.
-# You can include whether ALTER TABLE support or not for your custom database implementation.
+# optional: ALTER TABLE
+# you can include whether ALTER TABLE support or not for your custom database implementation.
 alter-table = []
 
-# INDEX is also optional.
+# optional: INDEX
 index = []
 
-# Who wants to make a custom storage engine,
+# optional: ORDER BY for non-indexed expressions
+# disable this feature if you use GlueSQL for big data analysis.
+sorter = []
+
+# for someone who wants to make a custom storage engine,
 # default storage engine sled-storage is not required.
 sled-storage = ["sled", "bincode"]
 
diff --git a/src/ast/query.rs b/src/ast/query.rs
index 6ccf04c1..29b4bb83 100644
--- a/src/ast/query.rs
+++ b/src/ast/query.rs
@@ -6,6 +6,7 @@ use {
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub struct Query {
     pub body: SetExpr,
+    pub order_by: Vec<OrderByExpr>,
     pub limit: Option<Expr>,
     pub offset: Option<Expr>,
 }
@@ -83,5 +84,11 @@ pub enum JoinConstraint {
     None,
 }
 
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
+pub struct OrderByExpr {
+    pub expr: Expr,
+    pub asc: bool,
+}
+
 #[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub struct Values(pub Vec<Vec<Expr>>);
diff --git a/src/executor/execute.rs b/src/executor/execute.rs
index b53588a0..e1210f24 100644
--- a/src/executor/execute.rs
+++ b/src/executor/execute.rs
@@ -123,6 +123,7 @@ pub async fn execute<T: 'static + Debug, U: GStore<T> + GStoreMut<T>>(
                     SetExpr::Select(select_query) => {
                         let query = || Query {
                             body: SetExpr::Select(select_query.clone()),
+                            order_by: vec![],
                             limit: None,
                             offset: None,
                         };
diff --git a/src/executor/mod.rs b/src/executor/mod.rs
index 3bcfec15..f096d635 100644
--- a/src/executor/mod.rs
+++ b/src/executor/mod.rs
@@ -1,6 +1,5 @@
 mod aggregate;
 mod alter;
-mod blend;
 mod context;
 mod evaluate;
 mod execute;
@@ -9,12 +8,12 @@ mod filter;
 mod join;
 mod limit;
 mod select;
+mod sort;
 mod update;
 mod validate;
 
 pub use aggregate::{AggregateError, GroupKey};
 pub use alter::AlterError;
-pub use blend::BlendError;
 pub use evaluate::{evaluate_stateless, EvaluateError};
 pub use execute::{execute, ExecuteError, Payload};
 pub use fetch::FetchError;
diff --git a/src/executor/blend.rs b/src/executor/select/blend.rs
similarity index 69%
rename from src/executor/blend.rs
rename to src/executor/select/blend.rs
index d49c94cc..c03ece97 100644
--- a/src/executor/blend.rs
+++ b/src/executor/select/blend.rs
@@ -1,28 +1,21 @@
 use {
-    super::{
-        context::{AggregateContext, BlendContext, FilterContext},
-        evaluate::evaluate,
-    },
+    super::SelectError,
     crate::{
         ast::{Aggregate, SelectItem},
         data::{get_name, Row, Value},
+        executor::{
+            context::{BlendContext, FilterContext},
+            evaluate::evaluate,
+        },
         result::{Error, Result},
         store::GStore,
     },
     futures::stream::{self, StreamExt, TryStreamExt},
     im_rc::HashMap,
-    serde::Serialize,
     std::convert::TryInto,
     std::{fmt::Debug, rc::Rc},
-    thiserror::Error as ThisError,
 };
 
-#[derive(ThisError, Serialize, Debug, PartialEq)]
-pub enum BlendError {
-    #[error("table alias not found: {0}")]
-    TableAliasNotFound(String),
-}
-
 pub struct Blend<'a, T: 'static + Debug> {
     storage: &'a dyn GStore<T>,
     fields: &'a [SelectItem],
@@ -33,23 +26,14 @@ impl<'a, T: 'static + Debug> Blend<'a, T> {
         Self { storage, fields }
     }
 
-    pub async fn apply(&self, context: AggregateContext<'a>) -> Result<Row> {
-        let AggregateContext { aggregated, next } = context;
-        let values = self.blend(aggregated, next).await?;
-
-        Ok(Row(values))
-    }
-
-    async fn blend(
+    pub async fn apply(
         &self,
-        aggregated: Option<HashMap<&'a Aggregate, Value>>,
+        aggregated: Option<Rc<HashMap<&'a Aggregate, Value>>>,
         context: Rc<BlendContext<'a>>,
-    ) -> Result<Vec<Value>> {
+    ) -> Result<Row> {
         let filter_context = FilterContext::concat(None, Some(Rc::clone(&context)));
         let filter_context = Some(filter_context).map(Rc::new);
 
-        let aggregated = aggregated.map(Rc::new);
-
         let values = stream::iter(self.fields.iter())
             .map(Ok::<&'a SelectItem, Error>)
             .and_then(|item| {
@@ -65,10 +49,10 @@ impl<'a, T: 'static + Debug> Blend<'a, T> {
 
                             match context.get_alias_values(table_alias) {
                                 Some(values) => Ok(values),
-                                None => {
-                                    Err(BlendError::TableAliasNotFound(table_alias.to_string())
-                                        .into())
-                                }
+                                None => Err(SelectError::BlendTableAliasNotFound(
+                                    table_alias.to_string(),
+                                )
+                                .into()),
                             }
                         }
                         SelectItem::Expr { expr, .. } => {
@@ -84,6 +68,6 @@ impl<'a, T: 'static + Debug> Blend<'a, T> {
             .await?
             .concat();
 
-        Ok(values)
+        Ok(Row(values))
     }
 }
diff --git a/src/executor/select/error.rs b/src/executor/select/error.rs
new file mode 100644
index 00000000..0f6837e9
--- /dev/null
+++ b/src/executor/select/error.rs
@@ -0,0 +1,17 @@
+use {serde::Serialize, std::fmt::Debug, thiserror::Error as ThisError};
+
+#[derive(ThisError, Serialize, Debug, PartialEq)]
+pub enum SelectError {
+    #[error("table alias not found: {0}")]
+    TableAliasNotFound(String),
+
+    #[error("table alias for blend not found: {0}")]
+    BlendTableAliasNotFound(String),
+
+    #[cfg(not(feature = "sorter"))]
+    #[error("order by on non-indexed expression is not supported: {0:?}")]
+    OrderByOnNonIndexedExprNotSupported(Vec<crate::ast::OrderByExpr>),
+
+    #[error("unreachable!")]
+    Unreachable,
+}
diff --git a/src/executor/select.rs b/src/executor/select/mod.rs
similarity index 85%
rename from src/executor/select.rs
rename to src/executor/select/mod.rs
index c9625022..e92fc754 100644
--- a/src/executor/select.rs
+++ b/src/executor/select/mod.rs
@@ -1,15 +1,21 @@
+mod blend;
+mod error;
+
+pub use error::SelectError;
+
 use {
+    self::blend::Blend,
     super::{
         aggregate::Aggregator,
-        blend::Blend,
         context::{BlendContext, FilterContext},
         fetch::fetch_columns,
         filter::Filter,
         join::Join,
         limit::Limit,
+        sort::Sort,
     },
     crate::{
-        ast::{Query, SelectItem, SetExpr, TableWithJoins},
+        ast::{Query, Select, SelectItem, SetExpr, TableWithJoins},
         data::{get_name, Row, Table},
         result::{Error, Result},
         store::GStore,
@@ -17,9 +23,7 @@ use {
     boolinator::Boolinator,
     futures::stream::{self, Stream, StreamExt, TryStream, TryStreamExt},
     iter_enum::Iterator,
-    serde::Serialize,
     std::{fmt::Debug, iter::once, rc::Rc},
-    thiserror::Error as ThisError,
 };
 
 #[cfg(feature = "index")]
@@ -29,15 +33,6 @@ use {
     std::convert::TryInto,
 };
 
-#[derive(ThisError, Serialize, Debug, PartialEq)]
-pub enum SelectError {
-    #[error("table alias not found: {0}")]
-    TableAliasNotFound(String),
-
-    #[error("unreachable!")]
-    Unreachable,
-}
-
 async fn fetch_blended<'a, T: 'static + Debug>(
     storage: &dyn GStore<T>,
     table: Table<'a>,
@@ -155,21 +150,24 @@ pub async fn select_with_labels<'a, T: 'static + Debug>(
     filter_context: Option<Rc<FilterContext<'a>>>,
     with_labels: bool,
 ) -> Result<(Vec<String>, impl TryStream<Ok = Row, Error = Error> + 'a)> {
-    macro_rules! err {
-        ($err: expr) => {{
-            return Err($err.into());
-        }};
+    #[cfg(not(feature = "sorter"))]
+    if !query.order_by.is_empty() {
+        let order_by = query.order_by.clone();
+
+        return Err(SelectError::OrderByOnNonIndexedExprNotSupported(order_by).into());
     }
 
-    let (table_with_joins, where_clause, projection, group_by, having) = match &query.body {
-        SetExpr::Select(statement) => (
-            &statement.from,
-            statement.selection.as_ref(),
-            statement.projection.as_ref(),
-            &statement.group_by,
-            statement.having.as_ref(),
-        ),
-        _ => err!(SelectError::Unreachable),
+    let Select {
+        from: table_with_joins,
+        selection: where_clause,
+        projection,
+        group_by,
+        having,
+    } = match &query.body {
+        SetExpr::Select(statement) => statement.as_ref(),
+        _ => {
+            return Err(SelectError::Unreachable.into());
+        }
     };
 
     let TableWithJoins { relation, joins } = &table_with_joins;
@@ -217,12 +215,18 @@ pub async fn select_with_labels<'a, T: 'static + Debug>(
         storage,
         projection,
         group_by,
-        having,
+        having.as_ref(),
         filter_context.as_ref().map(Rc::clone),
     );
     let blend = Rc::new(Blend::new(storage, projection));
-    let filter = Rc::new(Filter::new(storage, where_clause, filter_context, None));
-    let limit = Rc::new(Limit::new(query.limit.as_ref(), query.offset.as_ref())?);
+    let filter = Rc::new(Filter::new(
+        storage,
+        where_clause.as_ref(),
+        filter_context.as_ref().map(Rc::clone),
+        None,
+    ));
+    let limit = Limit::new(query.limit.as_ref(), query.offset.as_ref())?;
+    let sort = Sort::new(storage, filter_context, &query.order_by);
 
     let rows = fetch_blended(storage, table, columns)
         .await?
@@ -245,15 +249,14 @@ pub async fn select_with_labels<'a, T: 'static + Debug>(
         });
 
     let rows = limit.apply(rows);
-
-    let rows = aggregate
+    let rows = aggregate.apply(rows).await?;
+    let rows = sort
         .apply(rows)
         .await?
-        .into_stream()
-        .and_then(move |aggregate_context| {
+        .and_then(move |(aggregated, context)| {
             let blend = Rc::clone(&blend);
 
-            async move { blend.apply(aggregate_context).await }
+            async move { blend.apply(aggregated, context).await }
         });
 
     Ok((labels, rows))
diff --git a/src/executor/sort.rs b/src/executor/sort.rs
new file mode 100644
index 00000000..4a0722c9
--- /dev/null
+++ b/src/executor/sort.rs
@@ -0,0 +1,130 @@
+use {
+    super::{
+        context::{AggregateContext, BlendContext, FilterContext},
+        evaluate::evaluate,
+    },
+    crate::{
+        ast::{Aggregate, OrderByExpr},
+        data::Value,
+        result::Result,
+        store::GStore,
+        utils::Vector,
+    },
+    futures::stream::{self, Stream, StreamExt, TryStreamExt},
+    im_rc::HashMap,
+    std::{cmp::Ordering, convert::TryInto, fmt::Debug, pin::Pin, rc::Rc},
+};
+
+pub struct Sort<'a, T: 'static + Debug> {
+    storage: &'a dyn GStore<T>,
+    context: Option<Rc<FilterContext<'a>>>,
+    order_by: &'a [OrderByExpr],
+}
+
+type Item<'a> = Result<(
+    Option<Rc<HashMap<&'a Aggregate, Value>>>,
+    Rc<BlendContext<'a>>,
+)>;
+
+impl<'a, T: 'static + Debug> Sort<'a, T> {
+    pub fn new(
+        storage: &'a dyn GStore<T>,
+        context: Option<Rc<FilterContext<'a>>>,
+        order_by: &'a [OrderByExpr],
+    ) -> Self {
+        Self {
+            storage,
+            context,
+            order_by,
+        }
+    }
+
+    pub async fn apply(
+        &self,
+        rows: impl Stream<Item = Result<AggregateContext<'a>>> + 'a,
+    ) -> Result<Pin<Box<dyn Stream<Item = Item<'a>> + 'a>>> {
+        if self.order_by.is_empty() {
+            let rows = rows.map_ok(|aggregate_context| {
+                let AggregateContext { aggregated, next } = aggregate_context;
+
+                (aggregated.map(Rc::new), next)
+            });
+
+            return Ok(Box::pin(rows));
+        }
+
+        let rows = rows
+            .and_then(move |AggregateContext { aggregated, next }| async move {
+                let blend_context = Rc::clone(&next);
+                let filter_context = Rc::new(FilterContext::concat(
+                    self.context.as_ref().map(Rc::clone),
+                    Some(Rc::clone(&next)),
+                ));
+                let aggregated = aggregated.map(Rc::new);
+
+                let values = stream::iter(self.order_by.iter())
+                    .then(|OrderByExpr { expr, asc }| {
+                        let context = Some(Rc::clone(&filter_context));
+                        let aggregated = aggregated.as_ref().map(Rc::clone);
+
+                        async move {
+                            evaluate(self.storage, context, aggregated, expr)
+                                .await?
+                                .try_into()
+                                .map(|value| (value, *asc))
+                        }
+                    })
+                    .try_collect::<Vec<_>>()
+                    .await?;
+
+                Ok((values, aggregated, blend_context))
+            })
+            .try_collect::<Vec<_>>()
+            .await
+            .map(Vector::from)?
+            .sort_unstable_by(|(values_a, _, _), (values_b, _, _)| {
+                let pairs = values_a
+                    .iter()
+                    .map(|(a, _)| a)
+                    .zip(values_b.iter())
+                    .map(|(a, (b, asc))| (a, b, asc));
+
+                for (value_a, value_b, asc) in pairs {
+                    let apply_asc = |ord: Ordering| if *asc { ord } else { ord.reverse() };
+
+                    match (value_a, value_b) {
+                        (Value::Null, Value::Null) => {}
+                        (Value::Null, _) => {
+                            return apply_asc(Ordering::Greater);
+                        }
+                        (_, Value::Null) => {
+                            return apply_asc(Ordering::Less);
+                        }
+                        _ => {}
+                    };
+
+                    match value_a.partial_cmp(value_b) {
+                        Some(ord) if ord != Ordering::Equal => {
+                            return apply_asc(ord);
+                        }
+                        None => {
+                            let a = String::from(value_a);
+                            let b = String::from(value_b);
+                            let ord = a.cmp(&b);
+
+                            if ord != Ordering::Equal {
+                                return apply_asc(ord);
+                            }
+                        }
+                        _ => {}
+                    }
+                }
+
+                Ordering::Equal
+            })
+            .into_iter()
+            .map(|(_, aggregated, blend_context)| Ok((aggregated, blend_context)));
+
+        Ok(Box::pin(stream::iter(rows)))
+    }
+}
diff --git a/src/plan.rs b/src/plan.rs
index cd6dbe83..62a539d0 100644
--- a/src/plan.rs
+++ b/src/plan.rs
@@ -28,6 +28,7 @@ pub async fn plan<T: 'static + Debug>(
 async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) -> Result<Query> {
     let Query {
         body,
+        order_by,
         limit,
         offset,
     } = query;
@@ -37,6 +38,7 @@ async fn plan_query<T: 'static + Debug>(storage: &dyn Store<T>, query: Query) ->
         SetExpr::Values(_) => {
             return Ok(Query {
                 body,
+                order_by,
                 limit,
                 offset,
             });
@@ -46,6 +48,7 @@ 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,
     };
diff --git a/src/result.rs b/src/result.rs
index e6d14fa2..50d6d233 100644
--- a/src/result.rs
+++ b/src/result.rs
@@ -2,8 +2,8 @@ use {
     crate::{
         data::{IntervalError, LiteralError, RowError, TableError, ValueError},
         executor::{
-            AggregateError, AlterError, BlendError, EvaluateError, ExecuteError, FetchError,
-            SelectError, UpdateError, ValidateError,
+            AggregateError, AlterError, EvaluateError, ExecuteError, FetchError, SelectError,
+            UpdateError, ValidateError,
         },
         translate::TranslateError,
     },
@@ -48,8 +48,6 @@ pub enum Error {
     #[error(transparent)]
     Select(#[from] SelectError),
     #[error(transparent)]
-    Blend(#[from] BlendError),
-    #[error(transparent)]
     Aggregate(#[from] AggregateError),
     #[error(transparent)]
     Update(#[from] UpdateError),
@@ -86,7 +84,6 @@ impl PartialEq for Error {
             (Fetch(e), Fetch(e2)) => e == e2,
             (Evaluate(e), Evaluate(e2)) => e == e2,
             (Select(e), Select(e2)) => e == e2,
-            (Blend(e), Blend(e2)) => e == e2,
             (Aggregate(e), Aggregate(e2)) => e == e2,
             (Update(e), Update(e2)) => e == e2,
             (Row(e), Row(e2)) => e == e2,
diff --git a/src/translate/error.rs b/src/translate/error.rs
index 4f0560ba..7b2906e5 100644
--- a/src/translate/error.rs
+++ b/src/translate/error.rs
@@ -24,6 +24,9 @@ pub enum TranslateError {
     #[error("named function arg is not supported")]
     NamedFunctionArgNotSupported,
 
+    #[error("order by - NULLS (FIRST | LAST) is not supported")]
+    OrderByNullsFirstOrLastNotSupported,
+
     #[error("unsupported function: {0}")]
     UnsupportedFunction(String),
 
diff --git a/src/translate/query.rs b/src/translate/query.rs
index 24907a5a..64b503bc 100644
--- a/src/translate/query.rs
+++ b/src/translate/query.rs
@@ -2,28 +2,50 @@ use {
     super::{expr::translate_expr, translate_idents, translate_object_name, TranslateError},
     crate::{
         ast::{
-            Join, JoinConstraint, JoinOperator, Query, Select, SelectItem, SetExpr, TableAlias,
-            TableFactor, TableWithJoins, Values,
+            Join, JoinConstraint, JoinOperator, OrderByExpr, Query, Select, SelectItem, SetExpr,
+            TableAlias, TableFactor, TableWithJoins, Values,
         },
         result::Result,
     },
     sqlparser::ast::{
         Expr as SqlExpr, Join as SqlJoin, JoinConstraint as SqlJoinConstraint,
-        JoinOperator as SqlJoinOperator, Query as SqlQuery, Select as SqlSelect,
-        SelectItem as SqlSelectItem, SetExpr as SqlSetExpr, TableAlias as SqlTableAlias,
-        TableFactor as SqlTableFactor, TableWithJoins as SqlTableWithJoins,
+        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,
     },
 };
 
 pub fn translate_query(sql_query: &SqlQuery) -> Result<Query> {
     let SqlQuery {
         body,
+        order_by,
         limit,
         offset,
         ..
     } = sql_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),
+            })
+        })
+        .collect::<Result<_>>()?;
+
     let limit = limit.as_ref().map(translate_expr).transpose()?;
     let offset = offset
         .as_ref()
@@ -32,6 +54,7 @@ pub fn translate_query(sql_query: &SqlQuery) -> Result<Query> {
 
     Ok(Query {
         body,
+        order_by,
         limit,
         offset,
     })
diff --git a/src/utils/vector.rs b/src/utils/vector.rs
index 71237f97..976874dd 100644
--- a/src/utils/vector.rs
+++ b/src/utils/vector.rs
@@ -28,6 +28,15 @@ impl<T> Vector<T> {
         self
     }
 
+    pub fn sort_unstable_by<F>(mut self, compare: F) -> Self
+    where
+        F: FnMut(&T, &T) -> std::cmp::Ordering,
+    {
+        self.0.sort_by(compare);
+
+        self
+    }
+
     pub fn get(&self, i: usize) -> Option<&T> {
         self.0.get(i)
     }


Test patch:
diff --git a/src/tests/blend.rs b/src/tests/blend.rs
index af295a7f..c69bd422 100644
--- a/src/tests/blend.rs
+++ b/src/tests/blend.rs
@@ -139,7 +139,7 @@ test_case!(blend, async move {
             "SELECT Whatever.* FROM BlendUser",
         ),
         (
-            BlendError::TableAliasNotFound("Whatever".to_owned()).into(),
+            SelectError::BlendTableAliasNotFound("Whatever".to_owned()).into(),
             "SELECT * FROM BlendUser WHERE id IN (SELECT Whatever.* FROM BlendUser)",
         ),
         (
diff --git a/src/tests/mod.rs b/src/tests/mod.rs
index d1f26b13..95e91ca3 100644
--- a/src/tests/mod.rs
+++ b/src/tests/mod.rs
@@ -15,6 +15,7 @@ pub mod limit;
 pub mod migrate;
 pub mod nested_select;
 pub mod nullable;
+pub mod order_by;
 pub mod ordering;
 pub mod synthesize;
 pub mod validate;
@@ -64,6 +65,7 @@ macro_rules! generate_tests {
         glue!(nullable, nullable::nullable);
         glue!(nullable_text, nullable::nullable_text);
         glue!(ordering, ordering::ordering);
+        glue!(order_by, order_by::order_by);
         glue!(sql_types, data_type::sql_types::sql_types);
         glue!(date, data_type::date::date);
         glue!(timestamp, data_type::timestamp::timestamp);
diff --git a/src/tests/order_by.rs b/src/tests/order_by.rs
new file mode 100644
index 00000000..d41d9f9f
--- /dev/null
+++ b/src/tests/order_by.rs
@@ -0,0 +1,176 @@
+use crate::*;
+
+#[cfg(feature = "sorter")]
+test_case!(order_by, async move {
+    run!(
+        r#"
+CREATE TABLE Test (
+    id INTEGER,
+    num INTEGER,
+    name TEXT NULL,
+    rate FLOAT NULL
+)"#
+    );
+    run!(
+        r#"
+        INSERT INTO Test (id, num, name, rate)
+        VALUES
+            (1, 2, "Hello",    3.0),
+            (1, 9, NULL,       NULL),
+            (3, 4, "World",    1.0),
+            (4, 7, "Thursday", NULL);
+    "#
+    );
+
+    use Value::*;
+
+    test!(
+        Ok(select!(
+            id  | num
+            I64 | I64;
+            1     2;
+            1     9;
+            3     4;
+            4     7
+        )),
+        "SELECT id, num FROM Test"
+    );
+
+    macro_rules! s {
+        ($v: literal) => {
+            Str($v.to_owned())
+        };
+    }
+
+    test!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(2)   s!("Hello");
+            I64(3)   I64(4)   s!("World");
+            I64(1)   I64(9)   Null;
+            I64(4)   I64(7)   s!("Thursday")
+        )),
+        "SELECT id, num, name FROM Test ORDER BY id + num ASC"
+    );
+
+    test!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(9)   Null;
+            I64(4)   I64(7)   s!("Thursday");
+            I64(3)   I64(4)   s!("World");
+            I64(1)   I64(2)   s!("Hello")
+        )),
+        "SELECT id, num, name FROM Test ORDER BY num DESC"
+    );
+
+    test!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(2)   s!("Hello");
+            I64(4)   I64(7)   s!("Thursday");
+            I64(3)   I64(4)   s!("World");
+            I64(1)   I64(9)   Null
+        )),
+        "SELECT id, num, name FROM Test ORDER BY name"
+    );
+
+    test!(
+        Ok(select_with_null!(
+            id     | num    | name;
+            I64(1)   I64(9)   Null;
+            I64(3)   I64(4)   s!("World");
+            I64(4)   I64(7)   s!("Thursday");
+            I64(1)   I64(2)   s!("Hello")
+        )),
+        "SELECT id, num, name FROM Test ORDER BY name DESC"
+    );
+
+    test!(
+        Ok(select_with_null!(
+            id     | num    | name           | rate;
+            I64(4)   I64(7)   s!("Thursday")   Null;
+            I64(1)   I64(9)   Null             Null;
+            I64(1)   I64(2)   s!("Hello")      F64(3.0);
+            I64(3)   I64(4)   s!("World")      F64(1.0)
+        )),
+        "SELECT id, num, name, rate FROM Test ORDER BY rate DESC, id DESC"
+    );
+
+    test!(
+        Ok(select!(
+            id  | num
+            I64 | I64;
+            1     9;
+            1     2;
+            3     4;
+            4     7
+        )),
+        "SELECT id, num FROM Test ORDER BY id ASC, num DESC"
+    );
+
+    test!(
+        Ok(select!(
+            id  | num
+            I64 | I64;
+            1     9;
+            1     2;
+            3     4;
+            4     7
+        )),
+        "
+        SELECT id, num FROM Test
+        ORDER BY
+            (SELECT id FROM Test t2 WHERE Test.id = t2.id LIMIT 1) ASC,
+            num DESC
+        "
+    );
+
+    test!(
+        Ok(select!(
+            id  | num
+            I64 | I64;
+            1     9;
+            1     2;
+            3     4;
+            4     7
+        )),
+        "
+        SELECT id, num FROM Test
+        ORDER BY
+            (SELECT t2.id FROM Test t2
+                WHERE Test.id = t2.id
+                ORDER BY (Test.id + t2.id) LIMIT 1
+            ) ASC,
+            num DESC;
+        "
+    );
+
+    test!(
+        Err(TranslateError::OrderByNullsFirstOrLastNotSupported.into()),
+        "SELECT * FROM Test ORDER BY id NULLS FIRST"
+    );
+});
+
+#[cfg(not(feature = "sorter"))]
+test_case!(order_by, async move {
+    use ast::{Expr, OrderByExpr};
+
+    run!("CREATE TABLE Test (id INTEGER);");
+
+    test!(
+        Err(
+            SelectError::OrderByOnNonIndexedExprNotSupported(vec![OrderByExpr {
+                expr: Expr::Identifier("id".to_owned()),
+                asc: false,
+            }])
+            .into()
+        ),
+        "SELECT * FROM Test ORDER BY id DESC"
+    );
+
+    test!(
+        Err(TranslateError::OrderByNullsFirstOrLastNotSupported.into()),
+        "SELECT * FROM Test ORDER BY id NULLS LAST"
+    );
+});