#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

90.28

/src/modules/joinOrderOptimization.js

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

import TinyQueue from 'tinyqueue';

import {initialState, applyExpr} from './data';

/**
 * Formats into selection condition format for a given table
 * @param tableExpr - a relational algebra expression object to render
 * @param selections - an array where all created paths should be saved
 * @return a tree structure representing the exppression
 */
const getSelectionExpression = (
  tableExpr: string | {[key: string]: any},
  selections: Array<SelectionCondition>
) => {
  let relation =
    typeof tableExpr === 'string' ? {relation: tableExpr} : tableExpr;
  if (selections.length === 0) {
    return relation;
  }
  let select: {[key: string]: any} = {};
  if (selections.length === 1) {
    select = selections[0];
  } else {
    select = {
      and: {
        clauses: selections,
      },
    };
  }
  return {
    selection: {
      arguments: {
        select: select,
      },
      children: [relation],
    },
  };
};

/**
 * Formats into join condition format for a given table
 * @param joinConditions - a relational algebra expression object to render
 * @return a tree structure representing the exppression
 */
const formatJoinConditions = (joinConditions: Array<JoinCondition>) => {
  if (joinConditions.length === 0) {
    // This should not happen in a well-formed query, but handle gracefully
    console.warn('Empty join conditions encountered');
    return {cmp: {lhs: '1', op: '$eq', rhs: '1'}}; // Dummy true condition
  }
  if (joinConditions.length === 1) {
    return {cmp: joinConditions[0].condition};
  } else {
    const processedJoinConditions = joinConditions.map((joinCondition) => {
      return {cmp: joinCondition.condition};
    });
    return {and: {clauses: processedJoinConditions}};
  }
};

/**
 * Formats into relational expression format for a given table
 * @param tableName - a relational algebra expression object to render
 * @param tablesWithSelections - all tables with selections
 */
const getRelationExpression = (
  tableName: string,
  tablesWithSelections: {[key: string]: any}
) => {
  if (tableName in tablesWithSelections) {
    return tablesWithSelections[tableName];
  }
  return {relation: tableName};
};

/**
 * Parses the join order expression
 * @param tablesWithSelections - all tables with selections
 * @param joinOrder - the join order
 */
const parseJoinOrderExpression = (
  tablesWithSelections: {[key: string]: any},
  joinOrder: Array<string | Array<JoinCondition>>
) => {
  let leftJoinExpr: {[key: string]: any} = getRelationExpression(
    (joinOrder[0]: any),
    tablesWithSelections
  );
  for (let i = 2; i < joinOrder.length; i += 2) {
    const rightTable: any = joinOrder[i];
    const joinConditions: any = joinOrder[i - 1];
    const rightJoinExpr = getRelationExpression(
      rightTable,
      tablesWithSelections
    );
    leftJoinExpr = {
      join: {
        left: leftJoinExpr,
        right: rightJoinExpr,
        type:
          joinConditions.length > 0
            ? (joinConditions[0].type ?? 'inner')
            : 'inner',
        condition: formatJoinConditions(joinConditions),
      },
    };
  }
  return leftJoinExpr;
};

/**
 * Gets the relational expression for the given join order
 * @param graph - the relational graph
 * @param bestJoinOrder - the best join order
 * @param globalSelections - the global selections
 */
const getRelationalExpression = (
  graph: Graph,
  bestJoinOrder: Array<string | Array<JoinCondition>>,
  globalSelections: Array<SelectionCondition>
): {[key: string]: any} => {
  const tablesWithSelections: {[key: string]: any} = {};
  for (const tableName in graph) {
    const selections = graph[tableName]?.selections ?? [];
    if (selections.length > 0) {
      tablesWithSelections[tableName] = getSelectionExpression(
        tableName,
        selections
      );
    }
  }

  const joinExpr = parseJoinOrderExpression(
    tablesWithSelections,
    bestJoinOrder
  );
  return getSelectionExpression(joinExpr, globalSelections);
};

/**
 * Performs join order optimization
 * @param graph - the relational graph
 * @param globalSelections - the global selections
 * @return the relational expression
 */
