If reindexing didn't help, try to execute:
ANALYZE VERBOSE;
It helped me during postgresql 12 --> 16 upgrade