#111

Committed 11 Sep 2025 06:50PM UTC coverage: 77.045% (-0.3%) from 77.346%

Build # #111

Build Type

push

Committed by

Commit Message

Remove unused imports

Run Details

536 of 758 branches covered (70.71%)

Branch coverage included in aggregate %.

1018 of 1259 relevant lines covered (80.86%)

14202.75 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.7

/src/modules/constructRelationalGraph.js

// @flow
import {initialState} from './data';

import type {
  JoinCondition,
  SelectionCondition,
  Expression,
  Graph,
} from './types';

// Create a node of the table name with relevant fields
const addNode = (
  graph: Graph,
  tableName: string,
  selection?: ?SelectionCondition
) => {
  if (!(tableName in graph)) {
    graph[tableName] = {
      selections: [],
      edges: {},
    };
  }
  if (selection) {
    graph[tableName]['selections'].push(selection);
  }
  return tableName;
};

// Add an edge for two tables if there's a valid join relation between them
const addEdge = (
  graph: Graph,
  leftTable: string,
  rightTable: string,
  joinCondition: JoinCondition,
  joinType: string,
  leftSelection?: ?SelectionCondition,
  rightSelection?: ?SelectionCondition
) => {
  addNode(graph, leftTable, leftSelection);
  addNode(graph, rightTable, rightSelection);
  if (!(rightTable in graph[leftTable]['edges'])) {
    graph[leftTable]['edges'][rightTable] = [];
  }
  if (!(leftTable in graph[rightTable]['edges'])) {
    graph[rightTable]['edges'][leftTable] = [];
  }
  const edge = {condition: joinCondition, type: joinType};
  graph[leftTable]['edges'][rightTable].push(edge);
  graph[rightTable]['edges'][leftTable].push(edge);
};

const conditionIsOnValidAttributes = (
  attribute: string,
  tables: Array<string>
) => {
  const {sourceData} = initialState;
  for (const table of tables) {
    if (sourceData[table] && sourceData[table].columns.includes(attribute)) {
      return true;
    }
  }
  return false;
};

// function to check if a selection condition is a join condition
// assuming that the selection condition is on a single table and join condition is between two tables
const isValidJoinColumn = (attribute: string, tables: Array<string>) => {
  if (attribute.includes('.')) {
    const table = attribute.split('.')[0];
    if (!tables.includes(table)) return false;
  } else if (!conditionIsOnValidAttributes(attribute, tables)) {
    return false;
  }
  return true;
};

export const getTableFromAttribute = (
  attribute: string,
  tables: Array<string>
): string => {
  if (attribute.includes('.')) {
    return attribute.split('.')[0];
  }
  for (const table of tables) {
    if (conditionIsOnValidAttributes(attribute, [table])) {
      return table;
    }
  }
  // this should never happen except for edge cases
  return '';
};

const parseSelectionExpression = (
  graph: Graph,
  expr: Expression,
  tables: Array<string>,
  globalSelections: Array<SelectionCondition>
) => {
  if ('and' in expr) {
    const conditions = expr['and'].clauses;
    for (const condition of conditions) {
      parseSelectionExpression(graph, condition, tables, globalSelections);
    }
  } else if ('cmp' in expr) {
    const selection = expr['cmp'];
    if (
      isValidJoinColumn(selection.lhs, tables) &&
      isValidJoinColumn(selection.rhs, tables)
    ) {
      // this in future can be used as a join condition
      // right now we are just adding it to the global selections
      globalSelections.push(expr);
    } else {
      const {lhs, rhs} = selection;
      const leftTable = getTableFromAttribute(lhs, tables);
      const rightTable = getTableFromAttribute(rhs, tables);
      const table = leftTable || rightTable;
      if (table !== '') addNode(graph, table, expr);
      else globalSelections.push(expr);
    }
  } else {
    console.error(
      'Invalid selection expression for Join Order Optimization',
      expr
    );
  }
};

