We study the effect of the supersonic relative velocity between dark matter and baryons on large-scale galaxy clustering and derive the constraint on the relative velocity bias parameter from the Baryonic Oscillation Spectroscopic Survey (BOSS) power spectrum measurements. Recent work has shown that the relative velocity effect may have a dramatic impact on the star formation at high redshifts, if first stars are formed in minihalos around z˜20, or if the effect propagates through secondary effects to stars formed at later redshifts. The relative velocity effect has particularly strong signatures in the large scale clustering of these sources, including the baryonic acoustic oscillation position. Assuming that a small fraction of stars in low-redshift massive galaxies retain the memory of the primordial relative velocity effect, galaxy clustering measurements can be used to constrain the signatures of the first stars. Luminous red galaxies contain some of the oldest stars in the Universe and are ideally suited to search for this effect. Using the BOSS power spectrum measurements from the Sloan Data Release 9, in combination with Planck, we derive the upper limit on the fraction of the stars sensitive to the relative velocity effect f⋆<3.3% at the 95% confidence level in the CMASS galaxy sample. If an additional galaxy sample not sensitive to the effect is available in a given survey, a joint multitracer analysis can be applied to construct a sample-variance canceling combination, providing a model-independent way to verify the presence of the relative velocity effect in the galaxy power spectrum on large scales. Such a multitracer analysis in future galaxy surveys can greatly improve the current constraint, achieving a 0.1% level in f⋆.