1// Copyright (C) 2024 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15import {ColumnOrderClause, Filter, SqlColumn} from './column'; 16 17// The goal of this module is to generate a query statement from the list of columns, filters and order by clauses. 18// The main challenge is that the column definitions are independent, and the columns themselves can reference the same join multiple times: 19// 20// For example, in the following query `parent_slice_ts` and `parent_slice_dur` are both referencing the same join, but we want to include only one join in the final query. 21 22// SELECT 23// parent.ts AS parent_slice_ts, 24// parent.dur AS parent_slice_dur 25// FROM slice 26// LEFT JOIN slice AS parent ON slice.parent_id = parent.id 27 28// Normalised sql column, where the source table is resolved to a unique index. 29type NormalisedSqlColumn = { 30 column: string; 31 // If |joinId| is undefined, then the columnName comes from the primary table. 32 sourceTableId?: number; 33}; 34 35// Normalised source table, where the join constraints are resolved to a normalised columns. 36type NormalisedSourceTable = { 37 table: string; 38 joinOn: {[key: string]: NormalisedSqlColumn}; 39 innerJoin: boolean; 40}; 41 42// Checks whether two join constraints are equal. 43function areJoinConstraintsEqual( 44 a: {[key: string]: NormalisedSqlColumn}, 45 b: {[key: string]: NormalisedSqlColumn}, 46): boolean { 47 if (Object.keys(a).length !== Object.keys(b).length) { 48 return false; 49 } 50 51 for (const key of Object.keys(a)) { 52 if (typeof a[key] !== typeof b[key]) { 53 return false; 54 } 55 if (typeof a[key] === 'string') { 56 return a[key] === b[key]; 57 } 58 const aValue = a[key] as NormalisedSqlColumn; 59 const bValue = b[key] as NormalisedSqlColumn; 60 if ( 61 aValue.column !== bValue.column || 62 aValue.sourceTableId !== bValue.sourceTableId 63 ) { 64 return false; 65 } 66 } 67 return true; 68} 69 70// Class responsible for building a query and maintaing a list of normalised join tables. 71class QueryBuilder { 72 tables: NormalisedSourceTable[] = []; 73 tableAlias: string; 74 75 constructor(tableName: string) { 76 this.tableAlias = `${tableName}_0`; 77 } 78 79 // Normalises a column, including adding if necessary the joins to the list of tables. 80 normalise(column: SqlColumn): NormalisedSqlColumn { 81 if (typeof column === 'string') { 82 return { 83 column: column, 84 }; 85 } 86 const normalisedJoinOn: {[key: string]: NormalisedSqlColumn} = 87 Object.fromEntries( 88 Object.entries(column.source.joinOn).map(([key, value]) => [ 89 key, 90 this.normalise(value), 91 ]), 92 ); 93 94 // Check if this join is already present. 95 for (let i = 0; i < this.tables.length; ++i) { 96 const table = this.tables[i]; 97 if ( 98 table.table === column.source.table && 99 table.innerJoin === (column.source.innerJoin ?? false) && 100 areJoinConstraintsEqual(table.joinOn, normalisedJoinOn) 101 ) { 102 return { 103 column: column.column, 104 sourceTableId: i, 105 }; 106 } 107 } 108 109 // Otherwise, add a new join. 110 this.tables.push({ 111 table: column.source.table, 112 joinOn: normalisedJoinOn, 113 innerJoin: column.source.innerJoin ?? false, 114 }); 115 return { 116 column: column.column, 117 sourceTableId: this.tables.length - 1, 118 }; 119 } 120 121 // Prints a reference to a column, including properly disambiguated table alias. 122 printColumn(column: NormalisedSqlColumn): string { 123 if (column.sourceTableId === undefined) { 124 if (!/^[A-Za-z0-9_]*$/.test(column.column)) { 125 // If this is an expression, don't prefix it with the table name. 126 return column.column; 127 } 128 return `${this.tableAlias}.${column.column}`; 129 } 130 const table = this.tables[column.sourceTableId]; 131 // Dependent tables are 0-indexed, but we want to display them as 1-indexed to reserve 0 for the primary table. 132 return `${table.table}_${column.sourceTableId + 1}.${column.column}`; 133 } 134 135 printJoin(joinIndex: number): string { 136 const join = this.tables[joinIndex]; 137 const alias = `${join.table}_${joinIndex + 1}`; 138 const clauses = Object.entries(join.joinOn).map( 139 ([key, value]) => `${alias}.${key} = ${this.printColumn(value)}`, 140 ); 141 // Join IDs are 0-indexed, but we want to display them as 1-indexed to reserve 0 for the primary table. 142 return `${join.innerJoin ? '' : 'LEFT '}JOIN ${join.table} AS ${alias} ON ${clauses.join(' AND ')}`; 143 } 144} 145 146// Returns a query fetching the columns from the table, with the specified filters and order by clauses. 147// keys of the `columns` object are the names of the columns in the result set. 148export function buildSqlQuery(args: { 149 table: string; 150 columns: {[key: string]: SqlColumn}; 151 filters?: Filter[]; 152 orderBy?: ColumnOrderClause[]; 153}): string { 154 const builder = new QueryBuilder(args.table); 155 156 const normalisedColumns = Object.fromEntries( 157 Object.entries(args.columns).map(([key, value]) => [ 158 key, 159 builder.normalise(value), 160 ]), 161 ); 162 const normalisedFilters = (args.filters || []).map((filter) => ({ 163 op: filter.op, 164 columns: filter.columns.map((column) => builder.normalise(column)), 165 })); 166 const normalisedOrderBy = (args.orderBy || []).map((orderBy) => ({ 167 order: orderBy.direction, 168 column: builder.normalise(orderBy.column), 169 })); 170 171 const formatFilter = (filter: { 172 op: (cols: string[]) => string; 173 columns: NormalisedSqlColumn[]; 174 }) => { 175 return filter.op( 176 filter.columns.map((column) => builder.printColumn(column)), 177 ); 178 }; 179 180 const filterClause = 181 normalisedFilters.length === 0 182 ? '' 183 : `WHERE\n ${normalisedFilters.map(formatFilter).join('\n AND ')}`; 184 const joinClause = builder.tables 185 .map((_, index) => builder.printJoin(index)) 186 .join('\n'); 187 const orderByClause = 188 normalisedOrderBy.length === 0 189 ? '' 190 : `ORDER BY\n ${normalisedOrderBy.map((orderBy) => `${builder.printColumn(orderBy.column)} ${orderBy.order}`).join(', ')}`; 191 192 return ` 193 SELECT 194 ${Object.entries(normalisedColumns) 195 .map(([key, value]) => `${builder.printColumn(value)} AS ${key}`) 196 .join(',\n ')} 197 FROM ${args.table} AS ${builder.tableAlias} 198 ${joinClause} 199 ${filterClause} 200 ${orderByClause} 201 `; 202} 203