Attribute lineage: Dependency from aggregation expressions to preceding selection operations

[wajda]

In the following pseudo query, output attribute b should depend not only on a, but also on c and g even though they are not directly present in b's AST.

SELECT AGG(a) as b, g
  FROM t
 WHERE c
 GROUP BY g

[vidma]

@wajda I'd say might also depend on g also, as both c & g provide control lineage - the result value depend on the value of g even if indirectly. thus this we consider two types of lineages -data & control, data being the main one.

[wajda]

Yes, correct, of course, it's just an oversight in description. Thanks for pointing it out! :)

[wajda]

Just making a quick note of an idea.

This problem can be modeled in the following way. Every operation can have properties like if it potentially changes the number of rows (e.g. filter, union) or the order of rows (e.g. sort). Additionally if the operation changes either the number or the order of elements it can provide a reference to a corresponding expression or attribute involved in the process.

Then, on the expression definition level it could be specified if the expression is an aggregation, and if it's commutative.
Based on the above information we could derive additional dependencies for expressions/attributes.

Pseudo code:

trait OperationLike {
  ...
  def properties: Option[OperationProperties]
}

class OperationProperties (
  val resize: Option[Boolean | AttrOrExprRef] = false
  val reorder: Option[Boolean | AttrOrExprRef] = false
)

trait ExpressionLike {
  ...
  def isAggregation: Boolean = false
  def isCommutative: Boolean = false
}

So, considering example from the issue description, AGG could be marked as a aggregation operation that automatically makes it dependent of the number of elements in the input dataset which in turn is controlled by a filtering expression c. The WHERE clause could be defined in terms on pseudo Spline model like this:

operations: [
  {
    name: "WHERE",
    properties: {
      resize: {__exprId: "expr-111"}
    }
  }
]

attributes: [
  {
    id: "attr-a",
    name: "a"
  },
  {
    id: "attr-b",
    name: "b",
    childRefs: [{__exprId: "expr-222"}]
  },
]

expressions: [
  {
    id: "expr-111",
    name: "c"
  },
  {
    id: "expr-222",
    name: "AGG",
    isAggregation: true,
    childRefs: [{__exprId: "attr-a"}]
  },
]

As seen, the attribute b directly depends only on the attribute a through the expression expr-222. But because the expression expr-222 is an aggregation expression we look for the closest expression or attribute in the preceding sub-graph that influence the number of elements in the dataset (resize != false). That appears to be expression c (expr-111) in the WHERE operation. So we can implicitly add the expression c in the b's dependency list.

If the AGG is also marked as isCommutative: false then we would also look for the closest expression or attribute involved in the row reordering, that we could find in one of the ORDER BY operations for example.

A note for further thinking - how to model e.g. distinct operation that changes the number of elements, but preserves the dataset cardinality? How would the dependency from the MAX/MIN and SUM aggregation expressions could look like in that context?