aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranklin Wei <me@fwei.tk>2018-07-09 19:07:28 -0400
committerFranklin Wei <me@fwei.tk>2018-07-09 19:07:28 -0400
commitab8d3d75ce0dbd2b328b0b40dcb4d1e5f9dc862d (patch)
tree1f8bbfaae0b7c86585e35292b8b5b01d0a648e1e
parent5de9ff09f0a812e78681e8eb53b5c36844da1e58 (diff)
downloadcsaa-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.c68
-rw-r--r--iomt.h6
-rw-r--r--sqlinit.c20
-rw-r--r--sqlinit.txt5
4 files changed, 56 insertions, 43 deletions
diff --git a/iomt.c b/iomt.c
index fca951e..0406994 100644
--- a/iomt.c
+++ b/iomt.c
@@ -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);
}
diff --git a/iomt.h b/iomt.h
index 1c0c0f7..723ce6c 100644
--- a/iomt.h
+++ b/iomt.h
@@ -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
diff --git a/sqlinit.c b/sqlinit.c
index 2bb269a..7a21419 100644
--- a/sqlinit.c
+++ b/sqlinit.c
@@ -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);