5 ms·

Local First Tuple Database

83 points by jitl 4y ago

deleted 4y ago
[deleted]
hardwaresofton 4y ago
This looks like a good idea with high quality implementation. Interfaces & abstraction where you'd expect them to be, and leveraging Typescript's type system where you can. Looks awesome. I have no idea what to use it on/with first but it will be at the back of my head for quite a while!
radarsat1 4y ago
It's a weird world to me where someone thinks that, return db.scan({prefix: ["userByName", {last_name: lastName}]}) .map(({key, value}) => key) .map(namedTupleToObject) (requiring 3 comments that I removed here for brevity, to understand) is somehow shorter and cleaner and easier to read than, SELECT id, first_name FROM user WHERE last_name = $lastName but to each his own I guess.
- politician 4y ago
  If only SQL was designed to be written in the order of execution: FROM user WHERE last_name = $lastName SELECT id, first_name
  - cmrdporcupine 4y ago
    "SELECT" doesn't mean what you think it means, I think. In the relational algebra "select" is actually a "filter" operation. It's what the "where clause" implies. The other name for it is "Restrict." It reduces the result set down to the tuples that match on the supplied predicates. SQL does a funny thing by putting it at the front of the query, but it does so as a way of saying "Hey, I'm about to begin a relational query." What you've done here is more incorrect. Maybe? Not sure of your intent. The name for the operator which "chooses which attributes to put in my results" is "PROJECTION". That's the thing that some people seem to think "select" refers to. In a more pure relational system it would look something like (syntax totally made up) Project( (id, first_name), Select( Predicate(last_name = $lastName), Relation(User))) Or maybe: User.Select(last_name=$lastName).Project({id, first_name}) As for this "order of execution" thing, SQL explicitly doesn't do that on purpose because the entire point is that the query optimizer can and should re-order things for the most efficient result. The beauty of the relational algebra (which SQL only partially implements) is that the order of operations can in many cases be re-ordered (in logically provable ways). So there is no set execution order. The system can take care of that for you.
    - karamanolev 4y ago
      Without any further knowledge, what I think they did is not so much express execution order in the RDBMS engine sense, but some logical generic-to-specific, large-to-small order. Table first (all rows, all columns), WHERE after (filter row), SELECT/project (filter columns). I'm not sure where all the other SQL operators would fit in that order, especially JOINs, GROUP BYs and so on.
      - cmrdporcupine 4y ago
        Yeah I guess the thing is that that 'logical' ordering is entirely arbitrary. It makes sense to this author I guess, but wouldn't to others. SQL's syntax is crap, but I don't see any advantages to this. Chris Date's Tutorial D had alternate syntax proposals. Personally I'd go for something more terse, like in the Rel Project's impl of the D concepts: USER {ID, FIRST_NAME} WHERE LAST_NAME= NAME($lastName) https://reldb.org/c/wp-content/uploads/2017/12/Rel-and-Tutorial-D-Quickstart.pdf https://reldb.org/c/wp-content/uploads/2017/12/Rel-and-Tutor...
      - deleted 4y ago
        [deleted]
    - twic 4y ago
      SQL's SELECT does both restriction and projection; indeed, it always does projection, but the restriction is optional: select id, first_name from user; So it's not crazy to equate SELECT with projection. If we're making up new syntaxes for relational calculus, i think something pipey would feel most natural: from user | restrict last_name = $last_name | project id, first_name; Letting you repeat stages as you see fit (this is somewhat silly example): from user | project *, is_boss = role in ('manager', 'executive') | restrict last_name = $last_name and is_boss | project id, first_name; You need some sort of converging fork to do joins, maybe: from user | restrict role = 'executive' > boss from department | restrict location = 'HQ' > hq_dept join < boss < hq_dept on boss.id = hq_dept.head_id | project first_name, last_name, dept_name Or maybe something better!
      - 4y ago
  - dspillett 4y ago
    This is a common complaint, but I've never felt the normal arrangement to be counter-intuitive. I read it as “I want the id and first name, you can get this from…” — the projection clause stating what you want, and the following clauses detailing how the information what you want can be found in is arranged. You can also think of it like a recipe: “I'm, going to make a cake, from eggs, flour, …” rather than following the instructions then at the end being told what you are making. While “from <here>, filtering by <condition>, pick <things>” better matches your view of what the database engine is going to do to service your request, matching what the engine does internally to service your request is not SQL's priority. As another example of this: with joins you are not telling the engine “this is how to do…” (well, you are, but indirectly) — what you are actually doing is describing how the information links together. With this information and other information it already has (from the schema, particularly what indexes are available) it will decide the best way to proceed, and in fact will sometimes effectively reorder your request for efficiency (some simple DB engines will always follow the order you state the objects to use, but that is their limitation not something dictated by SQL in theory).
  - 8organicbits 4y ago
    I like that order, it matches how I'd work with a Javascript list of objects: users.filter((u) => u.lastName == "foo").map((u) => [u.id, u.firstName]); Python looks like the original SQL if you do it as a list comprehension: [ (user.id, user.firstName) for user in users if user.lastName == "foo" ]
  - julienfr112 4y ago
    as a declarative language, SQL does not expose the order of execution to the user.
    - politician 4y ago
      > as a declarative language, SQL does not expose the order of execution to the user. As a practical matter, this is not true. If it were true, tools like EXPLAIN PLAN would not exist because it would not be necessary to manipulate queries to get good performance.
