Skip to content

SigNoz is an open-source, OpenTelemetry-native observability platform for your team and their AI agents. Get logs, metrics, and traces in one tool with features like APM, distributed tracing, log management, infra monitoring, etc. Combined with SigNoz MCP and a native AI teammate (in SigNoz Cloud) it helps you build more resilient apps.

29.3 KB
Raw Blame
package querier

import (
	"cmp"
	"context"
	"encoding/json"
	"fmt"
	"log/slog"
	"slices"
	"time"

	"github.com/SigNoz/signoz/pkg/cache"
	"github.com/SigNoz/signoz/pkg/errors"
	"github.com/SigNoz/signoz/pkg/factory"
	"github.com/SigNoz/signoz/pkg/types/cachetypes"
	"github.com/SigNoz/signoz/pkg/types/metrictypes"
	qbtypes "github.com/SigNoz/signoz/pkg/types/querybuildertypes/querybuildertypesv5"
	"github.com/SigNoz/signoz/pkg/valuer"
)

// bucketCacheCellSteps is the grid cell width in steps; no cached bucket
// crosses a cell boundary.
const bucketCacheCellSteps = 60

// BucketCache is the interface for bucket-based caching.
type BucketCache interface {
	// cached portion + list of gaps to fetch
	GetMissRanges(ctx context.Context, orgID valuer.UUID, q qbtypes.Query, step qbtypes.Step) (cached *qbtypes.Result, missing []*qbtypes.TimeRange)
	// store fresh buckets for future hits
	Put(ctx context.Context, orgID valuer.UUID, q qbtypes.Query, step qbtypes.Step, fresh *qbtypes.Result)
}

// bucketCache implements the BucketCache interface.
type bucketCache struct {
	cache        cache.Cache
	logger       *slog.Logger
	cacheTTL     time.Duration
	fluxInterval time.Duration
}

var _ BucketCache = (*bucketCache)(nil)

// NewBucketCache creates a new BucketCache implementation.
func NewBucketCache(settings factory.ProviderSettings, cache cache.Cache, cacheTTL time.Duration, fluxInterval time.Duration) BucketCache {
	cacheSettings := factory.NewScopedProviderSettings(settings, "github.com/SigNoz/signoz/pkg/querier/bucket_cache")
	return &bucketCache{
		cache:        cache,
		logger:       cacheSettings.Logger(),
		cacheTTL:     cacheTTL,
		fluxInterval: fluxInterval,
	}
}

// GetMissRanges returns cached data and missing time ranges.
func (bc *bucketCache) GetMissRanges(
	ctx context.Context,
	orgID valuer.UUID,
	q qbtypes.Query,
	step qbtypes.Step,
) (cached *qbtypes.Result, missing []*qbtypes.TimeRange) {

	// Get query window
	startMs, endMs := q.Window()

	bc.logger.DebugContext(ctx, "getting miss ranges", slog.String("fingerprint", q.Fingerprint()), slog.Uint64("start", startMs), slog.Uint64("end", endMs))

	// Extract step interval if this is a builder query
	stepMs := uint64(step.Milliseconds())

	// No cached data, need to fetch entire range
	missing = []*qbtypes.TimeRange{{From: startMs, To: endMs}}

	if endMs <= startMs {
		return nil, missing
	}
	cellWidthMs := bucketCacheCellSteps * stepMs
	firstCellIdx, lastCellIdx := deriveCellIdx(startMs, cellWidthMs), deriveCellIdx(endMs-1, cellWidthMs)

	// Gather the buckets of every cell the window touches
	cellKeys := make([]string, 0, lastCellIdx-firstCellIdx+1)
	cellEntries := make([]cachetypes.Cacheable, 0, lastCellIdx-firstCellIdx+1)
	for cellIdx := firstCellIdx; cellIdx <= lastCellIdx; cellIdx++ {
		cellKeys = append(cellKeys, bc.generateCacheKey(q, cellIdx))
		cellEntries = append(cellEntries, &qbtypes.CachedData{})
	}

	// A cell that could not be read comes back nil like a miss, so the rest
	// are still worth serving
	if err := bc.cache.GetMany(ctx, orgID, cellKeys, cellEntries); err != nil {
		bc.logger.ErrorContext(ctx, "error getting cached data", errors.Attr(err))
	}

	cachedBuckets := []*qbtypes.CachedBucket{}
	cachedWarnings := []string{}
	for _, cellEntry := range cellEntries {
		if cellEntry == nil {
			continue
		}
		cellData := cellEntry.(*qbtypes.CachedData)
		cachedBuckets = append(cachedBuckets, cellData.Buckets...)
		cachedWarnings = append(cachedWarnings, cellData.Warnings...)
	}
	if len(cachedBuckets) == 0 {
		return nil, missing
	}

	// Find missing ranges with step alignment
	missing = bc.findMissingRangesWithStep(cachedBuckets, startMs, endMs, stepMs)
	bc.logger.DebugContext(ctx, "missing ranges", slog.Any("missing", missing), slog.Uint64("step", stepMs))

	// Extract relevant buckets and merge them
	relevantBuckets := bc.filterRelevantBuckets(cachedBuckets, startMs, endMs)
	if len(relevantBuckets) == 0 {
		// nothing cached overlaps the window, so all of it has to be fetched.
		return nil, []*qbtypes.TimeRange{{From: startMs, To: endMs}}
	}

	// Merge buckets into a single result
	mergedResult := bc.mergeBuckets(ctx, relevantBuckets, cachedWarnings)

	// Filter the merged result to only include values within the requested time range
	mergedResult = bc.filterResultToTimeRange(mergedResult, q, startMs, endMs, stepMs)

	return mergedResult, missing
}

