[Prometheus] PromQLエンジン内部構造：パーサーから実行エンジンまで

PromQL文字列
    |
    v
+----------+
| Lexer    |  （トークン化）
+----------+
    |
    v
+----------+
| Parser   |  （構文解析）
+----------+
    |
    v
+----------+
| AST      |  （抽象構文木）
+----------+
    |
    v
+----------+
| Analyzer |  （最適化/検証）
+----------+
    |
    v
+----------+
| Engine   |  （評価/実行）
+----------+
    |
    v
結果（Matrix/Vector/Scalar）

入力: rate(http_requests_total[5m]) > 10

トークンストリーム：
  IDENTIFIER("rate")
  LEFT_PAREN
  IDENTIFIER("http_requests_total")
  LEFT_BRACKET
  DURATION("5m")
  RIGHT_BRACKET
  RIGHT_PAREN
  GTR
  NUMBER(10)

リテラル：
  NUMBER      - 整数/浮動小数点（例: 42, 3.14）
  STRING      - 文字列リテラル（例: "hello"）
  DURATION    - 時間範囲（例: 5m, 1h, 30s）

識別子：
  IDENTIFIER  - メトリクス名、ラベル名
  METRIC_IDENTIFIER - メトリクス識別子

演算子：
  ADD, SUB, MUL, DIV, MOD, POW
  EQL, NEQ, LSS, GTR, LTE, GTE
  AND, OR, UNLESS

キーワード：
  BY, WITHOUT, ON, IGNORING
  GROUP_LEFT, GROUP_RIGHT
  OFFSET, BOOL
  SUM, AVG, MIN, MAX, COUNT, ...

パーサー動作フロー：
1. トークンストリームから次のトークンを読み取り
2. prefix解析関数呼び出し（リテラル、単項演算、括弧など）
3. 現在の優先度より高いinfix演算子があればinfix解析
4. ASTノードを返す

優先順位（低い順）：
1. OR
2. AND, UNLESS
3. ==, !=, <, >, <=, >=（比較）
4. +, -（加減算）
5. *, /, %（乗除算）
6. ^（べき乗、右結合）
7. 単項 +, -

Expr（式インターフェース）
  |
  +-- NumberLiteral        （数値リテラル）
  +-- StringLiteral        （文字列リテラル）
  +-- VectorSelector       （即時ベクターセレクタ）
  +-- MatrixSelector       （範囲ベクターセレクタ）
  +-- AggregateExpr        （集約式）
  +-- BinaryExpr           （二項演算式）
  +-- UnaryExpr            （単項演算式）
  +-- Call                 （関数呼び出し）
  +-- ParenExpr            （括弧式）
  +-- SubqueryExpr         （サブクエリ式）
  +-- StepInvariantExpr    （step不変式）

AggregateExpr (sum, by=[job])
  |
  +-- Call (rate)
        |
        +-- MatrixSelector
              |
              +-- VectorSelector (http_requests_total)
              +-- Range: 5m

Engine:
  +-- queryable      （TSDBストレージインターフェース）
  +-- maxSamples     （最大サンプル数制限）
  +-- timeout        （クエリタイムアウト）
  +-- activeQueries  （アクティブクエリカウンタ）
  +-- maxConcurrency （最大同時クエリ数）

リクエスト: GET /api/v1/query?query=up&time=1609459200

処理：
1. AST生成
2. time=1609459200で一度評価
3. 結果: Vector（各時系列に対する単一値）

リクエスト: GET /api/v1/query_range?query=up&start=1609455600&end=1609459200&step=60

処理：
1. AST生成
2. startからendまでstep（60秒）間隔で繰り返し評価
3. 各stepでinstant queryのように評価
4. 結果: Matrix（各時系列に対する時系列値配列）

query: rate(http_requests_total[5m])
start: T0, end: T0+300s, step: 60s

Step評価：
  T0:      rate(T0-5mからT0までのサンプル)
  T0+60:   rate(T0+60-5mからT0+60までのサンプル)
  T0+120:  rate(T0+120-5mからT0+120までのサンプル)
  T0+180:  rate(T0+180-5mからT0+180までのサンプル)
  T0+240:  rate(T0+240-5mからT0+240までのサンプル)
  T0+300:  rate(T0+300-5mからT0+300までのサンプル)

評価時点: T
lookback delta: 5m

サンプル検索範囲: (T - 5m, T]

動作：
1. T以前5分以内の最新サンプルを検索
2. そのサンプルがstale markerでなければ結果に含む
3. 5分以内にサンプルがなければその時系列を除外

重要: 正確にT時点のサンプルがなくてもよい
      lookback delta内の最新サンプルを使用

関数登録情報：
  Name:       "rate"
  ArgTypes:   [ValueTypeMatrix]     （引数タイプ）
  ReturnType: ValueTypeVector       （戻り値タイプ）
  Call:       funcRate              （実際の実装関数）
  Variadic:   0                     （可変引数数）

rate(counter[5m])の評価：

