News for hackers. Stuff that matters.
Re:FoundationDB: A distributed unbundled transactional key v... by sa46 on Friday March 11, 2022 @04:47PM (#30646420)
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.

Re:FoundationDB: A distributed unbundled transactional key v... by mamcx on Friday March 11, 2022 @05:51PM (#30647076)
Not expert, but as enthusiast I have read some about this (for 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
Re:FoundationDB: A distributed unbundled transactional key v... by jandrewrogers on Saturday March 12, 2022 @01:12AM (#30649357)
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.

Re:FoundationDB: A distributed unbundled transactional key v... by anonymousDan on Saturday March 12, 2022 @04:53AM (#30650297)
Any papers you can recommend that go into this in more detail?
Re:FoundationDB: A distributed unbundled transactional key v... by travisd on Friday March 11, 2022 @05:13PM (#30646667)
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.

Re:FoundationDB: A distributed unbundled transactional key v... by Gaelan on Friday March 11, 2022 @05:42PM (#30646975)
> 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.