Repository navigation
Investigate possibility of replacing SQLite with RocksDB #306
Description
Activity
Splitting up the indexing into two places sounds like it would be a good idea. Only concern might be consistency i.e. only one of the indexes is populated but not the other. We should also use column families so that they can be written to independently better and partitioned.
Another concern I have is that with this approach, we can't easily find "all paths that belong to a single file" because theres one mapping between file and symbol stacks, and the other is symbol stack to file path, so it would need more than one query.
With this proposal, the following mapping would make sense I believe:
f:${file_path} -> <serialized bincode array containing symbol stacks> s:${symbol_stack} -> string pathAre symbol stacks guaranteed to be unique? If so, how does it deal with duplicate files?
With regards to dropping in-memory and neutral naming, key-value being simpler gives us the benefit of being able to create abstractions more easily. I propose we design everything with RocksDB first, then once the implementation has settled, we create a
DBtrait with a small set of functions (ideally 4-5) that provide the same functionality and use that instead.Collecting the current database schema and queries here so we have a compact overview of the access patterns we'd need to support (leaving out strict and not null requirements for now).
Schema
TABLE graphs( file TEXT PRIMARY KEY, tag TEXT, error TEXT, value BLOB ); TABLE file_paths( file TEXT, local_id INTEGER, value BLOB, FOREIGN KEY(file) REFERENCES graphs(file) ); TABLE root_paths( file TEXT, symbol_stack TEXT, value BLOB NOT NULL, FOREIGN KEY(file) REFERENCES graphs(file) );Notes:
graphsis the only table with a unique key per row:filefile_pathsdoes not have a unique key per row, but in blob storage we might key on(file, local_id)and store a list of paths.root_pathsis the crux, because of the access patterns below. It contains paths from the same file with different symbol keys, and paths with the same symbol key from different files.
Queries
-
Delete all data for a file:
DELETE FROM file_paths WHERE file=? DELETE FROM root_paths WHERE file=? DELETE FROM graphs WHERE file=?This is called once per file that is indexed.
-
Delete all data for files that are inside a directory:
DELETE FROM file_paths WHERE path_descendant_of(file, ?) DELETE FROM root_paths WHERE path_descendant_of(file, ?) DELETE FROM graphs WHERE path_descendant_of(file, ?)This is called once per
cleancommands. -
Store data for a file:
INSERT INTO graphs (file, tag, error, value) VALUES (?, ?, ?, ?) INSERT INTO file_paths (file, local_id, value) VALUES (?, ?, ?) INSERT INTO root_paths (file, symbol_stack, value) VALUES (?, ?, ?)Called once per indexed file.
-
List files that are inside a directory:
SELECT file, tag, error FROM graphs WHERE path_descendant_of(file, ?)Called once per
statuscommand. -
Load graph data for a file
SELECT value FROM graphs WHERE file = ?Called many times during path stitching
-
Load paths for a file node
SELECT file,value from file_paths WHERE file = ? AND local_id = ?Called many times during path stitching.
-
Load paths for root node
SELECT file, value from root_paths WHERE symbol_stack = ?Called many times during path stitching.
So, in terms of performance, the last three queries are the once to focus on.
From having a look at your schema:
stack-graphs/stack-graphs/src/storage.rs
Lines 37 to 59 in ee490e9
It seems like you don't have indexes on the things you're SELECTing, with the exception of
graphs.file, which has an index because it's a primary key. Based on the statements you listed as important you could add:CREATE INDEX file_paths_file_local_id ON file_paths(file, local_id); CREATE INDEX root_paths_symbol_stack ON root_paths(symbol_stack);
If the data that you're fetching is in the index then SQLite won't even bother reading the row proper, so instead of the above some even better indexes would be:
CREATE INDEX graph_file_value ON graph(file, value); CREATE INDEX file_paths_file_local_id_value ON file_paths(file, local_id, value); CREATE INDEX root_paths_symbol_stack_file_value ON root_paths(symbol_stack, file, value);
If you use
CREATE INDEX IF NOT EXISTSthen the whole thing is idempotent, so could be run every time you open the database.- added a commit that references this issue
on Aug 7, 2023 - added a commit that references this issue
on Aug 7, 2023 awesome, i noticed the same thing when refactoring the database. wonder what the performance will be like after this gets merged.
- added a commit that references this issue
on Aug 7, 2023 @bluskript I just merged #308, would love to hear if this improves anything for you.
Closing this now that SQLite performance has been improved.
The current file based storage implementation is based on
rusqlite. It seems to be rather slow in practice, and we don't really depend on the SQL features. @bluskript suggested to replace it with something else like RocksDB #302. I think this is worth investigating and making the change if it improves performance.Similar to the binary encoding we use, the database itself should be mature, have a stable storage format, and perform well. These are explicit goals of the RocksDB project, making it a good candidate.
Changes
I imagine the following changes to be part of this transition:
One of the main challenges will be maintaining the index of file paths from the root node. The paths coming from root are indexed by partial symbol stacks, and originate from multiple files. Therefore, it should be possible to add paths belonging to a particular file to this shared index, but also to remove the paths from a particular files from the index, while keeping the rest.
See if we can exploit RocksDB's range based indexing to efficiently load/remove data from the database (e.g., all paths belong to a single file). This will require careful key design.
Drop the support for having an in-memory database. RocksDB doesn't support this, and once Allow path stitcher to work on
SQLiteReader#291 is merged, switching between a database and in-memory data structures should have little impact on code.Find more neutral naming for the storage classes. Currently, they explicitly mention
SQL, but we should use something to suggest disk, file-based, or persistent storage, without exposing the implementation.