// Put stores fresh query results in the cache.
func (bc *bucketCache) Put(ctx context.Context, orgID valuer.UUID, q qbtypes.Query, step qbtypes.Step, fresh *qbtypes.Result) {
	// Get query window
	startMs, endMs := q.Window()

	// Calculate the flux boundary - data after this point should not be cached
	currentMs := uint64(time.Now().UnixMilli())
	fluxBoundary := currentMs - uint64(bc.fluxInterval.Milliseconds())

	// If the entire range is within flux interval, skip caching
	if startMs >= fluxBoundary {
		bc.logger.DebugContext(ctx, "entire range within flux interval, skipping cache",
			slog.Uint64("start", startMs),
			slog.Uint64("end", endMs),
			slog.Uint64("flux_boundary", fluxBoundary))
		return
	}

	// Adjust endMs to not include data within flux interval
	cachableEndMs := endMs
	if endMs > fluxBoundary {
		cachableEndMs = fluxBoundary
		bc.logger.DebugContext(ctx, "adjusting end time to exclude flux interval",
			slog.Uint64("original_end", endMs),
			slog.Uint64("cachable_end", cachableEndMs))
	}

	// Trim the result to exclude data within flux interval
	trimmedResult := bc.trimResultToFluxBoundary(fresh, cachableEndMs)
	if trimmedResult == nil {
		// Result type is not cacheable (raw or scalar)
		return
	}

	// Adjust start and end times to only cache complete intervals
	cachableStartMs := startMs
	stepMs := uint64(step.Milliseconds())

	// If we have a step interval, adjust boundaries to only cache complete intervals
	if stepMs > 0 {
		// If start is not aligned, round up to next step boundary (first complete interval)
		if startMs%stepMs != 0 {
			cachableStartMs = ((startMs / stepMs) + 1) * stepMs
		}

		// If end is not aligned, round down to previous step boundary (last complete interval)
		if cachableEndMs%stepMs != 0 {
			cachableEndMs = (cachableEndMs / stepMs) * stepMs
		}

		// If after adjustment we have no complete intervals, don't cache
		if cachableStartMs >= cachableEndMs {
			bc.logger.DebugContext(ctx, "no complete intervals to cache",
				slog.Uint64("original_start", startMs),
				slog.Uint64("original_end", endMs),
				slog.Uint64("adjusted_start", cachableStartMs),
				slog.Uint64("adjusted_end", cachableEndMs),
				slog.Uint64("step", stepMs))
			return
		}
	}

	// Convert trimmed result to buckets, one per grid cell it spans
	cellWidthMs := bucketCacheCellSteps * stepMs
	freshBuckets := bc.resultToBuckets(ctx, trimmedResult, cachableStartMs, cachableEndMs, cellWidthMs)

	cellKeys := make([]string, len(freshBuckets))
	cellEntries := make([]cachetypes.Cacheable, len(freshBuckets))
	for i, freshBucket := range freshBuckets {
		cellKeys[i] = bc.generateCacheKey(q, deriveCellIdx(freshBucket.StartMs, cellWidthMs))
		cellEntries[i] = &qbtypes.CachedData{}
	}
	// A cell that could not be read comes back nil like a miss, so its entry is
	// rebuilt from the fresh bucket alone
	if err := bc.cache.GetMany(ctx, orgID, cellKeys, cellEntries); err != nil {
		bc.logger.ErrorContext(ctx, "error getting cached data", errors.Attr(err))
	}

	// Each cell is its own cache entry, rewritten only when the fresh bucket
	// changes what it holds, so an entry's TTL runs from its last new data
	for i, freshBucket := range freshBuckets {
		cellEntry := &qbtypes.CachedData{}
		if cellEntries[i] != nil {
			cellEntry = cellEntries[i].(*qbtypes.CachedData)
		}

		cellBuckets, changed := bc.mergeFreshBucketIntoCell(ctx, cellEntry.Buckets, freshBucket)
		if !changed {
			continue
		}
		cellEntry.Buckets = cellBuckets
		cellEntry.Warnings = bc.deduplicateWarnings(append(cellEntry.Warnings, trimmedResult.Warnings...))
		if err := bc.cache.Set(ctx, orgID, cellKeys[i], cellEntry, bc.cacheTTL); err != nil {
			bc.logger.ErrorContext(ctx, "error setting cached data", errors.Attr(err))
		}
	}
}

