Functional dependency analysis proposal [DRAFT]

[AngleNet]

Motivation

When we create a table, we could specify primary key, unique indexes, unique constraints for it. These constraints could be further exploited via functional dependencies between attributes while optimizing queries, such as calculating cost more accurately, removing unnecessary operators.

For example, there is a table create table tb(a int) and a query select distinct a + 1 from tb. The attribute a functionally determines a+1 . If a is a primary key, we could rewrite the query to select a+1 from tb by removing unnecessary distinct which could introduce a sort operator to eliminate duplicates.

Design Goal

• Solve Feature: functional dependency optimization #7438
• Describe how to represent and analyze functional dependencies, uniqueness, equalities and ordering for SQL operators
• Describe optimizations using the above analysis, such as distinct elimination.

Concepts

​ The main concepts involved in this doc are borrowed from [1]. We just list the most fundamental ones here.

• Functional dependency: let $x, y$ are attributes of a table $R$, if we have the value of $x$, we could get a deterministic value of $y$ . We say $x$ determines $y$ . The analysis is mainly based on the transitivity axiom ( $x \longrightarrow y, y \longrightarrow z \Longrightarrow x \longrightarrow z$ ), however, the semantics will be different when we introduce $null$ to the domain of $x$ and $y$. We borrow lax functional dependency from [1] to solve this
• Equivalence constraints: it models an equal relation. For example, the query select a as b, a from numbers. We could say $a$ equals to $b$. It's semantics also suffers from $nulls$. We also borrow lax equivalence constraints from [1] to solve this.

Basic Idea

We represent functional dependencies and equivalence constraint both in a directed hypergraph in which vertexes are determinants and dependents, edges are dependencies and constraints. To determine the set of dependencies that hold in an entire expression $e$, one can simply recursively traverse the expression tree in a postfix manner and compute the dependencies and equivalence constraint that hold for a given operator once the dependencies and equivalence constraint of its inputs have been determined. The algorithm details are listed in [1].

Implementations

later

Prototype

later

References

[1] Exploiting Functional Dependence in Query Optimization

[AngleNet]

The above doc is mainly from Paulley's paper: Exploiting Functional Dependence in Query Optimization. Thank him for the formal analysis work.

[Xuanwo]

Hi, @AngleNet. Thanks for your contribution!

However, this draft RFC is not actionable to me:

• The formal analysis is not the most critical part of RFC. They take too long, maybe we can refer to the paper directly if there are not too many changes.
• This RFC leaks the part of the detailed problem. For example, which problem this RFC want to address? The way to reproduce the problem.
• This RFC leaks the part of the implementation. How will we address the problem? Is there any other ways? What are the benefits and drawbacks between them?

Hoping those concerns can be addressed in the future.

BTW, take a look at this RFC example will be great!

[AngleNet]

@Xuanwo HI. Thank you point these problems out. I also think the formal analysis is too long to address. I will reference them from original giant paper here. For the implementations, I plan to put a prototype later.