diff --git a/src/engine/databasesanitizer.h b/src/engine/databasesanitizer.h
--- a/src/engine/databasesanitizer.h
+++ b/src/engine/databasesanitizer.h
@@ -72,6 +72,12 @@
     */
     void printDevices(const QVector<qint64>& deviceIds, const ItemAccessFilters accessFilter = IgnoreNone);
 
+    void removeStaleEntries(const QVector<qint64>& deviceIds,
+        const DatabaseSanitizer::ItemAccessFilters accessFilter = DatabaseSanitizer::IgnoreNone,
+        const bool dryRun = false,
+        const QSharedPointer<QRegularExpression>& urlFilter = nullptr
+    );
+
 private:
     DatabaseSanitizer(const DatabaseSanitizer& rhs) = delete;
     DatabaseSanitizerImpl* m_pimpl;
diff --git a/src/engine/databasesanitizer.cpp b/src/engine/databasesanitizer.cpp
--- a/src/engine/databasesanitizer.cpp
+++ b/src/engine/databasesanitizer.cpp
@@ -44,9 +44,10 @@
     struct FileInfo {
         quint32 deviceId = 0;
         quint32 inode = 0;
-        QString url = QString();
+        quint64 id = 0;
+        bool isSymLink = false;
         bool accessible = true;
-    };
+        QString url = QString();    };
 
     void printProgress(QTextStream& out, uint& cur, const uint max, const uint step) const
     {
@@ -102,11 +103,15 @@
 
             const quint32* arr = reinterpret_cast<quint32*>(&id);
             const auto url = docUrlDb.get(id);
+            const auto fileInfo = QFileInfo(url);
             FileInfo info;
+            info.id = id;
             info.deviceId = arr[0];
             info.inode = arr[1];
             info.url = url;
-            info.accessible = !url.isEmpty() && QFileInfo::exists(url);
+            info.accessible = !url.isEmpty() && fileInfo.exists();
+            info.isSymLink = fileInfo.isSymLink();
+
             if ((!includeIds.isEmpty() && !includeIds.contains(info.deviceId))
                 || (!excludeIds.isEmpty() && excludeIds.contains(info.deviceId))
                 || (info.accessible && (accessFilter & DatabaseSanitizer::IgnoreAvailable))
@@ -169,13 +174,28 @@
             ) {
                 devinfo.items = usedDevices.values(dev).count();
                 result.append(devinfo);
+            } else {
+                qDebug() << "Ignoring device" << devinfo.id;
             }
         }
+        return result;
+    }
 
+    struct IdInfo {
+        quint32 deviceId = 0;
+        quint32 inode = 0;
+        quint64 id = 0;
+    };
+
+    IdInfo toIdInfo(quint64 id) {
+        IdInfo result;
+        const quint32* arr = reinterpret_cast<quint32*>(&id);
+        result.deviceId = arr[0];
+        result.inode = arr[1];
+        result.id = id;
         return result;
     }
 
-private:
     Transaction* m_transaction;
 };
 }
@@ -272,3 +292,39 @@
 
     err << i18n("Found %1 matching in %2 devices", matchCount, usedDevices.count()) << endl;
 }
+
+void DatabaseSanitizer::removeStaleEntries(const QVector<qint64>& deviceIds,
+    const DatabaseSanitizer::ItemAccessFilters accessFilter,
+    const bool dryRun,
+    const QSharedPointer<QRegularExpression>& urlFilter)
+{
+    auto infos = m_pimpl->createList(deviceIds, IgnoreAvailable, urlFilter);
+    auto devices = m_pimpl->createDeviceList(infos, accessFilter);
+    QVector<quint32> deviceIdFilter;
+    for (const auto& devInfo: devices) {
+        deviceIdFilter.append(devInfo.id);
+    }
+    const auto sep = QLatin1Char(' ');
+    QTextStream out(stdout);
+    QTextStream err(stderr);
+    for (const auto& info: infos) {
+        if (deviceIdFilter.contains(info.deviceId)) {
+            if (info.isSymLink) {
+                out << i18n("IgnoredSymbolicLink:");
+            } else {
+                m_pimpl->m_transaction->removeDocument(info.id);
+                out << i18n("Removing:");
+            }
+            out << sep << QStringLiteral("device: %1").arg(info.deviceId)
+            << sep << QStringLiteral("inode: %1").arg(info.inode)
+            << sep << QStringLiteral("url: %1").arg(info.url)
+            << endl;
+        }
+    }
+    if (dryRun) {
+        m_pimpl->m_transaction->abort();
+    } else {
+        m_pimpl->m_transaction->commit();
+    }
+    err << i18n("Removed %1 items", infos.count()) << endl;
+}
diff --git a/src/engine/documenturldb.h b/src/engine/documenturldb.h
--- a/src/engine/documenturldb.h
+++ b/src/engine/documenturldb.h
@@ -112,7 +112,8 @@
         quint64 id = path.parentId;
         while (id) {
             auto path = idFilenameDb.get(id);
-            Q_ASSERT(!path.name.isEmpty());
+            // FIXME: Prevents database cleaning
+            // Q_ASSERT(!path.name.isEmpty());
 
             QVector<quint64> subDocs = idTreeDb.get(path.parentId);
             if (subDocs.size() == 1 && shouldDeleteFolder(id)) {
diff --git a/src/tools/baloodb/main.cpp b/src/tools/baloodb/main.cpp
--- a/src/tools/baloodb/main.cpp
+++ b/src/tools/baloodb/main.cpp
@@ -53,18 +53,18 @@
         i18n("integer"),
         0
     },
-    QCommandLineOption{
-        QStringList{QStringLiteral("D"), QStringLiteral("dry-run")},
-        i18n("Print results of a prune operation, but do not change anything."
-        "\nOnly applies to \"%1\" command", QStringLiteral("prune"))
-    },
     QCommandLineOption{
         QStringList{QStringLiteral("m"), QStringLiteral("missing-only")},
         i18n("List only inaccessible entries.\nOnly applies to \"%1\"", QStringLiteral("list"))
     },
     QCommandLineOption{
         QStringList{QStringLiteral("u"), QStringLiteral("mounted-only")},
         i18n("Act only on item on mounted devices")
+    },
+    QCommandLineOption{
+        QStringList{QStringLiteral("D"), QStringLiteral("dry-run")},
+        i18n("Print results of a prune operation, but do not change anything."
+        "\nOnly applies to \"%1\" command", QStringLiteral("prune"))
     }
 };
 
@@ -80,6 +80,12 @@
             QStringLiteral("device-id")
         }
     },
+    Command{
+        QStringLiteral("devices"),
+        i18n("List devices"),
+        QStringList{},
+        QStringList{QStringLiteral("missing-only"), QStringLiteral("mounted-only")}
+    },
     /*TODO:
     Command{
         QStringLiteral("check"),
@@ -89,25 +95,19 @@
         QStringList{}
     },
     */
-    /*TODO:
     Command{
-        QStringLiteral("prune"),
+        QStringLiteral("clean"),
         i18n("Remove stale database entries"),
         QStringList{
             QStringLiteral("pattern")
         },
         QStringList{
             QStringLiteral("dry-run"),
-            QStringLiteral("device-id")
+            QStringLiteral("device-id"),
+            QStringLiteral("mounted-only")
         }
-    },
-    */
-    Command{
-        QStringLiteral("devices"),
-        i18n("List devices"),
-        QStringList{},
-        QStringList{QStringLiteral("missing-only"), QStringLiteral("mounted-only")}
     }
+
 };
 
 const QStringList allowedCommands()
@@ -147,7 +147,7 @@
             .arg(argumentStr);
 
         const QString str = QStringLiteral("%1 %2")
-            .arg(commandStr, -48)
+            .arg(commandStr, -58)
             .arg(c.description);
 
         allowedcommands.append(str);
@@ -248,8 +248,14 @@
         san.printDevices(deviceIds, accessFilter);
 
     } else if (command == QStringLiteral("clean")) {
-        /* TODO: add prune command */
-        parser.showHelp(1);
+        auto dbMode = Database::ReadWriteDatabase;
+        if (!db->open(dbMode)) {
+            err << i18n("Baloo Index could not be opened") << endl;
+            return 1;
+        }
+        DatabaseSanitizer san(db, Transaction::ReadWrite);
+        err << i18n("Removing stale database contents...") << endl;
+        san.removeStaleEntries(deviceIds, accessFilter, parser.isSet(QStringLiteral("dry-run")), urlFilter);
 
     } else if (command == QStringLiteral("check")) {
         parser.showHelp(1);