Optimizer framework improvements

[thepinetree]

Feature Request

Summary

Optimizer framework rewrite tasks to support better operator choices and property pushdowns, in particular related to ORDER BY, LIMIT, DESCENDING scans.

Solution

Optimizer Related Changes

• Implement LIMIT clause pushdown and functionality on Index Scans and Index Joins
• Implement LIMIT clause pushdown and functionality on sequential scans
• Convert LIMIT nodes into properties for the optimizer front end, as is done with (ORDER BY), which should also address issue Optimizer does not successfully time out when query has a limit #1414
• Support Descending index scans, which are never selected by the optimizer in the following function in index_util.cpp:

  noisepage/src/optimizer/index_util.cpp

  Line 80 in 520e0da

  bool IndexUtil::CheckPredicates(

Cost Model Related Changes

• Add support for the cost model to choose the type of index scan based on the estimated cardinality of the scan itself (e.g. as observed by @tanujnay112, an Index Scan may match more predicate columns and create an open scan which runs more slowly compared to an Index Scan that matches fewer predicates but can perform an exact scan)
• Add framework for optional properties in the optimizer to make the (future) cost model aware of these for better operator choice
• Add support for operator tree pruning based on satisfied optional properties. ORDER BY nodes and LIMIT nodes are potential candidates

Index Related Changes

• Support an index iterator that allows for predicate push down into the index, at which point, predicate filter nodes can be removed for index scans, and LIMITs can be used more robustly, as explained in comments in (Index Scan Limit #1031)
• Exact scans should also be able to support LIMITs, but the ScanKey function doesn't expose this