חיפוש טקסטואלי במחרוזת של ספרות

26/05/2015

תגיות: , ,
אין תגובות

מחפשים תת מחרוזת בתוך מחרוזת, כאשר המחרוזת מורכבת מספרות בלבד. בערך כמו מספרי תעודת זהות או מספרי טלפון, שלכאורה הם מספרים אך בפועל אינם אלא מחרוזות, ואין להם שום משמעות מתימטית. יחד עם זאת, לאור העובדה שמדובר במספר מצומצם של תווים (10), ניתן להפוך אותה לבעייה שכרוכה במתימטיקה, ולשפר את הביצועים.
אקדים ואציין שחיפוש מהסוג של ‘%..%’ Select .. From .. Where .. Like מחייב ביצוע Scan מלא על הטבלה ו-“Scan” על כל מחרוזת (המערכת תצטרך לחפש את תת המחרוזת לאורכה של כל מחרוזת), ולא ניתן להיעזר באינדקסים. ניתן אולי לנסות ולפרק את המחרוזות מראש לתתי מחרוזות (בכפוף לאורכן) ולאלתר פתרון שיהיה יעיל בהרבה, אך יחייב שינויים מורכבים יחסית במבנה הנתונים.
הפתרון שאני הולך להציג להלן משפר את הביצועים יחסית לחיפוש “פשוט” אם כי לא כמו בפירוק של המחרוזות,
וכרוך בשינוי במבנה הטבלה, אך לא כמו בפירוק מחרוזות..
בקיצור- פתרון ביניים: קצת פחות שיפור, קצת פחות בלגן.
לצורך ההשוואה ניצור שתי טבלאות זהות ובכל אחת 10,000,000 שורות ובכל אחת עמודת מחרוזת בת 7 תווים (מדובר בכל הצירופים של 7 ספרות):

If Object_ID('T_Try1','U') Is Not Null Drop Table T_Try1;

 

With Nm As

(Select    0 N

Union All

Select    N+1

From    Nm

Where    N<9)

Select    Concat(Nm1.N,Nm2.N,Nm3.N,Nm4.N,Nm5.N,Nm6.N,Nm7.N) N

Into    T_Try1    

From    Nm Nm1

Cross Join Nm Nm2

Cross Join Nm Nm3

Cross Join Nm Nm4

Cross Join Nm Nm5

Cross Join Nm Nm6

Cross Join Nm Nm7;

 

If Object_ID('T_Try2','U') Is Not Null Drop Table T_Try2;

 

With Nm As

(Select    0 N

Union All

Select    N+1

From    Nm

Where    N<9)

Select    Concat(Nm1.N,Nm2.N,Nm3.N,Nm4.N,Nm5.N,Nm6.N,Nm7.N) N

Into    T_Try2    

From    Nm Nm1

Cross Join Nm Nm2

Cross Join Nm Nm3

Cross Join Nm Nm4

Cross Join Nm Nm5

Cross Join Nm Nm6

Cross Join Nm Nm7;

כעת נוסיף לשניה עמודה מחושבת Persisted (כלומר- תוצאות החישוב ישמרו בעמודה ולא יתבצעו תוך כדי שליפה), שתכלול את מכפלת המספרים הראשונים שיחליפו את הספרות. כלומר- את 0 נחליף בראשוני הראשון (2), את 1 בראשוני השני (3), וכך הלאה עד 9 שנחליף בראשוני העשירי (29); ואת 7 המספרים הראשוניים שנקבל כנגד 7 הספרות – נכפיל זה בזה.
מה נרוויח מכך? אם נחפש מחרוזת שמופיעות בה הספרות 01, אזי המכפלה בעמודה המחושבת תתחלק בוודאי ב-6=3*2. זה תנאי הכרחי אך לא מספיק, שכן לא ברור באיזה מקום ובאיזה סדר הספרות יופיעו, אך זה יאפשר לבצע סינון ראשוני.

Alter Table T_Try2 Add M As Cast(Choose(SubString(N,1,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,2,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,3,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,4,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,5,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,6,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))*

                        Cast(Choose(SubString(N,7,1)+1,2,3,5,7,11,13,17,19,23,29) As Decimal(38,0))

                        Persisted;

Go

הפונקציה Choose שהתווספה ב-2012 מאפשרת להחליף בקלות כל ספרה בראשוני המתאים, ואני משתמש ב-Decimal38 כי הוא מאפשר לשמור את המספרים הכי גדולים. במקרה זה, המספר הכי גדול יהיה 29 בחזקת 7 שזה כ-17 מיליארד, ואם נרחיב את המחרוזת – מהר מאוד “נדגדג” את גבולות האפשר.

ניסיון ראשון, נחפש מחרוזות בהן יש 01:

Declare    @N Varchar(7)='01';

Declare    @M BigInt=2*3;

 

Set        Statistics IO On;

Set        NoCount On;

Print    Concat('0',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

Select    Count(*)

From    T_Try1

Where    N Like Concat('%',@N,'%');

 

Print    Concat('1',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

Select    Count(*)

From    T_Try2

Where    M%@M=0

        And N Like Concat('%',@N,'%');

 

Print    Concat('2',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

Set        Statistics IO Off;

Go

image
החיפוש הראשון נמשך 1.933 שניות, והשני 1.830 לטובת השני, אם כי ההפרש לא גדול.
ננסה כעת עם מחרוזת בת 6 ספרות:

Declare    @N Varchar(7)='931031';

Declare    @M Decimal(38,0)=29*7*3*2*7*3;

Set        Statistics IO On;

Set        NoCount On;

Print    Concat('0',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

 

Select    Count(*)

From    T_Try1

Where    N Like Concat('%',@N,'%');

 

Print    Concat('1',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

Select    Count(*)

From    T_Try2

Where    M%@M=0

        And N Like Concat('%',@N,'%');

 

Print    Concat('2',Format(GetDate(),', yyyyMMdd HH:mm:ss.fff'));

Set        Statistics IO Off;

Go

image

החיפוש הראשון נמשך 1.934 שניות והשני 1.250 שניות, וזה כבר הרבה יותר משמעותי.

נסכם כך:

  • חישוב מודולו (=שארית) הרבה יותר מהיר מחיפוש טקסטואלי של תת מחרוזת במחרוזת.
  • ככל שהמחרוזת ותת המחרוזת ארוכות יותר, חישוב השארית יהיה מהיר יותר יחסית לחיפוש הטקסטואלי.
  • החיפוש המחושב מצמצם את האוכלוסיה שיש לבצע בה חיפוש טקסטואלי, אך לא מחליף אותו. במקרה הראשון החיפוש צומצם מ-10 מיליון לכ-2.5 מיליון, ובשני לכ-32 אלף.
  • ככל שיהיו יותר חזרות על אותה ספרה – החיפוש המחושב יהיה מהיר יותר (אם מחפשים את 1111111 החיפוש המחושב ימצא את התשובה הנכונה, אך אם מחפשים את 1234567 הוא יחזיר 840=!7 שורות שבהן יש לבצע חיפוש טקסטואלי).
  • גם בחיפוש מחושב לא ניתן להיעזר באינדקסים ויש לבצע Scan מלא על הטבלה, אך מצמצמים באופן ניכר פעולות “Scan” על המחרוזות ומחליפים בחישוב בודד של שארית.
הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *