BRIN (Block Range Index)

Updating 5% of rows drove one BRIN query from 1,536 heap pages to 51,268

PostgreSQL still reported 0.921 correlation and a 48 kB index at that point, so the damage only showed up in the execution plan, where recheck threw away 3.8 million rows to return 111,112.