In case it is ordered (see e.g. Mnist data set) SGD will have problems. Also, in case you run through it multiple times (so called epoches) having the same order on each run through will probably lead to problems like finding local minima or slower convergence. So you should randomize on each epoche.

Generally, in case your data is ordered (see e.g. Mnist data set) SGD will have problems. Also, in case you run through it multiple times (so called epoches) having the same order on each run through will probably lead to problems like finding local minima or slower convergence. So you should randomize on each epoche.

In case of a huge amount of data points it is not recommended to shuffle the whole data set. Rather you can follow another random strategy. It may be enough to randomly sample (without replacement) a mini batch of data points. Subsequently you fit the model on the mini-batch by SGD and repeat this process across more mini-batches until convergence. This procedure will also find the solution and probably will use far less data than the full set of data points (but the latter depends on the type of model and data). It is therefore most of the times the much cheaper procedure.