What is default_statistics_target set to? Or is there custom statistics value set for this table/column? Perhaps the planner is making sub-optimal choices because it only has a vague idea about the data and the histogram is not very informative. Planning time will increase when statistics target is increased, but perhaps 250 instead of default 100 would give *enough* more information to make better choices. Or perhaps your target is already max 10000 and then I have no idea why btree would be chosen. Except, if correlation is too low for the optimizer to consider BRIN to be best perhaps. What does pg_stats say about the column in question?