Php ile beraber genelde MySql kullanılır. Hangi veritabanını kullandığınızı belirtmediğiniz için MySql üzerinden yorum yapıyorum.

Öncelikle 300K veri MySql e göre fazla değil.

Arama yapılan alanların index lenmiş olması arama hızınızı baya azaltır.
JOIN kullanarak birden fazla tabloyu ilişkilendirerek arama yapıyorsanız ilgili tablolarda arama yapılan kısımlar içinde index oluşturabilirsiniz.
Arama sonucunda max x sayıda sonuç listelemek istiyorsanız sorgunuzda LIMIT kullandığınızdan emin olun.( Performans açısından önemli)
MySql veritabanı motorları birden fazladır (MyIsam - InnoDb vs vs). Okuma-yazma sıklığınıza göre tabloların hangi engine kullanacağını belirlemeniz faydalı olacaktır.