Ok, as nobody could answer my post it ist probably not specific enough. I'll try to clarify what my findings are.

If the server is slow I run a quite simple query and it takes about 4 seconds.
When I look at the tables, they look OK, no data_free, all Indices have correct cardinality. Anyhow if I optimize the table the query takes about 4 ms.

I post the definition and the Variables (I hope I chose the correct ones) as it seems to be a must-do in this forum, perhaps anybody could find anything. We have only MyIsam-Tables.

The main question is, what happens in the background, that the query is that fast again.

thanks for your time.

+---------------------------------+------------------------- -------------------------------------------+
| Variable_name | Value |
+---------------------------------+------------------------- -------------------------------------------+
| join_buffer_size | 2093056 |
| key_buffer_size | 536870912 |
| key_cache_age_threshold | 300 |
| key_cache_block_size | 1024 |
| key_cache_division_limit | 100 |
| max_allowed_packet | 1048576 |
| max_binlog_cache_size | 4294967295 |
| max_binlog_size | 1073741824 |
| max_connect_errors | 10 |
| max_connections | 120 |
| max_delayed_threads | 20 |
| max_error_count | 64 |
| max_heap_table_size | 134217728 |
| max_insert_delayed_threads | 20 |
| max_join_size | 18446744073709551615 |
| max_length_for_sort_data | 1024 |
| max_prepared_stmt_count | 16382 |
| max_relay_log_size | 0 |
| max_seeks_for_key | 4294967295 |
| max_sort_length | 1024 |
| max_sp_recursion_depth | 0 |
| max_tmp_tables | 32 |
| max_user_connections | 0 |
| max_write_lock_count | 4294967295 |
| multi_range_count | 256 |
| myisam_data_pointer_size | 6 |
| myisam_max_sort_file_size | 2147483647 |
| myisam_recover_options | OFF |
| myisam_repair_threads | 1 |
| myisam_sort_buffer_size | 8388608 |
| myisam_stats_method | nulls_unequal |
| open_files_limit | 1130 |
| optimizer_prune_level | 1 |
| optimizer_search_depth | 62 |
| preload_buffer_size | 32768 |
| query_alloc_block_size | 8192 |
| query_cache_limit | 2097152 |
| query_cache_min_res_unit | 40960 |
| query_cache_size | 536870912 |
| query_cache_type | ON |
| query_cache_wlock_invalidate | OFF |
| query_prealloc_size | 8192 |
| range_alloc_block_size | 2048 |
| read_buffer_size | 2093056 |
| read_only | OFF |
| read_rnd_buffer_size | 262144 |
| sort_buffer_size | 2097144 |
| table_cache | 500 |
| table_lock_wait_timeout | 50 |
| table_type | MyISAM |
| thread_cache_size | 16 |
| thread_stack | 196608 |
| tmp_table_size | 268435456 |
| version | 5.0.37-log |
| version_comment | MySQL Community Server (GPL) |
| version_compile_machine | i686 |
| version_compile_os | apple-darwin8.5.1 |
| wait_timeout | 28800 |
+---------------------------------+------------------------- -------------------------------------------+

Status Variables:

mysql> SHOW STATUS;
+-----------------------------------+-----------+
| Variable_name | Value |
+-----------------------------------+-----------+
| Connections | 141410 |
| Created_tmp_disk_tables | 0 |
| Created_tmp_files | 5 |
| Created_tmp_tables | 2 |
| Handler_read_rnd_next | 228 |
| Handler_write | 358 |
| Key_blocks_not_flushed | 0 |
| Key_blocks_unused | 443957 |
| Key_blocks_used | 62677 |
| Key_read_requests | 42233864 |
| Key_reads | 188714 |
| Key_write_requests | 123667 |
| Key_writes | 116333 |
| Last_query_cost | 10.499000 |
| Max_used_connections | 15 |
| Open_files | 211 |
| Open_streams | 0 |
| Open_tables | 118 |
| Opened_tables | 0 |
| Qcache_free_blocks | 49279 |
| Qcache_free_memory | 415283128 |
| Qcache_hits | 41696874 |
| Qcache_inserts | 1547461 |
| Qcache_lowmem_prunes | 52564 |
| Qcache_not_cached | 9414 |
| Qcache_queries_in_cache | 100825 |
| Qcache_total_blocks | 250999 |
| Questions | 43947663 |
| Select_full_join | 0 |
| Select_full_range_join | 0 |
| Select_range | 0 |
| Select_range_check | 0 |
| Select_scan | 2 |
| Slow_launch_threads | 0 |
| Slow_queries | 0 |
| Sort_merge_passes | 0 |
| Sort_range | 0 |
| Sort_rows | 0 |
| Sort_scan | 0 |
| Table_locks_immediate | 2327597 |
| Table_locks_waited | 289 |
| Threads_cached | 13 |
| Threads_connected | 2 |
| Threads_created | 15 |
| Threads_running | 1 |
| Uptime | 165225 |
| Uptime_since_flush_status | 165225 |
+-----------------------------------+-----------+

The Explain for the query:

mysql> EXPLAIN SELECT id FROM user WHERE un like '%somebody%';
+----+-------------+-------+------+---------------+------+-- -------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+-- -------+------+-------+-------------+
| 1 | SIMPLE | user | ALL | NULL | NULL | NULL | NULL | 10794 | Using where |
+----+-------------+-------+------+---------------+------+-- -------+------+-------+-------------+

(I am aware that this is not very good, but that's not my point at the moment)

mysql> SHOW TABLE STATUS LIKE 'user';
+------+--------+---------+------------+-------+------------ ----+-------------+-----------------+--------------+-------- ---+----------------+---------------------+----------------- ----+---------------------+-----------------+----------+---- ------------+-----------------------------+
| Name | Engine | Version | Row_format | Rows | Avg_row_length | Data_length | Max_data_length | Index_length | Data_free | Auto_increment | Create_time | Update_time | Check_time | Collation | Checksum | Create_options | Comment |
+------+--------+---------+------------+-------+------------ ----+-------------+-----------------+--------------+-------- ---+----------------+---------------------+----------------- ----+---------------------+-----------------+----------+---- ------------+-----------------------------+
| user | MyISAM | 10 | Dynamic | 10794 | 126 | 1369436 | 281474976710655 | 866304 | 0 | 11473 | 2009-02-10 13:14:51 | 2009-02-18 08:35:43 | 2009-02-18 07:53:26 | utf8_unicode_ci | NULL | | Users and global privileges |
+------+--------+---------+------------+-------+------------ ----+-------------+-----------------+--------------+-------- ---+----------------+---------------------+----------------- ----+---------------------+-----------------+----------+---- ------------+-----------------------------+

If you're using MyISAM, put a fulltext index on `un`.

You could get away with a regular index if you changed your query to WHERE un like 'somebody%' (remove the wildcard from the front).