Custom permalinks with W3 Total Cache, please help!

I’m using wordpress and w3 total cache for my site long time.

recently I had changed my permalinks from
%post_id%/%category%/%postname%.html
To
/%category%/%postname%.html

it is to improve my site structure..
so all contents will looks like they are under each categories folder.
site.com/pictures/
site.com/pictures/abc/
site.com/pictures/cake/banana
etc
old one was
site.com/63323/pictures/cake/banana/ad.html
site.com/12423/pictures/drink/water/post23.html

I’ve done the 301 redirection,etc

WordPress suggest to use post_id or year ,etc to make the sql queries less and make it perform faster.

But is this still affect the loading time if we use w3 total cache plugin ?

I’ve enabled all caching(db,obj,page), and I use CDN and minify too.
I used APC caching for all, and I use VPS.net hosting with 6 nodes currently. and CDN is from MaxCDN.

I have deleted more than 4,000 useless posts, and I currently have 5,200 posts only.

Please advice.