Brain dump: I've heard of QuickCheck before, but I only found time to look at it in some depth earlier today. It's a very simple but powerful tool: rather than writing unit test cases by hand, the tester just specifies a set of constraints that the function being tested must satisfy. QuickCheck then randomly generates test cases and checks that the constraints hold. A trivial example of a constraint given by in the 2000 QuickCheck paper is for an insertion function into ordered lists:
prop_Insert :: Int -> [Int] -> Property
prop_Insert x xs =
ordered xs ==> ordered (insert x xs)
That is: given any integer x and any ordered list of integers xs, insert x xs should produce an ordered list. QuickCheck takes care of generating the necessary random integers automatically. The programmer can view the distribution of random values generated by QuickCheck, or provide their own data generator.
I think it would be interesting to apply this to PostgreSQL. For example, I find it frustrating to try to manually test the impact of changes to the query optimizer: it's difficult to determine whether a local change to the optimizer is correct for all possible query trees. Worse yet, a planner change might optimize some queries and pessimize others — unless the developer realizes this while implementing the change, we often don't hear about these sorts of performance regressions until the beta period or even later.
It might be interesting to try to define a domain-specific language that would allow you to construct random SQL queries that satisfy certain high-level constraints, and then verify that the backend executes those queries correctly. For example, a statement in the DSL might be "for all SQL queries q such that q contains 0 < n < 10 joins, check that q is executed without error." Checking that queries can be executed without error is fairly trivial; perhaps we could check more advanced properties, like "executes within a certain amount of time" or "produces a result set that satisfies the constraint: [...]".
That said, there are plenty of low-hanging fruit when it comes to improving the state of testing for Postgres. For example, the ability to generate arbitrary n-relation joins of certain kinds (e.g. star schema) would be useful. Another simple improvement would be to convert the TPC-D query workload into something that could be used to isolate changes in the optimizer's performance for that set of (important) queries.