Evaluation algorithm​

EdgeQL is a functional language in the sense that every expression is a composition of one or more queries.

Queries can be explicit, such as a select statement, or implicit, as dictated by the semantics of a function, operator or a statement clause.

An implicit select subquery is assumed in the following situations:

  • expressions passed as an argument for an aggregate function parameter or operand;

  • the right side of the assignment operator (:=) in expression aliases and shape element declarations;

  • the majority of statement clauses.

A nested query is called a subquery. Here, the phrase “apearing directly in the query” means “appearing directly in the query rather than in the subqueries”.

A query is evaluated recursively using the following procedure:

  1. Make a list of simple paths appearing directly the query. For every path in the list, find all paths which begin with the same set reference and treat their longest common prefix as an equivalent set reference.

    Example:

  1. ```
  2. select (
  3.   User.firstname,
  4.   User.friends.firstname,
  5.   User.friends.lastname,
  6.   Issue.priority.name,
  7.   Issue.number,
  8.   Status.name
  9. );
  10. ```
  12. In the above query, the longest common prefixes are: `User`, `User.friends`, `Issue`, and `Status.name`.

  1. Make a query input list of all unique set references which appear directly in the query (including the common path prefixes identified above). The set references and path prefixes in this list are called input set references, and the sets they represent are called input sets. Order this list such that any input references come before any other input set reference for which it is a prefix (sorting lexicographically works).

  2. Compute a set of input tuples.

    • Begin with a set containing a single empty tuple.

    • For each input set reference, we compute a dependent Cartesian product of the input tuple set (X) so far and the input set Y being considered. In this dependent product, we pair each tuple x in the input tuple set X with each element of the subset of the input set Y corresponding to the tuple x. (For example, in the above example, computing the dependent product of User and User.friends would pair each user with all of their friends.)

      (Mathematically, X' = {(x, y) | x ∈ X, y ∈ f(x)}, if f(x) selects the appropriate subset.)

      The set produced becomes the new input tuple set and we continue down the list.

    • As a caveat to the above, if an input set appears exclusively as an optional argument, it produces pairs with a placeholder value Missing instead of an empty Cartesian product in the above set. (Mathematically, this corresponds to having f(x) = {Missing} whenever it would otherwise produce an empty set.)

  3. Iterate over the set of input tuples, and on every iteration:

    • in the query and its subqueries, replace each input set reference with the corresponding value from the input tuple or an empty set if the value is Missing;

    • evaluate the query expression in the order of precedence using the following rules:

      • subqueries are evaluated recursively from step 1;

      • a function or an operator is evaluated in a loop over a Cartesian product of its non-aggregate arguments (empty optional arguments are excluded from the product); aggregate arguments are passed as a whole set; the results of the invocations are collected to form a single set.

  4. Collect the results of all iterations to obtain the final result set.