Optimisation par table de cache spatiale et temporelle

**SuperCed** · 24/09/2019, 11h08

Hello,

aujourd’hui, je stocke des points (longitude, latitude) avec un timestamp, sessionID et une mapID.

J'ai 2 types de requête :
Une qui récupère dans un intervalle de temps un nombre de session différentes par petits intervalles de temps.
Ca va me produire un graph temporel ensuite coté front-end.

Une autre requête qui récupère des ensembles de points (aggrégés par environ 1 mètre) dans un intervalle de temps, et groupé aussi par intervalle de temps.
Ceci est ensuite affiché sur une carte.

En gros, je vais vous mettre les requêtes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
SELECT ROUND(p.lon * 100000) AS lon_int, ROUND(p.lat * 100000) AS lat_int,
        	 ROUND(UNIX_TIMESTAMP(p.timestamp)/60) AS ts_minute,
        	  COUNT(*) AS position_nb
        FROM `map_sessions` ms
        JOIN positions p
            ON (ms.id=p.`map_session_id`
            )
        WHERE ms.map_id IN (57)
        AND p.timestamp BETWEEN '2019-08-31 12:00:00' AND '2019-09-02 12:00:00'
		GROUP BY ts_interval, lon_int, lat_int
        ORDER BY ts_interval

Ici, on a un groupement d'environ 1 mètre pour les lat/lng, et 1 minute pour le temps.
Mais pour le temps, cela peut varier en fonction de l'intervalle considéré. Exemple, sur1 jour, on aura un intervalle de 24*60*60 / 100 = 864.

Voici l'autre type de requête qu'on peut avoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
SELECT ROUND(UNIX_TIMESTAMP(p.timestamp) / 60) AS ts_interval,
        COUNT(DISTINCT ms.id) AS session_nb,
        SUM(UNIX_TIMESTAMP(ms.session_stop)-UNIX_TIMESTAMP(ms.session_start)) AS diff
        FROM `map_sessions` ms
        JOIN positions p
            ON (ms.id=p.map_session_id)
 
        WHERE ms.map_id IN (196)
        AND p.timestamp > '2019-08-31 01:00:00' AND p.timestamp <= '2019-09-05 12:00:00'
        GROUP BY ts_interval   
        ORDER BY ts_interval ASC

En gros, c'est un peu pareil, mais on compte les sessions différentes et on prend toutes les positions possibles.

J'utilise des double pour stocker les lat/lng. J'utilise un datetime pour le timestamp.

Et voici le souci :
quand on a quelques dizaines de milliers de lignes, ça passe bien, mais quand on passe sur des centaines de milliers de lignes, ça commence à prendre quelques secondes (10s environ).

Je cherche donc à optimiser tout ça.
Voici plusieurs pistes que je pourrais explorer :
- faire des tables de cache avec agrégat, pré groupement au mètre, et à la minute (on ne descend jamais en dessous de la minute sur mes requêtes).
- Passer dans cette même table les lat/lng en entier, le temps en entier de type minute.

- Avoir plusieurs tables de cache avec différents niveau de groupement de temps... ???

- Utiliser des tables partitionnées ??? Partitionner par map_id/map_session_id, ou par année ? mois ? jour ?

Qu'en pensez vous ?

Merci!

**aieeeuuuuu** · 24/09/2019, 14h05

bonjour,

quelles sont les structures des tables et indexes ?

essayez en posant l'index suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

CREATE INDEX IX_position_session_ts ON positions (map_session_id, timestamp, lon, lat)

**SuperCed** · 24/09/2019, 14h12

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
CREATE TABLE `map_sessions` (
  `id` int(10) UNSIGNED NOT NULL,
  `session_id` int(10) UNSIGNED DEFAULT NULL,
  `map_id` int(10) UNSIGNED DEFAULT NULL,
  `session_start` datetime NOT NULL,
  `session_stop` datetime NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
 
ALTER TABLE `map_sessions`
  ADD PRIMARY KEY (`id`),
  ADD UNIQUE KEY `unique_map_session` (`session_id`,`map_id`),
  ADD KEY `IDX_F892AB34613FECDF` (`session_id`),
  ADD KEY `IDX_F892AB3453C55F64` (`map_id`),
  ADD KEY `tm_start_idx` (`session_start`),
  ADD KEY `tm_stop_idx` (`session_stop`);
 
ALTER TABLE `map_sessions`
  MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT;
 
ALTER TABLE `map_sessions`
  ADD CONSTRAINT `FK_F892AB3453C55F64` FOREIGN KEY (`map_id`) REFERENCES `maps` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `FK_F892AB34613FECDF` FOREIGN KEY (`session_id`) REFERENCES `sessions` (`id`);
 
CREATE TABLE `positions` (
  `id` int(10) UNSIGNED NOT NULL,
  `map_session_id` int(10) UNSIGNED DEFAULT NULL,
  `map_floor_id` int(10) UNSIGNED DEFAULT NULL,
  `map_tracked_item_id` int(10) UNSIGNED DEFAULT NULL,
  `timestamp` datetime NOT NULL,
  `lon` double NOT NULL,
  `lat` double NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
 
ALTER TABLE `positions`
  ADD PRIMARY KEY (`id`),
  ADD KEY `IDX_D69FE57C7440A9D1` (`map_session_id`),
  ADD KEY `IDX_D69FE57CE7B44FC5` (`map_floor_id`),
  ADD KEY `IDX_D69FE57CE108CB5E` (`map_tracked_item_id`),
  ADD KEY `tm_idx` (`timestamp`);
 
ALTER TABLE `positions`
  MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT;
 
ALTER TABLE `positions`
  ADD CONSTRAINT `FK_D69FE57C7440A9D1` FOREIGN KEY (`map_session_id`) REFERENCES `map_sessions` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `FK_D69FE57CE108CB5E` FOREIGN KEY (`map_tracked_item_id`) REFERENCES `map_tracked_items` (`id`) ON DELETE CASCADE,
  ADD CONSTRAINT `FK_D69FE57CE7B44FC5` FOREIGN KEY (`map_floor_id`) REFERENCES `map_floors` (`id`) ON DELETE CASCADE;

**SuperCed** · 24/09/2019, 14h25

Et hop, un explain de la première requête (via phpmyadmin) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
id 	select_type 	table 	type 	possible_keys 	key 	key_len 	ref 	rows 	Extra 	
1 	SIMPLE 	ms 	ref 	PRIMARY,IDX_F892AB3453C55F64 	IDX_F892AB3453C55F64 	5 	const 	7471 	Using temporary; Using filesort
1 	SIMPLE 	p 	ref 	IDX_D69FE57C7440A9D1,tm_idx 	IDX_D69FE57C7440A9D1 	5 	sdk_stat.ms.id 	53 	Using where

Un profilage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
Copying To Tmp Table On Disk 	3,8 s 	56,69% 	1 	3,8 s
Copying To Tmp Table 	2,5 s 	37,06% 	1 	2,5 s
Sorting Result 	354,2 ms 	5,23% 	1 	354,2 ms
Converting HEAP To Aria 	58,4 ms 	0,86% 	1 	58,4 ms
Sending Data 	5,8 ms 	0,09% 	1 	5,8 ms
Starting 	158 µs 	<0,01% 	1 	158 µs
Statistics 	92 µs 	<0,01% 	1 	92 µs
Creating Tmp Table 	46 µs 	<0,01% 	1 	46 µs
End 	38 µs 	<0,01% 	1 	38 µs
Updating Status 	37 µs 	<0,01% 	1 	37 µs
Opening Tables 	29 µs 	<0,01% 	1 	29 µs
Init 	27 µs 	<0,01% 	1 	27 µs
Preparing 	25 µs 	<0,01% 	1 	25 µs
Optimizing 	18 µs 	<0,01% 	1 	18 µs
Freeing Items 	18 µs 	<0,01% 	1 	18 µs
Unlocking Tables 	14 µs 	<0,01% 	1 	14 µs
Checking Permissions 	12 µs 	<0,01% 	1 	12 µs
Query End 	10 µs 	<0,01% 	1 	10 µs
Cleaning Up 	9 µs 	<0,01% 	1 	9 µs
Removing Tmp Table 	8 µs 	<0,01% 	1 	8 µs
After Opening Tables 	5 µs 	<0,01% 	1 	5 µs
System Lock 	4 µs 	<0,01% 	1 	4 µs
Table Lock 	4 µs 	<0,01% 	1 	4 µs
Closing Tables 	4 µs 	<0,01% 	1 	4 µs
Executing 	3 µs 	<0,01% 	1 	3 µs

6.8sec

Et maintenant, pareil avec l'index proposé (je l'ai appelé 'test') :

4.8729 ---> on a déjà gagné pas mal gratuitement ou presque !

explain :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
id 	select_type 	table 	type 	possible_keys 	key 	key_len 	ref 	rows 	Extra 	
1 	SIMPLE 	ms 	ref 	PRIMARY,IDX_F892AB3453C55F64 	IDX_F892AB3453C55F64 	5 	const 	7471 	Using temporary; Using filesort
1 	SIMPLE 	p 	ref 	IDX_D69FE57C7440A9D1,tm_idx,test 	test 	5 	sdk_stat.ms.id 	51 	Using where; Using index

profilage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
ÉtatDocumentation
	Temps total
	% Temps
	Appels
	Temps moyen
Copying To Tmp Table On Disk 	2,8 s 	59,19% 	1 	2,8 s
Copying To Tmp Table 	1,6 s 	33,00% 	1 	1,6 s
Sorting Result 	316,7 ms 	6,63% 	1 	316,7 ms
Converting HEAP To Aria 	47,2 ms 	0,99% 	1 	47,2 ms
Sending Data 	4,4 ms 	0,09% 	1 	4,4 ms
Statistics 	95 µs 	<0,01% 	1 	95 µs
Starting 	80 µs 	<0,01% 	1 	80 µs
End 	71 µs 	<0,01% 	1 	71 µs
Creating Tmp Table 	42 µs 	<0,01% 	1 	42 µs
Updating Status 	33 µs 	<0,01% 	1 	33 µs
Opening Tables 	26 µs 	<0,01% 	1 	26 µs
Init 	22 µs 	<0,01% 	1 	22 µs
Preparing 	21 µs 	<0,01% 	1 	21 µs
Optimizing 	16 µs 	<0,01% 	1 	16 µs
Unlocking Tables 	15 µs 	<0,01% 	1 	15 µs
Freeing Items 	15 µs 	<0,01% 	1 	15 µs
Removing Tmp Table 	13 µs 	<0,01% 	1 	13 µs
Query End 	10 µs 	<0,01% 	1 	10 µs
After Opening Tables 	5 µs 	<0,01% 	1 	5 µs
Closing Tables 	5 µs 	<0,01% 	1 	5 µs
Cleaning Up 	5 µs 	<0,01% 	1 	5 µs
Checking Permissions 	4 µs 	<0,01% 	1 	4 µs
System Lock 	4 µs 	<0,01% 	1 	4 µs
Table Lock 	4 µs 	<0,01% 	1 	4 µs
Executing 	3 µs 	<0,01% 	1 	3 µs

Bien sur, j'ai utilisé la clause SQL_NO_CACHE dans ma requête...

**SuperCed** · 24/09/2019, 14h34

Envoyé par aieeeuuuuu

bonjour,

quelles sont les structures des tables et indexes ?

essayez en posant l'index suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

CREATE INDEX IX_position_session_ts ON positions (map_session_id, timestamp, lon, lat)

Juste une question, tu es certain que le lat et le lon servent dans l'index ?
Car il n'y a pas de recherche dessus en direct, ça passe d'abord par une fonction.
Du coup, je pense que le début de l'index est utilisé, mais pas le reste (lat lon).

Je vais refaire quelques tests...

**aieeeuuuuu** · 24/09/2019, 16h45

j'ai ajouté lat et lon dans dans l'index afin que celui-ci couvre la première requête, et éviter tout accès à la table positions

**SuperCed** · 25/09/2019, 11h54

Envoyé par aieeeuuuuu

j'ai ajouté lat et lon dans dans l'index afin que celui-ci couvre la première requête, et éviter tout accès à la table positions

Pareil, dans la première requête, je ne pense pas que le lat/lon soit utilisé dans l'index, car il y a une fonction à appliquer sur lat/lon, donc l'index ne doit pas être utile.
Ca montre aussi ça dans mes tests.

En fait, pour que ce soit utile pour le GROUP BY, il faudrait que la donnée ne soit pas retraitée par une fonction.

**aieeeuuuuu** · 25/09/2019, 14h47

lat et lon ne sont pas utilisé lors de la recherche des lignes dans l'index, en effet.
En revanche, une fois que ces lignes sont trouvées, le fait que ces colonnes fasse parti de la clef évite de devoir aller ensuite dans la table chercher les lignes qui correspondent pour trouver leur valeur : l'index suffit pour répondre à la requete (sans accés à la table). on parle alors d'index couvrant.

Dans certains SGBDR comme SQL Server, il est possible d'ajouter des colonne en tant que colonne incluse (elle sont stockées dans les pages d'index, mais non ordonnées) justement pour cela.

Car en dessous d'une certain seuil de sélectivité de l'index, il peut ne plus être utilisé, le cout des recherches dans la table devenant supérieur au gain apporté par l'utilisation de l'index...

Optimisation par table de cache spatiale et temporelle

Requêtes MySQL

Vue hybride

Discussions similaires

Partager

Partager