const joinOrderOptimization = (
  graph: Graph,
  globalSelections: Array<SelectionCondition>
): {[key: string]: any} => {
  const queue = new TinyQueue([], function (a, b) {
    return a.getCost() - b.getCost();
  });
  // initialize the queue with all the nodes
  for (const node in graph) {
    queue.push(
      new JoinOrderQueueElement(graph, [node], getTableData(node), 0, [node], {
        relation: node,
      })
    );
  }

  let bestCost = Number.MAX_SAFE_INTEGER;
  let bestJoinOrder: Array<string | Array<JoinCondition>> = [];
  const JOIN_ORDER_SIZE = Object.keys(graph).length;
  while (queue.length > 0) {
    const joinOrderElement = queue.pop();
    // condition to prune this branch
    if (joinOrderElement && joinOrderElement.getCost() >= bestCost) {
      continue;
    }
    // condition to stop this branch
    if (joinOrderElement && joinOrderElement.getSize() === JOIN_ORDER_SIZE) {
      if (joinOrderElement.getCost() < bestCost) {
        bestCost = joinOrderElement.getCost();
        bestJoinOrder = joinOrderElement.joinOrder;
      }
      continue;
    }
    const children = joinOrderElement ? joinOrderElement.getChildren() : [];
    for (const child of children) {
      queue.push(child);
    }
  }
  // If no valid join order was found (empty bestJoinOrder),
  // it means the graph has disconnected components or optimization failed
  if (bestJoinOrder.length === 0) {
    console.warn(
      'Join order optimization failed: no complete join order found'
    );
    throw new Error(
      'Join order optimization failed: disconnected graph or no valid joins'
    );
  }

  return getRelationalExpression(graph, bestJoinOrder, globalSelections);
};

/**
 * Gets the rows and cost for the given join conditions
 * @param rows - the rows
 * @param cost - the cost
 * @param joinConditions - the join conditions
 * @param leftTables - the left tables
 * @param rightTable - the right table
 */
const getRowsAndCost = (
  rows: number,
  cost: number,
  joinExpr: {[key: string]: any},
  joinConditions: Array<JoinCondition>,
  leftTables: Array<string>,
  rightTable: string
) => {
  // trying to see if we can use applyExpr from data.js
  const joinConditionsExpr = formatJoinConditions(joinConditions);
  const combinedJoinExpr = {
    join: {
      left: joinExpr,
      right: {
        relation: rightTable,
      },
      type:
        joinConditions.length > 0
          ? (joinConditions[0].type ?? 'inner')
          : 'inner',
      condition: joinConditionsExpr,
    },
  };
  try {
    const joinResult = applyExpr(combinedJoinExpr, initialState.sourceData);
    const newRows = joinResult.data?.length ?? 0;
    const newCost = cost + rows * getTableData(rightTable);
    return {rows: newRows, cost: newCost, expr: combinedJoinExpr};
  } catch (error) {
    console.warn(
      'Error evaluating join expression during optimization:',
      error.message
    );
    // Return a high cost to discourage this path
    return {
      rows: Number.MAX_SAFE_INTEGER,
      cost: Number.MAX_SAFE_INTEGER,
      expr: combinedJoinExpr,
    };
  }
};

/**
 * Gets the data for the given table
 * @param tableName - the table name
 */
const getTableData = (tableName: string) => {
  return tableName in initialState.sourceData
    ? initialState.sourceData[tableName].data.length
    : 0;
};

class JoinOrderQueueElement {
  graph: Graph;
  joinTables: Array<string>;
  rows: number;
  cost: number;
  joinOrder: Array<string | Array<JoinCondition>>;
  joinExpr: {[key: string]: any};

  constructor(
    graph: Graph,
    joinTables: Array<string>,
    rows: number,
    cost: number,
    joinOrder: Array<string | Array<JoinCondition>>,
    joinExpr: {[key: string]: any}
  ) {
    this.graph = graph;
    this.joinTables = joinTables;
    this.rows = rows;
    this.cost = cost;
    this.joinOrder = joinOrder;
    this.joinExpr = joinExpr;
  }

  getCost = (): number => {
    return this.cost;
  };

  getSize = (): number => {
    return this.joinTables.length;
  };