// generateCacheKey names the cache entry holding one grid cell of a query.
func (bc *bucketCache) generateCacheKey(q qbtypes.Query, cellIdx uint64) string {
	return fmt.Sprintf("v6:query:%s:cellidx:%d", q.Fingerprint(), cellIdx)
}

// deriveCellIdx returns the index of the grid cell holding startMs; with no grid
// every bucket shares cell 0.
func deriveCellIdx(startMs, cellWidthMs uint64) uint64 {
	if cellWidthMs == 0 {
		return 0
	}
	return startMs / cellWidthMs
}

// findMissingRangesWithStep identifies time ranges not covered by cached buckets with step alignment.
func (bc *bucketCache) findMissingRangesWithStep(buckets []*qbtypes.CachedBucket, startMs, endMs uint64, stepMs uint64) []*qbtypes.TimeRange {
	// When step is 0, use simple algorithm
	if stepMs == 0 {
		return bc.findMissingRangesBasic(buckets, startMs, endMs)
	}

	// When no buckets exist, handle partial windows specially
	if len(buckets) == 0 {
		missing := make([]*qbtypes.TimeRange, 0, 3)

		currentMs := startMs

		// Check if start is not aligned - add partial window
		if startMs%stepMs != 0 {
			nextAggStart := startMs - (startMs % stepMs) + stepMs
			missing = append(missing, &qbtypes.TimeRange{
				From: startMs,
				To:   min(nextAggStart, endMs),
			})
			currentMs = nextAggStart
		}

		// Add the main range if needed
		if currentMs < endMs {
			missing = append(missing, &qbtypes.TimeRange{
				From: currentMs,
				To:   endMs,
			})
		}

		return missing
	}

	// Check if already sorted before sorting
	needsSort := false
	for i := 1; i < len(buckets); i++ {
		if buckets[i].StartMs < buckets[i-1].StartMs {
			needsSort = true
			break
		}
	}

	if needsSort {
		slices.SortFunc(buckets, func(a, b *qbtypes.CachedBucket) int {
			if a.StartMs < b.StartMs {
				return -1
			}
			if a.StartMs > b.StartMs {
				return 1
			}
			return 0
		})
	}

	// Pre-allocate with reasonable capacity
	missing := make([]*qbtypes.TimeRange, 0, len(buckets)+2)

	currentMs := startMs

	// Check if start is not aligned - add partial window
	if startMs%stepMs != 0 {
		nextAggStart := startMs - (startMs % stepMs) + stepMs
		missing = append(missing, &qbtypes.TimeRange{
			From: startMs,
			To:   min(nextAggStart, endMs),
		})
		currentMs = nextAggStart
	}

	for _, bucket := range buckets {
		// Skip buckets that end before current position
		if bucket.EndMs <= currentMs {
			continue
		}
		// Stop processing if we've reached the end time
		if bucket.StartMs >= endMs {
			break
		}

		// Align bucket boundaries to step intervals
		alignedBucketStart := bucket.StartMs
		if bucket.StartMs%stepMs != 0 {
			// Round up to next step boundary
			alignedBucketStart = bucket.StartMs - (bucket.StartMs % stepMs) + stepMs
		}

		// Add gap before this bucket if needed
		if currentMs < alignedBucketStart && currentMs < endMs {
			missing = append(missing, &qbtypes.TimeRange{
				From: currentMs,
				To:   min(alignedBucketStart, endMs),
			})
		}

		// Update current position to the end of this bucket
		// But ensure it's aligned to step boundary
		bucketEnd := min(bucket.EndMs, endMs)
		// The step the window ends inside is missing however far the bucket runs.
		if bucketEnd%stepMs != 0 {
			// Round down to step boundary
			bucketEnd = bucketEnd - (bucketEnd % stepMs)
		}
		currentMs = max(currentMs, bucketEnd)
	}

	// Add final gap if needed
	if currentMs < endMs {
		missing = append(missing, &qbtypes.TimeRange{
			From: currentMs,
			To:   endMs,
		})
	}

	// Don't merge ranges - keep partial windows separate for proper handling
	return missing
}

