diff --git a/src/file/fileindexscheduler.cpp b/src/file/fileindexscheduler.cpp
index dcb6426d..3ae5efc3 100644
--- a/src/file/fileindexscheduler.cpp
+++ b/src/file/fileindexscheduler.cpp
@@ -1,215 +1,245 @@
 /*
  * Copyright (C) 2015  Vishesh Handa <vhanda@kde.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library 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
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */
 
 #include "fileindexscheduler.h"
 
 #include "firstrunindexer.h"
 #include "newfileindexer.h"
 #include "modifiedfileindexer.h"
 #include "xattrindexer.h"
 #include "filecontentindexer.h"
 #include "filecontentindexerprovider.h"
 #include "unindexedfileindexer.h"
+#include "indexcleaner.h"
 
 #include "fileindexerconfig.h"
 
 #include <memory>
 
 #include <QTimer>
 #include <QDebug>
 #include <QDBusConnection>
 
 using namespace Baloo;
 
 FileIndexScheduler::FileIndexScheduler(Database* db, FileIndexerConfig* config, QObject* parent)
     : QObject(parent)
     , m_db(db)
     , m_config(config)
     , m_provider(db)
     , m_contentIndexer(nullptr)
     , m_indexerState(Idle)
     , m_timeEstimator(config, this)
     , m_checkUnindexedFiles(false)
