en-UShe-IL
You are here:   Blog
Register   |  Login

Blog Archive:

Maximize
* Can be used in order to search for older blogs Entries

Search in blogs


Blog Categories:

Maximize
* Can be used in order to search for blogs Entries by Categories

Blog Tags:

Maximize
* Can be used in order to search for blogs by keywords

TNWikiSummit


Awared MVP 


 


Microsoft® Community Contributor 


Microsoft® Community Contributor


 Read first, before you you use the blog! Maximize
דצמ25

Written by: ronen ariely
25/12/2010 13:25 RssIcon

בחירת רשומה אקראית מטבלה

* עדכון: הבלוג פוצל ל 2 בלוגים. הראשון שישמר במיקום המקורי הנוכחי ידון בבחירה של רשומה אקראית מטבלה. הבלוג השני ידון בשליפת הרשומות (כולן או מקצתן) בסדר אקראי.

במשך ההסבר בכללי אציג קוד התואם לשרתי MS-SQL. עם זה מדריך זה מופנה לכל שרתי ומסדי הנתונים השונים ומציג רעיון מחשבתי יותר מקוד ספציפי. בהמשך אציג פתרונות עבור שרתים ומסדי נתונים שונים.

נדון בשלושה מקרים שונים לשליפת רשומה אקראית מבין כל הרשומות. ננסה לתת פתרון שמצד אחד יהיה פשוט מבחינת הלוגריתמים וההבנה שלו ומצד שני יהיה יעיל. נתחיל את הדיון במקרה הפשוט ביותר בו יש לנו שדה מפתח ייחודי מסוג IDENTITY ללא רווחים. נעבור בהדרגה לדון במצב בו יש לנו שדה ייחודי מספרי כלשהו (מקרה כללי יותר של מצב של שדה ייחודי IDENTITY עם רווחים במספור), נתקדם למקרה השני בו נדון כשיש לנו שדה ייחודי טקסטואלי ומכאן נעבור למקרה האחרון בו נדון במצב כללי בו לא  נעזרים בנתונים קיימים בטבלה (יתאים לכל טבלה ולכל סוגי השדות).

נדגיש כמובן שהעדיפות תהיה לשימוש בשיטות הספציפיות ורק אם אין לנו ברירה נעלה לשיטה כללית יותר עד למקרה האחרון.

בחירה של רשומה אקראית משדה IDENTITY

הערה: פעם נוספת אני אדגיש (וארמוז על המשך המדריך) שבהמשך נראה שיטות נוספות המתאימות למקרים יותר כלליים כגון השימוש בהוספת עמודה חדשה לבחירה שלנו. בעמודה זו נוכל להכניס תכנים רנדומאליים.  שיטה זו משום מה נפוצה ביותר ועושים בה שימוש בטעות גם במקרים כגון המצב הנוכחי בו מדובר בפעולה כבדה מאוד כשהטבלה גדולה.

נייצר טבלה חדשה:

/**********************************************************/

/************************ using the Demo DataBase *********/

/**********************************************************/

use qq

go

 

/**********************************************************/

/******************* Solution for Numbers Primary Key *****/

/**********************************************************/

CREATE TABLE [MyTbl](

      [id] [int] IDENTITY NOT NULL

      ,[txt] nvarchar(10)

) ON [PRIMARY]

GO

נכניס כמה נתונים לדוגמה לטבלה:

insert [MyTbl] ([txt])

values

      ('q'),

      ('w'),

      ('e'),

      ('r'),

      ('t'),

      ('y'),

      ('u'),

      ('i'),

      ('o'),

      ('p'),

      ('a'),

      ('s'),

      ('d')

GO

 

 נוודא מה הנתונים שיש לנו בטבלה:

select * from [MyTbl]

GO

 

 נעזר בפונקציה המובנית RAND על מנת לבחור מספר אקראי בין המספר הכי קטן למספר הכי גדול שיש לנו בטבלה. לאחר מזה כל מה שיהיה עלינו לבצע זה לבחור את הרשומה עם המספר הרנדומלי שלנו:

declare @Min int, @Max int, @Rnd int

select @Min = MIN(id),@Max = MAX(id) from [MyTbl]

Select @Rnd = Cast(((@Max + 1) - @Min) * Rand() + @Min As int)

