The Sloan Digital Sky Survey (SDSS) was revolutionary because of the extraordinary breadth and ambition of its optical imaging and spectroscopy. We argue that a sub-millimeter SDSS - a sensitive large-area imaging+spectroscopic survey in the sub-mm window - will revolutionize our understanding of galaxy evolution in the early Universe. By detecting the thermal dust continuum emission and atomic and molecular line emission of galaxies out to z~10 it will be possible to measure the redshifts, star formation rates, dust and gas content of hundreds of thousands of high-z galaxies down to ~L*. Many of these galaxies will have counterparts visible in the deep optical imaging of the Large Synoptic Survey Telescope. This 3D map of galaxy evolution will span the peak epoch of galaxy formation all the way back to cosmic dawn, measuring the co-evolution of the star formation rate density and molecular gas content of galaxies, tracking the production of metals and charting the growth of large-scale structure.