Incorrect functional dependency analysis in index costing
- Dominant language
- Go
- Stars
- 24.4k
- Forks
- 873
- Avg merge
- 1d 8h
- Merged PRs (30d)
- 120
Description
The following function in `costed_index_scan.go` is incorrect:
```
func (c *conjCollector) getFds() *sql.FuncDepSet {
constCols := sql.ColSet{}
c.constant.ForEach(func(i int) {
constCols.Add(sql.ColumnId(i))
})
return sql.NewLookupFDs(c.stat.FuncDeps(), c.stat.ColSet(), sql.ColSet{}, constCols, nil)
}
```
The purpose of this function is to run a functional dependency analysis on a set of conjunctions, based on identifying which columns are bound to constant values by the filter expressions. But there's a subtle problem: `conjCollector` numbers fields based on their position in the index, while`c.stat` numbers fields based on their position in the table, and there is no mapping in scope that can translate between them. As a result, the wrong columns are marked as constant. This can influence how the index is costed.
Amazingly, it's very difficult to design a test case where this produces unexpected results, because in the most common case, we use the FDS to determine whether the query has at most one result and can be a point lookup, and that only happens if every column in the index gets marked as const. Since the size of `c.constant` can't exceed the number of columns in the index, then there are two main cases:
- An N-column index has fewer than N constant columns, so no matter how those constants get mapped, we'll never incorrectly deduce that the index can be used as a point lookup.
- An N-column index has exactly N constant columns, which gets detected and handled as a special case before index costing even begins.
So I don't think this issue can effect the result of analyzing simple lookups, but it can affect join planning.
The simplest way to observe this is just to comment out `constCols.Add(sql.ColumnId(i))` and see which plan tests change. Most of the changed tests feel like a lateral move: removing these incorrect inputs to the FDS modifies the costing for some plans, causing a slightly different join type to be chosen.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in costed_index_scan.go at conjCollector.getFds and trace how index-position columns and table-position columns are represented. Run the relevant plan tests, comparing results with constCols.Add(sql.ColumnId(i)) disabled, then identify the correct column correspondence. Done means functional dependency analysis uses the intended constant columns without introducing incorrect costing changes.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100