Merge lp:~thisfred/u1db/fix-get_keys_from_index into lp:u1db

[Eric Casteleijn]

get_keys_from_index now returns simple values for single column indexes, and tuples for multicolumn ones

get_keys_from_index now returns simple values for single column indexes, and tuples for multicolumn ones

Not ecstatic about the C implementation, so suggestions for improvement welcome.

[John A Meinel (jameinel)]

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

On 6/9/2012 1:11 AM, Eric Casteleijn wrote:
> Eric Casteleijn has proposed merging
> lp:~thisfred/u1db/fix-get_keys_from_index into lp:u1db.
>
> Requested reviews: Ubuntu One hackers (ubuntuone-hackers) Related
> bugs: Bug #1009505 in U1DB: "get_keys_from_index is useless for
> multicolumn indexes" https://bugs.launchpad.net/u1db/+bug/1009505
>
> For more details, see:
> https://code.launchpad.net/~thisfred/u1db/fix-get_keys_from_index/+merge/109451
>
> get_keys_from_index now returns simple values for single column
> indexes, and tuples for multicolumn ones
>
> Not ecstatic about the C implementation, so suggestions for
> improvement welcome.

I don't think we should change the type of the return based on the
index. If we need to return tuples than we should always do so. I'm
willing to be convinced otherwise, but this *strongly* feels like you
should have 2 apis if you want to have 2 different return signatures.

John
=:->

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

iEYEARECAAYFAk/VnhoACgkQJdeBCYSNAAPT0ACgrYlYY/fokYHlASC27ecQIXjD
ZqgAoLQ5dIy83PMoq9nYPxnjvnlPxtA8
=i/Oc
-----END PGP SIGNATURE-----

[lp:~thisfred/u1db/fix-get_keys_from_index]

328. By Eric Casteleijn on 2012-06-11

do not unpack single tuples, no matter how tempting

[Eric Casteleijn (thisfred)]

thanks, jam. fixed.

[John A Meinel (jameinel)]

So if I understand the C code correctly, you do a callback for each bit of the key, and then follow it up with a NULL for each run. So if you had a 3 column index (firstname, lastname, irc_nick), then the callback would give you:

 Eric
 Castelijn
 thisfred
 NULL
 John
 Meinel
 jam
 NULL
...

While this is functional, I really think the users would be better served getting:

 Eric, Castelijn, thisfred
 John, Meinel, jam
 ...

Since the C code is now doing the query that way anyway (it is doing the join of document_fields onto itself), I think we should probably just allocate an array to pass the data into the callback.

I would probably do it with const char * stuff. So that we share pointers with the sqlite code, and the callback needs to allocate memory if it wants to hold on to anything (vs allocating the memory, and the callback must free everything/save it into a buffer for later.)

So something like:

typedef int(*u1db_keys_callback)(void *context, int num_fields, const char **key)

and then in the function

int
u1db_get_index_keys(db, index_name, context, cb)
{
...

  char **key = NULL;
...

  key = (char**)calloc(num_fields, sizeof(char*));
...
  finally:
    if (key != NULL) {
      free(key)
    }

And then the inner loop becomes:

    while (status == SQLITE_ROW) {
        for (i = 0; i < num_fields; ++i) {
          field = (char*)sqlite3_column_text(statement, i);
          key[i] = field;
      }
      if ((status = cb(context, num_fields, key)) != U1DB_OK) {
          goto finish;
      }
      status = sqlite3_step(statement);
    }

Note that I'm intentionally calling the whole tuple a singular 'key' made up of 'fields'.

[lp:~thisfred/u1db/fix-get_keys_from_index]

329. By Eric Casteleijn on 2012-06-12

changed callback signature

[Eric Casteleijn (thisfred)]

Fixed, thanks!

[Eric Casteleijn (thisfred)]

now to fix the conflicts :)

[Eric Casteleijn (thisfred)]

resolved

[lp:~thisfred/u1db/fix-get_keys_from_index]

330. By Eric Casteleijn on 2012-06-12

merged trunk, resolved conflicts, removed unnecessary intermediate variable

331. By Eric Casteleijn on 2012-06-12

rereresolved conflicts

[John A Meinel (jameinel)]

+ key[i] = (char*)sqlite3_column_text(statement, i);

I think this line we probably want
key[i] = (const char*)...

are you getting a warning about const changing? (I know we need the cast at all because sqlite3 returns an unsigned char*).

