Timing complexity for correlation implementation on FPGA
If we assume 2 bytes per sample point (16 bits), then you have about 5 MB of database data, which pretty much dictates external memory to hold it on all but the very largest of FPGAs. The external memory interface will be the rate-limiting step in the correlation process.

If you have a number of DDR memory chips you could have an interface that's, say, 64 bits wide running at 200 MHz or so, which gives you a raw bandwidth of 3.2 GB/second. This allows you to scan through your database in less than 2 ms.

Then, you just need to make sure you have enough parallel logic to calculate your correlation as fast as the data comes in. I'm not familiar enough with the details of Spearman Correlation to offer any suggestions there.