The purpose of data warehouses is to enable business analysts tomake better decisions. Over the years the technology has maturedand data warehouses have become extremely successful. Asa consequence, more and more data has been added to the datawarehouses and their schemas have become increasingly complex.These systems still work great in order to generate pre-canned reports.However, with their current complexity, they tend to be apoor match for non tech-savvy business analysts who need answersto ad-hoc queries that were not anticipated.This paper describes the design, implementation, and experienceof the SODA system (Search over DAta Warehouse). SODAbridges the gap between the business needs of analysts and thetechnical complexity of current data warehouses. SODA enables aGoogle-like search experience for data warehouses by taking keywordqueries of business users and automatically generating executableSQL. The key idea is to use a graph pattern matching algorithmthat uses the metadata model of the data warehouse. Ourresults with real data from a global player in the financial servicesindustry show that SODA produces queries with high precision andrecall, and makes it much easier for business users to interactivelyexplore highly-complex data warehouses.