Adding where condition with index make query slower(use filesort and temporary) I'm trying to implement soft-delete so I added deleted_at (datetime) column to users table.
Also there is a query i need to run:

    SELECT 
    COUNT(*) AS count_all,
    `users`.`category_id` AS users_category_id
FROM
    `users`
GROUP BY `users`.`category_id`;



type, possible_keys, key, key_len, ref, rows, filtered, Extra
'index', 'index_users_on_category_id', 'index_users_on_category_id', '5', NULL, '840926', '100.00', 'Using index'


which was running just fine until i added  WHERE clause

    SELECT 
    COUNT(*) AS count_all,
    `users`.`category_id` AS users_category_id
FROM
    `users`
WHERE
    `users`.`deleted_at` IS NULL
GROUP BY `users`.`category_id`;

type, possible_keys, key, key_len, ref, rows, filtered, Extra
'ref', 'index_users_on_category_id,index_users_on_deleted_at', 'index_users_on_deleted_at', '6', 'const', '420463', '100.00', 'Using index condition; Using temporary; Using filesort'


Of course it becomes slower, i can't find information 


why type changed
why key_len changed from 5 to 6 
why rows in second query shows half of total number (800k)


And how can i make it faster without using USE INDEX (index_users_on_category_id)
this index actually helped: deleted_at, category_id, however, I tried to do this without adding new index
Since there are much more records where deleted_at is null, i tried next queries:

SELECT 
    COUNT(*) AS count_all,
    `users`.`category_id` AS users_category_id
FROM
    `users`
WHERE
     `users`.`id` NOT IN (SELECT `users`.`id` FROM `users` WHERE `users`.`deleted_at` IS NOT NULL)
GROUP BY `users`.`category_id`;


And query optimizer used much better schema. I will try it soon on big set and hoe it will work.