engineering/java-topology
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
java-topology/docs/tickets/mongodb-0001-relevant-tag-first-notfirst-linear-scan.md
russell@unturf.com 9934133dcf whitepaper: 312 sites / 151 ecosystems — wave2+3 defect tables and PDF rebuild 
Add 88 new defect entries to HIGH and MEDIUM tables:
  HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
        vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
        tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
        allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
        mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
        linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
        perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002

  MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
          cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
          pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
          ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
          r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
          ovs-0001, onos-0003, odl-0002, jetty-0001

PDF: 976K
2026-03-27 15:23:43 -04:00

1.9 KiB
Raw Permalink Blame History

mongodb-0001: RelevantTag first/notFirst vector linear membership scan

Target: mongodb/mongo File: src/mongo/db/query/index_tag.h, src/mongo/db/query/planner_ixselect.cpp Severity: MEDIUM Pattern: CWE-407 — O(n) membership test inside loop → O(n²)

Description

RelevantTag (used during index selection in the query planner) stores the set of index IDs that can satisfy a predicate in two std::vector<size_t> fields: first (leading-field indices) and notFirst (non-leading-field indices).

Three functions in planner_ixselect.cpp perform O(n) linear std::find scans on these vectors inside loops over AST children:

  • isIndexAssigned() — called while stripping invalid compound-wildcard index assignments (loop over children × std::find on first/notFirst)
  • stripInvalidAssignmentsToTextIndex() — loop over AND children × std::find on first/notFirst
  • removeIndexRelevantTag() — called from several strip-invalid loops × std::find + erase on first/notFirst

A query with P predicates each tagged with I candidate indices executes O(P × I) linear probes → O(P·I²) total work for the strip passes.

Reproduction

A compound text or 2dsphere query with many predicates and many applicable indices triggers repeated stripInvalidAssignments* calls. Each call does O(predicates × indices) linear scans over the tag vectors.

Fix

Change RelevantTag::first and RelevantTag::notFirst from std::vector<size_t> to std::unordered_set<size_t>. Membership tests become O(1); iteration and copy semantics remain the same.

See defects/mongodb/patch/0001.patch.

Complexity

Operation Before After
membership test (isIndexAssigned) O(n) O(1)
removeIndexRelevantTag O(n) search + O(n) erase O(1) each
strip pass total O(P·I) O(P)