diff --git a/src/Core/Banshee.Core/Banshee.Collection/AlbumInfo.cs b/src/Core/Banshee.Core/Banshee.Collection/AlbumInfo.cs
index 97160df..03d5ff4 100644
--- a/src/Core/Banshee.Core/Banshee.Collection/AlbumInfo.cs
+++ b/src/Core/Banshee.Core/Banshee.Collection/AlbumInfo.cs
@@ -73,6 +73,7 @@ namespace Banshee.Collection
             set { title_sort = value; }
         }
         
+        
         public virtual bool IsCompilation {
             get { return is_compilation; }
             set { is_compilation = value; }
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumInfo.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumInfo.cs
index ddeb2d5..ab3eb4e 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumInfo.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumInfo.cs
@@ -200,6 +200,16 @@ namespace Banshee.Collection.Database
             set { base.TitleSort = value; }
         }
         
+        [DatabaseColumn(Select = false)]
+        internal byte[] TitleSortKey {
+            get { return Hyena.StringUtil.SortKey (TitleSort ?? Title); }
+        }
+
+        [DatabaseColumn(Select = false)]
+        internal string TitleLowered {
+            get { return Hyena.StringUtil.SearchKey (Title); }
+        }
+
         [DatabaseColumn]
         public override string ArtistName {
             get { return base.ArtistName; }
@@ -213,12 +223,12 @@ namespace Banshee.Collection.Database
         }
 
         [DatabaseColumn(Select = false)]