- deleted 4y ago
  [deleted]
- chris_armstrong 4y ago
  My impression (based on their Readne) is that the author did this not necessarily for readability, but to remove the abstraction that the database engine provides in the form of the query planner. The developer is then responsible for selecting the index and storing their data appropriately, which gives more predictable performance and makes reasoning about the behavior of the query simpler(for beginners, not necessarily easier). This is very much in the pattern of DynamoDB (which they cite), which gives highly predictable performance at all scales by removing the query planner layer and leaving the developer to work out what indexes they need, how to mold their data to them, and how too query them.
- lijogdfljk 4y ago
  Sounds like the author intends this to be a layer to create relational DBs, not in place of directly.
  - chris_armstrong 4y ago
    Quite the contrary: the author intended to do away with the abstraction over indexes that SQL engines provide, so that the developer can code against them directly
cmrdporcupine 4y ago
These kinds of efforts are heading in somewhat the right direction but would be much better if the authors spent some time reading up on the foundations of the relational model -- and instead of rolling their own bespoke map/scan/etc and 'object' and 'type' models based what they were doing on what Date/Codd etc identified as universal operations on relations and sets. "Database In Depth" is a really good book. Highly recommended. Short and clear. Don't let SQL scare you off the relational model. It has given it a bad name.
- jitl 4y ago
  The relational algebra is highly idealized and quite abstract from bytes of data. It is “declarative”. Underneath every relational modeled system, there is a lower-level, much simpler system that implements the actual data storage as bytes - and the data access APIs like “scanKeyRange”, “readKey”, “writeKey” - over a sorted data structure like a B-tree. An algebraic operation like “filter” or “selection” (σ) requires the relational layer to understand the layout of data in the storage layer if we want any kind of performance better than O(total number of tuples), right? But that adds complexity and indirection, regardless of the syntax / API used to express the relational algebra, SQL or KQL. You can think of this project as such a storage layer. It is imperative, not declarative, as a primary objective. One could build a relational layer on top, though. From the Motivation section: > I've spent way too much time in Postgres manually denormalizing data and constructing elaborate indexes that perfectly complement a complex query with the goal of EXPLAIN outputting INDEX ONLY SCAN for optimal performance. This dance is a tiresome incidental complexity for application development. How can a relational algebra system (with any form of query language or API) escape this issue? It seems inherent to the declarative nature of relational algebra.
deleted 4y ago
[deleted]
gibsonf1 4y ago
We've been using https://github.com/linkeddata/rdflib.js/ https://github.com/linkeddata/rdflib.js/ with great success - an RDF graph in-browser triplestore with excellent server sync capabilities.
- jitl 4y ago
  What are you using this for? Are you doing collaborative editing or offline viewing? I've spent some time looking at RDF things but it seems like a huge, baroque cathedral to understand. How did you get started with this tech stack?
ccorcos 4y ago
Author here, glad to see some interest. The Background and Motivation sections go into a lot of detail, but a quick summary is that if I were to build Notion all over again, I would definitely use FoundationDb. It's a lower level of abstraction and is not for the faint of heart. But indexing user-defined properties and queries with many-to-many relationships is not simple. I've since become interested in "Local-First Software" and built this abstraction to underpin my next projects which are in a similar domain that I've been calling "end-user data modeling". If you have any questions, feel free to ask or open an issue on Github.

