russell@unturf.com
d4ed2dff91
Hibernate (5 HIGH): addColumn/addReferencedColumn/addIndex ArrayList→LinkedHashSet (19x) FK second-pass LinkedHashSet, orderHierarchy LinkedHashSet MyBatis (1 MEDIUM): sortConstructorMappings indexOf→HashMap (12x) EF Core (2 HIGH + 1 MEDIUM): FindGenerationProperty HashSet (250x), AddPrincipals HashSet (250x), FK discovery HashSet (6x) Diesel (3 MEDIUM): SQLite/MySQL row position()→BTreeMap (51x) SQLAlchemy (2 HIGH): _values_bindparam Set (500x), evaluated_keys Set (500x) Peewee (1 MEDIUM): _SortedFieldList.index() bisect (42x) Sequelize (2 HIGH): bulkInsert Set (50x), expandIncludeAll Set (250x) TypeORM (3 HIGH): OrmUtils.uniq Map (500x), diffColumns Set (125x), updatedColumns Set (100x) Doctrine ORM (1 HIGH + 2 MEDIUM): hydrator discriminator (26x), addSubClass (250x), SqlWalker partial (130x) GORM (1 MEDIUM): sortCallbacks getRIndex→map (194x) SQLite: SqliteTest unit proof 4/4 PASS (101x) Unit tests: all PASS — Hibernate/MyBatis/EfCore/Diesel/SQLAlchemy/Peewee/ Sequelize/TypeORM/Doctrine/GORM Whitepaper: 157 sites, 62 ecosystems; PDF 752K
105 lines
3.4 KiB
Markdown
105 lines
3.4 KiB
Markdown
# doctrine-orm-0001 — AbstractHydrator: O(rows × subclasses) discriminatorValues linear scan per result row
|
||
|
||
**Status:** OPEN
|
||
**Severity:** HIGH
|
||
**Component:** `doctrine/orm` — `src/Doctrine/ORM/Internal/Hydration/AbstractHydrator.php`
|
||
**Affects:** All queries over inheritance hierarchies (CTI/STI) that return multiple rows
|
||
|
||
---
|
||
|
||
## Root Cause
|
||
|
||
`AbstractHydrator.php:328` — inside `gatherRowData()`, called once per DB result row:
|
||
|
||
```php
|
||
// DEFECTIVE — O(subclasses) per row, per column with inheritance field collision
|
||
if (
|
||
isset($cacheKeyInfo['discriminatorColumn'], $data[$cacheKeyInfo['discriminatorColumn']])
|
||
&& ! in_array((string) $data[$cacheKeyInfo['discriminatorColumn']], $cacheKeyInfo['discriminatorValues'], true)
|
||
) {
|
||
break;
|
||
}
|
||
```
|
||
|
||
`$cacheKeyInfo['discriminatorValues']` is a PHP array of discriminator string values, built in
|
||
`getDiscriminatorValues()` (line 541–551) from `$classMetadata->subClasses[]`.
|
||
`in_array` performs a full linear scan of this array.
|
||
|
||
The outer loop (`foreach ($data as $key => $value)`) runs once per column per result row.
|
||
`gatherRowData()` is called per row in the `while` loop at `AbstractHydrator.php:114`:
|
||
|
||
```php
|
||
while (true) {
|
||
$row = $this->statement()->fetchAssociative();
|
||
...
|
||
$this->hydrateRowData($row, $result); // calls gatherRowData()
|
||
```
|
||
|
||
`ObjectHydrator.php:327` confirms this is the hot path:
|
||
|
||
```php
|
||
$rowData = $this->gatherRowData($row, $id, $nonemptyComponents);
|
||
```
|
||
|
||
The same pattern appears in `SimpleObjectHydrator.php:128`:
|
||
|
||
```php
|
||
if (isset($cacheKeyInfo['discriminatorValues']) && ! in_array((string) $discrColumnValue, $cacheKeyInfo['discriminatorValues'], true)) {
|
||
continue;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## Complexity Analysis
|
||
|
||
| Metric | Defective | Fixed |
|
||
|--------|-----------|-------|
|
||
| Discriminator check per row | O(subclasses) | O(1) |
|
||
| Full query (N rows, C affected columns) | O(N × C × subclasses) | O(N × C) |
|
||
| Growth pattern | Quadratic in subclasses | Linear |
|
||
|
||
For a CTI hierarchy with 50 subclasses, a 10-column SELECT returning 10,000 rows performs
|
||
50 × 10 × 10,000 = 5,000,000 comparisons for discriminator membership alone.
|
||
|
||
---
|
||
|
||
## Fix
|
||
|
||
`getDiscriminatorValues()` (line 541) builds a flat array. Change it to build a `Set`-equivalent
|
||
(`array` keyed by discriminator value for O(1) `isset` lookup):
|
||
|
||
```php
|
||
// FIXED — O(1) per row
|
||
private function getDiscriminatorValues(ClassMetadata $classMetadata): array
|
||
{
|
||
$values = [];
|
||
foreach ($classMetadata->subClasses as $subClass) {
|
||
$val = (string) $this->getClassMetadata($subClass)->discriminatorValue;
|
||
$values[$val] = true;
|
||
}
|
||
$values[(string) $classMetadata->discriminatorValue] = true;
|
||
return $values;
|
||
}
|
||
```
|
||
|
||
Then change both call sites from `in_array($val, $discriminatorValues, true)` to
|
||
`isset($discriminatorValues[$val])`.
|
||
|
||
---
|
||
|
||
## Call Sites
|
||
|
||
| File | Line | Path |
|
||
|------|------|------|
|
||
| `src/Internal/Hydration/AbstractHydrator.php` | 328 | `gatherRowData()` — ObjectHydrator hot path |
|
||
| `src/Internal/Hydration/SimpleObjectHydrator.php` | 128 | `hydrateRowData()` — SimpleObjectHydrator hot path |
|
||
|
||
---
|
||
|
||
## Speedup Estimate
|
||
|
||
For queries over CTI/STI hierarchies with many subclasses: **linear in subclass count**.
|
||
A hierarchy with S subclasses sees S× speedup on the discriminator-check portion of hydration.
|
||
Real-world inheritance hierarchies of 20–100 subclasses → 20–100× reduction in comparisons
|
||
on the discriminator check path.
|