Merge lp:~jameinel/u1db/index-transformations into lp:u1db

[John A Meinel]

This takes James Westby's great work on index transformations, and updates it a bit. Some thoughts:

1) This changes it so that the Getter api always thinks in terms of lists, rather than sometimes direct values and sometimes lists. It cleans up some of the internal code that had to check if thing was a list or not, and then apply it to the list, vs apply it to an item.

I think it will also match a C api better, since you don't have object types there. So you just end up with always-a-list. (still not sure what to do about ints vs strings, but I'm not worrying too much about that yet.)

2) The only one I'm not very sure about is IsNull. At the moment doing something like:

   create_index('null_field', ["is_null(field)"])

 Will always return a single width list. So if your document is:
  '{"field": "value"}' => [True]
  '{}' => [False]
  '{"field": ["list", "values"]}' => [False]
  '{"field": null}' => [True]
  '{"field": []}' => [True]
  '{"field": [null]}' => ??? I think [True]
  '{"field": [1, null]}' => [False]

 In James's original implementation the only one that was different was the empty-list, which would
 claim that an empty list is not null.

 I think this is what we want, though.

3) We should probably move how the indexing code is tested into being a backend permutation test. At least, we should add more than the small handful of tests we have now.

[Samuele Pedroni (pedronis)]

I suppose the parser is written in a style that is easy to translate to C but then I would really use some kind of caching of parser->getter outcomes in SQLitePartialExpandDatabase._evaluate_index. I would expect inserting data otherwise to be (quite?) slower than it was before these changes.

69 + if keys is None:
70 return None

that should just be if key: in the new world, the code doesn't break, but we don't bail out early anymore

