Awful execution plans after migrating from MySQL 5.5.11 to MariaDB 5.5.41
Well, this is a bit of voodoo/shotgun debugging, but I've got it functioning okay for the time being. I set the extended_keys option to on, and also created a covering index on the 8-million-row table in question. Now I'm getting an execution plan that's even better than the acceptable plan the old server was coming up with (which was only using Magento's default indexes).

Still, it all seems a bit hand-wavey, so I'll leave this open for now in case anybody has a better recommendation or explanation.