Do you want the URLs to all change, or are you just thinking that they have to? Because it seems like it should be possible to keep them the same, if you want to.
I just came across this old thread while Googling, so I thought I’d share how we solved it.
We kept a legacy route to catch old URLs and extract the original product ID. Using that ID, the application finds the product in the database, generates its new canonical URL, and returns a permanent 301 redirect.
This is more reliable than using regex in .htaccess, especially when product names, categories, or slugs have changed.
Old URLs and backlinks still work, with visitors and search engines redirected directly to the new URL.