think about partitioning maybe, if you can split it on what you are searching on.

Full scanning 500 million rows will take a long time - why *MUST* you full scan it and not index the relevant columns?