Does the number of rows really matter beyond a point? While working with any machine learning algorithm, does the number of rows really matter beyond a certain point?
I have kept some algorithms(decision tree in this instance) running for days, and the accuracy I get is similar to those I get immediately for 5000 rows. I'm kind of feeling that running it on the entire data set is more like a 'check' to verify the results you get with 5000 rows.
Is there any study on how many rows are actually needed and how much results vary when increasing the number of rows?
 A: Answer here will probably be application-specific, data-set specific. In any given situation you can try yourself, select $m$ (say, 5000) rows at random, do the same again, again, ... and compare results.
You could also exploit your situation to draw some hold-out sample, to use for independent model verification.  If you are using some kind of automatic variable selection, that could be very valuable.
If you need confidence intervals for model parameters, those may be to long with this "use only a large random subsample" procedure, but, anyhow, the confidence intervals calculated with the full dataset are probably too short ... they depend on assumptions such as "the model is absolutely correct", "all variables measured without error", and so on, which might be fairly innocuous with small data sets, but not trustworthy with large data sets. Things like variables only measured with a finite (small) number of correct decimals will ultimately limit how short confidence intervals can be! You can yourself, with your data, investigate such questions by redoing the random subsampling many times, plotting the different coefficients obtained from each subsample, and compare the variation between them to the length of calculated confidence intervals.
