What does "Table does not support optimize, doing recreate + analyze instead" mean?

That's really an informational message.

Likely, you're doing OPTIMIZE on an InnoDB table (table using the InnoDB storage engine, rather than the MyISAM storage engine).

InnoDB doesn't support the OPTIMIZE the way MyISAM does. It does something different. It creates an empty table, and copies all of the rows from the existing table into it, and essentially deletes the old table and renames the new table, and then runs an ANALYZE to gather statistics. That's the closest that InnoDB can get to doing an OPTIMIZE.

The message you are getting is basically MySQL server repeating what the InnoDB storage engine told MySQL server:

Table does not support optimize is the InnoDB storage engine saying...

"I (the InnoDB storage engine) don't do an OPTIMIZE operation like my friend (the MyISAM storage engine) does."

"doing recreate + analyze instead" is the InnoDB storage engine saying...

"I have decided to perform a different set of operations which will achieve an equivalent result."

OPTIMIZE TABLE works fine with InnoDB engine according to the official support article : http://dev.mysql.com/doc/refman/5.5/en/optimize-table.html

You'll notice that optimize InnoDB tables will rebuild table structure and update index statistics (something like ALTER TABLE).

Keep in mind that this message could be an informational mention only and the very important information is the status of your query : just OK !

mysql> OPTIMIZE TABLE foo;
+----------+----------+----------+-------------------------------------------------------------------+
| Table    | Op       | Msg_type | Msg_text                                                          |
+----------+----------+----------+-------------------------------------------------------------------+
| test.foo | optimize | note     | Table does not support optimize, doing recreate + analyze instead |
| test.foo | optimize | status   | OK                                                                |
+----------+----------+----------+-------------------------------------------------------------------+

Best option is create new table with same properties

CREATE TABLE <NEW.NAME.TABLE> LIKE <TABLE.CRASHED>;
INSERT INTO <NEW.NAME.TABLE> SELECT * FROM <TABLE.CRASHED>;

Rename NEW.NAME.TABLE and TABLE.CRASH

RENAME TABLE <TABLE.CRASHED> TO <TABLE.CRASHED.BACKUP>;
RENAME TABLE <NEW.NAME.TABLE> TO <TABLE.CRASHED>;

After work well, delete

DROP TABLE <TABLE.CRASHED.BACKUP>;