pkg/executor/infoschema_reader.go — view column lookup can become O(columns²)
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
• Problem Localization (Core)
When reading view columns in `information_schema.columns`, a linear column name match is performed in a loop over each column:
- View schema/output name cache: `pkg/executor/infoschema_reader.go:1063`
- Column-by-column lookup: `pkg/executor/infoschema_reader.go:1094`
- The called function performs a linear scan: `pkg/expression/simple_rewriter.go:96`
This causes this part of the "single wide view" to degenerate from O(C) to O(C²).
—
Execution Chain
1. `TableColumns` calls `hugeMemTableRetriever`: `pkg/executor/builder.go:3410`
2. `setDataForColumns()` iterates through the schema/table: `pkg/executor/infoschema_reader.go:1005`
3. When encountering a view, it first builds and caches the view logical plan: `pkg/executor/infoschema_reader.go:1063`
4. Then, for each column name in the view, it linearly searches for the index in `viewOutputNames` and retrieves the type: `pkg/executor/infoschema_reader.go:1087`
—
Why is this a substantial problem?
- When the number of columns `C` is large, `for cols { linear search in outputNames }` is explicitly O(C²).
- This process is easily triggered by high-frequency queries (monitoring/metadata probing queries) in paths like `information_schema.columns` and `show columns`. - The logic repeatedly retrieves the map and performs a linear scan within the lock, amplifying constant overhead.
---
Semantic Constraints (Must be maintained in the fix)
1. Maintain consistent behavior for duplicate names: FindFieldNameIdxByColName returns the "first matching" index. The cached map must be written to the first index and cannot be overwritten by subsequent writes.
2. Concurrency safety: Currently, viewMu protects view-related caches; new cache structures must reuse the same lock.
3. Failure tolerance: When BuildDataSourceFromView fails, it currently issues a warning and is skipped; this should not be changed.
---
Suggested Fix (Minimum Changes)
Add a cache to hugeMemTableRetriever:
- viewOutputIdxMap map[int64]map[string]int (tableID -> colName -> firstIndex)
Write timing:
- Initialize simultaneously with viewSchemaMap/viewOutputNamesMap (after tbl.IsView()'s first successful build).
Query Timing:
- Retrieve `idx` directly in the column loop using O(1) time and replace it with `FindFieldNameIdxByColName(...)`.
This reduces the complexity from O(C²) to O(C) while maintaining the semantics.
---
Relationship with `show` Path
`show` also has a linear lookup with the same pattern: `pkg/executor/show.go:3128`.
However, `show` is usually a single-table call, so the benefits are not as significant as `information_schema.columns`. It is recommended to modify `infoschema_reader` first, and then reuse the same approach for minor follow-ups.
Contributor guide
Assessment
This issue has not been assessed yet.