A user inputs, as a query pattern, a desired search-object rhythm pattern by operating a rhythm input device. At that time, a determination is made of a style of operation performed by a user on a rhythm input device, such as whether the user has operated a single key or a plurality of keys, or duration or intensity of the operation, and then, a user-intended performance part is identified, on the basis of the determined style of operation, from among one or more performance parts constituting a performance data set (automatic accompaniment data set). For the thus-identified performance part, a rhythm pattern search section searches an automatic accompaniment database for an automatic accompaniment data set including a rhythm pattern that matches the input rhythm pattern (query pattern).