pingcap / pingcap/tidb

pkg/executor/infoschema_reader.go — view column lookup can become O(columns²)

Open
#68,524 0 comments 0 reactions 0 assignees View on GitHub
type/enhancement
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.