רוטר - MYSQL - וריאציה של בעיית ה greatest n per group

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"MYSQL - וריאציה של בעיית ה greatest n per group"

גירסת הדפסה

קבוצות דיון בניית אתרים נושא #10316	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 10316

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

22:24 15.10.11

MYSQL - וריאציה של בעיית ה greatest n per group

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

TABLE items (itemid, dateline)
TABLE itemtype (typeid, itemid)
הטבלה itemtype מייצגת את הסוגים של כל item.
כלומר, לכל item יכולים להיות כמה סוגים, לכן אם item מספר 1 הוא מסוגים 1, 2, ו 5, יהיו בטבלה itemtype שלוש רשומות כאלו:

INSERT INTO itemtype (typeid, itemid) VALUES (1, 1), (2, 1), (5, 1)
מה שאני מנסה לעשות זה להוציא עבור כל type את N הפריטים (items) החדשים (או באמצעות dateline, או בלי להשתמש בטבלה items, ופשוט להניח שככל שה itemid יותר גבוה ככה הפריט נוצר מאוחר יותר).

אשמח לעזרה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
בבקשה	הולנדי	17.10.11 00:18	1
לא נראה לי שהבנת את השאלה :\	נחמיה	17.10.11 01:53	2
אממ	HeaveN	17.10.11 11:28	3
הוא רוצה להוציא את ה-ITEM הכי חדש מכל TYPE.	Ice Cold	17.10.11 13:04	4
אז תוסיף שדה DATE או לפחות ID שיהיה AI	HeaveN	17.10.11 15:13	5
ליתר דיוק, N ה ITEMים החדשים מכל TYPE	נחמיה	18.10.11 00:11	6
תגובה	HeaveN	18.10.11 11:58	7
איזה בלאגן עשו פה.	Deuce	18.10.11 15:26	8
קיוויתי לתגובה שלך :)	נחמיה	18.10.11 17:38	9
שאלה מעניינת.	Deuce	18.10.11 19:03	10
האמת היא שלא נראה שהוספת אינדקס עוזרת...	נחמיה	18.10.11 19:35	11
מכתב	נחמיה	18.10.11 19:52	12
מכתב	Deuce	18.10.11 21:14	13
מכתב	נחמיה	18.10.11 22:09	14

הולנדי
חבר מתאריך 26.5.05
603 הודעות

00:18 17.10.11

1. בבקשה
בתגובה להודעה מספר 0

SELECT * FROM items AS Item
LEFT JOIN `itemstype` AS ItemT ON(
Item.item=ItemT.itemid
AND
ItemT.typeid = ''
)
ORDER BY Item .dateline ORDER DESC

https://www.xchef.co.il | אתר
בישולים חברתי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

01:53 17.10.11

2. לא נראה לי שהבנת את השאלה :\
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

HeaveN
חבר מתאריך 10.6.05
1974 הודעות

11:28 17.10.11

3. אממ
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 17.10.11 בשעה 11:33 בברכה, HeaveN

לפי מה שאני מבין אתה רוצה להוציא מהבטלה itemtype כמה items יש לכל type ?
אם כן אז

SELECT COUNT(itemid) as qty, typeid FROM itemtype GROUP BY typeid

תקבל שורה של qty שזה הכמות, ולידו את ה type שלו, גם שמתי לב שאתה רוצה את החדשים, אם יש לך פרמטר של DATE בטבלה, אז פשוט תוסיף WHERE או שתסדר אותם לפי תאריכים עם ORDER BY
אם לא הבנתי נכון תתקן אותי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק

13:04 17.10.11

4. הוא רוצה להוציא את ה-ITEM הכי חדש מכל TYPE.
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

HeaveN
חבר מתאריך 10.6.05
1974 הודעות

15:13 17.10.11

5. אז תוסיף שדה DATE או לפחות ID שיהיה AI
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

00:11 18.10.11

6. ליתר דיוק, N ה ITEMים החדשים מכל TYPE
בתגובה להודעה מספר 4

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

HeaveN
חבר מתאריך 10.6.05
1974 הודעות

11:58 18.10.11

7. תגובה
בתגובה להודעה מספר 6

ומה זה חדש בשבילך, שעה אחרונה? יום אחרון? שבוע אחרון? חודש אחרון?
ומה נמצא ב dateline ?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

15:26 18.10.11

