Database Query Optimizer

Imagine you're building a powerful database system. A critical component of any efficient database is its query optimizer, which transforms user-written queries into an execution plan that runs as quickly as possible. This challenge focuses on creating a simplified query optimizer in Python that can reorder operations in a sequence of database queries to improve performance.

Problem Description

Your task is to implement a function optimize_queries(queries) that takes a list of database query operations and returns a reordered list of these operations that represents an optimized execution plan. The optimization strategy will focus on a common technique: pushing down filters. This means moving FILTER operations as early as possible in the execution sequence, ideally before computationally expensive operations like JOIN or SORT.

You will be dealing with a simplified representation of query operations. Each operation will be a dictionary with a type key indicating the operation (e.g., 'SELECT', 'FILTER', 'JOIN', 'SORT') and potentially other keys representing operands or conditions.

Key Requirements:

1. Identify and Reorder Filters: The primary goal is to identify FILTER operations and move them as early as possible in the query plan.
2. Preserve Logical Equivalence: The reordering must not change the final result of the query. A FILTER operation can be moved before any operation that does not depend on its outcome, as long as it doesn't violate dependencies.
3. Handle Dependencies: Be mindful of the order of operations. For instance, a FILTER operation usually applies to the output of a preceding operation. A JOIN operation might require specific operands to be available. For this simplified challenge, assume a FILTER can be pushed before any operation except if it's the very first operation and there's no preceding operation to filter. Also, assume that FILTER operations are independent of each other and can be reordered among themselves.
4. Output Format: The function should return a new list of query operations in the optimized order.

Expected Behavior:

The optimizer should process the input list of queries. It should iterate through the queries, looking for FILTER operations. When a FILTER is found, it should attempt to move it earlier in the list, but only if it's logically permissible. Operations that are not FILTER operations should maintain their relative order unless a FILTER is inserted before them.

Edge Cases:

• Empty Input: An empty list of queries should return an empty list.
• No Filters: If the input contains no FILTER operations, the original list should be returned.
• Filters at the Beginning: Filters already at the beginning of the query list should remain there.
• Multiple Filters: The optimizer should handle multiple FILTER operations, pushing them all as early as possible.

Examples

Example 1:

Input: [
    {'type': 'SELECT', 'from': 'users'},
    {'type': 'FILTER', 'condition': 'age > 18'},
    {'type': 'JOIN', 'on': 'users.id = orders.user_id'},
    {'type': 'SORT', 'by': 'order_date'}
]
Output: [
    {'type': 'SELECT', 'from': 'users'},
    {'type': 'FILTER', 'condition': 'age > 18'},
    {'type': 'JOIN', 'on': 'users.id = orders.user_id'},
    {'type': 'SORT', 'by': 'order_date'}
]
Explanation: In this case, the FILTER is already positioned optimally after the SELECT and before the JOIN. No reordering is necessary.

Example 2:

Input: [
    {'type': 'SELECT', 'from': 'products'},
    {'type': 'JOIN', 'on': 'products.id = reviews.product_id'},
    {'type': 'FILTER', 'condition': 'rating > 4'}
]
Output: [
    {'type': 'SELECT', 'from': 'products'},
    {'type': 'FILTER', 'condition': 'rating > 4'},
    {'type': 'JOIN', 'on': 'products.id = reviews.product_id'}
]
Explanation: The FILTER operation is moved before the JOIN operation. This is beneficial because it reduces the number of rows that need to be joined, potentially saving computation.

Example 3:

Input: [
    {'type': 'SELECT', 'from': 'customers'},
    {'type': 'FILTER', 'condition': 'country = "USA"'},
    {'type': 'JOIN', 'on': 'customers.id = orders.customer_id'},
    {'type': 'FILTER', 'condition': 'order_total > 100'}
]
Output: [
    {'type': 'SELECT', 'from': 'customers'},
    {'type': 'FILTER', 'condition': 'country = "USA"'},
    {'type': 'FILTER', 'condition': 'order_total > 100'},
    {'type': 'JOIN', 'on': 'customers.id = orders.customer_id'}
]
Explanation: Both FILTER operations are pushed as early as possible, before the JOIN. The relative order of the two FILTERs is maintained as they are independent.

Example 4: (Edge Case - No Filters)

Input: [
    {'type': 'SELECT', 'from': 'employees'},
    {'type': 'SORT', 'by': 'salary'}
]
Output: [
    {'type': 'SELECT', 'from': 'employees'},
    {'type': 'SORT', 'by': 'salary'}
]
Explanation: No FILTER operations are present, so the original order is returned.

Constraints

• The input queries will be a list of dictionaries.
• Each dictionary will have at least a 'type' key with a string value (e.g., 'SELECT', 'FILTER', 'JOIN', 'SORT').
• Other keys in the dictionaries will vary based on the operation type and are not relevant to the optimization logic itself for this problem.
• The number of queries in the list will be between 0 and 1000, inclusive.
• The optimization process should be efficient. Aim for a time complexity better than O(N^2) if possible, where N is the number of queries.

Notes

• Consider using a "two-pointer" approach or maintaining a separate list for optimized queries.
• The problem simplifies dependency handling; focus on the core logic of moving filters.
• Think about how to iterate through the queries and decide where to place each FILTER.
• The order of non-FILTER operations should be preserved relative to each other.