+    , m_checkStaleIndexEntries(false)
 {
     Q_ASSERT(db);
     Q_ASSERT(config);
 
     m_threadPool.setMaxThreadCount(1);
 
     connect(&m_powerMonitor, &PowerStateMonitor::powerManagementStatusChanged,
             this, &FileIndexScheduler::powerManagementStatusChanged);
 
     m_contentIndexer = new FileContentIndexer(m_config, &m_provider, this);
     m_contentIndexer->setAutoDelete(false);
     connect(m_contentIndexer, &FileContentIndexer::done, this,
             &FileIndexScheduler::scheduleIndexing);
     connect(m_contentIndexer, &FileContentIndexer::newBatchTime, &m_timeEstimator,
             &TimeEstimator::handleNewBatchTime);
 
     QDBusConnection::sessionBus().registerObject(QStringLiteral("/scheduler"),
                                                  this, QDBusConnection::ExportScriptableContents);
 }
 
 FileIndexScheduler::~FileIndexScheduler()
 {
     m_threadPool.waitForDone(0); // wait 0 msecs
 }
 
 void FileIndexScheduler::scheduleIndexing()
 {
     if (m_threadPool.activeThreadCount() || m_indexerState == Suspended) {
         return;
     }
 
     if (m_config->isInitialRun()) {
         auto runnable = new FirstRunIndexer(m_db, m_config, m_config->includeFolders());
         connect(runnable, &FirstRunIndexer::done, this, &FileIndexScheduler::scheduleIndexing);
 
         m_threadPool.start(runnable);
         m_indexerState = FirstRun;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
 
     if (!m_newFiles.isEmpty()) {
         auto runnable = new NewFileIndexer(m_db, m_config, m_newFiles);
         connect(runnable, &NewFileIndexer::done, this, &FileIndexScheduler::scheduleIndexing);
 
         m_threadPool.start(runnable);
         m_newFiles.clear();
         m_indexerState = NewFiles;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
 
     if (!m_modifiedFiles.isEmpty()) {
         auto runnable = new ModifiedFileIndexer(m_db, m_config, m_modifiedFiles);
         connect(runnable, &ModifiedFileIndexer::done, this, &FileIndexScheduler::scheduleIndexing);
 
         m_threadPool.start(runnable);
         m_modifiedFiles.clear();
         m_indexerState = ModifiedFiles;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
 
     if (!m_xattrFiles.isEmpty()) {
         auto runnable = new XAttrIndexer(m_db, m_config, m_xattrFiles);
         connect(runnable, &XAttrIndexer::done, this, &FileIndexScheduler::scheduleIndexing);
 
         m_threadPool.start(runnable);
         m_xattrFiles.clear();
         m_indexerState = XAttrFiles;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
 
     if (m_provider.size() && !m_powerMonitor.isOnBattery()) {
         m_threadPool.start(m_contentIndexer);
         m_indexerState = ContentIndexing;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
 
     if (m_checkUnindexedFiles) {
         auto runnable = new UnindexedFileIndexer(m_db, m_config);
         connect(runnable, &UnindexedFileIndexer::done, this, &FileIndexScheduler::scheduleIndexing);
 
         m_threadPool.start(runnable);
         m_checkUnindexedFiles = false;
         m_indexerState = UnindexedFileCheck;
         Q_EMIT stateChanged(m_indexerState);
         return;
     }
+
+    if (m_checkStaleIndexEntries) {
+        auto runnable = new IndexCleaner(m_db, m_config);
+        connect(runnable, &IndexCleaner::done, this, &FileIndexScheduler::scheduleIndexing);
+
+        m_threadPool.start(runnable);
+        m_checkStaleIndexEntries = false;
+        m_indexerState = StaleIndexEntriesClean;
+        Q_EMIT stateChanged(m_indexerState);
+        return;
+    }
     m_indexerState = Idle;
     Q_EMIT stateChanged(m_indexerState);
 }
 
 static void removeStartsWith(QStringList& list, const QString& dir)
 {
     const auto tail = std::remove_if(list.begin(), list.end(),
         [&dir](const QString& file) {
             return file.startsWith(dir);
         });
     list.erase(tail, list.end());
 }
 
 void FileIndexScheduler::handleFileRemoved(const QString& file)
 {
     if (!file.endsWith(QLatin1Char('/'))) {
         m_newFiles.removeOne(file);
         m_modifiedFiles.removeOne(file);
         m_xattrFiles.removeOne(file);
     }
     else {
         removeStartsWith(m_newFiles, file);
         removeStartsWith(m_modifiedFiles, file);
         removeStartsWith(m_xattrFiles, file);
     }
 }
 
 void FileIndexScheduler::powerManagementStatusChanged(bool isOnBattery)
 {
     qDebug() << "Power state changed";
     if (isOnBattery && m_indexerState == ContentIndexing) {
         qDebug() << "On battery stopping content indexer";
         m_contentIndexer->quit();
         //TODO: Maybe we can add a special state for suspended due to being on battery.
         m_indexerState = Idle;
         Q_EMIT stateChanged(m_indexerState);
     } else if (!isOnBattery) {
         scheduleIndexing();
     }
 }
 
 void FileIndexScheduler::setSuspend(bool suspend)
 {
     if (suspend) {
         qDebug() << "Suspending";
         if (m_indexerState == ContentIndexing) {
             m_contentIndexer->quit();
         }
         m_indexerState = Suspended;
         Q_EMIT stateChanged(m_indexerState);
     } else {
         qDebug() << "Resuming";
         m_indexerState = Idle;
         // No need to emit here we'll be emitting in scheduling
         scheduleIndexing();
     }
 }
 
 uint FileIndexScheduler::getRemainingTime()
 {
     if (m_indexerState != ContentIndexing) {
         return 0;
     }
     return m_timeEstimator.calculateTimeLeft(m_provider.size());
 }
 
+void FileIndexScheduler::scheduleCheckUnindexedFiles()
+{
+    m_checkUnindexedFiles = true;
+}
+
 void FileIndexScheduler::checkUnindexedFiles()
 {
     m_checkUnindexedFiles = true;
     scheduleIndexing();
 }
 
+void FileIndexScheduler::scheduleCheckStaleIndexEntries()
+{
+    m_checkStaleIndexEntries = true;
+}
+
+void FileIndexScheduler::checkStaleIndexEntries()
+{
+    m_checkStaleIndexEntries = true;
+    scheduleIndexing();
+}
+
+
 uint FileIndexScheduler::getBatchSize()
 {
     return m_config->maxUncomittedFiles();
 }
diff --git a/src/file/fileindexscheduler.h b/src/file/fileindexscheduler.h
index 6ba84855..e981e0c3 100644
--- a/src/file/fileindexscheduler.h
+++ b/src/file/fileindexscheduler.h
@@ -1,113 +1,117 @@
 /*
  * Copyright (C) 2015  Vishesh Handa <vhanda@kde.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library 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
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */
 
 #ifndef BALOO_FILEINDEXSCHEDULER_H
 #define BALOO_FILEINDEXSCHEDULER_H
 
 #include <QObject>
 #include <QStringList>
 #include <QThreadPool>
 #include <QTimer>
 
 #include "filecontentindexerprovider.h"
 #include "powerstatemonitor.h"
 #include "indexerstate.h"
 #include "timeestimator.h"
 
 namespace Baloo {
 
 class Database;
 class FileIndexerConfig;
 class FileContentIndexer;
 
 class FileIndexScheduler : public QObject
 {
     Q_OBJECT
     Q_CLASSINFO("D-Bus Interface", "org.kde.baloo.scheduler")
 
     Q_PROPERTY(int state READ state NOTIFY stateChanged)
 public:
     FileIndexScheduler(Database* db, FileIndexerConfig* config, QObject* parent = nullptr);
     ~FileIndexScheduler() override;
     int state() const { return m_indexerState; }
 
 Q_SIGNALS:
     Q_SCRIPTABLE void stateChanged(int state);
 
 public Q_SLOTS:
     void indexNewFile(const QString& file) {
         if (!m_newFiles.contains(file)) {
             m_newFiles << file;
             QTimer::singleShot(0, this, &FileIndexScheduler::scheduleIndexing);
         }
     }
 
     void indexModifiedFile(const QString& file) {
         if (!m_modifiedFiles.contains(file)) {
             m_modifiedFiles << file;
             QTimer::singleShot(0, this, &FileIndexScheduler::scheduleIndexing);
         }
     }
 
     void indexXAttrFile(const QString& file) {
         if (!m_xattrFiles.contains(file)) {
             m_xattrFiles << file;
             QTimer::singleShot(0, this, &FileIndexScheduler::scheduleIndexing);
         }
     }
 
     void handleFileRemoved(const QString& file);
 
     void scheduleIndexing();
+    void scheduleCheckUnindexedFiles();
+    void scheduleCheckStaleIndexEntries();
 
     Q_SCRIPTABLE void suspend() { setSuspend(true); }
     Q_SCRIPTABLE void resume() { setSuspend(false); }
     Q_SCRIPTABLE uint getRemainingTime();
     Q_SCRIPTABLE void checkUnindexedFiles();
+    Q_SCRIPTABLE void checkStaleIndexEntries();
     Q_SCRIPTABLE uint getBatchSize();
 
 private Q_SLOTS:
     void powerManagementStatusChanged(bool isOnBattery);
 
 private:
     void setSuspend(bool suspend);
 
     Database* m_db;
     FileIndexerConfig* m_config;
 
     QStringList m_newFiles;
     QStringList m_modifiedFiles;
     QStringList m_xattrFiles;
 
     QThreadPool m_threadPool;
 
     FileContentIndexerProvider m_provider;
     FileContentIndexer* m_contentIndexer;
 
     PowerStateMonitor m_powerMonitor;
 
     IndexerState m_indexerState;
     TimeEstimator m_timeEstimator;
 
     bool m_checkUnindexedFiles;
+    bool m_checkStaleIndexEntries;
 };
 
 }
 
 #endif // BALOO_FILEINDEXSCHEDULER_H
diff --git a/src/file/indexerstate.h b/src/file/indexerstate.h
index 4729bdce..74e973d4 100644
--- a/src/file/indexerstate.h
+++ b/src/file/indexerstate.h
@@ -1,78 +1,82 @@
 /*
  * This file is part of the KDE Baloo Project
  * Copyright (C) 2015  Pinak Ahuja <pinak.ahuja@gmail.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) version 3, or any
  * later version accepted by the membership of KDE e.V. (or its
  * successor approved by the membership of KDE e.V.), which shall
  * act as a proxy defined in Section 6 of version 3 of the license.
  *
  * This library 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
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
  *
  */
 #ifndef BALOO_INDEXER_STATE_H
 #define BALOO_INDEXER_STATE_H
 
 #include <QString>
 #include <KLocalizedString>
 
 namespace Baloo {
 enum IndexerState {
         Idle,
         Suspended,
         FirstRun,
         NewFiles,
         ModifiedFiles,
         XAttrFiles,
         ContentIndexing,
-        UnindexedFileCheck
+        UnindexedFileCheck,
+        StaleIndexEntriesClean
 };
 
 inline QString stateString(IndexerState state)
 {
     QString status = i18n("Unknown");
     switch (state) {
     case Idle:
         status = i18n("Idle");
         break;
     case Suspended:
         status =  i18n("Suspended");
         break;
     case FirstRun:
         status =  i18n("Initial Indexing");
         break;
     case NewFiles:
         status = i18n("Indexing new files");
         break;
     case ModifiedFiles:
         status = i18n("Indexing modified files");
         break;
     case XAttrFiles:
         status = i18n("Indexing Extended Attributes");
         break;
     case ContentIndexing:
         status = i18n("Indexing file content");
         break;
     case UnindexedFileCheck:
         status = i18n("Checking for unindexed files");
+        break;
+    case StaleIndexEntriesClean:
+        status = i18n("Checking for stale index entries");
     }
     return status;
 }
 
 //TODO: check for implicit conversion
 inline QString stateString(int state)
 {
     return stateString(static_cast<IndexerState>(state));
 }
 
 }
 #endif //BALOO_INDEXER_STATE_H
diff --git a/src/file/mainhub.cpp b/src/file/mainhub.cpp
index 693af8f2..8b210fc0 100644
--- a/src/file/mainhub.cpp
+++ b/src/file/mainhub.cpp
@@ -1,72 +1,76 @@
 /*
  * Copyright (C) 2015  Vishesh Handa <vhanda@kde.org>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library 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
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */
 
 #include "mainhub.h"
 #include "fileindexerconfig.h"
 #include "mainadaptor.h"
 
 #include <QDBusConnection>
 #include <QCoreApplication>
 #include <QTimer>
 
 using namespace Baloo;
 
 MainHub::MainHub(Database* db, FileIndexerConfig* config)
     : m_db(db)
     , m_config(config)
     , m_fileWatcher(db, config, this)
     , m_fileIndexScheduler(db, config, this)
 {
     Q_ASSERT(db);
     Q_ASSERT(config);
 
     connect(&m_fileWatcher, &FileWatch::indexNewFile, &m_fileIndexScheduler, &FileIndexScheduler::indexNewFile);
     connect(&m_fileWatcher, &FileWatch::indexModifiedFile, &m_fileIndexScheduler, &FileIndexScheduler::indexModifiedFile);
     connect(&m_fileWatcher, &FileWatch::indexXAttr, &m_fileIndexScheduler, &FileIndexScheduler::indexXAttrFile);
     connect(&m_fileWatcher, &FileWatch::fileRemoved, &m_fileIndexScheduler, &FileIndexScheduler::handleFileRemoved);
 
     connect(&m_fileWatcher, &FileWatch::installedWatches, &m_fileIndexScheduler, &FileIndexScheduler::scheduleIndexing);
 
     MainAdaptor* main = new MainAdaptor(this);
     Q_UNUSED(main)
 
     QDBusConnection bus = QDBusConnection::sessionBus();
     bus.registerObject(QStringLiteral("/"), this, QDBusConnection::ExportAllSlots |
                         QDBusConnection::ExportScriptableSignals | QDBusConnection::ExportAdaptors);
 
+    if (!m_config->isInitialRun()) {
+        m_fileIndexScheduler.scheduleCheckUnindexedFiles();
+        m_fileIndexScheduler.scheduleCheckStaleIndexEntries();
+    }
     QTimer::singleShot(0, &m_fileWatcher, &FileWatch::watchIndexedFolders);
 }
 
 void MainHub::quit() const
 {
     QCoreApplication::instance()->quit();
 }
 
 void MainHub::updateConfig()
 {
     m_config->forceConfigUpdate();
     // FIXME!!
     //m_fileIndexer.updateConfig();
     m_fileWatcher.updateIndexedFoldersWatches();
 }
 
 void MainHub::registerBalooWatcher(const QString &service)
 {
     m_fileWatcher.registerBalooWatcher(service);
 }