Google (NSDQ: GOOG) has expanded the breadth of its music search engine in China, signing deals with all four major record labels to put their tracks on the site. The service, launched in August, lets users look up songs by singer, song, album title or beat and then download MP3s for free. Initially, the search engine had about 350,000 songs. With the addition of EMI, Sony (NYSE: SNE) Music, Warner Music Group (NYSE: WMG) and Universal Music the site’s catalog will jump to 1.1 million songs. “We were missing one piece ... we didn’t have music,” Lee Kai-Fu, the president of Google in greater China, tells Reuters.

SEE ALSO: Record Labels Seek $9 Million From Baidu, $7.5 Million From Sohu For Piracy Chargeshttp://www.paidcontent.org/entry/419-record-labels-seek-9-million-from-baidu-75-million-from-sohu-for-piracy

The music search engine is a major part of Google’s strategy to compete with Baidu (NSDQ: BIDU), which dominates the search market in China. A substantial portion of Baidu’s traffic comes from searches for MP3s. But many of the MP3s Baidu links to are illegal, and Baidu has been sued by the major labels for linking to them. Google’s service promises to offer legal—and higher-quality—tracks.