On Mon, 16 Jan 2012 22:21:03 +0200, Andrei Popescu <andreimpopescu@gmail.com> wrot> > $ notmuch count 'Debian' > 65888 > $ notmuch count '*ebian' > 3 > $ notmuch count '?ebian' > 3 > $ notmuch count 'ebian' > 3 > $ notmuch count '0ebian' You have to delve into the mysteries of xapian query parsing unfortunately. The short answer is that "*" only works at the end of a word.