const parseJoinExpression = (
  graph: Graph,
  expr: Expression,
  joinType: string,
  tables: Array<string>
): void => {
  if (typeof expr === 'string') {
    throw new Error(
      'Invalid join expression for Join Order Optimization. This type of join condition is not supported currently'
    );
  } else if ('and' in expr) {
    const conditions = expr['and'].clauses;
    for (const condition of conditions) {
      parseJoinExpression(graph, condition, joinType, tables);
    }
  } else if ('cmp' in expr) {
    const {lhs, rhs} = expr['cmp'];
    const leftTable = getTableFromAttribute(lhs, tables);
    const rightTable = getTableFromAttribute(rhs, tables);
    if (leftTable === '' || rightTable === '') {
      throw new Error(
        'Invalid join expression for Join Order Optimization. This type of join condition is not supported currently'
      );
    }
    addEdge(graph, leftTable, rightTable, expr['cmp'], joinType);
  } else {
    throw new Error('Invalid join expression for Join Order Optimization');
  }
};

// function used to check all the tables that are involved in this query
const preParseExpression = (expr: Expression, tables: Array<string>) => {
  if (typeof expr === 'object') {
    if ('relation' in expr) tables.push(expr['relation']);
    for (const key in expr) {
      preParseExpression(expr[key], tables);
    }
  } else if (Array.isArray(expr)) {
    for (const item of expr) {
      preParseExpression(item, tables);
    }
  }
};

const parseExpression = (
  graph: Graph,
  expr: Expression,
  tables: Array<string>,
  globalSelections: Array<SelectionCondition>
): void => {
  if ('selection' in expr) {
    const selection = expr['selection'].arguments.select;
    parseSelectionExpression(graph, selection, tables, globalSelections);
    const children = expr['selection'].children;
    for (const child of children) {
      parseExpression(graph, child, tables, globalSelections);
    }
  } else if ('join' in expr) {
    const joinExpr = expr['join'];
    const {left, right, type, condition} = joinExpr;
    parseJoinExpression(graph, condition, type, tables);
    parseExpression(graph, left, tables, globalSelections);
    parseExpression(graph, right, tables, globalSelections);
  } else if ('relation' in expr) {
    const table = expr['relation'];
    addNode(graph, table);
  } else {
    throw new Error('Invalid expression type for join order optimization');
  }
};

/**
 * Constructs a relational graph from the expr
 * Nodes will have (tableName and selection criteria if any on that table)
 * Edges are the join relations
 * @param {*} expr
 */
export const constructRelationalGraph = (expr: {
  [key: string]: any,
}): {
  graph: Graph,
  globalSelections: Array<SelectionCondition>,
  canOptimize: boolean,
} => {
  const graph: Graph = {};
  const tables: Array<string> = [];
  const globalSelections: Array<SelectionCondition> = [];
  preParseExpression(expr, tables);
  // if duplicate tables found, console error and don't proceed
  const uniqueTables = new Set(tables);
  if (uniqueTables.size !== tables.length) {
    console.error('Duplicate tables found in the query');
    return {
      graph: graph,
      globalSelections: globalSelections,
      canOptimize: false,
    };
  }

  let canOptimize = true;
  try {
    parseExpression(graph, expr, tables, globalSelections);
  } catch (e) {
    console.error(e.message);
    canOptimize = false;
  }
  return {graph: graph, globalSelections: globalSelections, canOptimize};
};