-        protected string TitleLowered {
-            get { return Hyena.StringUtil.SearchKey (Title); }
+        internal byte[] ArtistNameSortKey {
+            get { return Hyena.StringUtil.SortKey (ArtistNameSort ?? ArtistName); }
         }
-
+        
         [DatabaseColumn(Select = false)]
-        protected string ArtistNameLowered {
+        internal string ArtistNameLowered {
             get { return Hyena.StringUtil.SearchKey (ArtistName); }
         }
 
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumListModel.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumListModel.cs
index eca3b5c..76c32b9 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumListModel.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseAlbumListModel.cs
@@ -51,7 +51,7 @@ namespace Banshee.Collection.Database
                         (SELECT CoreTracks.AlbumID FROM CoreTracks, CoreCache{0}
                             WHERE CoreCache.ModelID = {1} AND
                                   CoreCache.ItemId = {2} {3})
-                    ORDER BY CoreAlbums.TitleLowered, CoreAlbums.ArtistNameLowered";
+                    ORDER BY CoreAlbums.TitleSortKey, CoreAlbums.ArtistNameSortKey";
         }
         
         public override string FilterColumn {
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistInfo.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistInfo.cs
index c23cc77..0ffbce6 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistInfo.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistInfo.cs
@@ -134,7 +134,7 @@ namespace Banshee.Collection.Database
         }
 
         [DatabaseColumn(Select = false)]
-        protected string NameLowered {
+        internal string NameLowered {
             get { return Hyena.StringUtil.SearchKey (Name); }
         }
 
@@ -144,6 +144,11 @@ namespace Banshee.Collection.Database
             set { base.NameSort = value; }
         }
 
+        [DatabaseColumn(Select = false)]
+        internal byte[] NameSortKey {
+            get { return Hyena.StringUtil.SortKey (NameSort ?? Name); }
+        }
+        
         [DatabaseColumn("MusicBrainzID")]
         public override string MusicBrainzId {
             get { return base.MusicBrainzId; }
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistListModel.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistListModel.cs
index 7e21b62..697f28c 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistListModel.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseArtistListModel.cs
@@ -50,7 +50,7 @@ namespace Banshee.Collection.Database
                     (SELECT CoreTracks.ArtistID FROM CoreTracks, CoreCache{0}
                         WHERE CoreCache.ModelID = {1} AND
                               CoreCache.ItemID = {2} {3})
-                    ORDER BY NameLowered";
+                    ORDER BY NameSortKey";
         }
         
         public override string FilterColumn {
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackInfo.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackInfo.cs
index 1e0af21..f1abeea 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackInfo.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackInfo.cs
@@ -450,14 +450,19 @@ namespace Banshee.Collection.Database
             set { base.TrackTitle = value; }
         }
         
-        [DatabaseColumn]
+        [DatabaseColumn ("TitleSort")]
         public override string TrackTitleSort {
             get { return base.TrackTitleSort; }
             set { base.TrackTitleSort = value; }
         }
         
+        [DatabaseColumn("TitleSortKey", Select = false)]
+        internal byte[] TrackTitleSortKey {
+            get { return Hyena.StringUtil.SortKey (TrackTitleSort ?? TrackTitle); }
+        }
+        
         [DatabaseColumn(Select = false)]
-        protected string TitleLowered {
+        internal string TitleLowered {
             get { return Hyena.StringUtil.SearchKey (TrackTitle); }
         }
 
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/AlbumInfoTests.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/AlbumInfoTests.cs
new file mode 100644
index 0000000..c560423
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/AlbumInfoTests.cs
@@ -0,0 +1,122 @@
+//
+// AlbumInfoTests.cs
+//
+// Author:
+//   John Millikin <jmillikin@gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#if ENABLE_TESTS
+
+using NUnit.Framework;
+using Banshee.Collection;
+using Banshee.Collection.Database;
+
+namespace Banshee.Collection.Tests
+{
+    [TestFixture]
+    public class AlbumInfoTests
+    {
+        static AlbumInfoTests () {
+            Banshee.Database.BansheeDatabaseSettings.CheckTables = false;
+        }
+
+        protected void AssertTitleSort (string title, string title_sort, byte[] expected)
+        {
+            DatabaseAlbumInfo info = new DatabaseAlbumInfo ();
+            info.Title = title;
+            info.TitleSort = title_sort;
+            Assert.AreEqual (expected, info.TitleSortKey);
+        }
+        
+        protected void AssertTitleLowered (string title, string expected)
+        {
+            DatabaseAlbumInfo info = new DatabaseAlbumInfo ();
+            info.Title = title;
+            Assert.AreEqual (expected, info.TitleLowered);
+        }
+        
+        protected void AssertArtistNameSort (string name, string name_sort, byte[] expected)
+        {
+            DatabaseAlbumInfo info = new DatabaseAlbumInfo ();
+            info.ArtistName = name;
+            info.ArtistNameSort = name_sort;
+            Assert.AreEqual (expected, info.ArtistNameSortKey);
+        }
+        
+        protected void AssertArtistNameLowered (string name, string expected)
+        {
+            DatabaseAlbumInfo info = new DatabaseAlbumInfo ();
+            info.ArtistName = name;
+            Assert.AreEqual (expected, info.ArtistNameLowered);
+        }
+        
+        [Test]
+        public void TestWithoutTitleSortKey ()
+        {
+            AssertTitleSort ("", null, new byte[] {1, 1, 1, 1, 0});
+            AssertTitleSort ("a", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertTitleSort ("A", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestTitleSortKey ()
+        {
+            AssertTitleSort ("Title", "", new byte[] {1, 1, 1, 1, 0});
+            AssertTitleSort ("Title", "a", new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertTitleSort ("Title", "A", new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestTitleLowered ()
+        {
+            AssertTitleLowered ("", "");
+            AssertTitleLowered ("A", "a");
+            AssertTitleLowered ("\u0104", "a");
+        }
+        
+        [Test]
+        public void TestWithoutArtistNameSortKey ()
+        {
+            AssertArtistNameSort ("", null, new byte[] {1, 1, 1, 1, 0});
+            AssertArtistNameSort ("a", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertArtistNameSort ("A", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestArtistNameSortKey ()
+        {
+            AssertArtistNameSort ("Title", "", new byte[] {1, 1, 1, 1, 0});
+            AssertArtistNameSort ("Title", "a", new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertArtistNameSort ("Title", "A", new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestArtistNameLowered ()
+        {
+            AssertArtistNameLowered ("", "");
+            AssertArtistNameLowered ("A", "a");
+            AssertArtistNameLowered ("\u0104", "a");
+        }
+    }
+}
+
+#endif
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/ArtistInfoTests.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/ArtistInfoTests.cs
new file mode 100644
index 0000000..fc81db3
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/ArtistInfoTests.cs
@@ -0,0 +1,84 @@
+//
+// ArtistInfoTests.cs
+//
+// Author:
+//   John Millikin <jmillikin@gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#if ENABLE_TESTS
+
+using NUnit.Framework;
+using Banshee.Collection;
+using Banshee.Collection.Database;
+
+namespace Banshee.Collection.Tests
+{
+    [TestFixture]
+    public class ArtistInfoTests
+    {
+        static ArtistInfoTests () {
+            Banshee.Database.BansheeDatabaseSettings.CheckTables = false;
+        }
+
+        protected void AssertNameSort (string name, string name_sort, byte[] expected)
+        {
+            DatabaseArtistInfo info = new DatabaseArtistInfo ();
+            info.Name = name;
+            info.NameSort = name_sort;
+            Assert.AreEqual (expected, info.NameSortKey);
+        }
+        
+        protected void AssertNameLowered (string name, string expected)
+        {
+            DatabaseArtistInfo info = new DatabaseArtistInfo ();
+            info.Name = name;
+            Assert.AreEqual (expected, info.NameLowered);
+        }
+        
+        [Test]
+        public void TestWithoutNameSortKey ()
+        {
+            AssertNameSort ("", null, new byte[] {1, 1, 1, 1, 0});
+            AssertNameSort ("a", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertNameSort ("A", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestNameSortKey ()
+        {
+            AssertNameSort ("Title", "", new byte[] {1, 1, 1, 1, 0});
+            AssertNameSort ("Title", "a", new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertNameSort ("Title", "A", new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestNameLowered ()
+        {
+            AssertNameLowered ("", "");
+            AssertNameLowered ("A", "a");
+            AssertNameLowered ("\u0104", "a");
+        }
+    }
+}
+
+#endif
+
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/TrackInfoTests.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/TrackInfoTests.cs
new file mode 100644
index 0000000..ff0f07f
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/Tests/TrackInfoTests.cs
@@ -0,0 +1,83 @@
+//
+// TrackInfoTests.cs
+//
+// Author:
+//   John Millikin <jmillikin@gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#if ENABLE_TESTS
+
+using NUnit.Framework;
+using Banshee.Collection;
+using Banshee.Collection.Database;
+
+namespace Banshee.Collection.Tests
+{
+    [TestFixture]
+    public class TrackInfoTests
+    {
+        static TrackInfoTests () {
+            Banshee.Database.BansheeDatabaseSettings.CheckTables = false;
+        }
+
+        protected void AssertTitleSort (string title, string title_sort, byte[] expected)
+        {
+            DatabaseTrackInfo info = new DatabaseTrackInfo ();
+            info.TrackTitle = title;
+            info.TrackTitleSort = title_sort;
+            Assert.AreEqual (expected, info.TrackTitleSortKey);
+        }
+        
+        protected void AssertTitleLowered (string title, string expected)
+        {
+            DatabaseTrackInfo info = new DatabaseTrackInfo ();
+            info.TrackTitle = title;
+            Assert.AreEqual (expected, info.TitleLowered);
+        }
+        
+        [Test]
+        public void TestWithoutTitleSortKey ()
+        {
+            AssertTitleSort ("", null, new byte[] {1, 1, 1, 1, 0});
+            AssertTitleSort ("a", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertTitleSort ("A", null, new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestTitleSortKey ()
+        {
+            AssertTitleSort ("Title", "", new byte[] {1, 1, 1, 1, 0});
+            AssertTitleSort ("Title", "a", new byte[] {14, 2, 1, 1, 1, 1, 0});
+            AssertTitleSort ("Title", "A", new byte[] {14, 2, 1, 1, 1, 1, 0});
+        }
+        
+        [Test]
+        public void TestTitleLowered ()
+        {
+            AssertTitleLowered ("", "");
+            AssertTitleLowered ("A", "a");
+            AssertTitleLowered ("\u0104", "a");
+        }
+    }
+}
+
+#endif
diff --git a/src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs b/src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs
index 8c7739e..1e2f3d4 100644
--- a/src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs
+++ b/src/Core/Banshee.Services/Banshee.Database/BansheeDbConnection.cs
@@ -71,6 +71,9 @@ namespace Banshee.Database
             lock (this) {
                 migrator.Migrate ();
                 migrator = null;
+
+                // Update cached sorting keys
+                SortKeyUpdater.Update ();
             }
         }
 
diff --git a/src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs b/src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs
index 99f6a6a..9144763 100644
--- a/src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs
+++ b/src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs
@@ -52,7 +52,7 @@ namespace Banshee.Database
         // NOTE: Whenever there is a change in ANY of the database schema,
         //       this version MUST be incremented and a migration method
         //       MUST be supplied to match the new version number
-        protected const int CURRENT_VERSION = 24;
+        protected const int CURRENT_VERSION = 25;
         protected const int CURRENT_METADATA_VERSION = 5;
         
 #region Migration Driver
@@ -578,6 +578,20 @@ namespace Banshee.Database
         }
 #endregion
 
+#region Version 25
+
+        [DatabaseVersion (25)]
+        private bool Migrate_25 ()
+        {
+            Execute ("ALTER TABLE CoreArtists ADD COLUMN NameSortKey BLOB");
+            Execute ("ALTER TABLE CoreAlbums ADD COLUMN ArtistNameSortKey BLOB");
+            Execute ("ALTER TABLE CoreAlbums ADD COLUMN TitleSortKey BLOB");
+            Execute ("ALTER TABLE CoreTracks ADD COLUMN TitleSortKey BLOB");
+            return true;
+        }
+        
+#endregion
+
 #pragma warning restore 0169
         
 #region Fresh database setup
@@ -643,6 +657,7 @@ namespace Banshee.Database
                     Title               TEXT,
                     TitleLowered        TEXT,
                     TitleSort           TEXT,
+                    TitleSortKey        BLOB,
                     TrackNumber         INTEGER,
                     TrackCount          INTEGER,
                     Disc                INTEGER,
@@ -687,6 +702,7 @@ namespace Banshee.Database
                     Title               TEXT,
                     TitleLowered        TEXT,
                     TitleSort           TEXT,
+                    TitleSortKey        BLOB,
 
                     ReleaseDate         INTEGER,
                     Duration            INTEGER,
@@ -696,6 +712,7 @@ namespace Banshee.Database
                     ArtistName          TEXT,
                     ArtistNameLowered   TEXT,
                     ArtistNameSort      TEXT,
+                    ArtistNameSortKey   BLOB,
                     
                     Rating              INTEGER
                 )
@@ -711,6 +728,7 @@ namespace Banshee.Database
                     Name                TEXT,
                     NameLowered         TEXT,
                     NameSort            TEXT,
+                    NameSortKey         BLOB,
                     Rating              INTEGER
                 )
             ");
diff --git a/src/Core/Banshee.Services/Banshee.Database/BansheeModelProvider.cs b/src/Core/Banshee.Services/Banshee.Database/BansheeModelProvider.cs
index 3d55489..1d57a35 100644
--- a/src/Core/Banshee.Services/Banshee.Database/BansheeModelProvider.cs
+++ b/src/Core/Banshee.Services/Banshee.Database/BansheeModelProvider.cs
@@ -36,10 +36,16 @@ using Banshee.Configuration;
 
 namespace Banshee.Database
 {
+    // Used for disabling table-checks during testing
+    internal static class BansheeDatabaseSettings
+    {
+        internal static bool CheckTables = true;
+    }
+
     public class BansheeModelProvider<T> : SqliteModelProvider<T> where T : new ()
     {
         public BansheeModelProvider (BansheeDbConnection connection, string table_name)
-            : base (connection, table_name)
+            : base (connection, table_name, BansheeDatabaseSettings.CheckTables)
         {
         }
         
diff --git a/src/Core/Banshee.Services/Banshee.Database/SortKeyUpdater.cs b/src/Core/Banshee.Services/Banshee.Database/SortKeyUpdater.cs
new file mode 100644
index 0000000..ad969a2
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Database/SortKeyUpdater.cs
@@ -0,0 +1,69 @@
+//
+// SortKeyUpdater.cs
+//
+// Author:
+//   John Millikin <jmillikin@gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+using System;
+using System.Globalization;
+using Banshee.Configuration;
+using Banshee.ServiceStack;
+
+namespace Banshee.Database
+{
+    internal class SortKeyUpdater
+    {
+        public static void Update ()
+        {
+            string locale = CultureInfo.CurrentCulture.Name;
+            Hyena.Log.DebugFormat ("locale = {0}, previous = {1}", locale, PreviousLocale);
+            if (locale != PreviousLocale) {
+                ForceUpdate (locale);
+            }
+        }
+        
+        public static void ForceUpdate ()
+        {
+            ForceUpdate (CultureInfo.CurrentCulture.Name);
+        }
+        
+        protected static void ForceUpdate (string new_locale)
+        {
+            BansheeDbConnection db = ServiceManager.DbConnection;
+            db.Execute ("BEGIN");
+            db.Execute (@"UPDATE CoreArtists SET NameSortKey = HYENA_COLLATION_KEY(IFNULL(NameSort,Name))");
+            db.Execute (@"UPDATE CoreAlbums SET TitleSortKey = HYENA_COLLATION_KEY(IFNULL(TitleSort,Title)),
+                                                ArtistNameSortKey = HYENA_COLLATION_KEY(IFNULL(ArtistNameSort, ArtistName))");
+            db.Execute (@"UPDATE CoreTracks SET TitleSortKey = HYENA_COLLATION_KEY(IFNULL(TitleSort,Title))");
+            
+            DatabaseConfigurationClient.Client.Set<string> ("SortKeyLocale", new_locale);
+            db.Execute ("COMMIT");
+        }
+        
+        protected static string PreviousLocale {
+            get {
+                return DatabaseConfigurationClient.Client.Get<string> ("SortKeyLocale", "");
+            }
+        }
+    }
+}
diff --git a/src/Core/Banshee.Services/Banshee.Query/BansheeQuery.cs b/src/Core/Banshee.Services/Banshee.Query/BansheeQuery.cs
index 1b7850b..d47c2cb 100644
--- a/src/Core/Banshee.Services/Banshee.Query/BansheeQuery.cs
+++ b/src/Core/Banshee.Services/Banshee.Query/BansheeQuery.cs
@@ -337,7 +337,7 @@ namespace Banshee.Query
             PlayCountField.ShortLabel   = Catalog.GetString ("Plays");
         }
 
-        private const string default_sort = @"CoreAlbums.ArtistNameLowered ASC, CoreAlbums.TitleLowered ASC, CoreTracks.Disc ASC, CoreTracks.TrackNumber ASC";
+        private const string default_sort = @"CoreAlbums.ArtistNameSortKey ASC, CoreAlbums.TitleSortKey ASC, CoreTracks.Disc ASC, CoreTracks.TrackNumber ASC";
         public static string GetSort (string key)
         {
             return GetSort (key, false);
@@ -353,40 +353,40 @@ namespace Banshee.Query
                 case "track":
                 case "grouping":
                     sort_query = String.Format (@"
-                        CoreAlbums.ArtistNameLowered ASC, 
-                        CoreAlbums.TitleLowered ASC, 
+                        CoreAlbums.ArtistNameSortKey ASC, 
+                        CoreAlbums.TitleSortKey ASC, 
                         CoreTracks.Disc ASC,
                         CoreTracks.TrackNumber {0}", ascDesc); 
                     break;
 
                 case "albumartist":
                     sort_query = String.Format (@"
-                        CoreAlbums.ArtistNameLowered {0}, 
-                        CoreAlbums.TitleLowered ASC, 
+                        CoreAlbums.ArtistNameSortKey {0}, 
+                        CoreAlbums.TitleSortKey ASC, 
                         CoreTracks.Disc ASC,
                         CoreTracks.TrackNumber ASC", ascDesc); 
                     break;
 
                 case "artist":
                     sort_query = String.Format (@"
-                        CoreArtists.NameLowered {0}, 
-                        CoreAlbums.TitleLowered ASC,
+                        CoreArtists.NameSortKey {0}, 
+                        CoreAlbums.TitleSortKey ASC,
                         CoreTracks.Disc ASC,
                         CoreTracks.TrackNumber ASC", ascDesc); 
                     break;
 
                 case "album":
                     sort_query = String.Format (@"
-                        CoreAlbums.TitleLowered {0},
+                        CoreAlbums.TitleSortKey {0},
                         CoreTracks.Disc ASC,
                         CoreTracks.TrackNumber ASC", ascDesc); 
                     break;
 
                 case "title":
                     sort_query = String.Format (@"
-                        CoreTracks.TitleLowered {0},
-                        CoreAlbums.ArtistNameLowered ASC, 
-                        CoreAlbums.TitleLowered ASC", ascDesc); 
+                        CoreTracks.TitleSortKey {0},
+                        CoreAlbums.ArtistNameSortKey ASC, 
+                        CoreAlbums.TitleSortKey ASC", ascDesc); 
                     break;
 
                 case "random":
@@ -395,8 +395,8 @@ namespace Banshee.Query
 
                 case "disc":
                     sort_query = String.Format (@"
-                        CoreAlbums.ArtistNameLowered ASC, 
-                        CoreAlbums.TitleLowered ASC, 
+                        CoreAlbums.ArtistNameSortKey ASC, 
+                        CoreAlbums.TitleSortKey ASC, 
                         CoreTracks.Disc {0},
                         CoreTracks.TrackNumber ASC", ascDesc);
                     break;
@@ -406,18 +406,26 @@ namespace Banshee.Query
                 case "lastplayed":
                 case "lastskipped":
                     column = String.Format ("{0}stamp", key);
-                    goto case "comment";
+                    goto case "year";
                 case "added":
                     column = "dateaddedstamp";
-                    goto case "comment";
+                    goto case "year";
+
+                case "conductor":
+                case "genre":
+                case "composer":
+                case "comment":
+                    sort_query = String.Format (
+                        "HYENA_COLLATION_KEY(CoreTracks.{0}) {1}, {2}",
+                        column ?? key, ascDesc, default_sort
+                    );
+                    break;
 
                 case "year":
                 case "bitrate":
                 case "bpm":
-                case "conductor":
                 case "trackcount":
                 case "disccount":
-                case "genre":
                 case "duration":
                 case "rating":
                 case "playcount":
@@ -428,9 +436,7 @@ namespace Banshee.Query
                 case "dateaddedstamp":
                 case "uri":
                 case "mimetype":
-                case "composer":
                 case "licenseuri":
-                case "comment":
                     sort_query = String.Format (
                         "CoreTracks.{0} {1}, {2}",
                         column ?? key, ascDesc, default_sort
diff --git a/src/Core/Banshee.Services/Makefile.am b/src/Core/Banshee.Services/Makefile.am
index 2fde978..d3d42bd 100644
--- a/src/Core/Banshee.Services/Makefile.am
+++ b/src/Core/Banshee.Services/Makefile.am
@@ -22,6 +22,9 @@ SOURCES =  \
 	Banshee.Collection.Database/IDatabaseTrackModelCache.cs \
 	Banshee.Collection.Database/IDatabaseTrackModelProvider.cs \
 	Banshee.Collection.Database/QueryFilterInfo.cs \
+	Banshee.Collection.Database/Tests/AlbumInfoTests.cs \
+	Banshee.Collection.Database/Tests/ArtistInfoTests.cs \
+	Banshee.Collection.Database/Tests/TrackInfoTests.cs \
 	Banshee.Collection.Indexer/CollectionIndexer.cs \
 	Banshee.Collection.Indexer/CollectionIndexerService.cs \
 	Banshee.Collection.Indexer/ICollectionIndexer.cs \
@@ -48,6 +51,7 @@ SOURCES =  \
 	Banshee.Database/BansheeDbFormatMigrator.cs \
 	Banshee.Database/BansheeModelCache.cs \
 	Banshee.Database/BansheeModelProvider.cs \
+	Banshee.Database/SortKeyUpdater.cs \
 	Banshee.Equalizer/EqualizerManager.cs \
 	Banshee.Equalizer/EqualizerSetting.cs \
 	Banshee.Equalizer/EqualizerSettingEvent.cs \
diff --git a/src/Libraries/Hyena/Hyena.Data.Sqlite/HyenaSqliteCommand.cs b/src/Libraries/Hyena/Hyena.Data.Sqlite/HyenaSqliteCommand.cs
index 23305e5..fb08d65 100644
--- a/src/Libraries/Hyena/Hyena.Data.Sqlite/HyenaSqliteCommand.cs
+++ b/src/Libraries/Hyena/Hyena.Data.Sqlite/HyenaSqliteCommand.cs
@@ -207,7 +207,7 @@ namespace Hyena.Data.Sqlite
             return this;
         }
 
-        private static object SqlifyObject (object o)
+        public static object SqlifyObject (object o)
         {
             if (o is string) {
                 return String.Format ("'{0}'", (o as string).Replace ("'", "''"));
@@ -217,6 +217,9 @@ namespace Hyena.Data.Sqlite
                 return ((bool)o) ? "1" : "0";
             } else if (o == null) {
                 return "NULL";
+            } else if (o is byte[]) {
+                string hex = BitConverter.ToString (o as byte[]).Replace ("-", "");
+                return String.Format ("X'{0}'", hex);
             } else if (o is Array) {
                 StringBuilder sb = new StringBuilder ();
                 bool first = true;
diff --git a/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteModelProvider.cs b/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteModelProvider.cs
index 92f08fc..2e9c09d 100644
--- a/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteModelProvider.cs
+++ b/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteModelProvider.cs
@@ -43,6 +43,7 @@ namespace Hyena.Data.Sqlite
         private DatabaseColumn key;
         private int key_select_column_index;
         private HyenaSqliteConnection connection;
+        private bool check_table = true;
         
         private HyenaSqliteCommand create_command;
         private HyenaSqliteCommand insert_command;
@@ -86,15 +87,20 @@ namespace Hyena.Data.Sqlite
         public HyenaSqliteConnection Connection {
             get { return connection; }
         }
-        
+
         protected SqliteModelProvider (HyenaSqliteConnection connection)
         {
             this.connection = connection;
         }
+
+        public SqliteModelProvider (HyenaSqliteConnection connection, string table_name) : this (connection, table_name, true)
+        {
+        }
         
-        public SqliteModelProvider (HyenaSqliteConnection connection, string table_name) : this (connection)
+        public SqliteModelProvider (HyenaSqliteConnection connection, string table_name, bool checkTable) : this (connection)
         {
             this.table_name = table_name;
+            this.check_table = checkTable;
             Init ();
         }
 
@@ -126,8 +132,10 @@ namespace Hyena.Data.Sqlite
             
             key_select_column_index = select_columns.IndexOf (key);
             
-            CheckVersion ();
-            CheckTable ();
+            if (check_table) {
+                CheckVersion ();
+                CheckTable ();
+            }
         }
         
         protected virtual void CheckVersion ()
diff --git a/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteUtils.cs b/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteUtils.cs
index fffe699..9d89962 100644
--- a/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteUtils.cs
+++ b/src/Libraries/Hyena/Hyena.Data.Sqlite/SqliteUtils.cs
@@ -42,6 +42,8 @@ namespace Hyena.Data.Sqlite
             } else if (type == typeof (int) || type == typeof (long) || type == typeof (bool)
                 || type == typeof (DateTime) || type == typeof (TimeSpan) || type.IsEnum) {
                 return "INTEGER";
+            } else if (type == typeof (byte[])) {
+                return "BLOB";
             } else {
                 throw new Exception (String.Format (
                     "The type {0} cannot be bound to a database column.", type.Name));
@@ -123,11 +125,21 @@ namespace Hyena.Data.Sqlite
             return builder.ToString ();
         }
     }
+        
+    [SqliteFunction (Name = "HYENA_COLLATION_KEY", FuncType = FunctionType.Scalar, Arguments = 1)]
+    internal class CollationKeyFunction : SqliteFunction
+    {
+        public override object Invoke (object[] args)
+        {
+            return Hyena.StringUtil.SortKey (args[0] as string);
+        }
+    }
     
     [SqliteFunction (Name = "HYENA_SEARCH_KEY", FuncType = FunctionType.Scalar, Arguments = 1)]
     internal class SearchKeyFunction : SqliteFunction
     {
-        public override object Invoke (object[] args) {
+        public override object Invoke (object[] args)
+        {
             return Hyena.StringUtil.SearchKey (args[0] as string);
         }
     }
diff --git a/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteCommandTests.cs b/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteCommandTests.cs
index 88b0d92..17a24a4 100644
--- a/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteCommandTests.cs
+++ b/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteCommandTests.cs
@@ -106,6 +106,62 @@ namespace Hyena.Data.Sqlite.Tests
             return tf.GetValue (cmd, null) as string;
         }
     }
+    
+    [TestFixture]
+    public class ObjectToSqlTests
+    {
+        protected void AssertToSql (object o, object expected)
+        {
+            Assert.AreEqual (expected, HyenaSqliteCommand.SqlifyObject (o));
+        }
+        
+        [Test]
+        public void TestNull ()
+        {
+            AssertToSql (null, "NULL");
+        }
+        
+        [Test]
+        public void TestBool ()
+        {
+            AssertToSql (false, "0");
+            AssertToSql (true, "1");
+        }
+        
+        [Test]
+        public void TestString ()
+        {
+            AssertToSql ("", "''");
+            AssertToSql ("test", "'test'");
+            AssertToSql ("te'st", "'te''st'");
+        }
+        
+        [Test]
+        public void TestByteArray ()
+        {
+            // BLOB notation
+            AssertToSql (new byte[] {}, "X''");
+            AssertToSql (new byte[] {0x10, 0x20, 0x30}, "X'102030'");
+        }
+        
+        [Test]
+        public void TestOtherArray ()
+        {
+            AssertToSql (new object[] {}, "");
+            AssertToSql (new object[] {"a"}, "'a'");
+            AssertToSql (new object[] {"a", "b"}, "'a','b'");
+        }
+        
+        [Test]
+        public void TestDateTime ()
+        {
+            // Returned using local time, not UTC
+            AssertToSql (new DateTime (2000, 1, 2), 946792800);
+            
+            // Disregards milliseconds
+            AssertToSql (new DateTime (2000, 1, 2, 10, 9, 8, 7), 946829348);
+        }
+    }
 }
 
 #endif
diff --git a/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteUtilTests.cs b/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteUtilTests.cs
new file mode 100644
index 0000000..03804b9
--- /dev/null
+++ b/src/Libraries/Hyena/Hyena.Data.Sqlite/Tests/SqliteUtilTests.cs
@@ -0,0 +1,85 @@
+//
+// SqliteUtilTests.cs
+//
+// Author:
+//   John Millikin <jmillikin@gmail.com>
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+#if ENABLE_TESTS
+
+using NUnit.Framework;
+using Hyena.Data.Sqlite;
+
+namespace Hyena.Data.Sqlite.Tests
+{
+    [TestFixture]
+    public class CollationKeyTests
+    {
+        protected void CollationKeyTest (object before, object after)
+        {
+            Assert.AreEqual (after, (new CollationKeyFunction ()).Invoke (new object[] {before}));
+        }
+        
+        [Test]
+        public void TestNull ()
+        {
+            CollationKeyTest (null, null);
+            CollationKeyTest (System.DBNull.Value, null);
+        }
+        
+        [Test]
+        public void TestKey ()
+        {
+            // See Hyena.StringUtil.Tests for full tests. This just checks that
+            // the collation function is actually being used.
+            CollationKeyTest ("", new byte[] {1, 1, 1, 1, 0});
+            CollationKeyTest ("\u0104", new byte[] {14, 2, 1, 27, 1, 1, 1, 0});
+        }
+    }
+    
+    [TestFixture]
+    public class SearchKeyTests
+    {
+        protected void SearchKeyTest (object before, object after)
+        {
+            Assert.AreEqual (after, (new SearchKeyFunction ()).Invoke (new object[] {before}));
+        }
+        
+        [Test]
+        public void TestNull ()
+        {
+            SearchKeyTest (null, null);
+            SearchKeyTest (System.DBNull.Value, null);
+        }
+        
+        [Test]
+        public void TestKey ()
+        {
+            // See Hyena.StringUtil.Tests for full tests. This just checks that
+            // the search key function is actually being used.
+            SearchKeyTest ("", "");
+            SearchKeyTest ("\u0104", "a");
+        }
+    }
+}
+
+#endif
diff --git a/src/Libraries/Hyena/Hyena/StringUtil.cs b/src/Libraries/Hyena/Hyena/StringUtil.cs
index 94ef6bc..056b621 100644
--- a/src/Libraries/Hyena/Hyena/StringUtil.cs
+++ b/src/Libraries/Hyena/Hyena/StringUtil.cs
@@ -232,6 +232,13 @@ namespace Hyena
             return new Regex (regex_str, RegexOptions.Compiled);
         }
         
+        private static CompareInfo culture_compare_info = CultureInfo.CurrentCulture.CompareInfo;
+        public static byte[] SortKey (string orig)
+        {
+            if (orig == null) { return null; }
+            return culture_compare_info.GetSortKey (orig, CompareOptions.IgnoreCase).KeyData;
+        }
+        
         public static string EscapeFilename (string input)
         {
             if (input == null)
diff --git a/src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs b/src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs
index 59c731e..cfba158 100644
--- a/src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs
+++ b/src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs
@@ -279,6 +279,27 @@ href=http://lkjdflkjdflkjj>baz foo< /a> bar"));
             AssertProduces ("Greetings! -* 你好?", "Greetings! -_ 你好_");
         }
     }
+    
+    [TestFixture]
+    public class SortKeyTests
+    {
+        private void AssertSortKey (string before, object after)
+        {
+            Assert.AreEqual (after, StringUtil.SortKey (before));
+        }
+        
+        [Test]
+        public void TestNull ()
+        {
+            AssertSortKey (null, null);
+        }
+        
+        [Test]
+        public void TestEmpty ()
+        {
+            AssertSortKey ("", new byte[] {1, 1, 1, 1, 0});
+        }
+    }
 }
 
 #endif
diff --git a/src/Libraries/Hyena/Makefile.am b/src/Libraries/Hyena/Makefile.am
index a48fd53..b670ab8 100644
--- a/src/Libraries/Hyena/Makefile.am
+++ b/src/Libraries/Hyena/Makefile.am
@@ -31,6 +31,7 @@ SOURCES =  \
 	Hyena.Data.Sqlite/Tests/DbBoundType.cs \
 	Hyena.Data.Sqlite/Tests/SqliteCommandTests.cs \
 	Hyena.Data.Sqlite/Tests/SqliteModelProviderTests.cs \
+	Hyena.Data.Sqlite/Tests/SqliteUtilTests.cs \
 	Hyena.Data/ArrayModelCache.cs \
 	Hyena.Data/ColumnDescription.cs \
 	Hyena.Data/DictionaryModelCache.cs \
