1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/**
* Copyright (C) 2023-present MongoDB, Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the Server Side Public License, version 1,
* as published by MongoDB, Inc.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* Server Side Public License for more details.
*
* You should have received a copy of the Server Side Public License
* along with this program. If not, see
* <http://www.mongodb.com/licensing/server-side-public-license>.
*
* As a special exception, the copyright holders give permission to link the
* code of portions of this program with the OpenSSL library under certain
* conditions as described in each individual source file and distribute
* linked combinations including the program with the OpenSSL library. You
* must comply with the Server Side Public License in all respects for
* all of the code used other than as permitted herein. If you modify file(s)
* with this exception, you may extend this exception to your version of the
* file(s), but you are not obligated to do so. If you do not wish to do so,
* delete this exception statement from your version. If you delete this
* exception statement from all source files in the program, then also delete
* it in the license file.
*/
#pragma once
#include <boost/optional/optional.hpp>
#include <cmath>
#include <memory>
namespace mongo {
/**
* Eventually we'll be supporting multiple types of percentiles (discrete, continuous, approximate)
* and potentially multiple different algorithms for computing the approximate ones.
*
* The goal is to keep these algorithms MQL- and engine-agnostic with this interface.
*/
struct PercentileAlgorithm {
// We define "percentile" as:
// Percentile P(p) where 'p' is from [0.0, 1.0] on dataset 'D' with 'n', possibly duplicated,
// samples is value 'P' such that at least ceil(p*n) samples from 'D' are _less or equal_ to
// 'P' and no more than ceil(p*n) samples that are strictly _less_ than 'P'. Thus, p = 0 maps
// to the min of 'D' and p = 1 maps to the max of 'D'.
//
// Notice, that this definition is ambiguous. For example, on D = {1.0, 2.0, ..., 10.0} P(0.1)
// could be any value in [1.0, 2.0] range. For discrete percentiles the value 'P' _must_ be one
// of the samples from 'D' but it's still ambiguous as either 1.0 or 2.0 can be used.
//
// This definiton leads to the following computation of 0-based rank for percentile 'p' while
// resolving the ambiguity towards the lower rank.
static int computeTrueRank(int n, double p) {
if (p >= 1.0) {
return n - 1;
}
return std::max(0, static_cast<int>(std::ceil(n * p)) - 1);
}
virtual ~PercentileAlgorithm() {}
virtual void incorporate(double input) = 0;
virtual void incorporate(const std::vector<double>& inputs) = 0;
/**
* 'p' must be from [0, 1] range.
*
* It is always valid to call 'computePercentile()', however, if no input has been incorporated
* yet, all implementations must return 'boost::none'. It is allowed to incorporate more inputs
* after calling 'computePercentile()' and call it again (naturally, the result might differ
* depending on the new data).
*
* Note 1: the implementations are free to either return "none" or throw if they require setting
* up for computing a specific percentile but a different one is requested here.
*
* Note 2: the implementations might have different tradeoffs regarding balancing performance of
* ingress vs computing the percentile, so this interface provides no perfomance guarantees.
* Refer to the documentation of the specific implementations for details.
*/
virtual boost::optional<double> computePercentile(double p) = 0;
/**
* Computes multiple percentiles at once and might be more efficient than computing them one at
* a time. Same constraints apply as for 'computePercentile(double p)'. Returns an empty vector
* if no inputs have been incorporated.
*/
virtual std::vector<double> computePercentiles(const std::vector<double>& ps) = 0;
/*
* The owner might need a rough estimate of how much memory the algorithm is using.
*/
virtual long memUsageBytes() const = 0;
};
/**
* In sharded environment percentiles need to be partially computed on each shard and then combined
* together to compute the final result. 'TValue' type used to communicate the partial computation
* depends on the engine.
*/
template <typename TValue>
struct PartialPercentile {
virtual TValue serialize() = 0;
virtual void combine(const TValue& partial) = 0;
};
/**
* Factory methods for instantiating concrete algorithms.
*/
std::unique_ptr<PercentileAlgorithm> createDiscretePercentile();
std::unique_ptr<PercentileAlgorithm> createTDigest();
std::unique_ptr<PercentileAlgorithm> createTDigestDistributedClassic();
} // namespace mongo
|
