tp: pre-aggregate by path_hash in _heap_graph_path_hash_aggregate (#8071)

In `_heap_graph_path_hash_aggregate`
(`android.memory.heap_graph.helpers`), joining `$tab` to
`heap_graph_object` and `heap_graph_class` and projecting string columns
before `GROUP BY path_hash` forced SQLite to decode string and class
columns for every reachable object (`1.7M-4.1M` rows) and build a
multi-column temporary B-tree for the `GROUP BY`.

Pre-aggregate the integer size and count columns by `path_hash` first
using `FROM $tab CROSS JOIN heap_graph_object USING (id) GROUP BY
path_hash` so `Dataframe` consumes the `GROUP BY` sort on `path_hash`
directly in C++ and probes `heap_graph_object.id` via `O(1)` `IdSorted`
lookup. Then join `heap_graph_object` and `heap_graph_class` once per
distinct `path_hash` group (`335K-450K` rows, 5x-12x fewer lookups), and
remove the redundant second `GROUP BY path_hash` on the `[native]`
branch. This speeds up `_heap_graph_path_hash_aggregate` by 1.6x-2.4x.

Change-Id: Ia97e29f876d1e10cfd6e370de1d1d88dcf056b85

src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql

diff --git a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql
index b89cc37..1696d19 100644
--- a/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql
+++ b/src/trace_processor/perfetto_sql/stdlib/android/memory/heap_graph/helpers.sql
@@ -94,15 +94,17 @@
 RETURNS TableOrSubquery
 AS (
   WITH
-    x AS (
+    -- Pre-aggregate integer columns by path_hash first. CROSS JOIN keeps $tab
+    -- as the outer table so Dataframe consumes GROUP BY path_hash in C++ and
+    -- probes heap_graph_object.id via O(1) IdSorted lookup.
+    agg_by_hash AS (
       SELECT
-        o.graph_sample_ts,
-        o.upid,
+        -- All objects sharing a path_hash have the same (upid, graph_sample_ts,
+        -- root_type, heap_type) and class display name, so MIN(id) picks a
+        -- deterministic representative object to resolve those columns below.
+        MIN(id) AS sample_id,
         path_hash,
         parent_path_hash,
-        coalesce(c.deobfuscated_name, c.name, '') AS name,
-        o.root_type,
-        o.heap_type,
         count() AS self_count,
         -- -1 is a placeholder sentinel (see HeapGraphTracker::GetOrInsertObject
         -- in heap_graph_tracker.cc) for forward-referenced objects in
@@ -111,40 +113,44 @@
         sum(o.native_size > 0) AS self_native_count,
         sum(o.native_size) AS self_native_size
       FROM $tab
-      JOIN heap_graph_object AS o
+      CROSS JOIN heap_graph_object AS o
         USING (id)
-      JOIN heap_graph_class AS c
-        ON o.type_id = c.id
       GROUP BY
         path_hash
     )
   SELECT
-    graph_sample_ts,
-    upid,
-    hash(path_hash, 'native', '') AS path_hash,
-    path_hash AS parent_path_hash,
-    '[native] ' || x.name AS name,
-    root_type,
+    o.graph_sample_ts,
+    o.upid,
+    hash(a.path_hash, 'native', '') AS path_hash,
+    a.path_hash AS parent_path_hash,
+    '[native] ' || coalesce(c.deobfuscated_name, c.name, '') AS name,
+    o.root_type,
     'HEAP_TYPE_NATIVE' AS heap_type,
-    sum(x.self_native_count) AS self_count,
-    sum(x.self_native_size) AS self_size
-  FROM x
+    a.self_native_count AS self_count,
+    a.self_native_size AS self_size
+  FROM agg_by_hash AS a
+  JOIN heap_graph_object AS o
+    ON a.sample_id = o.id
+  JOIN heap_graph_class AS c
+    ON o.type_id = c.id
   WHERE
-    x.self_native_size > 0
-  GROUP BY
-    path_hash
+    a.self_native_size > 0
   UNION ALL
   SELECT
-    graph_sample_ts,
-    upid,
-    path_hash,
-    parent_path_hash,
-    name,
-    root_type,
-    heap_type,
-    self_count,
-    self_size
-  FROM x
+    o.graph_sample_ts,
+    o.upid,
+    a.path_hash,
+    a.parent_path_hash,
+    coalesce(c.deobfuscated_name, c.name, '') AS name,
+    o.root_type,
+    o.heap_type,
+    a.self_count,
+    a.self_size
+  FROM agg_by_hash AS a
+  JOIN heap_graph_object AS o
+    ON a.sample_id = o.id
+  JOIN heap_graph_class AS c
+    ON o.type_id = c.id
   ORDER BY
     path_hash
 );

test/trace_processor/diff_tests/stdlib/android/heap_graph_tests.py

diff --git a/test/trace_processor/diff_tests/stdlib/android/heap_graph_tests.py b/test/trace_processor/diff_tests/stdlib/android/heap_graph_tests.py
index 8265121..3dc49fd 100644
--- a/test/trace_processor/diff_tests/stdlib/android/heap_graph_tests.py
+++ b/test/trace_processor/diff_tests/stdlib/android/heap_graph_tests.py
@@ -103,6 +103,24 @@
           "java.lang.String",1,666,1,666
         """))
 
+  def test_heap_graph_class_tree_native_size(self):
+    return DiffTestBlueprint(
+        trace=Path('../../parser/profiling/heap_graph_native_size.textproto'),
+        query="""
+          INCLUDE PERFETTO MODULE android.memory.heap_graph.class_tree;
+
+          SELECT p.name AS parent_name, c.name, c.heap_type, c.self_count, c.self_size
+          FROM _heap_graph_class_tree c
+          LEFT JOIN _heap_graph_class_tree p ON c.parent_id = p.id
+          WHERE c.name GLOB '*Bitmap*'
+          ORDER BY c.name;
+        """,
+        out=Csv("""
+          "parent_name","name","heap_type","self_count","self_size"
+          "android.graphics.Bitmap","[native] android.graphics.Bitmap","HEAP_TYPE_NATIVE",1,123456
+          "[NULL]","android.graphics.Bitmap","[NULL]",1,46
+        """))
+
   # The same class loaded by two class loaders has the same name but distinct
   # type_ids. The class tree keys on class name, so the two instances must
   # coalesce into a single node (self_count = 2) rather than splitting.