You are mixing styles here:

167 + if (key != NULL)
168 + free(key);
169 + if (query_str != NULL) {
170 + free(query_str);
171 + }

Personally, I'm a fan of always using {} and putting it at the end of line like you did for query_str.

366 + a_list.append(field_list)

^ I think you want a tuple(field_list) here.

You are using "GROUP BY" in the query, which was useful when you were counting. I wonder if we would rather use "SELECT DISTINCT" rather than "SELECT ... GROUP BY". Probably best would be to try both and see if one is significantly faster. (SQL means that they could be identical internally).

Overall, I think it looks good, though.

review: Approve

[lp:~thisfred/u1db/fix-get_keys_from_index]

332. By Eric Casteleijn on 2012-06-13

added missing const, cosmetic fix

[Eric Casteleijn (thisfred)]

Thanks!

> + key[i] = (char*)sqlite3_column_text(statement, i);
>
> I think this line we probably want
> key[i] = (const char*)...

fixed

> are you getting a warning about const changing? (I know we need the cast at
> all because sqlite3 returns an unsigned char*).

There was no warning.

> You are mixing styles here:
>
> 167 + if (key != NULL)
> 168 + free(key);
> 169 + if (query_str != NULL) {
> 170 + free(query_str);
> 171 + }

Fixed.

> 366 + a_list.append(field_list)
>
> ^ I think you want a tuple(field_list) here.

The tuple cast was done later, but you're right, it's better to do it here and not iterate over the list later. Fixed.

> You are using "GROUP BY" in the query, which was useful when you were
> counting. I wonder if we would rather use "SELECT DISTINCT" rather than
> "SELECT ... GROUP BY". Probably best would be to try both and see if one is
> significantly faster. (SQL means that they could be identical internally).

I will test this, and fix it on a separate branch if necessary.

[lp:~thisfred/u1db/fix-get_keys_from_index]

333. By Eric Casteleijn on 2012-06-13

various small fixes

=== modified file 'include/u1db/u1db.h'
--- include/u1db/u1db.h	2012-06-12 15:17:40 +0000
+++ include/u1db/u1db.h	2012-06-13 11:19:23 +0000
@@ -40,7 +40,8 @@
 
 typedef struct _u1query u1query;
 typedef int (*u1db_doc_callback)(void *context, u1db_document *doc);
-typedef int (*u1db_key_callback)(void *context, const char *key);
+typedef int (*u1db_key_callback)(void *context, int num_fields,
+                                 const char **key);
 typedef int (*u1db_doc_gen_callback)(void *context, u1db_document *doc, int gen);
 typedef int (*u1db_doc_id_gen_callback)(void *context, const char *doc_id, int gen);
 typedef int (*u1db_trans_info_callback)(void *context, const char *doc_id,
@@ -352,7 +353,8 @@
  * Get keys under which documents are indexed.
  *
  * @param index_name Name of the index for which to get keys.
- * @param context Will be returned via the document callback
+ * @param context Will be returned via the document callback. cb will be called
+ *     once for each column, with a NULL value to separate rows.
  */
 int u1db_get_index_keys(u1database *db, char *index_name, void *context,
                         u1db_key_callback cb);

=== modified file 'include/u1db/u1db_internal.h'
--- include/u1db/u1db_internal.h	2012-06-12 15:17:40 +0000
+++ include/u1db/u1db_internal.h	2012-06-13 11:19:23 +0000
@@ -368,6 +368,16 @@
                              int *start_wildcard, int *end_wildcard);
 
 /**
+ * Format an index keys query
+ *
+ * @param n_fields  The number of fields being passed in, (the number of args
+ *     in argp)
+ * @param buf (OUT) The character array. This will be dynamically allocated,
+ *     and callers must free() it.
+ */
+int u1db__format_index_keys_query(int n_fields, char **buf);
+
+/**
  * Given this document content, update the indexed fields in the db.
  */
 int u1db__update_indexes(u1database *db, const char *doc_id,

=== modified file 'src/u1db_query.c'
--- src/u1db_query.c	2012-06-12 15:17:40 +0000
+++ src/u1db_query.c	2012-06-13 11:19:23 +0000
@@ -40,7 +40,6 @@
     int value_type;
 } operation;
 
-
 typedef struct string_list_item_
 {
     char *data;
@@ -78,7 +77,8 @@
 } transformation;
 
 typedef int(*op_function)(string_list *, const string_list *,
-                        const string_list *);
+                          const string_list *);
+
 
 static int
 init_list(string_list **list)
@@ -749,14 +749,21 @@
                     void *context, u1db_key_callback cb)
 {
     int status = U1DB_OK;
-    char *key = NULL;
+    int num_fields = 0;
+    int bind_arg, i;
+    const char **key = NULL;
+    string_list *field_names = NULL;
+    string_list_item *field_name = NULL;
+    char *query_str = NULL;
     sqlite3_stmt *statement;
+
+    status = init_list(&field_names);
+    if (status != U1DB_OK)
+        goto finish;
     status = sqlite3_prepare_v2(
         db->sql_handle,
-        "SELECT document_fields.value FROM "
-        "index_definitions INNER JOIN document_fields ON "
-        "index_definitions.field = document_fields.field_name WHERE "
-        "index_definitions.name = ? GROUP BY document_fields.value;",
+        "SELECT field FROM index_definitions WHERE name = ? ORDER BY "
+        "offset;",
         -1, &statement, NULL);
     if (status != SQLITE_OK) {
         goto finish;
@@ -768,37 +775,64 @@
     }
     status = sqlite3_step(statement);
     if (status == SQLITE_DONE) {
-        sqlite3_finalize(statement);
-        status = sqlite3_prepare_v2(
-            db->sql_handle,
-            "SELECT field FROM index_definitions WHERE name = ?;",
-            -1, &statement, NULL);
-        if (status != SQLITE_OK) {
+        status = U1DB_INDEX_DOES_NOT_EXIST;
+        goto finish;
+    }
+    while (status == SQLITE_ROW) {
+        num_fields++;
+        status = append(field_names, (char*)sqlite3_column_text(statement, 0));
+        if (status != U1DB_OK)
             goto finish;
-        }
+        status = sqlite3_step(statement);
+    }
+    if (status != SQLITE_DONE) {
+        goto finish;
+    }
+    sqlite3_finalize(statement);
+    status = u1db__format_index_keys_query(num_fields, &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_arg = 1;
+    for (field_name = field_names->head; field_name != NULL; field_name =
+             field_name->next) {
         status = sqlite3_bind_text(
-            statement, 1, index_name, -1, SQLITE_TRANSIENT);
-        if (status != SQLITE_OK) {
+            statement, bind_arg++, field_name->data, -1, SQLITE_TRANSIENT);
+        if (status != SQLITE_OK)
             goto finish;
-        }
-        status = sqlite3_step(statement);
-        if (status == SQLITE_DONE) {
-            status = U1DB_INDEX_DOES_NOT_EXIST;
-        } else {
-            status = U1DB_OK;
-        }
+    }
+    status = sqlite3_step(statement);
+    key = (const char**)calloc(num_fields, sizeof(char*));
+    if (key == NULL) {
+        status = U1DB_NOMEM;
         goto finish;
     }
     while (status == SQLITE_ROW) {
-        key = (char*)sqlite3_column_text(statement, 0);
-        if ((status = cb(context, key)) != U1DB_OK)
+        for (i = 0; i < num_fields; ++i) {
+            key[i]  = (const char*)sqlite3_column_text(statement, i);
+        }
+        if ((status = cb(context, num_fields, key)) != U1DB_OK) {
             goto finish;
+        }
         status = sqlite3_step(statement);
     }
     if (status == SQLITE_DONE) {
         status = U1DB_OK;
     }
 finish:
+    if (key != NULL) {
+        free(key);
+    }
+    if (query_str != NULL) {
+        free(query_str);
+    }
+    destroy_list(field_names);
     sqlite3_finalize(statement);
     return status;
 }
@@ -1007,6 +1041,62 @@
     return status;
 }
 