271 + elif isinstance(raw_doc, list):
272 + # If anything in the list is not a simple type, the list is
273 + result = [val for val in raw_doc

I don't understand the comment there, is it truncated?

is it intentional to check in .testr.conf?

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/2/2011 3:55 PM, Samuele Pedroni wrote:
> I suppose the parser is written in a style that is easy to
> translate to C but then I would really use some kind of caching of
> parser->getter outcomes in
> SQLitePartialExpandDatabase._evaluate_index. I would expect
> inserting data otherwise to be (quite?) slower than it was before
> these changes.
>

Yeah, I'm working on actually benchmarking it to make sure it matters.
It shouldn't be hard to just have a:

parsers = []
for field in fields:
  parsers.append(Parser(field))

for content in docs:
  raw_doc = loads(content)
  for parser in parsers:
    rows = parser.apply(raw_doc)

> 69 + if keys is None: 70 return None
>
> that should just be if key: in the new world, the code doesn't
> break, but we don't bail out early anymore

sure, good catch.

>
> 271 + elif isinstance(raw_doc, list): 272 + # If anything in the
> list is not a simple type, the list is 273 + result = [val for val
> in raw_doc
>
> I don't understand the comment there, is it truncated?
>

yeah, it got truncated. Originally there was a loop that if *any* item
in the list was not a simple value, then it would treat the whole list
as None. I changed it to just omit the non-simple types.

>
> is it intentional to check in .testr.conf?

This is something James did. But yes. It tells the 'testr' (test
repository?) program how to run your test suite. I'm fine including it.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk7ZBi0ACgkQJdeBCYSNAAMuZACfcwv8OzDgGeq4ZPFPKQGuW+6a
W5kAoK6iubdWpCs3HS5JrMiEEHh8ACli
=B2hV
-----END PGP SIGNATURE-----

[lp:~jameinel/u1db/index-transformations]

144. By John A Meinel on 2011-12-06

Use a for loop instead of while + counters to do _take_word

145. By John A Meinel on 2011-12-06

Pre-parse the index definition before we evaluate them on documents.

146. By John A Meinel on 2011-12-06

Add some doc strings.

[John A Meinel (jameinel)]

This has now been updated to pre-parse the index definitions, and then apply the getters to the documents. There was one trick that current trunk creates a PRIMARY KEY index on document_fields, and this patch removes it. These tests were done with the index removed.

Here are the benchmark results:

  2.530s create_index(title) trunk
  3.357s create_index(title) no-caching
  2.588s create_index(title) caching

The other thing to note is the effect if you create indexes with more complex definitions:
   2.588s create title
   2.859s create low_title
   3.879s create low_split_title
   3.540s create low_low_title

vs

   3.357s create title
   3.735s create low_title
   5.121s create low_split_title
   5.329s create low_low_title

Note that some of the slowdown is because the document_fields table is getting bigger. Also, we should note that the create_index time with *no* new fields inserted is:

   1.925s create low_title (trunk)

(that is because trunk doesn't support lower() as an operator yet, so it gives a good baseline of functionality.)

I was a bit surprised that it was that slow, given the speeds of _iter_all_docs and simplejson.loads.

[lp:~jameinel/u1db/index-transformations]

147. By John A Meinel on 2011-12-06

Fix the shortcut code.

[Samuele Pedroni (pedronis)]

looks good, I would probably be even more aggressive and do this, to amortize parsing the getters across put_docs as well:

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py 2011-12-06 14:18:56 +0000
+++ u1db/backends/sqlite_backend.py 2011-12-06 15:11:28 +0000
@@ -39,6 +39,8 @@
         self._db_handle = dbapi2.connect(sqlite_file)
         self._real_replica_uid = None
         self._ensure_schema()
+ self._parser = query_parser.Parser()
+ self._cached_getters = {}

     def get_sync_target(self):
         return SQLiteSyncTarget(self)
@@ -199,8 +201,11 @@

     def _parse_index_definition(self, index_field):
         """Parse a field definition for an index, returning a Getter."""
- parser = query_parser.Parser()
- getter = parser.parse(index_field)
+ try:
+ getter = self._cached_getters[index_field]
+ except KeyError:
+ getter = self._parser.parse(index_field)
+ self._cached_getters[index_field] = getter
         return getter

     def _update_indexes(self, doc_id, raw_doc, getters, db_cursor):

review: Approve

[lp:~jameinel/u1db/index-transformations]

148. By John A Meinel on 2011-12-06

Fix up a outdated comment.

149. By John A Meinel on 2011-12-06

add a comment about longer-lived Getter caching.

=== modified file '.bzrignore'
--- .bzrignore	2011-12-02 19:05:35 +0000
+++ .bzrignore	2011-12-06 15:24:25 +0000
@@ -2,3 +2,4 @@
 ./dist
 ./u1db.egg-info
 doc/sqlite_schema.html
+.testrepository

=== added file '.testr.conf'
--- .testr.conf	1970-01-01 00:00:00 +0000
+++ .testr.conf	2011-12-06 15:24:25 +0000
@@ -0,0 +1,4 @@
+[DEFAULT]
+test_command=${PYTHON:-python} -m subunit.run $LISTOPT $IDOPTION discover u1db
+test_id_option=--load-list $IDFILE
+test_list_option=--list

=== modified file 'doc/sqlite_schema.txt'
--- doc/sqlite_schema.txt	2011-11-16 08:03:06 +0000
+++ doc/sqlite_schema.txt	2011-12-06 15:24:25 +0000
@@ -38,7 +38,6 @@
         doc_id TEXT,
         field_name TEXT,
         value TEXT,
-        CONSTRAINT document_fields_pkey PRIMARY KEY (doc_id, field_name)
     );
 
 So if you had two documents of the form::

=== modified file 'u1db/backends/inmemory.py'
--- u1db/backends/inmemory.py	2011-12-02 11:02:42 +0000
+++ u1db/backends/inmemory.py	2011-12-06 15:24:25 +0000
@@ -16,7 +16,11 @@
 
 import simplejson
 
-from u1db import Document, errors
+from u1db import (
+    Document,
+    errors,
+    query_parser,
+    )
 from u1db.backends import CommonBackend, CommonSyncTarget
 
 
@@ -182,6 +186,8 @@
         self._name = index_name
         self._definition = index_definition
         self._values = {}
+        parser = query_parser.Parser()
+        self._getters = parser.parse_all(self._definition)
 
     def evaluate_json(self, doc):
         """Determine the 'key' after applying this index to the doc."""
@@ -190,32 +196,35 @@
 
     def evaluate(self, obj):
         """Evaluate a dict object, applying this definition."""
-        result = []
-        for field in self._definition:
-            val = obj
-            for subfield in field.split('.'):
-                val = val.get(subfield)
-            if val is None:
-                return None
-            result.append(val)
-        return '\x01'.join(result)
+        all_rows = [[]]
+        for getter in self._getters:
+            new_rows = []
+            keys = getter.get(obj)
+            if not keys:
+                return []
+            for key in keys:
+                new_rows.extend([row + [key] for row in all_rows])
+            all_rows = new_rows
+        all_rows = ['\x01'.join(row) for row in all_rows]
+        return all_rows
 
     def add_json(self, doc_id, doc):
         """Add this json doc to the index."""
-        key = self.evaluate_json(doc)
-        if key is None:
+        keys = self.evaluate_json(doc)
+        if not keys:
             return
-        self._values.setdefault(key, []).append(doc_id)
+        for key in keys:
+            self._values.setdefault(key, []).append(doc_id)
 
     def remove_json(self, doc_id, doc):
         """Remove this json doc from the index."""
-        key = self.evaluate_json(doc)
-        if key is None:
-            return
-        doc_ids = self._values[key]
-        doc_ids.remove(doc_id)
-        if not doc_ids:
-            del self._values[key]
+        keys = self.evaluate_json(doc)
+        if keys:
+            for key in keys:
+                doc_ids = self._values[key]
+                doc_ids.remove(doc_id)
+                if not doc_ids:
+                    del self._values[key]
 
     def _find_non_wildcards(self, values):
         """Check if this should be a wildcard match.
@@ -288,4 +297,3 @@
     def record_sync_info(self, other_replica_uid, other_replica_generation):
         self._db.set_sync_generation(other_replica_uid,
                                      other_replica_generation)
-

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py	2011-12-02 11:02:42 +0000
+++ u1db/backends/sqlite_backend.py	2011-12-06 15:24:25 +0000
@@ -21,7 +21,12 @@
 import uuid
 
 from u1db.backends import CommonBackend, CommonSyncTarget
-from u1db import Document, errors
+from u1db import (
+    compat,
+    Document,
+    errors,
+    query_parser,
+    )
 
 
 class SQLiteDatabase(CommonBackend):
@@ -136,9 +141,7 @@
         c.execute("CREATE TABLE document_fields ("
                   " doc_id TEXT,"
                   " field_name TEXT,"
-                  " value TEXT,"
-                  " CONSTRAINT document_fields_pkey"
-                  " PRIMARY KEY (doc_id, field_name))")
+                  " value TEXT)")
         # TODO: Should we include doc_id or not? By including it, the
         #       content can be returned directly from the index, and
         #       matched with the documents table, roughly saving 1 btree
@@ -194,6 +197,36 @@
     def _extra_schema_init(self, c):
         """Add any extra fields, etc to the basic table definitions."""
 
+    def _parse_index_definition(self, index_field):
+        """Parse a field definition for an index, returning a Getter."""
+        # Note: We may want to keep a Parser object around, and cache the
+        #       Getter objects for a greater length of time. Specifically, if
+        #       you create a bunch of indexes, and then insert 50k docs, you'll
+        #       re-parse the indexes between puts. The time to insert the docs
+        #       is still likely to dominate put_doc time, though.
+        parser = query_parser.Parser()
+        getter = parser.parse(index_field)
+        return getter
+
+    def _update_indexes(self, doc_id, raw_doc, getters, db_cursor):
+        """Update document_fields for a single document.
+
+        :param doc_id: Identifier for this document
+        :param raw_doc: The python dict representation of the document.
+        :param getters: A list of [(field_name, Getter)]. Getter.get will be
+            called to evaluate the index definition for this document, and the
+            results will be inserted into the db.
+        :param db_cursor: An sqlite Cursor.
+        :return: None
+        """
+        values = []
+        for field_name, getter in getters:
+            for idx_value in getter.get(raw_doc):
+                values.append((doc_id, field_name, idx_value))
+        if values:
+            db_cursor.executemany(
+                "INSERT INTO document_fields VALUES (?, ?, ?)", values)
+
     def _set_replica_uid(self, replica_uid):
         """Force the replica_uid to be set."""
         with self._db_handle:
@@ -550,21 +583,9 @@
 
     def _evaluate_index(self, raw_doc, field):
         val = raw_doc
-        for subfield in field.split('.'):
-            if val is None:
-                return None
-            val = val.get(subfield, None)
-        return val
-
-    def _update_indexes(self, doc_id, raw_doc, fields, db_cursor):
-        values = []
-        for field_name in fields:
-            idx_value = self._evaluate_index(raw_doc, field_name)
-            if idx_value is not None:
-                values.append((doc_id, field_name, idx_value))
-        if values:
-            db_cursor.executemany(
-                "INSERT INTO document_fields VALUES (?, ?, ?)", values)
+        parser = query_parser.Parser()
+        getter = parser.parse(field)
+        return getter.get(raw_doc)
 
     def _put_and_update_indexes(self, old_doc, doc):
         c = self._db_handle.cursor()
@@ -584,8 +605,9 @@
         if indexed_fields:
             # It is expected that len(indexed_fields) is shorter than
             # len(raw_doc)
-            # TODO: Handle nested indexed fields.
-            self._update_indexes(doc.doc_id, raw_doc, indexed_fields, c)
+            getters = [(field, self._parse_index_definition(field))
+                       for field in indexed_fields]
+            self._update_indexes(doc.doc_id, raw_doc, getters, c)
         c.execute("INSERT INTO transaction_log(doc_id) VALUES (?)",
                   (doc.doc_id,))
 
@@ -613,9 +635,15 @@
                 yield row
 
     def _update_all_indexes(self, new_fields):
+        """Iterate all the documents, and add content to document_fields.
+
+        :param new_fields: The index definitions that need to be added.
+        """
+        getters = [(field, self._parse_index_definition(field))
+                   for field in new_fields]
+        c = self._db_handle.cursor()
         for doc_id, doc in self._iter_all_docs():
             raw_doc = simplejson.loads(doc)
-            c = self._db_handle.cursor()
-            self._update_indexes(doc_id, raw_doc, new_fields, c)
+            self._update_indexes(doc_id, raw_doc, getters, c)
 
 SQLiteDatabase.register_implementation(SQLitePartialExpandDatabase)

=== modified file 'u1db/errors.py'
--- u1db/errors.py	2011-12-01 14:46:15 +0000
+++ u1db/errors.py	2011-12-06 15:24:25 +0000
@@ -65,6 +65,10 @@
     wire_description = "database does not exist"
 
 
+class IndexDefinitionParseError(U1DBError):
+    """The index definition cannot be parsed."""
+
+
 class HTTPError(U1DBError):
     """Unspecific HTTP errror."""
 

=== added file 'u1db/query_parser.py'
--- u1db/query_parser.py	1970-01-01 00:00:00 +0000
+++ u1db/query_parser.py	2011-12-06 15:24:25 +0000
@@ -0,0 +1,235 @@
+# Copyright 2011 Canonical Ltd.
+#
+# This program is free software: you can redistribute it and/or modify it
+# under the terms of the GNU General Public License version 3, as published
+# by the Free Software Foundation.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranties of
+# MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
+# PURPOSE.  See the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+"""Code for parsing Index definitions."""
+
+import string
+
+from u1db import (
+    errors,
+    )
+
+
+class Getter(object):
+    """Get values from a document based on a specification."""
+
+    def get(self, raw_doc):
+        """Get a value from the document.
+
+        :param raw_doc: a python dictionary to get the value from.
+        :return: A list of values that match the description.
+        """
+        raise NotImplementedError(self.get)
+
+
+class StaticGetter(Getter):
+    """A getter that returns a defined value (independent of the doc)."""
+
+    def __init__(self, value):
+        """Create a StaticGetter.
+
+        :param value: the value to return when get is called.
+        """
+        if value is None:
+            self.value = []
+        elif isinstance(value, list):
+            self.value = value
+        else:
+            self.value = [value]
+
+    def get(self, raw_doc):
+        return self.value
+
+
+class ExtractField(Getter):
+    """Extract a field from the document."""
+
+    def __init__(self, field):
+        """Create an ExtractField object.
+
+        When a document is passed to get() this will return a value
+        from the document based on the field specifier passed to
+        the constructor.
+
+        None will be returned if the field is nonexistant, or refers to an
+        object, rather than a simple type or list of simple types.
+
+        :param field: a specifier for the field to return.
+            This is either a field name, or a dotted field name.
+        """
+        self.field = field
+
+    def get(self, raw_doc):
+        for subfield in self.field.split('.'):
+            if isinstance(raw_doc, dict):
+                raw_doc = raw_doc.get(subfield)
+            else:
+                return []
+        if isinstance(raw_doc, dict):
+            return []
+        if raw_doc is None:
+            result = []
+        elif isinstance(raw_doc, list):
+            # Strip anything in the list that isn't a simple type
+            result = [val for val in raw_doc
+                      if not isinstance(val, (dict, list))]
+        else:
+            result = [raw_doc]
+        return result
+
+
+class Transformation(Getter):
+    """A transformation on a value from another Getter."""
+
+    name = None
+    """The name that the transform has in a query string."""
+
+    def __init__(self, inner):
+        """Create a transformation.
+
+        :param inner: the Getter to transform the value for.
+        """
+        self.inner = inner
+
+    def get(self, raw_doc):
+        inner_values = self.inner.get(raw_doc)
+        assert isinstance(inner_values, list), 'get() should always return a list'
+        return self.transform(inner_values)
+
+    def transform(self, values):
+        """Transform the values.
+
+        This should be implemented by subclasses to transform the
+        value when get() is called.
+
+        :param values: the values from the other Getter
+        :return: the transformed values.
+        """
+        raise NotImplementedError(self.transform)
+
+
+class Lower(Transformation):
+    """Lowercase a string.
+
+    This transformation will return None for non-string inputs. However,
+    it will lowercase any strings in a list, dropping any elements
+    that are not strings.
+    """
+
+    name = "lower"
+
+    def _can_transform(self, val):
+        return not isinstance(val, (int, bool, float, list, dict))
+
+    def transform(self, values):
+        if not values:
+            return []
+        return [val.lower() for val in values if self._can_transform(val)]
+
+
+class SplitWords(Transformation):
+    """Split a string on whitespace.
+
+    This Getter will return [] for non-string inputs. It will however
+    split any strings in an input list, discarding any elements that
+    are not strings.
+    """
+
+    name = "split_words"
+
+    def _can_transform(self, val):
+        return not isinstance(val, (int, bool, float, list, dict))
+
+    def transform(self, values):
+        if not values:
+            return []
+        result = []
+        for value in values:
+            if self._can_transform(value):
+                # TODO: This is quadratic to search the list linearly while we
+                #       are appending to it. Consider using a set() instead.
+                for word in value.split():
+                    if word not in result:
+                        result.append(word)
+        return result
+
+
+class IsNull(Transformation):
+    """Indicate whether the input is None.
+
+    This Getter returns a bool indicating whether the input is nil.
+    """
+
+    name = "is_null"
+
+    def transform(self, values):
+        return [len(values) == 0]
+
+
+class Parser(object):
+    """Parse an index expression into a sequence of transformations."""
+
+    _transformations = {}
+    _word_chars = string.lowercase + string.uppercase + "._" + string.digits
+
+    def _take_word(self, partial):
+        word = ''
+        for idx, char in enumerate(partial):
+            if char not in self._word_chars:
+                return partial[:idx], partial[idx:]
+        return partial, ''
+
+    def parse(self, field):
+        inner = self._inner_parse(field)
+        return inner
+
+    def _inner_parse(self, field):
+        word, field = self._take_word(field)
+        if field.startswith("("):
+            # We have an operation
+            if not field.endswith(")"):
+                raise errors.IndexDefinitionParseError(
+                    "Invalid transformation function: %s" % field)
+            op = self._transformations.get(word, None)
+            if op is None:
+                raise errors.IndexDefinitionParseError(
+                    "Unknown operation: %s" % word)
+            inner = self._inner_parse(field[1:-1])
+            return op(inner)
+        else:
+            if len(field) != 0:
+                raise errors.IndexDefinitionParseError(
+                    "Unhandled characters: %s" % (field,))
+            if len(word) == 0:
+                raise errors.IndexDefinitionParseError(
+                    "Missing field specifier")
+            if word.endswith("."):
+                raise errors.IndexDefinitionParseError(
+                    "Invalid field specifier: %s" % word)
+            return ExtractField(word)
+
+    def parse_all(self, fields):
+        return [self.parse(field) for field in fields]
+
+    @classmethod
+    def register_transormation(cls, transform):
+        assert transform.name not in cls._transformations, (
+                "Transform %s already registered for %s"
+                % (transform.name, cls._transformations[transform.name]))
+        cls._transformations[transform.name] = transform
+
+
+Parser.register_transormation(SplitWords)
+Parser.register_transormation(Lower)
+Parser.register_transormation(IsNull)

=== modified file 'u1db/tests/__init__.py'
--- u1db/tests/__init__.py	2011-11-28 19:51:23 +0000
+++ u1db/tests/__init__.py	2011-12-06 15:24:25 +0000
@@ -107,7 +107,6 @@
 
 class DatabaseBaseTests(TestCase):
 
-    create_database = None
     scenarios = LOCAL_DATABASES_SCENARIOS
 
     def create_database(self, replica_uid):

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2011-12-01 14:46:15 +0000
+++ u1db/tests/test_backends.py	2011-12-06 15:24:25 +0000
@@ -518,6 +518,63 @@
         self.assertEqual([doc1],
             self.db.get_from_index('test-idx', [('*',)]))
 
+    def test_get_from_index_with_lower(self):
+        self.db.create_index("index", ["lower(name)"])
+        content = '{"name": "Foo"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("foo", )])
+        self.assertEqual([doc], rows)
+
+    def test_get_from_index_with_lower_matches_same_case(self):
+        self.db.create_index("index", ["lower(name)"])
+        content = '{"name": "foo"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("foo", )])
+        self.assertEqual([doc], rows)
+
+    def test_index_lower_doesnt_match_different_case(self):
+        self.db.create_index("index", ["lower(name)"])
+        content = '{"name": "Foo"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("Foo", )])
+        self.assertEqual([], rows)
+
+    def test_index_lower_doesnt_match_other_index(self):
+        self.db.create_index("index", ["lower(name)"])
+        self.db.create_index("other_index", ["name"])
+        content = '{"name": "Foo"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("Foo", )])
+        self.assertEqual(0, len(rows))
+
+    def test_index_list(self):
+        self.db.create_index("index", ["name"])
+        content = '{"name": ["foo", "bar"]}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("bar", )])
+        self.assertEqual([doc], rows)
+
+    def test_index_split_words_match_first(self):
+        self.db.create_index("index", ["split_words(name)"])
+        content = '{"name": "foo bar"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("foo", )])
+        self.assertEqual([doc], rows)
+
+    def test_index_split_words_match_second(self):
+        self.db.create_index("index", ["split_words(name)"])
+        content = '{"name": "foo bar"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("bar", )])
+        self.assertEqual([doc], rows)
+
+    def test_index_split_words_match_both(self):
+        self.db.create_index("index", ["split_words(name)"])
+        content = '{"name": "foo foo"}'
+        doc = self.db.create_doc(content)
+        rows = self.db.get_from_index("index", [("foo", )])
+        self.assertEqual([doc], rows)
+
     def test_get_partial_from_index(self):
         content1 = '{"k1": "v1", "k2": "v2"}'
         content2 = '{"k1": "v1", "k2": "x2"}'

=== modified file 'u1db/tests/test_inmemory.py'
--- u1db/tests/test_inmemory.py	2011-12-02 11:02:42 +0000
+++ u1db/tests/test_inmemory.py	2011-12-06 15:24:25 +0000
@@ -53,20 +53,20 @@
 
     def test_evaluate_json(self):
         idx = inmemory.InMemoryIndex('idx-name', ['key'])
-        self.assertEqual('value', idx.evaluate_json(simple_doc))
+        self.assertEqual(['value'], idx.evaluate_json(simple_doc))
 
     def test_evaluate_json_field_None(self):
         idx = inmemory.InMemoryIndex('idx-name', ['missing'])
-        self.assertEqual(None, idx.evaluate_json(simple_doc))
+        self.assertEqual([], idx.evaluate_json(simple_doc))
 
     def test_evaluate_json_subfield_None(self):
         idx = inmemory.InMemoryIndex('idx-name', ['key', 'missing'])
-        self.assertEqual(None, idx.evaluate_json(simple_doc))
+        self.assertEqual([], idx.evaluate_json(simple_doc))
 
     def test_evaluate_multi_index(self):
         doc = '{"key": "value", "key2": "value2"}'
         idx = inmemory.InMemoryIndex('idx-name', ['key', 'key2'])
-        self.assertEqual('value\x01value2',
+        self.assertEqual(['value\x01value2'],
                          idx.evaluate_json(doc))
 
     def test_update_ignores_None(self):
@@ -119,4 +119,3 @@
             idx._find_non_wildcards, ('a', 'b', 'c', 'd'))
         self.assertRaises(errors.InvalidValueForIndex,
             idx._find_non_wildcards, ('*', 'b', 'c'))
-

=== added file 'u1db/tests/test_query_parser.py'
--- u1db/tests/test_query_parser.py	1970-01-01 00:00:00 +0000
+++ u1db/tests/test_query_parser.py	2011-12-06 15:24:25 +0000
@@ -0,0 +1,277 @@
+# Copyright 2011 Canonical Ltd.
+#
+# This program is free software: you can redistribute it and/or modify it
+# under the terms of the GNU General Public License version 3, as published
+# by the Free Software Foundation.
+#
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranties of
+# MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
+# PURPOSE.  See the GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+from u1db import (
+    errors,
+    query_parser,
+    tests,
+    )
+
+
+trivial_raw_doc = {}
+
+class TestStaticGetter(tests.TestCase):
+
+    def test_returns_string(self):
+        getter = query_parser.StaticGetter('foo')
+        self.assertEqual(['foo'], getter.get(trivial_raw_doc))
+
+    def test_returns_int(self):
+        getter = query_parser.StaticGetter(9)
+        self.assertEqual([9], getter.get(trivial_raw_doc))
+
+    def test_returns_float(self):
+        getter = query_parser.StaticGetter(9.2)
+        self.assertEqual([9.2], getter.get(trivial_raw_doc))
+
+    def test_returns_None(self):
+        getter = query_parser.StaticGetter(None)
+        self.assertEqual([], getter.get(trivial_raw_doc))
+
+    def test_returns_list(self):
+        getter = query_parser.StaticGetter(['a', 'b'])
+        self.assertEqual(['a', 'b'], getter.get(trivial_raw_doc))
+
+
+class TestExtractField(tests.TestCase):
+
+    def assertExtractField(self, expected, field_name, raw_doc):
+        getter = query_parser.ExtractField(field_name)
+        self.assertEqual(expected, getter.get(raw_doc))
+
+    def test_get_value(self):
+        self.assertExtractField(['bar'], 'foo', {'foo': 'bar'})
+
+    def test_get_value_None(self):
+        self.assertExtractField([], 'foo', {'foo': None})
+
+    def test_get_value_missing_key(self):
+        self.assertExtractField([], 'foo', {})
+
+    def test_get_value_subfield(self):
+        self.assertExtractField(['bar'], 'foo.baz', {'foo': {'baz': 'bar'}})
+
+    def test_get_value_subfield_missing(self):
+        self.assertExtractField([], 'foo.baz', {'foo': 'bar'})
+
+    def test_get_value_dict(self):
+        self.assertExtractField([], 'foo', {'foo': {'baz': 'bar'}})
+
+    def test_get_value_list(self):
+        self.assertExtractField(['bar', 'zap'], 'foo', {'foo': ['bar', 'zap']})
+
+    def test_get_value_mixed_list(self):
+        self.assertExtractField(['bar', 'zap'], 'foo',
+            {'foo': ['bar', ['baa'], 'zap', {'bing': 9}]})
+
+    def test_get_value_list_of_dicts(self):
+        self.assertExtractField([], 'foo', {'foo': [{'zap': 'bar'}]})
+
+    def test_get_value_int(self):
+        self.assertExtractField([9], 'foo', {'foo': 9})
+
+    def test_get_value_float(self):
+        self.assertExtractField([9.2], 'foo', {'foo': 9.2})
+
+    def test_get_value_bool(self):
+        self.assertExtractField([True], 'foo', {'foo': True})
+        self.assertExtractField([False], 'foo', {'foo': False})
+
+
+class TestLower(tests.TestCase):
+
+    def assertLowerGets(self, expected, input_val):
+        getter = query_parser.Lower(query_parser.StaticGetter(input_val))
+        out_val = getter.get(trivial_raw_doc)
+        self.assertEqual(expected, out_val)
+
+    def test_inner_returns_None(self):
+        self.assertLowerGets([], None)
+
+    def test_inner_returns_string(self):
+        self.assertLowerGets(['foo'], 'fOo')
+
+    def test_inner_returns_list(self):
+        self.assertLowerGets(['foo', 'bar'], ['fOo', 'bAr'])
+
+    def test_inner_returns_int(self):
+        self.assertLowerGets([], 9)
+
+    def test_inner_returns_float(self):
+        self.assertLowerGets([], 9.0)
+
+    def test_inner_returns_bool(self):
+        self.assertLowerGets([], True)
+
+    def test_inner_returns_list_containing_int(self):
+        self.assertLowerGets(['foo', 'bar'], ['fOo', 9, 'bAr'])
+
+    def test_inner_returns_list_containing_float(self):
+        self.assertLowerGets(['foo', 'bar'], ['fOo', 9.2, 'bAr'])
+
+    def test_inner_returns_list_containing_bool(self):
+        self.assertLowerGets(['foo', 'bar'], ['fOo', True, 'bAr'])
+
+    def test_inner_returns_list_containing_list(self):
+        # TODO: Should this be unfolding the inner list?
+        self.assertLowerGets(['foo', 'bar'], ['fOo', ['bAa'], 'bAr'])
+
+    def test_inner_returns_list_containing_dict(self):
+        self.assertLowerGets(['foo', 'bar'], ['fOo', {'baa': 'xam'}, 'bAr'])
+
+
+class TestSplitWords(tests.TestCase):
+
+    def assertSplitWords(self, expected, value):
+        getter = query_parser.SplitWords(query_parser.StaticGetter(value))
+        self.assertEqual(expected, getter.get(trivial_raw_doc))
+
+    def test_inner_returns_None(self):
+        self.assertSplitWords([], None)
+
+    def test_inner_returns_string(self):
+        self.assertSplitWords(['foo', 'bar'], 'foo bar')
+
+    def test_inner_returns_list(self):
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', 'bar sux'])
+
+    def test_deduplicates(self):
+        self.assertSplitWords(['bar'], ['bar', 'bar', 'bar'])
+
+    def test_inner_returns_int(self):
+        self.assertSplitWords([], 9)
+
+    def test_inner_returns_float(self):
+        self.assertSplitWords([], 9.2)
+
+    def test_inner_returns_bool(self):
+        self.assertSplitWords([], True)
+
+    def test_inner_returns_list_containing_int(self):
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', 9, 'bar sux'])
+
+    def test_inner_returns_list_containing_float(self):
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', 9.2, 'bar sux'])
+
+    def test_inner_returns_list_containing_bool(self):
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', True, 'bar sux'])
+
+    def test_inner_returns_list_containing_list(self):
+        # TODO: Expand sub-lists?
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', ['baa'], 'bar sux'])
+
+    def test_inner_returns_list_containing_dict(self):
+        self.assertSplitWords(['foo', 'baz', 'bar', 'sux'],
+                              ['foo baz', {'baa': 'xam'}, 'bar sux'])
+
+
+class TestIsNull(tests.TestCase):
+
+    def assertIsNull(self, value):
+        getter = query_parser.IsNull(query_parser.StaticGetter(value))
+        self.assertEqual([True], getter.get(trivial_raw_doc))
+
+    def assertIsNotNull(self, value):
+        getter = query_parser.IsNull(query_parser.StaticGetter(value))
+        self.assertEqual([False], getter.get(trivial_raw_doc))
+
+    def test_inner_returns_None(self):
+        self.assertIsNull(None)
+
+    def test_inner_returns_string(self):
+        self.assertIsNotNull('foo')
+
+    def test_inner_returns_list(self):
+        self.assertIsNotNull(['foo', 'bar'])
+
+    def test_inner_returns_empty_list(self):
+        # TODO: is this the behavior we want?
+        self.assertIsNull([])
+
+    def test_inner_returns_int(self):
+        self.assertIsNotNull(9)
+
+    def test_inner_returns_float(self):
+        self.assertIsNotNull(9.2)
+
+    def test_inner_returns_bool(self):
+        self.assertIsNotNull(True)
+
+    # TODO: What about a dict? Inner is likely to return None, even though the
+    #       attribute does exist...
+
+
+class TestParser(tests.TestCase):
+
+    def parse(self, spec):
+        parser = query_parser.Parser()
+        return parser.parse(spec)
+
+    def parse_all(self, specs):
+        parser = query_parser.Parser()
+        return parser.parse_all(specs)
+
+    def assertParseError(self, definition):
+        self.assertRaises(errors.IndexDefinitionParseError, self.parse,
+                          definition)
+
+    def test_parse_empty_string(self):
+        self.assertRaises(errors.IndexDefinitionParseError, self.parse, "")
+
+    def test_parse_field(self):
+        getter = self.parse("a")
+        self.assertIsInstance(getter, query_parser.ExtractField)
+        self.assertEqual("a", getter.field)
+
+    def test_parse_dotted_field(self):
+        getter = self.parse("a.b")
+        self.assertIsInstance(getter, query_parser.ExtractField)
+        self.assertEqual("a.b", getter.field)
+
+    def test_parse_dotted_field_nothing_after_dot(self):
+        self.assertParseError("a.")
+
+    def test_parse_missing_close_on_transformation(self):
+        self.assertParseError("lower(a")
+
+    def test_parse_missing_field_in_transformation(self):
+        self.assertParseError("lower()")
+
+    def test_parse_trailing_chars(self):
+        self.assertParseError("lower(ab$)")
+
+    def test_parse_empty_op(self):
+        self.assertParseError("(ab)")
+
+    def test_parse_unknown_op(self):
+        self.assertParseError("no_such_operation(field)")
+
+    def test_parse_transformation(self):
+        getter = self.parse("lower(a)")
+        self.assertIsInstance(getter, query_parser.Lower)
+        self.assertIsInstance(getter.inner, query_parser.ExtractField)
+        self.assertEqual("a", getter.inner.field)
+
+    def test_parse_all(self):
+        getters = self.parse_all(["a", "b"])
+        self.assertEqual(2, len(getters))
+        self.assertIsInstance(getters[0], query_parser.ExtractField)
+        self.assertEqual("a", getters[0].field)
+        self.assertIsInstance(getters[1], query_parser.ExtractField)
+        self.assertEqual("b", getters[1].field)

=== modified file 'u1db/tests/test_sqlite_backend.py'
--- u1db/tests/test_sqlite_backend.py	2011-12-02 11:02:42 +0000
+++ u1db/tests/test_sqlite_backend.py	2011-12-06 15:24:25 +0000
@@ -23,6 +23,7 @@
 from u1db import (
     errors,
     tests,
+    query_parser,
     )
 from u1db.backends import sqlite_backend
 
@@ -115,6 +116,22 @@
         c.execute("SELECT * FROM conflicts")
         c.execute("SELECT * FROM index_definitions")
 
+    def test__parse_index(self):
+        self.db = sqlite_backend.SQLitePartialExpandDatabase(':memory:')
+        g = self.db._parse_index_definition('fieldname')
+        self.assertIsInstance(g, query_parser.ExtractField)
+        self.assertEqual('fieldname', g.field)
+
+    def test__update_indexes(self):
+        self.db = sqlite_backend.SQLitePartialExpandDatabase(':memory:')
+        g = self.db._parse_index_definition('fieldname')
+        c = self.db._get_sqlite_handle().cursor()
+        self.db._update_indexes('doc-id', {'fieldname': 'val'},
+                                [('fieldname', g)], c)
+        c.execute('SELECT doc_id, field_name, value FROM document_fields')
+        self.assertEqual([('doc-id', 'fieldname', 'val')],
+                         c.fetchall())
+
     def test__set_replica_uid(self):
         # Start from scratch, so that replica_uid isn't set.
         self.db = sqlite_backend.SQLitePartialExpandDatabase(':memory:')