Add a cache for IMAP message in the database

Co-authored-by: Roeland Jago Douma <roeland@famdouma.nl>
Signed-off-by: Christoph Wurst <christoph@winzerhof-wurst.at>
Signed-off-by: Roeland Jago Douma <roeland@famdouma.nl>

41 files changed, 2210 insertions, 501 deletions

diff --git a/lib/Address.php b/lib/Address.php
index 4eff928b3..c099893fd 100644
--- a/lib/Address.php
+++ b/lib/Address.php
@@ -1,4 +1,5 @@
 <?php
+
 declare(strict_types=1);
 
 /**
@@ -30,6 +31,11 @@ use JsonSerializable;
 
 class Address implements JsonSerializable {
 
+	public const TYPE_FROM = 0;
+	public const TYPE_TO = 1;
+	public const TYPE_CC = 2;
+	public const TYPE_BCC = 3;
+
 	/** @var Horde_Mail_Rfc822_Address */
 	private $wrapped;
 
@@ -40,17 +46,17 @@ class Address implements JsonSerializable {
 	public function __construct($label, $email) {
 		$this->wrapped = new Horde_Mail_Rfc822_Address($email);
 		// If no label is set we use the email
-		if ($label !== $email && !is_null($label)) {
+		if ($label !== $email && $label !== null) {
 			$this->wrapped->personal = $label;
 		}
 	}
 
 	/**
-	 * @return string
+	 * @return string|null
 	 */
-	public function getLabel(): string {
+	public function getLabel(): ?string {
 		$personal = $this->wrapped->personal;
-		if (is_null($personal)) {
+		if ($personal === null) {
 			// Fallback
 			return $this->getEmail();
 		}
@@ -58,9 +64,9 @@ class Address implements JsonSerializable {
 	}
 
 	/**
-	 * @return string
+	 * @return string|null
 	 */
-	public function getEmail(): string {
+	public function getEmail(): ?string {
 		return $this->wrapped->bare_address;
 	}
 
diff --git a/lib/AddressList.php b/lib/AddressList.php
index 5b2c184ca..619ffba37 100644
--- a/lib/AddressList.php
+++ b/lib/AddressList.php
@@ -1,4 +1,4 @@
-<?php
+<?php declare(strict_types=1);
 
 /**
  * @copyright 2017 Christoph Wurst <christoph@winzerhof-wurst.at>
@@ -69,6 +69,12 @@ class AddressList implements Countable, JsonSerializable {
 		return new AddressList($addresses);
 	}
 
+	public static function fromRow(array $recipient): self {
+		return new self([
+			new Address($recipient['label'], $recipient['email'])
+		]);
+	}
+
 	/**
 	 * Get first element
 	 *
diff --git a/lib/AppInfo/BootstrapSingleton.php b/lib/AppInfo/BootstrapSingleton.php
index 3c6af088d..f0451845b 100644
--- a/lib/AppInfo/BootstrapSingleton.php
+++ b/lib/AppInfo/BootstrapSingleton.php
@@ -48,7 +48,7 @@ use OCA\Mail\Service\Group\IGroupService;
 use OCA\Mail\Service\Group\NextcloudGroupService;
 use OCA\Mail\Service\Group\ContactsGroupService;
 use OCA\Mail\Service\MailManager;
-use OCA\Mail\Service\MailSearch;
+use OCA\Mail\Service\Search\MailSearch;
 use OCA\Mail\Service\MailTransmission;
 use OCA\Mail\Service\UserPreferenceSevice;
 use OCP\AppFramework\IAppContainer;
diff --git a/lib/BackgroundJob/SyncJob.php b/lib/BackgroundJob/SyncJob.php
new file mode 100644
index 000000000..6dfab3d2e
--- /dev/null
+++ b/lib/BackgroundJob/SyncJob.php
@@ -0,0 +1,78 @@
+<?php declare(strict_types=1);
+/**
+ * @copyright Copyright (c) 2019, Roeland Jago Douma <roeland@famdouma.nl>
+ *
+ * @author Roeland Jago Douma <roeland@famdouma.nl>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+namespace OCA\Mail\BackgroundJob;
+
+use OCA\Mail\Service\AccountService;
+use OCA\Mail\Service\SyncService;
+use OCP\AppFramework\Db\DoesNotExistException;
+use OCP\AppFramework\Utility\ITimeFactory;
+use OCP\BackgroundJob\IJobList;
+use OCP\BackgroundJob\TimedJob;
+use OCP\ILogger;
+
+class SyncJob extends TimedJob {
+
+	/** @var AccountService */
+	private $accountService;
+	/** @var SyncService */
+	private $syncService;
+	/** @var ILogger */
+	private $logger;
+	/** @var IJobList */
+	private $jobList;
+
+	public function __construct(ITimeFactory $time,
+								AccountService $accountService,
+								SyncService $syncService,
+								ILogger $logger,
+								IJobList $jobList) {
+		parent::__construct($time);
+
+		$this->accountService = $accountService;
+		$this->syncService = $syncService;
+		$this->logger = $logger;
+
+		$this->setInterval(3600);
+		$this->jobList = $jobList;
+	}
+
+	protected function run($argument) {
+		$accountId = (int)$argument['accountId'];
+
+		try {
+			$account = $this->accountService->findById($accountId);
+		} catch (DoesNotExistException $e) {
+			$this->logger->debug('Could not find account <' . $accountId . '> removing from jobs');
+			$this->jobList->remove(self::class, $argument);
+			return;
+		}
+
+		try {
+			$this->syncService->syncAccount($account);
+		} catch (\Exception $e) {
+			$this->logger->logException($e);
+		}
+	}
+
+}
diff --git a/lib/Command/SyncAccount.php b/lib/Command/SyncAccount.php
new file mode 100644
index 000000000..459d7e5d7
--- /dev/null
+++ b/lib/Command/SyncAccount.php
@@ -0,0 +1,73 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Command;
+
+use OCA\Mail\Db\MailboxMapper;
+use OCA\Mail\Service\AccountService;
+use OCA\Mail\Service\SyncService;
+use Symfony\Component\Console\Command\Command;
+use Symfony\Component\Console\Input\InputArgument;
+use Symfony\Component\Console\Input\InputInterface;
+use Symfony\Component\Console\Input\InputOption;
+use Symfony\Component\Console\Output\OutputInterface;
+
+class SyncAccount extends Command {
+
+	const ARGUMENT_ACCOUNT_ID = 'account-id';
+	const OPTION_FORCE = 'force';
+
+	/** @var AccountService */
+	private $accountService;
+
+	/** @var MailboxMapper */
+	private $mailboxMapper;
+
+	/** @var SyncService */
+	private $syncService;
+
+	public function __construct(AccountService $service,
+								MailboxMapper $mailboxMapper,
+								SyncService $syncService) {
+		parent::__construct();
+
+		$this->accountService = $service;
+		$this->mailboxMapper = $mailboxMapper;
+		$this->syncService = $syncService;
+	}
+
+	protected function configure() {
+		$this->setName('mail:account:sync');
+		$this->setDescription('Synchronize an IMAP account');
+		$this->addArgument(self::ARGUMENT_ACCOUNT_ID, InputArgument::REQUIRED);
+		$this->addOption(self::OPTION_FORCE, 'f', InputOption::VALUE_NONE);
+	}
+
+	protected function execute(InputInterface $input, OutputInterface $output) {
+		$accountId = (int)$input->getArgument(self::ARGUMENT_ACCOUNT_ID);
+		$force = $input->getOption(self::OPTION_FORCE);
+
+		$account = $this->accountService->findById($accountId);
+		$this->syncService->syncAccount($account, $force);
+	}
+}
diff --git a/lib/Contracts/IMailManager.php b/lib/Contracts/IMailManager.php
index e82077d7a..9575c6cfc 100644
--- a/lib/Contracts/IMailManager.php
+++ b/lib/Contracts/IMailManager.php
@@ -69,17 +69,6 @@ interface IMailManager {
 	public function getMessage(Account $account, string $mailbox, int $id, bool $loadBody = false): IMAPMessage;
 
 	/**
-	 * @param Account
-	 * @param SyncRequest $syncRequest
-	 *
-	 * @return SyncResponse
-	 *
-	 * @throws ClientException
-	 * @throws ServiceException
-	 */
-	public function syncMessages(Account $account, SyncRequest $syncRequest): SyncResponse;
-
-	/**
 	 * @param Account $sourceAccount
 	 * @param string $sourceFolderId
 	 * @param int $messageId
diff --git a/lib/Controller/FoldersController.php b/lib/Controller/FoldersController.php
index 5316bfb1c..ca1b10f93 100644
--- a/lib/Controller/FoldersController.php
+++ b/lib/Controller/FoldersController.php
@@ -25,6 +25,10 @@ declare(strict_types=1);
 
 namespace OCA\Mail\Controller;
 
+use Horde_Imap_Client;
+use OCA\Mail\Exception\MailboxNotCachedException;
+use OCA\Mail\Exception\ServiceException;
+use OCA\Mail\Service\SyncService;
 use function base64_decode;
 use function is_array;
 use OCA\Mail\Contracts\IMailManager;
@@ -47,6 +51,9 @@ class FoldersController extends Controller {
 	/**  @var IMailManager */
 	private $mailManager;
 
+	/** @var SyncService */
+	private $syncService;
+
 	/**
 	 * @param string $appName
 	 * @param IRequest $request
@@ -54,13 +61,18 @@ class FoldersController extends Controller {
 	 * @param string $UserId
 	 * @param IMailManager $mailManager
 	 */
-	public function __construct(string $appName, IRequest $request,
-								AccountService $accountService, $UserId, IMailManager $mailManager) {
+	public function __construct(string $appName,
+								IRequest $request,
+								AccountService $accountService,
+								$UserId,
+								IMailManager $mailManager,
+								SyncService $syncService) {
 		parent::__construct($appName, $request);
 
 		$this->accountService = $accountService;
 		$this->currentUserId = $UserId;
 		$this->mailManager = $mailManager;
+		$this->syncService = $syncService;
 	}
 
 	/**
@@ -91,15 +103,28 @@ class FoldersController extends Controller {
 	 * @param string $syncToken
 	 * @param int[] $uids
 	 * @return JSONResponse
+	 * @throws ServiceException
 	 */
-	public function sync(int $accountId, string $folderId, string $syncToken, array $uids = []): JSONResponse {
+	public function sync(int $accountId, string $folderId, array $uids): JSONResponse {
 		$account = $this->accountService->find($this->currentUserId, $accountId);
 
-		if (empty($accountId) || empty($folderId) || empty($syncToken) || !is_array($uids)) {
+		if (empty($accountId) || empty($folderId) || !is_array($uids)) {
 			return new JSONResponse(null, Http::STATUS_BAD_REQUEST);
 		}
 
-		$syncResponse = $this->mailManager->syncMessages($account, new SyncRequest(base64_decode($folderId), $syncToken, $uids));
+		try {
+			$syncResponse = $this->syncService->syncMailbox(
+				$account,
+				base64_decode($folderId),
+				Horde_Imap_Client::SYNC_NEWMSGSUIDS | Horde_Imap_Client::SYNC_FLAGSUIDS | Horde_Imap_Client::SYNC_VANISHEDUIDS,
+				array_map(function($uid) {
+					return (int) $uid;
+				}, $uids),
+				true
+			);
+		} catch (MailboxNotCachedException $e) {
+			return new JSONResponse(null, Http::STATUS_PRECONDITION_REQUIRED);
+		}
 
 		return new JSONResponse($syncResponse);
 	}
diff --git a/lib/Controller/MessagesController.php b/lib/Controller/MessagesController.php
index 2764bbb3c..7e075621e 100755
--- a/lib/Controller/MessagesController.php
+++ b/lib/Controller/MessagesController.php
@@ -40,6 +40,7 @@ use OCA\Mail\Model\IMAPMessage;
 use OCA\Mail\Service\AccountService;
 use OCA\Mail\Service\IMailBox;
 use OCA\Mail\Service\ItineraryService;
+use OCA\Mail\Service\SyncService;
 use OCP\AppFramework\Controller;
 use OCP\AppFramework\Db\DoesNotExistException;
 use OCP\AppFramework\Http;
@@ -69,6 +70,9 @@ class MessagesController extends Controller {
 	/** @var ItineraryService */
 	private $itineraryService;
 
+	/** @var SyncService */
+	private $syncService;
+
 	/** @var string */
 	private $currentUserId;
 
@@ -104,6 +108,7 @@ class MessagesController extends Controller {
 								IMailManager $mailManager,
 								IMailSearch $mailSearch,
 								ItineraryService $itineraryService,
+								SyncService $syncService,
 								string $UserId,
 								$userFolder,
 								ILogger $logger,
@@ -116,6 +121,7 @@ class MessagesController extends Controller {
 		$this->mailManager = $mailManager;
 		$this->mailSearch = $mailSearch;
 		$this->itineraryService = $itineraryService;
+		$this->syncService = $syncService;
 		$this->currentUserId = $UserId;
 		$this->userFolder = $userFolder;
 		$this->logger = $logger;
@@ -144,6 +150,11 @@ class MessagesController extends Controller {
 			return new JSONResponse(null, Http::STATUS_FORBIDDEN);
 		}
 
+		$this->syncService->ensurePopulated(
+			$account,
+			base64_decode($folderId)
+		);
+
 		$this->logger->debug("loading messages of folder <$folderId>");
 
 		return new JSONResponse(
diff --git a/lib/Db/MailAccountMapper.php b/lib/Db/MailAccountMapper.php
index 3881912cc..a483b5e78 100644
--- a/lib/Db/MailAccountMapper.php
+++ b/lib/Db/MailAccountMapper.php
@@ -60,7 +60,7 @@ class MailAccountMapper extends QBMapper {
 	}
 
 	/**
-	 * @param int $id
+	 * Finds an mail account by id
 	 *
 	 * @return MailAccount
 	 * @throws DoesNotExistException
@@ -134,4 +134,13 @@ class MailAccountMapper extends QBMapper {
 		$delete->execute();
 	}
 
+	public function getAllAccounts(): array  {
+		$qb = $this->db->getQueryBuilder();
+		$query = $qb
+			->select('*')
+			->from($this->getTableName());
+
+		return $this->findEntities($query);
+	}
+
 }
diff --git a/lib/Db/Mailbox.php b/lib/Db/Mailbox.php
index d5727bf7f..c09b3981a 100644
--- a/lib/Db/Mailbox.php
+++ b/lib/Db/Mailbox.php
@@ -37,8 +37,18 @@ use function strtolower;
  * @method void setName(string $name)
  * @method int getAccountId()
  * @method void setAccountId(int $accountId)
- * @method string|null getSyncToken()
- * @method void setSyncToken(string|null $syncToken)
+ * @method string|null getSyncNewToken()
+ * @method void setSyncNewToken(string|null $syncNewToken)
+ * @method string|null getSyncChangedToken()
+ * @method void setSyncChangedToken(string|null $syncNewToken)
+ * @method string|null getSyncVanishedToken()
+ * @method void setSyncVanishedToken(string|null $syncNewToken)
+ * @method int|null getSyncNewLock()
+ * @method void setSyncNewLock(int|null $ts)
+ * @method int|null getSyncChangedLock()
+ * @method void setSyncChangedLock(int|null $ts)
+ * @method int|null getSyncVanishedLock()
+ * @method void setSyncVanishedLock(int|null $ts)
  * @method string getAttributes()
  * @method void setAttributes(string $attributes)
  * @method string getDelimiter()
@@ -56,7 +66,12 @@ class Mailbox extends Entity {
 
 	protected $name;
 	protected $accountId;
-	protected $syncToken;
+	protected $syncNewToken;
+	protected $syncChangedToken;
+	protected $syncVanishedToken;
+	protected $syncNewLock;
+	protected $syncChangedLock;
+	protected $syncVanishedLock;
 	protected $attributes;
 	protected $delimiter;
 	protected $messages;
@@ -68,6 +83,9 @@ class Mailbox extends Entity {
 		$this->addType('accountId', 'integer');
 		$this->addType('messages', 'integer');
 		$this->addType('unseen', 'integer');
+		$this->addType('syncNewLock', 'integer');
+		$this->addType('syncChangedLock', 'integer');
+		$this->addType('syncVanishedLock', 'integer');
 		$this->addType('selectable', 'boolean');
 	}
 
@@ -78,7 +96,6 @@ class Mailbox extends Entity {
 			json_decode($this->getAttributes() ?? '[]', true) ?? [],
 			$this->delimiter
 		);
-		$folder->setSyncToken($this->getSyncToken());
 		foreach ($this->getSpecialUseParsed() as $use) {
 			$folder->addSpecialUse($use);
 		}
diff --git a/lib/Db/MailboxMapper.php b/lib/Db/MailboxMapper.php
index 4cf8e1baf..3acbde53b 100644
--- a/lib/Db/MailboxMapper.php
+++ b/lib/Db/MailboxMapper.php
@@ -24,16 +24,25 @@
 namespace OCA\Mail\Db;
 
 use OCA\Mail\Account;
+use OCA\Mail\Exception\ConcurrentSyncException;
 use OCA\Mail\Exception\ServiceException;
 use OCP\AppFramework\Db\DoesNotExistException;
 use OCP\AppFramework\Db\MultipleObjectsReturnedException;
 use OCP\AppFramework\Db\QBMapper;
+use OCP\AppFramework\Utility\ITimeFactory;
+use OCP\DB\QueryBuilder\IQueryBuilder;
 use OCP\IDBConnection;
+use OCP\Security\ISecureRandom;
 
 class MailboxMapper extends QBMapper {
 
-	public function __construct(IDBConnection $db) {
+	/** @var ITimeFactory */
+	private $timeFactory;
+
+	public function __construct(IDBConnection $db,
+								ITimeFactory $timeFactory) {
 		parent::__construct($db, 'mail_mailboxes');
+		$this->timeFactory = $timeFactory;
 	}
 
 	/**
@@ -99,4 +108,90 @@ class MailboxMapper extends QBMapper {
 		throw new DoesNotExistException("Special mailbox $specialUse does not exist");
 	}
 
+	/**
+	 * @throws ConcurrentSyncException
+	 */
+	private function lockForSync(Mailbox $mailbox, string $attr, ?int $lock): int {
+		$now = $this->timeFactory->getTime();
+
+		if ($lock !== null
+			&& $lock > ($now - 5 * 60)) {
+			// Another process is syncing
+			throw new ConcurrentSyncException($mailbox->getId() . ' is already being synced');
+		}
+
+		$query = $this->db->getQueryBuilder();
+		$query->update($this->getTableName())
+			->set($attr, $query->createNamedParameter($now, IQueryBuilder::PARAM_INT))
+			->where(
+				$query->expr()->eq('id', $query->createNamedParameter($mailbox->getId(), IQueryBuilder::PARAM_INT)),
+				$this->eqOrNull($query, $attr, $lock, IQueryBuilder::PARAM_INT)
+			);
+		if ($query->execute() === 0) {
+			// Another process just started syncing
+
+			throw new ConcurrentSyncException();
+		}
+
+		return $now;
+	}
+
+	/**
+	 * @throws ConcurrentSyncException
+	 */
+	public function lockForNewSync(Mailbox $mailbox): void {
+		$mailbox->setSyncNewLock(
+			$this->lockForSync($mailbox, 'sync_new_lock', $mailbox->getSyncNewLock())
+		);
+	}
+
+	/**
+	 * @throws ConcurrentSyncException
+	 */
+	public function lockForChangeSync(Mailbox $mailbox): void {
+		$mailbox->setSyncChangedLock(
+			$this->lockForSync($mailbox, 'sync_changed_lock', $mailbox->getSyncChangedLock())
+		);
+	}
+
+	/**
+	 * @throws ConcurrentSyncException
+	 */
+	public function lockForVanishedSync(Mailbox $mailbox): void {
+		$mailbox->setSyncVanishedLock(
+			$this->lockForSync($mailbox, 'sync_vanished_lock', $mailbox->getSyncVanishedLock())
+		);
+	}
+
+	/**
+	 * @param Mailbox $mailbox
+	 * @param IQueryBuilder $query
+	 *
+	 * @return string
+	 */
+	private function eqOrNull(IQueryBuilder $query, string $column, $value, int $type): string {
+		if ($value === null) {
+			return $query->expr()->isNull($column);
+		}
+		return $query->expr()->eq($column, $query->createNamedParameter($value, $type));
+	}
+
+	public function unlockFromNewSync(Mailbox $mailbox): void {
+		$mailbox->setSyncNewLock(null);
+
+		$this->update($mailbox);
+	}
+
+	public function unlockFromChangedSync(Mailbox $mailbox): void {
+		$mailbox->setSyncChangedLock(null);
+
+		$this->update($mailbox);
+	}
+
+	public function unlockFromVanishedSync(Mailbox $mailbox): void {
+		$mailbox->setSyncVanishedLock(null);
+
+		$this->update($mailbox);
+	}
+
 }
diff --git a/lib/Db/Message.php b/lib/Db/Message.php
new file mode 100644
index 000000000..9ed4391bd
--- /dev/null
+++ b/lib/Db/Message.php
@@ -0,0 +1,186 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Db;
+
+use JsonSerializable;
+use OCA\Mail\AddressList;
+use OCP\AppFramework\Db\Entity;
+use function json_encode;
+
+/**
+ * @method void setUid(int $uid)
+ * @method int getUid()
+ * @method void setMessageId(string $id)
+ * @method string getMessageId()
+ * @method void setMailboxId(int $mailbox)
+ * @method int getMailboxId()
+ * @method void setSubject(string $subject)
+ * @method string getSubject()
+ * @method void setSentAt(int $time)
+ * @method int getSentAt()
+ * @method void setFlagAnswered(bool $answered)
+ * @method bool getFlagAnswered()
+ * @method void setFlagDeleted(bool $deleted)
+ * @method bool getFlagDeleted()
+ * @method void setFlagDraft(bool $answered)
+ * @method bool getFlagDraft()
+ * @method void setFlagFlagged(bool $flagged)
+ * @method bool getFlagFlagged()
+ * @method void setFlagSeen(bool $seen)
+ * @method bool getFlagSeen()
+ * @method void setFlagForwarded(bool $forwarded)
+ * @method bool getFlagForwarded()
+ * @method void setFlagJunk(bool $junk)
+ * @method bool getFlagJunk()
+ * @method void setFlagNotjunk(bool $notjunk)
+ * @method bool getFlagNotjunk()
+ * @method void setUpdatedAt(int $time)
+ * @method int getUpdatedAt()
+ */
+class Message extends Entity implements JsonSerializable {
+
+	protected $uid;
+	protected $messageId;
+	protected $mailboxId;
+	protected $subject;
+	protected $sentAt;
+	protected $flagAnswered;
+	protected $flagDeleted;
+	protected $flagDraft;
+	protected $flagFlagged;
+	protected $flagSeen;
+	protected $flagForwarded;
+	protected $flagJunk;
+	protected $flagNotjunk;
+	protected $updatedAt;
+
+	/** @var AddressList */
+	private $from;
+
+	/** @var AddressList */
+	private $to;
+
+	/** @var AddressList */
+	private $cc;
+
+	/** @var AddressList */
+	private $bcc;
+
+	public function __construct() {
+		$this->from = new AddressList([]);
+		$this->to = new AddressList([]);
+		$this->cc = new AddressList([]);
+		$this->bcc = new AddressList([]);
+
+		$this->addType('uid', 'integer');
+		$this->addType('sentAt', 'integer');
+		$this->addType('flagAnswered', 'bool');
+		$this->addType('flagDeleted', 'bool');
+		$this->addType('flagDraft', 'bool');
+		$this->addType('flagFlagged', 'bool');
+		$this->addType('flagSeen', 'bool');
+		$this->addType('flagForwarded', 'bool');
+		$this->addType('flagJunk', 'bool');
+		$this->addType('flagNotjunk', 'bool');
+		$this->addType('updatedAt', 'integer');
+	}
+
+	/**
+	 * @return AddressList
+	 */
+	public function getFrom(): AddressList {
+		return $this->from;
+	}
+
+	/**
+	 * @param AddressList $from
+	 */
+	public function setFrom(AddressList $from): void {
+		$this->from = $from;
+	}
+
+	/**
+	 * @return AddressList
+	 */
+	public function getTo(): AddressList {
+		return $this->to;
+	}
+
+	/**
+	 * @param AddressList $to
+	 */
+	public function setTo(AddressList $to): void {
+		$this->to = $to;
+	}
+
+	/**
+	 * @return AddressList
+	 */
+	public function getCc(): AddressList {
+		return $this->cc;
+	}
+
+	/**
+	 * @param AddressList $cc
+	 */
+	public function setCc(AddressList $cc): void {
+		$this->cc = $cc;
+	}
+
+	/**
+	 * @return AddressList
+	 */
+	public function getBcc(): AddressList {
+		return $this->bcc;
+	}
+
+	/**
+	 * @param AddressList $bcc
+	 */
+	public function setBcc(AddressList $bcc): void {
+		$this->bcc = $bcc;
+	}
+
+	public function jsonSerialize() {
+		return [
+			'id' => $this->getUid(), // Change to UID on front-end
+			'subject' => $this->getSubject(),
+			'dateInt' => $this->getSentAt(),
+			'flags' => [
+				'unseen' => !$this->getFlagSeen(),
+				'flagged' => $this->getFlagFlagged(),
+				'answered' => $this->getFlagAnswered(),
+				'deleted' => $this->getFlagDeleted(),
+				'draft' => $this->getFlagDraft(),
+				'forwarded' => $this->getFlagForwarded(),
+				'hasAttachments' => false, // TODO
+			],
+			'from' => $this->getFrom()->jsonSerialize(),
+			'to' => $this->getTo()->jsonSerialize(),
+			'cc' => $this->getCc()->jsonSerialize(),
+			'bcc' => $this->getBcc()->jsonSerialize(),
+		];
+	}
+
+}
diff --git a/lib/Db/MessageMapper.php b/lib/Db/MessageMapper.php
new file mode 100644
index 000000000..c3cb8b42b
--- /dev/null
+++ b/lib/Db/MessageMapper.php
@@ -0,0 +1,378 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Db;
+
+use Horde_Imap_Client;
+use OCA\Mail\Address;
+use OCA\Mail\AddressList;
+use OCA\Mail\Service\Search\SearchQuery;
+use OCP\AppFramework\Db\QBMapper;
+use OCP\AppFramework\Utility\ITimeFactory;
+use OCP\DB\QueryBuilder\IQueryBuilder;
+use OCP\IDBConnection;
+use function array_combine;
+use function array_keys;
+use function array_map;
+
+class MessageMapper extends QBMapper {
+
+	/** @var ITimeFactory */
+	private $timeFactory;
+
+	public function __construct(IDBConnection $db,
+								ITimeFactory $timeFactory) {
+		parent::__construct($db, 'mail_messages');
+		$this->timeFactory = $timeFactory;
+	}
+
+	public function findAllUids(Mailbox $mailbox): array {
+		$query = $this->db->getQueryBuilder();
+
+		$query->select('uid')
+			->from($this->getTableName())
+			->where($query->expr()->eq('mailbox_id', $query->createNamedParameter($mailbox->getId())));
+
+		$result = $query->execute();
+		$uids = array_map(function (array $row) {
+			return (int) $row['uid'];
+		}, $result->fetchAll());
+		$result->closeCursor();
+
+		return $uids;
+	}
+
+	public function insertBulk(Message ...$messages): void {
+		$this->db->beginTransaction();
+
+		$qb1 = $this->db->getQueryBuilder();
+		$qb1->insert($this->getTableName());
+		$qb1->setValue('uid', $qb1->createParameter('uid'));
+		$qb1->setValue('message_id', $qb1->createParameter('message_id'));
+		$qb1->setValue('mailbox_id', $qb1->createParameter('mailbox_id'));
+		$qb1->setValue('subject', $qb1->createParameter('subject'));
+		$qb1->setValue('sent_at', $qb1->createParameter('sent_at'));
+		$qb1->setValue('flag_answered', $qb1->createParameter('flag_answered'));
+		$qb1->setValue('flag_deleted', $qb1->createParameter('flag_deleted'));
+		$qb1->setValue('flag_draft', $qb1->createParameter('flag_draft'));
+		$qb1->setValue('flag_flagged', $qb1->createParameter('flag_flagged'));
+		$qb1->setValue('flag_seen', $qb1->createParameter('flag_seen'));
+		$qb1->setValue('flag_forwarded', $qb1->createParameter('flag_forwarded'));
+		$qb1->setValue('flag_junk', $qb1->createParameter('flag_junk'));
+		$qb1->setValue('flag_notjunk', $qb1->createParameter('flag_notjunk'));
+		$qb2 = $this->db->getQueryBuilder();
+
+		$qb2->insert('mail_recipients')
+			->setValue('message_id', $qb2->createParameter('message_id'))
+			->setValue('type', $qb2->createParameter('type'))
+			->setValue('label', $qb2->createParameter('label'))
+			->setValue('email', $qb2->createParameter('email'));
+
+		foreach ($messages as $message) {
+			$qb1->setParameter('uid', $message->getUid(), IQueryBuilder::PARAM_INT);
+			$qb1->setParameter('message_id', $message->getMessageId(), IQueryBuilder::PARAM_STR);
+			$qb1->setParameter('mailbox_id', $message->getMailboxId(), IQueryBuilder::PARAM_INT);
+			$qb1->setParameter('subject', $message->getSubject(), IQueryBuilder::PARAM_STR);
+			$qb1->setParameter('sent_at', $message->getSentAt(), IQueryBuilder::PARAM_INT);
+			$qb1->setParameter('flag_answered', $message->getFlagAnswered(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_deleted', $message->getFlagDeleted(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_draft', $message->getFlagDraft(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_flagged', $message->getFlagFlagged(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_seen', $message->getFlagSeen(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_forwarded', $message->getFlagForwarded(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_junk', $message->getFlagJunk(), IQueryBuilder::PARAM_BOOL);
+			$qb1->setParameter('flag_notjunk', $message->getFlagNotjunk(), IQueryBuilder::PARAM_BOOL);
+
+			$qb1->execute();
+
+			$messageId = $qb1->getLastInsertId();
+			$recipientTypes = [
+				Address::TYPE_FROM => $message->getFrom(),
+				Address::TYPE_TO => $message->getTo(),
+				Address::TYPE_CC => $message->getCc(),
+				Address::TYPE_BCC => $message->getBcc(),
+			];
+			foreach ($recipientTypes as $type => $recipients) {
+				/** @var AddressList $recipients */
+				foreach ($recipients->iterate() as $recipient) {
+					/** @var Address $recipient */
+					if ($recipient->getEmail() === null) {
+						// If for some reason the e-mail is not set we should ignore this entry
+						continue;
+					}
+
+					$qb2->setParameter('message_id', $messageId, IQueryBuilder::PARAM_INT);
+					$qb2->setParameter('type', $type, IQueryBuilder::PARAM_INT);
+					$qb2->setParameter('label', $recipient->getLabel(), IQueryBuilder::PARAM_STR);
+					$qb2->setParameter('email', $recipient->getEmail(), IQueryBuilder::PARAM_STR);
+
+					$qb2->execute();
+				}
+			}
+		}
+
+		$this->db->commit();
+	}
+
+	public function updateBulk(Message ...$messages): void {
+		$this->db->beginTransaction();
+
+		$query = $this->db->getQueryBuilder();
+		$query->update($this->getTableName())
+			->set('flag_answered', $query->createParameter('flag_answered'))
+			->set('flag_deleted', $query->createParameter('flag_deleted'))
+			->set('flag_draft', $query->createParameter('flag_draft'))
+			->set('flag_flagged', $query->createParameter('flag_flagged'))
+			->set('flag_seen', $query->createParameter('flag_seen'))
+			->set('flag_forwarded', $query->createParameter('flag_forwarded'))
+			->set('flag_junk', $query->createParameter('flag_junk'))
+			->set('flag_notjunk', $query->createParameter('flag_notjunk'))
+			->set('updated_at', $query->createNamedParameter($this->timeFactory->getTime()))
+			->where($query->expr()->andX(
+				$query->expr()->eq('uid', $query->createParameter('uid')),
+				$query->expr()->eq('mailbox_id', $query->createParameter('mailbox_id'))
+			));
+
+		foreach ($messages as $message) {
+			$query->setParameter('uid', $message->getUid(), IQueryBuilder::PARAM_INT);
+			$query->setParameter('mailbox_id', $message->getMailboxId(), IQueryBuilder::PARAM_INT);
+			$query->setParameter('flag_answered', $message->getFlagAnswered(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_deleted', $message->getFlagDeleted(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_draft', $message->getFlagDraft(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_flagged', $message->getFlagFlagged(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_seen', $message->getFlagSeen(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_forwarded', $message->getFlagForwarded(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_junk', $message->getFlagJunk(), IQueryBuilder::PARAM_BOOL);
+			$query->setParameter('flag_notjunk', $message->getFlagNotjunk(), IQueryBuilder::PARAM_BOOL);
+
+			$query->execute();
+		}
+
+		$this->db->commit();
+	}
+
+	public function deleteAll(Mailbox $mailbox): void {
+		$query = $this->db->getQueryBuilder();
+
+		$query->delete($this->getTableName())
+			->where($query->expr()->eq('mailbox_id', $query->createNamedParameter($mailbox->getId())));
+
+		$query->execute();
+	}
+
+	public function deleteByUid(Mailbox $mailbox, int ...$uids): void {
+		$query = $this->db->getQueryBuilder();
+
+		$query->delete($this->getTableName())
+			->where(
+				$query->expr()->eq('mailbox_id', $query->createNamedParameter($mailbox->getId())),
+				$query->expr()->in('uid', $query->createNamedParameter($uids, IQueryBuilder::PARAM_INT_ARRAY))
+			);
+
+		$query->execute();
+	}
+
+	/**
+	 * @param Mailbox $mailbox
+	 * @param SearchQuery $query
+	 *
+	 * @return int[]
+	 */
+	public function findUidsByQuery(Mailbox $mailbox, SearchQuery $query): array {
+		$qb = $this->db->getQueryBuilder();
+
+		$select = $qb
+			->selectDistinct('m.uid')
+			->from($this->getTableName(), 'm');
+
+		if (!empty($query->getFrom())) {
+			$select->innerJoin('m', 'mail_recipients', 'r0', 'm.id = r0.message_id');
+		}
+		if (!empty($query->getTo())) {
+			$select->innerJoin('m', 'mail_recipients', 'r1', 'm.id = r1.message_id');
+		}
+		if (!empty($query->getCc())) {
+			$select->innerJoin('m', 'mail_recipients', 'r2', 'm.id = r2.message_id');
+		}
+		if (!empty($query->getBcc())) {
+			$select->innerJoin('m', 'mail_recipients', 'r3', 'm.id = r3.message_id');
+		}
+
+		$select->where(
+			$qb->expr()->eq('mailbox_id', $qb->createNamedParameter($mailbox->getId()), IQueryBuilder::PARAM_INT)
+		);
+
+		if (!empty($query->getFrom())) {
+			$select->andWhere(
+				$qb->expr()->in('r0.email', $qb->createNamedParameter($query->getFrom(), IQueryBuilder::PARAM_STR_ARRAY))
+			);
+		}
+		if (!empty($query->getTo())) {
+			$select->andWhere(
+				$qb->expr()->in('r1.email', $qb->createNamedParameter($query->getTo(), IQueryBuilder::PARAM_STR_ARRAY))
+			);
+		}
+		if (!empty($query->getTo())) {
+			$select->andWhere(
+				$qb->expr()->in('r2.email', $qb->createNamedParameter($query->getCc(), IQueryBuilder::PARAM_STR_ARRAY))
+			);
+		}
+		if (!empty($query->getTo())) {
+			$select->andWhere(
+				$qb->expr()->in('r3.email', $qb->createNamedParameter($query->getBcc(), IQueryBuilder::PARAM_STR_ARRAY))
+			);
+		}
+
+		if ($query->getCursor() !== null) {
+			$select->andWhere(
+				$qb->expr()->lt('sent_at', $qb->createNamedParameter($query->getCursor(), IQueryBuilder::PARAM_INT))
+			);
+		}
+
+		$flags = $query->getFlags();
+		$flagKeys = array_keys($flags);
+		foreach ([
+					 Horde_Imap_Client::FLAG_ANSWERED,
+					 Horde_Imap_Client::FLAG_DELETED,
+					 Horde_Imap_Client::FLAG_DRAFT,
+					 Horde_Imap_Client::FLAG_FLAGGED,
+					 Horde_Imap_Client::FLAG_RECENT,
+					 Horde_Imap_Client::FLAG_SEEN,
+					 Horde_Imap_Client::FLAG_FORWARDED,
+					 Horde_Imap_Client::FLAG_JUNK,
+					 Horde_Imap_Client::FLAG_NOTJUNK,
+				 ] as $flag) {
+			if (in_array($flag, $flagKeys, true)) {
+				$key = ltrim($flag, '\\');
+				$select->andWhere($qb->expr()->eq("flag_$key", $qb->createNamedParameter($flags[$flag], IQueryBuilder::PARAM_BOOL)));
+			}
+		}
+
+		$select = $select
+			->orderBy('sent_at', 'desc')
+			->setMaxResults(20);
+
+		return array_map(function (Message $message) {
+			return $message->getUid();
+		}, $this->findEntities($select));
+	}
+
+	/**
+	 * @param Mailbox $mailbox
+	 * @param int[] $uids
+	 *
+	 * @return Message[]
+	 */
+	public function findByUids(Mailbox $mailbox, array $uids): array {
+		$qb = $this->db->getQueryBuilder();
+
+		$select = $qb
+			->select('*')
+			->from($this->getTableName())
+			->where(
+				$qb->expr()->eq('mailbox_id', $qb->createNamedParameter($mailbox->getId()), IQueryBuilder::PARAM_INT),
+				$qb->expr()->in('uid', $qb->createNamedParameter($uids, IQueryBuilder::PARAM_INT_ARRAY))
+			)
+			->orderBy('sent_at', 'desc');
+
+		return $this->findRecipients($this->findEntities($select));
+	}
+
+	/**
+	 * @param Message[] $messages
+	 * @return Message[]
+	 */
+	private function findRecipients(array $messages): array {
+		/** @var Message[] $indexedMessages */
+		$indexedMessages = array_combine(
+			array_map(function (Message $msg) {
+				return $msg->getId();
+			}, $messages),
+			$messages
+		);
+		$qb2 = $this->db->getQueryBuilder();
+		$qb2->select('label', 'email', 'type', 'message_id')
+			->from('mail_recipients')
+			->where(
+				$qb2->expr()->in('message_id', $qb2->createNamedParameter(array_keys($indexedMessages), IQueryBuilder::PARAM_INT_ARRAY))
+			);
+		$recipientsResult = $qb2->execute();
+		foreach ($recipientsResult->fetchAll() as $recipient) {
+			$message = $indexedMessages[(int)$recipient['message_id']];
+			switch ($recipient['type']) {
+				case Address::TYPE_FROM:
+					$message->setFrom(
+						$message->getFrom()->merge(AddressList::fromRow($recipient))
+					);
+					break;
+				case Address::TYPE_TO:
+					$message->setTo(
+						$message->getTo()->merge(AddressList::fromRow($recipient))
+					);
+					break;
+				case Address::TYPE_CC:
+					$message->setCc(
+						$message->getCc()->merge(AddressList::fromRow($recipient))
+					);
+					break;
+				case Address::TYPE_BCC:
+					$message->setFrom(
+						$message->getFrom()->merge(AddressList::fromRow($recipient))
+					);
+					break;
+			}
+		}
+		$recipientsResult->closeCursor();
+
+		return $messages;
+	}
+
+	public function findNew(Mailbox $mailbox, int $highest): array {
+		$qb = $this->db->getQueryBuilder();
+
+		$select = $qb
+			->select('*')
+			->from($this->getTableName())
+			->where(
+				$qb->expr()->eq('mailbox_id', $qb->createNamedParameter($mailbox->getId(), IQueryBuilder::PARAM_INT)),
+				$qb->expr()->gt('uid', $qb->createNamedParameter($highest, IQueryBuilder::PARAM_INT))
+			);
+
+		return $this->findRecipients($this->findEntities($select));
+	}
+
+	public function findChanged(Mailbox $mailbox, int $since): array {
+		$qb = $this->db->getQueryBuilder();
+
+		$select = $qb
+			->select('*')
+			->from($this->getTableName())
+			->where(
+				$qb->expr()->eq('mailbox_id', $qb->createNamedParameter($mailbox->getId(), IQueryBuilder::PARAM_INT)),
+				$qb->expr()->gt('updated_at', $qb->createNamedParameter($since, IQueryBuilder::PARAM_INT))
+			);
+
+		return $this->findRecipients($this->findEntities($select));
+	}
+
+}
diff --git a/lib/IMAP/Search/ISearchStrategy.php b/lib/Exception/ConcurrentSyncException.php
index 264a0f33c..7cc91136d 100644
--- a/lib/IMAP/Search/ISearchStrategy.php
+++ b/lib/Exception/ConcurrentSyncException.php
@@ -21,16 +21,10 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-namespace OCA\Mail\IMAP\Search;
+namespace OCA\Mail\Exception;
 
-use Horde_Imap_Client_Exception;
-use Horde_Imap_Client_Ids;
+use Exception;
 
-interface ISearchStrategy {
-
-	/**
-	 * @throws Horde_Imap_Client_Exception
-	 */
-	public function getIds(int $maxResults, array $flags = []): Horde_Imap_Client_Ids;
+class ConcurrentSyncException extends Exception {
 
 }
diff --git a/lib/Exception/MailboxNotCachedException.php b/lib/Exception/MailboxNotCachedException.php
new file mode 100644
index 000000000..37242b1ad
--- /dev/null
+++ b/lib/Exception/MailboxNotCachedException.php
@@ -0,0 +1,7 @@
+<?php declare(strict_types=1);
+
+namespace OCA\Mail\Exception;
+
+class MailboxNotCachedException extends ServiceException {
+
+}
diff --git a/lib/Exception/UidValidityChangedException.php b/lib/Exception/UidValidityChangedException.php
new file mode 100644
index 000000000..9000909c2
--- /dev/null
+++ b/lib/Exception/UidValidityChangedException.php
@@ -0,0 +1,30 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\mail\lib\Exception;
+
+use OCA\Mail\Exception\ServiceException;
+
+class UidValidityChangedException extends ServiceException {
+
+}
diff --git a/lib/Folder.php b/lib/Folder.php
index 486c21c4a..9048bd68d 100644
--- a/lib/Folder.php
+++ b/lib/Folder.php
@@ -48,8 +48,6 @@ class Folder implements JsonSerializable {
 	private $specialUse;
 
 	/** @var string */
-	private $syncToken;
-
 	/**
 	 * @param Account $account
 	 * @param Horde_Imap_Client_Mailbox $mailbox
@@ -130,17 +128,6 @@ class Folder implements JsonSerializable {
 	}
 
 	/**
-	 * @param string $syncToken
-	 */
-	public function setSyncToken($syncToken) {
-		$this->syncToken = $syncToken;
-	}
-
-	public function getSyncToken(): ?string {
-		return $this->syncToken;
-	}
-
-	/**
 	 * @return array
 	 */
 	public function jsonSerialize() {
@@ -161,7 +148,6 @@ class Folder implements JsonSerializable {
 			'folders' => array_values($folders),
 			'specialUse' => $this->specialUse,
 			'specialRole' => empty($this->specialUse) ? null : $this->specialUse[0],
-			'syncToken' => $this->syncToken,
 		];
 	}
 
diff --git a/lib/IMAP/FolderMapper.php b/lib/IMAP/FolderMapper.php
index 87ce28722..0a6bd8f7a 100644
--- a/lib/IMAP/FolderMapper.php
+++ b/lib/IMAP/FolderMapper.php
@@ -76,16 +76,9 @@ class FolderMapper {
 				$mailbox['delimiter']
 			);
 
-			if ($folder->isSearchable()) {
-				$folder->setSyncToken($client->getSyncToken($folder->getMailbox()));
-			}
-
 			$folders[] = $folder;
 			if ($mailbox['mailbox']->utf8 === 'INBOX') {
 				$searchFolder = new SearchFolder($account->getId(), $mailbox['mailbox'], $mailbox['attributes'], $mailbox['delimiter']);
-				if ($folder->isSearchable()) {
-					$searchFolder->setSyncToken($client->getSyncToken($folder->getMailbox()));
-				}
 				$folders[] = $searchFolder;
 			}
 		}
diff --git a/lib/IMAP/MailboxSync.php b/lib/IMAP/MailboxSync.php
index bbd19e796..c631b4156 100644
--- a/lib/IMAP/MailboxSync.php
+++ b/lib/IMAP/MailboxSync.php
@@ -115,7 +115,6 @@ class MailboxSync {
 
 	private function updateMailboxFromFolder(Folder $folder, Mailbox $mailbox): void {
 		$mailbox->setDelimiter($folder->getDelimiter());
-		$mailbox->setSyncToken($folder->getSyncToken());
 		$mailbox->setAttributes(json_encode($folder->getAttributes()));
 		$mailbox->setDelimiter($folder->getDelimiter());
 		$mailbox->setMessages(0); // TODO
@@ -129,7 +128,6 @@ class MailboxSync {
 		$mailbox = new Mailbox();
 		$mailbox->setName($folder->getMailbox());
 		$mailbox->setAccountId($account->getId());
-		$mailbox->setSyncToken($folder->getSyncToken());
 		$mailbox->setAttributes(json_encode($folder->getAttributes()));
 		$mailbox->setDelimiter($folder->getDelimiter());
 		$mailbox->setMessages(0); // TODO
diff --git a/lib/IMAP/MessageMapper.php b/lib/IMAP/MessageMapper.php
index f42f8bc35..d0366912a 100644
--- a/lib/IMAP/MessageMapper.php
+++ b/lib/IMAP/MessageMapper.php
@@ -67,6 +67,33 @@ class MessageMapper {
 	}
 
 	/**
+	 * @param Horde_Imap_Client_Socket $client
+	 * @param Mailbox $mailbox
+	 *
+	 * @return IMAPMessage[]
+	 * @throws Horde_Imap_Client_Exception
+	 */
+	public function findAll(Horde_Imap_Client_Socket $client, Mailbox $mailbox): array {
+		$query = new Horde_Imap_Client_Fetch_Query();
+		$query->uid();
+
+		return $this->findByIds(
+			$client,
+			$mailbox->getMailbox(),
+			array_map(
+				function(Horde_Imap_Client_Data_Fetch $data) {
+					return $data->getUid();
+				},
+				iterator_to_array($client->fetch(
+					$mailbox->getMailbox(),
+					$query,
+					[]
+				))
+			)
+		);
+	}
+
+	/**
 	 * @return IMAPMessage[]
 	 * @throws Horde_Imap_Client_Exception
 	 */
@@ -77,10 +104,8 @@ class MessageMapper {
 		$query = new Horde_Imap_Client_Fetch_Query();
 		$query->envelope();
 		$query->flags();
-		$query->size();
 		$query->uid();
 		$query->imapDate();
-		$query->structure();
 
 		$fetchResults = iterator_to_array($client->fetch($mailbox, $query, [
 			'ids' => new Horde_Imap_Client_Ids($ids),
diff --git a/lib/IMAP/Search/FullScanSearchStrategy.php b/lib/IMAP/Search/FullScanSearchStrategy.php
deleted file mode 100644
index 758dde1be..000000000
--- a/lib/IMAP/Search/FullScanSearchStrategy.php
+++ /dev/null
@@ -1,86 +0,0 @@
-<?php declare(strict_types=1);
-
-/**
- * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @license GNU AGPL version 3 or any later version
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-namespace OCA\Mail\IMAP\Search;
-
-use Horde_Imap_Client_Exception;
-use Horde_Imap_Client_Fetch_Query;
-use Horde_Imap_Client_Ids;
-use Horde_Imap_Client_Socket;
-use function array_keys;
-use function array_slice;
-use function uasort;
-
-class FullScanSearchStrategy implements ISearchStrategy {
-
-	/** @var Horde_Imap_Client_Socket */
-	private $client;
-
-	/** @var string */
-	private $mailbox;
-
-	/** @var int|null */
-	private $cursor;
-
-	public function __construct(Horde_Imap_Client_Socket $client,
-								string $mailbox,
-								?int $cursor) {
-		$this->client = $client;
-		$this->mailbox = $mailbox;
-		$this->cursor = $cursor;
-	}
-
-	/**
-	 * Scan all messages of a mailbox and filter out matching ones
-	 *
-	 * This is slow, but some IMAP server don't support the SORT capability.
-	 *
-	 * @throws Horde_Imap_Client_Exception
-	 */
-	public function getIds(int $maxResults, array $flags = []): Horde_Imap_Client_Ids {
-		$query = new Horde_Imap_Client_Fetch_Query();
-		$query->uid();
-		$query->imapDate();
-
-		$result = $this->client->fetch($this->mailbox, $query);
-		$uidMap = [];
-		foreach ($result as $r) {
-			$ts = $r->getImapDate()->getTimeStamp();
-			if ($this->cursor === null || $ts < $this->cursor) {
-				$uidMap[$r->getUid()] = $ts;
-			}
-		}
-		// sort by time
-		uasort($uidMap, function ($a, $b) {
-			return $a < $b;
-		});
-		return new Horde_Imap_Client_Ids(
-			array_slice(
-				array_keys($uidMap),
-				0,
-				$maxResults
-			)
-		);
-	}
-
-}
diff --git a/lib/IMAP/Search/ImapSortSearchStrategy.php b/lib/IMAP/Search/ImapSortSearchStrategy.php
deleted file mode 100644
index 7c61de35d..000000000
--- a/lib/IMAP/Search/ImapSortSearchStrategy.php
+++ /dev/null
@@ -1,109 +0,0 @@
-<?php declare(strict_types=1);
-
-/**
- * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @license GNU AGPL version 3 or any later version
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-namespace OCA\Mail\IMAP\Search;
-
-use DateTime;
-use Horde_Imap_Client;
-use Horde_Imap_Client_Exception;
-use Horde_Imap_Client_Ids;
-use Horde_Imap_Client_Search_Query;
-use Horde_Imap_Client_Socket;
-use OCA\Mail\IMAP\Search\SearchFilterStringParser;
-use function array_reverse;
-use function array_slice;
-
-class ImapSortSearchStrategy implements ISearchStrategy {
-
-	/** @var Horde_Imap_Client_Socket */
-	private $client;
-
-	/** @var string */
-	private $mailbox;
-
-	/** @var Horde_Imap_Client_Search_Query */
-	private $query;
-
-	/** @var int|null */
-	private $cursor;
-
-	/** @var ISearchStrategy */
-	private $fallback;
-
-	public function __construct(Horde_Imap_Client_Socket $client,
-								string $mailbox,
-								Horde_Imap_Client_Search_Query $query,
-								?int $cursor,
-								ISearchStrategy $fallback) {
-		$this->client = $client;
-		$this->mailbox = $mailbox;
-		$this->query = $query;
-		$this->cursor = $cursor;
-		$this->fallback = $fallback;
-	}
-
-	/**
-	 * @param int $maxResults
-	 * @param array $flags
-	 *
-	 * @return Horde_Imap_Client_Ids
-	 * @throws Horde_Imap_Client_Exception
-	 */
-	public function getIds(int $maxResults, array $flags = []): Horde_Imap_Client_Ids {
-		$query = clone $this->query;
-
-		if ($this->cursor !== null) {
-			$query->dateTimeSearch(
-				DateTime::createFromFormat("U", (string) $this->cursor),
-				Horde_Imap_Client_Search_Query::DATE_BEFORE
-			);
-		}
-
-		try {
-			$result = $this->client->search(
-				$this->mailbox,
-				$query,
-				[
-					'sort' => [
-						Horde_Imap_Client::SORT_REVERSE,
-						Horde_Imap_Client::SORT_DATE
-					],
-				]
-			);
-		} catch (Horde_Imap_Client_Exception $e) {
-			// maybe the server's advertisement of SORT was a fake
-			// see https://github.com/nextcloud/mail/issues/50
-			// try again without SORT
-			return $this->fallback->getIds($maxResults, $flags);
-		}
-
-		return new Horde_Imap_Client_Ids(
-			array_slice(
-				$result['match']->ids,
-				0,
-				$maxResults
-			)
-		);
-	}
-
-}
diff --git a/lib/IMAP/Search/Provider.php b/lib/IMAP/Search/Provider.php
new file mode 100644
index 000000000..4cccc9fa8
--- /dev/null
+++ b/lib/IMAP/Search/Provider.php
@@ -0,0 +1,82 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\IMAP\Search;
+
+use Horde_Imap_Client_Exception;
+use Horde_Imap_Client_Search_Query;
+use OCA\Mail\Account;
+use OCA\Mail\Db\Mailbox;
+use OCA\Mail\Exception\ServiceException;
+use OCA\Mail\IMAP\IMAPClientFactory;
+use OCA\Mail\Service\Search\SearchQuery;
+use OCP\ILogger;
+
+class Provider {
+
+	/** @var IMAPClientFactory */
+	private $clientFactory;
+
+	/** @var ILogger */
+	private $logger;
+
+	public function __construct(IMAPClientFactory $clientFactory,
+								ILogger $logger) {
+		$this->clientFactory = $clientFactory;
+		$this->logger = $logger;
+	}
+
+	/**
+	 * @return int[]
+	 * @throws ServiceException
+	 */
+	public function findMatches(Account $account,
+								Mailbox $mailbox,
+								SearchQuery $searchQuery): array {
+		$client = $this->clientFactory->getClient($account);
+
+		try {
+			$fetchResult = $client->search(
+				$mailbox->getMailbox(),
+				$this->convertMailQueryToHordeQuery($searchQuery)
+			);
+		} catch (Horde_Imap_Client_Exception $e) {
+			throw new ServiceException('Could not get message IDs: ' . $e->getMessage(), 0, $e);
+		}
+
+		return $fetchResult['match']->ids;
+	}
+
+	private function convertMailQueryToHordeQuery(SearchQuery $searchQuery): Horde_Imap_Client_Search_Query {
+		$query = new Horde_Imap_Client_Search_Query();
+
+		foreach ($searchQuery->getFlags() as $flag => $set) {
+			$query->flag($flag, $set);
+		}
+
+		// TODO: text, header text
+
+		return $query;
+	}
+
+}
diff --git a/lib/IMAP/Sync/ISyncStrategy.php b/lib/IMAP/Sync/ISyncStrategy.php
index e8e69504d..028d419a9 100644
--- a/lib/IMAP/Sync/ISyncStrategy.php
+++ b/lib/IMAP/Sync/ISyncStrategy.php
@@ -57,6 +57,6 @@ interface ISyncStrategy {
 	 * @param Horde_Imap_Client_Data_Sync $hordeSync
 	 * @return int[]
 	 */
-	public function getVanishedMessages(Horde_Imap_Client_Base $imapClient,
-										Request $syncRequest, Horde_Imap_Client_Data_Sync $hordeSync): array;
+	public function getVanishedMessageUids(Horde_Imap_Client_Base $imapClient,
+										   Request $syncRequest, Horde_Imap_Client_Data_Sync $hordeSync): array;
 }
diff --git a/lib/IMAP/Sync/Response.php b/lib/IMAP/Sync/Response.php
index 00276f13c..1ae46b595 100644
--- a/lib/IMAP/Sync/Response.php
+++ b/lib/IMAP/Sync/Response.php
@@ -28,39 +28,63 @@ use OCA\Mail\Model\IMAPMessage;
 
 class Response implements JsonSerializable {
 
-	/** @var string */
-	private $syncToken;
-
 	/** @var IMAPMessage[] */
 	private $newMessages;
 
 	/** @var IMAPMessage[] */
 	private $changedMessages;
 
-	/** @var array */
-	private $vanishedMessages;
+	/** @var int[] */
+	private $vanishedMessageUids;
 
 	/**
 	 * @param string $syncToken
 	 * @param IMAPMessage[] $newMessages
 	 * @param IMAPMessage[] $changedMessages
-	 * @param array $vanishedMessages
+	 * @param int[] $vanishedMessageUids
 	 */
-	public function __construct(string $syncToken, array $newMessages = [], array $changedMessages = [],
-								array $vanishedMessages = []) {
-		$this->syncToken = $syncToken;
+	public function __construct(array $newMessages = [], array $changedMessages = [],
+								array $vanishedMessageUids = []) {
 		$this->newMessages = $newMessages;
 		$this->changedMessages = $changedMessages;
-		$this->vanishedMessages = $vanishedMessages;
+		$this->vanishedMessageUids = $vanishedMessageUids;
+	}
+
+	/**
+	 * @return IMAPMessage[]
+	 */
+	public function getNewMessages(): array {
+		return $this->newMessages;
+	}
+
+	/**
+	 * @return IMAPMessage[]
+	 */
+	public function getChangedMessages(): array {
+		return $this->changedMessages;
+	}
+
+	/**
+	 * @return int[]
+	 */
+	public function getVanishedMessageUids(): array {
+		return $this->vanishedMessageUids;
 	}
 
 	public function jsonSerialize(): array {
 		return [
 			'newMessages' => $this->newMessages,
 			'changedMessages' => $this->changedMessages,
-			'vanishedMessages' => $this->vanishedMessages,
-			'token' => $this->syncToken,
+			'vanishedMessages' => $this->vanishedMessageUids,
 		];
 	}
 
+	public function merge(Response $other): self {
+		return new self(
+			array_merge($this->getNewMessages(), $other->getNewMessages()),
+			array_merge($this->getChangedMessages(), $other->getChangedMessages()),
+			array_merge($this->getVanishedMessageUids(), $other->getVanishedMessageUids())
+		);
+	}
+
 }
diff --git a/lib/IMAP/Sync/SimpleMailboxSync.php b/lib/IMAP/Sync/SimpleMailboxSync.php
index 002c49c2b..919ea7367 100644
--- a/lib/IMAP/Sync/SimpleMailboxSync.php
+++ b/lib/IMAP/Sync/SimpleMailboxSync.php
@@ -69,8 +69,8 @@ class SimpleMailboxSync implements ISyncStrategy {
 	 * @param Horde_Imap_Client_Data_Sync $hordeSync
 	 * @return IMAPMessage[]
 	 */
-	public function getVanishedMessages(Horde_Imap_Client_Base $imapClient,
-										Request $syncRequest, Horde_Imap_Client_Data_Sync $hordeSync): array {
+	public function getVanishedMessageUids(Horde_Imap_Client_Base $imapClient,
+										   Request $syncRequest, Horde_Imap_Client_Data_Sync $hordeSync): array {
 		return $hordeSync->vanisheduids->ids;
 	}
 
diff --git a/lib/IMAP/Sync/Synchronizer.php b/lib/IMAP/Sync/Synchronizer.php
index 54db5128b..d286f33ec 100644
--- a/lib/IMAP/Sync/Synchronizer.php
+++ b/lib/IMAP/Sync/Synchronizer.php
@@ -23,11 +23,13 @@ declare(strict_types=1);
 
 namespace OCA\Mail\IMAP\Sync;
 
+use Horde_Imap_Client;
 use Horde_Imap_Client_Base;
 use Horde_Imap_Client_Exception;
 use Horde_Imap_Client_Exception_Sync;
 use Horde_Imap_Client_Ids;
 use Horde_Imap_Client_Mailbox;
+use OCA\mail\lib\Exception\UidValidityChangedException;
 
 class Synchronizer {
 
@@ -50,24 +52,36 @@ class Synchronizer {
 	/**
 	 * @param Horde_Imap_Client_Base $imapClient
 	 * @param Request $request
+	 * @param int $criteria
+	 *
 	 * @return Response
 	 * @throws Horde_Imap_Client_Exception
 	 * @throws Horde_Imap_Client_Exception_Sync
+	 * @throws UidValidityChangedException
 	 */
-	public function sync(Horde_Imap_Client_Base $imapClient, Request $request): Response {
+	public function sync(Horde_Imap_Client_Base $imapClient,
+						 Request $request,
+						 int $criteria = Horde_Imap_Client::SYNC_NEWMSGSUIDS|Horde_Imap_Client::SYNC_FLAGSUIDS|Horde_Imap_Client::SYNC_VANISHEDUIDS): Response {
 		$mailbox = new Horde_Imap_Client_Mailbox($request->getMailbox());
 		$ids = new Horde_Imap_Client_Ids($request->getUids());
-		$hordeSync = $imapClient->sync($mailbox, $request->getToken(), [
-			'ids' => $ids
-		]);
+		try {
+			$hordeSync = $imapClient->sync($mailbox, $request->getToken(), [
+				'criteria' => $criteria,
+				'ids' => $ids
+			]);
+		} catch (Horde_Imap_Client_Exception_Sync $e) {
+			if ($e->getCode() === Horde_Imap_Client_Exception_Sync::UIDVALIDITY_CHANGED) {
+				throw new UidValidityChangedException();
+			}
+			throw $e;
+		}
 
 		$syncStrategy = $this->getSyncStrategy($request);
 		$newMessages = $syncStrategy->getNewMessages($imapClient, $request, $hordeSync);
 		$changedMessages = $syncStrategy->getChangedMessages($imapClient, $request, $hordeSync);
-		$vanishedMessages = $syncStrategy->getVanishedMessages($imapClient, $request, $hordeSync);
+		$vanishedMessageUids = $syncStrategy->getVanishedMessageUids($imapClient, $request, $hordeSync);
 
-		$newSyncToken = $imapClient->getSyncToken($request->getMailbox());
-		return new Response($newSyncToken, $newMessages, $changedMessages, $vanishedMessages);
+		return new Response($newMessages, $changedMessages, $vanishedMessageUids);
 	}
 
 	/**
diff --git a/lib/Migration/FixAccountSyncs.php b/lib/Migration/FixAccountSyncs.php
new file mode 100644
index 000000000..319e0cb4e
--- /dev/null
+++ b/lib/Migration/FixAccountSyncs.php
@@ -0,0 +1,64 @@
+<?php
+declare(strict_types=1);
+/**
+ * @copyright Copyright (c) 2019, Roeland Jago Douma <roeland@famdouma.nl>
+ *
+ * @author Roeland Jago Douma <roeland@famdouma.nl>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+namespace OCA\Mail\Migration;
+
+use OCA\Mail\BackgroundJob\SyncJob;
+use OCA\Mail\Db\MailAccount;
+use OCA\Mail\Db\MailAccountMapper;
+use OCP\BackgroundJob\IJobList;
+use OCP\Migration\IOutput;
+use OCP\Migration\IRepairStep;
+
+class FixAccountSyncs implements IRepairStep {
+
+	/** @var IJobList */
+	private $jobList;
+	/** @var MailAccountMapper */
+	private $mapper;
+
+	public function __construct(IJobList $jobList, MailAccountMapper $mapper) {
+		$this->jobList = $jobList;
+		$this->mapper = $mapper;
+	}
+
+	public function getName(): string {
+		return 'Insert sync background job for all accounts';
+	}
+
+	public function run(IOutput $output) {
+		/** @var MailAccount[] $accounts */
+		$accounts = $this->mapper->getAllAccounts();
+
+		$output->startProgress(count($accounts));
+
+		foreach ($accounts as $account) {
+			$this->jobList->add(SyncJob::class, ['accountId' => $account->getId()]);
+			$output->advance();
+		}
+
+		$output->finishProgress();
+	}
+
+}
diff --git a/lib/Migration/Version1020Date20191002091034.php b/lib/Migration/Version1020Date20191002091034.php
new file mode 100644
index 000000000..4020be614
--- /dev/null
+++ b/lib/Migration/Version1020Date20191002091034.php
@@ -0,0 +1,33 @@
+<?php declare(strict_types=1);
+
+namespace OCA\Mail\Migration;
+
+use Closure;
+use OCP\DB\ISchemaWrapper;
+use OCP\IDBConnection;
+use OCP\Migration\SimpleMigrationStep;
+use OCP\Migration\IOutput;
+
+class Version1020Date20191002091034 extends SimpleMigrationStep {
+
+	/** @var IDBConnection */
+	protected $connection;
+
+	/**
+	 * @param IOutput $output
+	 * @param Closure $schemaClosure The `\Closure` returns a `ISchemaWrapper`
+	 * @param array $options
+	 *
+	 * @return ISchemaWrapper
+	 */
+	public function changeSchema(IOutput $output, Closure $schemaClosure, array $options) {
+		/** @var ISchemaWrapper $schema */
+		$schema = $schemaClosure();
+
+		$mailboxTable = $schema->getTable('mail_mailboxes');
+		$mailboxTable->dropColumn('sync_token');
+
+		return $schema;
+	}
+
+}
diff --git a/lib/Migration/Version1020Date20191002091035.php b/lib/Migration/Version1020Date20191002091035.php
new file mode 100644
index 000000000..d0cb3b054
--- /dev/null
+++ b/lib/Migration/Version1020Date20191002091035.php
@@ -0,0 +1,157 @@
+<?php declare(strict_types=1);
+
+namespace OCA\Mail\Migration;
+
+use Closure;
+use OCP\DB\ISchemaWrapper;
+use OCP\IDBConnection;
+use OCP\Migration\SimpleMigrationStep;
+use OCP\Migration\IOutput;
+
+class Version1020Date20191002091035 extends SimpleMigrationStep {
+
+	/** @var IDBConnection */
+	protected $connection;
+
+	public function __construct(IDBConnection $connection) {
+		$this->connection = $connection;
+	}
+
+	/**
+	 * @param IOutput $output
+	 * @param Closure $schemaClosure The `\Closure` returns a `ISchemaWrapper`
+	 * @param array $options
+	 *
+	 * @return ISchemaWrapper
+	 */
+	public function changeSchema(IOutput $output, Closure $schemaClosure, array $options) {
+		/** @var ISchemaWrapper $schema */
+		$schema = $schemaClosure();
+
+		$messagesTable = $schema->createTable('mail_messages');
+		$messagesTable->addColumn('id', 'integer', [
+			'autoincrement' => true,
+			'notnull' => true,
+			'length' => 20,
+		]);
+		$messagesTable->addColumn('uid', 'integer', [
+			'notnull' => true,
+			'length' => 4,
+		]);
+		$messagesTable->addColumn('message_id', 'string', [
+			'notnull' => false,
+			'length' => 255,
+		]);
+		$messagesTable->addColumn('mailbox_id', 'string', [
+			'notnull' => true,
+			'length' => 4,
+		]);
+		$messagesTable->addColumn('subject', 'string', [
+			'notnull' => true,
+			'length' => 255,
+			'default' => '',
+		]);
+		$messagesTable->addColumn('sent_at', 'integer', [
+			'notnull' => true,
+			'length' => 4,
+		]);
+		$messagesTable->addColumn('flag_answered', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_deleted', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_draft', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_flagged', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_seen', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_forwarded', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_junk', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('flag_notjunk', 'boolean', [
+			'notnull' => true,
+			'default' => false,
+		]);
+		$messagesTable->addColumn('updated_at', 'integer', [
+			'notnull' => false,
+			'length' => 4,
+		]);
+		$messagesTable->setPrimaryKey(['id']);
+		// We allow each UID just once
+		$messagesTable->addUniqueIndex([
+			'uid',
+			'mailbox_id',
+		]);
+		$messagesTable->addIndex(['sent_at'], 'mail_message_sent_idx');
+
+		$recipientsTable = $schema->createTable('mail_recipients');
+		$recipientsTable->addColumn('id', 'integer', [
+			'autoincrement' => true,
+			'notnull' => true,
+			'length' => 20,
+		]);
+		$recipientsTable->addColumn('message_id', 'integer', [
+			'notnull' => true,
+			'length' => 20,
+		]);
+		$recipientsTable->addColumn('type', 'integer', [
+			'notnull' => true,
+			'length' => 2,
+		]);
+		$recipientsTable->addColumn('label', 'string', [
+			'notnull' => false,
+			'length' => 255,
+		]);
+		$recipientsTable->addColumn('email', 'string', [
+			'notnull' => true,
+			'length' => 255,
+		]);
+		$recipientsTable->setPrimaryKey(['id']);
+		$recipientsTable->addIndex(['message_id'], 'mail_recipient_msg_id_idx');
+		$recipientsTable->addIndex(['email'], 'mail_recipient_email_idx');
+
+		$mailboxTable = $schema->getTable('mail_mailboxes');
+		$mailboxTable->addColumn('sync_new_lock', 'integer', [
+			'notnull' => false,
+			'length' => 4,
+		]);
+		$mailboxTable->addColumn('sync_changed_lock', 'integer', [
+			'notnull' => false,
+			'length' => 4,
+		]);
+		$mailboxTable->addColumn('sync_vanished_lock', 'integer', [
+			'notnull' => false,
+			'length' => 4,
+		]);
+		$mailboxTable->addColumn('sync_new_token', 'string', [
+			'notnull' => false,
+			'length' => 255,
+		]);
+		$mailboxTable->addColumn('sync_changed_token', 'string', [
+			'notnull' => false,
+			'length' => 255,
+		]);
+		$mailboxTable->addColumn('sync_vanished_token', 'string', [
+			'notnull' => false,
+			'length' => 255,
+		]);
+
+		return $schema;
+	}
+
+}
diff --git a/lib/Model/IMAPMessage.php b/lib/Model/IMAPMessage.php
index 714342d6a..be30a78ad 100644
--- a/lib/Model/IMAPMessage.php
+++ b/lib/Model/IMAPMessage.php
@@ -48,6 +48,7 @@ use OCP\AppFramework\Db\DoesNotExistException;
 use OCP\Files\File;
 use OCP\Files\SimpleFS\ISimpleFile;
 use function base64_encode;
+use function json_encode;
 use function mb_convert_encoding;
 
 class IMAPMessage implements IMessage, JsonSerializable {
@@ -69,6 +70,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	 * @param Horde_Imap_Client_Data_Fetch|null $fetch
 	 * @param bool $loadHtmlMessage
 	 * @param Html|null $htmlService
+	 *
 	 * @throws DoesNotExistException
 	 */
 	public function __construct($conn,
@@ -145,6 +147,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param array $flags
+	 *
 	 * @throws Exception
 	 */
 	public function setFlags(array $flags) {
@@ -168,6 +171,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param AddressList $from
+	 *
 	 * @throws Exception
 	 */
 	public function setFrom(AddressList $from) {
@@ -183,6 +187,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param AddressList $to
+	 *
 	 * @throws Exception
 	 */
 	public function setTo(AddressList $to) {
@@ -198,6 +203,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param AddressList $cc
+	 *
 	 * @throws Exception
 	 */
 	public function setCC(AddressList $cc) {
@@ -213,6 +219,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param AddressList $bcc
+	 *
 	 * @throws Exception
 	 */
 	public function setBcc(AddressList $bcc) {
@@ -237,6 +244,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param string $subject
+	 *
 	 * @throws Exception
 	 */
 	public function setSubject(string $subject) {
@@ -259,6 +267,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 
 	/**
 	 * @param Horde_Mime_Part $part
+	 *
 	 * @return bool
 	 */
 	private function hasAttachments($part) {
@@ -319,7 +328,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 		} else {
 			if (!is_null($structure->findBody())) {
 				// get the body from the server
-				$partId = (int) $structure->findBody();
+				$partId = (int)$structure->findBody();
 				$this->getPart($structure->getPart($partId), $partId);
 			}
 		}
@@ -328,6 +337,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	/**
 	 * @param Horde_Mime_Part $p
 	 * @param mixed $partNo
+	 *
 	 * @throws DoesNotExistException
 	 */
 	private function getPart(Horde_Mime_Part $p, $partNo) {
@@ -427,6 +437,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	 * @param int $accountId
 	 * @param string $folderId
 	 * @param int $messageId
+	 *
 	 * @return string
 	 */
 	public function getHtmlBody(int $accountId, string $folderId, int $messageId): string {
@@ -457,6 +468,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	/**
 	 * @param Horde_Mime_Part $part
 	 * @param mixed $partNo
+	 *
 	 * @throws DoesNotExistException
 	 */
 	private function handleMultiPartMessage(Horde_Mime_Part $part, $partNo) {
@@ -470,6 +482,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	/**
 	 * @param Horde_Mime_Part $p
 	 * @param mixed $partNo
+	 *
 	 * @throws DoesNotExistException
 	 */
 	private function handleTextMessage(Horde_Mime_Part $p, $partNo) {
@@ -480,6 +493,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	/**
 	 * @param Horde_Mime_Part $p
 	 * @param mixed $partNo
+	 *
 	 * @throws DoesNotExistException
 	 */
 	private function handleHtmlMessage(Horde_Mime_Part $p, $partNo) {
@@ -493,6 +507,7 @@ class IMAPMessage implements IMessage, JsonSerializable {
 	/**
 	 * @param Horde_Mime_Part $p
 	 * @param mixed $partNo
+	 *
 	 * @return string
 	 * @throws DoesNotExistException
 	 * @throws Exception
@@ -582,4 +597,30 @@ class IMAPMessage implements IMessage, JsonSerializable {
 		throw new Exception('not implemented');
 	}
 
+	public function toDbMessage(int $mailboxId): \OCA\Mail\Db\Message {
+		$msg = new \OCA\Mail\Db\Message();
+
+		$msg->setUid($this->getUid());
+		$msg->setMessageId($this->getMessageId());
+		$msg->setMailboxId($mailboxId);
+		$msg->setFrom($this->getFrom());
+		$msg->setTo($this->getTo());
+		$msg->setCc($this->getCc());
+		$msg->setBcc($this->getBcc());
+		$msg->setSubject(mb_substr($this->getSubject(), 0, 255));
+		$msg->setSentAt($this->getSentDate()->getTimestamp());
+
+		$flags = $this->fetch->getFlags();
+		$msg->setFlagAnswered(in_array(Horde_Imap_Client::FLAG_ANSWERED, $flags, true));
+		$msg->setFlagDeleted(in_array(Horde_Imap_Client::FLAG_DELETED, $flags, true));
+		$msg->setFlagDraft(in_array(Horde_Imap_Client::FLAG_DRAFT, $flags, true));
+		$msg->setFlagFlagged(in_array(Horde_Imap_Client::FLAG_FLAGGED, $flags, true));
+		$msg->setFlagSeen(in_array(Horde_Imap_Client::FLAG_SEEN, $flags, true));
+		$msg->setFlagForwarded(in_array(Horde_Imap_Client::FLAG_FORWARDED, $flags, true));
+		$msg->setFlagJunk(in_array(Horde_Imap_Client::FLAG_JUNK, $flags, true));
+		$msg->setFlagNotjunk(in_array(Horde_Imap_Client::FLAG_NOTJUNK, $flags, true));
+
+		return $msg;
+	}
+
 }
diff --git a/lib/Service/AccountService.php b/lib/Service/AccountService.php
index 70472ba9b..e7b7e9ed6 100644
--- a/lib/Service/AccountService.php
+++ b/lib/Service/AccountService.php
@@ -25,10 +25,12 @@ declare(strict_types=1);
 namespace OCA\Mail\Service;
 
 use OCA\Mail\Account;
+use OCA\Mail\BackgroundJob\SyncJob;
 use OCA\Mail\Db\MailAccount;
 use OCA\Mail\Db\MailAccountMapper;
 use OCA\Mail\Exception\ServiceException;
 use OCP\AppFramework\Db\DoesNotExistException;
+use OCP\BackgroundJob\IJobList;
 use function array_map;
 
 class AccountService {
@@ -46,10 +48,15 @@ class AccountService {
 	/** @var AliasesService */
 	private $aliasesService;
 
+	/** @var IJobList */
+	private $jobList;
+
 	public function __construct(MailAccountMapper $mapper,
-								AliasesService $aliasesService) {
+								AliasesService $aliasesService,
+								IJobList $jobList) {
 		$this->mapper = $mapper;
 		$this->aliasesService = $aliasesService;
+		$this->jobList = $jobList;
 	}
 
 	/**
@@ -67,6 +74,14 @@ class AccountService {
 	}
 
 	/**
+	 * @param string $id
+	 * @return Account
+	 */
+	public function findById(int $id): Account {
+		return new Account($this->mapper->findById($id));
+	}
+
+	/**
 	 * @param string $uid
 	 * @param int $accountId
 	 *
@@ -87,16 +102,6 @@ class AccountService {
 	}
 
 	/**
-	 * @param int $id
-	 *
-	 * @return Account
-	 * @throws DoesNotExistException
-	 */
-	public function findById(int $id): Account {
-		return new Account($this->mapper->findById($id));
-	}
-
-	/**
 	 * @param int $accountId
 	 */
 	public function delete(string $currentUserId, int $accountId): void {
@@ -110,7 +115,12 @@ class AccountService {
 	 * @return MailAccount
 	 */
 	public function save(MailAccount $newAccount): MailAccount {
-		return $this->mapper->save($newAccount);
+		$newAccount = $this->mapper->save($newAccount);
+
+		// Insert a background sync job for this account
+		$this->jobList->add(SyncJob::class, ['accountId' => $newAccount->getId()]);
+
+		return $newAccount;
 	}
 
 	public function updateSignature(int $id, string $uid, string $signature = null): void {
diff --git a/lib/Service/AutoCompletion/AddressCollector.php b/lib/Service/AutoCompletion/AddressCollector.php
index 53131e74b..4f22080e4 100644
--- a/lib/Service/AutoCompletion/AddressCollector.php
+++ b/lib/Service/AutoCompletion/AddressCollector.php
@@ -76,7 +76,7 @@ class AddressCollector {
 			$this->logger->debug("<$address> is not a valid RFC822 mail address");
 			return;
 		}
-		if (!$this->mapper->exists($this->userId, $address->getEmail())) {
+		if ($address->getEmail() !== null && !$this->mapper->exists($this->userId, $address->getEmail())) {
 			$this->logger->debug("saving new address <{$address->getEmail()}>");
 
 			$entity = new CollectedAddress();
diff --git a/lib/Service/MailManager.php b/lib/Service/MailManager.php
index 9ccc6866d..4c5359dc2 100644
--- a/lib/Service/MailManager.php
+++ b/lib/Service/MailManager.php
@@ -24,13 +24,11 @@ declare(strict_types=1);
 namespace OCA\Mail\Service;
 
 use Horde_Imap_Client_Exception;
-use Horde_Imap_Client_Exception_Sync;
 use OCA\Mail\Account;
 use OCA\Mail\Contracts\IMailManager;
 use OCA\Mail\Db\Mailbox;
 use OCA\Mail\Db\MailboxMapper;
 use OCA\Mail\Events\BeforeMessageDeletedEvent;
-use OCA\Mail\Exception\ClientException;
 use OCA\Mail\Exception\ServiceException;
 use OCA\Mail\Folder;
 use OCA\Mail\IMAP\FolderMapper;
@@ -38,9 +36,6 @@ use OCA\Mail\IMAP\FolderStats;
 use OCA\Mail\IMAP\IMAPClientFactory;
 use OCA\Mail\IMAP\MailboxSync;
 use OCA\Mail\IMAP\MessageMapper;
-use OCA\Mail\IMAP\Sync\Request;
-use OCA\Mail\IMAP\Sync\Response;
-use OCA\Mail\IMAP\Sync\Synchronizer;
 use OCA\Mail\Model\IMAPMessage;
 use OCP\AppFramework\Db\DoesNotExistException;
 use OCP\EventDispatcher\IEventDispatcher;
@@ -59,9 +54,6 @@ class MailManager implements IMailManager {
 	/** @var FolderMapper */
 	private $folderMapper;
 
-	/** @var Synchronizer */
-	private $synchronizer;
-
 	/** @var MessageMapper */
 	private $messageMapper;
 
@@ -72,14 +64,12 @@ class MailManager implements IMailManager {
 								MailboxMapper $mailboxMapper,
 								MailboxSync $mailboxSync,
 								FolderMapper $folderMapper,
-								Synchronizer $synchronizer,
 								MessageMapper $messageMapper,
 								IEventDispatcher $eventDispatcher) {
 		$this->imapClientFactory = $imapClientFactory;
 		$this->mailboxMapper = $mailboxMapper;
 		$this->mailboxSync = $mailboxSync;
 		$this->folderMapper = $folderMapper;
-		$this->synchronizer = $synchronizer;
 		$this->messageMapper = $messageMapper;
 		$this->eventDispatcher = $eventDispatcher;
 	}
@@ -102,27 +92,6 @@ class MailManager implements IMailManager {
 
 	/**
 	 * @param Account $account
-	 * @param Request $syncRequest
-	 *
-	 * @return Response
-	 *
-	 * @throws ClientException
-	 * @throws ServiceException
-	 */
-	public function syncMessages(Account $account, Request $syncRequest): Response {
-		$client = $this->imapClientFactory->getClient($account);
-
-		try {
-			return $this->synchronizer->sync($client, $syncRequest);
-		} catch (Horde_Imap_Client_Exception $e) {
-			throw new ServiceException("Could not sync messages", 0, $e);
-		} catch (Horde_Imap_Client_Exception_Sync $e) {
-			throw new ClientException("Sync failed because of an invalid sync token or UID validity changed", 0, $e);
-		}
-	}
-
-	/**
-	 * @param Account $account
 	 * @param string $name
 	 *
 	 * @return Folder
diff --git a/lib/Service/MailSearch.php b/lib/Service/MailSearch.php
deleted file mode 100644
index a2729705b..000000000
--- a/lib/Service/MailSearch.php
+++ /dev/null
@@ -1,139 +0,0 @@
-<?php
-/**
- * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
- *
- * @license GNU AGPL version 3 or any later version
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program.  If not, see <http://www.gnu.org/licenses/>.
- */
-
-namespace OCA\Mail\Service;
-
-
-use DateTime;
-use Horde_Imap_Client;
-use Horde_Imap_Client_Exception;
-use Horde_Imap_Client_Exception_NoSupportExtension;
-use Horde_Imap_Client_Fetch_Query;
-use Horde_Imap_Client_Ids;
-use Horde_Imap_Client_Search_Query;
-use Horde_Imap_Client_Socket;
-use OCA\Mail\Account;
-use OCA\Mail\Contracts\IMailSearch;
-use OCA\Mail\Db\MailboxMapper;
-use OCA\Mail\Exception\ServiceException;
-use OCA\Mail\IMAP\IMAPClientFactory;
-use OCA\Mail\IMAP\Search\SearchStrategyFactory;
-use OCA\Mail\Model\IMAPMessage;
-use OCA\Mail\IMAP\Search\SearchFilterStringParser;
-use OCP\AppFramework\Db\DoesNotExistException;
-use OCP\ILogger;
-use function array_keys;
-use function array_reverse;
-use function in_array;
-use function uasort;
-
-class MailSearch implements IMailSearch {
-
-	/** @var IMAPClientFactory */
-	private $clientFactory;
-
-	/** @var SearchStrategyFactory */
-	private $searchStrategyFactory;
-
-	/** @var SearchFilterStringParser */
-	private $filterStringParser;
-
-	/** @var MailboxMapper */
-	private $mailboxMapper;
-
-	/** @var ILogger */
-	private $logger;
-
-	public function __construct(IMAPClientFactory $clientFactory,
-								SearchStrategyFactory $searchStrategyFactory,
-								SearchFilterStringParser $filterStringParser,
-								MailboxMapper $mailboxMapper,
-								ILogger $logger) {
-		$this->clientFactory = $clientFactory;
-		$this->searchStrategyFactory = $searchStrategyFactory;
-		$this->filterStringParser = $filterStringParser;
-		$this->mailboxMapper = $mailboxMapper;
-		$this->logger = $logger;
-	}
-
-	/**
-	 * @param Account $account
-	 * @param string $mailboxName
-	 * @param string|null $filter
-	 * @param string|null $cursor
-	 *
-	 * @return IMAPMessage[]
-	 * @throws ServiceException
-	 */
-	public function findMessages(Account $account, string $mailboxName, ?string $filter, ?int $cursor): array {
-		$client = $this->clientFactory->getClient($account);
-		try {
-			$mailbox = $this->mailboxMapper->find($account, $mailboxName);
-		} catch (DoesNotExistException $e) {
-			throw new ServiceException('Mailbox does not exist', 0, $e);
-		}
-
-		try {
-			$query = $this->filterStringParser->parse($filter);
-
-			// In flagged we don't want anything but flagged messages
-			if ($mailbox->isSpecialUse(Horde_Imap_Client::SPECIALUSE_FLAGGED)) {
-				$query->flag(Horde_Imap_Client::FLAG_FLAGGED);
-			}
-
-			// Don't show deleted messages unless for folders
-			if (!$mailbox->isSpecialUse(Horde_Imap_Client::SPECIALUSE_TRASH)) {
-				$query->flag(Horde_Imap_Client::FLAG_DELETED, false);
-			}
-
-			$ids = $this->searchStrategyFactory
-				->getStrategy($client, $mailbox->getMailbox(), $query, $cursor)
-				->getIds(20);
-		} catch (Horde_Imap_Client_Exception $e) {
-			throw new ServiceException('Could not get message IDs: ' . $e->getMessage(), 0, $e);
-		}
-
-		try {
-			$fetchQuery = new Horde_Imap_Client_Fetch_Query();
-			$fetchQuery->envelope();
-			$fetchQuery->flags();
-			$fetchQuery->size();
-			$fetchQuery->uid();
-			$fetchQuery->imapDate();
-			$fetchQuery->structure();
-
-			$fetchResult = $client->fetch($mailbox->getMailbox(), $fetchQuery, ['ids' => $ids]);
-		} catch (Horde_Imap_Client_Exception $e) {
-			throw new ServiceException('Could not fetch messages', 0, $e);
-		}
-
-		// TODO: do we still need this fix?
-		ob_start(); // fix for Horde warnings
-		$messages = array_map(function (int $messageId) use ($mailbox, $client, $fetchResult) {
-			$header = $fetchResult[$messageId];
-			return new IMAPMessage($client, $mailbox->getMailbox(), $messageId, $header);
-		}, $fetchResult->ids());
-		ob_get_clean();
-
-		return $messages;
-	}
-}
diff --git a/lib/IMAP/Search/SearchFilterStringParser.php b/lib/Service/Search/FilterStringParser.php
index 665700a83..d3779f5e8 100644
--- a/lib/IMAP/Search/SearchFilterStringParser.php
+++ b/lib/Service/Search/FilterStringParser.php
@@ -21,11 +21,9 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-namespace OCA\Mail\IMAP\Search;
+namespace OCA\Mail\Service\Search;
 
-use Horde_Imap_Client_Search_Query;
-
-class SearchFilterStringParser {
+class FilterStringParser {
 
 	private const FLAG_MAP = [
 		'read' => ['SEEN', true],
@@ -33,26 +31,22 @@ class SearchFilterStringParser {
 		'answered' => ['ANSWERED', true],
 	];
 
-	public function parse(?string $filter): Horde_Imap_Client_Search_Query {
-		$query = new Horde_Imap_Client_Search_Query();
+	public function parse(?string $filter): SearchQuery {
+		$query = new SearchQuery();
 		if (empty($filter)) {
 			return $query;
 		}
 		$tokens = explode(' ', $filter);
-		$textTokens = [];
 		foreach ($tokens as $token) {
 			if (!$this->parseFilterToken($query, $token)) {
-				$textTokens[] = $token;
+				$query->addTextToken($token);
 			}
 		}
-		if (count($textTokens)) {
-			$query->text(implode(' ', $textTokens), false);
-		}
 
 		return $query;
 	}
 
-	private function parseFilterToken(Horde_Imap_Client_Search_Query $query, $token): bool {
+	private function parseFilterToken(SearchQuery $query, $token): bool {
 		if (strpos($token, ':') === false) {
 			return false;
 		}
@@ -65,16 +59,24 @@ class SearchFilterStringParser {
 			case 'not':
 				if (array_key_exists($param, self::FLAG_MAP)) {
 					$flag = self::FLAG_MAP[$param];
-					$query->flag($flag[0], $type === 'is' ? $flag[1] : !$flag[1]);
+					$query->addFlag($flag[0], $type === 'is' ? $flag[1] : !$flag[1]);
 					return true;
 				}
 				break;
 			case 'from':
+				$query->addFrom($param);
+				return true;
 			case 'to':
+				$query->addTo($param);
+				return true;
 			case 'cc':
+				$query->addCc($param);
+				return true;
 			case 'bcc':
+				$query->addBcc($param);
+				return true;
 			case 'subject':
-				$query->headerText($type, $param);
+				$query->setSubject($param);
 				return true;
 		}
 
diff --git a/lib/Service/Search/MailSearch.php b/lib/Service/Search/MailSearch.php
new file mode 100644
index 000000000..1927af9aa
--- /dev/null
+++ b/lib/Service/Search/MailSearch.php
@@ -0,0 +1,130 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Service\Search;
+
+use Horde_Imap_Client;
+use OCA\Mail\Account;
+use OCA\Mail\Contracts\IMailSearch;
+use OCA\Mail\Db\Mailbox;
+use OCA\Mail\Db\MailboxMapper;
+use OCA\Mail\Db\Message;
+use OCA\Mail\Db\MessageMapper;
+use OCA\Mail\Exception\ServiceException;
+use OCA\Mail\IMAP\Search\Provider as ImapSearchProvider;
+use OCP\AppFramework\Db\DoesNotExistException;
+use OCP\ILogger;
+
+class MailSearch implements IMailSearch {
+
+	/** @var FilterStringParser */
+	private $filterStringParser;
+
+	/** @var MailboxMapper */
+	private $mailboxMapper;
+
+	/** @var ImapSearchProvider */
+	private $imapSearchProvider;
+
+	/** @var MessageMapper */
+	private $messageMapper;
+
+	/** @var ILogger */
+	private $logger;
+
+	public function __construct(FilterStringParser $filterStringParser,
+								MailboxMapper $mailboxMapper,
+								ImapSearchProvider $imapSearchProvider,
+								MessageMapper $messageMapper,
+								ILogger $logger) {
+		$this->filterStringParser = $filterStringParser;
+		$this->mailboxMapper = $mailboxMapper;
+		$this->imapSearchProvider = $imapSearchProvider;
+		$this->messageMapper = $messageMapper;
+		$this->logger = $logger;
+	}
+
+	/**
+	 * @param Account $account
+	 * @param string $mailboxName
+	 * @param string|null $filter
+	 * @param string|null $cursor
+	 *
+	 * @return Message[]
+	 * @throws ServiceException
+	 */
+	public function findMessages(Account $account,
+								 string $mailboxName,
+								 ?string $filter,
+								 ?int $cursor): array {
+		try {
+			$mailbox = $this->mailboxMapper->find($account, $mailboxName);
+		} catch (DoesNotExistException $e) {
+			throw new ServiceException('Mailbox does not exist', 0, $e);
+		}
+
+		$query = $this->filterStringParser->parse($filter);
+		if ($cursor !== null) {
+			$query->setCursor($cursor);
+		}
+		// In flagged we don't want anything but flagged messages
+		if ($mailbox->isSpecialUse(Horde_Imap_Client::SPECIALUSE_FLAGGED)) {
+			$query->addFlag(Horde_Imap_Client::FLAG_FLAGGED);
+		}
+		// Don't show deleted messages except for trash folders
+		if (!$mailbox->isSpecialUse(Horde_Imap_Client::SPECIALUSE_TRASH)) {
+			$query->addFlag(Horde_Imap_Client::FLAG_DELETED, false);
+		}
+
+		$uids = array_merge(
+			$this->getDbUids($mailbox, $query),
+			$this->getImapUids($account, $mailbox, $query)
+		);
+
+		return $this->messageMapper->findByUids($mailbox, $uids);
+	}
+
+	private function getDbUids(Mailbox $mailbox, SearchQuery $query) {
+		return $this->messageMapper->findUidsByQuery($mailbox, $query);
+	}
+
+	/**
+	 * @param Account $account
+	 * @param SearchQuery $query
+	 * @param Mailbox $mailbox
+	 *
+	 * @throws ServiceException
+	 */
+	private function getImapUids(Account $account, Mailbox $mailbox, SearchQuery $query): array {
+		if (empty($query->getTextTokens())) {
+			return [];
+		}
+
+		return $this->imapSearchProvider->findMatches(
+			$account,
+			$mailbox,
+			$query
+		);
+	}
+
+}
diff --git a/lib/Service/Search/SearchQuery.php b/lib/Service/Search/SearchQuery.php
new file mode 100644
index 000000000..560420d90
--- /dev/null
+++ b/lib/Service/Search/SearchQuery.php
@@ -0,0 +1,143 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Service\Search;
+
+class SearchQuery {
+
+	/** @var int|null */
+	private $cursor;
+
+	/** @var bool[] */
+	private $flags = [];
+
+	/** @var string[] */
+	private $to = [];
+
+	/** @var string[] */
+	private $from = [];
+
+	/** @var string[] */
+	private $cc = [];
+
+	/** @var string[] */
+	private $bcc = [];
+
+	/** @var string|null */
+	private $subject;
+
+	/** @var string[] */
+	private $textTokens = [];
+
+	/**
+	 * @return int|null
+	 */
+	public function getCursor(): ?int {
+		return $this->cursor;
+	}
+
+	/**
+	 * @param int $cursor
+	 */
+	public function setCursor(int $cursor): void {
+		$this->cursor = $cursor;
+	}
+
+	/**
+	 * @return bool[]
+	 */
+	public function getFlags(): array {
+		return $this->flags;
+	}
+
+	public function addFlag(string $flag, bool $value = true): void {
+		$this->flags[$flag] = $value;
+	}
+
+	/**
+	 * @return string[]
+	 */
+	public function getTo(): array {
+		return $this->to;
+	}
+
+	public function addTo(string $to): void {
+		$this->to[] = $to;
+	}
+
+	/**
+	 * @return string[]
+	 */
+	public function getFrom(): array {
+		return $this->from;
+	}
+
+	public function addFrom(string $from): void {
+		$this->from[] = $from;
+	}
+
+	/**
+	 * @return string[]
+	 */
+	public function getCc(): array {
+		return $this->cc;
+	}
+
+	public function addCc(string $cc): void {
+		$this->cc[] = $cc;
+	}
+
+	/**
+	 * @return string[]
+	 */
+	public function getBcc(): array {
+		return $this->bcc;
+	}
+
+	public function addBcc(string $bcc): void {
+		$this->bcc[] = $bcc;
+	}
+
+	/**
+	 * @return string|null
+	 */
+	public function getSubject(): ?string {
+		return $this->subject;
+	}
+
+	public function setSubject(?string $subject): void {
+		$this->subject = $subject;
+	}
+
+	/**
+	 * @return string[]
+	 */
+	public function getTextTokens(): array {
+		return $this->textTokens;
+	}
+
+	public function addTextToken(string $textToken): void {
+		$this->textTokens[] = $textToken;
+	}
+
+}
diff --git a/lib/Service/SyncService.php b/lib/Service/SyncService.php
new file mode 100644
index 000000000..6a084a575
--- /dev/null
+++ b/lib/Service/SyncService.php
@@ -0,0 +1,393 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Service;
+
+use Horde_Imap_Client;
+use Horde_Imap_Client_Exception;
+use Horde_Imap_Client_Exception_Sync;
+use OCA\Mail\Account;
+use OCA\Mail\Db\Mailbox;
+use OCA\Mail\Db\MailboxMapper;
+use OCA\Mail\Db\Message;
+use OCA\Mail\Db\MessageMapper;
+use OCA\Mail\Db\MessageMapper as DatabaseMessageMapper;
+use OCA\Mail\Exception\ConcurrentSyncException;
+use OCA\Mail\Exception\MailboxNotCachedException;
+use OCA\Mail\Exception\ServiceException;
+use OCA\Mail\IMAP\IMAPClientFactory;
+use OCA\Mail\IMAP\MessageMapper as ImapMessageMapper;
+use OCA\Mail\IMAP\Sync\Request;
+use OCA\Mail\IMAP\Sync\Response;
+use OCA\Mail\IMAP\Sync\Synchronizer;
+use OCA\mail\lib\Exception\UidValidityChangedException;
+use OCA\Mail\Model\IMAPMessage;
+use OCA\Mail\Support\PerformanceLogger;
+use OCP\AppFramework\Db\DoesNotExistException;
+use OCP\ILogger;
+use Throwable;
+use function array_chunk;
+use function array_map;
+
+class SyncService {
+
+	/** @var DatabaseMessageMapper */
+	private $dbMapper;
+
+	/** @var IMAPClientFactory */
+	private $clientFactory;
+
+	/** @var ImapMessageMapper */
+	private $imapMapper;
+
+	/** @var MailboxMapper */
+	private $mailboxMapper;
+
+	/** @var DatabaseMessageMapper */
+	private $messageMapper;
+
+	/** @var Synchronizer */
+	private $synchronizer;
+
+	/** @var PerformanceLogger */
+	private $performanceLogger;
+
+	/** @var ILogger */
+	private $logger;
+
+	public function __construct(DatabaseMessageMapper $dbMapper,
+								IMAPClientFactory $clientFactory,
+								ImapMessageMapper $imapMapper,
+								MailboxMapper $mailboxMapper,
+								MessageMapper $messageMapper,
+								Synchronizer $synchronizer,
+								PerformanceLogger $performanceLogger,
+								ILogger $logger) {
+		$this->dbMapper = $dbMapper;
+		$this->clientFactory = $clientFactory;
+		$this->imapMapper = $imapMapper;
+		$this->mailboxMapper = $mailboxMapper;
+		$this->messageMapper = $messageMapper;
+		$this->synchronizer = $synchronizer;
+		$this->performanceLogger = $performanceLogger;
+		$this->logger = $logger;
+	}
+
+	/**
+	 * @throws ServiceException
+	 */
+	public function syncAccount(Account $account,
+								bool $force = false,
+								int $criteria = Horde_Imap_Client::SYNC_NEWMSGSUIDS | Horde_Imap_Client::SYNC_FLAGSUIDS | Horde_Imap_Client::SYNC_VANISHEDUIDS): void {
+		foreach ($this->mailboxMapper->findAll($account) as $mailbox) {
+			$this->sync(
+				$account,
+				$mailbox,
+				$criteria,
+				null,
+				$force
+			);
+		}
+	}
+
+	/**
+	 * @param int[] $knownUids
+	 *
+	 * @throws ServiceException
+	 */
+	public function syncMailbox(Account $account,
+								string $mailbox,
+								int $criteria = Horde_Imap_Client::SYNC_NEWMSGSUIDS | Horde_Imap_Client::SYNC_FLAGSUIDS | Horde_Imap_Client::SYNC_VANISHEDUIDS,
+								array $knownUids = null,
+								bool $partialOnly = true): Response {
+		try {
+			$mb = $this->mailboxMapper->find($account, $mailbox);
+
+			if ($partialOnly && $mb->getSyncNewToken() === null) {
+				throw new MailboxNotCachedException();
+			}
+
+			return $this->sync(
+				$account,
+				$mb,
+				$criteria,
+				$knownUids
+			);
+		} catch (DoesNotExistException $e) {
+			throw new ServiceException('Mailbox to sync does not exist in the database', 0, $e);
+		}
+	}
+
+	/**
+	 * @throws ServiceException
+	 */
+	public function ensurePopulated(Account $account, string $mailbox): void {
+		try {
+			$mb = $this->mailboxMapper->find($account, $mailbox);
+		} catch (DoesNotExistException $e) {
+			throw new ServiceException('Mailbox does not exist', 0, $e);
+		}
+
+		if ($mb->getSyncNewToken() !== null) {
+			return;
+		}
+
+		try {
+			$this->mailboxMapper->lockForNewSync($mb);
+			$this->mailboxMapper->lockForChangeSync($mb);
+			$this->mailboxMapper->lockForVanishedSync($mb);
+
+			$this->runInitialSync($account, $mb);
+		} catch (ConcurrentSyncException $e) {
+			// Fine, then we don't have to do it
+		} finally {
+			$this->mailboxMapper->unlockFromNewSync($mb);
+			$this->mailboxMapper->unlockFromChangedSync($mb);
+			$this->mailboxMapper->unlockFromVanishedSync($mb);
+		}
+	}
+
+	/**
+	 * @param int[] $knownUids
+	 *
+	 * @throws ServiceException
+	 */
+	private function sync(Account $account,
+						  Mailbox $mailbox,
+						  int $criteria,
+						  array $knownUids = null,
+						  bool $force = false): Response {
+		if ($mailbox->getSelectable() === false) {
+			return new Response();
+		}
+
+		try {
+			if ($criteria & Horde_Imap_Client::SYNC_NEWMSGSUIDS) {
+				$this->mailboxMapper->lockForNewSync($mailbox);
+			}
+			if ($criteria & Horde_Imap_Client::SYNC_FLAGSUIDS) {
+				$this->mailboxMapper->lockForChangeSync($mailbox);
+			}
+			if ($criteria & Horde_Imap_Client::SYNC_VANISHEDUIDS) {
+				$this->mailboxMapper->lockForVanishedSync($mailbox);
+			}
+		} catch (ConcurrentSyncException $e) {
+			throw new ServiceException('Another sync is in progress for ' . $mailbox->getId(), 0, $e);
+		}
+
+		try {
+			if ($force
+				|| $mailbox->getSyncNewToken() === null
+				|| $mailbox->getSyncChangedToken() === null
+				|| $mailbox->getSyncVanishedToken() === null) {
+				$response = $this->runInitialSync($account, $mailbox);
+			} else {
+				$response = $this->runPartialSync($account, $mailbox, $criteria, $knownUids);
+			}
+		} catch (Throwable $e) {
+			throw new ServiceException('Sync failed', 0, $e);
+		} finally {
+			if ($criteria & Horde_Imap_Client::SYNC_VANISHEDUIDS) {
+				$this->mailboxMapper->unlockFromVanishedSync($mailbox);
+			}
+			if ($criteria & Horde_Imap_Client::SYNC_FLAGSUIDS) {
+				$this->mailboxMapper->unlockFromChangedSync($mailbox);
+			}
+			if ($criteria & Horde_Imap_Client::SYNC_NEWMSGSUIDS) {
+				$this->mailboxMapper->unlockFromNewSync($mailbox);
+			}
+		}
+
+		return $response;
+	}
+
+	/**
+	 * @throws ServiceException
+	 */
+	private function runInitialSync(Account $account, Mailbox $mailbox): Response {
+		$perf = $this->performanceLogger->start('Initial sync ' . $account->getId() . ':' . $mailbox->getName());
+
+		$client = $this->clientFactory->getClient($account);
+		try {
+			$imapMessages = $this->imapMapper->findAll($client, $mailbox);
+			$perf->step('fetch all messages from IMAP');
+		} catch (Horde_Imap_Client_Exception $e) {
+			throw new ServiceException('Can not get messages from mailbox ' . $mailbox->getName() . ': ' . $e->getMessage(), 0, $e);
+		}
+
+		// The sync token could be reset by a migration, hence there could be existing data
+		$this->dbMapper->deleteAll($mailbox);
+		$perf->step('delete existing messages');
+
+		foreach (array_chunk($imapMessages, 500) as $chunk) {
+			$this->dbMapper->insertBulk(...array_map(function (IMAPMessage $imapMessage) use ($mailbox) {
+				return $imapMessage->toDbMessage($mailbox->getId());
+			}, $chunk));
+		}
+		$perf->step('persist messages in database');
+
+		$mailbox->setSyncNewToken($client->getSyncToken($mailbox->getMailbox()));
+		$mailbox->setSyncChangedToken($client->getSyncToken($mailbox->getMailbox()));
+		$mailbox->setSyncVanishedToken($client->getSyncToken($mailbox->getMailbox()));
+		$this->mailboxMapper->update($mailbox);
+
+		$perf->end();
+
+		// Not returning *all* new messages here as this could exhaust the memory
+		return new Response();
+	}
+
+	/**
+	 * @param int[] $knownUids
+	 *
+	 * @throws ServiceException
+	 */
+	private function runPartialSync(Account $account,
+									Mailbox $mailbox,
+									int $criteria,
+									array $knownUids = null): Response {
+		$perf = $this->performanceLogger->start('partial sync ' . $account->getId() . ':' . $mailbox->getName());
+
+		$client = $this->clientFactory->getClient($account);
+		$uids = $knownUids ?? $this->dbMapper->findAllUids($mailbox);
+		$perf->step('get all known UIDs');
+
+		$response = new Response();
+		if ($criteria & Horde_Imap_Client::SYNC_NEWMSGSUIDS) {
+			try {
+				$response = $response->merge($this->synchronizer->sync(
+					$client,
+					new Request(
+						$mailbox->getMailbox(),
+						$mailbox->getSyncNewToken(),
+						$uids
+					),
+					Horde_Imap_Client::SYNC_NEWMSGSUIDS
+				));
+			} catch (UidValidityChangedException $e) {
+				$this->logger->warning('Mailbox UID validity changed. Performing full sync.');
+
+				return $this->runInitialSync($account, $mailbox);
+			}
+			$perf->step('get new messages via Horde');
+
+			foreach (array_chunk($response->getNewMessages(), 500) as $chunk) {
+				$this->dbMapper->insertBulk(...array_map(function (IMAPMessage $imapMessage) use ($mailbox) {
+					return $imapMessage->toDbMessage($mailbox->getId());
+				}, $chunk));
+			}
+			$perf->step('persist new messages');
+
+			$mailbox->setSyncNewToken($client->getSyncToken($mailbox->getMailbox()));
+		}
+		if ($criteria & Horde_Imap_Client::SYNC_FLAGSUIDS) {
+			try {
+				$response = $response->merge($this->synchronizer->sync(
+					$client,
+					new Request(
+						$mailbox->getMailbox(),
+						$mailbox->getSyncChangedToken(),
+						$uids
+					),
+					Horde_Imap_Client::SYNC_FLAGSUIDS
+				));
+			} catch (UidValidityChangedException $e) {
+				$this->logger->warning('Mailbox UID validity changed. Performing full sync.');
+
+				return $this->runInitialSync($account, $mailbox);
+			}
+			$perf->step('get changed messages via Horde');
+
+			foreach (array_chunk($response->getChangedMessages(), 500) as $chunk) {
+				$this->dbMapper->updateBulk(...array_map(function (IMAPMessage $imapMessage) use ($mailbox) {
+					return $imapMessage->toDbMessage($mailbox->getId());
+				}, $chunk));
+			}
+			$perf->step('persist changed messages');
+
+			// If a list of UIDs was *provided* (as opposed to loaded from the DB,
+			// we can not assume that all changes were detected, hence this is kinda
+			// a silent sync and we don't update the change token until the next full
+			// mailbox sync
+			if ($knownUids === null) {
+				$mailbox->setSyncChangedToken($client->getSyncToken($mailbox->getMailbox()));
+			}
+		}
+		if ($criteria & Horde_Imap_Client::SYNC_VANISHEDUIDS) {
+			try {
+				$response = $response->merge($this->synchronizer->sync(
+					$client,
+					new Request(
+						$mailbox->getMailbox(),
+						$mailbox->getSyncVanishedToken(),
+						$uids
+					),
+					Horde_Imap_Client::SYNC_VANISHEDUIDS
+				));
+			} catch (UidValidityChangedException $e) {
+				$this->logger->warning('Mailbox UID validity changed. Performing full sync.');
+
+				return $this->runInitialSync($account, $mailbox);
+			}
+			$perf->step('get vanished messages via Horde');
+
+			foreach (array_chunk($response->getVanishedMessageUids(), 500) as $chunk) {
+				$this->dbMapper->deleteByUid($mailbox, ...$chunk);
+			}
+			$perf->step('persist new messages');
+
+			$mailbox->setSyncVanishedToken($client->getSyncToken($mailbox->getMailbox()));
+		}
+		$this->mailboxMapper->update($mailbox);
+
+		$response = $response->merge(
+			$this->getDatabaseSyncChanges($mailbox, $uids)
+		);
+
+		$perf->end();
+
+		return $response;
+	}
+
+	private function getDatabaseSyncChanges(Mailbox $mailbox, array $uids): Response {
+		if (empty($uids)) {
+			return new Response();
+		}
+
+		sort($uids, SORT_NUMERIC);
+		$last = end($uids);
+
+		$new = $this->messageMapper->findNew($mailbox, $last);
+		// TODO: $changed = $this->messageMapper->findChanged($mailbox, $uids);
+		$changed = $this->messageMapper->findByUids($mailbox, $uids);
+		$old = array_map(function (Message $msg) {
+			return $msg->getUid();
+		}, $this->messageMapper->findByUids($mailbox, $uids));
+		$vanished = array_filter($uids, function (int $uid) use ($old) {
+			return !in_array($uid, $old, true);
+		});
+
+		return new Response($new, $changed, $vanished);
+	}
+
+}
diff --git a/lib/IMAP/Search/SearchStrategyFactory.php b/lib/Support/PerformanceLogger.php
index 0ad13f8f3..7043fbb36 100644
--- a/lib/IMAP/Search/SearchStrategyFactory.php
+++ b/lib/Support/PerformanceLogger.php
@@ -21,27 +21,30 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
-namespace OCA\Mail\IMAP\Search;
-
-use Horde_Imap_Client_Search_Query;
-use Horde_Imap_Client_Socket;
-
-class SearchStrategyFactory {
-
-	public function getStrategy(Horde_Imap_Client_Socket $client,
-								string $mailbox,
-								Horde_Imap_Client_Search_Query $query,
-								?int $cursor): ISearchStrategy {
-		if (!$client->capability->query('SORT') && 'ALL' === $query->__toString()) {
-			return new FullScanSearchStrategy($client, $mailbox, $cursor);
-		}
-
-		return new ImapSortSearchStrategy(
-			$client,
-			$mailbox,
-			$query,
-			$cursor,
-			new FullScanSearchStrategy($client, $mailbox, $cursor)
+namespace OCA\Mail\Support;
+
+use OCP\AppFramework\Utility\ITimeFactory;
+use OCP\ILogger;
+
+class PerformanceLogger {
+
+	/** @var ITimeFactory */
+	private $timeFactory;
+
+	/** @var ILogger */
+	private $logger;
+
+	public function __construct(ITimeFactory $timeFactory,
+								ILogger $logger) {
+		$this->timeFactory = $timeFactory;
+		$this->logger = $logger;
+	}
+
+	public function start(string $task): PerformanceLoggerTask {
+		return new PerformanceLoggerTask(
+			$task,
+			$this->timeFactory,
+			$this->logger
 		);
 	}
 
diff --git a/lib/Support/PerformanceLoggerTask.php b/lib/Support/PerformanceLoggerTask.php
new file mode 100644
index 000000000..1452f2754
--- /dev/null
+++ b/lib/Support/PerformanceLoggerTask.php
@@ -0,0 +1,72 @@
+<?php declare(strict_types=1);
+
+/**
+ * @copyright 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @author 2019 Christoph Wurst <christoph@winzerhof-wurst.at>
+ *
+ * @license GNU AGPL version 3 or any later version
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+namespace OCA\Mail\Support;
+
+use OCP\AppFramework\Utility\ITimeFactory;
+use OCP\ILogger;
+
+class PerformanceLoggerTask {
+
+	/** @var string */
+	private $task;
+
+	/** @var ITimeFactory */
+	private $timeFactory;
+
+	/** @var ILogger */
+	private $logger;
+
+	/** @var int */
+	private $start;
+
+	/** @var int */
+	private $rel;
+
+	public function __construct(string $task,
+								ITimeFactory $timeFactory,
+								ILogger $logger) {
+		$this->task = $task;
+		$this->timeFactory = $timeFactory;
+		$this->logger = $logger;
+
+		$this->start = $this->rel = $timeFactory->getTime();
+	}
+
+	public function step(string $description): void {
+		$now = $this->timeFactory->getTime();
+		$passed = $now - $this->rel;
+
+		$this->logger->debug($this->task . " - $description took ${passed}s");
+
+		$this->rel = $now;
+	}
+
+	public function end(): void {
+		$now = $this->timeFactory->getTime();
+		$passed = $now - $this->start;
+
+		$this->logger->debug($this->task . " took ${passed}s");
+	}
+
+}