1. A method of performing a multi-way join of a plurality of database relations, comprising executing a plurality of pipelined two-way joins with said relations, each said two-way join comprising two sequential phases; wherein a first phase of each said two-way join comprises: fetching from a nonvolatile memory device any missing attributes in input relations that are required to evaluate a joining criterion specific to said two-way join; and joining said input relations according to said criterion; and wherein said second phase of each said two-way join comprises: fetching from said nonvolatile memory device any additional missing attributes in said input relations as assigned by an optimization process executed prior to commencing said multi-way join.