【IT168 技术文章】

    这两天做多表查询的时候感叹，无论是for all entries 还是inner join ,本质上还是逃不开嵌套查询，复杂度仍然是O(m*n)。在数据量很大的时候查询效率会急剧降低，局限性太多，于是我开始想尽可能的降低这个复杂度。

    首先我采用了网上普遍提到的二分法查询优化。

    如果关系匹配条件是其中一个表的关键字（参照以下示例）：vbak和tvkot均是数据字典里定义好结构的sap表，我们要把符合条件

    （vbak-vkorg=tvkot-vkorg）的数据选出,并输出vbak表的vbeln vkorg vkgrp kunnr waerk netwr字段以及tvkot表的vtext字段。如果vkorg字段是tvkot表的主键，那么可以用binary search降低复杂度为O(m*lgn)。

    一.先定义两个结构：

    DATA: BEGIN OF wa_big_result,

    vbeln TYPE vbak-vbeln,

    vkorg TYPE vbak-vkorg,

    vkgrp TYPE vbak-vkgrp,

    kunnr TYPE vbak-kunnr,

    waerk TYPE vbak-waerk,

    netwr TYPE vbak-netwr,

    vtext TYPE tvkot-vtext,

    END OF wa_big_result,

    it_big_result LIKE TABLE OF wa_big_result WITH HEADER LINE.

    DATA: BEGIN OF wa_tvkot_result,

    vkorg TYPE tvkot-vkorg,

    vtext TYPE tvkot-vtext,

    END OF wa_tvkot_result,

    it_tvkot_result LIKE TABLE OF wa_tvkot_result.

    二.把数据分别放入定义的两个内表中，并且用关键字vkgrp给内表t_tvgrt_result排序。然后循环内表it_big_result用内部用二分法查询找出匹配数据行并且修改内表it_big_result当前行数据，没有匹配则为空。

    SELECT vbeln vkorg vkgrp kunnr waerk netwr

    FROM vbak

    INTO CORRESPONDING FIELDS OF TABLE it_big_result.

    SELECT vkgrp bezei

    FROM tvgrt

    INTO CORRESPONDING FIELDS OF TABLE it_tvgrt_result.

    SORT it_tvgrt_result BY vkgrp.

    LOOP AT it_big_result.

    READ TABLE it_tvgrt_result WITH KEY vkgrp = it_big_result-vkgrp BINARY SEARCH

    INTO wa_tvgrt_result.

    IF sy-subrc = 0.

    it_big_result-bezei = wa_tvgrt_result-bezei.

    MODIFY it_big_result.

    ENDIF.

    ENDLOOP.

    上述代码为优化后的复杂度为O（m*lgn）的算法。但是仍然感觉性能一般，怎样可以继续优化？我想到了一个可以把复杂度降低为O（m+n）的算法，在这里献出并和大家一起讨论一下：