3 ms·

One of the challenges with layering SQL on top of a KV store is query performance. The most obvious way to model a secondary index on top of a pure KV store is

One of the challenges with layering SQL on top of a KV store is query performance. The most obvious way to model a secondary index on top of a pure KV store is to map indexed values to keys. For example, given the (rowID, name) tuples (123, "Bob"), (345, "Jane"), (234, "Zack"), you can store these as keys: name:Bob:123 name:Jane:345 name:Zack:234 At this point you don't need or even want values, so this is effectively a sorted set. Now you can easily find the rowID of Jane by doing a key scan for "name:Jane:", which should be efficient in a KV store that supports key range scans. You can do prefix searches this way ("name:Jane" finds all keys starting with "Jane"), as well as ordinal constraints ("age > 32", which requires that the age index is encoded to something like: age:Bob:\x00\x00\x00\x20:123 To perform an union ("name = 'Bob' OR name = 'Jane'"), you simply do multiple range scans, performing a merge sort-ish union operation as you go. To perform an intersection ("name = 'Bob' AND age > 10"), you find the starting point for all the terms and use that as the key range, then do the merge sort. This is what TiDB and FoundationDB's record layers do, which both have a strict separation between the stateless database layer and the stateful KV layer. The performance bottleneck will be the network layer. Your range scan operations will be streaming a lot of data from the KV store to the SQL layer, and potentially you'll be reading a lot of data that is discarded by higher-level query layers. This is why TiKV has "co-processor" logic in the KV store that knows how to do things like filter; when TiDB plays your query, it pushes some query operators down to TiKV itself for performance. Unfortunately, this is not possible with FoundationDB. This is why FoundationDB's authors recommend you co-locate FDB with your application on the same machine. But since FDB key ranges are distributed, there's no way to actually bring the query code close to the data (as far as I know!). I'm sure you could do something similiar with Redis and Lua scripting, i.e. building query operators as Lua scripts that worked on sorted sets. I wouldn't trust Redis as a primary data store, but it can be a fast secondary index.

senderista 7y ago
I disagree that an index is a set rather than a map: it is by definition a map from keys to row ids. As for a generic relational layer over K/V stores, I think it’s a superficially appealing idea that would be impossible to optimize adequately in practice. Honestly, if you want to implement a distributed relational database, I would recommend starting with Postgres as your local storage engine and pushing down as much relational logic as possible to that layer. I have worked on such a system in the past and it produced very good results for minimal development effort.
- atombender 7y ago
  I'm not talking about just any index, I'm talking about using a plain KV store as an index. The row ID can be encoded into the key. From my example, a basic mapping might be: name:Bob:123 => <empty value> If your KV store is optimized for range scans, as they usually are, then there's no reason to store anything in the value, because a key range scan can efficiently jump to the first instance of a key prefix. For example, if I want to search for "name = 'Bob'", then I simply start at the key "name:Bob:" and pluck the row ID from each key, scanning sequentially until I reach the end of my range. This works great for multiple values. For example: name:Bob:123 => <empty value> name:Bob:124 => <empty value> name:Bob:125 => <empty value> Finding all rows matching "Bob" is a matter of just scanning by prefix. If you store row IDs in the value, you'll risk read/write contention on the value. Let's say there are multiple rows with "Bob", you'll end up storing something like: name:Bob => [123, 124, 125] To add or remove row IDs you'll now have to merge values of unrelated rows, and make sure this happens atomically. That usually means locking. This also puts a constraint on the number of row IDs you can fit in a single value. KV stores typically co-locate value data with keys, so now you might not be able to efficiently scan a large range without also loading that data. You can do tricks like introducing an indirection, where you don't store "row IDs", but "row page IDs", where each page is sharded maximum of N row IDs, allowing you to sidestep the size limit on values. But that comes with other costs. I'm not counting in-memory stores like Redis here. Implementing in-memory indexes is a completely different ball game to something that needs to live on disk. As for "superficially appealing idea that would be impossible to optimize adequately in practice", your assertion is demonstrably false: TiDB and CockroachDB both implement performant relational databases on top of general-purpose KV stores.
ryanworl 7y ago
FoundationDB's client bindings have a locality API which allows you to query the client's metadata cache of which key ranges are on which storage processes. This would allow you to build that feature of routing a query to the data.
- atombender 7y ago
  I didn't know that. Very cool, thanks!

senderista 7y ago

I disagree that an index is a set rather than a map: it is by definition a map from keys to row ids. As for a generic relational layer over K/V stores, I think it’s a superficially appealing idea that would be impossible to optimize adequately in practice. Honestly, if you want to implement a distributed relational database, I would recommend starting with Postgres as your local storage engine and pushing down as much relational logic as possible to that layer. I have worked on such a system in the past and it produced very good results for minimal development effort.

atombender 7y ago
I'm not talking about just any index, I'm talking about using a plain KV store as an index. The row ID can be encoded into the key. From my example, a basic mapping might be: name:Bob:123 => <empty value> If your KV store is optimized for range scans, as they usually are, then there's no reason to store anything in the value, because a key range scan can efficiently jump to the first instance of a key prefix. For example, if I want to search for "name = 'Bob'", then I simply start at the key "name:Bob:" and pluck the row ID from each key, scanning sequentially until I reach the end of my range. This works great for multiple values. For example: name:Bob:123 => <empty value> name:Bob:124 => <empty value> name:Bob:125 => <empty value> Finding all rows matching "Bob" is a matter of just scanning by prefix. If you store row IDs in the value, you'll risk read/write contention on the value. Let's say there are multiple rows with "Bob", you'll end up storing something like: name:Bob => [123, 124, 125] To add or remove row IDs you'll now have to merge values of unrelated rows, and make sure this happens atomically. That usually means locking. This also puts a constraint on the number of row IDs you can fit in a single value. KV stores typically co-locate value data with keys, so now you might not be able to efficiently scan a large range without also loading that data. You can do tricks like introducing an indirection, where you don't store "row IDs", but "row page IDs", where each page is sharded maximum of N row IDs, allowing you to sidestep the size limit on values. But that comes with other costs. I'm not counting in-memory stores like Redis here. Implementing in-memory indexes is a completely different ball game to something that needs to live on disk. As for "superficially appealing idea that would be impossible to optimize adequately in practice", your assertion is demonstrably false: TiDB and CockroachDB both implement performant relational databases on top of general-purpose KV stores.

ryanworl 7y ago

FoundationDB's client bindings have a locality API which allows you to query the client's metadata cache of which key ranges are on which storage processes. This would allow you to build that feature of routing a query to the data.

atombender 7y ago
I didn't know that. Very cool, thanks!