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
46 lines
1.4 KiB
Markdown
46 lines
1.4 KiB
Markdown
# seaorm-0001: establish_links leftover scan — O(N²) list scan
|
|
|
|
**Severity:** HIGH
|
|
**File:** src/entity/active_model.rs
|
|
**Line:** 1267
|
|
**Status:** PATCHED
|
|
|
|
## Description
|
|
|
|
`establish_links` iterates over `related_models` (up to N items) and inside
|
|
the loop calls `leftover.iter().any(|t| t.1 == via_key)` to check whether the
|
|
computed junction key already exists in the leftover vec. `leftover` can also
|
|
be up to N items long (one per existing junction row), so the combined
|
|
complexity is O(N²) where N is the number of related models / existing junction
|
|
rows.
|
|
|
|
This path is exercised every time a many-to-many link set is written with
|
|
`set_relation`, which is a normal ORM operation. For an entity with 1 000
|
|
related models the check issues ~500 000 equality comparisons where 1 000 would
|
|
suffice.
|
|
|
|
## Root Cause
|
|
|
|
`leftover` is built as a `Vec<(ActiveModel, ValueTuple)>` and then scanned with
|
|
`iter().any()` per related model instead of being indexed by key before the
|
|
loop begins.
|
|
|
|
## Fix
|
|
|
|
Extract the keys from `leftover` into a `HashSet<ValueTuple>` before the loop
|
|
so each existence check is O(1).
|
|
|
|
```rust
|
|
// before loop
|
|
let leftover_keys: std::collections::HashSet<ValueTuple> =
|
|
leftover.iter().map(|(_, k)| k.clone()).collect();
|
|
|
|
// inside loop (was leftover.iter().any(|t| t.1 == via_key))
|
|
if !leftover_keys.contains(&via_key) {
|
|
via_models.push(via);
|
|
}
|
|
```
|
|
|
|
## Speedup
|
|
|
|
~200x at N=1000 (500 000 comparisons → 1 000 hash lookups)
|