8 ms·

For context, SQLite4 explored reimplementing SQLite using a key-value store on log-structured merge trees, like RocksDB and Cassandra. I'd be interested to hea

For context, SQLite4 explored reimplementing SQLite using a key-value store on log-structured merge trees, like RocksDB and Cassandra. I'd be interested to hear why they stopped. Presumably reimplementing SQL on a KV store was seen as not worth it, when applications that are satisfied with an embedded KV store backend (which is much faster and simpler to write!) already have many options.

deleted 9y ago
[deleted]
tyingq 9y ago
Would have been a neat way to experiment around with putting a SQL front end on various KV interfaces. Redis or etcd, for example.
- nerfhammer 9y ago
  Fairly straightforward to make a mysql storage engine for it, e.g. https://github.com/AALEKH/ReEngine https://github.com/AALEKH/ReEngine
- michaelmior 9y ago
  CockroachDB has a good blog post[0] that describes how they implemented SQL. (CockroachDB is a key-value store.) [0] https://www.cockroachlabs.com/blog/sql-in-cockroachdb-mapping-table-data-to-key-value-storage/ https://www.cockroachlabs.com/blog/sql-in-cockroachdb-mappin...
  - zaarn 9y ago
    >(CockroachDB is a key-value store.) Correction: CockroachDB is based on a KV store, it's a full SQL RDBMS on top of this KV store.
    - michaelmior 9y ago
      Yes, that note was misleading. Thanks for clarifying :)
- electrum 9y ago
  Presto has connectors for various types of non-SQL databases including Redis: https://prestodb.io/docs/current/connector/redis.html https://prestodb.io/docs/current/connector/redis.html Presto is a distributed SQL query engine for big data, so basically the complete opposite of SQLite, though it often gets used in federation scenarios, as does SQLite. An interesting anecdote is that the team working on what would become osquery (https://osquery.io/ https://osquery.io/) asked if they could reuse the SQL parser from Presto. We get that question a lot, and after explaining that the parser is the easy part (semantic analysis and execution is the real work), I determined that what they really wanted were SQLite virtual tables: https://sqlite.org/vtab.html https://sqlite.org/vtab.html (and those worked out great for them)
alphaalpha101 9y ago
Scaevolus, I recognise that name. #0x10c-dev on freenode? rmmh? skybot? I created a logsql.py plugin for skybot, it just logs to the DB instead of to text files. Is that something you'd be interested in merging back in?
- striking 9y ago
  Developer of some optimization mods for Minecraft, one of which became OptiFine.
sliverstorm 9y ago
Everything I hear about SQLite3 always suggests that, essentially, it is considered "done". It does what it is supposed to do with great performance. There is nothing major left to do. If it doesn't meet your needs, pick a different SQL database. Which, while a totally alien concept in the modern software world, is actually a pretty cool thought. (I'm sure under the hood bugs are getting fixed and all)
- Someone 9y ago
  Done? Almost every .0 version I checked in https://www.sqlite.org/chronology.html https://www.sqlite.org/chronology.html saw some new features.
- coleifer 9y ago
  Check out the changelog...they've added a ton of new stuff. Native json support, completely new full-text search extension, lsm key/value extension, performance improvements. I think they're looking at some changes to locking in the near future as well. Lots of stuff to find if you look.
- Oxitendwe 9y ago
  SQLite is one of my favorite pieces of software for this exact reason, that it is actually a more or less "finished" program instead of a mire of shifting design requirements and constant security updates, a comfortably static and unchanging object against the chaotic backdrop of modern software development.
- ianamartin 9y ago
  Well, obviously they should rewrite it in Rust.
  - sametmax 9y ago
    Although i get the joke, it would be a fun and interesting experiment wouldn't it ? Espacially since the sqlite test suite is so exhaustive.
    - 9y ago
