--- a/src/lib-storage/mail-search-args-simplify.c	Thu Dec 01 02:26:08 2016 +0200
+++ b/src/lib-storage/mail-search-args-simplify.c	Thu Dec 01 02:29:44 2016 +0200
@@ -1,6 +1,7 @@
 /* Copyright (c) 2002-2016 Dovecot authors, see the included COPYING file */
 
 #include "lib.h"
+#include "array.h"
 #include "hash.h"
 #include "mail-search.h"
 
@@ -105,15 +106,35 @@
 	}
 }
 
+static void mail_search_args_simplify_set(struct mail_search_arg *args)
+{
+	const struct seq_range *seqset;
+	unsigned int count;
+
+	if (args->match_not) {
+		/* invert the set to drop the NOT */
+		args->match_not = FALSE;
+		seq_range_array_invert(&args->value.seqset, 1, (uint32_t)-1);
+	}
+	seqset = array_get(&args->value.seqset, &count);
+	if (count == 1 && seqset->seq1 == 1 && seqset->seq2 == (uint32_t)-1) {
+		/* 1:* is the same as ALL. */
+		args->type = SEARCH_ALL;
+	} else if (count == 0) {
+		/* empty set is the same as NOT ALL. this is mainly coming
+		   from mail_search_args_merge_set() intersection. */
+		args->type = SEARCH_ALL;
+		args->match_not = TRUE;
+	}
+}
+
 static bool mail_search_args_merge_set(struct mail_search_simplify_ctx *ctx,
 				       struct mail_search_arg *args)
 {
 	struct mail_search_simplify_prev_arg mask;
 	struct mail_search_arg **prev_argp;
 
-	if (!((!args->match_not && ctx->parent_and) ||
-	      (args->match_not && !ctx->parent_and)))
-		return FALSE;
+	i_assert(!args->match_not);
 
 	mail_search_arg_get_base_mask(args, &mask);
 	prev_argp = mail_search_args_simplify_get_prev_argp(ctx, &mask);
@@ -121,6 +142,10 @@
 	if (*prev_argp == NULL) {
 		*prev_argp = args;
 		return FALSE;
+	} else if (ctx->parent_and) {
+		seq_range_array_intersect(&(*prev_argp)->value.seqset,
+					  &args->value.seqset);
+		return TRUE;
 	} else {
 		seq_range_array_merge(&(*prev_argp)->value.seqset,
 				      &args->value.seqset);
@@ -526,6 +551,9 @@
 							  args->type != SEARCH_OR))
 				ctx.removals = TRUE;
 		}
+		if (args->type == SEARCH_SEQSET ||
+		    args->type == SEARCH_UIDSET)
+			mail_search_args_simplify_set(args);
 
 		/* try to merge arguments */
 		merged = FALSE;

--- a/src/lib-storage/test-mail-search-args-simplify.c	Thu Dec 01 02:26:08 2016 +0200
+++ b/src/lib-storage/test-mail-search-args-simplify.c	Thu Dec 01 02:29:44 2016 +0200
@@ -46,20 +46,28 @@
 	{ "ANSWERED NOT FLAGGED SEEN NOT DRAFT", "(ANSWERED SEEN) NOT (FLAGGED) NOT (DRAFT)" },
 	{ "OR NOT ANSWERED NOT SEEN", "NOT (ANSWERED SEEN)" },
 
-	{ "1:5 10:20", "1:5,10:20" },
-	{ "1:5 NOT 10:20", "1:5 NOT 10:20" },
-	{ "1:5 NOT 10:20 NOT 30:40", "1:5 NOT 10:20 NOT 30:40" },
-	{ "OR 1:5 NOT 10:20", "(OR 1:5 NOT 10:20)" },
-	{ "OR 1:5 OR NOT 10:20 NOT 30:40", "(OR 1:5 NOT 10:20,30:40)" },
+	{ "1:* 1:*", "ALL" },
+	{ "OR 1:5 6:*", "ALL" },
+
+	{ "2:* 2:*", "2:4294967295" },
+	{ "OR 2:* 2:*", "2:4294967295" },
 
-	{ "UID 1:5 UID 10:20", "UID 1:5,10:20" },
-	{ "UID 1:5 NOT UID 10:20", "UID 1:5 NOT UID 10:20" },
-	{ "UID 1:5 NOT UID 10:20 NOT UID 30:40", "UID 1:5 NOT UID 10:20 NOT UID 30:40" },
-	{ "OR UID 1:5 NOT UID 10:20", "(OR UID 1:5 NOT UID 10:20)" },
-	{ "OR UID 1:5 OR NOT UID 10:20 NOT UID 30:40", "(OR UID 1:5 NOT UID 10:20,30:40)" },
+	{ "1:5 6:7", "NOT ALL" },
+	{ "1:5 3:7", "3:5" },
+	{ "1:5 3:7 4:9", "4:5" },
+	{ "1:5 OR 3:4 4:6", "3:5" },
+	{ "OR 1 2", "1:2" },
+	{ "NOT 1,3:5", "2,6:4294967295" },
+	{ "NOT 1:100 NOT 50:200", "201:4294967295" },
+	{ "OR NOT 1:100 NOT 50:200", "1:49,101:4294967295" },
+
+	{ "UID 1:5 UID 6:7", "NOT ALL" },
+	{ "UID 1:5 UID 3:7", "UID 3:5" },
+	{ "OR UID 1 UID 2", "UID 1:2" },
+	{ "NOT UID 1,3:5", "UID 2,6:4294967295" },
 
 	{ "1:5 UID 10:20", "1:5 UID 10:20" },
-	{ "1:5 NOT UID 10:20", "1:5 NOT UID 10:20" },
+	{ "1:5 NOT UID 10:20", "1:5 UID 1:9,21:4294967295" },
 
 	{ "BEFORE 03-Aug-2014 BEFORE 01-Aug-2014 BEFORE 02-Aug-2014", "BEFORE \"01-Aug-2014\"" },
 	{ "OR BEFORE 01-Aug-2014 BEFORE 02-Aug-2014", "BEFORE \"02-Aug-2014\"" },