Skip to content

opt: improve functional dependencies performance for equalities #83963

@DrewKimball

Description

@DrewKimball

Describe the problem

Currently, sets of equivalent columns are represented inefficiently in functional dependencies. Consider a set of three equivalent columns (a, b, c). A FuncDepSet would represent this equivalence as (a=b,c), (b=a,c), (c=a,b), which would require 6 opt.ColSet structs to be allocated. In general, the number of opt.ColSets needed is 2n where n is the number of columns in the equivalence. This can cause a large number of allocations when there are a large number of expressions in the memo with many equivalent columns, especially once the columns exceed the size of the small set.

To Reproduce

Profiling TPCH Q2 shows many allocations resulting from handling equivalencies. Additionally, customers have run into this issue causing long planning time.

Expected behavior

Each equivalence group should be represented by a single opt.ColSet rather than 2n of them.

Metadata

Metadata

Assignees

Labels

C-bugCode not up to spec/doc, specs & docs deemed correct. Solution expected to change code/behavior.T-sql-queriesSQL Queries Team

Type

No type

Projects

Status

Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions