Goodness-of-fit for very large sample sizes I collect very large samples (>1,000,000) of categorical data each day and want to see the data looks "significantly" different between days to detect errors in data collection.
I thought using a good-of-fit test (in particular, a G-test) would be a good fit (pun intended) for this. The expected distribution is given by the distribution of the previous day.
But, because my sample sizes are so large, the test has very high power and gives off many false positives. That is to say, even a very minor daily fluctuation will give a near-zero p-value.
I ended up multiplying my test statistic by some constant (0.001), which has the nice interpretation of sampling the data at that rate. This article seems to agree with this approach. They say that:

Chi square is most reliable with samples of between roughly 100 to
  2500 people

I'm looking for some more authoritative comments about this. Or perhaps some alternative solutions to false positives when running statistical tests on large data sets.
 A: The test is returning the correct result. The distributions are not the same from day to day. This is, of course,  no use to you. The issue you are facing has been long known. See: Karl Pearson and R. A. Fisher on Statistical Tests: A 1935 Exchange from Nature
Instead you could look back at previous data (either yours or from somewhere else) and get the distribution of day to day changes for each category. Then you check if the current change is likely to have occurred given that distribution. It is difficult to answer more specifically without knowing about the data and types of errors, but this approach seems more suited to your problem.
A: Let's go ahead and kill the sacred cow of 5%.
You have (correctly) pointed out that the issue is that of exuberant power of the test. You may want to recalibrate it towards a more relevant power, like say a more traditional value of 80%:


*

*Decide on the effect size you want to detect (e.g., 0.2% shift)

*Decide on the power that is good enough for you so that it's not overpowered (e.g., $1-\beta=80\%)$

*Work back from the existing theory of Pearson test to determine the level which would make your test practical.


Suppose you have 5 categories with equal probabilities, $p_1=p_2=p_3=p_4=p_5=0.2$, and your alternative is $p+\delta/\sqrt{n}=(0.198,0.202,0.2,0.2,0.2)$. So for $n=10^6$, $\delta=(-2,+2,0,0,0)$. The asymptotic distribution is non-central chi-square with $k=$ (# categories-1) = 4 d.f. and non-centrality parameter
$$
\lambda=\sum_j \delta_j^2/p_j = 4/0.2 + 4/0.2 = 40
$$
With this large value of $\lambda$, this is close enough to $N(\mu=\lambda+k=44,\sigma^2=2(k+2\lambda)=168)$. The 80%-tile is $44+13\cdot\Phi^{-1}(0.8)=44+13\cdot0.84=54.91$. Hence your desirable level of the test is the inverse tail cdf of $\chi^2_4$ from 54.91: $${\rm Prob}[\chi_4^2>54.91]=3.3\cdot10^{-11}$$
So that would be the level you should consider testing your data at so that it would have the power of 80% to detect the 0.2% differences. 
(Please check my math, this is a ridiculous level of a test, but that's what you wanted with your Big Data, didn't you? On the other hand, if you routinely see Pearson $\chi^2$ in the range of a couple hundred, this may be an entirely meaningful critical value to entertain.)
Keep in mind though that the approximations, both for the null and the alternative, may work poorly in the tails, see this discussion.
A: In these cases, my professor has suggested to compute Cramér's V which is a measure of association based on the chi-squared statistic. This should give you the strength and help you decide if the test is hypersensitive. But, I am not sure whether you can use the V with the kind of statistic which the G2 tests return.
This should be the formula for V: 
$$\phi_c=\sqrt{\frac{\chi^2}{n(k-1)}}$$ 
where $n$ is the grand total of observations and $k$ is the number of rows or number of columns whichever is less. Or for goodness of fit tests, the $k$ is apparently the no. of rows.
A: One approach would be to make the goodness-of fit tests more meaningful by performing them on smaller blocks of data.
You could split your data from a given day into e.g. 1000 blocks of 1000 samples each, and run an individual goodness-of-fit test for each block, with the expected distribution given by the full dataset from the previous day. Keep the significance level for each individual test at the level you were using (e.g. $\alpha =  0.05$). Then look for significant departures of the total number of positive tests from the expected number of false positives (under the null hypothesis that there is no difference in the distributions, the total number of positive tests is binomially distributed, with parameter $\alpha$).
You could find a good block size to use by taking datasets from two days where you could assume the distribution was the same, and seeing what block size gives a frequency of positive tests that is roughly equal to $\alpha$ (i.e., what block size stops your test from reporting spurious differences).
