【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）的算法，在这里献出并和大家一起讨论一下：
lips和likp均是在数据字典里定义好结构的sap表，likp是抬头，lips是对应的行项目。我们要把符合条件（lips-vbeln=likp-vbeln）的数据选出，并输出lips表的vgbel vbeln posnr matnr arktx lfimg字段以及likp表的ernam erdat lfdat lifnr字段。其中vbeln是表likp的主键。
一.定义存储表lips,likp部分字段的内表。ekko表的数据下一个例子要用到。
DATA: BEGIN OF wa_lips_result,
bukrs TYPE ekko-bukrs,
ekorg TYPE ekko-ekorg,
vgbel TYPE lips-vgbel,
vbeln TYPE lips-vbeln,
posnr TYPE lips-posnr,
matnr TYPE lips-matnr,
arktx TYPE lips-arktx,
lfimg TYPE lips-lfimg,
ernam TYPE likp-ernam,
erdat TYPE likp-erdat,
lfdat TYPE likp-lfdat,
lifnr TYPE likp-lifnr,
END OF wa_lips_result,
it_lips_result LIKE TABLE OF wa_lips_result WITH HEADER LINE.
DATA: BEGIN OF wa_likp_result,
vbeln TYPE likp-vbeln,
ernam TYPE likp-ernam,
erdat TYPE likp-erdat,
lfdat TYPE likp-lfdat,
lifnr TYPE likp-lifnr,
END OF wa_likp_result,
it_likp_result LIKE TABLE OF wa_likp_result WITH HEADER LINE.
二.从屏幕条件中选出数据填入两内表，按关键字vbeln对两内表排序，然后按条件选出数据。
SELECT vgbel vbeln posnr matnr arktx lfimg
FROM lips
INTO CORRESPONDING FIELDS OF TABLE it_lips_result
WHERE vbeln IN s_lvbeln.
SELECT vbeln ernam erdat lfdat lifnr
FROM likp
INTO CORRESPONDING FIELDS OF TABLE it_likp_result
WHERE lfdat IN s_lfdat
AND erdat IN s_erdat.
SORT it_lips_result BY vbeln.
SORT it_likp_result BY vbeln.
LOOP AT it_lips_result.
LOOP AT it_likp_result.
IF it_likp_result-vbeln = it_lips_result-vbeln.
MOVE-CORRESPONDING it_likp_result TO it_lips_result.
MODIFY it_lips_result.
EXIT.
ELSE.
DELETE it_likp_result.
ENDIF.
ENDLOOP.
ENDLOOP.
这个查询看似嵌套查询，复杂度为O(m*n),但实际上只有O(m+n)。我让两个内表一直按排序的顺序从小到大向前走，也就是说每次循环至少让其中一个表走一个数据。
如果说抬头和对应的行项目不具有普遍性，那么继续，ekko表同样是一个sap表，我们要把符合条件（ekko-ebeln= lips-vgbel）的数据进行筛选。
先为ekko定义包含其输出字段和匹配条件的内表，然后按屏幕条件选出数据填入此内表， 其中ebeln是ekko表的主键，按字段ebeln排序。ekko表的bukrs和ekorg字段是必输项。
DATA: BEGIN OF wa_ekko_result,
bukrs TYPE ekko-bukrs,
ekorg TYPE ekko-ekorg,
ebeln TYPE ekko-ebeln,
END OF wa_ekko_result,
it_ekko_result LIKE TABLE OF wa_ekko_result WITH HEADER LINE.
SELECT bukrs ekorg ebeln
FROM ekko
INTO CORRESPONDING FIELDS OF TABLE it_ekko_result
WHERE bukrs IN s_bukrs
AND ekorg IN s_ekorg.
SORT it_ekko_result BY ebeln.
二.把表it_ekko_result数据按主键ebeln装入it_lips_result，特别注意：此次外循环表it_lips_result在没有匹配到的时候也要删除！因为ekko的字段bukrs和ekorg是必输项！
DATA flag TYPE i VALUE 0.
LOOP AT it_lips_result.
LOOP AT it_ekko_result.
IF it_ekko_result-ebeln = it_lips_result-vgbel.
MOVE-CORRESPONDING it_ekko_result TO it_lips_result.
MODIFY it_lips_result.
flag = 1.
EXIT.
ELSEIF it_ekko_result-ebeln > it_lips_result-vgbel. "当内部循环表数值更大时跳到外部循环
EXIT.
ELSE.
DELETE it_ekko_result.
ENDIF.
ENDLOOP.
IF flag = 0.
DELETE it_lips_result.
ENDIF.
flag = 0.
ENDLOOP.
这个就不是抬头与行项目的对应关系。我们可以这样想想：有两份扑克牌，先都从小到大排序。以其中一份牌为基准，另一份牌有相等的就取出，小了就丢弃，这两种情况继续取，如果大了则把基准牌丢弃翻下一张。这样只需要扑克牌总张数次比较即可。容易想象这个算法的复杂度显然为O(m+n)。
如果关键字是联合主键一样可以，如：
ELSEIF it_mseg_result-mblnr > it_big_result-vbeln
OR ( it_mseg_result-mblnr = it_big_result-vbeln AND it_mseg_result-zeile > it_big_result-posnn ).
EXIT.
这个例子(mblnr, zeile)是联合主键。道理是相同的，按照排序从小到大依次比较。
我相当于实现了 两表结合查询中，如果匹配条件涉及的关键字段是其中一个表的主键时，可以把查询性能优化到一阶。
多表查询可以分拆为两表查询，我在作公司的一个报表程序中发现很多时候查询条件都得是其中一个表的主键，因此利用这个优化可以把程序的复杂度大大降低！
