Simple indexed select query takes 350 seconds (?!) even though Filtered 100.00 "Using index condition"
The optimal index for this query would be a composite index with 4 columns, in any order:

INDEX(contact_id, job_class_name, execute_at, deleted_at)


And, depending on the order you pick, you can get rid of one of the existing KEYs.

Watch out for backslashes.  'App\Jobs\MyJob' may be treated as App[LF]obs[CR]yJob or AppJobsMyJob.

352 seconds is really unreasonable.  Perhaps something else was going on, and blocking access to the rows and/or the table? (The 352s was bogus.)

"Using index condition" is not the same as "Using index".  The latter indicates a "covering index", which is not practical for this query and table.