)]}'
{
  "commit": "d7369caa738660f06a14165c3120cc5b94b41f31",
  "tree": "85f193e655ea39e26f239192f0a5ea0faac6e162",
  "parents": [
    "3da067ae399721e785e8389ae08f5d7627c7c220"
  ],
  "author": {
    "name": "Lalit Maganti",
    "email": "lalitm@google.com",
    "time": "Fri Apr 24 14:43:47 2026 +0000"
  },
  "committer": {
    "name": "Lalit Maganti",
    "email": "lalitm@google.com",
    "time": "Fri Apr 24 18:05:57 2026 +0000"
  },
  "message": "tp: Add O(1) hashmap companion to single-column integer indexes\n\nFor single-column indexes on non-null integer/Double columns with no\nduplicates, BuildIndex now also builds a uint64-\u003erow_index hashmap\nalongside the sorted permutation vector. The query planner prefers the\nhashmap for Eq constraints via a new IndexedFilterEqHashMap bytecode,\nwhich does one O(1) Find() instead of an O(log n) binary search over\nthe permutation.\n\nMotivation: resolve_groups in the flamegraph pipeline does a LEFT JOIN\non a unique hash column. Previously each join probe took\nO(log n) through IndexedFilterEq; on large heap-graph traces the\nmerged step was ~21s because of 8.4M log-n probes. On a 1.3M-object\ntrace where the binary search is still only 17 comparisons, this\nmeasures at ~10% speedup on the merged step (0.179s -\u003e 0.160s). The\nwin grows with row count.\n\nPhase 1 (sorted-column binary search) now skips Eq specs on columns\nthat have a hashmap index companion, so those fall through to Phase 2\n(IndexConstraints) where the new bytecode is emitted.\n\nCorrectness: full diff-test suite (1356 tests) is green and manual\nA/B on the flamegraph pipeline produces bit-identical output between\nhashmap-on and hashmap-off.\n\nThe hashmap companion is opt-in via CanBuildHashMapEqIndex: single\ncolumn, non-null, integer-like type, no duplicates (checked by an\nexact scan over the sorted permutation, because the\nHasDuplicates/NoDuplicates metadata is conservative on 64-bit hash\ncolumns).\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "fdeffffb00ed961400db3b5f27b137725d489367",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/common/storage_types.h",
      "new_id": "373ef0cf6892be81459e88b05ffa7c7fa2cf3f26",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/common/storage_types.h"
    },
    {
      "type": "modify",
      "old_id": "d09d35e543266f0b6cf6ad412849cf96b014aaf8",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/dataframe/dataframe.cc",
      "new_id": "57fb800c415b1a09885e7738ad09f11e115adeab",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/dataframe/dataframe.cc"
    },
    {
      "type": "modify",
      "old_id": "cc004f3e88c163aeaa39d6ae01001871d9b76ac4",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/dataframe/query_plan.cc",
      "new_id": "88403a286dd8d39eb6e00800c6407f07bc56fd3b",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/dataframe/query_plan.cc"
    },
    {
      "type": "modify",
      "old_id": "1d21646f2d9740e295410784a41599cd5fe44e61",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/dataframe/query_plan.h",
      "new_id": "456b5b4e6c1a6605eee4f6fec056c0de5151b288",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/dataframe/query_plan.h"
    },
    {
      "type": "modify",
      "old_id": "7e943ef3ee6988f73886ca921b3edeeb8322332c",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/dataframe/types.h",
      "new_id": "7132b0ad4efdac6c086ba157f77adc1c7ae47105",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/dataframe/types.h"
    },
    {
      "type": "modify",
      "old_id": "5014364c75bbca4ba67ae9953249011c3b17f4df",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/interpreter/bytecode_instructions.h",
      "new_id": "71c0e424466b2a457a528b18f271e4778865eba6",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/interpreter/bytecode_instructions.h"
    },
    {
      "type": "modify",
      "old_id": "efb8bb18c94e57a863eca207569036ec49e269fc",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/interpreter/bytecode_interpreter_impl.h",
      "new_id": "c9d509dc5b714070ae6fc06b07c71096faa6f165",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/interpreter/bytecode_interpreter_impl.h"
    },
    {
      "type": "modify",
      "old_id": "6a38f728cca54ce7c587a2781d98aa23e3927d59",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/interpreter/bytecode_registers.h",
      "new_id": "906307f1151b9bcbd1f0c171de780e223d6fe6bb",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/interpreter/bytecode_registers.h"
    },
    {
      "type": "modify",
      "old_id": "500298e20cd7d8b96a12deec442450ee0331e839",
      "old_mode": 33188,
      "old_path": "src/trace_processor/core/interpreter/interpreter_types.h",
      "new_id": "4289c9998b508beadbb06ac23ef76f6524b0e0e0",
      "new_mode": 33188,
      "new_path": "src/trace_processor/core/interpreter/interpreter_types.h"
    }
  ]
}