What statistical test would I use to test that both data sources are matching Suppose I am only working with two datasets, Data Source 1 with columns Customer ID and Install Date; and Data Source 2 with columns Customer ID and Install Date. 
Now suppose each data source has some un-observably large number of rows - so that I brute force checking if the install dates for customers in both datasets are the same is not feasible.
I could sample some number of observations from both sources and and create a binary feature which is 1 if matching and 0 if not matching. 
What statistical test would I use to test that both data sources are matching? My goal is to eventually obtain a sample size (with power=.9 and alpha=.05).
My first instinct was to reach for the McNemar's test - but that doesn't feel right. 
Any help is much appreciated!
 A: If you find a single mismatched pair, you know the data sets are not matched. It's impossible both to find a mismatched pair and for the datasets to be perfectly matched. So any test that relies on finding any mismatched pairs will have a false alarm rate (i.e., alpha) of 0.
The power of any test depends on the true "effect". The datasets would be considered mismatched if even one pair was mismatched. If you have a massive number of pairs and only one of them is mismatched, the probability of finding a mismatched pair in any sample is so low that you won't have any power to detect it. There is no way to balance power and size of the sample without knowing the proportion of mismatched pairs, but if you knew the proportion of mismatched pairs was different from 0, then you'd already have the answer to your question.
A: I think you want to do paired t test on dates, with the null hypothesis that on average dates agree against the alternative hypothesis that dates differ from DB 1 to DB 2 (earlier or later).
Here is a 'power and sample size' analysis from Minitab. 
Lacking details from you, I assumed the SD of the difference is
$\sigma = 2$ and that it is important to detect a systematic difference as large as one or two days. 
Power Curve for Paired t Test 

Power and Sample Size 

Paired t Test

Testing mean paired difference = 0 (versus ≠ 0)
Calculating power for mean paired difference = differenceα 
α = 0.05  
Assumed standard deviation of paired differences = 2

            Sample  Target
Difference    Size   Power  Actual Power
         1      44     0.9      0.900031
         2      13     0.9      0.910708


As you can see, under these assumptions, you would need to
look at about 44 pairs (customer IDs) to detect a difference of one day, and only about 13 for a difference of two days. You need to contrive a method to sample these customers at random.
You should check to see if differences are roughly normal.
If there are many huge outliers (either positive or negative),
then a t test may not be appropriate.
If the sample SD of differences is much different from my
assumed $\sigma = 2,$ then you need to re-do the computations
for sample size. (For example, if $\sigma=1,$ then respective sample sizes drop to about 13 and 5; if $\sigma=4,$ then increase to 170 and 44.)
Note: For the purpose you stated in your Comment, you should not reduce the differences to 0's and non-0's. The actual size of the difference matters.
