Quel est le but de la définition d'une clé dans data.table?

J'utilise data.table et il existe de nombreuses fonctions qui m'obligent à définir une clé (par exemple X[Y]). En tant que tel, je souhaite comprendre ce que fait une clé afin de définir correctement les clés dans mes tables de données.

Une source que j'ai lue était ?setkey.

setkey()trie un data.tableet le marque comme trié. Les colonnes triées sont la clé. La clé peut être n'importe quelle colonne dans n'importe quel ordre. Les colonnes sont toujours triées par ordre croissant. Le tableau est modifié par référence. Aucune copie n'est effectuée, à l'exception de la mémoire de travail temporaire de la taille d'une colonne.

Ce que je retiens ici, c'est qu'une clé «trierait» la table data.table, ce qui aurait un effet très similaire à order(). Cependant, cela n'explique pas le but d'avoir une clé.

La FAQ data.table 3.2 et 3.3 explique:

3.2 Je n'ai pas de clé sur une grande table, mais le regroupement est toujours très rapide. Pourquoi donc?

data.table utilise le tri par base. C'est beaucoup plus rapide que les autres algorithmes de tri. Radix est uniquement pour les entiers, voir ?base::sort.list(x,method="radix"). C'est aussi une des raisons pour lesquelles setkey()c'est rapide. Lorsqu'aucune clé n'est définie, ou que nous groupons dans un ordre différent de celui de la clé, nous l'appelons un par ad hoc.

3.3 Pourquoi le regroupement par colonnes dans la clé est-il plus rapide qu'un ad hoc par?

Parce que chaque groupe est contigu en RAM, minimisant ainsi les récupérations de pages, et la mémoire peut être copiée en masse ( memcpyen C) plutôt qu'en boucle en C.

À partir de là, je suppose que la définition d'une clé permet en quelque sorte à R d'utiliser le "tri par base" sur d'autres algorithmes, et c'est pourquoi il est plus rapide.

Le guide de démarrage rapide de 10 minutes contient également un guide sur les clés.

1. Clés

Commençons par considérer data.frame, spécifiquement les noms de lignes (ou en anglais, les noms de lignes). Autrement dit, les noms multiples appartenant à une seule ligne. Les noms multiples appartenant à la seule ligne? Ce n'est pas ce à quoi nous sommes habitués dans un data.frame. Nous savons que chaque ligne a au plus un nom. Une personne a au moins deux noms, un premier nom et un deuxième nom. Cela est utile pour organiser un annuaire téléphonique, par exemple, qui est trié par nom, puis par premier nom. Cependant, chaque ligne d'un data.frame ne peut avoir qu'un seul nom.

Une clé se compose d'une ou plusieurs colonnes de noms de lignes, qui peuvent être des nombres entiers, des facteurs, des caractères ou une autre classe, pas simplement des caractères. De plus, les lignes sont triées par clé. Par conséquent, un data.table peut avoir au plus une clé, car il ne peut pas être trié de plusieurs manières.

L'unicité n'est pas appliquée, c'est-à-dire que les valeurs de clé en double sont autorisées. Puisque les lignes sont triées par clé, tous les doublons dans la clé apparaîtront consécutivement

L'annuaire téléphonique a été utile pour comprendre ce qu'est une clé, mais il semble qu'une clé ne soit pas différente par rapport à une colonne de facteurs. De plus, il n'explique pas pourquoi une clé est nécessaire (notamment pour utiliser certaines fonctions) et comment choisir la colonne à définir comme clé. De plus, il semble que dans une data.table avec le temps comme colonne, définir une autre colonne comme clé gâcherait probablement la colonne de temps aussi, ce qui la rend encore plus déroutante car je ne sais pas si je suis autorisé à définir une autre colonne comme clé. Quelqu'un peut-il m'éclairer s'il vous plaît?

Mise à jour mineure: veuillez également vous référer aux nouvelles vignettes HTML . Ce numéro met en évidence les autres vignettes que nous prévoyons de réaliser.

