Anda benar, meja sebesar itu tidak dapat digunakan. Jika Anda membutuhkan sistem penyimpanan pesan yang sebenarnya, lebih baik lihat solusi NoSQL (seperti HBase, Cassandra, MongoDB, dll.), Anda hanya perlu melupakan apa pun yang Anda ketahui tentang basis data relasional.
Dengan MySQL, Anda masih dapat melakukan sesuatu yang skalabel jika membagi tabel menjadi bagian-bagian yang sangat kecil. Buat satu tabel, simpan pesan dari maksimal 1.000 pengguna (Anda harus menulis semua pesan dua kali kecuali kedua pengguna berasal dari tabel yang sama). Plus simpan tidak lebih dari 1k tabel dalam satu DB, buat tabel lain secara otomatis saat batas ini tercapai. Memiliki beberapa database (bahkan pada satu server fisik) akan memudahkan DBA untuk mentransfer masing-masing ke server baru ketika yang sekarang menjadi kelebihan beban. Untuk mendapatkan pesan dari pengguna tertentu, kode Anda harus mendapatkan DB/tabel yang diperlukan dari peta yang akan Anda miliki.