makmanalp 9y ago
I've had the chance to hear Richard Hipp talk about SQLite yesterday! He mentioned that the LSM tree storage engine is available as an extension to sqlite3. More specifically, he mentioned that he didn't really get the performance improvements he had hoped for, for insertion-heavy use cases. I think part of this is because of a fundamental limitation of sqlite that it's an embedded database that has to persist data on disk at all times: The design of LSM trees works well with databases with a resident in-memory component because it's an approximation of just dumping every new thing you see at the end of an unordered in-memory array. This is as opposed to a data structure like a b-tree where you have to /find/ exactly where to put the data first, and then put it there. This finding bit means you're doing a lot of random access in memory, which is thrashing all of your caches (CPU / disk etc). LSM trees avoid this thrashing by just dumping stuff at the end of an array. However this means you have to scan that array to do lookups (as opposed to something easier like binary search). Then as your array gets big, you merge and flush it down to a lower "layer" of the lsm tree which is slightly bigger and sorted. And when that one fills, you flush further. And these merge-flushes are nice big sequential writes so that's nice too. Anyway, with SQLite, the highest layer of your LSM tree would probably (this is conjecture) have to be on disk because of the way that there is no server component, versus in an in-memory system it'd probably be in your L2/L3 cache or at least your main memory. So this could be one reason why that model didn't work out as well for them.
- coleifer 9y ago
  I'm jealous you got to hear Dr. Hipp, that sounds cool. Would love to hear more about the circumstances :) Regarding the LSM engine, you can find all the relevant implementation details here: https://sqlite.org/src4/doc/trunk/www/lsm.wiki#summary https://sqlite.org/src4/doc/trunk/www/lsm.wiki#summary > The in-memory tree is an append-only red-black tree structure used to stage user data that has not yet flushed into the database file by the system. Under normal circumstances, the in-memory tree is not allowed to grow very large.
  - 8ig8 9y ago
    I stumbled on this video presentation by Dr Hipp recently (may have been from another HN comment). I really enjoyed it. Probably because he seems so enthusiastic and passionate. SQLite: The Database at the Edge of the Network with Dr. Richard Hipp https://m.youtube.com/watch?v=Jib2AmRb_rk https://m.youtube.com/watch?v=Jib2AmRb_rk
robotbikes 9y ago
According to a presentation Richard Hipp did at Ohio State, they just didn't get the same level of performance from a log-structured merge vs. the b-tree in SQLite 3. If I remember correctly, while log structured merges where able to accumulate in memory actual to consolidate writes there was still a number of reads required to support joins etc. So they just determined based upon their testing that the b-tree based code was just faster. I don't recall the exact benchmarks, it is probably on the web somewhere.
HNSucksAss 9y ago
It's key/value store, not key-value.
manigandham 9y ago
There is also a project called UnQLite for UnQL (unstructured query language) designed to be an embedded document store, announced in 2011 [1]. Looks like it's now maintained by another company. [2] 1. https://www.infoq.com/news/2011/08/UnQL https://www.infoq.com/news/2011/08/UnQL 2. https://unqlite.org/ https://unqlite.org/

deleted 9y ago

[deleted]

tyingq 9y ago

Would have been a neat way to experiment around with putting a SQL front end on various KV interfaces. Redis or etcd, for example.

nerfhammer 9y ago
Fairly straightforward to make a mysql storage engine for it, e.g. https://github.com/AALEKH/ReEngine https://github.com/AALEKH/ReEngine
michaelmior 9y ago
CockroachDB has a good blog post[0] that describes how they implemented SQL. (CockroachDB is a key-value store.) [0] https://www.cockroachlabs.com/blog/sql-in-cockroachdb-mapping-table-data-to-key-value-storage/ https://www.cockroachlabs.com/blog/sql-in-cockroachdb-mappin...
- zaarn 9y ago
  >(CockroachDB is a key-value store.) Correction: CockroachDB is based on a KV store, it's a full SQL RDBMS on top of this KV store.
  - michaelmior 9y ago
    Yes, that note was misleading. Thanks for clarifying :)
electrum 9y ago
Presto has connectors for various types of non-SQL databases including Redis: https://prestodb.io/docs/current/connector/redis.html https://prestodb.io/docs/current/connector/redis.html Presto is a distributed SQL query engine for big data, so basically the complete opposite of SQLite, though it often gets used in federation scenarios, as does SQLite. An interesting anecdote is that the team working on what would become osquery (https://osquery.io/ https://osquery.io/) asked if they could reuse the SQL parser from Presto. We get that question a lot, and after explaining that the parser is the easy part (semantic analysis and execution is the real work), I determined that what they really wanted were SQLite virtual tables: https://sqlite.org/vtab.html https://sqlite.org/vtab.html (and those worked out great for them)

alphaalpha101 9y ago

Scaevolus, I recognise that name. #0x10c-dev on freenode? rmmh? skybot? I created a logsql.py plugin for skybot, it just logs to the DB instead of to text files. Is that something you'd be interested in merging back in?

