A method of performing a multi-way join of a plurality of database relations includes executing a plurality of pipelined two-way joins with the database relations. Each two-way join has two sequential phases. In the first phase, missing attributes of the input relations that are required to evaluate a joining criterion specific to said two-way join are fetched from a non-volatile memory device, and the input relations are joined according to the criterion. In the second phase, any additional missing attributes of the input relations are fetched from the non-volatile memory device as assigned by an optimization process executed prior to commencing the multi-way join.