+int
+u1db__format_index_keys_query(int n_fields, char **buf)
+{
+    int status = U1DB_OK;
+    int buf_size, i;
+    char *cur = 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 ");
+    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);
+    }
+    add_to_buf(&cur, &buf_size, " FROM ");
+    for (i = 0; i < n_fields; ++i) {
+        if (i != 0) {
+            add_to_buf(&cur, &buf_size, ", ");
+        }
+        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);
+        }
+        add_to_buf(&cur, &buf_size, " AND d%d.value NOT NULL", i);
+    }
+    add_to_buf(&cur, &buf_size, " GROUP 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);
+    }
+    if (status != U1DB_OK && *buf != NULL) {
+        free(*buf);
+        *buf = NULL;
+    }
+    return status;
+}
+
 struct sqlcb_to_field_cb {
     void *user_context;
     int (*user_cb)(void *, const char*, transformation *tr);

=== modified file 'u1db/__init__.py'
--- u1db/__init__.py	2012-06-12 15:17:40 +0000
+++ u1db/__init__.py	2012-06-13 11:19:23 +0000
@@ -222,8 +222,7 @@
     def get_index_keys(self, index_name):
         """Return all keys under which documents are indexed in this index.
 
-        :return: [(key, frequency)] A list of indexed keys and the frequency
-            they occur.
+        :return: [] A list of tuples of indexed keys.
         :param index_name: The index to query
         """
         raise NotImplementedError(self.get_index_keys)

=== modified file 'u1db/backends/inmemory.py'
--- u1db/backends/inmemory.py	2012-06-05 21:17:09 +0000
+++ u1db/backends/inmemory.py	2012-06-13 11:19:23 +0000
@@ -250,7 +250,9 @@
             index = self._indexes[index_name]
         except KeyError:
             raise errors.IndexDoesNotExist
-        return list(set(index.keys()))
+        keys = index.keys()
+        # XXX inefficiency warning
+        return list(set([tuple(key.split('\x01')) for key in keys]))
 
     def whats_changed(self, old_generation=0):
         changes = []

=== modified file 'u1db/backends/sqlite_backend.py'
--- u1db/backends/sqlite_backend.py	2012-06-06 17:08:22 +0000
+++ u1db/backends/sqlite_backend.py	2012-06-13 11:19:23 +0000
@@ -34,12 +34,6 @@
     vectorclock,
     )
 
-SQL_INDEX_KEYS = """
-    SELECT document_fields.value FROM index_definitions INNER JOIN
-    document_fields ON field = field_name WHERE index_definitions.name = ?
-    GROUP BY document_fields.value;
-    """
-
 
 class SQLiteDatabase(CommonBackend):
     """A U1DB implementation that uses SQLite as its persistence layer."""
@@ -734,18 +728,28 @@
         res = c.fetchall()
         return [self._factory(r[0], r[1], r[2]) for r in res]
 
-    def get_index_keys(self, index):
+    def get_index_keys(self, index_name):
         c = self._db_handle.cursor()
+        definition = self._get_index_definition(index_name)
+        value_fields = ', '.join([
+            'd%d.value' % i for i in range(len(definition))])
+        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))]
+        where = [
+            novalue_where[i] + (" AND d%d.value NOT NULL" % (i,)) for i in
+            range(len(definition))]
+        statement = (
+            "SELECT %s FROM document d, %s WHERE %s GROUP BY %s;" % (
+                value_fields, ', '.join(tables), ' AND '.join(where),
+                value_fields))
         try:
-            c.execute(SQL_INDEX_KEYS, (index,))
+            c.execute(statement, tuple(definition))
         except dbapi2.OperationalError, e:
             raise dbapi2.OperationalError(str(e) +
-                '\nstatement: %s\nargs: %s\n' % (SQL_INDEX_KEYS, (index,)))
-        res = c.fetchall()
-        if not res:
-            # raise IndexDoesNotExist if appropriate
-            self._get_index_definition(index)
-        return [r[0] for r in res]
+                '\nstatement: %s\nargs: %s\n' % (statement, tuple(definition)))
+        return c.fetchall()
 
     def delete_index(self, index_name):
         with self._db_handle:

=== modified file 'u1db/commandline/client.py'
--- u1db/commandline/client.py	2012-06-06 13:28:10 +0000
+++ u1db/commandline/client.py	2012-06-13 11:19:23 +0000
@@ -401,8 +401,9 @@
     def run(self, database, index):
         try:
             db = self._open(database, create=False)
-            for i in db.get_index_keys(index):
-                self.stdout.write("%s\n" % (i.encode('utf-8'),))
+            for key in db.get_index_keys(index):
+                self.stdout.write("%s\n" % (", ".join(
+                    [i.encode('utf-8') for i in key],)))
         except errors.DatabaseDoesNotExist:
             self.stderr.write("Database does not exist.\n")
         except errors.IndexDoesNotExist:

