I'm posting this as I am trying to understand what has happened. TLDR: The problem seems to be fixed now. By bumping the statistics_target we see that most_common_vals is having its contents filled more often, causing way better estimates: attname | status inherited | f null_frac | 0 avg_width | 4 n_distinct | 3 most_common_vals | {PRINTED,PREPARED,ERROR} most_common_freqs | {0.996863,0.00307333,6.33333e-05} histogram_bounds | (null) correlation | 0.98207 most_common_elems | (null) most_common_elem_freqs | (null) elem_count_histogram | (null) Basically 100% of the records are accounted for in these statistics, the planner now consistently estimates the number of rows to be very small for other values. Before bumping the target we didn't have information for 0.34% of the rows, which in this case means roughly 11K rows. What is the reasoning behind having at least 2 hits before including it in the most_common_* columns? -- Sent via pgsql-performance mailing list (pgsql-performance@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance