Big Data technologies are now widely adopted by enterprises to aid knowledge discovery and decision making. To support modern data applications, contemporary relational database systems (RDBMSs) have been augmented and even redesigned to better support large-scale analytical query processing. Typically, the end user is an analyst who interacts with the system in a ``compose query -- execute query -- interpret output -- compose new query based on insights from the output'' loop. The key aspects of this paradigm is to allow the analyst to discover insights from the underlying data as efficiently and effectively as possible. In this dissertation, we focus on a high-performance relational data platform, Quickstep, and propose two components to reduce query execution time for complex join queries and facilitate interactive analysis on provenance graph data, respectively, thus contributing to improving the productivity of the end users in each analytical scenario. First, we introduce a novel query execution strategy called LIP for robust query processing. LIP collapses the space of left-deep query plans for star schema warehouses down to almost a single point near the optimal plan. In addition to this robustness benefit, it also significantly speeds up query execution in the left-deep subplan space. Besides the immediate application of LIP, we believe our work opens a novel approach to the notion of ``robustness'', one that is focused on query execution strategies possibly tailored to corresponding query plan (sub-)spaces. Second, we build on top of Quickstep a new system called QuickGrail that supports efficient and effective querying on large provenance graphs. The QuickGrail system comes together with an expressive domain-specific query language that allows a human analyst to evaluate complex filter / lineage / path / pattern matching queries to yield possibly very large subgraphs as intermediate results, and do set operations such as union, intersection, subtraction on the subgraphs. The intermediate results can be efficiently concretized and used as inputs for subsequent iterations of exploratory analyses. We explain in detail the underlying implementations that support all the QuickGrail operations with high performance, robustness and scalability.