Query Planner

[chewxy]

An Edit Mistake

@amaster507

To understand my thoughts let’s look at another potential pitfall given even this very small sample of schema and these two queries

I miswrote:

q and r returns the same results under the condition that the schema was as given

should be

q and r returns the same results under the condition that the schema and data was as given

I think an earlier version of the draft did use data.

@amaster507

The schema is not what made the two queries return the same results, but rather it was the data that yielded to the same results.

Yes and no. Under a strict schema regime, you would not have data that do not fit the schema. But as you say:

@amaster507

What is even more frustrating is that Dgraph can be utilized in a schema-less style and sort of build a schema as it goes when first seeing a predicate and guessing at it’s type from the received type. That is great for flexibility, but makes things difficult when trying to implement a query planner.

On The Concrete Steps Listed

Your concrete steps (1,2,3,4) are very very excellent and specific elaborations/examples of the table of compositions process I listed above. I have some comments:

@amaster507

3. Rewriting queries with cascade
   …
4. Reversing a query and then recompiling the results returned

A key thing I feel that has been slightly missed is that the @cascade directive or ~ are actually elements of the query language, and thus can be boiled down to an operation. I do think this is jumping to solutions before a blueprint is even created (e.g. the table of compositions)

On Denotational Semantics

@amaster507

And here is wherein lies almost every problem with any kind of query planner/optimization that would really be performant:

The shape of the graph the client asks for is the shape of the graph the response should return

…

Which contains the same nodes of data if hobbies is what you really want, but a query planner cannot make assumptions into what you really want vs. what you asked for.

That’s what the whole denotational semantics shebang is all about. You can only make a rewrite if you know that the result of the rewrite will yield the same data (same denotation).

The main issue is you run into “runtime” issues, requiring you to look at the data before you look at the data. Enforcing a strict schema would allow you to avoid doing that, so you look at the metadata (schema) before you look at the data.

On the Suitability of a Query Planner for DQL

@amaster507

Hence which leads me to believe that a query planner might not really work well after all in a graph database, and instead query planner would really just be a query rewriter/optimizer to do 1, 2, 3, but nothing as complex as 4 like a rdbms query planner might do when doing joins differently than how the client asked for them.

I think the flexibility of the query specifically allows for a query planner to be written! Other than directives (which are “action” words, or “commands” if you are used to 1960s style PLT lingo), everything else is declarative. That leaves a LOT of freedom to re-order the operations to something that best fits the performance characteristics. A key is to lean on Codd’s relational algebra, or to create something similar.

On @normalize

@amaster507

A factor into this might be the normalize directive which I still do not understand fluently enough to make educated assumptions on how to optimize that.

My understanding is @normalize is just a fmap. It’s just an operation.