Deleting/updating is slow on single numeric row key tables

A user reported that deleting 50M rows on the simplest of tables, (id INT, text STRING, PRIMARY KEY (id)), doesn't complete.

It reproduces locally and I was able to see that we're deleting 1.4 rows / ms which is awful considering that everything is cached.

Todd found that we're spending most of our time decoding big blocks of bit-shuffled keys. Intuitively he though that having a composite row key would perform better and indeed adding a column set to 0 in front makes it 10x faster.