4 ms·

Very curious, what’s an alternative implementation strategy or more appropriate mental model? My mental model (I am not a database engineer) is that every SQL

by sa46 5y ago

Very curious, what’s an alternative implementation strategy or more appropriate mental model? My mental model (I am not a database engineer) is that every SQL database is fundamentally backed by a key value store. For Postgres, each value is a row of a relation, the key is the relation’s key, and the physical storage is the table file. Postgres builds b-trees on top to make it fast, but the b-tree itself is a relation, a key value store that Postgres works hard to keep sorted.

travisd 5y ago
i’m also not a db engineer, but i think this is true-ish. however building and maintaining those index tables is hard and probably prone to issues if you can’t update multiple as part of the same transaction. the other major thing you’d miss is smarter joins. the distributed databases do a lot of work to be able to push down predicates as far down as possible to the physical nodes storing the data. there’s probably more as well.
- Gaelan 5y ago
  > probably prone to issues if you can’t update multiple as part of the same transaction IIRC one of FoundationDB's features is that it does support such transactions, so you can easily implement indexing on top of it.
mamcx 5y ago
Not expert, but as enthusiast I have read some about this (for https://tablam.org https://tablam.org). KV is truly ill-suited for this. Is very easy to see if you put the data layout: --data pk city country 1 miami USA 2 bogota Colombia --As Kv (naive): pk1: 1 pk2: 2 city1: miami city2: bogota --As btree, with "value" being N (as you say): Key Value 1 1 miami USA 2 2 bogota Colombia --As paged btree Page1 Low: 1 High:2 //think this is a block 1 miami USA 2 bogota Colombia --As columnar: pk: 1 2 city: miami bogota --As PAX (hybrid columnar/row) Page1 Low: 1 High:2 //think this is a block pk: 1 2 city: miami bogota
jandrewrogers 5y ago
Many data models don't have obvious singular keys. The critical search relationships cannot be reduced to an order relationship on a single column a priori. Much of the most interesting research in storage models is around increasingly efficient ways of indexing complex information theoretic features across multiple columns in a single structure, with an underlying storage implementation to match. At some level, every database contains a key-value store. For performance reasons, the hardware always has to be treated this way. Databases work at the level of blocks/pages, but those abstractions are usually hidden from users with a lot of clever logic in the middle that is more opinionated to enable optimization. That doesn't change. An interesting and important property of search data structures is that, at the limit, a single index that can optimally satisfy all possible queries is equivalent to general AI. It is also completely intractable. Fortunately real-world queries tend to be much more limited in nature. A corollary is that the distinction between indexing, storage, and scheduling in databases is a fiction -- useful for making some things simple but not necessary in any database. In essence, the practice of treating indexing, storage, and scheduling as discrete functions in a database is the opposite extreme. There are a vast number of possible implementations between these two extremes with better properties than either in practical real-world databases. As a general design principle for scalability and performance reasons, you want to organize your data model around a single indexing mechanic. Consequently, it is critical to maximize the expressiveness and efficiency of any particular indexing mechanic. At the limit, with a good algorithm, it is equivalent to having an index for each column, with the ability to efficiently search more features of the data and without the overhead of actually having an index for each column. I think we are entering a new golden age of database technology where the boundaries between elements we treated as discrete are much fuzzier.
- anonymousDan 5y ago
  Any papers you can recommend that go into this in more detail?

by sa46 5y ago

travisd 5y ago

i’m also not a db engineer, but i think this is true-ish. however building and maintaining those index tables is hard and probably prone to issues if you can’t update multiple as part of the same transaction. the other major thing you’d miss is smarter joins. the distributed databases do a lot of work to be able to push down predicates as far down as possible to the physical nodes storing the data. there’s probably more as well.

Gaelan 5y ago
> probably prone to issues if you can’t update multiple as part of the same transaction IIRC one of FoundationDB's features is that it does support such transactions, so you can easily implement indexing on top of it.

mamcx 5y ago

Not expert, but as enthusiast I have read some about this (for https://tablam.org https://tablam.org). KV is truly ill-suited for this. Is very easy to see if you put the data layout: --data pk city country 1 miami USA 2 bogota Colombia --As Kv (naive): pk1: 1 pk2: 2 city1: miami city2: bogota --As btree, with "value" being N (as you say): Key Value 1 1 miami USA 2 2 bogota Colombia --As paged btree Page1 Low: 1 High:2 //think this is a block 1 miami USA 2 bogota Colombia --As columnar: pk: 1 2 city: miami bogota --As PAX (hybrid columnar/row) Page1 Low: 1 High:2 //think this is a block pk: 1 2 city: miami bogota

jandrewrogers 5y ago

Many data models don't have obvious singular keys. The critical search relationships cannot be reduced to an order relationship on a single column a priori. Much of the most interesting research in storage models is around increasingly efficient ways of indexing complex information theoretic features across multiple columns in a single structure, with an underlying storage implementation to match. At some level, every database contains a key-value store. For performance reasons, the hardware always has to be treated this way. Databases work at the level of blocks/pages, but those abstractions are usually hidden from users with a lot of clever logic in the middle that is more opinionated to enable optimization. That doesn't change. An interesting and important property of search data structures is that, at the limit, a single index that can optimally satisfy all possible queries is equivalent to general AI. It is also completely intractable. Fortunately real-world queries tend to be much more limited in nature. A corollary is that the distinction between indexing, storage, and scheduling in databases is a fiction -- useful for making some things simple but not necessary in any database. In essence, the practice of treating indexing, storage, and scheduling as discrete functions in a database is the opposite extreme. There are a vast number of possible implementations between these two extremes with better properties than either in practical real-world databases. As a general design principle for scalability and performance reasons, you want to organize your data model around a single indexing mechanic. Consequently, it is critical to maximize the expressiveness and efficiency of any particular indexing mechanic. At the limit, with a good algorithm, it is equivalent to having an index for each column, with the ability to efficiently search more features of the data and without the overhead of actually having an index for each column. I think we are entering a new golden age of database technology where the boundaries between elements we treated as discrete are much fuzzier.

anonymousDan 5y ago
Any papers you can recommend that go into this in more detail?