Might the issue be with pg_index or pg_attribute rather than pg_class? Is the query still slow? Do you have the output of explain analyze for use on https://explain.depesz.com/ or the output of EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS, FORMAT JSON) for use on http://tatiyants.com/pev/#/plans/new website?