83 points by jitl 4y ago

deleted 4y ago

[deleted]

This looks like a good idea with high quality implementation. Interfaces & abstraction where you'd expect them to be, and leveraging Typescript's type system where you can. Looks awesome. I have no idea what to use it on/with first but it will be at the back of my head for quite a while!

radarsat1 4y ago

It's a weird world to me where someone thinks that, return db.scan({prefix: ["userByName", {last_name: lastName}]}) .map(({key, value}) => key) .map(namedTupleToObject) (requiring 3 comments that I removed here for brevity, to understand) is somehow shorter and cleaner and easier to read than, SELECT id, first_name FROM user WHERE last_name = $lastName but to each his own I guess.

politician 4y ago
If only SQL was designed to be written in the order of execution: FROM user WHERE last_name = $lastName SELECT id, first_name
- cmrdporcupine 4y ago
  "SELECT" doesn't mean what you think it means, I think. In the relational algebra "select" is actually a "filter" operation. It's what the "where clause" implies. The other name for it is "Restrict." It reduces the result set down to the tuples that match on the supplied predicates. SQL does a funny thing by putting it at the front of the query, but it does so as a way of saying "Hey, I'm about to begin a relational query." What you've done here is more incorrect. Maybe? Not sure of your intent. The name for the operator which "chooses which attributes to put in my results" is "PROJECTION". That's the thing that some people seem to think "select" refers to. In a more pure relational system it would look something like (syntax totally made up) Project( (id, first_name), Select( Predicate(last_name = $lastName), Relation(User))) Or maybe: User.Select(last_name=$lastName).Project({id, first_name}) As for this "order of execution" thing, SQL explicitly doesn't do that on purpose because the entire point is that the query optimizer can and should re-order things for the most efficient result. The beauty of the relational algebra (which SQL only partially implements) is that the order of operations can in many cases be re-ordered (in logically provable ways). So there is no set execution order. The system can take care of that for you.
  - karamanolev 4y ago
    Without any further knowledge, what I think they did is not so much express execution order in the RDBMS engine sense, but some logical generic-to-specific, large-to-small order. Table first (all rows, all columns), WHERE after (filter row), SELECT/project (filter columns). I'm not sure where all the other SQL operators would fit in that order, especially JOINs, GROUP BYs and so on.
    - cmrdporcupine 4y ago
      Yeah I guess the thing is that that 'logical' ordering is entirely arbitrary. It makes sense to this author I guess, but wouldn't to others. SQL's syntax is crap, but I don't see any advantages to this. Chris Date's Tutorial D had alternate syntax proposals. Personally I'd go for something more terse, like in the Rel Project's impl of the D concepts: USER {ID, FIRST_NAME} WHERE LAST_NAME= NAME($lastName) https://reldb.org/c/wp-content/uploads/2017/12/Rel-and-Tutorial-D-Quickstart.pdf https://reldb.org/c/wp-content/uploads/2017/12/Rel-and-Tutor...
    - deleted 4y ago
      [deleted]
  - twic 4y ago
    SQL's SELECT does both restriction and projection; indeed, it always does projection, but the restriction is optional: select id, first_name from user; So it's not crazy to equate SELECT with projection. If we're making up new syntaxes for relational calculus, i think something pipey would feel most natural: from user | restrict last_name = $last_name | project id, first_name; Letting you repeat stages as you see fit (this is somewhat silly example): from user | project *, is_boss = role in ('manager', 'executive') | restrict last_name = $last_name and is_boss | project id, first_name; You need some sort of converging fork to do joins, maybe: from user | restrict role = 'executive' > boss from department | restrict location = 'HQ' > hq_dept join < boss < hq_dept on boss.id = hq_dept.head_id | project first_name, last_name, dept_name Or maybe something better!
    - 4y ago
- dspillett 4y ago
  This is a common complaint, but I've never felt the normal arrangement to be counter-intuitive. I read it as “I want the id and first name, you can get this from…” — the projection clause stating what you want, and the following clauses detailing how the information what you want can be found in is arranged. You can also think of it like a recipe: “I'm, going to make a cake, from eggs, flour, …” rather than following the instructions then at the end being told what you are making. While “from <here>, filtering by <condition>, pick <things>” better matches your view of what the database engine is going to do to service your request, matching what the engine does internally to service your request is not SQL's priority. As another example of this: with joins you are not telling the engine “this is how to do…” (well, you are, but indirectly) — what you are actually doing is describing how the information links together. With this information and other information it already has (from the schema, particularly what indexes are available) it will decide the best way to proceed, and in fact will sometimes effectively reorder your request for efficiency (some simple DB engines will always follow the order you state the objects to use, but that is their limitation not something dictated by SQL in theory).
