Repository: prometheus/prometheus (language: go)

Issue:
promql (histograms): Implement max/min for native histograms.
### Proposal

A max (and min) of a native histograms could be defined as the upper (lower) bound of the highest (lowest) bucket, thereby yielding a strict upper (lower) limit of the observed values. (The pull-based stateless scrape model of Prometheus doesn't allow tracking of the "true" highest (lowest) observed value.)

The question is how to utilize this definition in PromQL functions or aggregation operators. `max` and `min` are aggregation operators. We could incorporate the above definitions into those operators by using the max (min) value of a native histogram as defined above instead of the plain float value of a float sample when encountering a native histogram. Then we could still apply `max` (`min`) to a single native histogram to get its max (min) value, albeit without labels. (The labels could be retained by writing `max without () (my_single_histogram)`.)

However, if you actually want the max (min) of each histogram in a vector individually (probably quite common), you would more like a dedicated function (not aggregation!), presumably called `histogram_max` (`histogram_min`), which would apply to every histogram in a vector individually. To get the max of a vector of histograms, you would simply write `max(histogram_max(my_histogram_vector))`.

I guess the latter is the way to go, but happy to hear more thoughts.


Discussion / hints:
I would like to work on this!

Fix patch:
diff --git a/docs/querying/functions.md b/docs/querying/functions.md
index e1a0b4a769c..55ed92ecc8b 100644
--- a/docs/querying/functions.md
+++ b/docs/querying/functions.md
@@ -317,6 +317,12 @@ bound of that bucket is greater than
 bucket. Otherwise, the upper bound of the lowest bucket is returned for
 quantiles located in the lowest bucket. 
 
+You can use `histogram_quantile(0, v instant-vector)` to get the estimated minimum value stored in
+a histogram.
+
+You can use `histogram_quantile(1, v instant-vector)` to get the estimated maximum value stored in
+a histogram.
+
 
 ## `holt_winters()`
 
diff --git a/model/histogram/float_histogram.go b/model/histogram/float_histogram.go
index f4ee13facc1..2ced0901671 100644
--- a/model/histogram/float_histogram.go
+++ b/model/histogram/float_histogram.go
@@ -615,10 +615,24 @@ func (h *FloatHistogram) NegativeReverseBucketIterator() BucketIterator[float64]
 // set to the zero threshold.
 func (h *FloatHistogram) AllBucketIterator() BucketIterator[float64] {
 	return &allFloatBucketIterator{
-		h:       h,
-		negIter: h.NegativeReverseBucketIterator(),
-		posIter: h.PositiveBucketIterator(),
-		state:   -1,
+		h:         h,
+		leftIter:  h.NegativeReverseBucketIterator(),
+		rightIter: h.PositiveBucketIterator(),
+		state:     -1,
+	}
+}
+
+// AllReverseBucketIterator returns a BucketIterator to iterate over all negative,
+// zero, and positive buckets in descending order (starting at the lowest bucket
+// and going up). If the highest negative bucket or the lowest positive bucket
+// overlap with the zero bucket, their upper or lower boundary, respectively, is
+// set to the zero threshold.
+func (h *FloatHistogram) AllReverseBucketIterator() BucketIterator[float64] {
+	return &allFloatBucketIterator{
+		h:         h,
+		leftIter:  h.PositiveReverseBucketIterator(),
+		rightIter: h.NegativeBucketIterator(),
+		state:     -1,
 	}
 }
 
@@ -903,8 +917,8 @@ func (i *reverseFloatBucketIterator) Next() bool {
 }
 
 type allFloatBucketIterator struct {
-	h                *FloatHistogram
-	negIter, posIter BucketIterator[float64]
+	h                   *FloatHistogram
+	leftIter, rightIter BucketIterator[float64]
 	// -1 means we are iterating negative buckets.
 	// 0 means it is time for the zero bucket.
 	// 1 means we are iterating positive buckets.
@@ -916,10 +930,13 @@ type allFloatBucketIterator struct {
 func (i *allFloatBucketIterator) Next() bool {
 	switch i.state {
 	case -1:
-		if i.negIter.Next() {
-			i.currBucket = i.negIter.At()
-			if i.currBucket.Upper > -i.h.ZeroThreshold {
+		if i.leftIter.Next() {
+			i.currBucket = i.leftIter.At()
+			switch {
+			case i.currBucket.Upper < 0 && i.currBucket.Upper > -i.h.ZeroThreshold:
 				i.currBucket.Upper = -i.h.ZeroThreshold
+			case i.currBucket.Lower > 0 && i.currBucket.Lower < i.h.ZeroThreshold:
+				i.currBucket.Lower = i.h.ZeroThreshold
 			}
 			return true
 		}
@@ -940,10 +957,13 @@ func (i *allFloatBucketIterator) Next() bool {
 		}
 		return i.Next()
 	case 1:
-		if i.posIter.Next() {
-			i.currBucket = i.posIter.At()
-			if i.currBucket.Lower < i.h.ZeroThreshold {
+		if i.rightIter.Next() {
+			i.currBucket = i.rightIter.At()
+			switch {
+			case i.currBucket.Lower > 0 && i.currBucket.Lower < i.h.ZeroThreshold:
 				i.currBucket.Lower = i.h.ZeroThreshold
+			case i.currBucket.Upper < 0 && i.currBucket.Upper > -i.h.ZeroThreshold:
+				i.currBucket.Upper = -i.h.ZeroThreshold
 			}
 			return true
 		}
diff --git a/promql/quantile.go b/promql/quantile.go
index d80345e817f..793a6629f12 100644
--- a/promql/quantile.go
+++ b/promql/quantile.go
@@ -158,9 +158,21 @@ func histogramQuantile(q float64, h *histogram.FloatHistogram) float64 {
 	var (
 		bucket histogram.Bucket[float64]
 		count  float64
-		it     = h.AllBucketIterator()
-		rank   = q * h.Count
+		it     histogram.BucketIterator[float64]
+		rank   float64
 	)
+
+	// if there are NaN observations in the histogram (h.Sum is NaN), use the forward iterator
+	// if the q < 0.5, use the forward iterator
+	// if the q >= 0.5, use the reverse iterator
+	if math.IsNaN(h.Sum) || q < 0.5 {
+		it = h.AllBucketIterator()
+		rank = q * h.Count
+	} else {
+		it = h.AllReverseBucketIterator()
+		rank = (1 - q) * h.Count
+	}
+
 	for it.Next() {
 		bucket = it.At()
 		count += bucket.Count
@@ -193,7 +205,15 @@ func histogramQuantile(q float64, h *histogram.FloatHistogram) float64 {
 		return bucket.Upper
 	}
 
-	rank -= count - bucket.Count
+	// if there are NaN observations in the histogram (h.Sum is NaN), use the forward iterator
+	// if the q < 0.5, use the forward iterator
+	// if the q >= 0.5, use the reverse iterator
+	if math.IsNaN(h.Sum) || q < 0.5 {
+		rank -= count - bucket.Count
+	} else {
+		rank = count - rank
+	}
+
 	// TODO(codesome): Use a better estimation than linear.
 	return bucket.Lower + (bucket.Upper-bucket.Lower)*(rank/bucket.Count)
 }


Test patch:
diff --git a/model/histogram/float_histogram_test.go b/model/histogram/float_histogram_test.go
index 242ef4c92c7..ce749b71017 100644
--- a/model/histogram/float_histogram_test.go
+++ b/model/histogram/float_histogram_test.go
@@ -1979,3 +1979,229 @@ func TestAllFloatBucketIterator(t *testing.T) {
 		})
 	}
 }
+
+func TestAllReverseFloatBucketIterator(t *testing.T) {
+	cases := []struct {
+		h FloatHistogram
+		// To determine the expected buckets.
+		includeNeg, includeZero, includePos bool
+	}{
+		{
+			h: FloatHistogram{
+				Count:         405,
+				ZeroCount:     102,
+				ZeroThreshold: 0.001,
+				Sum:           1008.4,
+				Schema:        1,
+				PositiveSpans: []Span{
+					{Offset: 0, Length: 4},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 3},
+					{Offset: 3, Length: 0},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				PositiveBuckets: []float64{100, 344, 123, 55, 3, 63, 2, 54, 235, 33},
+				NegativeSpans: []Span{
+					{Offset: 0, Length: 3},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 0},
+					{Offset: 3, Length: 4},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				NegativeBuckets: []float64{10, 34, 1230, 54, 67, 63, 2, 554, 235, 33},
+			},
+			includeNeg:  true,
+			includeZero: true,
+			includePos:  true,
+		},
+		{
+			h: FloatHistogram{
+				Count:         405,
+				ZeroCount:     102,
+				ZeroThreshold: 0.001,
+				Sum:           1008.4,
+				Schema:        1,
+				NegativeSpans: []Span{
+					{Offset: 0, Length: 3},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 0},
+					{Offset: 3, Length: 4},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				NegativeBuckets: []float64{10, 34, 1230, 54, 67, 63, 2, 554, 235, 33},
+			},
+			includeNeg:  true,
+			includeZero: true,
+			includePos:  false,
+		},
+		{
+			h: FloatHistogram{
+				Count:         405,
+				ZeroCount:     102,
+				ZeroThreshold: 0.001,
+				Sum:           1008.4,
+				Schema:        1,
+				PositiveSpans: []Span{
+					{Offset: 0, Length: 4},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 3},
+					{Offset: 3, Length: 0},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				PositiveBuckets: []float64{100, 344, 123, 55, 3, 63, 2, 54, 235, 33},
+			},
+			includeNeg:  false,
+			includeZero: true,
+			includePos:  true,
+		},
+		{
+			h: FloatHistogram{
+				Count:         405,
+				ZeroCount:     102,
+				ZeroThreshold: 0.001,
+				Sum:           1008.4,
+				Schema:        1,
+			},
+			includeNeg:  false,
+			includeZero: true,
+			includePos:  false,
+		},
+		{
+			h: FloatHistogram{
+				Count:         405,
+				ZeroCount:     0,
+				ZeroThreshold: 0.001,
+				Sum:           1008.4,
+				Schema:        1,
+				PositiveSpans: []Span{
+					{Offset: 0, Length: 4},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 3},
+					{Offset: 3, Length: 0},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				PositiveBuckets: []float64{100, 344, 123, 55, 3, 63, 2, 54, 235, 33},
+				NegativeSpans: []Span{
+					{Offset: 0, Length: 3},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 0},
+					{Offset: 3, Length: 4},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				NegativeBuckets: []float64{10, 34, 1230, 54, 67, 63, 2, 554, 235, 33},
+			},
+			includeNeg:  true,
+			includeZero: false,
+			includePos:  true,
+		},
+		{
+			h: FloatHistogram{
+				Count:         447,
+				ZeroCount:     42,
+				ZeroThreshold: 0.5, // Coinciding with bucket boundary.
+				Sum:           1008.4,
+				Schema:        0,
+				PositiveSpans: []Span{
+					{Offset: 0, Length: 4},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 3},
+					{Offset: 3, Length: 0},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				PositiveBuckets: []float64{100, 344, 123, 55, 3, 63, 2, 54, 235, 33},
+				NegativeSpans: []Span{
+					{Offset: 0, Length: 3},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 0},
+					{Offset: 3, Length: 4},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				NegativeBuckets: []float64{10, 34, 1230, 54, 67, 63, 2, 554, 235, 33},
+			},
+			includeNeg:  true,
+			includeZero: true,
+			includePos:  true,
+		},
+		{
+			h: FloatHistogram{
+				Count:         447,
+				ZeroCount:     42,
+				ZeroThreshold: 0.6, // Within the bucket closest to zero.
+				Sum:           1008.4,
+				Schema:        0,
+				PositiveSpans: []Span{
+					{Offset: 0, Length: 4},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 3},
+					{Offset: 3, Length: 0},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				PositiveBuckets: []float64{100, 344, 123, 55, 3, 63, 2, 54, 235, 33},
+				NegativeSpans: []Span{
+					{Offset: 0, Length: 3},
+					{Offset: 1, Length: 0},
+					{Offset: 3, Length: 0},
+					{Offset: 3, Length: 4},
+					{Offset: 2, Length: 0},
+					{Offset: 5, Length: 3},
+				},
+				NegativeBuckets: []float64{10, 34, 1230, 54, 67, 63, 2, 554, 235, 33},
+			},
+			includeNeg:  true,
+			includeZero: true,
+			includePos:  true,
+		},
+	}
+
+	for i, c := range cases {
+		t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
+			var expBuckets, actBuckets []Bucket[float64]
+
+			if c.includePos {
+				it := c.h.PositiveReverseBucketIterator()
+				for it.Next() {
+					b := it.At()
+					if c.includeZero && b.Lower < c.h.ZeroThreshold {
+						b.Lower = c.h.ZeroThreshold
+					}
+					expBuckets = append(expBuckets, b)
+				}
+			}
+			if c.includeZero {
+				expBuckets = append(expBuckets, Bucket[float64]{
+					Lower:          -c.h.ZeroThreshold,
+					Upper:          c.h.ZeroThreshold,
+					LowerInclusive: true,
+					UpperInclusive: true,
+					Count:          c.h.ZeroCount,
+				})
+			}
+			if c.includeNeg {
+				it := c.h.NegativeBucketIterator()
+				for it.Next() {
+					b := it.At()
+					if c.includeZero && b.Upper > -c.h.ZeroThreshold {
+						b.Upper = -c.h.ZeroThreshold
+					}
+					expBuckets = append(expBuckets, b)
+				}
+			}
+
+			it := c.h.AllReverseBucketIterator()
+			for it.Next() {
+				actBuckets = append(actBuckets, it.At())
+			}
+
+			require.Equal(t, expBuckets, actBuckets)
+		})
+	}
+}