1	// @flow
2	import {initialState} from './data';
3
4	import type {
5	JoinCondition,
6	SelectionCondition,
7	Expression,
8	Graph,
9	} from './types';
10
11	// Create a node of the table name with relevant fields
12	const addNode = (	7✔
13	graph: Graph,
14	tableName: string,
15	selection?: ?SelectionCondition
16	) => {
17	if (!(tableName in graph)) {	88✔
18	graph[tableName] = {	31✔
19	selections: [],
20	edges: {},
21	};
22	}
23	if (selection) {	88✔
24	graph[tableName]['selections'].push(selection);	27✔
25	}
26	return tableName;	88✔
27	};
28
29	// Add an edge for two tables if there's a valid join relation between them
30	const addEdge = (	7✔
31	graph: Graph,
32	leftTable: string,
33	rightTable: string,
34	joinCondition: JoinCondition,
35	joinType: string,
36	leftSelection?: ?SelectionCondition,
37	rightSelection?: ?SelectionCondition
38	) => {
39	addNode(graph, leftTable, leftSelection);	16✔
40	addNode(graph, rightTable, rightSelection);	16✔
41	if (!(rightTable in graph[leftTable]['edges'])) {	16!
42	graph[leftTable]['edges'][rightTable] = [];	16✔
43	}
44	if (!(leftTable in graph[rightTable]['edges'])) {	16!
45	graph[rightTable]['edges'][leftTable] = [];	16✔
46	}
47	const edge = {condition: joinCondition, type: joinType};	16✔
48	graph[leftTable]['edges'][rightTable].push(edge);	16✔
49	graph[rightTable]['edges'][leftTable].push(edge);	16✔
50	};
51
52	const conditionIsOnValidAttributes = (	7✔
53	attribute: string,
54	tables: Array<string>
55	) => {
56	const {sourceData} = initialState;	98✔
57	for (const table of tables) {	98✔
58	if (sourceData[table] && sourceData[table].columns.includes(attribute)) {	130!
59	return true;	×
60	}
61	}
62	return false;	98✔
63	};
64
65	// function to check if a selection condition is a join condition
66	// assuming that the selection condition is on a single table and join condition is between two tables
67	const isValidJoinColumn = (attribute: string, tables: Array<string>) => {	7✔
68	if (attribute.includes('.')) {	56✔
69	const table = attribute.split('.')[0];	27✔
70	if (!tables.includes(table)) return false;	27!
71	} else if (!conditionIsOnValidAttributes(attribute, tables)) {	29!
72	return false;	29✔
73	}
74	return true;	27✔
75	};
76
77	export const getTableFromAttribute = (	7✔
78	attribute: string,
79	tables: Array<string>
80	): string => {
81	if (attribute.includes('.')) {	92✔
82	return attribute.split('.')[0];	59✔
83	}
84	for (const table of tables) {	33✔
85	if (conditionIsOnValidAttributes(attribute, [table])) {	69!
86	return table;	×
87	}
88	}
89	// this should never happen except for edge cases
90	return '';	33✔
91	};
92
93	const parseSelectionExpression = (	7✔
94	graph: Graph,
95	expr: Expression,
96	tables: Array<string>,
97	globalSelections: Array<SelectionCondition>
98	) => {
99	if ('and' in expr) {	38✔
100	const conditions = expr['and'].clauses;	8✔
101	for (const condition of conditions) {	8✔
102	parseSelectionExpression(graph, condition, tables, globalSelections);	21✔
103	}
104	} else if ('cmp' in expr) {	30✔
105	const selection = expr['cmp'];	29✔
106	if (	29!
107	isValidJoinColumn(selection.lhs, tables) &&	56✔
108	isValidJoinColumn(selection.rhs, tables)
109	) {
110	// this in future can be used as a join condition
111	// right now we are just adding it to the global selections
112	globalSelections.push(expr);	×
113	} else {
114	const {lhs, rhs} = selection;	29✔
115	const leftTable = getTableFromAttribute(lhs, tables);	29✔
116	const rightTable = getTableFromAttribute(rhs, tables);	29✔
117	const table = leftTable \|\| rightTable;	29✔
118	if (table !== '') addNode(graph, table, expr);	29✔
119	else globalSelections.push(expr);	2✔
120	}
121	} else {
122	console.error(	1✔
123	'Invalid selection expression for Join Order Optimization',
124	expr
125	);
126	}
127	};
128
129	const parseJoinExpression = (	7✔
130	graph: Graph,
131	expr: Expression,
132	joinType: string,
133	tables: Array<string>
134	): void => {
135	if (typeof expr === 'string') {	20✔
136	throw new Error(	1✔
137	'Invalid join expression for Join Order Optimization. This type of join condition is not supported currently'
138	);
139	} else if ('and' in expr) {	19✔
140	const conditions = expr['and'].clauses;	2✔
141	for (const condition of conditions) {	2✔
142	parseJoinExpression(graph, condition, joinType, tables);	4✔
143	}
144	} else if ('cmp' in expr) {	17!
145	const {lhs, rhs} = expr['cmp'];	17✔
146	const leftTable = getTableFromAttribute(lhs, tables);	17✔
147	const rightTable = getTableFromAttribute(rhs, tables);	17✔
148	if (leftTable === '' \|\| rightTable === '') {	17✔
149	throw new Error(	1✔
150	'Invalid join expression for Join Order Optimization. This type of join condition is not supported currently'
151	);
152	}
153	addEdge(graph, leftTable, rightTable, expr['cmp'], joinType);	16✔
154	} else {
155	throw new Error('Invalid join expression for Join Order Optimization');	×
156	}
157	};
158
159	// function used to check all the tables that are involved in this query
160	const preParseExpression = (expr: Expression, tables: Array<string>) => {	7✔
161	if (typeof expr === 'object') {	509✔
162	if ('relation' in expr) tables.push(expr['relation']);	290✔
163	for (const key in expr) {	290✔
164	preParseExpression(expr[key], tables);	491✔
165	}
166	} else if (Array.isArray(expr)) {	219!
167	for (const item of expr) {	×
168	preParseExpression(item, tables);	×
169	}
170	}
171	};
172
173	const parseExpression = (	7✔
174	graph: Graph,
175	expr: Expression,
176	tables: Array<string>,
177	globalSelections: Array<SelectionCondition>
178	): void => {
179	if ('selection' in expr) {	62✔
180	const selection = expr['selection'].arguments.select;	17✔
181	parseSelectionExpression(graph, selection, tables, globalSelections);	17✔
182	const children = expr['selection'].children;	17✔
183	for (const child of children) {	17✔
184	parseExpression(graph, child, tables, globalSelections);	17✔
185	}
186	} else if ('join' in expr) {	45✔
187	const joinExpr = expr['join'];	16✔
188	const {left, right, type, condition} = joinExpr;	16✔
189	parseJoinExpression(graph, condition, type, tables);	16✔
190	parseExpression(graph, left, tables, globalSelections);	14✔
191	parseExpression(graph, right, tables, globalSelections);	14✔
192	} else if ('relation' in expr) {	29!
193	const table = expr['relation'];	29✔
194	addNode(graph, table);	29✔
195	} else {
196	throw new Error('Invalid expression type for join order optimization');	×
197	}
198	};
199
200	/**
201	* Constructs a relational graph from the expr
202	* Nodes will have (tableName and selection criteria if any on that table)
203	* Edges are the join relations
204	* @param {*} expr
205	*/
206	export const constructRelationalGraph = (expr: {	7✔
207	[key: string]: any,
208	}): {
209	graph: Graph,
210	globalSelections: Array<SelectionCondition>,
211	canOptimize: boolean,
212	} => {
213	const graph: Graph = {};	18✔
214	const tables: Array<string> = [];	18✔
215	const globalSelections: Array<SelectionCondition> = [];	18✔
216	preParseExpression(expr, tables);	18✔
217	// if duplicate tables found, console error and don't proceed
218	const uniqueTables = new Set(tables);	18✔
219	if (uniqueTables.size !== tables.length) {	18✔
220	console.error('Duplicate tables found in the query');	1✔
221	return {	1✔
222	graph: graph,
223	globalSelections: globalSelections,
224	canOptimize: false,
225	};
226	}
227
228	let canOptimize = true;	17✔
229	try {	17✔
230	parseExpression(graph, expr, tables, globalSelections);	17✔
231	} catch (e) {
232	console.error(e.message);	2✔
233	canOptimize = false;	2✔
234	}
235	return {graph: graph, globalSelections: globalSelections, canOptimize};	17✔
236	};

dataunitylab / relational-playground / #111

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous