Changing Permalink Settings in WordPress gives “Fatal error: Out of memory”

I tried to change the URL structure of my WordPress site. I am getting following error

"Fatal error: Out of memory (allocated 31981568) (tried to allocate 1111781 bytes) in ../wp-includes/wp-db.php on line 774"

I researched in internet and I got this solution:

1. Try adding this line to your wp-config.php file:
define('WP_MEMORY_LIMIT', '64M');

2. If you have access to your PHP.ini file, change the line in PHP.ini
If your line shows 32M try 64M:
memory_limit = 64M ; Maximum amount of memory a script may consume (64MB)

3. If you don't have access to PHP.ini try adding this to an .htaccess file:
php_value memory_limit 64M

4. Talk to your host.  

Nothing worked for me, I did not try the second option since I do not have access to php.ini file.

My Question is why changing an simple URL cause this issue? Is this because of cache or some thing?

Any help would be greatly appreciated.