The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.
2. Prefer Inner Join Over Left Join (modified query below): We identified that one or more left joined entities (e.g. `right_table`) are used in the 'where' clause, in a way that allows to replace it with an optimized inner join. Inner joins can be fully optimized by the database, while Left joins apply limitations on the database's optimizer.
3. Prefer Sorting/Grouping By The First Table In Join Order (modified query below): The database can use indexes more efficiently when sorting and grouping using columns from the first table in the join order. The first table is determined based on the prediction of the the optimal first table, and is not necessarily the first table shown in the FROM clause.

Optimal indexes for this query:

ALTER TABLE `left_table` ADD INDEX `left_table_idx_right_id_add_time` (`right_table_id`,`add_time`);
ALTER TABLE `right_table` ADD INDEX `right_table_idx_category_id` (`category`,`id`);

The optimized query:

SELECT
        `left_table`.`right_table_id`,
        MAX(left_table.add_time) AS max_add_time 
    FROM
        `left_table` 
    INNER JOIN
        `right_table` 
            ON `left_table`.`right_table_id` = `right_table`.`id` 
    WHERE
        left_table.add_time <= NOW() 
        AND (
            (
                right_table.some_id = 1 
                AND right_table.category != -2
            ) 
            OR (
                right_table.another_id = 1 
                AND right_table.category != -1
            )
        ) 
        AND NOT (right_table.category = -3) 
        AND NOT (right_table.category = -4) 
    GROUP BY
        `right_table`.`id` 
    ORDER BY
        `max_add_time` DESC,
        `left_table`.`id` DESC LIMIT 12