Search apparatus and method using order pattern including repeating pattern

An order relation extracted from a search pattern query is converted into a deterministic finite automaton (DFA). A process of determining whether or not a state transition can be performed by the DFA using each record, and of registering a transition destination and history information in a state transition set, is repeated, thereby obtaining a combination of records corresponding to the search pattern query.