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-- sqlformat file off 17 18CREATE PERFETTO MACRO _graph_scan_df_agg(x ColumnName, y ColumnName) 19RETURNS _ProjectionFragment AS __intrinsic_stringify!($x), init_table.$y; 20 21CREATE PERFETTO MACRO _graph_scan_bind(x ColumnName, y ColumnName) 22RETURNS Expr AS __intrinsic_table_ptr_bind(result.$x, __intrinsic_stringify!($y)); 23 24CREATE PERFETTO MACRO _graph_scan_select(x ColumnName, y ColumnName) 25RETURNS _ProjectionFragment AS result.$x as $y; 26 27-- Performs a "scan" over the graph starting at `init_table` and using `graph_table` 28-- for edges to follow. 29-- 30-- See https://en.wikipedia.org/wiki/Prefix_sum#Scan_higher_order_function for 31-- details of what a scan means. 32CREATE PERFETTO MACRO _graph_scan( 33 -- The table containing the edges of the graph. Needs to have the columns 34 -- `source_node_id` and `dest_node_id`. 35 graph_table TableOrSubquery, 36 -- The table of nodes to start the scan from. Needs to have the column `id` 37 -- and all columns specified by `scan_columns`. 38 init_table TableOrSubquery, 39 -- A parenthesised and comma separated list of columns which will be returned 40 -- by the scan. Should match exactly both the names and order of the columns 41 -- in both `init_table` and `step_query`. 42 -- 43 -- Example: (cumulative_sum, cumulative_count). 44 scan_columns _ColumnNameList, 45 -- A subquery which is reads all the data (from a variable table called $table) 46 -- for a single step of the scan and performs some computation for each node in 47 -- the step. 48 -- 49 -- Should return a column `id` and all columns specified by `scan_columns`. 50 step_query TableOrSubquery 51) 52RETURNS TableOrSubquery AS 53( 54 select 55 c0 as id, 56 __intrinsic_token_apply!( 57 _graph_scan_select, 58 (c1, c2, c3, c4, c5, c6, c7), 59 $scan_columns 60 ) 61 from __intrinsic_table_ptr(__intrinsic_graph_scan( 62 ( 63 select __intrinsic_graph_agg(g.source_node_id, g.dest_node_id) 64 from $graph_table g 65 ), 66 ( 67 select __intrinsic_row_dataframe_agg( 68 'id', init_table.id, 69 __intrinsic_token_apply!( 70 _graph_scan_df_agg, 71 $scan_columns, 72 $scan_columns 73 ) 74 ) 75 from $init_table AS init_table 76 ), 77 __intrinsic_stringify_ignore_table!($step_query), 78 __intrinsic_stringify!($scan_columns) 79 )) result 80 where __intrinsic_table_ptr_bind(result.c0, 'id') 81 and __intrinsic_token_apply_and!( 82 _graph_scan_bind, 83 (c1, c2, c3, c4, c5, c6, c7), 84 $scan_columns 85 ) 86); 87 88-- Performs a "scan" over the graph starting at `init_table` and using `graph_table` 89-- for edges to follow, aggregating on each node wherever possible using `agg_query`. 90-- 91-- See https://en.wikipedia.org/wiki/Prefix_sum#Scan_higher_order_function for 92-- details of what a scan means. 93CREATE PERFETTO MACRO _graph_aggregating_scan( 94 -- The table containing the edges of the graph. Needs to have the columns 95 -- `source_node_id` and `dest_node_id`. 96 graph_table TableOrSubquery, 97 -- The table of nodes to start the scan from. Needs to have the column `id` 98 -- and all columns specified by `agg_columns`. 99 init_table TableOrSubquery, 100 -- A parenthesised and comma separated list of columns which will be returned 101 -- by the scan. Should match exactly both the names and order of the columns 102 -- in both `init_table` and `agg_query`. 103 -- 104 -- Example: (cumulative_sum, cumulative_count). 105 agg_columns _ColumnNameList, 106 -- A subquery which aggregates the data for one step of the scan. Should contain 107 -- the column `id` and all columns specified by `agg_columns`. Should read from 108 -- a variable table labelled `$table`. 109 agg_query TableOrSubquery 110) 111RETURNS TableOrSubquery AS 112( 113 select 114 c0 as id, 115 __intrinsic_token_apply!( 116 _graph_scan_select, 117 (c1, c2, c3, c4, c5, c6, c7), 118 $agg_columns 119 ) 120 from __intrinsic_table_ptr(__intrinsic_graph_aggregating_scan( 121 ( 122 select __intrinsic_graph_agg(g.source_node_id, g.dest_node_id) 123 from $graph_table g 124 ), 125 ( 126 select __intrinsic_row_dataframe_agg( 127 'id', init_table.id, 128 __intrinsic_token_apply!( 129 _graph_scan_df_agg, 130 $agg_columns, 131 $agg_columns 132 ) 133 ) 134 from $init_table AS init_table 135 ), 136 __intrinsic_stringify_ignore_table!($agg_query), 137 __intrinsic_stringify!($agg_columns) 138 )) result 139 where __intrinsic_table_ptr_bind(result.c0, 'id') 140 and __intrinsic_token_apply_and!( 141 _graph_scan_bind, 142 (c1, c2, c3, c4, c5, c6, c7), 143 $agg_columns 144 ) 145); 146