The total number of locks exceeds the lock table sizeは、大量にデータを削除する場合等に発生する可能性があります。
見ての通り、ロックするメモリー不足です。
なお、InooDBは行ロック、MyIsamはテーブルロックのようです。
メモリーの拡張
一般的にはinnodb_buffer_pool_sizeを拡張することで対応可能です。
しかしinnodb_buffer_pool_sizeは動的システム変数ではありません。
そのため一応再起動が必要です。
また、innodb_buffer_pool_sizeは、
グローバル変数であるため、
（セッション変数は接続数に応じて消費されるので大量の割り当てはさけるべきです）
データベースサーバーの場合、総メモリーの７～８割を当ててもよいとされています。
その割には、初期値が8M（8388608）しかありません・・・。
さらに、innodb_log_file_sizeも合わせて変更しなければ、パフォーマンスの向上が望めず、
別の問題を引き起こすかもしれません。
（innodb_log_file_size×innodb_log_files_in_group > innodb_buffer_pool_size）
こうした点を踏まえてinnodb_buffer_pool_sizeを変更する分には、これが直接的かつ唯一の対応策となるでしょう。
SQLの見直し
先程も述べたように、innoDBは行ロックを行います。
SQL Serverのようなロックエスカレーション（あまりに多い行ロックはメモリー効率が悪くなるのでテーブルロックになる）
もありません。
そのため、削除の場合は単純に条件を十分に絞り込むことや、削除を複数に分けることでこのエラーを回避することも可能です。
もちろん、こうした対応ができない場合はinnodb_buffer_pool_sizeの変更が必用となります。
削除や更新系のSQLの条件で、explainを先頭につければ実行計画をみて条件を検討できます。
delete from table where id < 100; を explain select * from table where id < 100;
検討してみてはいかがでしょうか。
