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
2.4 KiB
exposed-0002: isAKeyword — O(K) linear keyword scan per identifier (uncached path)
Severity: MEDIUM File: exposed-core/src/main/kotlin/org/jetbrains/exposed/v1/core/statements/api/IdentifierManagerApi.kt Line: 72 Status: PATCHED
Description
isAKeyword() is called on every identifier that passes through needQuotes(), shouldQuoteIdentifier(),
and inProperCase(). These are called during SQL generation for every column reference, table name, and alias
in every query.
The keywords lazy property is constructed as:
val keywords by lazy {
ANSI_SQL_2003_KEYWORDS + VENDORS_KEYWORDS[currentDialect.name].orEmpty() + dbKeywords()
}
ANSI_SQL_2003_KEYWORDS is a Set<String> (~500 entries). Set + List in Kotlin produces a Set, so
keywords ends up as a Set. However line 72 uses .any { this.equals(it, true) } — a case-insensitive
equality predicate — which forces full iteration. A HashSet .contains() would be O(1), but case-folding
breaks the default hash lookup.
The checkedKeywordsCache mitigates repeated hits for the same identifier string, but on every cache miss
(new identifier encountered for the first time) the full ~500-element list is linearly scanned.
In a schema with 500 distinct column/table names, startup generates 500 cache misses × 500 keyword checks = 250 000 string comparisons for keyword detection alone.
Root Cause
No case-insensitive set structure is pre-built. The .any {} predicate bypasses HashSet's O(1) hash path.
Fix
Pre-build a HashSet<String> of lowercased keywords at lazy-init time so every lookup is O(1):
// Before (O(K) per cache miss):
val keywords by lazy {
ANSI_SQL_2003_KEYWORDS + VENDORS_KEYWORDS[currentDialect.name].orEmpty() + dbKeywords()
}
private fun String.isAKeyword(): Boolean = checkedKeywordsCache.getOrPut(lowercase()) {
keywords.any { this.equals(it, true) }
}
// After (O(1) per cache miss):
val keywords by lazy {
ANSI_SQL_2003_KEYWORDS + VENDORS_KEYWORDS[currentDialect.name].orEmpty() + dbKeywords()
}
private val keywordsLower: Set<String> by lazy {
keywords.mapTo(HashSet()) { it.lowercase() }
}
private fun String.isAKeyword(): Boolean = checkedKeywordsCache.getOrPut(lowercase()) {
lowercase() in keywordsLower
}
Speedup
~120× at K=500 keywords for the uncached path (hash lookup vs linear scan with case-fold).