Distributed tensor decomposition (DTD) is a fundamental data-analytics technique that extracts latent important properties from multi-attribute datasets distributed over edge devices. Its conventional one-shot implementation with over-the-air computation (AirComp) is confronted with the issues of limited storage-and-computation capacities and link interruption, which motivates us to propose a framework of on-thefly communication-and-computing (FlyCom(2)) in this work. The proposed framework enables streaming computation with low complexity by leveraging a random sketching technique and achieves progressive global aggregation through the integration of progressive uploading and multiple-input-multiple-output (MIMO) AirComp. To develop FlyCom(2), an on-the-fly sub-space estimator is designed to take real-time sketches accumulated at the server to generate online estimates for the decomposition. Its performance is evaluated by deriving both deterministic and probabilistic error bounds, which reveal the scaling laws of the decomposition error and inspire a threshold-based scheme to select reliably received sketches. Experimental results validate the performance gain of the proposed selection algorithm and show that compared to its one-shot counterparts, FlyCom(2) achieves comparable (even better with large eigen-gaps) decomposition accuracy besides dramatically reducing devices' complexity costs.