left join复杂度优化

left join的时间复杂度通常比较高，类似于笛卡尔积的复杂度。即使关联字段是索引字段，也依然很费时。为了优化left join的复杂度，可以采取以下方法：
1. 将关联子查询转化为Left Outer Join。这样可以扩大IndexLookupJoin的使用范围，并且索引前缀匹配的场景也可以使用该算法。
2. 重构SQL执行引擎，使用Chunk结构进行优化。这样可以改进执行器的效率，提高查询性能。
3. 在left join的过程中，优化驱动表和被驱动表的选择。尽量选择小的结果集作为驱动表，并使用索引来加速查询。这样可以最大程度地减少时间复杂度。
4. 使用非聚集索引时，需要先找到聚集索引的唯一主键，然后根据聚集索引查找值。但是覆盖索引（多列索引）例外，查询列在索引列中，不需要再到聚集索引中查找一遍。这样可以减少IO操作，提高查询性能。
综上所述，通过合理选择驱动表和被驱动表，使用索引优化，以及优化关联子查询处理算法，可以对left join的复杂度进行优化，提高查询效率。<span class="em">1</span><span class="em">2</span><span class="em">3</span><span class="em">4</span>