=== modified file 'u1db/tests/c_backend_wrapper.pyx'
--- u1db/tests/c_backend_wrapper.pyx	2012-06-12 15:17:40 +0000
+++ u1db/tests/c_backend_wrapper.pyx	2012-06-13 11:19:23 +0000
@@ -58,7 +58,8 @@
 
     ctypedef char* const_char_ptr "const char*"
     ctypedef int (*u1db_doc_callback)(void *context, u1db_document *doc)
-    ctypedef int (*u1db_key_callback)(void *context, char *key)
+    ctypedef int (*u1db_key_callback)(void *context, int num_fields,
+                                      const_char_ptr *key)
     ctypedef int (*u1db_doc_gen_callback)(void *context,
         u1db_document *doc, int gen)
     ctypedef int (*u1db_trans_info_callback)(void *context,
@@ -283,9 +284,14 @@
     a_list.append(pydoc)
     return 0
 
-cdef int _append_key_to_list(void *context, const_char_ptr key) with gil:
-    a_list = <object>context
-    a_list.append(key)
+cdef int _append_key_to_list(void *context, int num_fields,
+                             const_char_ptr *key) with gil:
+    a_list = <object>(context)
+    field_list = []
+    for i from 0 <= i < num_fields:
+        field = key[i]
+        field_list.append(field.decode('utf-8'))
+    a_list.append(tuple(field_list))
     return 0
 
 cdef _list_to_array(lst, const_char_ptr **res, int *count):
@@ -1190,12 +1196,12 @@
 
     def get_index_keys(self, index_name):
         cdef int status
-        result = []
+        keys = []
         status = U1DB_OK
         status = u1db_get_index_keys(
-            self._db, index_name, <void*>result, _append_key_to_list)
+            self._db, index_name, <void*>keys, _append_key_to_list)
         handle_status("get_index_keys", status)
-        return result
+        return keys
 
     def _query_init(self, index_name):
         cdef CQuery query

=== modified file 'u1db/tests/test_backends.py'
--- u1db/tests/test_backends.py	2012-06-06 16:59:22 +0000
+++ u1db/tests/test_backends.py	2012-06-13 11:19:23 +0000
@@ -1300,7 +1300,23 @@
         self.db.create_doc(content2)
         self.db.create_doc(content3)
         self.assertEqual(
-            ['value1', 'value2'],
+            [('value1',), ('value2',)],
+            sorted(self.db.get_index_keys('test-idx')))
+
+    def test_get_index_keys_from_multicolumn_index(self):
+        self.db.create_index('test-idx', 'key1', 'key2')
+        content1 = '{"key1": "value1", "key2": "val2-1"}'
+        content2 = '{"key1": "value2", "key2": "val2-2"}'
+        content3 = '{"key1": "value2", "key2": "val2-2"}'
+        content4 = '{"key1": "value2", "key2": "val3"}'
+        self.db.create_doc(content1)
+        self.db.create_doc(content2)
+        self.db.create_doc(content3)
+        self.db.create_doc(content4)
+        self.assertEqual([
+            ('value1', 'val2-1'),
+            ('value2', 'val2-2'),
+            ('value2', 'val3')],
             sorted(self.db.get_index_keys('test-idx')))
 
 

=== modified file 'u1db/tests/test_c_backend.py'
--- u1db/tests/test_c_backend.py	2012-06-12 13:03:18 +0000
+++ u1db/tests/test_c_backend.py	2012-06-13 11:19:23 +0000
@@ -199,7 +199,7 @@
         self.db.create_doc(tests.simple_doc)
         self.db.create_index("key-idx", "key")
         keys = self.db.get_index_keys('key-idx')
-        self.assertEqual(["value"], keys)
+        self.assertEqual([("value",)], keys)
 
     def test__query_init_one_field(self):
         self.db = c_backend_wrapper.CDatabase(':memory:')

=== modified file 'u1todo/u1todo.py'
--- u1todo/u1todo.py	2012-05-31 18:51:20 +0000
+++ u1todo/u1todo.py	2012-06-13 11:19:23 +0000
@@ -78,7 +78,7 @@
 
     def get_all_tags(self):
         """Get all tags in use in the entire database."""
-        return self.db.get_index_keys(TAGS_INDEX)
+        return [key[0] for key in self.db.get_index_keys(TAGS_INDEX)]
 
     def get_tasks_by_tags(self, tags):
         """Get all tasks that have every tag in tags."""