1. 5分範囲のサンプル抽出: [s1, s2, s3, ..., sN]
2. Counterリセット検知と補正：
   - 値が減少したら前の値を累積に加算
3. 補正された総増加量計算：
   resultValue = (last - first) + counterCorrection
4. 外挿（extrapolation）：
   - 範囲開始/終了を超える時間比率計算
5. 秒あたりの増加率：
   result = extrapolatedIncrease / rangeDurationSeconds

histogram_quantile(phi, buckets)の評価：

1. leラベルでバケットをソート
2. 各バケットの累積カウントを収集
3. phi（例: 0.95） * total_count = target_countを計算
4. target_countを含むバケットを検索
5. バケット境界間で線形補間：
   bucketStart + (bucketEnd - bucketStart) *
   (target - countBelow) / (countInBucket)

sum by (job) (metric)の評価：

1. metricのすべての時系列を収集
2. jobラベル値でグルーピング
3. 各グループ内で値を合算
4. 結果時系列: jobラベルのみ保持

実装：
- ハッシュマップでグループ管理
- ラベルセットのハッシュをキーとして使用
- 衝突時は正確なラベル比較

metric_a + metric_b

マッチングアルゴリズム：
1. 両方のベクターの時系列をラベルセットでインデックス
2. マッチングラベルセットが同一のペアを検索
3. 演算実行（ここでは値の加算）
4. 結果時系列に左側のラベルセットを使用

パフォーマンス：
- ハッシュジョイン方式でO(n+m)時間計算量
- 小さい方をハッシュテーブルとして構築

metric_a * on(job) group_left metric_b

処理：
1. on(job)でマッチングキーを決定
2. metric_b（one側）をjob別ハッシュマップにインデックス
3. metric_a（many側）の各時系列に対して：
   a. jobラベルでmetric_bのマッチング項目を検索
   b. 演算実行
   c. metric_aのすべてのラベルを保持（group_left）

max_over_time(rate(http_requests_total[5m])[30m:1m])

評価過程：
1. 外部関数（max_over_time）がrange vectorを必要
2. サブクエリ部分: rate(http_requests_total[5m])[30m:1m]
3. 内部評価：
   - 現在時点（T）の30分前からTまで
   - 1分間隔でrate(http_requests_total[5m])を評価
   - 30個のinstant vector結果を生成
4. range vectorに変換
5. max_over_timeが各時系列の最大値を計算

サブクエリ評価の主要最適化：
1. 内部クエリのrange vectorを再利用（同一時系列）
2. stepアラインメント：サブクエリのstepを外部stepに整列
3. resolutionが指定されなければglobal evaluation_intervalを使用

--query.max-samples（デフォルト50,000,000）

カウント方式：
- 各stepでロード/生成されたサンプル数を累積
- range vectorの場合は範囲内のすべてのサンプルをカウント
- 制限超過時にクエリを即座に中断

--query.max-concurrency（デフォルト20）

実装：
- セマフォで同時クエリ数を制限
- 新クエリがセマフォ取得を待機
- タイムアウト内に取得失敗時にエラーを返す

ポイントプール動作：
1. クエリ開始時にポイントスライスをプールから割り当て
2. step評価間で再利用
3. クエリ完了時にプールに返却
4. sync.Poolを使用してGC負担を軽減

Native Histogramは既存のfloatサンプルと異なる処理パス：
1. ヒストグラムスキーマ（resolution）の整列
2. バケット単位でのマージ
3. 集約時にスキーマ変換が必要な場合は自動実行

sum(native_histogram_metric)の評価：
1. 各時系列のヒストグラムを収集
2. スキーマが異なる場合はより低い解像度に統一
3. バケット別カウントを合算
4. sumとcountフィールドを合算

複数ブロックにまたがる同一時系列が存在する場合：
1. 各ブロックで時系列集合を検索
2. マージソートで統合
3. チャンクレベルで時間範囲フィルタリング
4. 重複排除

stepに関係なく同一結果を返す式を検知：
- 数値リテラル
- offsetのないスカラー関数
- 特定の集約結果

検知された場合：
- 一度だけ評価してすべてのstepに結果をコピー
- 不要な繰り返し評価を排除

最適化パス：
1. 定数畳み込み（constant folding）: 2 + 3 -> 5
2. ラベルマッチング最適化：インデックスヒント生成
3. 不要なラベル演算の除去
4. 空の結果の早期リターン

1. "query processing would load too many samples"
   - max-samples制限超過
   - 解決：クエリ範囲の縮小または制限の増加

2. "query timed out in expression evaluation"
   - query.timeout超過
   - 解決：クエリ最適化またはタイムアウトの増加

3. "found duplicate series for the match group"
   - ベクターマッチングで多対一関係にgroup_left/right未指定
   - 解決：group_leftまたはgroup_rightの追加

4. "many-to-many matching not allowed"
   - 両側とも多数のマッチングはサポートされない
   - 解決：集約で片側を一（one）に縮小