1-- 2-- Copyright 2024 The Android Open Source Project 3-- 4-- Licensed under the Apache License, Version 2.0 (the "License"); 5-- you may not use this file except in compliance with the License. 6-- You may obtain a copy of the License at 7-- 8-- https://www.apache.org/licenses/LICENSE-2.0 9-- 10-- Unless required by applicable law or agreed to in writing, software 11-- distributed under the License is distributed on an "AS IS" BASIS, 12-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13-- See the License for the specific language governing permissions and 14-- limitations under the License. 15 16-- Partitions a tree into a forest of trees based on a given grouping key 17-- in a structure-preserving way. 18-- 19-- Specifically, for each tree in the output forest, all the nodes in that tree 20-- have the same ancestors and descendants as in the original tree *iff* that 21-- ancestor/descendent belonged to the same group. 22-- 23-- Example: 24-- Input 25-- 26-- id | parent_id | group_key 27-- ---|-----------|---------- 28-- 1 | NULL | 1 29-- 2 | 1 | 1 30-- 3 | NULL | 2 31-- 4 | NULL | 2 32-- 5 | 2 | 1 33-- 6 | NULL | 3 34-- 7 | 4 | 2 35-- 8 | 4 | 1 36-- 37-- Or as a graph: 38-- ``` 39-- 1 (1) 40-- / 41-- 2 (1) 42-- / \ 43-- 3 (2) 4 (2) 44-- / \ 45-- 5 (1) 8 (1) 46-- / \ 47-- 6 (3) 7 (2) 48-- ``` 49-- Possible output (order of rows is implementation-defined) 50-- 51-- id | parent_id | group_key 52-- ---|-----------|------- 53-- 1 | NULL | 1 54-- 2 | 1 | 1 55-- 3 | NULL | 2 56-- 4 | NULL | 2 57-- 5 | 2 | 1 58-- 6 | NULL | 3 59-- 7 | 4 | 2 60-- 8 | 2 | 1 61-- 62-- Or as a forest: 63-- ``` 64-- 1 (1) 3 (2) 4 (2) 6 (3) 65-- | | 66-- 2 (1) 7 (2) 67-- / \ 68-- 5 (1) 8 (1) 69-- ``` 70CREATE PERFETTO MACRO tree_structural_partition_by_group( 71 -- A table/view/subquery corresponding to a tree which should be partitioned. 72 -- This table must have the columns "id", "parent_id" and "group_key". 73 -- 74 -- Note: the columns must contain uint32 similar to ids in trace processor 75 -- tables (i.e. the values should be relatively dense and close to zero). The 76 -- implementation makes assumptions on this for performance reasons and, if 77 -- this criteria is not, can lead to enormous amounts of memory being 78 -- allocated. 79 tree_table TableOrSubquery 80) 81-- The returned table has the schema 82-- (id LONG, parent_id LONG, group_key LONG). 83RETURNS TableOrSubquery AS 84( 85 -- Rename the generic columns of __intrinsic_table_ptr to the actual columns. 86 SELECT 87 c0 AS id, 88 c1 AS parent_id, 89 c2 AS group_key 90 FROM __intrinsic_table_ptr( 91 ( 92 -- Aggregate function to perform the partitioning algorithm. 93 SELECT 94 __intrinsic_structural_tree_partition(g.id, g.parent_id, g.group_key) 95 FROM $tree_table AS g 96 ) 97 ) 98 -- Bind the dynamic columns in the |__intrinsic_table_ptr| to the columns of 99 -- the partitioning table. 100 WHERE 101 __intrinsic_table_ptr_bind(c0, 'node_id') 102 AND __intrinsic_table_ptr_bind(c1, 'parent_node_id') 103 AND __intrinsic_table_ptr_bind(c2, 'group_key') 104); 105