package query import ( "math" ) // DownsampleOptions specifies parameters for server-side query downsampling. type DownsampleOptions struct { MaxPoints int // Target maximum number of points (0 = unlimited / raw) StepMS int64 // Time-bucket step in milliseconds (0 = disabled) Method string // Downsampling method: "lttb" (default), "avg", "min", "max", "sum", "count", "none" } // Downsample reduces the density of a time-series according to the specified options. func Downsample(ts []int64, vals []float64, opts DownsampleOptions) ([]int64, []float64) { if len(ts) <= 2 { return ts, vals } // 1. Time-bucket step aggregation takes precedence if specified if opts.StepMS > 0 { method := opts.Method if method == "" || method == "lttb" { method = "avg" } return AggregateBuckets(ts, vals, opts.StepMS, method) } // 2. Maximum point count threshold downsampling if opts.MaxPoints > 0 && len(ts) > opts.MaxPoints { switch opts.Method { case "none", "raw": return ts, vals case "min", "max", "avg", "sum", "count": span := ts[len(ts)-1] - ts[0] step := span / int64(opts.MaxPoints) if step > 0 { return AggregateBuckets(ts, vals, step, opts.Method) } return DownsampleLTTB(ts, vals, opts.MaxPoints) default: // "lttb" return DownsampleLTTB(ts, vals, opts.MaxPoints) } } return ts, vals } // DownsampleLTTB implements the Largest Triangle Three Buckets (LTTB) downsampling algorithm. // It downsamples a series of N points down to threshold points while preserving visual shape, // peaks, valleys, and trends. Linear time O(N). func DownsampleLTTB(ts []int64, vals []float64, threshold int) ([]int64, []float64) { n := len(ts) if threshold >= n || threshold <= 0 { return ts, vals } if threshold == 1 { return []int64{ts[0]}, []float64{vals[0]} } if threshold == 2 { return []int64{ts[0], ts[n-1]}, []float64{vals[0], vals[n-1]} } sampledTS := make([]int64, threshold) sampledVals := make([]float64, threshold) // Bucket size: divide intermediate points (1 to n-2) into (threshold - 2) buckets every := float64(n-2) / float64(threshold-2) // First point is always selected sampledTS[0] = ts[0] sampledVals[0] = vals[0] a := 0 // index of previous selected point for i := 0; i < threshold-2; i++ { // Calculate point average for the next bucket (i + 1) nextStart := int(math.Floor(float64(i+1)*every)) + 1 nextEnd := min(int(math.Floor(float64(i+2)*every))+1, n) var avgX float64 var avgY float64 nextCount := nextEnd - nextStart if nextCount > 0 { var sumX float64 var sumY float64 for j := nextStart; j < nextEnd; j++ { sumX += float64(ts[j]) sumY += vals[j] } avgX = sumX / float64(nextCount) avgY = sumY / float64(nextCount) } else { avgX = float64(ts[nextStart]) avgY = vals[nextStart] } // Find point in current bucket i that maximizes triangle area with point a and next bucket average curStart := int(math.Floor(float64(i)*every)) + 1 curEnd := min(int(math.Floor(float64(i+1)*every))+1, n) ax := float64(ts[a]) ay := vals[a] maxArea := -1.0 maxIdx := curStart for j := curStart; j < curEnd; j++ { // Area of triangle: 0.5 * |(Ax - AvgX)*(Y_j - Ay) - (Ax - X_j)*(AvgY - Ay)| // Factor of 0.5 can be omitted as it does not affect the argmax area := math.Abs((ax-avgX)*(vals[j]-ay) - (ax-float64(ts[j]))*(avgY-ay)) if area > maxArea { maxArea = area maxIdx = j } } sampledTS[i+1] = ts[maxIdx] sampledVals[i+1] = vals[maxIdx] a = maxIdx } // Last point is always selected sampledTS[threshold-1] = ts[n-1] sampledVals[threshold-1] = vals[n-1] return sampledTS, sampledVals } // AggregateBuckets divides the series into fixed time buckets of stepMS duration and // aggregates points within each bucket using method ("avg", "min", "max", "sum", "count"). func AggregateBuckets(ts []int64, vals []float64, stepMS int64, method string) ([]int64, []float64) { if len(ts) == 0 || stepMS <= 0 { return ts, vals } var outTS []int64 var outVals []float64 currentBucket := (ts[0] / stepMS) * stepMS bucketCount := 0 bucketSum := 0.0 bucketMin := vals[0] bucketMax := vals[0] flushBucket := func() { if bucketCount == 0 { return } var finalVal float64 switch method { case "min": finalVal = bucketMin case "max": finalVal = bucketMax case "sum": finalVal = bucketSum case "count": finalVal = float64(bucketCount) default: // "avg", "mean" finalVal = bucketSum / float64(bucketCount) } outTS = append(outTS, currentBucket) outVals = append(outVals, finalVal) } for i, t := range ts { b := (t / stepMS) * stepMS if b != currentBucket { flushBucket() currentBucket = b bucketCount = 0 bucketSum = 0.0 bucketMin = vals[i] bucketMax = vals[i] } v := vals[i] bucketSum += v if bucketCount == 0 || v < bucketMin { bucketMin = v } if bucketCount == 0 || v > bucketMax { bucketMax = v } bucketCount++ } flushBucket() return outTS, outVals } // Downsample downsamples the SeriesResult points in place according to opts. func (s *SeriesResult) Downsample(opts DownsampleOptions) { if len(s.Timestamps) <= 2 { return } s.Timestamps, s.Values = Downsample(s.Timestamps, s.Values, opts) }