ExportXMLWordPrintableJSON

    • Type: Improvement
    • Resolution: Duplicate
    • Priority: Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • None
    • Query Optimization
    • None
    • None
    • None
    • None
    • None
    • None
    • None

      Summary

      With more accurate cardinality estimates, the join optimizer switches some TPC-H plans from an index nested loop join (INLJ) to a COLLSCAN + hash join (HJ), and the new plans are 2.8–7.3x slower when the data is in memory, the regime the join plan stability tests and most working sets run in. When the cache is cold they are no faster (0.98–1.04x). The join cost model appears to misprice INLJ probes against COLLSCAN + HJ in the CPU-bound (cached) regime.

      The previous plans only won because of underestimates: SERVER-139137 replaces the sampling "one row" clamp and raw 1/n estimates for equality values absent from or seen once in the sample, which corrects join cardinality estimates (see below) and exposes this.

      Evidence

      Branch: starzia/SERVER-139137 at dc4baf401a3 ([PR #66573|https://github.com/10gen/mongo/pull/66573]]) vs. master 797084f80017. TPC-H scale 0.1, server settings from query_golden_join_optimization_plan_stability.yml (1GB WiredTiger cache, dataset ~285MB). Queries are from jstests/query_golden/join_opt/plan_stability_tpch_fuzzed.js. Results are identical in every case.

      idx rows master plan (cost, est. rows) branch plan (cost, est. rows) keys+docs master -> branch warm median master -> branch cold median master -> branch
      219 24 INLJ chain (0.892, 0.069) INLJ over HJ l_partkey = p_partkey with part COLLSCAN (47.926, 16.95) 1,020 -> 20,534 2.88 -> 8.20 ms (2.84x) 1442 -> 1439 ms (1.00x)
      217 10 INLJ chain (0.874, 0.0029) INLJ over HJ ps_partkey = l_partkey with partsupp COLLSCAN (170.58, 1.63) 5,860 -> 81,188 6.20 -> 45.49 ms (7.33x) 1434 -> 1487 ms (1.04x)
      221 21 INLJ chain (0.919, 0.055) INLJ over HJ with partsupp COLLSCAN (195.6, 31.0) 6,172 -> 81,292 5.73 -> 27.88 ms (4.87x) 1442 -> 1470 ms (1.02x)
      10 (control) 1 NLJ/INLJ (165.8) INLJ + 2 HJ (169.65) 80,107 -> 81,029 24.59 -> 24.34 ms (0.99x) 205 -> 201 ms (0.98x)
      • Warm: 3 warmups + 15 timed runs x 5 alternating blocks (n=75 per binary per query), client wall time.
      • Cold: 7 runs per query per binary; mongod restarted and OS page cache dropped before every run. Cold runs include ~1.3s of fixed start-up work (sampling, catalog), which masks small IO differences; a dataset much larger than the cache could behave differently.
      • The branch's estimates are the accurate ones. E.g. the lineitem point-date subjoin of idx 219 (l_shipdate = 1998-03-11) is estimated at 1 row on master and 246 on the branch; the actual is 243. On plan_stability_subjoin_cardinality_md.js, all 6 estimates the branch changes become more accurate (geometric-mean q-error 12.6 -> 1.25), none get worse.
      • idx 219 on the branch is a near tie: the winning HJ plan costs 47.9264 and the master-shaped INLJ plan is the runner-up at 47.9296.

      Likely cause

      join_estimates.cpp prices a document at ~612ns of CPU, a sequential IO page at 261.1x that and a random IO page at 1411.4x (calibrated by buildscripts/cost_model/join_start.py), i.e. a cold-cache, IO-bound model. With accurate (larger) outer cardinalities, the INLJ probes are charged as random IO and lose to a sequential COLLSCAN + HJ, although with the data cached the probes are cheap and the scan processes 20k–80k documents. Note that the plan stability keys+docs metric overstates the slowdown (13–20x vs. 3–7x in time), since it weights sequential and random accesses equally.

      Suggested next steps

      * Revisit the INLJ vs. COLLSCAN + HJ crossover, e.g. account for the share of the working set expected to be cached, or recalibrate the IO coefficients for in-memory data.
      * Use idx 217, 219 and 221 as regression tests; SERVER-139137 should not enable its improved estimates for join optimization until this is addressed.

      Reproduction

      Repro scripts (mongod start-up, TPC-H restore, warm/cold timing, explains) are available from the reporter. Build master and the branch with bazel build --dbg=False --opt=on install-dist-test, restore tpch-0.1-normalized.archive.gz from s3://query-benchmark-data/tpc-h/ as jstests/libs/query/tpch_dataset.js does, and run the idx 217/219/221 aggregate commands from jstests/query_golden/expected_output/plan_stability_tpch_fuzzed (convert the

      {"$date": ...}

      literals to Dates first, otherwise idx 219 returns no rows).

            Assignee:
            Unassigned
            Reporter:
            Steve Tarzia
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved: