लाखों प्रविष्टियों के साथ रैंकिंग

एक सिंगल डिस्क सीक लगभग 15ms का होता है, शायद सर्वर ग्रेड डिस्क के साथ थोड़ा कम। 500ms से कम का प्रतिक्रिया समय आपको लगभग 30 रैंडम डिस्क एक्सेस तक सीमित कर देता है। यह बहुत कुछ नहीं है।

मेरे छोटे लैपटॉप पर, मेरे पास विकास डेटाबेस है

[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb      |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)

और एक धीमी लैपटॉप डिस्क। मैंने

[email protected] [kris]> show create table score\G
*************************** 1. row ***************************
       Table: score
Create Table: CREATE TABLE `score` (
  `player_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `score` int(11) NOT NULL,
  PRIMARY KEY (`player_id`),
  KEY `score` (`score`)
) ENGINE=InnoDB AUTO_INCREMENT=2490316 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

यादृच्छिक पूर्णांक स्कोर और अनुक्रमिक खिलाड़ी_आईडी मानों के साथ। हमारे पास है

[email protected] [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)

डेटाबेस जोड़ी को बनाए रखता है (score, player_id) score में सूचकांक में क्रम score , क्योंकि एक InnoDB अनुक्रमणिका में डेटा एक BTREE में संग्रहीत होता है, और पंक्ति सूचक (डेटा सूचक) प्राथमिक कुंजी मान होता है, ताकि परिभाषा KEY (score) हो अंत होता है KEY(score, player_id) आंतरिक रूप से। स्कोर पुनर्प्राप्ति के लिए क्वेरी योजना को देखकर हम यह साबित कर सकते हैं:

[email protected] [kris]> explain select * from score where score = 17\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: score
         type: ref
possible_keys: score
          key: score
      key_len: 4
          ref: const
         rows: 29
        Extra: Using index
1 row in set (0.00 sec)

जैसा कि आप देख सकते हैं, key: score Using index . के साथ प्रयोग किया जा रहा है , जिसका अर्थ है कि कोई डेटा एक्सेस आवश्यक नहीं है।

किसी दिए गए स्थिर player_id . के लिए रैंकिंग क्वेरी मेरे लैपटॉप पर ठीक 500ms लेता है:

[email protected] [kris]>  select p.*, count(*) as rank 
    from score as p join score as s on p.score < s.score 
   where p.player_id = 479269\G
*************************** 1. row ***************************
player_id: 479269
    score: 99901
     rank: 2074
1 row in set (0.50 sec)

अधिक मेमोरी के साथ और तेज़ बॉक्स पर यह तेज़ हो सकता है, लेकिन यह अभी भी तुलनात्मक रूप से महंगा ऑपरेशन है, क्योंकि योजना बेकार है:

[email protected] [kris]> explain select p.*, count(*) as rank from score as p join score as s on p.score < s.score where p.player_id = 479269;
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref   | rows    | Extra                    |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
|  1 | SIMPLE      | p     | const | PRIMARY,score | PRIMARY | 4       | const |       1 |                          |
|  1 | SIMPLE      | s     | index | score         | score   | 4       | NULL  | 2097979 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
2 rows in set (0.00 sec)

जैसा कि आप देख सकते हैं, योजना में दूसरी तालिका एक इंडेक्स स्कैन है, इसलिए क्वेरी खिलाड़ियों की संख्या के साथ रैखिक रूप से धीमी हो जाती है।

यदि आप एक पूर्ण लीडरबोर्ड चाहते हैं, तो आपको जहां क्लॉज छोड़ना होगा, और फिर आपको दो स्कैन और द्विघात निष्पादन समय मिलेंगे। तो यह योजना पूरी तरह से धराशायी हो जाती है।

यहां प्रक्रियात्मक होने का समय:

[email protected] [kris]> set @count = 0; 
    select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ;
...
|   2353218 | 99901 | 2075 |
|   2279992 | 99901 | 2076 |
|   2264334 | 99901 | 2077 |
|   2239927 | 99901 | 2078 |
|   2158161 | 99901 | 2079 |
|   2076159 | 99901 | 2080 |
|   2027538 | 99901 | 2081 |
|   1908971 | 99901 | 2082 |
|   1887127 | 99901 | 2083 |
|   1848119 | 99901 | 2084 |
|   1692727 | 99901 | 2085 |
|   1658223 | 99901 | 2086 |
|   1581427 | 99901 | 2087 |
|   1469315 | 99901 | 2088 |
|   1466122 | 99901 | 2089 |
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
...

क्योंकि यह एक प्रक्रियात्मक योजना है, यह अस्थिर है:

• आप LIMIT का उपयोग नहीं कर सकते, क्योंकि इससे काउंटर ऑफसेट हो जाएगा। इसके बजाय आपको यह सारा डेटा डाउनलोड करना होगा।
• आप वास्तव में क्रमबद्ध नहीं कर सकते। यह ORDER BY क्लॉज काम करता है, क्योंकि यह सॉर्ट नहीं करता है, लेकिन एक इंडेक्स का उपयोग करता है। जैसे ही आपको using filesort दिखाई देता है , काउंटर मान बेतहाशा बंद हो जाएंगे।

यह वह समाधान है जो एक निष्पादन योजना के रूप में एक NoSQL (पढ़ें:प्रक्रियात्मक) डेटाबेस के सबसे करीब आता है।

हम सबक्वेरी के अंदर NoSQL को स्थिर कर सकते हैं और फिर उस हिस्से को काट सकते हैं जो हमारे लिए रुचिकर है, हालांकि:

[email protected] [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where player_id = 479269;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|    479269 | 99901 | 2094 |
+-----------+-------+------+
1 row in set (0.00 sec)

[email protected] [kris]> set @count = 0; 
    select * from ( 
        select *, @count := @count + 1 as rank 
          from score 
         where score >= 99901 
      order by score desc 
    ) as t 
    where rank between 2090 and 2100;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
|   1387171 | 99901 | 2090 |
|   1286378 | 99901 | 2091 |
|    666050 | 99901 | 2092 |
|    633419 | 99901 | 2093 |
|    479269 | 99901 | 2094 |
|    329168 | 99901 | 2095 |
|    299189 | 99901 | 2096 |
|    290436 | 99901 | 2097 |
+-----------+-------+------+
8 rows in set (0.01 sec)

सबक्वेरी टी नाम की एड-हॉक टेबल के रूप में सेट किए गए पूर्व परिणाम को अमल में लाएगी, जिसे हम बाहरी क्वेरी में एक्सेस कर सकते हैं। क्योंकि यह एक एड-हॉक टेबल है, MySQL में इसका कोई इंडेक्स नहीं होगा। यह बाहरी क्वेरी में कुशलता से जो संभव है उसे सीमित करता है।

ध्यान दें कि कैसे दोनों प्रश्न आपके समय की कमी को पूरा करते हैं। ये है योजना:

[email protected] [kris]> set @count = 0; explain select * from ( select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ) as t where rank between 2090 and 2100\G
Query OK, 0 rows affected (0.00 sec)

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: <derived2>
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2097
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DERIVED
        table: score
         type: range
possible_keys: score
          key: score
      key_len: 4
          ref: NULL
         rows: 3750
        Extra: Using where; Using index
2 rows in set (0.00 sec)

दोनों क्वेरी घटक (आंतरिक, DERIVED क्वेरी और बाहरी BETWEEN बाधा) खराब रैंक वाले खिलाड़ियों के लिए धीमी हो जाएगी, और फिर आपके समय की बाधाओं का घोर उल्लंघन करेगी।

[email protected] [kris]> set @count = 0; select * from ( select *, @count := @count + 1 as rank from score where score >= 0 order by score desc ) as t;
...
2097152 rows in set (3.56 sec)

वर्णनात्मक दृष्टिकोण के लिए निष्पादन समय स्थिर है (केवल तालिका आकार पर निर्भर):

[email protected] [kris]> select p.*, count(*) as rank 
   from score as p join score as s on p.score < s.score 
   where p.player_id = 1134026;
+-----------+-------+---------+
| player_id | score | rank    |
+-----------+-------+---------+
|   1134026 |     0 | 2097135 |
+-----------+-------+---------+
1 row in set (0.53 sec)

आपका कॉल.