select @Min,@Max,@Rnd

--- Now the select query can be:

select * from [MyTbl] where id = @Rnd

GO

אך מה קורה במצב הנורמאלי שיש לנו שדה IDENTITY? עם הזמן יווצר רווחים במספור הרשומות בשל מחיקה של רשומות למשל. הפתרון במקרה זה לא יהיה שונה בהרבה. מכיוון שמדובר בשדה ייחודי הרי שנוכל לבחור את הרשומה הכי קרובה למספר הרנדומלי שלנו (נניח קרובה מלמעלה ז"א שווה או גדולה יותר מהמספר שלנו)

 declare @Min int, @Max int, @Rnd int

select @Min = MIN(id),@Max = MAX(id) from [MyTbl]

Select @Rnd = Cast(((@Max + 1) - @Min) * Rand() + @Min As int)

select @Min,@Max,@Rnd

--- Now the select query can be:

select top 1 * from [MyTbl] where id >= @Rnd order by id

GO

* הערה: אם קיים לנו בטבלה שדה מספרי ייחודי שאינו מסוג IDENTITY הרי ששיטה זו תעבוד בצורה זהה לחלוטין. מבחינת השאילתה מדובר בשדה הזהה לשדה IDENTITY אשר יש בו רווחים.

בחירה של רשומה אקראית משדה ייחודי טקסטואלי (מאונדקס)

בחלק זה נראה את האלגוריתמים הכי מורכב שיש לנו במדריך. נציג יתרונות וחסרונות ונקודות למחשבה שונות של שיטה זו. מצד אחד השיטה שתוצג יכולה לתת לנו שיפור מאוד ניכר ביחס לשימוש בשיטות כלליות יותר אך לעיתים שיטה זו אינה מיטבית ועדיף לעבור לשימוש בשיטות הכלליות יותר בלי להשתמש בשדה הנוכחי. הדבר תלוי במספר הרשומות שלנו, באינדוקס הטבלה ובמבנה הנתונים ובנתונים שיש לנו וההחלטה באיזה שיטה לבחור אינה זהה תמיד

הרעיון הראשון בו נדון יהיה שימוש באותו אלגוריתמים שביצענו במקרה של מספרים עבור שרשרת תווים. בשלב הראשון נמצא את הערך הכי קטן והערך הכי גדול שיש לנו בטבלה בשדה הייחודי שלנו. בשלב הבא נבנה שרשרת של תווים שגודלה בין ערכים אלו (זה לא מיידי הפעם כי יש חשיבות לנקודות כמו אורך שרשרת ועוד נתונים בהם נדון או נראה) ובשלב האחרון נבצע בחירה של הנתון הכי קרוב לשרשרת הרנדומאלית שלנו. בואו נתחיל בביצוע...

נייצר טבלה חדשה, נכניס כמה נתונים לדוגמה ונציג את הנתונים שיש לנו לשם בדיקה. הפעם בחרתי לגוון ולבצע את העבודה בעזרת משתנה טבלאי ולא בזרת טבלה חדשה במסד הנתונים:

/**********************************************************/

/******************* Solution for Strings Primary Key *****/

/**********************************************************/

declare @TblString as table([PrimeryKey] varchar(10))

 

insert @TblString

select 'a' union

select 's' union

select 'ds' union

select 'f' union

select 'g' union

select 'h' union

select 'j' union

select 'k' union

select 'fds'

 

select * from @TblString

בניגוד למספרים צריך לחשוב כאן על מצבים הרבה יותר מורכבים. השוואה של מספרים נעשית על ידי השוואה של הערך הכולל של המספר. כך למשל המספר 10 יהיה תמיד גדול יותר מהמספר 9. דבר זה אינו נכון לגבי שרשרת תווים. ההתייחסות לשרשרת תווים היא כאל אוסף של תווים (מכאן גם אנשי פיתוח יזכרו שניתן לבצע פעולת foreach על שרשרת תווים כמו שעובדים עם מערכים למשל).

כיצד מבוצעת ההשוואה של אוספים? השוואה בין 2 שרשראות תווים נעשית על ידי השוואה של האיבר הראשון בשרשרת ראשונה אל האיבר הראשון בשרשרת השנייה ורק אז עוברים לאיבר השני בשרשרת ראשונה שמושווה אל האיבר השני בשרשרת השנייה וכן הלאה...

אם נחזור לחשוב על המספרים 10 ו 9 כשרשראות תווים הרי שנקבל שהתו הראשון שמושווה הוא האחד אל ה 9 ולכן נקבל ש 10 קטן יותר מ 9.

מכיוון שאנו עובדים עם משתנה זמני ולא טבלה אמיתית במסד הנתונים הרי שאת כל החלק הבא עלינו תמיד להריץ ביחד עם החלק מעל. ההפרדה נעשית רק לצורך ההסבר.

declare @MinString as varchar(10),@MaxString as varchar(10)

select @MinString = MIN([PrimeryKey]), @MaxString = MAX([PrimeryKey]) from @TblString

 

-- כפי שנראה בהמשך ההתייחסות שלנו לאות הראשונה ולאות האחרונה באלגורתמים שלנו שונה מעט

-- מיון נעשה קודם על האות הראשונה

-- לכן האות הראשונה הכי גדולה תהיה באיבר הכי גדול

declare @MaxLeftChar as int  = ASCII(LEFT(@MaxString,1))

-- והאות הראשונה הכי קטנה תהיה באיבר הכי קטן

declare @MinLeftChar as int = ASCII(LEFT(@MinString,1))

-- האות האחרונה הכי גדולה תהיה שוב בשרשרת הכי גדולה

declare @MaxRightChar as int = ASCII(RIGHT(@MaxString,1))

 

-- נתחיל בייצור שרשרת אקראית על ידיד בחירה אקראית של מספר התווים בשרשרת התוצאה שלנו

declare @MaxLen as int

select @MaxLen = MAX(LEN([PrimeryKey])) from @TblString

declare @RandLen as int = (RAND()*(@MaxLen-1))+1

 

declare @RndString as varchar(10) = ''

 

-- ונתחיל לבנות את השרשרת האקראית שלנו על ידי לולאה כמספר התווים שעלינו לבחור

if @RandLen = 0

      BEGIN

            set @RndString = ''

      END

else if @RandLen = 1

      BEGIN

            set @RndString = @RndString + char(cast((RAND()*(@MaxLeftChar-@MinLeftChar))+@MinLeftChar as int))

      END

else

      BEGIN

            -- First Letter

            set @RndString = @RndString + char(cast((RAND()*(@MaxLeftChar-@MinLeftChar))+@MinLeftChar as int))

           

            -- All The Middle Letters

            declare @qq as int = 1

            while @qq < @RandLen - 1 Begin

                  set @RndString = @RndString + char(cast((RAND()*(122-97))+97 as int))

                  set @qq = @qq + 1

            End

           

            -- Last Letter

            set @RndString = @RndString + char(cast((RAND()*(@MaxRightChar-97))+97 as int))

      END

 

-- סיימנו את האלגורתמים המורכב שנראה ארוך בהסבר

-- אבל למעשה מבחינת משאבים הוא יכול להיות זניח לחלוטין ביחס לשיטות אחרות של בחירה כאשר נדון בטבלאות גדולות

 

-- זהו... עתה נוכל להריץ את הבחירה המיידית שלנו בצורה קלה ומהירה עד כדי זניחה אם הטבלה מאונדקסת טוב לפי שדה

select

      @MinString MinString

      ,@MinLeftChar MinChar

      ,@MaxLeftChar MaxLeftChar

      ,@MaxString MaxString

      ,@MaxRightChar MaxRightChar

      ,@MaxLen MaxLen

      ,@RandLen RandLen

      ,@RndString RndString

 

select top 1 * from @TblString where PrimeryKey >= @RndString

 

בחירה של רשומה אקראית ללא שימוש ברשומות קיימות

רעיון 1: ניתן ליישם את הדרכים המוצגות מעל בצורה עקיפה. כך למשל אם היינו יכולים לייצר לנו עמודה עם מספור רציף של הרשומות אז היינו יכולים את המקרה הראשון. פעולה זו קל לבצע למשל עם פונקצית ROW_NUMBER שיש לנו בשרת SQL. באחד הבלוגים בעבר הצגתי כיצד ניתן לבנות עמודה ממוספרת ללא שימוש בפונקציה ROW_NUMBER. שיטה זו תעבוד בכל מסד נתונים והלוגיקה שלה פשוטה מאוד.

רעיון 2: ניתן לבנות עמודה ממוספרת בכל מסד נתונים פשוט על ידי הוספת עמודת IDENDITY חדשה או להעביר את הנתונים לטבלה זמנית עם עמודה כזו ולבצע אינדוקס מתאים לשיפור המשך הפעולות.

רעיון 3: בטבלאות מאוד גדולות כל השיטות המוזכרות כאן עלולות לשרוש משאבים ולקחת זמן רב. אם לא ניתן לממש את השיטות הראשונות מומלץ מאוד לבדוק את הרעיון של שימוש ב tablesample שיכול להיות מיטבי במקרים של טבלאות גדולות מאוד. הפונקציה tablesample מחזירה לנו מדגם של נתונים בצורה רנדומלית. יש לשים לב שפונקציה זו עלולה להחזיר גם אפס רשומות מה שייצור לנו שגיאה בלוגיקה ולכן מומלץ לבחור מדגם שאינו קטן מדי.

SELECT TOP 1 * FROM table25million tablesample(1000 rows)

רעיון 4: רעיון זה השארתי לסיום גם מהסיבה שהוא אינו המיטבי בדרך וגם מהסיבה שהוא הנפוץ ביותר ברוב הבלוגים ברשת. הרעיון המרכזי מאחורי פתרון המוצג כאן הוא יצירה של שדה נוסף בזמן בחירת הנתונים, אשר הערכים שלו יקבעו בצורה רנדומאלית בזמן ריצה. לכן נוכל לבצע בחירה של הנתון הראשון כאשר מבצעים סידור לפי שדה זה. כך נקבל למעשה את שליפת רשומה אקראית. הלוג הבא מהווה את הבסיס לרעיון זה ומציג בצורה מלאה את הלוגיקה מאחורי הוספת שדה עם ערך רנדומלי: שליפת רשומות בסדר אקראי

כאמור אחרי שהצלחנו לבנות שדה רנדומאלי כל מה שנשאר לנו זה לבחור את הרשומה הראשונה לפי סידור שדה זה. 

Select a random row with MySQL:

SELECT id FROM MyTbl

ORDER BY RAND()

LIMIT 1

 

Select a random row with PostgreSQL:

SELECT id FROM MyTbl

ORDER BY RANDOM()

LIMIT 1

 

Select a random row with Microsoft SQL Server:

SELECT TOP 1 id FROM MyTbl ORDER BY NEWID()

SELECT TOP 1

      [id],NEWID() AS [RandomNumber]

FROM [MyTbl]

order by [RandomNumber]

-- הוספת ערך שלם רנדומלי

ABS(CAST(CAST(NEWID() AS VARBINARY) AS INT)) AS [RandomNumber]

 

Select a random row with IBM DB2

SELECT id, RAND() as MyRand

FROM MyTbl

ORDER BY MyRand FETCH FIRST 1 ROWS ONLY

 

Select a random record with Oracle:

SELECT id FROM

( SELECT id FROM MyTbl ORDER BY dbms_random.value )

WHERE rownum = 1

 

Select a random row with Access:

-- עובד טוב באקסס

Select id,rnd(id)

from MyTbl

order by rnd(id)

--ליתר ביטחון למנוע בעיה של זכירת תוצאות קודמות

select

    id

    ,rnd(id),datepart("s",now())

    ,CDbl(Now())

    ,rnd(1000*id*CDbl(now()))

from MyTbl

order by rnd(1000*id*CDbl(now()))

 

Select a random record with Any Database that use ROW_NUMBER:

select * from (

      SELECT [id],ROW_NUMBER() over (order by id) as MyRnd FROM [KMessagesTbl]

      ) MyTbl

where MyRnd = CAST(

      RAND() *

      ((SELECT COUNT(*) FROM [KMessagesTbl]) - 1 )

      AS INT) + 1

GO

 

Select a random record (more ways):

-- עובד מעולה ולוגיקה זו תעבוד בכל מסד נתונים לאחר התאמה של השאילתה

SELECT TOP 10

       [id]

       , RAND(

              -- כאן מגיע ערך מספרי הקובע את תוצאת הרנדום עבור הסשן הנוכחי

              --כל שימוש באותו ערך פנימי יביא את אותם תוצאות

              -- הדבר חשוב למשל כדי שנוכל להמשיך להישתמש בערך הרנדומלי שלנו

              --בהמשך השאילתה בלי שצריך להכניס אותו למשתנה

              1000         

              -- לכן אם הערך בתוך הרנדום משתנה על פי מספר הרשומה

              -- הרי שנקבל בכל רשומה בחירת מספר רנדומלי אחר

              *[id]

              --     ללא חלק זה אכן ייבחר ערך חדש בכל רשומה

              --     אבל הוא יהיה קבוע בכל פעם שנריץ את השאילתה

              --     מכיוון שהשרת שומר תוצאות שאילתות בקש

              --     לכן פשוט יש להוסיף פרמטר ברנדום שמשתנה בכל הרצה

              --     למשל הזמן הנוכחי

              *DATEPART(millisecond, GETDATE())

              ) as MyRnd

    FROM [KMessagesTbl]

    ORDER BY RAND(

              1000*[id]

              *DATEPART(millisecond, GETDATE())

              )

Go

 

 

נקודות נוספות למחשבה:

* השיטות הראשונות יעילות יותר כשאר קיים לנו מפתח ראשי ואינדקסים מוכנים כי אנחנו מבצעים פעולות על השדה הייחודי.

* בגישה הראשונה והשנייה אנו אכן בוחרים בצורה אקראית אבל הסבירות לקבל כל תוצאה לא זהה! ככל שיש יותר רווחים בין הנתונים בשדה לפיו בוחרים הרי שהמשקל יטה יותר לכיוון של לקבל תוצאה גדולה יותר. מכיוון שבבחירה האקראית שלנו אנחנו למעשה בוחרים ערך אקראי הכולל את הנתונים החסרים. כך למשל אם יש לנו נתון 1 ונתון 10 בלבד הרי שכל מספר בין 2 לבין 10 ייתן את התוצאה 10 בסינון שמבצעים אם עושים שימוש ב "גדול מ" והפוך אם נבחר ב"קטן מ"

* בדוגמה של השדה הטקסטואלי הצגתי רק פתרון  עם טקסט הבנוי מאותיות אנגליות קטנות. למעשה צריך לבדוק גם על מספרים ואותיות בכל שפה איתה עובדים. התוצאה כרגע לא תעבוד טוב אם יש מספר או אות גדולה בהתחלה או בסיום התוכן למשל. במדריך זה הצגתי רק את הלוגיקה של בניית שרשרת אקראית מאותיות קטנות כפתרון לדוגמה לשם הבנת הלוגיקה. למי שמעוניין החלק הבא יעזור להרחיב את הפתרון למספרים, לאותיות גדולות באנגלית ולעברית:

--numbers 0 – 9: CHAR 48-57

--En letters a – z: CHAR 97-122

--En letters A – Z: CHAR 65-90

--Heb letters א-ת: CHAR 224-250

 

 

* אם מדובר בשאילתה שרצה מספר רב של פעמים יש לבדוק כדאיות של בניית אינדקס על השדה הטקסטואלי שיתאים לשאילתות.

* אם קיים לנו שדה ייחודי טקסטואלי (בעיקר אם הוא גדול) ומדובר בטבלה גדולה מאוד הרי שביצוע חיפוש של רשומה אחת לפי טקסט יכולה להיות כבדה מאוד. אחת השיטות לעקוף את הבעיה היא שימוש ב Hash indexes. בשרת SQL לא מובנה לנו אינדקס מסוג זה אבל ניתן לייצר משהו זהה בקלות.

הרעיון הוא ליצור שדה מחושב נוסף בטבלה שיחושב מהשדות הטקסטואליים ועל שדה זה נוכל להקים אינדקס פשוט. את הפעולות נבצע על השדה המחושב ולא על השדה המקורי. הדוגמה הכי פשוט היא יצירת שדה מחושב לשם אינדקס בעזרת הפונקציה CHECKSUM.

ALTER TABLE MyTbl

ADD cs_Txt AS CHECKSUM(Txt);

GO

CREATE INDEX cs_Txt_index ON MyTbl (cs_Txt);

GO