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
1 KiB
1 KiB
rails-0005: SchemaDumper — O(I×C) constraint_names Array#include? in indexes.reject
Severity: MEDIUM File: activerecord/lib/active_record/schema_dumper.rb Lines: 247-255 Status: PATCHED
Description
SchemaDumper#indexes_in_create builds exclusion_constraint_names and
unique_constraint_names as Arrays via .collect(&:name), then calls include? on each
inside indexes.reject { ... }. With I indexes and C constraints, each reject pass
costs O(I×C).
This runs once per table during db:schema:dump, so with T tables the total is
O(T × I × C). In large schemas with many tables and constraints this is measurably slow.
Root Cause
.collect(&:name) returns an Array. The subsequent Array#include? is O(C) per index.
Fix
# BEFORE
exclusion_constraint_names = exclusion_constraints.collect(&:name)
# AFTER
exclusion_constraint_names = exclusion_constraints.collect(&:name).to_set
Same fix for unique_constraint_names.
Speedup
~50x at I=500 indexes, C=200 constraints