Simple Query Optimizer in JavaScript

Building a query optimizer is a fundamental task in database systems. This challenge asks you to implement a basic query optimizer that reorders operations in a simple query plan to potentially improve performance. The goal is to understand the core concepts of query optimization without the complexity of a full database system.

Problem Description

You are tasked with creating a JavaScript function optimizeQuery that takes a query plan represented as an array of operations and returns an optimized query plan. The operations are represented as strings, and the optimizer should reorder them based on a simple cost model: multiplication (*) is more expensive than addition (+). The optimizer should prioritize performing additions before multiplications.

The query plan array will contain a sequence of operations. Each operation is a string representing either an addition (+) or a multiplication (*). The function should rearrange the operations in the array such that all addition operations appear before any multiplication operations. The order of additions relative to each other, and multiplications relative to each other, does not matter.

Key Requirements:

• The function must take an array of strings as input, where each string is either "+" or "*".
• The function must return a new array of strings with the same elements, but reordered such that all "+" operations precede all "*" operations.
• The original array should not be modified.
• The function should handle empty input arrays gracefully.

Expected Behavior:

The function should return an array where all addition operations are placed at the beginning, followed by all multiplication operations.

Edge Cases to Consider:

• Empty input array.
• Array containing only addition operations.
• Array containing only multiplication operations.
• Array with a mix of addition and multiplication operations.
• Array with duplicate operations.

Examples

Example 1:

Input: ["+", "*", "+", "*"]
Output: ["+", "+", "*", "*"]
Explanation: The additions are moved to the beginning, followed by the multiplications. The relative order within additions and multiplications is preserved.

Example 2:

Input: ["*", "*", "*"]
Output: ["*", "*", "*"]
Explanation: Since there are no additions, the array remains unchanged.

Example 3:

Input: ["+", "+", "+"]
Output: ["+", "+", "+"]
Explanation: Since there are no multiplications, the array remains unchanged.

Example 4:

Input: []
Output: []
Explanation: Empty input results in an empty output.

Example 5:

Input: ["+", "*", "+", "*", "+"]
Output: ["+", "+", "+", "*", "*"]
Explanation: All additions are grouped at the beginning, followed by all multiplications.

Constraints

• The input array will contain only strings, either "+" or "*".
• The length of the input array can be between 0 and 1000 (inclusive).
• The function should have a time complexity of O(n), where n is the length of the input array. This is because we need to iterate through the array at least once.
• The function should have a space complexity of O(n) in the worst case, as a new array of the same size is created.

Notes

• Consider using separate arrays or counters to track the number of additions and multiplications.
• You can create a new array to store the optimized query plan.
• The order of operations within the addition group and within the multiplication group does not need to be preserved. Focus on separating the two types of operations.
• This is a simplified query optimizer. Real-world query optimizers are significantly more complex and consider various factors like data statistics, indexes, and join algorithms. This challenge focuses on a single, basic optimization rule.