Merge lp:~thisfred/u1db/and-the-wild-rocky-mountains-to-roam into lp:u1db

[Eric Casteleijn]

Made range queries work with wildcards in exactly the same way that regular queries do.

Made range queries work with wildcards in exactly the same way that regular queries do.

[lp:~thisfred/u1db/and-the-wild-rocky-mountains-to-roam]

327. By Eric Casteleijn on 2012-06-06

more out of memory checks. clearer variable names.

[Samuele Pedroni (pedronis)]

looks good,

I find the constant 0,1,2 used in start_wildcard[i] and end_wildcard[i] a bit cryptic, can they get names or something,

a bit worried about the size of/repetitions in get_from_index/get_range_from_index, suppose the bug about extracting a _format_query will possibly address that.

review: Approve

[lp:~thisfred/u1db/and-the-wild-rocky-mountains-to-roam]

328. By Eric Casteleijn on 2012-06-11

added constants for glob cases

[Eric Casteleijn (thisfred)]

> looks good,
>
> I find the constant 0,1,2 used in start_wildcard[i] and end_wildcard[i] a bit
> cryptic, can they get names or something,

Done.

> a bit worried about the size of/repetitions in
> get_from_index/get_range_from_index, suppose the bug about extracting a
> _format_query will possibly address that.

That is my plan.

[lp:~thisfred/u1db/and-the-wild-rocky-mountains-to-roam]

329. By Eric Casteleijn on 2012-06-12

merged trunk, resolved conflicts

330. By Eric Casteleijn on 2012-06-12

more conflicts resolved

