I wrote:
>> This might be a bug in the LIKE estimator (if so, it's in 8.2.3 as
>> well). I don't have time to look closer right now, but can you show us
>> the pg_stats row for orders_smaller.order_number?
> Oh, never mind that ... on inspection, the NOT LIKE selectivity
> estimator is obviously broken: patternsel() doesn't realize it needs
> to negate the results of the operator when applying same to histogram
> entries.
I've applied a patch that should make this better:
http://archives.postgresql.org/pgsql-committers/2007-11/msg00101.php
regards, tom lane