Mysql – Awful execution plans after migrating from MySQL 5.5.11 to MariaDB 5.5.41

We just migrated our web site database from a server running MySQL 5.5.11 to one running MariaDB 5.5.41. Everything is working mostly fine, except there's at least one query from our storefront that's generating pretty terrible execution plans on the new server, causing scans of a table that's around 6 GB.

It's a query with two InnoDB tables and a relatively simple join between them, on two columns that are indexed (PK in catalog_category_flat_store_1, but not a covering index on core_url_rewrite):

SELECT
    `main_table`.`entity_id`,
    main_table.`name`,
    main_table.`path`,
    `main_table`.`is_active`,
    `main_table`.`is_anchor`,
    `url_rewrite`.`request_path`
FROM `catalog_category_flat_store_1` AS `main_table`
    LEFT JOIN `core_url_rewrite` AS `url_rewrite`
        ON url_rewrite.category_id=main_table.entity_id
        AND url_rewrite.is_system=1
        AND url_rewrite.product_id IS NULL
        AND url_rewrite.store_id='1'
        AND url_rewrite.id_path LIKE 'category/%'
WHERE (main_table.is_active = '1') AND (main_table.include_in_menu = '1') AND (main_table.path like '1/2/5/204/225/%') AND (`level` <= 5) ORDER BY `main_table`.`position` ASC

catalog_category_flat_store_1 has 627 rows, and core_url_rewrite has 8,687,266 rows (kill me).

The EXPLAIN shows me that catalog_category_flat_store_1 is "Using index condition; Using where; Using filesort", and core_url_rewrite (the huge table) is "Range checked for each record (index map: 0xF4)", despite allegedly using the index on category_id as its key.

On the old server, catalog_category_flat_store_1 is "Using where; Using filesort", and core_url_rewrite doesn't have anything listed for "Extra", and appears to be using the correct index.

I noticed MariaDB has a lot of additional options for optimizer_switch, and I'm wondering if any of these options are causing the different optimizer behavior, so I figure it's worth testing. The problem is that I don't know what the values should be to make MariaDB act like MySQL.

Here's the old server, where the query runs just fine:

index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on

And here's the new server, where the exact same query can end up running for ages:

index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,index_merge_sort_intersection=off,engine_condition_pushdown=off,index_condition_pushdown=on,derived_merge=on,derived_with_keys=on,firstmatch=on,loosescan=on,materialization=on,in_to_exists=on,semijoin=on,partial_match_rowid_merge=on,partial_match_table_scan=on,subquery_cache=on,mrr=off,mrr_cost_based=off,mrr_sort_keys=off,outer_join_with_cache=on,semijoin_with_cache=on,join_cache_incremental=on,join_cache_hashed=on,join_cache_bka=on,optimize_join_buffer_size=off,table_elimination=on,extended_keys=off

P.S. Greetings from Magento core_url_rewrite hell.