82 lines
2.5 KiB
Markdown
82 lines
2.5 KiB
Markdown
# UNDF: UNDF-2026-000000300
|
||
# sqlite-0003 — `sqlite3CreateForeignKey`: O(F×C) column resolution with `sqlite3StrICmp` inside nested loop
|
||
|
||
## Status
|
||
PATCHED
|
||
|
||
## Severity
|
||
MEDIUM (>50× speedup at F=100 FK cols, C=1000 table cols)
|
||
|
||
## Location
|
||
`src/build.c`, function `sqlite3CreateForeignKey()`, lines ~3680-3688
|
||
|
||
## Description
|
||
When resolving FK source column names to column indices during `CREATE TABLE`
|
||
parsing, SQLite uses a nested loop:
|
||
|
||
```c
|
||
for(i=0; i<nCol; i++){ /* F = number of FK columns */
|
||
int j;
|
||
for(j=0; j<p->nCol; j++){ /* C = total columns in table */
|
||
if( sqlite3StrICmp(p->aCol[j].zCnName, pFromCol->a[i].zEName)==0 ){
|
||
pFKey->aCol[i].iFrom = j;
|
||
break;
|
||
}
|
||
}
|
||
if( j>=p->nCol ){
|
||
/* error: unknown column */
|
||
}
|
||
}
|
||
```
|
||
|
||
Total cost: O(F × C) with `sqlite3StrICmp` (case-insensitive string compare)
|
||
for each comparison.
|
||
|
||
`sqlite3ColumnIndex(Table *, const char *)` already exists and uses the
|
||
pre-built `pTab->aHx[]` hash table for amortized-O(1) case-insensitive
|
||
column lookup. The table `p` already has `aHx` fully populated at FK parsing
|
||
time (columns are parsed before REFERENCES clauses in SQL syntax).
|
||
|
||
## Patch
|
||
|
||
```c
|
||
--- a/src/build.c
|
||
+++ b/src/build.c
|
||
@@ -3680,14 +3680,17 @@ void sqlite3CreateForeignKey(...){
|
||
if( pFromCol==0 ){
|
||
pFKey->aCol[0].iFrom = p->nCol-1;
|
||
}else{
|
||
for(i=0; i<nCol; i++){
|
||
- int j;
|
||
- for(j=0; j<p->nCol; j++){
|
||
- if( sqlite3StrICmp(p->aCol[j].zCnName, pFromCol->a[i].zEName)==0 ){
|
||
- pFKey->aCol[i].iFrom = j;
|
||
- break;
|
||
- }
|
||
- }
|
||
- if( j>=p->nCol ){
|
||
+ /* CWE-407 fix (sqlite-0003): use hash-based sqlite3ColumnIndex instead
|
||
+ ** of O(p->nCol) sqlite3StrICmp inner loop. */
|
||
+ int j = sqlite3ColumnIndex(p, pFromCol->a[i].zEName);
|
||
+ if( j<0 ){
|
||
sqlite3ErrorMsg(pParse,
|
||
"unknown column \"%s\" in foreign key definition",
|
||
pFromCol->a[i].zEName);
|
||
goto fk_end;
|
||
+ }else{
|
||
+ pFKey->aCol[i].iFrom = j;
|
||
}
|
||
if( IN_RENAME_OBJECT ){
|
||
```
|
||
|
||
## Speedup
|
||
At F=100, C=1000: O(F×C)=100,000 `sqlite3StrICmp` calls → O(F)=100 hash
|
||
lookups → **1000× speedup**.
|
||
Typical case (F=5, C=100): O(500) → O(5) → **100× speedup**.
|
||
|
||
The `CREATE TABLE` stage is compilation, not runtime execution. Still matters
|
||
for schema-intensive workloads (migrations, ORM startup, test suites creating
|
||
many tables with wide FK column sets).
|
||
|
||
## Test
|
||
`defects/sqlite/unit/SqliteTest.java` — `sqlite-0003` section.
|