8. איזה בלאגן עשו פה.
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 18.10.11 בשעה 15:31 בברכה, Deuce

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

SELECT TOP(N)
FROM itemtype
WHERE item_type = 1
ORDER BY itemid DESC

או באופן דומה עבור אורקל:

SELECT * FROM
(SELECT TOP(N)
FROM itemtype
WHERE item_type = 1
ORDER BY itemid DESC)
WHERE ROWNUM <= N

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

(1012,1)
(1010,1)
(1009,1)
(1011,2)
(1008,2)
(1005,2)

כאשר N = 3, יש לנו 2 סוגי פריטים ו-1012,1010,1009 הם הפריטים האחרונים מסוג 1 ובאופן דומה עבור פריט מסוג 2.
קודם כל באורקל יש לך קצת יותר כוח, כי אתה יכול להשתמש בפונקציות אנליטיות. אתה יכול לבצע משהו בסגנון:
rank() over ( partition by itemtype order by itemid desc) rank

ואז תוכל לשלוף פשוט את כל התוצאות עם rank <= N, לעשות group by פעמיים לפי typeid ולפי itemid וקיבלת את המבוקש.
סביר להניח שאנחנו לא מדברים על אורקל (ואם כן, אני מוכן להרחיב), אז ב-SQL אפשר לכתוב פרוצדורה שעוברת בלולאה על כל ה-types, מבצעת את השאילתה שכתבתי למעלה ומחזירה UNION בין כל הטבלאות.
אפשרות נוספת היא לכתוב שאילתה קצת מכוערת, אבל שאמורה לעבוד של מכפלה עצמית:

SELECT I1.*
FROM items AS I1
LEFT OUTER JOIN items AS I2
ON (I1.itemtype=I2.itemtype AND I1.itemid <= I2.itemid)
GROUP BY I1.itemtype, I1.itemid
HAVING COUNT(*) <= N
ORDER BY I1.itemtype

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

בהצלחה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

17:38 18.10.11

9. קיוויתי לתגובה שלך :)
בתגובה להודעה מספר 8

השאילתה בהחלט עובדת בצורה מעולה, תודה רבה!
תודה גם על ההסבר המקיף על האופציות באורקל ו SQL, טוב לדעת.
יש לי עוד שאלה אחת בנוגע לשאילתה, מה לדעתך יהיה האינדקס המתאים ביותר לטבלה, כדי להפוך את השאילתה הזאת ליעילה ביותר? אינדקס של itemtype ו itemid אני מניח?
אגב, אי אפשר להתחמק מ filesort? אין ברירה?
שוב, המון המון תודה!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

19:03 18.10.11

10. שאלה מעניינת.
בתגובה להודעה מספר 9

