I've worked with several over these over the years. I started with the ones that were integrated with DBI, like DBIx::Abstract. I eventually found it cumbersome that this approach left very little space for me to further tweak the SQL.
I was then drawn to SQL::Abstract for the simplicity of it-- just generating SQL and staying away from the database handle.
I had more flexibility, but eventually found SQL::Abstract's where clause generation too abstract and inflexible-- some kinds of AND/OR nesting just wasn't possible.
This brings me to my current recommendation, which is SQL::Interpolate. It allows you to express parts of SQL in Perlish ways, with a result that is natural looking and still open generating the rest of the SQL however you want.
No SQL statement has been too complex to use with SQL::Interpolate. Just to bring things full circle, I use it through DBIx::Interpolate, which simply passes the result on to DBI without getting the way further.
Still, it may not be a complete solution for what you are describing. Today I ran into a problem that perhaps like what you described. I needed to take a simple keyword field, split up the words, and generate some nested SQL to regular expression matches against several fields.
For that I wrote SQL::KeywordSearch, which I hope to put on CPAN soon. It can either generate $sql and @bind directly, or it can alternately generate a syntax that would plug directly into a larger SQL::Interpolate query.
If there's interest, I could prioritize wrapping up SQL::KeywordSearch for publishing. It's definitely a niche tool, but may at least be helpful as an example.
Note: I think SQL::Interpolate 0.40 may be released soon, with some improved syntax and docs.