a few years ago I was playing with B-tree index cardinality
of MEMORY storage engine and come up with a patch (attached)
implementing on-line cardinality calculation.
According to my benchmarks, in certain cases MEMORY table scan
may be up to 45% faster than index scan. But since MEMORY engine
doesn't provide cardinality for B-tree indexes, index scan is
always preferred over table scan.
The idea of the patch is to provide accurate cardinality for
B-tree indexes at any time.
Max overhead should be 5-10% slowdown of DELETE/UPDATE queries.
Maxim N. Deviatov
Attachment: [text/x-patch] cardinality2.patch