Question answering in natural language over tabular and relational data has become a key capability in the democratization of insights from structured data sources. These systems first require table retrieval to identify data that is relevant to a given natural language query, for which several methods have been introduced. In this work we present and study a fine-grained decomposition-based and global connectivity-aware table retrieval mechanism (DCTR) that handles the challenges induced by open-domain question answering over relational databases in complex usage contexts. We evaluate the effectiveness of these two mechanisms through the lens of retrieval complexity which we measure along the axes of query- and data complexity. Our complexity analyses over industry-aligned benchmarks illustrates the robustness of DCTR for highly composite queries and densely connected relational databases.