  /**
   * Gets the children of the current join order
   * Iterates through all the tables in the current join order
   * For each table, iterates through all its neighbors
   * If the neighbor is not in the current join order, evaluate the cost of adding it
   * and add it to the queue
   * Add the join conditions between the tables in the join order so far and the new neighbor
   * @return the children
   */
  // eslint-disable-next-line no-use-before-define
  getChildren(): Array<JoinOrderQueueElement> {
    const children = [];
    // iterate through all the tables in the current join order
    for (const table of this.joinTables) {
      const edges = this.graph[table].edges;
      const neighbors = Object.keys(edges);
      // iterate through all the neighbors of the current table
      for (const neighbor of neighbors) {
        if (this.joinTables.includes(neighbor)) continue;
        let joinConditions: Array<JoinCondition> = [];
        for (const currentTable in this.graph[neighbor].edges) {
          if (this.joinTables.includes(currentTable)) {
            joinConditions = [
              ...joinConditions,
              ...this.graph[neighbor].edges[currentTable],
            ];
          }
        }
        const newJoinOrder = [...this.joinOrder, joinConditions, neighbor];
        // evaluate the cost of adding the neighbor
        const {rows, cost, expr} = getRowsAndCost(
          this.rows,
          this.cost,
          this.joinExpr,
          joinConditions,
          this.joinTables,
          neighbor
        );
        // add it to the list of children
        children.push(
          new JoinOrderQueueElement(
            this.graph,
            [...this.joinTables, neighbor],
            rows,
            cost,
            newJoinOrder,
            expr
          )
        );
      }
    }
    return children;
  }
}

export {joinOrderOptimization};

