Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-66957

Histogram-based CE for SargableNodes based on the CE prototype

    • Type: Icon: Task Task
    • Resolution: Fixed
    • Priority: Icon: Major - P3 Major - P3
    • 6.1.0-rc0
    • Affects Version/s: None
    • Component/s: None
    • Labels:
    • Fully Compatible
    • QO 2022-06-13, QO 2022-06-27, QO 2022-07-11

      Implement histogram-based CE for SargableNodes based on the prototype implementation in branch "hist-ce".

      The goal of this task is to pick all relevant pieces from the 'hist-ce' branch, and implement basic histogram-based CE as follows:

      • Implement the CEInterface interface in a new class (e.g. HistogramCE) similar to the ones for heuristic- and sampling- based CE.
      • This new class should provide transport methods for the following Nodes: SargableNode, ScanNode. All other nodes should be processed by a catch-all transport that uses heuristic estimation.
      • Figure out how to extract the necessary information from Sargable nodes in order to use a histogram directly to estimate their cardinality.
      • Estimate implicit/explicit Boolean expressions inside a single Sargable node via exponential backoff. Reuse the formulas for exponential backoff from SERVER-67166.
      • Add an optimizer knob to disable/enable histogram-based CE.
      • Implement tests as unit tests. For testing purposes hack around the lack of a statistics module that can provide us histograms. There should be two types of tests:
        • Correctness tests - these tests use hand-crafted histograms and predicates that verify that given some known histogram CE produces a certain (hand-verified) estimate.
        • Accuracy tests - these tests generate some data, create a histogram, and run the estimator. The result is compared either against a hand-verified result, or to a result produced via running a query over the input dataset. The hist-ce prototype has examples how this is done.

            Assignee:
            alya.berciu@mongodb.com Alya Berciu
            Reporter:
            timour.katchaounov@mongodb.com Timour Katchaounov
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated:
              Resolved: