About skyline prunning

For code in planner/core/find_best_task.go, I can’t quiet get the sense of comment above compareCandidates function.

// compareCandidates is the core of skyline pruning. It compares the two candidate paths on three dimensions:
// (1): the set of columns that occurred in the access condition,
// (2): whether or not it matches the physical property
// (3): does it require a double scan.
// If `x` is not worse than `y` at all factors,
// and there exists one factor that `x` is better than `y`, then `x` is better than `y`.

Can you provide more detail examples to clarify these 3 requirements?

Hi, @bowenxiaoCUHKSZ

  1. the set of columns that occurred in the access condition

If we have two indices, for example, idx1(b, a) and idx2(a). We knew that idx1 is stricter than idx2, that is, the total scan row return by idx1 is less or equal to idx2.

  1. whether or not it matches the physical property

The physical property includes ordering. If the SQL has order by b, we know that idx1 is better than idx2. Because idx1 matches the ordering property.

  1. does it require a double scan.

consider the SQL select a, b from t where a > 1 with indices idx2(a) and idx3(a, b). idx3 requires a single scan. But idx2 need a double scan, that is, firstly use idx2 to get a and handle, then use the handle to get a and b. So, idx3 is better than idx2 in this case.

Besides, you can refer to this proposal

1赞

Thx. Great Answer. So all three points are dealing with index path. LGTM.