striking 9y ago
Developer of some optimization mods for Minecraft, one of which became OptiFine.

sliverstorm 9y ago

Everything I hear about SQLite3 always suggests that, essentially, it is considered "done". It does what it is supposed to do with great performance. There is nothing major left to do. If it doesn't meet your needs, pick a different SQL database. Which, while a totally alien concept in the modern software world, is actually a pretty cool thought. (I'm sure under the hood bugs are getting fixed and all)

Someone 9y ago
Done? Almost every .0 version I checked in https://www.sqlite.org/chronology.html https://www.sqlite.org/chronology.html saw some new features.
coleifer 9y ago
Check out the changelog...they've added a ton of new stuff. Native json support, completely new full-text search extension, lsm key/value extension, performance improvements. I think they're looking at some changes to locking in the near future as well. Lots of stuff to find if you look.
Oxitendwe 9y ago
SQLite is one of my favorite pieces of software for this exact reason, that it is actually a more or less "finished" program instead of a mire of shifting design requirements and constant security updates, a comfortably static and unchanging object against the chaotic backdrop of modern software development.
ianamartin 9y ago
Well, obviously they should rewrite it in Rust.
- sametmax 9y ago
  Although i get the joke, it would be a fun and interesting experiment wouldn't it ? Espacially since the sqlite test suite is so exhaustive.
  - 9y ago

makmanalp 9y ago

I've had the chance to hear Richard Hipp talk about SQLite yesterday! He mentioned that the LSM tree storage engine is available as an extension to sqlite3. More specifically, he mentioned that he didn't really get the performance improvements he had hoped for, for insertion-heavy use cases. I think part of this is because of a fundamental limitation of sqlite that it's an embedded database that has to persist data on disk at all times: The design of LSM trees works well with databases with a resident in-memory component because it's an approximation of just dumping every new thing you see at the end of an unordered in-memory array. This is as opposed to a data structure like a b-tree where you have to /find/ exactly where to put the data first, and then put it there. This finding bit means you're doing a lot of random access in memory, which is thrashing all of your caches (CPU / disk etc). LSM trees avoid this thrashing by just dumping stuff at the end of an array. However this means you have to scan that array to do lookups (as opposed to something easier like binary search). Then as your array gets big, you merge and flush it down to a lower "layer" of the lsm tree which is slightly bigger and sorted. And when that one fills, you flush further. And these merge-flushes are nice big sequential writes so that's nice too. Anyway, with SQLite, the highest layer of your LSM tree would probably (this is conjecture) have to be on disk because of the way that there is no server component, versus in an in-memory system it'd probably be in your L2/L3 cache or at least your main memory. So this could be one reason why that model didn't work out as well for them.

coleifer 9y ago
I'm jealous you got to hear Dr. Hipp, that sounds cool. Would love to hear more about the circumstances :) Regarding the LSM engine, you can find all the relevant implementation details here: https://sqlite.org/src4/doc/trunk/www/lsm.wiki#summary https://sqlite.org/src4/doc/trunk/www/lsm.wiki#summary > The in-memory tree is an append-only red-black tree structure used to stage user data that has not yet flushed into the database file by the system. Under normal circumstances, the in-memory tree is not allowed to grow very large.
- 8ig8 9y ago
  I stumbled on this video presentation by Dr Hipp recently (may have been from another HN comment). I really enjoyed it. Probably because he seems so enthusiastic and passionate. SQLite: The Database at the Edge of the Network with Dr. Richard Hipp https://m.youtube.com/watch?v=Jib2AmRb_rk https://m.youtube.com/watch?v=Jib2AmRb_rk

robotbikes 9y ago

According to a presentation Richard Hipp did at Ohio State, they just didn't get the same level of performance from a log-structured merge vs. the b-tree in SQLite 3. If I remember correctly, while log structured merges where able to accumulate in memory actual to consolidate writes there was still a number of reads required to support joins etc. So they just determined based upon their testing that the b-tree based code was just faster. I don't recall the exact benchmarks, it is probably on the web somewhere.

HNSucksAss 9y ago

It's key/value store, not key-value.

manigandham 9y ago

There is also a project called UnQLite for UnQL (unstructured query language) designed to be an embedded document store, announced in 2011 [1]. Looks like it's now maintained by another company. [2] 1. https://www.infoq.com/news/2011/08/UnQL https://www.infoq.com/news/2011/08/UnQL 2. https://unqlite.org/ https://unqlite.org/