We’ve been working on the advanced search for a while now and it has undergone one round of testing in an un-designed format. Based on feedback we’ve arrived at something like this:

The bottom half is where you build individual lines of queries and these appear at the top of the page. You then combine them using the AND, OR and NOT commands.

What do you think?