Les index logiciels accélèrent les applications en intelligence d'affaire, en apprentissage machine et en science des données. Ils déterminent souvent la performance des applications portant sur les mégadonnées. Les index efficaces améliorent non seulement la latence et le débit, mais aussi la consommation d'énergie. Plusieurs index font une utilisation parcimonieuse de la mémoire vive afin que les données critiques demeurent près du processeur. Il est aussi souhaitable de travailler directement sur les données compressées afin d'éviter une étape de décodage supplémentaire. Ainsi nous utilisons des techniques de compression légères, optimisées pour la vitesse.

Nous nous intéressons aux index bitmap. Nous les trouvons dans une vaste gamme de systèmes: Oracle, Hive, Spark, Druid, Kylin, Lucene, Elastic, Git... Ils sont une composante de systèmes — tels que Wikipedia ou GitHub — dont dépendent des millions d'utilisateurs à tous les jours.

Notre plan comporte trois axes de recherche:

(1) Poursuivre l'optimisation des index bitmap, tels qu'ils sont utilisés au sein des systèmes actuels. Plusieurs de ces systèmes dépendent des index Roaring et EWAH, deux formats que nous avons développés. Nous prévoyons multiplier la performance de ces index sur les processeurs bénéficiant d'instructions SIMD (instruction unique, données multiples) avancées.

(2) Continuer de battre des records de vitesse avec nos techniques de compression d'entiers. Nous ciblons les listes d'entiers que l'on trouve au sein des arbres B+, dans les index inversés et les index bitmap compressés. Ces dernières années, nous avons montré que l'on pouvait décoder des milliards d'entiers par seconde tout en maintenant des ratios de compression proches de la limite entropique de Shannon. Ce faisant, nous n'avons utilisé qu'une fraction des capacités des derniers processeurs. Nous établirons de nouveaux records de performance tout en compressant davantage les données. Nous allons aussi accélérer les applications avec des fonctions de rang, de sélection, de fusion, de mise à jour et d'insertion opérant directement sur les données compressées. Nous allons appliquer nos travaux aux moteurs de bases de données (par ex., upscaledb) et aux systèmes de mégadonnées (par ex., Parquet, Druid, Spark, etc.).

(3) Développer un nouveau format d'index bitmap qui surclasse les techniques de pointe tant en ce qui a trait à l'utilisation de la mémoire qu'à la vitesse. Actuellement, un des meilleurs formats est Roaring: il est largement adopté, rapide et il utilise peu de mémoire. Nous souhaitons concevoir un nouveau format qui utilise encore moins de mémoire tout en améliorant la vitesse. Alors qu'il est relativement facile d'offrir une meilleure compression, le faire tout en améliorant la vitesse des requêtes représente un véritable défi. Cet axe de recherche repose directement sur les deux précédents.

Chercheur principal

Daniel Lemire

Organisme subventionnaire

CRSNG (Conseil de recherches en sciences naturelle et en génie)

Programme

Subvention à la découverte individuelle et supplément d'accélération

Secteur de recherche

Systèmes intelligents, sciences et technologies de l'information

Années

2017 - 2020

Montant accordé

437 500,00 $