diff options
author | Franklin Wei <me@fwei.tk> | 2018-07-09 19:07:28 -0400 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2018-07-09 19:07:28 -0400 |
commit | ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d (patch) | |
tree | 1f8bbfaae0b7c86585e35292b8b5b01d0a648e1e | |
parent | 5de9ff09f0a812e78681e8eb53b5c36844da1e58 (diff) | |
download | csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.zip csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.gz csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.bz2 csaa-ab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d.tar.xz |
Optimize IOMT leaf lookup/encloser search
We now use three separate searches, which are O(log n) time each, whereas the
OR'd together version would incur a O(n) scan of the entire leaves table.
-rw-r--r-- | iomt.c | 68 | ||||
-rw-r--r-- | iomt.h | 6 | ||||
-rw-r--r-- | sqlinit.c | 20 | ||||
-rw-r--r-- | sqlinit.txt | 5 |
4 files changed, 56 insertions, 43 deletions
@@ -347,21 +347,25 @@ struct iomt_node iomt_find_encloser(const struct iomt *tree, uint64_t idx, uint6 } else { - sqlite3_stmt *st = tree->db.findencloser; - reset_and_bind(tree, st); + /* try all three cases */ + for(int i = 0; i < 3; ++i) + { + sqlite3_stmt *st = tree->db.findencloser[i]; + reset_and_bind(tree, st); - sqlite3_bind_int64(st, 3, idx); + sqlite3_bind_int64(st, 3, idx); - if(sqlite3_step(st) == SQLITE_ROW) - { - if(leafidx) + if(sqlite3_step(st) == SQLITE_ROW) + { + if(leafidx) *leafidx = sqlite3_column_int64(st, 0); - struct iomt_node ret; - ret.idx = sqlite3_column_int64(st, 1); - ret.next_idx = sqlite3_column_int64(st, 2); - memcpy(&ret.val, sqlite3_column_blob(st, 3), sizeof(ret.val)); + struct iomt_node ret; + ret.idx = sqlite3_column_int64(st, 1); + ret.next_idx = sqlite3_column_int64(st, 2); + memcpy(&ret.val, sqlite3_column_blob(st, 3), sizeof(ret.val)); - return ret; + return ret; + } } return node_null; } @@ -385,22 +389,14 @@ struct iomt_node iomt_find_leaf_or_encloser(const struct iomt *tree, uint64_t id } else { - sqlite3_stmt *st = tree->db.findleaf_or_encloser; - reset_and_bind(tree, st); + struct iomt_node leaf = iomt_find_leaf(tree, idx, leafidx); + if(leaf.idx != 0) + return leaf; - sqlite3_bind_int64(st, 3, idx); - - if(sqlite3_step(st) == SQLITE_ROW) - { - if(leafidx) - *leafidx = sqlite3_column_int64(st, 0); - struct iomt_node ret; - ret.idx = sqlite3_column_int64(st, 1); - ret.next_idx = sqlite3_column_int64(st, 2); - memcpy(&ret.val, sqlite3_column_blob(st, 3), sizeof(ret.val)); + leaf = iomt_find_encloser(tree, idx, leafidx); + if(leaf.idx != 0) + return leaf; - return ret; - } return node_null; } } @@ -604,16 +600,23 @@ struct iomt *iomt_new_from_db(void *db, and_clauses); sqlite3_prepare_v2(db, sql, -1, &tree->db.findleaf, 0); - /* These both need table scans. FIXME */ - sprintf(sql, "SELECT LeafIdx, Idx, NextIdx, Val FROM %s WHERE ( ( Idx < ?3 AND ?3 < NextIdx ) OR ( NextIdx < Idx AND Idx < ?3 ) OR ( ?3 < NextIdx AND NextIdx < Idx ) )%s;", + /* These should all be O(log n) searches, not linear-time + * scans. We separate them since SQLite can't seem to handle them + * efficiently when OR'd together. */ + sprintf(sql, "SELECT LeafIdx, Idx, NextIdx, Val FROM %s WHERE (Idx < ?3 AND ?3 < NextIdx)%s;", + tree->db.leaves_table, + and_clauses); + sqlite3_prepare_v2(db, sql, -1, &tree->db.findencloser[0], 0); + + sprintf(sql, "SELECT LeafIdx, Idx, NextIdx, Val FROM %s WHERE ( NextIdx < Idx AND Idx < ?3 )%s;", tree->db.leaves_table, and_clauses); - sqlite3_prepare_v2(db, sql, -1, &tree->db.findencloser, 0); + sqlite3_prepare_v2(db, sql, -1, &tree->db.findencloser[1], 0); - sprintf(sql, "SELECT LeafIdx, Idx, NextIdx, Val FROM %s WHERE ( ( Idx < ?3 AND ?3 < NextIdx ) OR ( NextIdx < Idx AND Idx < ?3 ) OR ( ?3 < NextIdx AND NextIdx < Idx ) OR ( Idx = ?3 ) )%s;", + sprintf(sql, "SELECT LeafIdx, Idx, NextIdx, Val FROM %s WHERE ( ?3 < NextIdx AND NextIdx < Idx )%s;", tree->db.leaves_table, and_clauses); - sqlite3_prepare_v2(db, sql, -1, &tree->db.findleaf_or_encloser, 0); + sqlite3_prepare_v2(db, sql, -1, &tree->db.findencloser[2], 0); return tree; } @@ -837,8 +840,9 @@ void iomt_free(struct iomt *tree) sqlite3_finalize(tree->db.updateleaf); sqlite3_finalize(tree->db.insertleaf); sqlite3_finalize(tree->db.findleaf); - sqlite3_finalize(tree->db.findencloser); - sqlite3_finalize(tree->db.findleaf_or_encloser); + + for(int i = 0; i < 3; ++i) + sqlite3_finalize(tree->db.findencloser[i]); } free(tree); } @@ -41,7 +41,11 @@ struct iomt { sqlite3_stmt *getnode, *updatenode, *insertnode; sqlite3_stmt *getleaf, *updateleaf, *insertleaf; - sqlite3_stmt *findleaf, *findencloser, *findleaf_or_encloser; + sqlite3_stmt *findleaf; + sqlite3_stmt *findencloser[3]; /* 3 cases, OR'd together + * (we run them + * individually so they're + * O(logn) each */ } db; struct { hash_t *mt_nodes; /* this has 2 * mt_leafcount - 1 elements. Note @@ -205,12 +205,16 @@ unsigned char sqlinit_txt[] = { 0x65, 0x73, 0x28, 0x49, 0x64, 0x78, 0x2c, 0x20, 0x4e, 0x65, 0x78, 0x74, 0x49, 0x64, 0x78, 0x29, 0x3b, 0x0a, 0x43, 0x52, 0x45, 0x41, 0x54, 0x45, 0x20, 0x49, 0x4e, 0x44, 0x45, 0x58, 0x20, 0x49, 0x64, 0x78, 0x33, 0x20, - 0x4f, 0x4e, 0x20, 0x41, 0x43, 0x4c, 0x4c, 0x65, 0x61, 0x76, 0x65, 0x73, - 0x28, 0x46, 0x69, 0x6c, 0x65, 0x49, 0x64, 0x78, 0x2c, 0x20, 0x4c, 0x65, - 0x61, 0x66, 0x49, 0x64, 0x78, 0x29, 0x3b, 0x0a, 0x43, 0x52, 0x45, 0x41, - 0x54, 0x45, 0x20, 0x49, 0x4e, 0x44, 0x45, 0x58, 0x20, 0x49, 0x64, 0x78, - 0x34, 0x20, 0x4f, 0x4e, 0x20, 0x41, 0x43, 0x4c, 0x4e, 0x6f, 0x64, 0x65, - 0x73, 0x28, 0x46, 0x69, 0x6c, 0x65, 0x49, 0x64, 0x78, 0x2c, 0x20, 0x4e, - 0x6f, 0x64, 0x65, 0x49, 0x64, 0x78, 0x29, 0x3b, 0x0a, 0x00 + 0x4f, 0x4e, 0x20, 0x46, 0x69, 0x6c, 0x65, 0x4c, 0x65, 0x61, 0x76, 0x65, + 0x73, 0x28, 0x4e, 0x65, 0x78, 0x74, 0x49, 0x64, 0x78, 0x29, 0x3b, 0x0a, + 0x43, 0x52, 0x45, 0x41, 0x54, 0x45, 0x20, 0x49, 0x4e, 0x44, 0x45, 0x58, + 0x20, 0x49, 0x64, 0x78, 0x34, 0x20, 0x4f, 0x4e, 0x20, 0x41, 0x43, 0x4c, + 0x4c, 0x65, 0x61, 0x76, 0x65, 0x73, 0x28, 0x46, 0x69, 0x6c, 0x65, 0x49, + 0x64, 0x78, 0x2c, 0x20, 0x4c, 0x65, 0x61, 0x66, 0x49, 0x64, 0x78, 0x29, + 0x3b, 0x0a, 0x43, 0x52, 0x45, 0x41, 0x54, 0x45, 0x20, 0x49, 0x4e, 0x44, + 0x45, 0x58, 0x20, 0x49, 0x64, 0x78, 0x35, 0x20, 0x4f, 0x4e, 0x20, 0x41, + 0x43, 0x4c, 0x4e, 0x6f, 0x64, 0x65, 0x73, 0x28, 0x46, 0x69, 0x6c, 0x65, + 0x49, 0x64, 0x78, 0x2c, 0x20, 0x4e, 0x6f, 0x64, 0x65, 0x49, 0x64, 0x78, + 0x29, 0x3b, 0x0a, 0x00 }; -unsigned int sqlinit_txt_len = 2553; +unsigned int sqlinit_txt_len = 2595; diff --git a/sqlinit.txt b/sqlinit.txt index b8e34ec..484d49d 100644 --- a/sqlinit.txt +++ b/sqlinit.txt @@ -109,5 +109,6 @@ FOREIGN KEY (Version) REFERENCES Versions(Version) CREATE INDEX Idx1 ON Versions(FileIdx, Version); CREATE INDEX Idx2 ON FileLeaves(Idx, NextIdx); -CREATE INDEX Idx3 ON ACLLeaves(FileIdx, LeafIdx); -CREATE INDEX Idx4 ON ACLNodes(FileIdx, NodeIdx); +CREATE INDEX Idx3 ON FileLeaves(NextIdx); +CREATE INDEX Idx4 ON ACLLeaves(FileIdx, LeafIdx); +CREATE INDEX Idx5 ON ACLNodes(FileIdx, NodeIdx); |