// findMissingRangesBasic is the simple algorithm without step alignment.
func (bc *bucketCache) findMissingRangesBasic(buckets []*qbtypes.CachedBucket, startMs, endMs uint64) []*qbtypes.TimeRange {
	// Check if already sorted before sorting
	needsSort := false
	for i := 1; i < len(buckets); i++ {
		if buckets[i].StartMs < buckets[i-1].StartMs {
			needsSort = true
			break
		}
	}

	if needsSort {
		slices.SortFunc(buckets, func(a, b *qbtypes.CachedBucket) int {
			if a.StartMs < b.StartMs {
				return -1
			}
			if a.StartMs > b.StartMs {
				return 1
			}
			return 0
		})
	}

	// Pre-allocate with reasonable capacity
	missing := make([]*qbtypes.TimeRange, 0, len(buckets)+1)
	currentMs := startMs

	for _, bucket := range buckets {
		// Skip buckets that end before start time
		if bucket.EndMs <= startMs {
			continue
		}
		// Stop processing if we've reached the end time
		if bucket.StartMs >= endMs {
			break
		}

		// Add gap before this bucket if needed
		if currentMs < bucket.StartMs {
			missing = append(missing, &qbtypes.TimeRange{
				From: currentMs,
				To:   min(bucket.StartMs, endMs),
			})
		}

		// Update current position, but don't go past the end time
		currentMs = max(currentMs, min(bucket.EndMs, endMs))
	}

	// Add final gap if needed
	if currentMs < endMs {
		// Check if we need to limit due to flux interval
		currentTime := uint64(time.Now().UnixMilli())
		fluxBoundary := currentTime - uint64(bc.fluxInterval.Milliseconds())

		// If the missing range extends beyond flux boundary, limit it
		if currentMs < fluxBoundary {
			// Add range up to flux boundary
			missing = append(missing, &qbtypes.TimeRange{
				From: currentMs,
				To:   min(endMs, fluxBoundary),
			})
			// If endMs is beyond flux boundary, add that as another missing range
			if endMs > fluxBoundary {
				missing = append(missing, &qbtypes.TimeRange{
					From: fluxBoundary,
					To:   endMs,
				})
			}
		} else {
			// Entire missing range is within flux interval
			missing = append(missing, &qbtypes.TimeRange{
				From: currentMs,
				To:   endMs,
			})
		}
	}

	// Don't merge ranges - keep partial windows separate for proper handling
	return missing
}

// filterRelevantBuckets returns buckets that overlap with the requested time range.
func (bc *bucketCache) filterRelevantBuckets(buckets []*qbtypes.CachedBucket, startMs, endMs uint64) []*qbtypes.CachedBucket {
	// Pre-allocate with estimated capacity
	relevant := make([]*qbtypes.CachedBucket, 0, len(buckets))

	for _, bucket := range buckets {
		// Check if bucket overlaps with requested range
		if bucket.EndMs > startMs && bucket.StartMs < endMs {
			relevant = append(relevant, bucket)
		}
	}

	// Sort by start time
	slices.SortFunc(relevant, func(a, b *qbtypes.CachedBucket) int {
		if a.StartMs < b.StartMs {
			return -1
		}
		if a.StartMs > b.StartMs {
			return 1
		}
		return 0
	})

	return relevant
}