=== modified file 'include/u1db/u1db_internal.h'
--- include/u1db/u1db_internal.h	2012-06-12 14:28:50 +0000
+++ include/u1db/u1db_internal.h	2012-06-12 15:20:23 +0000
@@ -364,7 +364,8 @@
  *     and callers must free() it.
  */
 int u1db__format_range_query(int n_fields, const char **start_values,
-                             const char **end_values, char **buf);
+                             const char **end_values, char **buf,
+                             int *start_wildcard, int *end_wildcard);
 
 /**
  * Given this document content, update the indexed fields in the db.

=== modified file 'src/u1db_query.c'
--- src/u1db_query.c	2012-06-12 14:28:50 +0000
+++ src/u1db_query.c	2012-06-12 15:20:23 +0000
@@ -23,6 +23,10 @@
 #include <ctype.h>
 #include <json/json.h>
 
+#define NO_GLOB 0
+#define IS_GLOB 1
+#define ENDS_IN_GLOB 2
+
 #define OPS 4
 #define MAX_INT_STR_LEN 21
 #ifndef max
@@ -93,6 +97,8 @@
     if (new_item == NULL)
         return U1DB_NOMEM;
     new_item->data = strdup(data);
+    if (new_item->data == NULL)
+        return U1DB_NOMEM;
     if (list->head == NULL)
     {
         list->head = new_item;
@@ -381,6 +387,8 @@
     for (item = values->head; item != NULL; item = item->next)
     {
         intermediate = strdup(item->data);
+        if (intermediate == NULL)
+            return U1DB_NOMEM;
         intermediate_ptr = intermediate;
         while (intermediate_ptr != NULL) {
             space_chr = strchr(intermediate_ptr, ' ');
@@ -459,6 +467,10 @@
             goto finish;
         }
         query->fields[offset] = strdup(field);
+        if (query->fields[offset] == NULL) {
+            status = U1DB_NOMEM;
+            goto finish;
+        }
         status = sqlite3_step(statement);
     }
     if (status == SQLITE_DONE) {
@@ -533,7 +545,6 @@
     return status;
 }
 
-
 int
 u1db_get_from_index_list(u1database *db, u1query *query, void *context,
                          u1db_doc_callback cb, int n_values,
@@ -569,12 +580,12 @@
                                    SQLITE_TRANSIENT);
         bind_arg++;
         if (status != SQLITE_OK) { goto finish; }
-        if (wildcard[i] == 0) {
+        if (wildcard[i] == NO_GLOB) {
             // Not a wildcard, so add the argument
             status = sqlite3_bind_text(statement, bind_arg, values[i], -1,
                                        SQLITE_TRANSIENT);
             bind_arg++;
-        } else if (wildcard[i] == 2) {
+        } else if (wildcard[i] == ENDS_IN_GLOB) {
             status = sqlite3_bind_text(statement, bind_arg, values[i], -1,
                                        SQLITE_TRANSIENT);
             bind_arg++;
@@ -602,7 +613,6 @@
     return status;
 }
 
-
 int
 u1db_get_range_from_index(u1database *db, u1query *query,
                           void *context, u1db_doc_callback cb,
@@ -613,6 +623,9 @@
     char *query_str = NULL;
     sqlite3_stmt *statement = NULL;
     char *doc_id = NULL;
+    char *stripped = NULL;
+    int start_wildcard[20] = {0};
+    int end_wildcard[20] = {0};
 
     if (db == NULL || query == NULL || cb == NULL || n_values < 0) {
         return U1DB_INVALID_PARAMETER;
@@ -621,7 +634,8 @@
         return U1DB_INVALID_VALUE_FOR_INDEX;
     }
     status = u1db__format_range_query(
-        query->num_fields, start_values, end_values, &query_str);
+        query->num_fields, start_values, end_values, &query_str,
+        start_wildcard, end_wildcard);
     if (status != U1DB_OK) { goto finish; }
     status = sqlite3_prepare_v2(db->sql_handle, query_str, -1,
                                 &statement, NULL);
@@ -634,16 +648,49 @@
         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 (start_wildcard[i] == NO_GLOB) {
+                status = sqlite3_bind_text(
+                    statement, bind_arg, start_values[i], -1,
+                    SQLITE_TRANSIENT);
+                bind_arg++;
+            } else if (start_wildcard[i] == ENDS_IN_GLOB) {
+                if (stripped != NULL)
+                    free(stripped);
+                stripped = strdup(start_values[i]);
+                if (stripped == NULL) {
+                    status = U1DB_NOMEM;
+                    goto finish;
+                }
+                stripped[strlen(stripped) - 1] = '\0';
+                status = sqlite3_bind_text(
+                    statement, bind_arg, stripped, -1, SQLITE_TRANSIENT);
+                bind_arg++;
+            }
+           if (status != SQLITE_OK) { goto finish; }
         }
         if (end_values != NULL) {
-            status = sqlite3_bind_text(
-                statement, bind_arg, end_values[i], -1, SQLITE_TRANSIENT);
+            if (end_wildcard[i] == NO_GLOB) {
+                status = sqlite3_bind_text(
+                    statement, bind_arg, end_values[i], -1,
+                    SQLITE_TRANSIENT);
+                bind_arg++;
+            } else if (end_wildcard[i] == ENDS_IN_GLOB) {
+                if (stripped != NULL)
+                    free(stripped);
+                stripped = strdup(end_values[i]);
+                if (stripped == NULL) {
+                    status = U1DB_NOMEM;
+                    goto finish;
+                }
+                stripped[strlen(stripped) - 1] = '\0';
+                status = sqlite3_bind_text(
+                    statement, bind_arg, stripped, -1, SQLITE_TRANSIENT);
+                bind_arg++;
+                status = sqlite3_bind_text(
+                    statement, bind_arg, end_values[i], -1, SQLITE_TRANSIENT);
+                bind_arg++;
+            }
             if (status != SQLITE_OK) { goto finish; }
-            bind_arg++;
         }
     }
     status = sqlite3_step(statement);
@@ -664,6 +711,8 @@
     if (query_str != NULL) {
         free(query_str);
     }
+    if (stripped != NULL)
+        free(stripped);
     return status;
 }
 
@@ -806,12 +855,12 @@
             goto finish;
         }
         if (val[0] == '*') {
-            wildcard[i] = 1;
+            wildcard[i] = IS_GLOB;
             have_wildcard = 1;
             add_to_buf(&cur, &buf_size, " AND d%d.value NOT NULL", i);
         } else if (val[0] != '\0' && val[strlen(val)-1] == '*') {
             // glob
-            wildcard[i] = 2;
+            wildcard[i] = ENDS_IN_GLOB;
             if (have_wildcard) {
                 //globs not allowed after another wildcard
                 status = U1DB_INVALID_GLOBBING;
@@ -820,7 +869,7 @@
             have_wildcard = 1;
             add_to_buf(&cur, &buf_size, " AND d%d.value GLOB ?", i);
         } else {
-            wildcard[i] = 0;
+            wildcard[i] = NO_GLOB;
             if (have_wildcard) {
                 // Can't have a non-wildcard after a wildcard
                 status = U1DB_INVALID_GLOBBING;
@@ -846,12 +895,15 @@
 
 int
 u1db__format_range_query(int n_fields, const char **start_values,
-                         const char **end_values, char **buf)
+                         const char **end_values, char **buf,
+                         int *start_wildcard, int *end_wildcard)
 {
     int status = U1DB_OK;
     int buf_size, i;
     char *cur = NULL;
     const char *val = NULL;
+    int have_start_wildcard = 0;
+    int have_end_wildcard = 0;
 
     if (n_fields < 1) {
         return U1DB_INVALID_PARAMETER;
@@ -882,7 +934,29 @@
                 status = U1DB_INVALID_VALUE_FOR_INDEX;
                 goto finish;
             }
-            add_to_buf(&cur, &buf_size, " AND d%d.value >= ?", i);
+            if (val[0] == '*') {
+                start_wildcard[i] = IS_GLOB;
+                have_start_wildcard= 1;
+                add_to_buf(&cur, &buf_size, " and d%d.value not null", i);
+            } else if (val[0] != '\0' && val[strlen(val)-1] == '*') {
+                // glob
+                start_wildcard[i] = ENDS_IN_GLOB;
+                if (have_start_wildcard) {
+                    //globs not allowed after another wildcard
+                    status = U1DB_INVALID_GLOBBING;
+                    goto finish;
+                }
+                have_start_wildcard = 1;
+                add_to_buf(&cur, &buf_size, " and d%d.value >= ?", i);
+            } else {
+                start_wildcard[i] = NO_GLOB;
+                if (have_start_wildcard) {
+                    // can't have a non-wildcard after a wildcard
+                    status = U1DB_INVALID_GLOBBING;
+                    goto finish;
+                }
+                add_to_buf(&cur, &buf_size, " and d%d.value >= ?", i);
+            }
         }
         if (end_values != NULL) {
             val = end_values[i];
@@ -890,7 +964,31 @@
                 status = U1DB_INVALID_VALUE_FOR_INDEX;
                 goto finish;
             }
-            add_to_buf(&cur, &buf_size, " AND d%d.value <= ?", i);
+            if (val[0] == '*') {
+                end_wildcard[i] = IS_GLOB;
+                have_end_wildcard = 1;
+                add_to_buf(&cur, &buf_size, " AND d%d.value NOT NULL", i);
+            } else if (val[0] != '\0' && val[strlen(val)-1] == '*') {
+                // glob
+                end_wildcard[i] = ENDS_IN_GLOB;
+                if (have_end_wildcard) {
+                    //globs not allowed after another wildcard
+                    status = U1DB_INVALID_GLOBBING;
+                    goto finish;
+                }
+                have_end_wildcard = 1;
+                add_to_buf(
+                    &cur, &buf_size,
+                    " AND (d%d.value < ? OR d%d.value GLOB ?)", i, i);
+            } else {
+                end_wildcard[i] = NO_GLOB;
+                if (have_end_wildcard) {
+                    // Can't have a non-wildcard after a wildcard
+                    status = U1DB_INVALID_GLOBBING;
+                    goto finish;
+                }
+                add_to_buf(&cur, &buf_size, " AND d%d.value <= ?", i);
+            }
         }
 
     }
@@ -919,12 +1017,16 @@
 {
     transformation *inner = NULL;
     char *new_field = NULL, *new_ptr, *argptr, *argend;
-    char *word, *first_comma;
+    char *word = NULL, *first_comma;
     int status = U1DB_OK;
     int i, size;
     int new_value_type = json_type_string;
     char *field_copy, *end = NULL;
     field_copy = strdup(field);
+    if (field_copy == NULL) {
+        status = U1DB_NOMEM;
+        goto finish;
+    }
     end = field_copy;
     while (*end != '(' && *end != ')' && *end != '\0')
     {
@@ -940,12 +1042,15 @@
         }
     }
     else {
-        // TODO: unicode fieldnames ?
         size = (end - field_copy);
         word = (char *)calloc(size + 1, 1);
         strncpy(word, field_copy, size);
     }
     new_field = strdup(end);
+    if (new_field == NULL) {
+        status = U1DB_NOMEM;
+        goto finish;
+    }
     new_ptr = new_field;
     if (status != U1DB_OK)
         goto finish;
@@ -1035,10 +1140,12 @@
         result->value_type = value_type;
     }
 finish:
-    free(word);
-    free(field_copy);
+    if (word != NULL)
+        free(word);
+    if (field_copy != NULL)
+        free(field_copy);
     if (new_field != NULL)
-    free(new_field);
+        free(new_field);
     return status;
 }
 

=== modified file 'u1db/__init__.py'
--- u1db/__init__.py	2012-06-12 14:28:50 +0000
+++ u1db/__init__.py	2012-06-12 15:20:23 +0000
@@ -198,20 +198,24 @@
     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.
+        Both ends of the range are inclusive. 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. 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.) It is also
+        possible to append a '*' to the last supplied value (eg 'val*', '*',
+        '*' or 'val', 'val*', '*', but not 'val*', 'val', '*')
 
         :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), ...
+        :param start_values: tuples of values that define the lower bound of
+            the range. eg, if you have an index with 3 fields then you would
+            have: (val1, val2, val3)
+        :param end_values: tuples of values that define the upper bound of the
+            range. eg, if you have an index with 3 fields then you would have:
+            (val1, val2, val3)
         """
         raise NotImplementedError(self.get_range_from_index)
 

=== modified file 'u1db/backends/inmemory.py'
--- u1db/backends/inmemory.py	2012-06-04 21:01:26 +0000
+++ u1db/backends/inmemory.py	2012-06-12 15:20:23 +0000
@@ -27,6 +27,11 @@
 from u1db.backends import CommonBackend, CommonSyncTarget
 
 
+def get_prefix(value):
+    key_prefix = '\x01'.join(value)
+    return key_prefix.rstrip('*')
+
+
 class InMemoryDatabase(CommonBackend):
     """A database that only stores the data internally."""
 
@@ -368,15 +373,24 @@
         # TODO: Wildly inefficient, which is unlikely to be a problem for the
         # inmemory implementation.
         if start_values:
-            start_values = '\x01'.join(start_values)
+            self._find_non_wildcards(start_values)
+            start_values = get_prefix(start_values)
         if end_values:
-            end_values = '\x01'.join(end_values)
+            if self._find_non_wildcards(end_values) == -1:
+                exact = True
+            else:
+                exact = False
+            end_values = get_prefix(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
+                if exact:
+                    break
+                else:
+                    if not key.startswith(end_values):
+                        break
             found.extend(doc_ids)
         return found
 
@@ -388,8 +402,7 @@
         """Find docs that match the prefix string in values."""
         # TODO: We need a different data structure to make prefix style fast,
         #       some sort of sorted list would work, but a plain dict doesn't.
-        key_prefix = '\x01'.join(value)
-        key_prefix = key_prefix.rstrip('*')
+        key_prefix = get_prefix(value)
         all_doc_ids = []
         for key, doc_ids in sorted(self._values.iteritems()):
             if key.startswith(key_prefix):

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py	2012-06-04 18:36:31 +0000
+++ u1db/backends/sqlite_backend.py	2012-06-12 15:20:23 +0000
@@ -568,14 +568,19 @@
 
     @staticmethod
     def _transform_glob(value, escape_char='.'):
-        """Transform the given glob value into a valid LIKE statement.
-        """
+        """Transform the given glob value into a valid LIKE statement."""
         to_escape = [escape_char, '%', '_']
         for esc in to_escape:
             value = value.replace(esc, escape_char + esc)
         assert value[-1] == '*'
         return value[:-1] + '%'
 
+    @staticmethod
+    def _strip_glob(value):
+        """Remove the trailing * from a value."""
+        assert value[-1] == '*'
+        return value[:-1]
+
     def get_from_index(self, index_name, *key_values):
         definition = self._get_index_definition(index_name)
         # First, build the definition. We join the document_fields table
@@ -646,6 +651,14 @@
         novalue_where = [
             "d.doc_id = d%d.doc_id AND d%d.field_name = ?" % (i, i) for i in
             range(len(definition))]
+        wildcard_where = [
+            novalue_where[i] + (" AND d%d.value NOT NULL" % (i,)) for i in
+            range(len(definition))]
+        like_where = [
+            novalue_where[i] + (
+                " AND (d%d.value < ? OR d%d.value LIKE ? ESCAPE '.')" %
+                (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))]
@@ -659,19 +672,52 @@
                 start_value = (start_value,)
             if len(start_value) != len(definition):
                 raise errors.InvalidValueForIndex()
+            is_wildcard = False
             for idx, (field, value) in enumerate(zip(definition, start_value)):
                 args.append(field)
-                where.append(range_where_lower[idx])
-                args.append(value)
+                if value.endswith('*'):
+                    if value == '*':
+                        where.append(wildcard_where[idx])
+                    else:
+                        # This is a glob match
+                        if is_wildcard:
+                            # We can't have a partial wildcard following
+                            # another wildcard
+                            raise errors.InvalidGlobbing
+                        where.append(range_where_lower[idx])
+                        args.append(self._strip_glob(value))
+                    is_wildcard = True
+                else:
+                    if is_wildcard:
+                        raise errors.InvalidGlobbing
+                    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()
+            is_wildcard = False
             for idx, (field, value) in enumerate(zip(definition, end_value)):
                 args.append(field)
-                where.append(range_where_upper[idx])
-                args.append(value)
+                if value.endswith('*'):
+                    if value == '*':
+                        where.append(wildcard_where[idx])
+                    else:
+                        # This is a glob match
+                        if is_wildcard:
+                            # We can't have a partial wildcard following
+                            # another wildcard
+                            raise errors.InvalidGlobbing
+                        where.append(like_where[idx])
+                        args.append(self._strip_glob(value))
+                        args.append(self._transform_glob(value))
+                    is_wildcard = True
+                else:
+                    if is_wildcard:
+                        raise errors.InvalidGlobbing
+                    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;" % (

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2012-06-04 14:52:57 +0000
+++ u1db/tests/test_backends.py	2012-06-12 15:20:23 +0000
@@ -844,6 +844,39 @@
             [doc4, doc2],
             self.db.get_range_from_index('test-idx', None, 'value2'))
 
+    def test_get_wildcard_range_from_index_start(self):
+        doc1 = self.db.create_doc('{"key": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value23"}')
+        doc3 = self.db.create_doc('{"key": "value2"}')
+        doc4 = self.db.create_doc('{"key": "value22"}')
+        self.db.create_doc('{"key": "value1"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc3, doc4, doc2, doc1],
+            self.db.get_range_from_index('test-idx', 'value2*'))
+
+    def test_get_wildcard_range_from_index_end(self):
+        self.db.create_doc('{"key": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value23"}')
+        doc3 = self.db.create_doc('{"key": "value2"}')
+        doc4 = self.db.create_doc('{"key": "value22"}')
+        doc5 = self.db.create_doc('{"key": "value1"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc5, doc3, doc4, doc2],
+            self.db.get_range_from_index('test-idx', None, 'value2*'))
+
+    def test_get_wildcard_range_from_index_start_end(self):
+        self.db.create_doc('{"key": "a"}')
+        doc2 = self.db.create_doc('{"key": "boo3"}')
+        doc3 = self.db.create_doc('{"key": "catalyst"}')
+        doc4 = self.db.create_doc('{"key": "whaever"}')
+        doc5 = self.db.create_doc('{"key": "zerg"}')
+        self.db.create_index('test-idx', 'key')
+        self.assertEqual(
+            [doc3, doc4],
+            self.db.get_range_from_index('test-idx', 'cat*', 'zap*'))
+
     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"}')
@@ -876,6 +909,71 @@
             self.db.get_range_from_index(
                 'test-idx', None, ('value2', 'value3')))
 
+    def test_get_wildcard_range_from_index_multi_column_start(self):
+        doc1 = self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value23"}')
+        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, doc1],
+            self.db.get_range_from_index('test-idx', ('value2', 'value2*')))
+
+    def test_get_wildcard_range_from_index_multi_column_end(self):
+        self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value23"}')
+        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', 'value2*')))
+
+    def test_get_glob_range_from_index_multi_column_start(self):
+        doc1 = self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value23"}')
+        self.db.create_doc('{"key": "value1", "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', '*')))
+
+    def test_get_glob_range_from_index_multi_column_end(self):
+        self.db.create_doc('{"key": "value3", "key2": "value4"}')
+        doc2 = self.db.create_doc('{"key": "value2", "key2": "value23"}')
+        doc3 = self.db.create_doc('{"key": "value1", "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', '*')))
+
+    def test_get_range_from_index_illegal_wildcard_order(self):
+        self.db.create_index('test-idx', 'k1', 'k2')
+        self.assertRaises(
+            errors.InvalidGlobbing,
+            self.db.get_range_from_index, 'test-idx', ('*', 'v2'))
+
+    def test_get_range_from_index_illegal_glob_after_wildcard(self):
+        self.db.create_index('test-idx', 'k1', 'k2')
+        self.assertRaises(
+            errors.InvalidGlobbing,
+            self.db.get_range_from_index, 'test-idx', ('*', 'v*'))
+
+    def test_get_range_from_index_illegal_wildcard_order_end(self):
+        self.db.create_index('test-idx', 'k1', 'k2')
+        self.assertRaises(
+            errors.InvalidGlobbing,
+            self.db.get_range_from_index, 'test-idx', None, ('*', 'v2'))
+
+    def test_get_range_from_index_illegal_glob_after_wildcard_end(self):
+        self.db.create_index('test-idx', 'k1', 'k2')
+        self.assertRaises(
+            errors.InvalidGlobbing,
+            self.db.get_range_from_index, 'test-idx', None, ('*', 'v*'))
+
     def test_get_from_index_fails_if_no_index(self):
         self.assertRaises(
             errors.IndexDoesNotExist, self.db.get_from_index, 'foo')