J'ai à nouveau mis à jour cette réponse (février 2016) à la lumière de la nouvelle on=fonctionnalité qui permet également les jointures ad hoc . Consultez l'historique pour les réponses précédentes (obsolètes).

Que fait exactement setkey(DT, a, b)?

Il fait deux choses:

1. réorganise les lignes de la table data.table DT par la ou les colonnes fournies ( a , b ) par référence , toujours par ordre croissant .
2. marque ces colonnes comme des colonnes clés en définissant un attribut appelé sortedà DT.

La réorganisation est à la fois rapide (grâce au tri de base interne de data.table ) et efficace en mémoire (une seule colonne supplémentaire de type double est allouée).

Quand est-ce setkey()nécessaire?

Pour les opérations de regroupement, cela setkey()n'a jamais été une exigence absolue. Autrement dit, nous pouvons effectuer un cold by ou adhoc-by .

## "cold" by
require(data.table)
DT <- data.table(x=rep(1:5, each=2), y=1:10)
DT[, mean(y), by=x] # no key is set, order of groups preserved in result

Cependant, avant v1.9.6, les jointures de la forme x[i]doivent keyêtre activées x. Avec le nouvel on=argument de la v1.9.6 + , ce n'est plus vrai, et la définition des clés n'est donc pas non plus une exigence absolue ici.

## joins using < v1.9.6 
setkey(X, a) # absolutely required
setkey(Y, a) # not absolutely required as long as 'a' is the first column
X[Y]

## joins using v1.9.6+
X[Y, on="a"]
# or if the column names are x_a and y_a respectively
X[Y, on=c("x_a" = "y_a")]

Notez que l' on=argument peut être spécifié explicitement même pour les keyedjointures.

La seule opération keyà définir absolument est la fonction foverlaps () . Mais nous travaillons sur d'autres fonctionnalités qui, une fois terminées, supprimeraient cette exigence.

• Alors, quelle est la raison de la mise en œuvre de l' on=argument?

  Il y a plusieurs raisons.

  1. Il permet de distinguer clairement l'opération comme une opération impliquant deux tables de données . Le simple fait de faire X[Y]ne distingue pas cela non plus, bien que cela puisse être clair en nommant les variables de manière appropriée.

  2. Il permet également de comprendre les colonnes sur lesquelles la jointure / sous-ensemble est effectuée immédiatement en regardant cette ligne de code (et sans avoir à retracer la setkey()ligne correspondante ).

  3. Dans les opérations où des colonnes sont ajoutées ou mises à jour par référence , les on=opérations sont beaucoup plus performantes car il n'est pas nécessaire de réorganiser la totalité de la table data.table juste pour ajouter / mettre à jour des colonnes. Par exemple,

     ## compare 
     setkey(X, a, b) # why physically reorder X to just add/update a column?
     X[Y, col := i.val]
     
     ## to
     X[Y, col := i.val, on=c("a", "b")]

     Dans le second cas, nous n'avons pas eu à commander à nouveau. Il ne s'agit pas de calculer la commande qui prend du temps, mais de réorganiser physiquement la table data.table dans la RAM, et en l'évitant, nous conservons l'ordre d'origine, et il est également performant.

  4. Même autrement, à moins que vous n'effectuiez des jointures de manière répétitive, il ne devrait y avoir aucune différence de performances notable entre une jointure à clé et une jointure ad hoc .

Cela conduit à la question, quel avantage la saisie d'une table data.table a- t -elle plus?

• Y a-t-il un avantage à saisir une table data.table?

  La saisie d'une table data.table la réorganise physiquement en fonction de ces colonnes dans la RAM. Le calcul de la commande n'est généralement pas la partie qui prend du temps, mais plutôt la réorganisation elle-même. Cependant, une fois les données triées en RAM, les lignes appartenant au même groupe sont toutes contiguës en RAM, et sont donc très efficaces en cache. C'est le tri qui accélère les opérations sur les tables de données à clé.

  Il est donc essentiel de déterminer si le temps passé à réorganiser l'ensemble de la table data.table vaut le temps de faire une jointure / agrégation efficace du cache. Habituellement, à moins que des opérations de regroupement / jointure répétitives soient effectuées sur la même table de données à clé , il ne devrait pas y avoir de différence notable.

