russell@unturf.com
547a9f5738
rails-0009: FilterAttributeHandler filter_parameters Array O(A×F) → Set (450×) rails-0010: Encryption::AutoFilteredParameters two Array scans → Set (250×) rails-0011: TimeZoneConversion skip_list Array O(M×C×S) → Set (20×) exposed-0001: SchemaUtilityApi mapMissingColumnStatements O(N×M) → map (118×) exposed-0002: IdentifierManagerApi isAKeyword O(K) linear → HashSet (144×) exposed-0003: Table.clone consParams.map fresh List → hoisted HashSet (6×) seaorm-0001: active_model establish_links leftover.any O(N²) → HashSet (501×) seaorm-0002: rbac engine group_permissions .values().find() → HashMap by ID (502×) seaorm-0003: schema builder sorted_tables Vec::contains → HashSet (500×) seaorm-0004: TopologicalSort from_iter seen Vec O(N²) → BTreeSet (28×) Unit tests: RailsTest 11/11, ExposedTest 3/3, SeaORMTest 4/4 PASS Whitepaper: 157→167 sites, 62→64 ecosystems; §13.12 ORM Wave 2 added
37 lines
1.3 KiB
Markdown
37 lines
1.3 KiB
Markdown
# rails-0006: PostgreSQL schema_statements — O(C×I) include_columns Array#include? in reject
|
||
|
||
**Severity:** MEDIUM
|
||
**File:** activerecord/lib/active_record/connection_adapters/postgresql/schema_statements.rb
|
||
**Line:** 133-139
|
||
**Status:** PATCHED
|
||
|
||
## Description
|
||
|
||
When loading PostgreSQL index metadata, `include_columns` is built as an Array by
|
||
splitting and mapping the include clause. Then `columns.reject! { |c| include_columns.include?(c) }`
|
||
scans the full include_columns Array for each column — O(C×I) where C = column count
|
||
and I = include_column count.
|
||
|
||
This runs during every schema reflection call (e.g., `connection.indexes(table_name)`),
|
||
which is invoked on every model class load and on every `db:schema:dump`.
|
||
|
||
## Root Cause
|
||
|
||
`include.split(",").map { ... }` returns an Array. The subsequent `Array#include?` in the
|
||
`reject!` block is O(I) per column.
|
||
|
||
## Fix
|
||
|
||
```ruby
|
||
# BEFORE
|
||
include_columns = include ? include.split(",").map { |c| Utils.unquote_identifier(c.strip.gsub('""', '"')) } : []
|
||
columns.reject! { |c| include_columns.include?(c) }
|
||
|
||
# AFTER
|
||
include_set = include ? include.split(",").map { |c| Utils.unquote_identifier(c.strip.gsub('""', '"')) }.to_set : Set.new
|
||
columns.reject! { |c| include_set.include?(c) }
|
||
```
|
||
|
||
## Speedup
|
||
|
||
~50x at C=500 columns, I=200 include columns
|