// mergeBuckets combines multiple cached buckets into a single result.
func (bc *bucketCache) mergeBuckets(ctx context.Context, buckets []*qbtypes.CachedBucket, warnings []string) *qbtypes.Result {
	if len(buckets) == 0 {
		return &qbtypes.Result{}
	}

	// All buckets should have the same type
	resultType := buckets[0].Type

	// Aggregate stats
	var totalStats qbtypes.ExecStats
	for _, bucket := range buckets {
		totalStats.RowsScanned += bucket.Stats.RowsScanned
		totalStats.BytesScanned += bucket.Stats.BytesScanned
		totalStats.DurationMS += bucket.Stats.DurationMS
	}

	// Merge values based on type
	var mergedValue any
	switch resultType {
	case qbtypes.RequestTypeTimeSeries, qbtypes.RequestTypeHeatmap:
		mergedValue = bc.mergeTimeSeriesValues(ctx, buckets)
		// Raw and Scalar types are not cached, so no merge needed
	}

	return &qbtypes.Result{
		Type:     resultType,
		Value:    mergedValue,
		Stats:    totalStats,
		Warnings: warnings,
	}
}

// mergeTimeSeriesValues merges time series data from multiple buckets.
func (bc *bucketCache) mergeTimeSeriesValues(ctx context.Context, buckets []*qbtypes.CachedBucket) *qbtypes.TimeSeriesData {
	// Estimate capacity based on bucket count
	estimatedSeries := len(buckets) * 10

	// Flat map with composite key for better performance
	type seriesKey struct {
		aggIndex int
		key      string
	}
	seriesMap := make(map[seriesKey]*qbtypes.TimeSeries, estimatedSeries)

	decodedTimeSeriesData := make([]*qbtypes.TimeSeriesData, 0, len(buckets))

	// Alias and Meta are taken from whichever cached bucket covers the latest
	// range, and the buckets do not arrive in StartMs order, so keep the winner
	// per AggregationBucket.Index alongside the StartMs that won it.
	aggregationIndexToLatest := map[int]*qbtypes.AggregationBucket{}
	aggregationIndexToLatestStartMs := map[int]uint64{}

	for _, bucket := range buckets {
		var tsData *qbtypes.TimeSeriesData
		if err := json.Unmarshal(bucket.Value, &tsData); err != nil {
			bc.logger.ErrorContext(ctx, "failed to unmarshal time series data", errors.Attr(err))
			continue
		}
		decodedTimeSeriesData = append(decodedTimeSeriesData, tsData)

		for _, aggBucket := range tsData.Aggregations {
			if _, seen := aggregationIndexToLatest[aggBucket.Index]; !seen || bucket.StartMs >= aggregationIndexToLatestStartMs[aggBucket.Index] {
				aggregationIndexToLatest[aggBucket.Index] = aggBucket
				aggregationIndexToLatestStartMs[aggBucket.Index] = bucket.StartMs
			}
		}
	}

	mergedUpperBounds := qbtypes.MergeBucketUpperBounds(decodedTimeSeriesData...)

	for _, tsData := range decodedTimeSeriesData {
		for _, aggBucket := range tsData.Aggregations {
			aggBucket.ReindexValuesToNewUpperBounds(mergedUpperBounds[aggBucket.Index])

			for _, series := range aggBucket.Series {
				// Create series key from labels
				key := seriesKey{
					aggIndex: aggBucket.Index,
					key:      qbtypes.GetUniqueSeriesKey(series.Labels),
				}

				if existingSeries, ok := seriesMap[key]; ok {
					// Merge values, avoiding duplicate timestamps
					timestampMap := make(map[int64]bool)
					for _, v := range existingSeries.Values {
						timestampMap[v.Timestamp] = true
					}

					// Pre-allocate capacity for merged values
					newCap := len(existingSeries.Values) + len(series.Values)
					if cap(existingSeries.Values) < newCap {
						newValues := make([]*qbtypes.TimeSeriesValue, len(existingSeries.Values), newCap)
						copy(newValues, existingSeries.Values)
						existingSeries.Values = newValues
					}

					// Only add values with new timestamps
					for _, v := range series.Values {
						if !timestampMap[v.Timestamp] {
							existingSeries.Values = append(existingSeries.Values, v)
						}
					}
				} else {
					// New series
					seriesMap[key] = series
				}
			}
		}
	}

	// Group series by aggregation index
	aggMap := make(map[int][]*qbtypes.TimeSeries)
	for key, series := range seriesMap {
		aggMap[key.aggIndex] = append(aggMap[key.aggIndex], series)
	}

	// Convert map back to slice
	result := &qbtypes.TimeSeriesData{
		Aggregations: make([]*qbtypes.AggregationBucket, 0, len(aggMap)),
	}

	for index, seriesList := range aggMap {
		// Sort values by timestamp for each series
		for _, s := range seriesList {
			// Check if already sorted before sorting
			needsSort := false
			for i := 1; i < len(s.Values); i++ {
				if s.Values[i].Timestamp < s.Values[i-1].Timestamp {
					needsSort = true
					break
				}
			}

			if needsSort {
				slices.SortFunc(s.Values, func(a, b *qbtypes.TimeSeriesValue) int {
					if a.Timestamp < b.Timestamp {
						return -1
					}
					if a.Timestamp > b.Timestamp {
						return 1
					}
					return 0
				})
			}
		}

		aggBucket := &qbtypes.AggregationBucket{
			Index:  index,
			Series: seriesList,
		}
		if latest, ok := aggregationIndexToLatest[index]; ok {
			aggBucket.Alias = latest.Alias
			aggBucket.Meta = latest.Meta
		}
		result.Aggregations = append(result.Aggregations, aggBucket)
	}

	return result
}

