Performance of really big tile maps

Tiles are 1000 wide / 1000 high == 1million tiles
Tiles are 16 pixels / 16 pixels == 256 pixels.