1	// @flow
2	import type {JoinCondition, SelectionCondition, Graph} from './types';
3
4	import TinyQueue from 'tinyqueue';
5
6	import {initialState, applyExpr} from './data';
7
8	/**
9	* Formats into selection condition format for a given table
10	* @param tableExpr - a relational algebra expression object to render
11	* @param selections - an array where all created paths should be saved
12	* @return a tree structure representing the exppression
13	*/
14	const getSelectionExpression = (	6✔
15	tableExpr: string \| {[key: string]: any},
16	selections: Array<SelectionCondition>
17	) => {
18	let relation =
19	typeof tableExpr === 'string' ? {relation: tableExpr} : tableExpr;	18✔
20	if (selections.length === 0) {	18✔
21	return relation;	7✔
22	}
23	let select: {[key: string]: any} = {};	11✔
24	if (selections.length === 1) {	11✔
25	select = selections[0];	7✔
26	} else {
27	select = {	4✔
28	and: {
29	clauses: selections,
30	},
31	};
32	}
33	return {	11✔
34	selection: {
35	arguments: {
36	select: select,
37	},
38	children: [relation],
39	},
40	};
41	};
42
43	/**
44	* Formats into join condition format for a given table
45	* @param joinConditions - a relational algebra expression object to render
46	* @return a tree structure representing the exppression
47	*/
48	const formatJoinConditions = (joinConditions: Array<JoinCondition>) => {	6✔
49	if (joinConditions.length === 0) {	41!
50	// This should not happen in a well-formed query, but handle gracefully
51	console.warn('Empty join conditions encountered');	×
52	return {cmp: {lhs: '1', op: '$eq', rhs: '1'}}; // Dummy true condition	×
53	}
54	if (joinConditions.length === 1) {	41✔
55	return {cmp: joinConditions[0].condition};	32✔
56	} else {
57	const processedJoinConditions = joinConditions.map((joinCondition) => {	9✔
58	return {cmp: joinCondition.condition};	18✔
59	});
60	return {and: {clauses: processedJoinConditions}};	9✔
61	}
62	};
63
64	/**
65	* Formats into relational expression format for a given table
66	* @param tableName - a relational algebra expression object to render
67	* @param tablesWithSelections - all tables with selections
68	*/
69	const getRelationExpression = (	6✔
70	tableName: string,
71	tablesWithSelections: {[key: string]: any}
72	) => {
73	if (tableName in tablesWithSelections) {	16✔
74	return tablesWithSelections[tableName];	11✔
75	}
76	return {relation: tableName};	5✔
77	};
78
79	/**
80	* Parses the join order expression
81	* @param tablesWithSelections - all tables with selections
82	* @param joinOrder - the join order
83	*/
84	const parseJoinOrderExpression = (	6✔
85	tablesWithSelections: {[key: string]: any},
86	joinOrder: Array<string \| Array<JoinCondition>>
87	) => {
88	let leftJoinExpr: {[key: string]: any} = getRelationExpression(	7✔
89	(joinOrder[0]: any),
90	tablesWithSelections
91	);
92	for (let i = 2; i < joinOrder.length; i += 2) {	7✔
93	const rightTable: any = joinOrder[i];	9✔
94	const joinConditions: any = joinOrder[i - 1];	9✔
95	const rightJoinExpr = getRelationExpression(	9✔
96	rightTable,
97	tablesWithSelections
98	);
99	leftJoinExpr = {	9✔
100	join: {
101	left: leftJoinExpr,
102	right: rightJoinExpr,
103	type:
104	joinConditions.length > 0	9!
105	? (joinConditions[0].type ?? 'inner')	9!
106	: 'inner',
107	condition: formatJoinConditions(joinConditions),
108	},
109	};
110	}
111	return leftJoinExpr;	7✔
112	};
113
114	/**
115	* Gets the relational expression for the given join order
116	* @param graph - the relational graph
117	* @param bestJoinOrder - the best join order
118	* @param globalSelections - the global selections
119	*/
120	const getRelationalExpression = (	6✔
121	graph: Graph,
122	bestJoinOrder: Array<string \| Array<JoinCondition>>,
123	globalSelections: Array<SelectionCondition>
124	): {[key: string]: any} => {
125	const tablesWithSelections: {[key: string]: any} = {};	7✔
126	for (const tableName in graph) {	7✔
127	const selections = graph[tableName]?.selections ?? [];	16!
128	if (selections.length > 0) {	16✔
129	tablesWithSelections[tableName] = getSelectionExpression(	11✔
130	tableName,
131	selections
132	);
133	}
134	}
135
136	const joinExpr = parseJoinOrderExpression(	7✔
137	tablesWithSelections,
138	bestJoinOrder
139	);
140	return getSelectionExpression(joinExpr, globalSelections);	7✔
141	};
142
143	/**
144	* Performs join order optimization
145	* @param graph - the relational graph
146	* @param globalSelections - the global selections
147	* @return the relational expression
148	*/
149	const joinOrderOptimization = (	6✔
150	graph: Graph,
151	globalSelections: Array<SelectionCondition>
152	): {[key: string]: any} => {
153	const queue = new TinyQueue([], function (a, b) {	9✔
154	return a.getCost() - b.getCost();	108✔
155	});
156	// initialize the queue with all the nodes
157	for (const node in graph) {	9✔
158	queue.push(	18✔
159	new JoinOrderQueueElement(graph, [node], getTableData(node), 0, [node], {
160	relation: node,
161	})
162	);
163	}
164
165	let bestCost = Number.MAX_SAFE_INTEGER;	9✔
166	let bestJoinOrder: Array<string \| Array<JoinCondition>> = [];	9✔
167	const JOIN_ORDER_SIZE = Object.keys(graph).length;	9✔
168	while (queue.length > 0) {	9✔
169	const joinOrderElement = queue.pop();	50✔
170	// condition to prune this branch
171	if (joinOrderElement && joinOrderElement.getCost() >= bestCost) {	50✔
172	continue;	17✔
173	}
174	// condition to stop this branch
175	if (joinOrderElement && joinOrderElement.getSize() === JOIN_ORDER_SIZE) {	33✔
176	if (joinOrderElement.getCost() < bestCost) {	7!
177	bestCost = joinOrderElement.getCost();	7✔
178	bestJoinOrder = joinOrderElement.joinOrder;	7✔
179	}
180	continue;	7✔
181	}
182	const children = joinOrderElement ? joinOrderElement.getChildren() : [];	26!
183	for (const child of children) {	26✔
184	queue.push(child);	32✔
185	}
186	}
187	// If no valid join order was found (empty bestJoinOrder),
188	// it means the graph has disconnected components or optimization failed
189	if (bestJoinOrder.length === 0) {	9✔
190	console.warn(	2✔
191	'Join order optimization failed: no complete join order found'
192	);
193	throw new Error(	2✔
194	'Join order optimization failed: disconnected graph or no valid joins'
195	);
196	}
197
198	return getRelationalExpression(graph, bestJoinOrder, globalSelections);	7✔
199	};
200
201	/**
202	* Gets the rows and cost for the given join conditions
203	* @param rows - the rows
204	* @param cost - the cost
205	* @param joinConditions - the join conditions
206	* @param leftTables - the left tables
207	* @param rightTable - the right table
208	*/
209	const getRowsAndCost = (	6✔
210	rows: number,
211	cost: number,
212	joinExpr: {[key: string]: any},
213	joinConditions: Array<JoinCondition>,
214	leftTables: Array<string>,
215	rightTable: string
216	) => {
217	// trying to see if we can use applyExpr from data.js
218	const joinConditionsExpr = formatJoinConditions(joinConditions);	32✔
219	const combinedJoinExpr = {	32✔
220	join: {
221	left: joinExpr,
222	right: {
223	relation: rightTable,
224	},
225	type:
226	joinConditions.length > 0	32!
227	? (joinConditions[0].type ?? 'inner')	32!
228	: 'inner',
229	condition: joinConditionsExpr,
230	},
231	};
232	try {	32✔
233	const joinResult = applyExpr(combinedJoinExpr, initialState.sourceData);	32✔
234	const newRows = joinResult.data?.length ?? 0;	32!
235	const newCost = cost + rows * getTableData(rightTable);	32✔
236	return {rows: newRows, cost: newCost, expr: combinedJoinExpr};	32✔
237	} catch (error) {
238	console.warn(	×
239	'Error evaluating join expression during optimization:',
240	error.message
241	);
242	// Return a high cost to discourage this path
243	return {	×
244	rows: Number.MAX_SAFE_INTEGER,
245	cost: Number.MAX_SAFE_INTEGER,
246	expr: combinedJoinExpr,
247	};
248	}
249	};
250
251	/**
252	* Gets the data for the given table
253	* @param tableName - the table name
254	*/
255	const getTableData = (tableName: string) => {	6✔
256	return tableName in initialState.sourceData	50!
257	? initialState.sourceData[tableName].data.length
258	: 0;
259	};
260
261	class JoinOrderQueueElement {
262	graph: Graph;
263	joinTables: Array<string>;
264	rows: number;
265	cost: number;
266	joinOrder: Array<string \| Array<JoinCondition>>;
267	joinExpr: {[key: string]: any};
268
269	constructor(
270	graph: Graph,
271	joinTables: Array<string>,
272	rows: number,
273	cost: number,
274	joinOrder: Array<string \| Array<JoinCondition>>,
275	joinExpr: {[key: string]: any}
276	) {
277	this.graph = graph;	50✔
278	this.joinTables = joinTables;	50✔
279	this.rows = rows;	50✔
280	this.cost = cost;	50✔
281	this.joinOrder = joinOrder;	50✔
282	this.joinExpr = joinExpr;	50✔
283	}
284
285	getCost = (): number => {	50✔
286	return this.cost;	280✔
287	};
288
289	getSize = (): number => {	50✔
290	return this.joinTables.length;	33✔
291	};
292
293	/**
294	* Gets the children of the current join order
295	* Iterates through all the tables in the current join order
296	* For each table, iterates through all its neighbors
297	* If the neighbor is not in the current join order, evaluate the cost of adding it
298	* and add it to the queue
299	* Add the join conditions between the tables in the join order so far and the new neighbor
300	* @return the children
301	*/
302	// eslint-disable-next-line no-use-before-define
303	getChildren(): Array<JoinOrderQueueElement> {
304	const children = [];	26✔
305	// iterate through all the tables in the current join order
306	for (const table of this.joinTables) {	26✔
307	const edges = this.graph[table].edges;	34✔
308	const neighbors = Object.keys(edges);	34✔
309	// iterate through all the neighbors of the current table
310	for (const neighbor of neighbors) {	34✔
311	if (this.joinTables.includes(neighbor)) continue;	48✔
312	let joinConditions: Array<JoinCondition> = [];	32✔
313	for (const currentTable in this.graph[neighbor].edges) {	32✔
314	if (this.joinTables.includes(currentTable)) {	48✔
315	joinConditions = [	40✔
316	...joinConditions,
317	...this.graph[neighbor].edges[currentTable],
318	];
319	}
320	}
321	const newJoinOrder = [...this.joinOrder, joinConditions, neighbor];	32✔
322	// evaluate the cost of adding the neighbor
323	const {rows, cost, expr} = getRowsAndCost(	32✔
324	this.rows,
325	this.cost,
326	this.joinExpr,
327	joinConditions,
328	this.joinTables,
329	neighbor
330	);
331	// add it to the list of children
332	children.push(	32✔
333	new JoinOrderQueueElement(
334	this.graph,
335	[...this.joinTables, neighbor],
336	rows,
337	cost,
338	newJoinOrder,
339	expr
340	)
341	);
342	}
343	}
344	return children;	26✔
345	}
346	}
347
348	export {joinOrderOptimization};

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