// isEmptyResult checks if a result is truly empty (no data exists) vs filtered empty (data was filtered out).
func (bc *bucketCache) isEmptyResult(result *qbtypes.Result) (isEmpty bool, isFiltered bool) {
	if result.Value == nil {
		return true, false
	}

	switch result.Type {
	case qbtypes.RequestTypeTimeSeries, qbtypes.RequestTypeHeatmap:
		if tsData, ok := result.Value.(*qbtypes.TimeSeriesData); ok {
			// No aggregations at all means truly empty
			if len(tsData.Aggregations) == 0 {
				return true, false
			}

			// Check if we have aggregations but no series (filtered out)
			totalSeries := 0
			for _, agg := range tsData.Aggregations {
				totalSeries += len(agg.Series)
			}

			if totalSeries == 0 {
				// We have aggregations but no series - data was filtered out
				return true, true
			}

			// Check if all series have no values
			hasValues := false
			for _, agg := range tsData.Aggregations {
				for _, series := range agg.Series {
					if len(series.Values) > 0 {
						hasValues = true
						break
					}
				}
				if hasValues {
					break
				}
			}

			return !hasValues, !hasValues && totalSeries > 0
		}

	case qbtypes.RequestTypeRaw, qbtypes.RequestTypeScalar, qbtypes.RequestTypeTrace:
		// Raw and scalar data are not cached
		return true, false
	}

	return true, false
}

// resultToBuckets converts a query result into time-based buckets.
func (bc *bucketCache) resultToBuckets(ctx context.Context, result *qbtypes.Result, startMs, endMs, cellWidthMs uint64) []*qbtypes.CachedBucket {
	// Check if result is empty
	isEmpty, isFiltered := bc.isEmptyResult(result)

	// Don't cache if result is empty but not filtered
	// Empty filtered results should be cached to avoid re-querying
	if isEmpty && !isFiltered {
		bc.logger.DebugContext(ctx, "skipping cache for empty non-filtered result")
		return nil
	}

	// Empty filtered results still become buckets, so the range is not re-queried
	perCellBuckets, err := result.SplitIntoCacheCellBuckets(startMs, endMs, cellWidthMs)
	if err != nil {
		bc.logger.ErrorContext(ctx, "failed to convert result to buckets", errors.Attr(err))
		return nil
	}
	return perCellBuckets
}

