Sitemap protocol edge case

we're running a free xml sitemap generator, and our site mapping process hit a wall with truly massive sites. we're talking millions of URLs.

• the standard sitemap protocol specifies limits (50k URLs, 50MB file size). we're handling index files, no problem.
• the real issue surfaces when a *single sitemap file* (not the index) needs to contain a large number of URLs with complex parameters, leading to very long URL strings, pushing the 50MB limit even with fewer than 50k URLs.
• specifically, how to efficiently segment these complex-URL sitemaps without creating a ridiculous number of sub-files or exceeding google's processing capacity for sitemap indexes?

we've tried gzip compression, of course, but the raw XML size before compression for some edge cases is just brutal. thinking about splitting based on URL length/complexity rather than just count. not sure if that's even a viable strategy without breaking the protocol.

has anyone implemented a robust segmentation logic for sitemap files where URL string length/complexity is the primary bottleneck, not just the raw URL count or file size post-compression? especially regarding the sitemap protocol's implicit handling of such edge cases. anyone faced this before?