We discussed ways to improve the performance at the ground level, partitioning the tables by properties and creating new tables (duplicate ones) with partition based on subjects. The documentation is again at http://www.semantic-mediawiki.org/wiki/SQLStore_Update. This let to an interesting idea of separating the smw_id table into  two new tables for  subjects (pages) and properties separately, and this will enable us to store additional information about properties such as their table name (as now we shall have different ones for some properties) and  datatype of their values.
Some of the places that helped us are http://backchannel.org/blog/friendfeed-schemaless-mysql and http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html

Currently, I am ready to create these tables, any further additions will be done on the fly, as otherwise we will never get to code actually. I won’t rewrite the setup.php now and will do it once everything is finalized (also then we will think of the migration script).