Abfrage über mehrere Felder optimieren

[SvB]

Ich habe eine Suchmaske für Beleg, in der folgende Felder angezeigt werden: Belegnummer, Belegdatum, Kundennummer, Kundenname 1, Kundenname 2, Straße, PLZ, Ort, Seriennummer. Das Belegdatum ist ein TIMESTAMP, alle anderen Felder sind VARCHARs. Die Felder sind alle in der selben Tabelle. Zu jedem Feld gibt es auch einen eigenen Index, da ich diesen auch für andere Dinge benötige.
In der Suchmaske gibt es ein Eingabefeld, in den etwas beliebiges eingegeben werden kann und in den oben genannten Feldern gesucht werden soll. Im Moment baue ich mir ein SQL mit OR und LIKE zusammen. Beim Kunden dauert die Abfrage je nach dem zwischen mehreren Sekunden bis zu 3 Minuten und ist daher nicht optimal. Der Anwender ist damit nicht sehr zufrieden.
Da ist kein 100%-iger Datenbank Profi bin, weiß ich im Moment nicht wie ich das verbessern kann. Ich wäre für einige Tipps sehr dankbar.