// mergeFreshBucketIntoCell folds a fresh bucket into the buckets of its cell
// and reports whether the cell changed: a bucket already covering the fresh
// one leaves it as is, buckets inside the fresh one are replaced, buckets
// overlapping or edge to edge with it are unioned, and the rest are kept apart.
func (bc *bucketCache) mergeFreshBucketIntoCell(ctx context.Context, cellBuckets []*qbtypes.CachedBucket, freshBucket *qbtypes.CachedBucket) ([]*qbtypes.CachedBucket, bool) {
	keptBuckets := make([]*qbtypes.CachedBucket, 0, len(cellBuckets)+1)
	touchingBuckets := []*qbtypes.CachedBucket{}
	for _, cellBucket := range cellBuckets {
		switch {
		case cellBucket.Contains(freshBucket):
			return cellBuckets, false
		case cellBucket.Touches(freshBucket):
			touchingBuckets = append(touchingBuckets, cellBucket)
		default:
			keptBuckets = append(keptBuckets, cellBucket)
		}
	}
	keptBuckets = append(keptBuckets, bc.unionBuckets(ctx, freshBucket, touchingBuckets))

	slices.SortFunc(keptBuckets, func(a, b *qbtypes.CachedBucket) int {
		return cmp.Compare(a.StartMs, b.StartMs)
	})
	return keptBuckets, true
}

// unionBuckets widens the fresh bucket by the buckets it touches. Buckets
// inside it are replaced outright, so only a genuine partial overlap decodes
// anything.
func (bc *bucketCache) unionBuckets(ctx context.Context, freshBucket *qbtypes.CachedBucket, touchingBuckets []*qbtypes.CachedBucket) *qbtypes.CachedBucket {
	bucketsToMerge := []*qbtypes.CachedBucket{freshBucket}
	for _, touchingBucket := range touchingBuckets {
		if !freshBucket.Contains(touchingBucket) {
			bucketsToMerge = append(bucketsToMerge, touchingBucket)
		}
	}
	if len(bucketsToMerge) == 1 {
		return freshBucket
	}

	value, err := json.Marshal(bc.mergeTimeSeriesValues(ctx, bucketsToMerge))
	if err != nil {
		bc.logger.ErrorContext(ctx, "failed to marshal unioned bucket", errors.Attr(err))
		return freshBucket
	}
	unionBucket := &qbtypes.CachedBucket{
		StartMs: freshBucket.StartMs,
		EndMs:   freshBucket.EndMs,
		Type:    freshBucket.Type,
		Value:   value,
		Stats:   qbtypes.ExecStats{StepIntervals: freshBucket.Stats.StepIntervals},
	}
	for _, mergedBucket := range bucketsToMerge {
		unionBucket.StartMs = min(unionBucket.StartMs, mergedBucket.StartMs)
		unionBucket.EndMs = max(unionBucket.EndMs, mergedBucket.EndMs)
		unionBucket.Stats.RowsScanned += mergedBucket.Stats.RowsScanned
		unionBucket.Stats.BytesScanned += mergedBucket.Stats.BytesScanned
		unionBucket.Stats.DurationMS += mergedBucket.Stats.DurationMS
	}
	return unionBucket
}

// deduplicateWarnings removes duplicate warnings.
func (bc *bucketCache) deduplicateWarnings(warnings []string) []string {
	return dedupeWarnings(warnings)
}

// trimResultToFluxBoundary trims the result to exclude data points beyond the flux boundary.
func (bc *bucketCache) trimResultToFluxBoundary(result *qbtypes.Result, fluxBoundary uint64) *qbtypes.Result {
	trimmedResult := &qbtypes.Result{
		Type:     result.Type,
		Stats:    result.Stats,
		Warnings: result.Warnings,
	}

	switch result.Type {
	case qbtypes.RequestTypeTimeSeries, qbtypes.RequestTypeHeatmap:
		// Trim time series data
		if tsData, ok := result.Value.(*qbtypes.TimeSeriesData); ok && tsData != nil {
			trimmedData := &qbtypes.TimeSeriesData{}

			for _, aggBucket := range tsData.Aggregations {
				// Meta has to survive the trim: a heatmap's counts are
				// positional against Meta.Buckets, so a cached bucket that
				// lost its axis cannot be read back against anything.
				trimmedBucket := &qbtypes.AggregationBucket{
					Index: aggBucket.Index,
					Alias: aggBucket.Alias,
					Meta:  aggBucket.Meta,
				}

				for _, series := range aggBucket.Series {
					trimmedSeries := &qbtypes.TimeSeries{
						Labels: series.Labels,
					}

					// Filter values to exclude those beyond flux boundary and partial values
					for _, value := range series.Values {
						// Skip partial values - they cannot be cached
						if value.Partial {
							continue
						}
						if uint64(value.Timestamp) <= fluxBoundary {
							trimmedSeries.Values = append(trimmedSeries.Values, value)
						}
					}

					// Always add the series to preserve filtered empty results
					trimmedBucket.Series = append(trimmedBucket.Series, trimmedSeries)
				}

				// Always add the bucket to preserve aggregation structure
				trimmedData.Aggregations = append(trimmedData.Aggregations, trimmedBucket)
			}

			// Always set the value to preserve empty filtered results
			trimmedResult.Value = trimmedData
		}

	case qbtypes.RequestTypeRaw, qbtypes.RequestTypeScalar, qbtypes.RequestTypeTrace:
		// Don't cache raw or scalar data
		return nil
	}

	return trimmedResult
}

