The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.

Optimal indexes for this query:

ALTER TABLE `orderdtl` ADD INDEX `orderdtl_idx_company_ordernum` (`company`,`ordernum`);
ALTER TABLE `orderhed` ADD INDEX `orderhed_idx_ordernum_company` (`ordernum`,`company`);
ALTER TABLE `orderrel` ADD INDEX `orderrel_idx_company_ordernum_orderline` (`company`,`ordernum`,`orderline`);
ALTER TABLE `part` ADD INDEX `part_idx_company_partnum` (`company`,`partnum`);
ALTER TABLE `partwhse` ADD INDEX `partwhse_idx_company_partnum` (`company`,`partnum`);

The optimized query:

SELECT
        orderhed.ordernum,
        orderdtl.orderline,
        orderrel.orderrelnum,
        orderhed.custnum,
        orderhed.requestdate AS hedrequestdate,
        orderhed.orderdate AS hedorderdate,
        orderdtl.partnum,
        orderdtl.requestdate AS dtlrequestdate,
        orderrel.reqdate AS relreqdate,
        orderrel.needbydate AS relneedbydate,
        orderrel.ourreqqty,
        orderrel.plant AS releaseplant,
        partwhse.plant,
        partwhse.warehousecode,
        partwhse.allocqty,
        partwhse.onhandqty,
        part.partdescription 
    FROM
        part 
    RIGHT OUTER JOIN
        orderdtl 
            ON part.company = orderdtl.company 
            AND part.partnum = orderdtl.partnum 
    RIGHT OUTER JOIN
        orderhed 
            ON orderdtl.company = orderhed.company 
            AND orderdtl.ordernum = orderhed.ordernum 
    LEFT OUTER JOIN
        orderrel 
            ON orderdtl.company = orderrel.company 
            AND orderdtl.ordernum = orderrel.ordernum 
            AND orderdtl.orderline = orderrel.orderline 
    LEFT OUTER JOIN
        partwhse 
            ON orderdtl.company = partwhse.company 
            AND orderdtl.partnum = partwhse.partnum 
    WHERE
        (
            orderhed.ordernum = @p_ordernum
        ) 
        AND (
            orderhed.company = 'lot'
        ) 
    ORDER BY
        orderhed.ordernum,
        orderdtl.orderline,
        orderrel.orderrelnum