[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