Re:Show HN: A strongly-typed document DB that runs on any tr...
by losfair on Tuesday August 31, 2021 @12:03AM
(#28363856)
- Both FDB record layer and RefineDB support complex types and indexes (with the details differing a lot); FDB record layer's index support is more complete for now.
- FDB record layer is more mature and well-tested.
- RefineDB supports KV backends other than FoundationDB.
- RefineDB can run either as a server or an embedded library in user applications; FDB record layer is a Java-only library.
- RefineDB has a functional query language for complex queries; FDB record layer does not and provides a query API instead that allows to scan, filter and sort across records.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by lewisjoe on Monday August 30, 2021 @04:07AM
(#28353631)
Great work! The ideas are intriguing. I want to know more about the quering approach. How is it better than SQL or other document quering representations? What is a concurrent data flow virtual machine ?
What is the contract to make this layer talk with the underlying stores (say, POSTGRES)?
Just want to pick your brain on these topics. Thanks :)
Re:Show HN: A strongly-typed document DB that runs on any tr...
by losfair on Monday August 30, 2021 @04:48AM
(#28353813)
Thanks for the questions!
> How is it better than SQL or other document querying representations?
SQL is a nice language for querying relational data, but RefineDB deals with nested documents. I think translation from SQL is possible for the subset of RefineDB schemas where documents are not nested though.
And RefineDB has types, and I’m not aware of any other query language that deal with types (let me know if I'm wrong).
> What is a concurrent data flow virtual machine?
The query language (RefineAsm) is a functional language with immutable semantics where values cannot be modified after construction. So a RefineAsm program can be encoded as a data flow graph where nodes are instructions and edges are data dependencies, and instructions that don’t depend on each other can be evaluated concurrently.
Read accesses to a distributed key-value store usually incur at least a few hundred microseconds of latency, so by evaluating instructions concurrently the total latency can be minimized. Somewhat similar to what a SQL query planner does.
> What is the contract to make this layer talk with the underlying stores
A storage plan is generated from the schema (the schema is the type of the storage plan). The storage plan describes how paths of document accesses should map to the underlying key-value space.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by unraveller on Monday August 30, 2021 @07:49AM
(#28354692)
>other query language that deal with types
EdgeDB has a similar strongly typed schema [1], see their edgeQL/graphQL ability. Their typed schema also facilitates computed references and computed anything, which is crucial for nested items as it keeps your DB calls much simpler. They make SQL style queries for nested data easy. On the topic of great QL i really love what deeprQL[2] brought to the table but it's JS only.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by cormacrelf on Monday August 30, 2021 @12:02PM
(#28357055)
This is a bit off-topic, but I would really like to see a good query optimiser for GraphQL. Last I checked the industry standard solution to the "N+1 selects" problem that nested queries trigger was to add a delay and attempt to batch those N calls into one. I expect EdgeDB's GraphQL implementation just translates to EdgeQL/SQL and can simply optimise that. (Probably Hasura does this too.) But I have yet to see anything near that in a GraphQL server implementation for any programming language.
From the GraphQL FAQ:
> Accessing and manipulating data is performed with arbitrary functions called resolvers. ... Generally, these resolver functions should delegate to a business logic layer responsible for communicating with the various underlying data sources. These data sources could be remote APIs, databases, local cache, and nearly anything else your programming language can access.
Somehow the lets-implement-this-syntax-in-100-popular-languages part of being a new language means these GraphQL server libraries just give you bare bones "get by id", "get all" interfaces to implement, and you're stuck with their dumb processing. This looks like a pretty standard experience of implementing GraphQL, and having to clear out a dozen jaw-droppingly dumb bugs introduced because the libraries do literally nothing for you: https://www.toptal.com/graphql/graphql-internal-api-optimiza....
Being a language, of course it must describe what the queries actually do in abstract, naive terms. Just like a programming language standard. But undefined behaviours are meant to be exploited, not used as a prototype for every implementation on Earth. I don't think GraphQL implementations are doing this nearly enough, considering that the goal is to build an SQL-like for arbitrary data backends. SQL databases ALL have optimisers. It's simply non-negotiable. For GraphQL, do whatever you need -- ask me which collections are available as tables in the same database so you can reorganise a query and send them as one "codegen unit", ask me to estimate the cost of using a resolver, ask me to build and keep indexes. That's the job, right?
Re:Show HN: A strongly-typed document DB that runs on any tr...
by 1st1 on Monday August 30, 2021 @01:34PM
(#28358431)
> I expect EdgeDB's GraphQL implementation just translates to EdgeQL/SQL and can simply optimise that.
Yeah, that's what we do. Any GraphQL query can easily be compiled to an EdgeQL (as it's a superset language) query, which then can be compiled to one SQL query.
This functionality is critical for writing web apps that reflect the current state when multiple users are collaborating on the same data.
I've been down the road many times of starting with a POST-style request/response website, only to find that it inevitably needs a realtime event feed over WebSocket to show notifications or otherwise update the view when another user changes some data. I can't stress this enough, but, IMHO a database that doesn't have this doesn't really have anything. And most databases don't have this.
If that's too ambitious, another option would be filters and/or callback hooks on the server. That way a process would be notified when something was trying to be changed, or had been changed. Then the user could append events containing the data identifier/path onto their own WebSocket manually. Apologies if you've already implemented this and I just haven't read the documentation.
Another rather selfish ask for myself would be a transpiler from SQL to your RefineASM DSL. Being able to go the other way would be pretty awesome too. I'd love to design queries using sets and be able to generate the SQL without having to deal with SQL's quirks since it's so old.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by tluyben2 on Monday August 30, 2021 @04:10AM
(#28353641)
Nice work! Been playing with this idea for a while to write something like this (in Rust); now you did a lot of the heavy lifting for what I would need already.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by voidmain on Monday August 30, 2021 @07:58AM
(#28354754)
This looks really cool!
Perhaps you should show some nontrivial examples of (read) queries in RefineASM.
Also, what are your plans (if any) for non primary indexing? Storage plans seem like a good fit, but will you transform RefineASM to maintain the indexes or what? What about using the indexes?
For example, here's a test that generates a list of integers, inserts the list into the database as set members, computes the sum and verifies it, and reads back the list: https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105dd... . The read-back part looks like:
Re:Show HN: A strongly-typed document DB that runs on any tr...
by losfair on Monday August 30, 2021 @08:59AM
(#28355182)
On non-primary indexing: It's a nice thing to have but I haven't decided on the design yet. My current preference is to implement the non-primary index feature as a library once the human-friendly higher layer of RefineAsm (RefineQL) is built.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by voidmain on Monday August 30, 2021 @11:38AM
(#28356739)
Consider thinking of index maintenance as part of your storage mapping layer. Basically you have redundant storage plans for the same schema. There is nothing particularly special about primary row indexes - that is just one physical representation of your schema, as are all indexes. You could have, say, a column oriented representation of the same data instead, or a covering index, or all of the above.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by tluyben2 on Monday August 30, 2021 @12:06PM
(#28357099)
I really like TiKV: can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves?
Did you do any profiling on your in memory store? I am looking, working on a toy project, for something like this that has 3 layers: local mem, distributed memory and distributed persistence with the same api and, more specifically, query engine. There are kv stores for these (TiKV and Foundation for the last category), Rondb maybe for the in distributed in memory but locally, it should be capable of very high volume (evmap doing a billion/minute but that would not work as not transactional). I bet it is too early to worry about perf for you but it seems you can leave most of that to the kv store which I like.
Re:Show HN: A strongly-typed document DB that runs on any tr...
by losfair on Monday August 30, 2021 @11:46PM
(#28363762)
> can you explain what the issue is with it? And do what are ways to resolve it if TiKV does not resolve it themselves?
TiKV is based on multi-raft + Percolator where there is no way to coordinate a consistent range operation across regions (key ranges) and therefore does not support range deletion.
RefineDB uses range deletion to delete non-primitive types that contain multiple members, e.g. tables and sets.
To support TiKV, RefineDB needs to support asynchronous range deletion - mark a range as deleted, and never use it again. This requires some work on the storage mapping layer, to map ABA accesses to a recreated-after-deleted range to a different keyspace.
> Did you do any profiling on your in memory store?
Not yet, actually the in-memory store is just for use in tests and the web playground where performance isn't important.
For a better in-memory store, I think it's better to use the SQLite backend with an in-memory database.
[1] https://github.com/FoundationDB/fdb-record-layer
- FDB record layer is more mature and well-tested.
- RefineDB supports KV backends other than FoundationDB.
- RefineDB can run either as a server or an embedded library in user applications; FDB record layer is a Java-only library.
- RefineDB has a functional query language for complex queries; FDB record layer does not and provides a query API instead that allows to scan, filter and sort across records.
What is the contract to make this layer talk with the underlying stores (say, POSTGRES)?
Just want to pick your brain on these topics. Thanks :)
> How is it better than SQL or other document querying representations?
SQL is a nice language for querying relational data, but RefineDB deals with nested documents. I think translation from SQL is possible for the subset of RefineDB schemas where documents are not nested though.
And RefineDB has types, and I’m not aware of any other query language that deal with types (let me know if I'm wrong).
> What is a concurrent data flow virtual machine?
The query language (RefineAsm) is a functional language with immutable semantics where values cannot be modified after construction. So a RefineAsm program can be encoded as a data flow graph where nodes are instructions and edges are data dependencies, and instructions that don’t depend on each other can be evaluated concurrently.
Read accesses to a distributed key-value store usually incur at least a few hundred microseconds of latency, so by evaluating instructions concurrently the total latency can be minimized. Somewhat similar to what a SQL query planner does.
> What is the contract to make this layer talk with the underlying stores
A storage plan is generated from the schema (the schema is the type of the storage plan). The storage plan describes how paths of document accesses should map to the underlying key-value space.
There are detailed description and examples of how this mapping is done at https://github.com/losfair/RefineDB/blob/main/design/storage....
EdgeDB has a similar strongly typed schema [1], see their edgeQL/graphQL ability. Their typed schema also facilitates computed references and computed anything, which is crucial for nested items as it keeps your DB calls much simpler. They make SQL style queries for nested data easy. On the topic of great QL i really love what deeprQL[2] brought to the table but it's JS only.
[1] https://www.edgedb.com/docs/edgeql/index [2] https://github.com/deeprjs/deepr
From the GraphQL FAQ:
> Accessing and manipulating data is performed with arbitrary functions called resolvers. ... Generally, these resolver functions should delegate to a business logic layer responsible for communicating with the various underlying data sources. These data sources could be remote APIs, databases, local cache, and nearly anything else your programming language can access.
Somehow the lets-implement-this-syntax-in-100-popular-languages part of being a new language means these GraphQL server libraries just give you bare bones "get by id", "get all" interfaces to implement, and you're stuck with their dumb processing. This looks like a pretty standard experience of implementing GraphQL, and having to clear out a dozen jaw-droppingly dumb bugs introduced because the libraries do literally nothing for you: https://www.toptal.com/graphql/graphql-internal-api-optimiza....
Being a language, of course it must describe what the queries actually do in abstract, naive terms. Just like a programming language standard. But undefined behaviours are meant to be exploited, not used as a prototype for every implementation on Earth. I don't think GraphQL implementations are doing this nearly enough, considering that the goal is to build an SQL-like for arbitrary data backends. SQL databases ALL have optimisers. It's simply non-negotiable. For GraphQL, do whatever you need -- ask me which collections are available as tables in the same database so you can reorganise a query and send them as one "codegen unit", ask me to estimate the cost of using a resolver, ask me to build and keep indexes. That's the job, right?
Yeah, that's what we do. Any GraphQL query can easily be compiled to an EdgeQL (as it's a superset language) query, which then can be compiled to one SQL query.
Can't you just expand the nested documents into a non-nested version and use references?
In what sense is SQL not typed?
https://rethinkdb.com/docs/changefeeds/javascript/
https://firebase.google.com/docs/functions/database-events
This functionality is critical for writing web apps that reflect the current state when multiple users are collaborating on the same data.
I've been down the road many times of starting with a POST-style request/response website, only to find that it inevitably needs a realtime event feed over WebSocket to show notifications or otherwise update the view when another user changes some data. I can't stress this enough, but, IMHO a database that doesn't have this doesn't really have anything. And most databases don't have this.
If that's too ambitious, another option would be filters and/or callback hooks on the server. That way a process would be notified when something was trying to be changed, or had been changed. Then the user could append events containing the data identifier/path onto their own WebSocket manually. Apologies if you've already implemented this and I just haven't read the documentation.
Another rather selfish ask for myself would be a transpiler from SQL to your RefineASM DSL. Being able to go the other way would be pretty awesome too. I'd love to design queries using sets and be able to generate the SQL without having to deal with SQL's quirks since it's so old.
Which is incredible.
Perhaps you should show some nontrivial examples of (read) queries in RefineASM.
Also, what are your plans (if any) for non primary indexing? Storage plans seem like a good fit, but will you transform RefineASM to maintain the indexes or what? What about using the indexes?
For example, here's a test that generates a list of integers, inserts the list into the database as set members, computes the sum and verifies it, and reads back the list: https://github.com/losfair/RefineDB/blob/ddac0d35b16c01105dd... . The read-back part looks like:
And it's trivial to modify the reduce function `decompose_numbers` to return a more interesting aggregated value, e.g. the sum.The syntax is not yet very optimized for humans though (hence the name RefineAsm).
I'll explore targeting this with my repository implementation to save some complexity.
Plans to support more DBs? do you intend for the OS community to build the translation layers?
> Plans to support more DBs?
RocksDB and TiKV backends are planned: https://github.com/losfair/RefineDB/issues/3
> do you intend for the OS community to build the translation layers?
What do you mean by "translation layers" here?
Did you do any profiling on your in memory store? I am looking, working on a toy project, for something like this that has 3 layers: local mem, distributed memory and distributed persistence with the same api and, more specifically, query engine. There are kv stores for these (TiKV and Foundation for the last category), Rondb maybe for the in distributed in memory but locally, it should be capable of very high volume (evmap doing a billion/minute but that would not work as not transactional). I bet it is too early to worry about perf for you but it seems you can leave most of that to the kv store which I like.
TiKV is based on multi-raft + Percolator where there is no way to coordinate a consistent range operation across regions (key ranges) and therefore does not support range deletion.
RefineDB uses range deletion to delete non-primitive types that contain multiple members, e.g. tables and sets.
To support TiKV, RefineDB needs to support asynchronous range deletion - mark a range as deleted, and never use it again. This requires some work on the storage mapping layer, to map ABA accesses to a recreated-after-deleted range to a different keyspace.
> Did you do any profiling on your in memory store?
Not yet, actually the in-memory store is just for use in tests and the web playground where performance isn't important.
For a better in-memory store, I think it's better to use the SQLite backend with an in-memory database.