1. A search apparatus searching for a combination of records from a set of records consisting of a plurality of attributes, comprising: an input device inputting a search pattern query that includes a repetition of an event and that is designated using a plurality of events, each of which defines that a predetermined attribute of a record has a predetermined value, and using an order relation among the plurality of events, which is defined based on an order of an attribute value; a conversion device extracting the order relation from the search pattern query, and converting the extracted order relation into a deterministic finite automaton; a search device repeating a process of, reading one or more records positioned in a same order position from a set of records, of checking whether or not a state transition can be performed by the deterministic finite automaton using the read records, and of registering in a state transition set a transition destination of a possible state transition and additional information indicating a record enabling the possible state transition, and when an end state of the deterministic finite automaton is registered in the state transition set as a transition destination, obtaining a combination of records corresponding to the search pattern query from additional information of a state transition which has reached the end state; and an output device outputting the obtained combination of records as a search result.