[Fdo-trac] [fdo-trac] #1019: Better handle large chains of OR conditions
FDO
trac_fdo at osgeo.org
Wed Oct 21 05:26:51 PDT 2026
#1019: Better handle large chains of OR conditions
---------------------+----------------------
Reporter: jng | Owner: jng
Type: defect | Status: closed
Priority: major | Milestone: 4.2.0
Component: FDO API | Version:
Severity: 3 | Resolution: fixed
Keywords: | External ID:
---------------------+----------------------
Changes (by jng):
* resolution: => fixed
* status: assigned => closed
Comment:
In [changeset:"8418" 8418]:
{{{#!CommitTicketReference repository="" revision="8418"
Handle filter trees whose depth grows with the number of terms
A selection of features is rendered by turning its identity values into a
disjunction with one comparison per selected feature, so a filter's depth
grows
with the size of the selection. Selecting more than 1000 features from a
SQLite
feature source failed with "Expression tree is too large (maximum depth
1000)",
because the provider emitted that tree as SQL of the same depth and the
bundled
SQLite build enforces SQLITE_MAX_EXPR_DEPTH (Providers/SQLite/Src/sqlite/
sqliteLimit.h). Larger selections did not fail but terminated the process:
the
Expression Engine's optimizer and the filter tree's own destructor both
walk the
tree recursively, one stack frame per term.
Reported against MapGuide as https://trac.osgeo.org/mapguide/ticket/2751.
SQLite provider
- SltQueryTranslator collects the terms of a disjunction with an
explicit stack
and, above 900 of them, translates it differently instead of emitting
SQL of
the same depth. Terms that are all "property = value" comparisons on
one
property become an IN list, which is both shallower and smaller; any
other
disjunction becomes a balanced tree whose depth grows with the
logarithm of the
term count. Shorter disjunctions keep the translation they had, so no
statement
changes for a filter that already worked.
Expression Engine
- OptimizeFilter only rewrites a filter in order to merge spatial
conditions.
Without one it rebuilt an equivalent tree at one stack frame per term,
which is
what exhausted the stack before the provider was reached. It now scans
the tree
iteratively for a spatial condition and returns the filter unchanged
when there
is none; a filter that has one takes the existing path, so the
optimizer's
output for those is unchanged.
Filter tree teardown
- FdoBinaryLogicalOperator's destructor released its operands, which
released
theirs. It now walks an explicit worklist, detaching and deleting a
child only
when this node is its sole owner (GetRefCount() == 1) and releasing a
shared
child exactly as before. Releasing a chain of a few thousand terms no
longer
depends on the stack.
Tests
- SQLite SelectTest.TestLargeOrChainFilter: 1100 features selected by an
identity-value disjunction, and by a disjunction of compound terms,
one term
per feature. Fails with the ticket's message when the provider change
is
removed.
- SDF FdoExpressionFunctionTest.RunOptimizerLongChain: a 5000-term
disjunction
taken through OptimizeFilter, then counted back without recursing.
Terminated
with 0xC00000FD when the optimizer change is removed.
- FDO Core FilterTest.testDeepFilterChain: builds a 5000-term chain,
checks its
operand count without recursing, and releases it. Terminated with
0xC00000FD
when the teardown change is removed.
Verified in Debug and Release: FDOCore 152 tests, SDF 125, SQLite 100, all
passing. The CRT debug heap reports no leak for FilterTest, and the SDF
fixture's
report carries the same 255-block signature with and without the new test
(those
blocks are pre-existing in that fixture).
Fixes #1019
}}}
--
Ticket URL: <https://trac.osgeo.org/fdo/ticket/1019#comment:1>
FDO <http://fdo.osgeo.org/>
Feature Data Objects
More information about the fdo-trac
mailing list