Dans la plupart des cas, il ne devrait donc plus être nécessaire de définir des clés. Nous vous recommandons d'utiliser dans la on=mesure du possible, à moins que la définition de la clé n'améliore considérablement les performances que vous souhaitez exploiter.

Question: Selon vous, quelles seraient les performances par rapport à une jointure à clé , si vous l'utilisez setorder()pour réorganiser la table data.table et l'utiliser on=? Si vous avez suivi jusqu'à présent, vous devriez être en mesure de le comprendre :-).

Une clé est essentiellement un index dans un ensemble de données, ce qui permet des opérations de tri, de filtrage et de jointure très rapides et efficaces. Ce sont probablement les meilleures raisons d'utiliser des tables de données au lieu de blocs de données (la syntaxe d'utilisation des tables de données est également beaucoup plus conviviale, mais cela n'a rien à voir avec les clés).

Si vous ne comprenez pas les index, considérez ceci: un annuaire téléphonique est «indexé» par nom. Donc, si je veux rechercher le numéro de téléphone de quelqu'un, c'est assez simple. Mais supposons que je veuille rechercher par numéro de téléphone (par exemple, rechercher qui a un numéro de téléphone particulier)? À moins que je ne puisse «réindexer» l'annuaire téléphonique par numéro de téléphone, cela prendra beaucoup de temps.

Prenons l'exemple suivant: supposons que j'ai une table, ZIP, de tous les codes postaux aux États-Unis (> 33 000) avec les informations associées (ville, état, population, revenu médian, etc.). Si je veux rechercher les informations pour un code postal spécifique, la recherche (filtre) est environ 1000 fois plus rapide si je suis d' setkey(ZIP,zipcode)abord.

Un autre avantage concerne les jointures. Supposons que vous ayez une liste de personnes et leurs codes postaux dans une table de données (appelez-la "PPL"), et que je veuille ajouter des informations de la table ZIP (par exemple, ville, état, etc.). Le code suivant le fera:

setkey(ZIP,zipcode)
setkey(PPL,zipcode)
full.info <- PPL[ZIP, nomatch=F]

Il s'agit d'une "jointure" dans le sens où je joins les informations de 2 tables basées dans un champ commun (code postal). Les jointures comme celle-ci sur de très grandes tables sont extrêmement lentes avec les trames de données et extrêmement rapides avec les tables de données. Dans un exemple réel, j'ai dû faire plus de 20 000 jointures comme celle-ci sur une table complète de codes postaux. Avec les tables de données, le script a duré environ 20 minutes. courir. Je ne l'ai même pas essayé avec des trames de données car cela aurait pris plus de 2 semaines.

À mon humble avis, vous ne devriez pas seulement lire mais étudier la FAQ et le matériel d'introduction. C'est plus facile à comprendre si vous avez un problème réel auquel appliquer cela.

[Réponse au commentaire de @ Frank]

Re: tri vs indexation - Sur la base de la réponse à cette question , il semble que setkey(...)réorganise en fait les colonnes de la table (par exemple, un tri physique), et ne crée pas d'index au sens de la base de données. Cela a des implications pratiques: d'une part, si vous définissez la clé dans une table avec setkey(...), puis modifiez l'une des valeurs de la colonne clé, data.table déclare simplement que la table n'est plus triée (en désactivant l' sortedattribut); il ne réindexe pas dynamiquement pour maintenir le bon ordre de tri (comme cela se produirait dans une base de données). De plus, "supprimer la clé" à l'aide de setky(DT,NULL)ne restaure pas la table dans son ordre d'origine non trié.

Re: filter vs join - la différence pratique est que le filtrage extrait un sous-ensemble d'un seul ensemble de données, tandis que join combine les données de deux ensembles de données basés sur un champ commun. Il existe de nombreux types de jointures (interne, externe, gauche). L'exemple ci-dessus est une jointure interne (seuls les enregistrements avec des clés communes aux deux tables sont renvoyés), et cela présente de nombreuses similitudes avec le filtrage.