- 8organicbits 4y ago
  I like that order, it matches how I'd work with a Javascript list of objects: users.filter((u) => u.lastName == "foo").map((u) => [u.id, u.firstName]); Python looks like the original SQL if you do it as a list comprehension: [ (user.id, user.firstName) for user in users if user.lastName == "foo" ]
- julienfr112 4y ago
  as a declarative language, SQL does not expose the order of execution to the user.
  - politician 4y ago
    > as a declarative language, SQL does not expose the order of execution to the user. As a practical matter, this is not true. If it were true, tools like EXPLAIN PLAN would not exist because it would not be necessary to manipulate queries to get good performance.
deleted 4y ago
[deleted]
chris_armstrong 4y ago
My impression (based on their Readne) is that the author did this not necessarily for readability, but to remove the abstraction that the database engine provides in the form of the query planner. The developer is then responsible for selecting the index and storing their data appropriately, which gives more predictable performance and makes reasoning about the behavior of the query simpler(for beginners, not necessarily easier). This is very much in the pattern of DynamoDB (which they cite), which gives highly predictable performance at all scales by removing the query planner layer and leaving the developer to work out what indexes they need, how to mold their data to them, and how too query them.
lijogdfljk 4y ago
Sounds like the author intends this to be a layer to create relational DBs, not in place of directly.
- chris_armstrong 4y ago
  Quite the contrary: the author intended to do away with the abstraction over indexes that SQL engines provide, so that the developer can code against them directly

cmrdporcupine 4y ago

These kinds of efforts are heading in somewhat the right direction but would be much better if the authors spent some time reading up on the foundations of the relational model -- and instead of rolling their own bespoke map/scan/etc and 'object' and 'type' models based what they were doing on what Date/Codd etc identified as universal operations on relations and sets. "Database In Depth" is a really good book. Highly recommended. Short and clear. Don't let SQL scare you off the relational model. It has given it a bad name.

jitl 4y ago
The relational algebra is highly idealized and quite abstract from bytes of data. It is “declarative”. Underneath every relational modeled system, there is a lower-level, much simpler system that implements the actual data storage as bytes - and the data access APIs like “scanKeyRange”, “readKey”, “writeKey” - over a sorted data structure like a B-tree. An algebraic operation like “filter” or “selection” (σ) requires the relational layer to understand the layout of data in the storage layer if we want any kind of performance better than O(total number of tuples), right? But that adds complexity and indirection, regardless of the syntax / API used to express the relational algebra, SQL or KQL. You can think of this project as such a storage layer. It is imperative, not declarative, as a primary objective. One could build a relational layer on top, though. From the Motivation section: > I've spent way too much time in Postgres manually denormalizing data and constructing elaborate indexes that perfectly complement a complex query with the goal of EXPLAIN outputting INDEX ONLY SCAN for optimal performance. This dance is a tiresome incidental complexity for application development. How can a relational algebra system (with any form of query language or API) escape this issue? It seems inherent to the declarative nature of relational algebra.

deleted 4y ago

[deleted]

gibsonf1 4y ago

We've been using https://github.com/linkeddata/rdflib.js/ https://github.com/linkeddata/rdflib.js/ with great success - an RDF graph in-browser triplestore with excellent server sync capabilities.

jitl 4y ago
What are you using this for? Are you doing collaborative editing or offline viewing? I've spent some time looking at RDF things but it seems like a huge, baroque cathedral to understand. How did you get started with this tech stack?

ccorcos 4y ago

Author here, glad to see some interest. The Background and Motivation sections go into a lot of detail, but a quick summary is that if I were to build Notion all over again, I would definitely use FoundationDb. It's a lower level of abstraction and is not for the faint of heart. But indexing user-defined properties and queries with many-to-many relationships is not simple. I've since become interested in "Local-First Software" and built this abstraction to underpin my next projects which are in a similar domain that I've been calling "end-user data modeling". If you have any questions, feel free to ask or open an issue on Github.