Merge lp:~thisfred/u1db/home-on-the-range into lp:u1db

[Eric Casteleijn]

Implemented range queries on all backends

Implemented range queries on all backends

[lp:~thisfred/u1db/home-on-the-range]

328. By Eric Casteleijn on 2012-06-04

removed copy pasta

[John A Meinel (jameinel)]

Quick thing. Your doc is "n_start_values" but the variable is "n_values"

John
=:->

[John A Meinel (jameinel)]

You also didn't document the public API in u1db/__init__.py. and the
inmemory one could probably use a couple comments about efficiency. (You
sort the items, but don't bisect to find the start, nor stop early. It
would be significantly more efficient to filter then sort, etc.)

Otherwise seems good to me.
John
=:->
On Jun 4, 2012 8:29 PM, "Eric Casteleijn" <email address hidden>
wrote:

> Eric Casteleijn has proposed merging lp:~thisfred/u1db/home-on-the-range
> into lp:u1db with lp:~thisfred/u1db/c-api-improvements as a prerequisite.
>
> Requested reviews:
> Ubuntu One hackers (ubuntuone-hackers)
> Related bugs:
> Bug #999585 in U1DB: "support range queries"
> https://bugs.launchpad.net/u1db/+bug/999585
>
> For more details, see:
> https://code.launchpad.net/~thisfred/u1db/home-on-the-range/+merge/108606
>
> Implemented range queries on all backends
> --
> https://code.launchpad.net/~thisfred/u1db/home-on-the-range/+merge/108606
> Your team Ubuntu One hackers is requested to review the proposed merge of
> lp:~thisfred/u1db/home-on-the-range into lp:u1db.
>
> === modified file 'include/u1db/u1db.h'
> --- include/u1db/u1db.h 2012-06-04 18:28:18 +0000
> +++ include/u1db/u1db.h 2012-06-04 18:28:18 +0000
> @@ -337,6 +337,20 @@
> u1db_doc_callback cb, int n_values, ...);
>
>
> +
> +/**
> + * Get documents with key values in the specified range
> + *
> + * @param query A u1query object, as created by u1db_query_init.
> + * @param context Will be returned via the document callback
> + * @param n_start_values The number of values.
> + * @param start_values An array of values. If NULL, assume an open ended
> query.
> + * @param end_values An array of values. If NULL, assume an open ended
> query.
> + */
> +int u1db_get_range_from_index(u1database *db, u1query *query,
> + void *context, u1db_doc_callback cb,
> + int n_values, const char **start_values,
> + const char **end_values);
> /**
> * Get keys under which documents are indexed.
> *
>
> === modified file 'include/u1db/u1db_internal.h'
> --- include/u1db/u1db_internal.h 2012-06-04 18:28:18 +0000
> +++ include/u1db/u1db_internal.h 2012-06-04 18:28:18 +0000
> @@ -331,11 +331,10 @@
> /**
> * Format a given query.
> *
> - * @param n_fields The number of fields being passed in, (the number of
> args
> - * in argp)
> + * @param n_fields The number of fields being passed in. (The number of
> values
> + * in values)
> * @param values Array of values being passed.
> * @param buf (OUT) The character array. This will be dynamically
> allocated,
> - * print key_values
> * and callers must free() it.
> * @param wildcard (IN/OUT) Any array indicating a wildcard type for this
> * argument. A 0 indicates this is an exact match, a 1
> @@ -348,6 +347,22 @@
>
>
> /**
> + * Format a given range query.
> + *
> + * @param n_fields The number of fields being passed in. (The number of
> values
> + * in start_values and end_values)
> + * @param start_values Array of values used to define the lower bound of
> the
> + * query.
> + * @param end_value...

[lp:~thisfred/u1db/home-on-the-range]

329. By Eric Casteleijn on 2012-06-04

fixed documentation

[Eric Casteleijn (thisfred)]

On 06/04/2012 04:28 PM, John A Meinel wrote:
> Quick thing. Your doc is "n_start_values" but the variable is "n_values"

Thanks, fix pushed (I started off with both n_start_values and
n_end_values, before realizing that was unnecessary.)

[lp:~thisfred/u1db/home-on-the-range]

330. By Eric Casteleijn on 2012-06-04

added get_range_from_index to API definition, fixed some documentation lag

331. By Eric Casteleijn on 2012-06-04

added docstring to inmemory implementation stating inefficiency.

[Eric Casteleijn (thisfred)]

On 06/04/2012 04:38 PM, John A Meinel wrote:
> You also didn't document the public API in u1db/__init__.py. and the
> inmemory one could probably use a couple comments about efficiency. (You
> sort the items, but don't bisect to find the start, nor stop early. It
> would be significantly more efficient to filter then sort, etc.)

Both fixed (that is, I commented, rather than made the inmem
implementation faster, aside from breaking from the loop early, since to
make it fast, we'd need something other than a dictionary anyway, now
that we have ordering.)

--
eric casteleijn
https://launchpad.net/~thisfred

[John A Meinel (jameinel)]

Well, you could easily get O(N + M log M) ~ O(N) rather than O(N log N + N) ~ O(N log N) (where N is all keys and M is just the subset). But meh, we can do it if it matters later.

review: Approve

[lp:~thisfred/u1db/home-on-the-range]

332. By Eric Casteleijn on 2012-06-12

merged trunk and fixed conflicts

=== modified file 'include/u1db/u1db.h'
--- include/u1db/u1db.h	2012-06-12 12:35:05 +0000
+++ include/u1db/u1db.h	2012-06-12 14:34:24 +0000
@@ -271,7 +271,6 @@
 int u1db_create_index_list(u1database *db, const char *index_name,
                            int n_expressions, const char **expressions);
 
-
 /**
  * Delete a defined index.
  */
