Why are references to wp_postmeta so slow?

Fetching of attributes in WordPress (using MySQL) seems to be slower than necessary.

(This is a self-answered question, so proceed to my answer.)

The standard schema for wp_postmeta provides poor indexes. This leads to performance problems.

By changing the schema to this, most references to meta data will be faster:

CREATE TABLE wp_postmeta (
    post_id …,
    meta_key …,
    meta_value …,
    PRIMARY KEY(post_id, meta_key),
    INDEX(meta_key)
) ENGINE=InnoDB;

Notes:

The current AUTO_INCREMENT column is a waste of space, and slows down queries because it is the PRIMARY KEY, thereby eschewing the "natural" "composite" PK of (post_id, meta_key).
InnoDB further boosts the performance of that PK due to "clustering". (I hope you are not still using MyISAM!)
If you are using MySQL 5.6 (Or MariaDB 10.0 or 10.1), change meta_key from VARCHAR(255), not VARCHAR(191). (We can discuss the reasons, and workarounds, in a separate question, if 191 is not sufficient.)
INDEX(meta_key) is optional, but needed if you want to "find posts that have a particular key".
Caveat: These changes will speed up many uses of postmeta, but not all. I don't think it will slow down any use cases. (Please provide such queries if you encounter them. It could be a caching issue, not ar real degradation.)

If you would like to present your CREATE TABLE, I can provide an ALTER to convert it to this.

If you need the ability to have multiple meta keys with the same key name for one post, then use this solution. It is nearly as good as the above suggestion.

    meta_id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,  -- keep after all
    ...
    PRIMARY KEY(post_id, meta_key, meta_id),  -- to allow dup meta_key for a post

Source doc

Possible ALTER

Caveats:

I have no way to test this.
This does not address the 767 error
This keeps meta_id because some WP user pointed out that it is referenced by other tables.
It assumes you might have multiple rows for a (post_id, meta_key) combo. (This seems like poor schema design?)
All this does is speed up typical SELECTs involving postmeta.
This probably applies to woocommerce, too.
If you use this, please dump your database and be ready to reload it in case of trouble.

The SQL:

ALTER TABLE wp_postmeta
    DROP PRIMARY KEY,
    DROP INDEX post_id,
    ADD PRIMARY KEY(post_id, meta_key, meta_id),  -- to allow dup meta_key for a post
    ADD INDEX(meta_id);    -- to keep AUTO_INCREMENT happy