A query-processing computer system comprising an optimized-query-plan caching subsystem (816, 818), the optimized-query-plan caching subsystem comprising: an optimized-query-plan cache contained in electronic memory of the computer system or distributed across one or more electronic memories and mass-storage devices within the computer system; and a caching component that executes within the query-processing computer system and that stores optimized query plans in the optimized-query-plan cache, wherein each optimized query plan is stored in association with an associated representation of an equivalence group and in association with an associated representation of an equivalence class contained within the equivalence group and that retrieves optimized query plans from the optimized-query-plan cache, wherein each equivalence-group representation stored in the-optimized query-plan cache represents a normalized and parameterized query plan, wherein each equivalence-class representation (1020, 1022) stored in the optimized-query-plan cache represents one optimized query plan produced by optimizing the normalized and parameterized query plan represented by the equivalence group that contains the equivalence class following replacement of parameters of the normalized and parameterized query plan with literal values, and wherein each equivalence-class representation (1020, 1022) stored in the optimized-query-plan cache is defined by a predicate selectivity or a range of predicate selectivities (1026, 1028) computed for queries that, when normalized and parameterized, are equivalent to the normalized and parameterized query plan represented by the equivalence group, wherein the caching component retrieves an optimized query plan from the optimized-query-plan cache by: receiving an initial query plan and predicate selectivity computed for the initial query plan (1114, 1150); determining whether or not an equivalence group for the query plan is stored in the optimize-query-plan cache; when an equivalence group for the query plan is stored in the optimize-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity; and when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the identified equivalence class. an optimized-query-plan cache contained in electronic memory of the computer system or distributed across one or more electronic memories and mass-storage devices within the computer system; and a caching component that executes within the query-processing computer system and that stores optimized query plans in the optimized-query-plan cache, wherein each optimized query plan is stored in association with an associated representation of an equivalence group and in association with an associated representation of an equivalence class contained within the equivalence group and that retrieves optimized query plans from the optimized-query-plan cache, wherein each equivalence-group representation stored in the-optimized query-plan cache represents a normalized and parameterized query plan, wherein each equivalence-class representation (1020, 1022) stored in the optimized-query-plan cache represents one optimized query plan produced by optimizing the normalized and parameterized query plan represented by the equivalence group that contains the equivalence class following replacement of parameters of the normalized and parameterized query plan with literal values, and wherein each equivalence-class representation (1020, 1022) stored in the optimized-query-plan cache is defined by a predicate selectivity or a range of predicate selectivities (1026, 1028) computed for queries that, when normalized and parameterized, are equivalent to the normalized and parameterized query plan represented by the equivalence group, wherein the caching component retrieves an optimized query plan from the optimized-query-plan cache by: receiving an initial query plan and predicate selectivity computed for the initial query plan (1114, 1150); determining whether or not an equivalence group for the query plan is stored in the optimize-query-plan cache; when an equivalence group for the query plan is stored in the optimize-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity; and when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the identified equivalence class. receiving an initial query plan and predicate selectivity computed for the initial query plan (1114, 1150); determining whether or not an equivalence group for the query plan is stored in the optimize-query-plan cache; when an equivalence group for the query plan is stored in the optimize-query-plan cache, traversing equivalence-class representations of equivalence class contained in the equivalence group to identify an equivalence class that corresponds to the received predicate selectivity; and when an equivalence class that corresponds to the received predicate selectivity is identified, retrieving an optimized query plan stored in association with the identified equivalence class.