How do you increase MySQL performance using current server resources?
Here is your original query from the slow log

SELECT COUNT(inboxentities.id) FROM inboxentities
WHERE (active=true)
AND (deleted=false)
AND ((to_ = '44219ca4-a657-4909-b30d-a7ba0ed8e4b0'))
AND (notification=true);


The most effective way to index for a query like this is to generate an index that covers as many of the fields in the WHERE clause as possible. An index produced with that concept in mind is called a covering index.

Look at the WHERE clause


'active' is true or false (2 values). An index of just that field is lopsided.
'deleted' is true or false (2 values). An index of just that field is lopsided.
'notification' is true or false (2 values). An index of just that field is lopsided.
'to_' is a values worth indexing and narrowing down.


Although you have idx_complex defined, there is one more element to the query causing the idx_complex index not be used: the COUNT(inboxentities.id) clause.

You are counting something in a table. The index has no reference point to the table except to_. The MySQL Query Optmizer would choose idx_to, the simplest index. To force the MySQL Query Optimizer to choose the covering index you want (idx_complex) just COUNT from the index rather than the table. My suggestion is to change the query slightly:

SELECT COUNT(to_) FROM inboxentities
WHERE (active=true)
AND (deleted=false)
AND ((to_ = '44219ca4-a657-4909-b30d-a7ba0ed8e4b0'))
AND (notification=true);


Give it a Try !!!

UPDATE 2011-08-15 15:16 EDT

Some have seen marginal-to-significant performance increases scaling up by changing my.cnf to satisfy Storage Engine performance needs.

You need to set the MyISAM Key Cache and InnoDB Buffer Pool.

This will recommend the right size MyISAM Key Cache for your given data set:

SELECT CONCAT(ROUND(KBS/POWER(1024,
IF(PowerOf1024&lt;0,0,IF(PowerOf1024&gt;3,0,PowerOf1024)))+0.4999),
SUBSTR(' KMG',IF(PowerOf1024&lt;0,0,
IF(PowerOf1024&gt;3,0,PowerOf1024))+1,1))
recommended_key_buffer_size FROM
(SELECT LEAST(POWER(2,32),KBS1) KBS
FROM (SELECT SUM(index_length) KBS1
FROM information_schema.tables
WHERE engine='MyISAM' AND
table_schema NOT IN ('information_schema','mysql')) AA ) A,
(SELECT 2 PowerOf1024) B;


This will recommend the right size InnoDB Buffer Pool for your given data set

SELECT CONCAT(ROUND(KBS/POWER(1024,
IF(PowerOf1024&lt;0,0,IF(PowerOf1024&gt;3,0,PowerOf1024)))+0.49999),
SUBSTR(' KMG',IF(PowerOf1024&lt;0,0,
IF(PowerOf1024&gt;3,0,PowerOf1024))+1,1)) recommended_innodb_buffer_pool_size
FROM (SELECT SUM(data_length+index_length) KBS FROM information_schema.tables
WHERE engine='InnoDB') A,
(SELECT 2 PowerOf1024) B;


BTW 


(SELECT 0 PowerOf1024) generates the answer in Bytes
(SELECT 1 PowerOf1024) generates the answer in KB
(SELECT 2 PowerOf1024) generates the answer in MB
(SELECT 3 PowerOf1024) generates the answer in GB


If you go beyond this, email me.

Once you have these settings, make sure that the combined number for recommended_key_buffer_size and recommended_innodb_buffer_pool_size does not exceed 75% of installed RAM.

UPDATE 2011-08-15 15:35 EDT

You may want to run mysqltuner.pl on the server to let it tell you how to tweek memory useage for DB Connections. Settings governing memory usage per DB Connection include


join_buffer_size
sort_buffer_size
read_buffer_size


These are usually multiplied by max_connections.

You can get mysqltuner.pl get downloading it as follows from the Linux command line:

wget mysqltuner.pl


The output from it is something like this:

$ perl mysqltuner.pl

 &gt;&gt;  MySQLTuner 1.2.0 - Major Hayden &lt;major@mhtx.net&gt;
 &gt;&gt;  Bug reports, feature requests, and downloads at http://mysqltuner.com/
 &gt;&gt;  Run with '--help' for additional options and output filtering
Please enter your MySQL administrative login: username
Please enter your MySQL administrative password: (password hidden)

-------- General Statistics --------------------------------------------------
[--] Skipped version check for MySQLTuner script
[OK] Currently running supported MySQL version 5.1.47-community-log
[OK] Operating on 64-bit architecture

-------- Storage Engine Statistics -------------------------------------------
[--] Status: +Archive -BDB -Federated +InnoDB -ISAM -NDBCluster
[--] Data in MyISAM tables: 7G (Tables: 6)
[--] Data in InnoDB tables: 2G (Tables: 382)
[!!] Total fragmented tables: 84

-------- Security Recommendations  -------------------------------------------
[OK] All database users have passwords assigned

-------- Performance Metrics -------------------------------------------------
[--] Up for: 12d 20h 24m 6s (54M q [49.462 qps], 555K conn, TX: 287B, RX: 95B)
[--] Reads / Writes: 62% / 38%
[--] Total buffers: 9.3G global + 48.2M per thread (1250 max threads)
[!!] Maximum possible memory usage: 68.2G (291% of installed RAM)
[OK] Slow queries: 0% (647/54M)
[OK] Highest usage of available connections: 5% (69/1250)
[OK] Key buffer size / total MyISAM indexes: 256.0M/19.4M
[OK] Key buffer hit rate: 100.0% (51M cached / 10 reads)
[OK] Query cache efficiency: 89.3% (47M cached / 52M selects)
[!!] Query cache prunes per day: 60670
[OK] Sorts requiring temporary tables: 0% (239 temp sorts / 1M sorts)
[!!] Temporary tables created on disk: 47% (1M on disk / 2M total)
[OK] Thread cache hit rate: 99% (103 created / 555K connections)
[OK] Table cache hit rate: 21% (722 open / 3K opened)
[OK] Open file limit used: 0% (70/32K)
[OK] Table locks acquired immediately: 99% (12M immediate / 12M locks)
[OK] InnoDB data size / buffer pool: 2.4G/8.0G

-------- Recommendations -----------------------------------------------------
General recommendations:
    Run OPTIMIZE TABLE to defragment tables for better performance
    Reduce your overall MySQL memory footprint for system stability
    Increasing the query_cache size over 128M may reduce performance
    When making adjustments, make tmp_table_size/max_heap_table_size equal
    Reduce your SELECT DISTINCT queries without LIMIT clauses
Variables to adjust:
  *** MySQL's maximum memory usage is dangerously high ***
  *** Add RAM before increasing MySQL buffer variables ***
    query_cache_size (&gt; 1G) [see warning above]
    tmp_table_size (&gt; 32M)
    max_heap_table_size (&gt; 32M)