What is the source for singing zemirot on Shabbat?

Question

Who and when did the custom of singing zemirot at the Shabbat table, and what was the basis (halacha, verse, etc.) for instituting it? What was the 1st zemirah?

Answer 1

This article notes that a seeming reference to zemirot as part of the Shabbos seudah is made by the Gemara (Megillah 12b):

יום השביעי שבת היה שישראל אוכלין ושותין מתחילין בד''ת ובדברי תשבחות

Early proponents of zemirot include R. Yehudah HaChassid (Sefer Chassidim 271) and R. Eliezer Rokeach (Rokeach 54).

Zemiros are extant from the period of the Geonim such as "baruch Hashem Yom Yom" from the 10th century.

Answer 2

The Machzor Vitry (a talmid of Rashi, who therefore preceeds R' Yehudah HaChassid and R' Elazar Rokeach) has a considerable number of the zemiros that we still sing today, some of which have variant girsaos. For example, Kol Mekadesh in the MV has lines for the entire alef-bais. Also, a number of zemiros were written by Donash Ben Labrat who preceeded Rashi.