@@ -325,7 +324,6 @@
                              u1db_doc_callback cb, int n_values,
                              const char **values);
 
-
 /**
  * Get documents which match a given index.
  *
@@ -337,7 +335,19 @@
 int u1db_get_from_index(u1database *db, u1query *query, void *context,
                         u1db_doc_callback cb, int n_values, ...);
 
-
+/**
+ * Get documents with key values in the specified range
+ *
+ * @param query A u1query object, as created by u1db_query_init.
+ * @param context Will be returned via the document callback
+ * @param n_values The number of values.
+ * @param start_values An array of values. If NULL, assume an open ended query.
+ * @param end_values An array of values. If NULL, assume an open ended query.
+ */
+int u1db_get_range_from_index(u1database *db, u1query *query,
+                              void *context, u1db_doc_callback cb,
+                              int n_values, const char **start_values,
+                              const char **end_values);
 /**
  * Get keys under which documents are indexed.
  *

=== modified file 'include/u1db/u1db_internal.h'
--- include/u1db/u1db_internal.h	2012-06-12 12:35:05 +0000
+++ include/u1db/u1db_internal.h	2012-06-12 14:34:24 +0000
@@ -337,11 +337,10 @@
 /**
  * Format a given query.
  *
- * @param n_fields The number of fields being passed in, (the number of args
- *     in argp)
+ * @param n_fields The number of fields being passed in. (The number of values
+ *     in values)
  * @param values Array of values being passed.
  * @param buf (OUT) The character array. This will be dynamically allocated,
- *      print key_values
  *     and callers must free() it.
  * @param wildcard (IN/OUT) Any array indicating a wildcard type for this
  *     argument. A 0 indicates this is an exact match, a 1
@@ -352,6 +351,20 @@
 int u1db__format_query(int n_fields, const char **values, char **buf,
                        int *wildcard);
 
+/**
+ * Format a given range query.
+ *
+ * @param n_fields The number of fields being passed in. (The number of values
+ *     in start_values and end_values)
+ * @param start_values Array of values used to define the lower bound of the
+ *     query.
+ * @param end_values Array of values used to define the upper bound of the
+ *     query.
+ * @param buf (OUT) The character array. This will be dynamically allocated,
+ *     and callers must free() it.
+ */
+int u1db__format_range_query(int n_fields, const char **start_values,
+                             const char **end_values, char **buf);
 
 /**
  * Given this document content, update the indexed fields in the db.

=== modified file 'src/u1db_query.c'
--- src/u1db_query.c	2012-06-05 23:00:23 +0000
+++ src/u1db_query.c	2012-06-12 14:34:24 +0000
@@ -604,6 +604,71 @@
 
 
 int
+u1db_get_range_from_index(u1database *db, u1query *query,
+                          void *context, u1db_doc_callback cb,
+                          int n_values, const char **start_values,
+                          const char **end_values)
+{
+    int i, bind_arg, status = U1DB_OK;
+    char *query_str = NULL;
+    sqlite3_stmt *statement = NULL;
+    char *doc_id = NULL;
+
+    if (db == NULL || query == NULL || cb == NULL || n_values < 0) {
+        return U1DB_INVALID_PARAMETER;
+    }
+    if (n_values != query->num_fields) {
+        return U1DB_INVALID_VALUE_FOR_INDEX;
+    }
+    status = u1db__format_range_query(
+        query->num_fields, start_values, end_values, &query_str);
+    if (status != U1DB_OK) { goto finish; }
+    status = sqlite3_prepare_v2(db->sql_handle, query_str, -1,
+                                &statement, NULL);
+    if (status != SQLITE_OK) { goto finish; }
+    // Bind all of the 'field_name' parameters. sqlite_bind starts at 1
+    bind_arg = 1;
+    for (i = 0; i < query->num_fields; ++i) {
+        status = sqlite3_bind_text(
+            statement, bind_arg, query->fields[i], -1, SQLITE_TRANSIENT);
+        if (status != SQLITE_OK) { goto finish; }
+        bind_arg++;
+        if (start_values != NULL) {
+            status = sqlite3_bind_text(
+                statement, bind_arg, start_values[i], -1, SQLITE_TRANSIENT);
+            if (status != SQLITE_OK) { goto finish; }
+            bind_arg++;
+        }
+        if (end_values != NULL) {
+            status = sqlite3_bind_text(
+                statement, bind_arg, end_values[i], -1, SQLITE_TRANSIENT);
+            if (status != SQLITE_OK) { goto finish; }
+            bind_arg++;
+        }
+    }
+    status = sqlite3_step(statement);
+    while (status == SQLITE_ROW) {
+        doc_id = (char*)sqlite3_column_text(statement, 0);
+        // We use u1db_get_docs so we can pass check_for_conflicts=0, which is
+        // currently expected by the test suite.
+        status = u1db_get_docs(
+            db, 1, (const char**)&doc_id, 0, 0, context, cb);
+        if (status != U1DB_OK) { goto finish; }
+        status = sqlite3_step(statement);
+    }
+    if (status == SQLITE_DONE) {
+        status = U1DB_OK;
+    }
+finish:
+    sqlite3_finalize(statement);
+    if (query_str != NULL) {
+        free(query_str);
+    }
+    return status;
+}
+
+
+int
 u1db_get_from_index(u1database *db, u1query *query, void *context,
                     u1db_doc_callback cb, int n_values, ...)
 {
@@ -704,7 +769,7 @@
 
 int
 u1db__format_query(int n_fields, const char **values, char **buf,
-                    int *wildcard)
+                   int *wildcard)
 {
     int status = U1DB_OK;
     int buf_size, i;
@@ -779,6 +844,70 @@
     return status;
 }
 
+int
+u1db__format_range_query(int n_fields, const char **start_values,
+                         const char **end_values, char **buf)
+{
+    int status = U1DB_OK;
+    int buf_size, i;
+    char *cur = NULL;
+    const char *val = NULL;
+
+    if (n_fields < 1) {
+        return U1DB_INVALID_PARAMETER;
+    }
+    // 81 for 1 doc, 166 for 2, 251 for 3
+    buf_size = (1 + n_fields) * 100;
+    // The first field is treated specially
+    cur = (char*)calloc(buf_size, 1);
+    if (cur == NULL) {
+        return U1DB_NOMEM;
+    }
+    *buf = cur;
+    add_to_buf(&cur, &buf_size, "SELECT d0.doc_id FROM document_fields d0");
+    for (i = 1; i < n_fields; ++i) {
+        add_to_buf(&cur, &buf_size, ", document_fields d%d", i);
+    }
+    add_to_buf(&cur, &buf_size, " WHERE d0.field_name = ?");
+    for (i = 0; i < n_fields; ++i) {
+        if (i != 0) {
+            add_to_buf(&cur, &buf_size,
+                " AND d0.doc_id = d%d.doc_id"
+                " AND d%d.field_name = ?",
+                i, i);
+        }
+        if (start_values != NULL) {
+            val = start_values[i];
+            if (val == NULL) {
+                status = U1DB_INVALID_VALUE_FOR_INDEX;
+                goto finish;
+            }
+            add_to_buf(&cur, &buf_size, " AND d%d.value >= ?", i);
+        }
+        if (end_values != NULL) {
+            val = end_values[i];
+            if (val == NULL) {
+                status = U1DB_INVALID_VALUE_FOR_INDEX;
+                goto finish;
+            }
+            add_to_buf(&cur, &buf_size, " AND d%d.value <= ?", i);
+        }
+
+    }
+    add_to_buf(&cur, &buf_size, " ORDER BY ");
+    for (i = 0; i < n_fields; ++i) {
+        if (i != 0) {
+            add_to_buf(&cur, &buf_size, ", ");
+        }
+        add_to_buf(&cur, &buf_size, "d%d.value", i);
+    }
+finish:
+    if (status != U1DB_OK && *buf != NULL) {
+        free(*buf);
+        *buf = NULL;
+    }
+    return status;
+}
 
 struct sqlcb_to_field_cb {
     void *user_context;

=== modified file 'u1db/__init__.py'
--- u1db/__init__.py	2012-06-08 07:39:35 +0000
+++ u1db/__init__.py	2012-06-12 14:34:24 +0000
@@ -180,22 +180,41 @@
     def get_from_index(self, index_name, *key_values):
         """Return documents that match the keys supplied.
 
-        You must supply exactly the same number of values as has been defined
+        You must supply exactly the same number of values as have been defined
         in the index. It is possible to do a prefix match by using '*' to
         indicate a wildcard match. You can only supply '*' to trailing entries,
-        (eg [('val', '*', '*')] is allowed, but [('*', 'val', 'val')] is not.)
+        (eg 'val', '*', '*' is allowed, but '*', 'val', 'val' is not.)
         It is also possible to append a '*' to the last supplied value (eg
-        [('val*', '*', '*')] or [('val', 'val*', '*')], but not [('val*',
-        'val', '*')])
+        'val*', '*', '*' or 'val', 'val*', '*', but not 'val*', 'val', '*')
 
         :return: List of [Document]
         :param index_name: The index to query
-        :param key_values: tuples of values to match. eg, if you have
+        :param key_values: values to match. eg, if you have
             an index with 3 fields then you would have:
-            (x-val1, x-val2, x-val3), (y-val1, y-val2, y-val3), ...
+            get_from_index(index_name, val1, val2, val3)
         """
         raise NotImplementedError(self.get_from_index)
 
+    def get_range_from_index(self, index_name, start_value, end_value):
+        """Return documents that fall within the specified range.
+
+        For both start_value and end_value, one must supply exactly the same
+        number of values as have been defined in the index, or pass None. In
+        case of a single column index, a string is accepted as an alternative
+        for a tuple with a single value. No wildcards of any kind are
+        supported.
+
+        :return: List of [Document]
+        :param index_name: The index to query
+        :param start_values: tuples of values that define the upperbound of the
+            range. eg, if you have an index with 3 fields then you would have:
+            (x-val1, x-val2, x-val3), (y-val1, y-val2, y-val3), ...
+        :param end_values: tuples of values that define the upperbound of the
+            range. eg, if you have an index with 3 fields then you would have:
+            (x-val1, x-val2, x-val3), (y-val1, y-val2, y-val3), ...
+        """
+        raise NotImplementedError(self.get_range_from_index)
+
     def get_index_keys(self, index_name):
         """Return all keys under which documents are indexed in this index.
 

=== modified file 'u1db/backends/inmemory.py'
--- u1db/backends/inmemory.py	2012-05-31 18:51:20 +0000
+++ u1db/backends/inmemory.py	2012-06-12 14:34:24 +0000
@@ -222,6 +222,24 @@
             result.append(self._factory(doc_id, doc_rev, doc))
         return result
 
+    def get_range_from_index(self, index_name, start_value=None,
+                             end_value=None):
+        """Return all documents with key values in the specified range."""
+        try:
+            index = self._indexes[index_name]
+        except KeyError:
+            raise errors.IndexDoesNotExist
+        if isinstance(start_value, basestring):
+            start_value = (start_value,)
+        if isinstance(end_value, basestring):
+            end_value = (end_value,)
+        doc_ids = index.lookup_range(start_value, end_value)
+        result = []
+        for doc_id in doc_ids:
+            doc_rev, doc = self._docs[doc_id]
+            result.append(self._factory(doc_id, doc_rev, doc))
+        return result
+
     def get_index_keys(self, index_name):
         try:
             index = self._indexes[index_name]
@@ -345,6 +363,23 @@
         else:
             return self._lookup_prefix(values[:last])
 
+    def lookup_range(self, start_values, end_values):
+        """Find docs within the range."""
+        # TODO: Wildly inefficient, which is unlikely to be a problem for the
+        # inmemory implementation.
+        if start_values:
+            start_values = '\x01'.join(start_values)
+        if end_values:
+            end_values = '\x01'.join(end_values)
+        found = []
+        for key, doc_ids in sorted(self._values.iteritems()):
+            if start_values and start_values > key:
+                continue
+            if end_values and end_values < key:
+                break
+            found.extend(doc_ids)
+        return found
+
     def keys(self):
         """Find the indexed keys."""
         return self._values.keys()

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py	2012-05-31 18:51:20 +0000
+++ u1db/backends/sqlite_backend.py	2012-06-12 14:34:24 +0000
@@ -638,6 +638,56 @@
         res = c.fetchall()
         return [self._factory(r[0], r[1], r[2]) for r in res]
 
+    def get_range_from_index(self, index_name, start_value=None,
+                             end_value=None):
+        """Return all documents with key values in the specified range."""
+        definition = self._get_index_definition(index_name)
+        tables = ["document_fields d%d" % i for i in range(len(definition))]
+        novalue_where = [
+            "d.doc_id = d%d.doc_id AND d%d.field_name = ?" % (i, i) for i in
+            range(len(definition))]
+        range_where_lower = [
+            novalue_where[i] + (" AND d%d.value >= ?" % (i,)) for i in
+            range(len(definition))]
+        range_where_upper = [
+            novalue_where[i] + (" AND d%d.value <= ?" % (i,)) for i in
+            range(len(definition))]
+        args = []
+        where = []
+        if start_value:
+            if isinstance(start_value, basestring):
+                start_value = (start_value,)
+            if len(start_value) != len(definition):
+                raise errors.InvalidValueForIndex()
+            for idx, (field, value) in enumerate(zip(definition, start_value)):
+                args.append(field)
+                where.append(range_where_lower[idx])
+                args.append(value)
+        if end_value:
+            if isinstance(end_value, basestring):
+                end_value = (end_value,)
+            if len(end_value) != len(definition):
+                raise errors.InvalidValueForIndex()
+            for idx, (field, value) in enumerate(zip(definition, end_value)):
+                args.append(field)
+                where.append(range_where_upper[idx])
+                args.append(value)
+        statement = (
+            "SELECT d.doc_id, d.doc_rev, d.content FROM document d, %s "
+            "WHERE %s ORDER BY %s;" % (
+                ', '.join(tables),
+                ' AND '.join(where),
+                ', '.join(
+                    ['d%d.value' % i for i in range(len(definition))])))
+        c = self._db_handle.cursor()
+        try:
+            c.execute(statement, tuple(args))
+        except dbapi2.OperationalError, e:
+            raise dbapi2.OperationalError(str(e) +
+                '\nstatement: %s\nargs: %s\n' % (statement, args))
+        res = c.fetchall()
+        return [self._factory(r[0], r[1], r[2]) for r in res]
+
     def get_index_keys(self, index):
         c = self._db_handle.cursor()
         try:

=== modified file 'u1db/tests/c_backend_wrapper.pyx'
--- u1db/tests/c_backend_wrapper.pyx	2012-06-12 12:35:05 +0000
+++ u1db/tests/c_backend_wrapper.pyx	2012-06-12 14:34:24 +0000
@@ -102,6 +102,10 @@
     int u1db_get_from_index(u1database *db, u1query *query, void *context,
                              u1db_doc_callback cb, int n_values, char *val0,
                              ...)
+    int u1db_get_range_from_index(u1database *db, u1query *query,
+                                  void *context, u1db_doc_callback cb,
+                                  int n_values, const_char_ptr *start_values,
+                                  const_char_ptr *end_values)
     int u1db_delete_index(u1database *db, char *index_name)
     int u1db_list_indexes(u1database *db, void *context,
                   int (*cb)(void *context, const_char_ptr index_name,
@@ -1148,6 +1152,42 @@
         handle_status("get_from_index", status)
         return res
 
+    def get_range_from_index(self, index_name, start_value=None,
+                             end_value=None):
+        cdef CQuery query
+        cdef const_char_ptr *start_values
+        cdef int n_values
+        cdef const_char_ptr *end_values
+
+        if start_value is not None:
+            if isinstance(start_value, basestring):
+                start_value = (start_value,)
+            new_objs_1 = _list_to_str_array(
+                start_value, &start_values, &n_values)
+        else:
+            n_values = 0
+            start_values = NULL
+        if end_value is not None:
+            if isinstance(end_value, basestring):
+                end_value = (end_value,)
+            new_objs_2 = _list_to_str_array(
+                end_value, &end_values, &n_values)
+        else:
+            end_values = NULL
+        query = self._query_init(index_name)
+        res = []
+        try:
+            handle_status("get_range_from_index",
+                u1db_get_range_from_index(
+                    self._db, query._query, <void*>res, _append_doc_to_list,
+                    n_values, start_values, end_values))
+        finally:
+            if start_values != NULL:
+                free(<void*>start_values)
+            if end_values != NULL:
+                free(<void*>end_values)
+        return res
+
     def get_index_keys(self, index_name):
         cdef int status
         result = []

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2012-05-31 18:51:20 +0000
+++ u1db/tests/test_backends.py	2012-06-12 14:34:24 +0000
@@ -814,6 +814,68 @@
             [doc4, doc3, doc2, doc1],
             self.db.get_from_index('test-idx', 'v*', '*'))
 
+    def test_get_range_from_index_start_end(self):
+        doc1 = self.db.create_doc('{"key": "value3"}')
+        doc2 = self.db.create_doc('{"key": "value2"}')
+        self.db.create_doc('{"key": "value4"}')
+        self.db.create_doc('{"key": "value1"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc2, doc1],
+            self.db.get_range_from_index('test-idx', 'value2', 'value3'))
+
+    def test_get_range_from_index_start(self):
+        doc1 = self.db.create_doc('{"key": "value3"}')
+        doc2 = self.db.create_doc('{"key": "value2"}')
+        doc3 = self.db.create_doc('{"key": "value4"}')
+        self.db.create_doc('{"key": "value1"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc2, doc1, doc3],
+            self.db.get_range_from_index('test-idx', 'value2'))
+
+    def test_get_range_from_index_end(self):
+        self.db.create_doc('{"key": "value3"}')
+        doc2 = self.db.create_doc('{"key": "value2"}')
+        self.db.create_doc('{"key": "value4"}')
+        doc4 = self.db.create_doc('{"key": "value1"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc4, doc2],
+            self.db.get_range_from_index('test-idx', None, 'value2'))
+
+    def test_get_range_from_index_multi_column_start_end(self):
+        self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value3"}')
+        doc3 = self.db.create_doc('{"key": "value2", "key2": "value2"}')
+        self.db.create_doc('{"key": "value1", "key2": "value1"}')
+        self.db.create_index('test-idx', 'key', 'key2')
+        self.assertEqual(
+            [doc3, doc2],
+            self.db.get_range_from_index(
+                'test-idx', ('value2', 'value2'), ('value2', 'value3')))
+
+    def test_get_range_from_index_multi_column_start(self):
+        doc1 = self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value3"}')
+        self.db.create_doc('{"key": "value2", "key2": "value2"}')
+        self.db.create_doc('{"key": "value1", "key2": "value1"}')
+        self.db.create_index('test-idx', 'key', 'key2')
+        self.assertEqual(
+            [doc2, doc1],
+            self.db.get_range_from_index('test-idx', ('value2', 'value3')))
+
+    def test_get_range_from_index_multi_column_end(self):
+        self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value3"}')
+        doc3 = self.db.create_doc('{"key": "value2", "key2": "value2"}')
+        doc4 = self.db.create_doc('{"key": "value1", "key2": "value1"}')
+        self.db.create_index('test-idx', 'key', 'key2')
+        self.assertEqual(
+            [doc4, doc3, doc2],
+            self.db.get_range_from_index(
+                'test-idx', None, ('value2', 'value3')))
+
     def test_get_from_index_fails_if_no_index(self):
         self.assertRaises(
             errors.IndexDoesNotExist, self.db.get_from_index, 'foo')