1. A method, comprising: obtaining a generated query plan by a shared-nothing data store system having a query distribution master node and a plurality of query execution segment nodes, each query execution segment node of the data store system comprising a respective processor and a respective non-transitory storage medium, the query plan having a tree-type data structure comprising data objects occupying leaf positions organized in hierarchical levels; determining, by the data store system, whether to cache the query plan based on a likelihood of the query plan becoming invalid, the likelihood of the query plan becoming invalid being determined based on complexity of the query plan, the likelihood being determined using actions comprising: determining whether a number of leaves in the tree-type data structure is greater than a preselected and user configurable threshold number; upon determining that the number of leaves is greater than the preselected and user configurable threshold number, designating the likelihood of the query plan becoming invalid as high; and upon determining that the number of leaves is not greater than the threshold number, performing actions comprising: determining whether the query plan contains one or more objects that are different from built-in objects represented by metadata; and upon determining that the query plan contains one or more objects that are different from built-in objects, designating the likelihood of the query plan becoming invalid as low, otherwise designating the likelihood of the query plan becoming invalid as high; and caching the query plan upon determining that the likelihood of the query plan becoming invalid is low.