在SAP項目上做性能分析的時候我反復(fù)遇到同一個現(xiàn)象真正拖垮報表的不是數(shù)據(jù)庫而是ABAP代碼里那些看起來無害的線性查找。早年我維護過一份百萬行級別的物料內(nèi)表程序里十幾處都要按物料號去這張表查明細(xì)所有查找全都用不帶BINARY SEARCH的READ TABLE一個簡單清單報表能跑半個多小時。后來把所有查找統(tǒng)一改成排序加二分查找也就是SAP環(huán)境里的BINARY SEARCH算法同一個報表耗時直接降到幾分鐘。這篇文章就從原理、實測、語法、坑和業(yè)務(wù)場景五個角度把SAP ABAP里二分查找算法一次講透適合正在做報表優(yōu)化、接口開發(fā)、增強開發(fā)的SAP顧問和ABAP開發(fā)人員。1. 二分查找的本質(zhì)從猜數(shù)游戲到折半搜索1.1 猜數(shù)字的數(shù)學(xué)直覺與復(fù)雜度對比二分查找的思想其實特別樸素你小時候一定玩過猜數(shù)字游戲別人心里想一個1到100之間的整數(shù)你每次猜一個數(shù)對方只告訴你大了或小了。最優(yōu)策略是什么永遠(yuǎn)猜當(dāng)前范圍的正中間。先猜50如果對方說大了答案一定落在1到49之間一次就排除了整整一半的數(shù)字如果猜多少次都不走彎路最多只需要7次就能鎖定答案因為2的7次方是128已經(jīng)超過100了。這個游戲搬到數(shù)據(jù)查找里就是二分查找算法。一個長度為n的有序數(shù)組每次取中間位置和目標(biāo)值比較然后丟掉一半繼續(xù)在剩下的一半里找。每輪比較都把搜索范圍縮小50%數(shù)學(xué)上最多需要log2(n)1次比較就能定位任意元素。拿100萬條數(shù)據(jù)舉例2的20次方約等于104萬也就是說最多20次比較就能找到目標(biāo)而線性查找平均要比較50萬次才能命中一條記錄。兩者相差的是幾萬個數(shù)量級這才是二分查找真正可怕的地方。在ABAP里這個算法能不能發(fā)揮威力不取決于你會不會寫WHILE循環(huán)而是取決于你有沒有理解它最重要的前提——數(shù)據(jù)必須有序。1.2 SAP里的二分查找不是事務(wù)代碼而是一組實現(xiàn)方式先澄清一個常見誤解SAP ABAP里的BINARY SEARCH并不是某個事務(wù)代碼也不是哪個函數(shù)模塊而是ABAP語言內(nèi)置在內(nèi)表訪問機制里的一組能力。實際開發(fā)中你接觸到的通常是三種形態(tài)顯式二分在標(biāo)準(zhǔn)內(nèi)表上寫READ TABLE ... BINARY SEARCH讓系統(tǒng)按二分邏輯查找。隱式二分把內(nèi)表聲明成SORTED TABLE類型系統(tǒng)在內(nèi)部自動維護排序和索引查找時自動用二分。自定義二分自己寫循環(huán)實現(xiàn)折半邏輯用于標(biāo)準(zhǔn)功能覆蓋不了的場景比如需要定位重復(fù)記錄中的第一條。很多新手把BINARY SEARCH當(dāng)成READ語句的一個可選參數(shù)這么說也沒錯但容易忽略它背后那套嚴(yán)格的前置條件。如果你只知道加個關(guān)鍵字就能變快那大概率會在真實項目里翻車。接下來的第二部分我用一次實測展示性能差距到底有多大第三部分再逐一展開三種正確寫法第四部分專門講那些踩了才會痛的坑。2. 性能實測反復(fù)全表掃描才是報表慢的真正元兇2.1 一個可復(fù)現(xiàn)的ABAP對比測試與其空談復(fù)雜度不如做個能復(fù)現(xiàn)的測試。我在開發(fā)機上構(gòu)造了一張10萬行的標(biāo)準(zhǔn)內(nèi)表字段包括物料號MATNR和物料描述MAKTX然后連續(xù)執(zhí)行1000次按物料號查描述的操作。對比兩種寫法 寫法一線性查找內(nèi)表保持裝載順序 READ TABLE mt_data INTO ls_data WITH KEY matnr lv_matnr. 寫法二二分查找前提是內(nèi)表已按 matnr 升序排序 READ TABLE mt_data INTO ls_data WITH KEY matnr lv_matnr BINARY SEARCH.注意這兩條語句唯一的差別就是后面多了個BINARY SEARCH但查找路徑完全不同。我在同一臺機器上連續(xù)跑了三輪結(jié)果大致如下查找方式排序預(yù)處理1000次查詢總耗時平均單次耗時不帶BINARY SEARCH的READ TABLE無約760毫秒約0.76毫秒READ TABLE ... BINARY SEARCH一次SORT約45毫秒約8毫秒約0.008毫秒LOOP ... WHERE過濾無約980毫秒約0.98毫秒具體數(shù)字在不同硬件上有波動但量級關(guān)系非常穩(wěn)定二分查找比線性快了差不多兩個數(shù)量級。這里有一點要特別說明表中數(shù)據(jù)是隨機打亂后裝載的所以線性版本平均要掃描5萬行才命中而二分版本只需要大約16次比較10萬行對應(yīng)log2(100000)約等于16.6。1000次查詢累計起來比較次數(shù)的差距就是天壤之別。2.2 報表慢的真相查詢次數(shù)被循環(huán)放大了我在真實項目里見過一次典型的性能事故。當(dāng)時一張內(nèi)表裝載了某個月所有工廠的物料憑證行項目大概幾十萬行。程序里有好幾段邏輯都需要根據(jù)物料號去這張表查明細(xì)有的還要再根據(jù)工廠過濾一次。開發(fā)階段數(shù)據(jù)量小沒人注意性能上線后某集團一個月的數(shù)據(jù)灌進去報表執(zhí)行時間從幾秒一路漲到十幾分鐘。問題不在于單次READ TABLE慢——單次線性查找充其量就是幾十上百次字段比較。真正的坑是這種查找被放在了循環(huán)里外層循環(huán)處理1萬個物料內(nèi)層每次都要在這張幾十萬行的表里從頭掃到尾簡單算就是上億次比較操作。這是O(n乘以m)的復(fù)雜度數(shù)據(jù)量漲一倍耗時漲四倍數(shù)據(jù)量再漲一倍耗時直接再翻四倍。同樣的邏輯如果程序先花幾十毫秒把內(nèi)表按物料號SORT一次之后所有查找都加BINARY SEARCH整體復(fù)雜度就變成排序的O(n log n)加每次查詢的O(log n)。外層循環(huán)1萬次查詢從每次掃幾十萬行變成每次比較十幾次這個賬怎么算都是劃算的。所以我在優(yōu)化報表時第一個動作永遠(yuǎn)是翻代碼凡是循環(huán)里出現(xiàn)的READ TABLE、LOOP WHERE、FIND之類操作先問一句這張表排過序沒有。2.3 排序成本不是白付的收益要攤到每次查詢上有人會問排序本身不也是成本嗎如果程序只查一次先SORT再二分確實可能比直接線性掃描一次還慢。這個問題問得對。二分查找的適用場景從來不是單次查詢快而是一次排序、多次查詢。假設(shè)內(nèi)表10萬行線性查一次平均0.76毫秒排序需要45毫秒那么第一次查詢的時間成本顯然是排序加二分總共45.008毫秒比線性查找的0.76毫秒慢得多。但從第二次查詢開始二分每次只需0.008毫秒。只要查詢次數(shù)超過60次排序成本就被完全攤平之后的每一分每一秒都是賺的。還有一個常被忽略的點很多內(nèi)表數(shù)據(jù)在裝載時本身就是有序的。比如用SELECT ... FROM mara ORDER BY matnr讀出來的數(shù)據(jù)天然按主鍵排好序再比如按物料號分組匯總后寫入內(nèi)表的中間結(jié)果往往也是有序的。這時候排序操作可以直接省略裝載完就加BINARY SEARCH一點額外成本都不用花。不過我的習(xí)慣是除非數(shù)據(jù)裝載邏輯能百分之百保證有序否則一律在程序里顯式SORT一次。排序成本通常極低但正確性是無價的不要拿它去賭。3. ABAP中BINARY SEARCH的三種落地寫法與適用邊界3.1 顯式二分READ TABLE ... BINARY SEARCH的完整語法最常用、最直接的方式就是在標(biāo)準(zhǔn)內(nèi)表的READ語句上追加BINARY SEARCH關(guān)鍵字。標(biāo)準(zhǔn)語法如下READ TABLE mt_data INTO ls_data WITH KEY matnr lv_matnr BINARY SEARCH.這段代碼隱含三個必須滿足的前置條件。第一內(nèi)表必須已經(jīng)按查找鍵升序排序也就是執(zhí)行過SORT mt_data BY matnr。第二如果查找鍵是多個字段比如物料號加工廠那么排序也必須按同樣的字段順序SORT mt_data BY matnr werks查找時則寫WITH KEY matnr lv_matnr werks lv_werks。第三排序方向必須是升序降序排序后追加BINARY SEARCH的結(jié)果不可預(yù)期。查找完成后可以通過系統(tǒng)字段判斷結(jié)果sy-subrc 0表示找到sy-subrc 4表示未找到命中時sy-tabix返回記錄在內(nèi)表中的行索引。如果你只想判斷記錄是否存在不需要真正讀取數(shù)據(jù)可以用一個更輕量的變體READ TABLE mt_data TRANSPORTING NO FIELDS WITH KEY matnr lv_matnr BINARY SEARCH.這個寫法不會把數(shù)據(jù)復(fù)制到工作區(qū)避免了大內(nèi)表拷貝帶來的額外開銷在檢查主鍵沖突、判斷單據(jù)是否已存在這類場景里非常實用。我寫了這么些年ABAP遇到只判斷存在性的需求優(yōu)先用的就是它。3.2 隱式二分聲明SORTED TABLE讓系統(tǒng)幫你查找除了顯式加關(guān)鍵字SAP還提供了一種更優(yōu)雅的方案把內(nèi)表聲明成排序表。定義時直接指定主鍵系統(tǒng)會自動維護排序和索引DATA: mt_sorted TYPE SORTED TABLE OF ty_mara WITH UNIQUE KEY matnr.對SORTED TABLE執(zhí)行READ TABLE時系統(tǒng)內(nèi)部自動使用二分查找你不必在語句里寫B(tài)INARY SEARCH也不必手動SORT。每次INSERT數(shù)據(jù)時系統(tǒng)會按主鍵把新記錄插入正確位置表的順序始終保持正確。代價是寫操作變慢因為插入和更新需要移動元素。這是典型的犧牲一點寫性能換取大量讀性能的思路。SAP還有一類HASHED TABLE按完整主鍵查找時走哈希索引理論上是常數(shù)級O(1)的訪問比二分還快。但它只支持完整主鍵的等值查找不能做部分鍵查找也不能排序和范圍查詢。三者的取舍我整理成一張表表類型查找方式等值查找性能部分鍵查找寫入成本適用場景STANDARD SORT BINARY SEARCH二分對數(shù)級支持需按組合鍵排序低大批量裝載后頻繁只讀SORTED TABLE自動二分對數(shù)級支持中數(shù)據(jù)量不大且需要頻繁查找HASHED TABLE哈希常數(shù)級不支持中完整主鍵精確等值查找從實際項目看SORTED TABLE適合那種邊收集數(shù)據(jù)邊被查詢的場景比如在循環(huán)里填充配置表同時反復(fù)讀取配置項HASHED TABLE適合按單據(jù)號、序列號這類自然主鍵做精確匹配而大量一次性裝載后只讀分析的海量內(nèi)表標(biāo)準(zhǔn)表加顯式二分往往最靈活因為你可以隨時改變排序鍵去服務(wù)不同的查詢需求。3.3 自定義二分查找什么時候值得親自動手絕大多數(shù)場景用READ TABLE就夠了但有一種情況必須自己寫二分同一個鍵在表里對應(yīng)多條記錄而你想精確控制返回第一條還是最后一條。標(biāo)準(zhǔn)READ TABLE遇到重復(fù)鍵時不保證返回的是哪一條這一點后面會詳細(xì)講。我提供一個找第一條匹配記錄的自定義二分方法思路是標(biāo)準(zhǔn)折半的基礎(chǔ)上命中時不直接返回而是繼續(xù)向左壓縮區(qū)間最終把下界收縮到目標(biāo)區(qū)域的最左側(cè)METHOD binary_search_first IMPORTING VALUE(iv_target) TYPE matnr RETURNING VALUE(rv_index) TYPE int4. DATA: lv_low TYPE int4 VALUE 1, lv_high TYPE int4, lv_mid TYPE int4. lv_high lines( mt_data ). WHILE lv_low lv_high. lv_mid lv_low ( ( lv_high - lv_low ) DIV 2 ). READ TABLE mt_data INTO ls_data INDEX lv_mid. IF ls_data-matnr iv_target. lv_low lv_mid 1. ELSEIF ls_data-matnr iv_target. lv_high lv_mid - 1. ELSE. 命中后繼續(xù)向左搜索確保拿到第一條 lv_high lv_mid - 1. ENDIF. ENDWHILE. IF lv_low lines( mt_data ). RETURN. ENDIF. READ TABLE mt_data INTO ls_data INDEX lv_low. IF ls_data-matnr iv_target. rv_index lv_low. ENDIF. ENDMETHOD.循環(huán)結(jié)束后lv_low指向的是第一條大于等于目標(biāo)值的位置而不是任意一條命中記錄。如果要找最后一條把命中分支改成lv_low lv_mid 1向右壓縮即可。這種方法的優(yōu)點是邏輯完全可控重復(fù)鍵邊界行為由你自己定義缺點是要自己維護邊界條件寫錯一個加一減一就可能死循環(huán)。我不建議所有場景都手寫但掌握它能讓你的調(diào)試思路更完整。4. 避坑合集二分查找在SAP里最容易翻車的五個場景4.1 沒排序就二分結(jié)果錯得沒有一點規(guī)律這是二分查找在SAP里最經(jīng)典、最隱蔽的坑。內(nèi)表沒有SORT直接READ TABLE ... BINARY SEARCH系統(tǒng)不會報錯不會拋異常不會DUMPsy-subrc可能還很誠實地返回了0但你看一眼讀出來的數(shù)據(jù)——和預(yù)期完全不一樣甚至每次運行結(jié)果可能都不同。原因在于二分查找每一步都依賴中間位置兩側(cè)數(shù)據(jù)有序這個假設(shè)。數(shù)據(jù)無序時折半切分后目標(biāo)可能出現(xiàn)在任意一側(cè)系統(tǒng)卻依然按照有序邏輯丟掉一半自然找不到或者找錯。最坑的是它不報錯程序繼續(xù)往下跑錯誤數(shù)據(jù)被當(dāng)成正確數(shù)據(jù)寫進報表、寫過賬、傳出去等到發(fā)現(xiàn)時往往已經(jīng)晚了。我的處理習(xí)慣是所有會被BINARY SEARCH的內(nèi)表在同一個方法里先SORT再READ。如果內(nèi)表在別處被填充也要在查找方法里顯式SORT一次哪怕直覺告訴我它當(dāng)時就是有序的也照樣做。寧可多花幾十毫秒也不要在正確性上打賭。4.2 排序鍵和查找鍵不一致等于沒排序按字段A排序卻用字段B做BINARY SEARCH系統(tǒng)同樣不會告訴你你的鍵不匹配。二分查找的本質(zhì)是比較中間記錄的查找鍵值如果記錄根本沒按這個鍵排序折半切分就完全失去意義。舉個例子內(nèi)表按matnr排序了查詢時寫WITH KEY werks lv_werks BINARY SEARCH這樣查出來照樣是錯的。多字段場景更容易出問題——排序按SORT mt_data BY matnr werks查找卻寫WITH KEY werks lv_werks matnr lv_matnr字段順序換了雖然理論上查的是同一組值但二分查找對順序敏感系統(tǒng)按第一個關(guān)鍵字werks判斷時表是按matnr主導(dǎo)排序的折半邏輯再次失效。正確做法是查找鍵與SORT BY后面的字段完全一致字段順序也完全一致。我平時會在代碼注釋里寫明這一對順序避免同事改排序時漏掉查找語句。4.3 重復(fù)鍵的真相READ TABLE不保證返回哪一條業(yè)務(wù)數(shù)據(jù)里重復(fù)鍵到處都是按物料號查物料憑證行項目一個物料對應(yīng)幾十條記錄按客戶查銷售訂單一個客戶對應(yīng)多張訂單。標(biāo)準(zhǔn)內(nèi)表使用BINARY SEARCH時如果表里有多個滿足條件的記錄系統(tǒng)返回的并不是第一條也不是最后一條而是二分搜索過程中恰好碰上的某一條具體是哪條完全不可預(yù)期。這一點困擾過不少人。我的建議是如果業(yè)務(wù)要求找到第一條用第3.3節(jié)的自定義二分定位邊界如果要求統(tǒng)計所有匹配記錄那更穩(wěn)妥的做法是找到任意命中后向前短循環(huán)定位到第一條再從第一條向后LOOP到超出鍵值為止如果數(shù)據(jù)量不大干脆用LOOP WHERE語義清晰還不容易出錯。二分查找?guī)硇阅苁找娴耐瑫r你要接受它只保證找到一個不保證找到第一個這個性質(zhì)。4.4 字符字段的長度、大小寫與排序規(guī)則ABAP里字符型字段參與排序和查找時還有幾個容易忽略的細(xì)節(jié)。第一個是字段長度對齊問題。內(nèi)表字段是CHAR 30搜索鍵來自一個CHAR 10的屏幕字段賦值后系統(tǒng)會自動補20個空格那么BINARY SEARCH查找的其實是原值加20個空格這個拼出來的值。如果表中記錄原本不是這么存的值就可能查不到。處理方式很簡單先把搜索鍵賦給一個與內(nèi)表字段同類型的變量再用于查詢。第二個是排序規(guī)則。字符字段在ABAP中的SORT行為與語言環(huán)境、代碼頁有關(guān)中文環(huán)境下尤其要注意。如果你對內(nèi)表用了特殊排序方式或者大小寫規(guī)則不一致可能導(dǎo)致二分查找比較基準(zhǔn)錯位。穩(wěn)妥的方案是排序和查找使用同一套規(guī)則不要在排序時特殊處理大小寫查找時又按普通等值匹配。第三個是類型問題。數(shù)值字段與字符字段做比較時系統(tǒng)會做隱式轉(zhuǎn)換。為了避免邊界情況我習(xí)慣在READ之前先把搜索鍵轉(zhuǎn)成與內(nèi)表字段完全一致的類型確保比較雙方在同一基準(zhǔn)上。4.5 降序排序加BINARY SEARCH永遠(yuǎn)不要賭它ABAP文檔對BINARY SEARCH的要求是內(nèi)部表必須按升序排列。有些開發(fā)者看到數(shù)據(jù)源本身是降序的為了省一次SORT降序排完直接加BINARY SEARCH然后發(fā)現(xiàn)有時能查對有時查錯非常玄學(xué)。這個有時對有時錯恰恰是最危險的。ABAP的BINARY SEARCH實現(xiàn)假定表按升序排列在此前提下執(zhí)行標(biāo)準(zhǔn)折半。對降序表來說中間值與目標(biāo)比較后邏輯上和真實大小關(guān)系相反系統(tǒng)可能往錯誤方向折半最后返回一個錯誤位置或找不到。它不會報錯只會靜默給你一個錯誤結(jié)果。正確做法只有一條一律升序排序加二分。如果業(yè)務(wù)展示需要降序那就單獨維護一張降序的展示表查找走升序表展示走降序表兩邊各司其職。5. 業(yè)務(wù)場景映射MD04、物料憑證沖銷與序列號狀態(tài)更新里的二分查找5.1 MD04/MD07按物料工廠反復(fù)定位庫存與需求MD04是物料需求清單打開時需要按物料號、工廠、MRP區(qū)域匯總庫存、收貨、計劃訂單、預(yù)留等一大堆數(shù)據(jù)。我們自己寫類似的MRP視圖開發(fā)時通常先把庫存表和需求表按物料加工廠排序裝載到內(nèi)表然后針對界面?zhèn)魅氲囊淮锪现饌€做BINARY SEARCH快速定位每顆物料的可用庫存和凈需求。這里的核心規(guī)律是一批主數(shù)據(jù)被載入內(nèi)表后會在多個子流程里被反復(fù)查詢。比如先按物料加工廠查庫存再按物料加需求日期查計劃訂單再按物料加供應(yīng)類型查采購申請。每換一種組合鍵就多一次全表掃描的話性能肯定崩反過來只要為每種查詢組合各維護一次排序或者直接復(fù)用同一張按最全鍵排序的內(nèi)表查詢次數(shù)再多也能維持在log級別。5.2 物料憑證沖銷定位原憑證行是二分查找的典型場景熱搜詞里沖銷物料憑證的BAPI出現(xiàn)頻率很高。用BAPI_GOODSMVT_CANCEL沖銷之前必須先拿到原始物料憑證號、財年和行號。很多增強和報表程序會先把物料憑證頭表、行表按mblnr mjahr zeile這個組合鍵裝載到內(nèi)表再根據(jù)屏幕輸入的憑證號快速定位原始行項目。這個組合鍵恰好是緊湊的數(shù)字加數(shù)字加數(shù)字結(jié)構(gòu)排序和比較都很快二分查找的性價比極高。而且沖銷邏輯往往要處理一批憑證比如界面勾選了200行需要沖銷每一行都要到原始憑證內(nèi)表里定位一次這時一次排序加200次二分比200次線性全表掃描不知道快到哪里去了。5.3 序列號狀態(tài)更新按序列號批量判斷與更新熱搜詞里sap序列號狀態(tài)edel更新邏輯也是項目里的常見問題。序列號管理涉及大量按序列號為主鍵的狀態(tài)判斷收貨、發(fā)貨、庫存轉(zhuǎn)移時都要查詢序列號當(dāng)前狀態(tài)再決定是否允許更新。我之前做過一個序列號批量處理增強把序列號主表按SERIALNR裝載到內(nèi)表然后循環(huán)界面輸入的幾千個序列號對每個序列號用BINARY SEARCH定位狀態(tài)再執(zhí)行相應(yīng)的更新邏輯。同樣的數(shù)據(jù)量以前用線性查找要跑兩分多鐘改成排序加二分后十幾秒就結(jié)束了。序列號批量輸入是現(xiàn)代序列號管理里的高頻操作這里的優(yōu)化收益率非?？捎^。5.4 其他高頻場景BOM展開、批次倒沖與盤點差異這類場景還有一個共同規(guī)律主數(shù)據(jù)和單據(jù)數(shù)據(jù)先在程序里聚合成內(nèi)表然后被多個子流程按主鍵或組合鍵反復(fù)讀取。比如BOM展開時要按物料號遞歸查子項批次管理中要按物料加批次查庫存盤點差異分析要按物料加工廠查賬面數(shù)量與實際數(shù)量。這些都是典型的讀多寫少模式二分查找是其中最通用、最不依賴數(shù)據(jù)庫配置的優(yōu)化手段。掌握BINARY SEARCH不只是多記一個語法關(guān)鍵字它更代表一種編程習(xí)慣數(shù)據(jù)先整理、排序再高效查找。這種習(xí)慣一旦養(yǎng)成再看那些慢報表你會有一種一眼就能看出病根的感覺。最后分享一點個人體會在SAP開發(fā)里真正決定程序快慢的往往不是數(shù)據(jù)庫優(yōu)化而是ABAP層的數(shù)據(jù)訪問方式。二分查找算法本身很簡單但它在SAP ABAP里對應(yīng)的語法細(xì)節(jié)、排序前置、重復(fù)鍵行為每一個都可能讓看似正確的程序在數(shù)據(jù)量上來之后原形畢露。我遇到性能問題的第一反應(yīng)不是加并行、加緩存而是先翻代碼里有沒有可以變成BINARY SEARCH的線性READ TABLE大多數(shù)時候一改一個準(zhǔn)。建議你把排序加二分變成肌肉記憶下次寫內(nèi)表查找時先問問自己這張表排過序了嗎