Data exceptions often reflect potential problems or dangers in the management of corporation. Analysts often need to identify these exceptions from large amount of data. A recent proposed approach automatically detects and marks the exceptions for the user and reduces the reliance on manual discovery. However, the efficiency and scalability of this method are not so satisfying. According to these disadvantages, the optimizations are investigated to improve it. A new method that pushes several constraints into the mining process is proposed in this paper. By enforcing several user-defined constraints, this method first restricts the multidimensional space to a small constrained-cube and then mines exceptions on it. Experimental results show that this method is efficient and scalable.