attribute_group [id, name, order]
attribute [id, group_id, name, order]
attribute_value [id, value]
product_attribute [product_id, attribute_id, attribute_value_id]
У разных товаров могут быть атрибуты объединенные в группы. Их можно сортировать по полю order.
При необходимости, вы можете создать связь между категориями и группами атрибутов.
category_attribute [category_id, group_id]
Не бойтесь, будут сложные запросы, но ввиду декомпозиции объем данных будет уменьшен.
Сложность запросов легко нивелируется кэшированием.
А до миллионов товаров в таблицах нужно еще дорасти.