The SQL query in /usr/share/perl5/Mail/SpamAssassin/BayesStore/SQL.pm line
243 calculates the expire delta, but in a way that can't use
an index:

   my $sql = "SELECT count(*)
                FROM bayes_token
               WHERE id = ?
                AND (? - atime) > ?";



Changing this as follows would make it so it can utilize the index, thus
examining less rows (which could be locked). Mysql can't look up $newest_atime -
atime from the index because that value is made up, so it uses the "id" portion
of the index on (id, atime)... if it doesn't have to calculate the value for
$newest_atime + $something for every row and only needs to check the index then
it would be much faster.

Index: lib/Mail/SpamAssassin/BayesStore/SQL.pm
===================================================================
--- lib/Mail/SpamAssassin/BayesStore/SQL.pm     (revision 579950)
+++ lib/Mail/SpamAssassin/BayesStore/SQL.pm     (working copy)
@@ -241,7 +241,7 @@
   my $sql = "SELECT count(*)
                FROM bayes_token
               WHERE id = ?
-                AND (? - atime) > ?";
+                AND atime < ?";

   my $sth = $self->{_dbh}->prepare_cached($sql);

@@ -251,7 +251,7 @@
   }

   for (my $i = 1; $i <= $max_expire_mult; $i<<=1) {
-    my $rc = $sth->execute($self->{_userid}, $newest_atime, $start * $i);
+    my $rc = $sth->execute($self->{_userid}, $newest_atime - $start * $i);

     unless ($rc) {
       dbg("bayes: calculate_expire_delta: SQL error:
".$self->{_dbh}->errstr());

Thanks to Mark Martinec and Nils for the patch and analysis.