The underlying organization of a database is not about what can be expressed in theory, it is about what can be expressed <i>efficiently</i>. Not only is there a very rich set of data structure designs that can be used with varying tradeoffs, but most sophisticated databases use an ecosystem of different, tightly interwoven data structures that smooth over the sharp corners that any single data structure has.<p>Efficient expressiveness follows from the relationships directly preserved in the organization. Generally from least-to-most expressive you have:<p>- cardinality preserving (hash tables, most KV stores)<p>- order preserving (LSM, btree, skiplist, space-filling curves*)<p>- space preserving (space decomposition e.g. quad-tree, a zoo of exotics)<p>Competent implementation is progressively more complex, nuanced, and sophisticated as you go down the list, so most implementations reflect the comfort level of implementor. As you move down this stack, you can express things efficiently that will be very inefficient to express with a less expressive class of organization.<p>SQL was designed for databases built on order-preserving structures. While you can implement it on a KV store, it will never be as efficient as a database organized in the more expressive organization that SQL assumes.<p>KV stores are popular because they are relatively simple to design and implement, not because they are expressive. It is an architectural impedance mismatch to add query functionality that tacitly assumes a more expressive organization. It will never perform well against a database actually organized for the expressiveness of the query layer.<p>Any database can only do a few things really well. It is inherent in the tradeoffs. You can add mediocre support for a laundry list of other "good enough" capabilities but you never want to market and position your product around those mediocre capabilities.