According to the PQS paper, they pick an existing row in the database and generate random predicates until they find one that’s true for that row. They then use that as a WHERE clause and verify the original row is contained in the result set. A similar procedure is used to find relevant JOIN clauses.