Percona-Server: slow TokuDB queries after upgrading from 5.6 to 5.7. ANALYZE TABLE doesn't resolve the problem

After upgrading from Percona-TokuDB 5.6.29-76.2 to 5.7.19-17 we see some very slow queries on some tables without primary keys, but multiple non-unique indexes. The box we migrated to is pretty well equipped (768 GB RAM, PCIe SSDs). We used mysql_upgrade after migration. After investigating https://dba.stackexchange.com/questions/135180/percona-5-7-tokudb-poor-query-performance-wrong-non-clustered-index-chosen we tried ANALYZE TABLE, even with RECOUNT_ROWS, REPAIR TABLE, ALTER TABLE *** FORCE without any effect. Typical table structure: CREATE TABLE letter_archiv_12375 ( user_id int(12) unsigned NOT NULL DEFAULT '0', letter_id mediumint(6) unsigned NOT NULL DEFAULT '0', crypt_id bigint(12) unsigned NOT NULL DEFAULT '0', mailerror tinyint(1) unsigned NOT NULL DEFAULT '0', unsubscribe tinyint(1) unsigned NOT NULL DEFAULT '0', send_date date NOT NULL, code varchar(255) NOT NULL DEFAULT '', KEY crypt_id (crypt_id), KEY letter_id (letter_id), KEY user_id (user_id) ) ENGINE=TokuDB A simple query like that takes 4 seconds on a table with 200m rows. UPDATE hoovie_1.letter_archiv_14167 SET unsubscribe = 1 WHERE letter_id = "784547" AND user_id = "2881564"; The cardinality values are correct. EXPLAIN will result in: id select_type table partitions type possible_keys key key_len ref rows filtered Extra 1 UPDATE letter_archiv_14167 NULL range letter_id,user_id letter_id 3 const 1 100.00 Using where The only solution is to remove and re-create at least one index. After dropping and re-creating the index letter_id the table will perform well (in 0.01 s). The EXPLAIN will change to id select_type table partitions type possible_keys key key_len ref rows filtered Extra 1 UPDATE letter_archiv_14167 NULL range user_id,letter_id user_id 4 const 99 100.00 Using where We have some thousands of TokuDB tables in production - a performance loss of factor 300-500 is a problem. So we are unsure to migrate to 5.7 - this behaviour could occur even after re-creating all indexes again. Any ideas?