4 ms·

I hope using an embeddable database will also free us from delegating the choice of query language to the database library. It should be possible to have a gene

I hope using an embeddable database will also free us from delegating the choice of query language to the database library. It should be possible to have a general purpose low level persistence API and many different query engines built on top of it.

packetlost 4y ago
I think the problem with querying is efficient query-planning requires understanding the indexes on the dataset, so you at least need to be able to expose indexes and the their properties in an API.
- Kinrany 4y ago
  The API should definitely either allow directly managing indexes or provide even lower level primitives that let the query engine create its own indexes.
  - packetlost 4y ago
    I mean, if you have a KV-like store that supports enumeration, you can pretty much always index the data yourself.
- kjeetgill 4y ago
  Imho the 90% of query planning is not that hard at all in practice. If it's your data, and your query you'll probably have a pretty good idea which table you'll want to filter first, and what to join the same you would with any data structures. The hard part is getting all of that consistent with concurrent writes. Can rows change while you scan? can indexes? How do you check that your write is valid immediately before committing, etc. things like that. I think SQL makes that pretty hard already, but in a "database-as-a-bag-of-data-structures" mode I think that's going to get even harder.
  - thesz 4y ago
    IMNSHO query planning is pretty hard. I recently found exponential behavior in SELECT query processing that depends on the depth of subselects. This happened with pretty seasoned database system, let me say. To have good query optimization, you need to implement, at the very least, some form of dynamic programming, otherwise you will not be able to optimize queries that have more than half a dozen tables in selects. Then you have to implement selection of the best plan or approximation to it, which would make you implement beam search through space of all solutions you generated, and that's simplest case. For guaranteed optimization, you need to implement or utilize pseudoboolean optimization engine. I am a database engine developer right now. ;)
    - j-pb 4y ago
      If you just pick a worst case optimal join algorithm with a limited table cardinality, i.e. triples like in the case of OP, so that you can materialise every possible index, you can perform a dynamic _instance optimal_ search (i.e. you can ignore skew), if you choose the best possible variable every time you have to pick a variable. This can be done by estimating the cardinality and jaccard index of the variables, which is pretty straightforward with the right datastructure. If you don't want to limit yourself to just three columns, you can also go for cutting edge succinct data-structure magic. https://aidanhogan.com/docs/wco-ring.pdf https://aidanhogan.com/docs/wco-ring.pdf Either way, using a WCO join combined with a data-structure that allows for efficient range estimate and dynamic variable ordering, completely obliviates the need for query planning.
      - thesz 4y ago
        "Estimate the cardinality", "jaccard index", "succinct data structure" and, finally, some unknown abbreviation "WCO" (I guess, it stands for "worst case optimal"). Yes, of course, having implementation of all that completely obliviates the need for query planning. ;) I can't help being sarcastic for a moment, sorry. In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices. If what you described is simpler than query planning, then query planning is hard.
awild 4y ago
Have you had a look at arrow? It has those capabilities

packetlost 4y ago

I think the problem with querying is efficient query-planning requires understanding the indexes on the dataset, so you at least need to be able to expose indexes and the their properties in an API.

Kinrany 4y ago
The API should definitely either allow directly managing indexes or provide even lower level primitives that let the query engine create its own indexes.
- packetlost 4y ago
  I mean, if you have a KV-like store that supports enumeration, you can pretty much always index the data yourself.
kjeetgill 4y ago
Imho the 90% of query planning is not that hard at all in practice. If it's your data, and your query you'll probably have a pretty good idea which table you'll want to filter first, and what to join the same you would with any data structures. The hard part is getting all of that consistent with concurrent writes. Can rows change while you scan? can indexes? How do you check that your write is valid immediately before committing, etc. things like that. I think SQL makes that pretty hard already, but in a "database-as-a-bag-of-data-structures" mode I think that's going to get even harder.
- thesz 4y ago
  IMNSHO query planning is pretty hard. I recently found exponential behavior in SELECT query processing that depends on the depth of subselects. This happened with pretty seasoned database system, let me say. To have good query optimization, you need to implement, at the very least, some form of dynamic programming, otherwise you will not be able to optimize queries that have more than half a dozen tables in selects. Then you have to implement selection of the best plan or approximation to it, which would make you implement beam search through space of all solutions you generated, and that's simplest case. For guaranteed optimization, you need to implement or utilize pseudoboolean optimization engine. I am a database engine developer right now. ;)
  - j-pb 4y ago
    If you just pick a worst case optimal join algorithm with a limited table cardinality, i.e. triples like in the case of OP, so that you can materialise every possible index, you can perform a dynamic _instance optimal_ search (i.e. you can ignore skew), if you choose the best possible variable every time you have to pick a variable. This can be done by estimating the cardinality and jaccard index of the variables, which is pretty straightforward with the right datastructure. If you don't want to limit yourself to just three columns, you can also go for cutting edge succinct data-structure magic. https://aidanhogan.com/docs/wco-ring.pdf https://aidanhogan.com/docs/wco-ring.pdf Either way, using a WCO join combined with a data-structure that allows for efficient range estimate and dynamic variable ordering, completely obliviates the need for query planning.
    - thesz 4y ago
      "Estimate the cardinality", "jaccard index", "succinct data structure" and, finally, some unknown abbreviation "WCO" (I guess, it stands for "worst case optimal"). Yes, of course, having implementation of all that completely obliviates the need for query planning. ;) I can't help being sarcastic for a moment, sorry. In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices. If what you described is simpler than query planning, then query planning is hard.

awild 4y ago

Have you had a look at arrow? It has those capabilities