With 60k messages and 12k tagged as sent:

$ time notmuch tag +sent -- from:flo@chaoflow.net

real	0m8.561s
user	0m8.069s
sys	0m0.212s

$ time notmuch tag +sent -- from:flo@chaoflow.net and not tag:sent

real	0m0.043s
user	0m0.036s
sys	0m0.006s


This could be made implicit:

notmuch tag +A +B -- <filter>
-->
notmuch tag +A +B -- <filter> and not \(tag:A and tag:B\)

Apply command, if one of the tags is not set.


notmuch tag -C -D -- <filter>
-->
notmuch tag -C -D -- <filter> and \(tag:C or tag:D\)

Apply command, if one of the tags is set.


notmuch tag +A +B -C -D -- <filter>
-->
notmuch tag +A +B -C -D -- <filter> and \(not tag:A or not tag:B\ or tag:C or tag:D\)


In order to enforce tagging and disable the filter there could be a
flag.

I lack the knowledge/time to implement it, but I think it's at least
worth documenting it.

-- 
Florian Friesdorf <flo@chaoflow.net>
  GPG FPR: 7A13 5EEE 1421 9FC2 108D  BAAF 38F8 99A3 0C45 F083
Jabber/XMPP: flo@chaoflow.net
IRC: chaoflow on freenode,ircnet,blafasel,OFTC