This paper presents MODPAROPT, MODular PARallel Query OPTimizer) a parallel optimizer for complex relational queries in a multi-query environment, which meets perfectly the requirements of modern database applications (e.g. decision support and data mining). The optimizers architecture was developed in a very strict modular way being therefore highly extensible. It integrates an intelligent resource allocation module coupled with a randomized search module in order to seek for the best parallelization strategy when resource availability is heterogeneous and probably limited. Experiments performed on a 100 relation database with 432 randomly chosen queries show the effectiveness of MODPAROPT.