You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I am investigating a case where the data access rule needs to enumerate candidates for index anding (intersection of index scans) for dozens of indexes. In my case the number of indexes is 12 and the number of combinations that need to be considered for intersections is around 4k. Since we compute the (among other things) the common ordering repeatedly we end up spending more than a second on this one rule.
Observations:
A necessary condition for the intersection to be plan-able is for the common ordering to exist. In fact, this condition is the most filtering condition when planning the intersection of index scans.
The intersection merge of n orderings is commutative and associative.
If there is a set of two orderings among the n orderings for a combination of single access orderings that does not have a common intersection ordering, the entire intersection ordering also does not exist and the intersection of these n single accesses cannot be planned.
If all combinations of size k <= n - 1 do not have a common intersection ordering, then there cannot be a combination of size k + 1. Reasoning: Under the assumption that there is such a common intersection ordering of size k + 1, there must be a common ordering of size k that then can be intersection merged with the (k + 1)th ordering. That contradicts the assumption.
To address this issue:
define a data structure that records all two-element sets of orderings of single accesses that do not have a common intersection ordering,
define an algorithm that allows us to quickly establish whether a set of n orderings contains a two-element set of orderings that is known to not have a common intersection ordering
early out if we were unable to find combinations of size k that have a common intersection ordering
The text was updated successfully, but these errors were encountered:
I am investigating a case where the data access rule needs to enumerate candidates for index anding (intersection of index scans) for dozens of indexes. In my case the number of indexes is 12 and the number of combinations that need to be considered for intersections is around 4k. Since we compute the (among other things) the common ordering repeatedly we end up spending more than a second on this one rule.
Observations:
k <= n - 1
do not have a common intersection ordering, then there cannot be a combination of sizek + 1
. Reasoning: Under the assumption that there is such a common intersection ordering of sizek + 1
, there must be a common ordering of size k that then can be intersection merged with the(k + 1)
th ordering. That contradicts the assumption.To address this issue:
The text was updated successfully, but these errors were encountered: