4 ms·

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

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.

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.