MySQL DELETE becomes exceptionaly slow with a large number of rows

When performing a DELETE against a large number of rows in the Prices table, the DELETE becomes progressively slower. If deleting 15,000 rows it runs in about 15 seconds. 20K rows takes 3 or 4 minutes. 40,000 rows takes 15 minutes, 100,000 rows runs for well over an hour.

The below After DELETE trigger updates the Items table with a count of the available price types. This is used when calculating prices to speed up that process in production.

Both tables are InnoDB, and I have updated innodb_buffer_pool_size to 4G, with no effect.

I have verified that all SQL statements are using indexes. There is a PriceType + ItemID index on the Prices table, and ItemID is the primary key for the Items table.

Unfortunately this schema is determined by another application and I can't modify the table structure. I can modify the triggers, indexes, etc. That application cannot be changed to update the counts in the Items table directly.

BEGIN

    DECLARE iPriceTypeA INT;
    DECLARE iPriceTypeB INT;
    DECLARE iPriceTypeC INT;

    SET iPriceTypeA = (SELECT COUNT(*) FROM Prices WHERE PriceType='A' AND ItemID=OLD.ItemID),
        iPriceTypeB = (SELECT COUNT(*) FROM Prices WHERE PriceType='B' AND ItemID=OLD.ItemID),
        iPriceTypeC = (SELECT COUNT(*) FROM Prices WHERE PriceType='C' AND ItemID=OLD.ItemID);

    UPDATE Items 
        SET PriceTypeA = iPriceTypeA,
            PriceTypeB = iPriceTypeB,
            PriceTypeC = iPriceTypeC,
        WHERE ItemID = OLD.ItemID;

END

This doesn't seem like it ought to create a problem, but when deleting 120K rows the server becomes unusable for a couple of hours. Why would this query become essentially exponentially slower with more rows?

Edit: updating with Prices table schema

ItemCode varchar(30)
PriceType char(1)
Method char(1)
Factor decimal(7,2)

Edit:

I am still mystified why this trigger causes the delete to become slower the greater the number of records. As I said if I remove the trigger call the

With InnoDB, deleted rows must be held in case there is a crash or other reason to rollback the action. This is costly, and may get more costly with larger counts, as you are seeing.

Plan A: Delete in smaller chunks and COMMIT after each chunk. (Similarly, chunking should be applied to Updates.)

Plan B, C, D, ... See more tips

If no WHERE

No WHERE? It would be much better to create a new table, then use RENAME TABLE to atomically swap the new one into place. And finish with DROP TABLE. No down time; no costly delete.

Query rewrite

If you are running 5.7, there is a new feature there which lets you "rewrite" queries to accommodate various kinds of nasties. More discussion. You could probably turn a delete without a where into DROP and CREATE. (This is not quite as good as the previous suggestion.)

StackExchange Database Administrators Q#147103, answer score: 16