Optimizing DELETE Query on MySQL MEMORY Table

Question

I run a large forum which maintains a MySQL database for backend data storage. The 'session' table tracks logged in users & guests. It is currently about 100k records, so not really that large. However, this session table is showing up in the slow query log when we trim old records:

# Time: 120719 10:05:11
# User@Host: xxx[xxx] @  [10.x.x.x]
# Thread_id: 369051896  Schema: forumdb  Last_errno: 0  Killed: 0
# Query_time: 8.352811  Lock_time: 0.000028  Rows_sent: 0  Rows_examined: 19635  Rows_affected: 19635  Rows_read: 0
# Bytes_sent: 13  Tmp_tables: 0  Tmp_disk_tables: 0  Tmp_table_sizes: 0
SET timestamp=1342710311;
DELETE FROM session
    WHERE lastactivity < 1342709401;

I've confirmed there is a BTREE index on the lastactivity table:

mysql> SHOW INDEX FROM session FROM forumdb;
+---------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name     | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| session |          0 | PRIMARY      |            1 | sessionhash  | NULL      |       78941 |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | userid       |            1 | userid       | NULL      |       26313 |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | idhash       |            1 | idhash       | NULL      |        8771 |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | userid_2     |            1 | userid       | NULL      |        NULL |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | userid_2     |            2 | lastactivity | NULL      |       39470 |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | userid_3     |            1 | userid       | NULL      |        NULL |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | userid_3     |            2 | host         | NULL      |       39470 |     NULL | NULL   |      | HASH       |         |               |
| session |          1 | lastactivity |            1 | lastactivity | A         |        NULL |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+--------------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
8 rows in set (0.00 sec)

I'm curious why the delete query is taking so long with so few records.

It should be noted that this table is utilized very heavily with so many users online at the same time. We have some heavy hardware sitting behind it.

Any ideas on what I can do to speed up this process? It appears to be locking the table so that I see high load across my cluster when this delete function is taking place.

Query cache is turned off (we use memcache). Here is relevant portions of my.cnf:

table_open_cache=8242
table_definition_cache=600
open_files_limit=65535
binlog_cache_size=6M
sort_buffer_size=8M
key_buffer_size=5G
myisam_sort_buffer_size=256M
join_buffer_size=3M
thread_cache_size=1000
thread_concurrency=16
ft_min_word_len=3
tmp_table_size=512M
max_allowed_packet=128M
max_heap_table_size=512M
read_rnd_buffer_size=1M
skip-external-locking

query_cache_limit=1M
query_cache_size= 32M
query_cache_type = 0

Finally, here is some more info on the table:

FIXED:

After changing table over to InnoDB (at 17:15 in the chart below) I am seeing much better performance and no more DELETE in the slowlogs for this table. The whole cluster is seeing better performance since making this change. Thank you.