Well first off I wouldn't recommend trying to power your client's database with the standard WordPress database instance. They can use WordPress for the website all they like. But with millions of records like that, you really don't want to move those data in with WordPress.

For that matter, you're probably gonna want a dedicated database server to answer those questions, if the client doesn't already have one. You might also need to investigate something like Elastic Search, depending on what your search requirements are and what sort of database they are using (pay close attention to whether or not it provides full text search ability).

Beyond that, and somewhat obviously, you're also gonna want SSL on the website and to make sure you're up to date on federal and state privacy requirements for data like this, as well as best practices for securely transferring data over the web (port configuration, ssh keys, etc).

The privacy concerns would raise a flag for me. If those data have anything personally identifiable in them - which they very probably do - then you're really gonna want to make sure you do your research on security of personally identifiable information. Government specific privacy /security /auditability requirements may also apply, so double check that too.

You need to hire a WordPress consultant to help you with that. If you email me at http://bradt.ca/contact/ with an approximate budget, timeline, and details about the project, I can forward it to freelance consultants I know.

I would look into a knowledgebase sort of wordpress application. For example http://debthelpdesk.org is a site that has their search built into blog posts, faq entries, files, forums...basically any public information they have setup on the site.

I believe this is the plugin that was built into their theme http://codecanyon.net/item/knb-wordpress-knowledge-base-wiki-shortcode-/full_screen_preview/8937609

You will also need a developer to allow for you to automatically upload a spreadsheet of data to make things easy

It's not clear from your question, but I'm assuming your client wants a frontend built in WordPress for this data. So assuming you'd be building a custom plugin.

Depending on the data structure, it may be best to keep this data in its own tables - within the same WP database if you like.

You can indeed create custom post types in WordPress and store any kind of data. But you may hit performance bottlenecks when you want to perform searches or want data in particular format.

We've built and tested some of our plugins with millions of rows of data. When we need higher performance, we've used our own tables inside WP. Rather than relying on WP's core data structures.

Hope this helps. And I'd be happy to answer any specific questions you may have.

I would advise for such a monster DB to keep it external to wordpress. Use elasticsearch for the DB and create an external service/api to be accesible from the WP site.

I believe these links will greatly help you when you sit creating large searchable database in WordPress:
I.
https://wordpress.org/plugins/inline-google-spreadsheet-viewer/
II.
https://wordpress.org/plugins/custom-database-tables/
III.
https://wordpress.org/plugins/custom-database-applications-by-caspio/
IV.
https://wordpress.org/plugins/wptables/
V.
https://wordpress.org/plugins/tabulate/

Also, have a look at this link: https://www.data.gov/local/get-local-government-data-gov ?

Besides if you do have any questions give me a call: https://clarity.fm/joy-brotonath