search

cockroachdb / cockroach

CockroachDB — the cloud native, distributed SQL database designed for high availability, effortless scale, and control over data placement.
https://www.cockroachlabs.com
Other
30.1k stars 3.81k forks source link

opt: improve functional dependencies performance for equalities #83963

Open DrewKimball opened 2 years ago

DrewKimball commented 2 years ago

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.

github-actions[bot] commented 10 months ago

We have marked this issue as stale because it has been inactive for 18 months. If this issue is still relevant, removing the stale label or adding a comment will keep it active. Otherwise, we'll close it in 10 days to keep the issue queue tidy. Thank you for your contribution to CockroachDB!