I think the key is goiong to be what the users want to do with the output, as Frantisek says.
If it's for an export, I'd export the data without sorting, then sort in the spreadsheet.
If it's for display, I would hope there's some paging involved, otherwise it will take a very long time to push the HTML from the server to the browser, so I'd recommend doing an FT Search on Project_no and Realization_date between certain ranges and "chunking" your requests. You'll need a manual pager to load the next set of results, but if you're expecting that many, you won't get a pager that calculates the total number of pages anyway.
Also, if it's an XAgent or displaying everything in one go, set viewState="nostate" on the relevant XPage. Otherwise, every request will get serialized to disk. So the results of your search get serialized to disk / memory, which is probably what's causing the Java memory issues you're seeing.
Remember FT_MAX_SEARCH_RESULTS notes.ini variable can be amended on the server to increase the (default) maximum from 5000.
500,000 is a very high set of results and is probably not going to make it very user-friendly for any subsequent actions on them. I'd probably also recommend restricting the search, e.g. forcing a separate entry of the "2015" portion or preventing entry of just one number, so it has to be e.g. "30" instead of just "3". That may also mean amending your view so the Project_no format displays as @Right("0000" + @Left(Project_no,"/"), 4)
, so users don't get 3, 30, 31, 32....300, 301, 302...., but can search for "003" and find just 30, 31, 32..., 39. It really depends on what the users are wanting to do and may require a bit of thinking outside the box, to quickly give them access to the targeted set of documents they want to action.