func min(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b uint64) uint64 {
	if a > b {
		return a
	}
	return b
}

// filterResultToTimeRange narrows the cached result to the requested window, both
// the values in it and the heatmap axis under them.
func (bc *bucketCache) filterResultToTimeRange(result *qbtypes.Result, q qbtypes.Query, startMs, endMs, stepMs uint64) *qbtypes.Result {
	if result == nil || result.Value == nil {
		return result
	}

	_, isPromQL := q.(*promqlQuery)
	maxTimestampMs := endMs
	// A promql value at T is the query evaluated at T, so T == endMs is inside the
	// requested range. For every other query type the value at T aggregates
	// [T, T+stepMs), which the requested range contains only when T <= endMs-stepMs.
	if !isPromQL {
		if stepMs > 0 {
			maxTimestampMs = endMs - stepMs
		} else {
			maxTimestampMs = endMs - 1
		}
	}

	switch result.Type {
	case qbtypes.RequestTypeTimeSeries, qbtypes.RequestTypeHeatmap:
		if tsData, ok := result.Value.(*qbtypes.TimeSeriesData); ok {
			filteredData := &qbtypes.TimeSeriesData{
				Aggregations: make([]*qbtypes.AggregationBucket, 0, len(tsData.Aggregations)),
			}

			for _, aggBucket := range tsData.Aggregations {
				filteredBucket := &qbtypes.AggregationBucket{
					Index:  aggBucket.Index,
					Alias:  aggBucket.Alias,
					Meta:   aggBucket.Meta,
					Series: make([]*qbtypes.TimeSeries, 0, len(aggBucket.Series)),
				}

				for _, series := range aggBucket.Series {
					filteredSeries := &qbtypes.TimeSeries{
						Labels: series.Labels,
						Values: make([]*qbtypes.TimeSeriesValue, 0, len(series.Values)),
					}

					// Filter values to only include those within the requested time range
					for _, value := range series.Values {
						timestampMs := uint64(value.Timestamp)
						if timestampMs >= startMs && timestampMs <= maxTimestampMs {
							filteredSeries.Values = append(filteredSeries.Values, value)
						}
					}

					// Always add series to preserve structure (even if empty)
					filteredBucket.Series = append(filteredBucket.Series, filteredSeries)
				}

				// Only add bucket if it has series
				if len(filteredBucket.Series) > 0 {
					filteredData.Aggregations = append(filteredData.Aggregations, filteredBucket)
				}
			}

			bc.trimHeatmapAxisToTheWindow(q, filteredData)

			// Create a new result with the filtered data
			return &qbtypes.Result{
				Type:     result.Type,
				Value:    filteredData,
				Stats:    result.Stats,
				Warnings: result.Warnings,
			}
		}
	}

	// For non-time series data, return as is
	return result
}

// A cache entry can hold a longer time range than the one now requested, and its
// bucket axis spans every sample value seen across that longer range. Once the
// points outside the requested range are dropped, the axis may still list
// buckets that only those dropped points counted into. Left there, they render
// as empty rows that the same request never has when it bypasses the cache.
//
// PromQL and ClickHouse queries name their own buckets, and a histogram's are
// its `le` labels, so only a gauge, sum or summary axis is cut.
func (bc *bucketCache) trimHeatmapAxisToTheWindow(q qbtypes.Query, tsData *qbtypes.TimeSeriesData) {
	metricQuery, isMetricQuery := q.(*builderQuery[qbtypes.MetricAggregation])
	if !isMetricQuery {
		return
	}
	if metricQuery.spec.Aggregations[0].Type == metrictypes.HistogramType {
		return
	}

	for _, aggBucket := range tsData.Aggregations {
		aggBucket.TrimAxisToCountedBuckets()
	}
}