ראשית, אין בעד מה וכמו שאמרתי לך, זאת לא שאילתה יעילה במיוחד וככל שהנתונים ילכו ויצטברו, כך ייקח לה יותר זמן לחזור.
כמו כן אני מציין מראש שב-MYSQL אני פחות מבין () אבל יכול לתת המלצות.
נתחיל מ-filesort:
אם הוא מבצע את ה-filesort אחרי שכבר חזרו כל הנתונים (ז"א רק בגלל ה-order by) אז לא צריך להיות לך אכפת, זאת פעולה זולה.
אם הוא מבצע את ה-filesort לפני ה-join אז זה משפר לך את הביצועים, כי תחשוב שביצעת פעולה אחת כבדה (ו-filesort לא כזה כבד) ועכשיו הטבלה מסודרת ובמקום עבור כל רשומה לרוץ על כל הטבלה, אתה יכול לגשת מהר מאד לחיתוכים המתאימים.
הבעיה היא שאם אין אינדקסים על הטבלה, זה מאלץ את האופטימייזר של השליפה לבצע filesort, שזאת פעולה יחסית כבדה על טבלה גדולה. אם נשתמש באינדקסים על itemid לבדו, ייתכן שהוא לא יבצע filesort (ואם כן, אז הוא לא אמור לבצע על כל הטבלה) ואם תוסיף אינדקס גם עם ה-itemtype (שזה פחות קריטי לדעתי), הוא לא אמור לבצע filesort בכלל, אבל אמור לפעמים זה שם של דג.
בסופו של דבר הכל שיקולים של קריאה וכתיבה וככל שיש יותר אינדקסים, כך הכתיבה איטית יותר.
מכיוון שמדובר בטבלה יחסית קטנה, אין שום בעולם שבתור התחלה לא תשים אינדקס (ואפילו PRIMARY KEY) על itemid ותראה איך זה משפיע. אני לא חושב שיש צורך לשים גם על itemtype כי כאשר יהיה לך אינדקס על itemid, תוכל מהר מאד להצלבה בין הטבלאות והבדיקה של ה-itemtype היא מהירה מאד.
בנוסף אני ממליץ (וזה נכון באופן כללי) לחלק את הטבלה למחיצות לפי תאריכים, כי אם למשל אתה יודע שהנתונים של חודש אחורה לא מעניינים אותך ויש לך מחיצות לפי חודשים ותשלוף חודש אחורה, תוכל לחתוך מהר מאד חלק גדול מהטבלה.

תעדכן אותי לגבי הביצועים, זה תמיד מעניין

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

19:35 18.10.11

11. האמת היא שלא נראה שהוספת אינדקס עוזרת...
בתגובה להודעה מספר 10

זמן הריצה של השאילתה ממש ארוך כשמספר הרשומות גדול, וזה כשאני מגדיר אינדקס על השדות typeid ו itemid. אם אני מגדיר אינדקס רק על itemid, זה בכלל לא מגיב לי דרך ה PHPMYADMIN (כלומר זמן הריצה הוא כנראה לכיוון הכמה דקות, אז אני אפילו לא אנסה מה command line).

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

19:52 18.10.11

12. מכתב
בתגובה להודעה מספר 10

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

SET @count := -1, @typeid := 0;
SELECT
typeid,
itemid
FROM
(SELECT typeid, itemid FROM test ORDER BY typeid, itemid DESC) AS x
WHERE
IF(typeid != @typeid, @count := -1, 0) IS NOT NULL
AND IF(typeid != @typeid, @typeid := typeid, typeid) IS NOT NULL
AND (@count := @count + 1) < 4

עם זאת, לא לגמרי הבנתי אותו
אז אם בא לך אולי להסביר, אני אשמח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

21:14 18.10.11

13. מכתב
בתגובה להודעה מספר 12

כמו שאמרתי לך, הכי טוב זה ליצור מעין פרוצדורה או קטע קוד שעובר בלולאה על התוצאות.
פה זה קצת תחכום כי זה עדיין שאילתה, אבל שאילתה יחסית מתקדמת.
זה כתוב בצורה לא כ"כ יפה, ניתן היה לכתוב את זה בצורה אלגנטית יותר בלי כל ה-IS NOT NULL.
הרעיון בכל אופן הוא כזה:
אתה מסדר את הטבלה במעין מחיצות שכל מחיצה היא של typeid אחר.
אתה מאפס מונה (count = -1) ומאפס סוגים (typeid = 0) ואז אתה מתחיל לרוץ רשומה אחרי רשומה (כאשר הן מסודרות להזכירך לפי המחיצה) ומבצע את הדבר הבא:
אם הגעת למחיצה חדשה (ה-typeid שאני אוגר הוא לא ה-typeid הנוכחי), אז תאפס את המונה, אחרת זה מחזיר 0 ו-0 is not null וממשיכים. כמו כן, תעדכן את ה-typeid להיות ה-typeid הנוכחי. כמקודם, אם אנחנו במסגרת הסכימה אז משוערך typeid שהוא לא NULL.
לבסוף, הגדל את המונה ב-1 ואם הערך קטן מ-N, כלומר אני נמצא על רשומה במחיצה שקטנה מ-N, אז תוסיף אותה לתוצאה.

פתרון אלגנטי.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

נחמיה

חבר מתאריך 24.5.05
5984 הודעות, 3 פידבק

22:09 18.10.11

14. מכתב
בתגובה להודעה מספר 13

אני חייב לומר שלא חשבתי לשלוף את כל הרשומות ולהוציא את אלה שאני צריך ב PHP.
בדקתי את זה עכשיו, סתם כדי לראות מה הביצועים כשמדובר ב 10000 איטרציות, והתוצאות די הפתיעו אותי, מהירות מתקבלת לחלוטין.
מה שכן, השאילתה עם המשתנים (תודה על ההסבר אגב) עדיין יותר מהירה פי 20 בערך (0.05~ מול 0.0025~), אז אני מניח שאלך עם השאילתה.
תודה רבה לך שוב על העזרה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד