Index: src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs
===================================================================
--- src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs	(revision 4862)
+++ src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs	(working copy)
@@ -37,12 +37,17 @@
 
 using Banshee.Base;
 using Banshee.ServiceStack;
+using Banshee.Configuration;
 
 namespace Banshee.Database
 {
     public sealed class BansheeDbConnection : HyenaSqliteConnection, IInitializeService, IRequiredService
     {
         private BansheeDbFormatMigrator migrator;
+        private DatabaseConfigurationClient configuration;
+        public DatabaseConfigurationClient Configuration {
+            get { return configuration; }
+        }
 
         public BansheeDbConnection () : base (DatabaseFile)
         {
@@ -59,6 +64,7 @@
             Log.DebugFormat ("Opened SQLite connection to {0}", DatabaseFile);
 
             migrator = new BansheeDbFormatMigrator (this);
+            configuration = new DatabaseConfigurationClient (this);
             
             if (Banshee.Base.ApplicationContext.CommandLine.Contains ("debug-sql")) {
                 Hyena.Data.Sqlite.HyenaSqliteCommand.LogAll = true;
@@ -70,8 +76,47 @@
             lock (this) {
                 migrator.Migrate ();
                 migrator = null;
+                
+                try {
+                    OptimizeDatabase ();
+                } catch (Exception e) {
+                    Log.Exception ("Error determining if ANALYZE is necessary", e);
+                }
             }
         }
+        
+        private void OptimizeDatabase ()
+        {
+            using (IDataReader reader = Query (@"
+                SELECT COUNT(*), ifnull (
+                    (SELECT Value 
+                            FROM CoreConfiguration 
+                            WHERE Key = 'Database.AnalyzeThreshold'
+                            LIMIT 1), 
+                        100)
+                    FROM CoreTracks 
+                    WHERE DateUpdatedStamp > ifnull (
+                        (SELECT Value 
+                            FROM CoreConfiguration 
+                            WHERE Key = 'Database.LastAnalyzed'
+                            LIMIT 1), 
+                        0)")) {
+                reader.Read ();
+                long updated_since_last_analyze = (long)Convert.ChangeType (reader[0], typeof (long));
+                long analyze_threshold = (long)Convert.ChangeType (reader[1], typeof (long));
+                
+                if (updated_since_last_analyze > analyze_threshold) {
+                    Log.DebugFormat ("Running ANALYZE against database to improve performance " + 
+                        "(rows updated: {0}, threshold: {1})", updated_since_last_analyze, analyze_threshold);
+                    Execute ("ANALYZE");
+                    configuration.Set<long> ("Database", "AnalyzeThreshold", analyze_threshold);
+                    configuration.Set<long> ("Database", "LastAnalyzed",  DateTimeUtil.FromDateTime (DateTime.Now));
+                } else {
+                    Log.DebugFormat ("Skipping ANALYZE (rows updated: {0}, threshold: {1})", 
+                        updated_since_last_analyze, analyze_threshold);
+                }
+            }
+        }
 
         public BansheeDbFormatMigrator Migrator {
             get { lock (this) { return migrator; } }
Index: src/Core/Banshee.Services/Banshee.Configuration/DatabaseConfigurationClient.cs
===================================================================
--- src/Core/Banshee.Services/Banshee.Configuration/DatabaseConfigurationClient.cs	(revision 4862)
+++ src/Core/Banshee.Services/Banshee.Configuration/DatabaseConfigurationClient.cs	(working copy)
@@ -37,11 +37,8 @@
 {
     public class DatabaseConfigurationClient : IConfigurationClient
     {
-        private static DatabaseConfigurationClient instance = new DatabaseConfigurationClient (
-            ServiceManager.DbConnection);
-        
         public static DatabaseConfigurationClient Client {
-            get { return instance; }
+            get { return ServiceManager.DbConnection.Configuration; }
         }
         
         private readonly BansheeDbConnection connection;
