SQLite Optimization

1. Overview

This page summarizes the the tests and results of various experiments done with the aim of optimizing SQLite performance under Android.

A presentation on this subject was given by Khasim during Linaro Connect Asia (LCA14). The presentation talks about the motivation for optimizing SQLite for Android and some test results. The presentation can be found here.

2. Latest SQLite Package

Android KitKat (4.4) ships with SQLite 3.7.11 and the latest version (as of April 2014) from http://www.sqlite.org is 3.8.4.3. The SQLite package is used to generate the SQLite shared library (libsqlite.so) used in Android.

An experiment was carried out to move to a newer version (3.8.3.1) and the newer SQLite package showed a 7% improvement over the older version when running the RL Benchmark SQLite Android app. In addition, the newer package includes several bug fixes, which is always beneficial for stability and security.

The patch to update to the newer version has been submitted to AOSP and can be tracked here: https://android-review.googlesource.com/#/q/status:open+project:platform/external/sqlite

3. Bionic C with Cortex-String

Since all SQL statements are in plain text format, there is inherently a lot of string operations. Thus, one way to improve the performance of SQLite is to optimize the Bionic C string library. The cortex-strings is a set of string routines, such as strlen, memchr, memcpy, etc, that are optimized for that ARM Cortex-A family of processors.

The string routines inside Bionic C were replaced with versions from cortex-strings. A benchmark between the original Bionic C implementation and cortex-string implementation can be found here: https://wiki.linaro.org/Platform/Android/CortexStringsInBionic

4. F2FS

Flash-Friendly File System (F2FS) is a file system created by Samsung specifically to improve performance for NAND flash memory devices commonly found in smartphones and tablets. It was released with Linux kernel 3.8 in February 2013. Today, most Android distributions are still using the EXT4 file system, which was developed with mechanical hard drives in mind. Since SQLite databases are stored in the file system, a better file system could lead to faster SQLite operations.

To enable use of F2FS in Android, two things had to be done:

  1. Enable support of F2FS in the Linux kernel
  2. Format the user data (/data) partition using F2FS; since the databases are stored in the user data partition, there is no need to format the other partitions

  3. Update the Android fstab to mount the partition properly

A Nexus 7 (2013) device was used for the experiment. Since the device officially ships with kernel 3.4, F2FS support had to be backported (from here and here). The following kernel config options were set:

CONFIG_F2FS_FS=y
CONFIG_F2FS_STAT_FS=y
CONFIG_F2FS_FS_XATTR=y
# CONFIG_F2FS_FS_POSIX_ACL is not set
CONFIG_F2FS_FS_SECURITY=y

As for formatting the user data partition, the easiest way was to use the third-party TWRP open recovery. F2FS formatting tools were added to the recovery and the twrp.fstab modified to use F2FS for the /data partition. The final piece was to use the following entry in Android's fstab file:

/dev/block/platform/msm_sdcc.1/by-name/userdata /data f2fs noatime,nosuid,nodev,nodiratime,background_gc=off,discard wait,check,encryptable=/dev/block/platform/msm_sdcc.1/by-name/metadata

To benchmark the performance of F2FS vs EXT4, a few SQLite benchmark Android apps were downloaded from the Google Play Store and sideloaded onto the Nexus 7. From the results (see below), it does not seem F2FS is a clear winner. The advantage of F2FS seems to highlighted when SQLite performance is performing many operations in a single transaction. Another thing to consider is that F2FS is still being actively worked on. The backport is not 100% synced up to the latest so there might be some improvements that is not present for this experiment.

4.1. Test Setup

  • Nexus 7 (2013) 32 GB WiFi (razor/flo)

  • Android: AOSP 4.4.2
  • Flight mode: on
  • Brightness: minimum
  • Screen timeout: 30 min
  • Rotation locked to portrait
  • CPU governor: performance @ 1512000 (via removing the lines in init.flo.rc to switch to the ondemand governor and to start the mpdecision service)

4.2. Test Results

  • All results are number of seconds to complete; lower is better

RL Benchmark

SQLite Operation

AOSP 4.4.2

AOSP 4.4.2 + F2FS

1000 INSERTs

8.00125

8.2485

25000 INSERTs in a transaction

4.06275

4.09775

25000 INSERTs into an indexed table in a transaction

4.0395

4.83975

100 SELECTs without an index

0.02075

0.0295

100 SELECTs on a string comparison

0.023

0.02325

Creating an index

0.52925

0.5135

5000 SELECTs with an index

0.9295

0.93825

1000 UPDATEs without an index

3.662

3.6525

25000 UPDATEs with an index

5.6545

5.68025

INSERTs from a SELECT

0.861

0.8445

DELETE without an index

0.76725

0.74775

DELETE with an index

0.6835

0.653

DROP TABLE

0.328

0.29725

Overall

29.56225

29.81575

SQLite Benchmark

SQLite Operation

AOSP 4.4.2

AOSP 4.4.2 + F2FS

Insert 200 Statements

2.013

1.5605

Insert 15000 Statements in Transaction

1.53075

1.851

Update 500 Statements

4.33025

4.10875

Update 15000 Statements in Transaction

2.01875

2.033

Select 15000 Statements

4.166

4.335

Delete 200 Statements

1.95475

1.53675

Delete 15000 Statements in Transaction

1.8495

2.1125

Overall

17.863

17.5375

AndroBench

SQLite Operation

AOSP 4.4.2

AOSP 4.4.2 + F2FS

1000 INSERTs

9.43

9.14

1000 UPDATEs

9.45

9.0875

1000 DELETEs

8.9875

9.0275

Overall

27.8675

27.255

ACREVE Benchmark

SQLite Operation

AOSP 4.4.2

AOSP 4.4.2 + F2FS

1000 INSERTs

9.998

10.62475

25000 INSERTs in a transaction

19.9235

18.8725

25000 INSERTs into an indexed table

19.54025

11.337

100 SELECTs without an index

0.108

0.048

100 SELECTs on a string comparison

0.053

0.0495

INNER JOIN without an index

0.002

0.0025

Creating an index

0.709

0.7205

5000 SELECTs with an index

1.4355

1.4505

1000 UPDATEs without an index

1.17425

1.26775

25000 UPDATEs with an index

31.48775

28.48025

25000 text UPDATEs with an index

6.3715

6.4675

INSERTs from a SELECT

1.42325

1.47775

INNER JOIN wih index on one side

0.00025

0.00075

INNER JOIN on text field with index on one side

0.00175

0.00075

100 SELECTs with subqueries. Subquery is using index

0.04125

0.04525

DELETE without an index

0.2565

0.23975

DELETE with an index

1.7475

1.772

A big INSERT after a big DELETE

1.2245

1.20275

A big DELETE followed by many small INSERTs

1.03525

1.09325

DROP TABLE

0.63175

0.63225

Total

97.16475

85.78525

4.3. Analysis

After pinging Arnd on his thoughts regarding the results, he suggested to check if writes happen synchronously or asynchronously. By using strace() and looking for fdatasync() calls, it is shown that writes are buffered before being written out to the flash, i.e., asynchronous writes. Thus, any speed improvement of F2FS over EXT4 is not very prominent.

4.4. Analysis with Iozone

Iozone is a filesystem benchmark tool. It includes a suite of read/write tests with various conditions and parameters. To understand why F2FS is not showing vast improvements, Arnd proposed to run iozone benchmark while running the SQLite benchmarks to see if it makes a difference. However, it would be interesting to see how F2FS fairs on its own compared to EXT4 with just iozone.

The following are results from running iozone on the Nexus 7 with two different images: vanilla AOSP, and AOSP with F2FS added and enabled. All tests ran with same conditions as running the SQLite benchmarks mentioned earlier (performance governor, flight mode, etc.). Each test is ran four times and then averaged for each filesystem. The results (see below) are then converted into an unary percent of improvement of F2FS over EXT4.

The results paint a clear picture: F2FS has healthy gains in write performance over EXT4, but the reverse is true for reads. In cases such as with direct I/O where the buffer cache is completely bypassed, the read performance can drop by over 20%. Luckily, Android does use buffer caches so this is not a problem. The rest of the results show a 4-9% increased in write performance and a 2-3% decrease in read performance.

4.4.1. Iozone Results

* All results are represented as a unary percent (1 = 100%, 0.5 = 50%, etc.) improvement of F2FS over EXT4. The color scheme is as follows:

Range

Highlight

-0.20]

(-0.20, -0.10]

(-0.10, -0.05]

(-0.05, 0.00)

(0.00, 0.05)

[0.05, 0.10)

[0.10, 0.20)

[0.20

Default case: Automatic mode with filed 32 MB file size, varying record lengths, include flush operation, and purge processor caches in between operations (command: iozone -a -e -N -p -s32M -R)

Test

Record Length (KB)

4

8

16

32

64

128

256

512

1024

2048

4096

8192

16384

Writer Report

0.07

0.067

0.068

0.069

0.074

0.065

0.067

0.064

0.085

0.076

0.077

0.069

0.074

Re-writer Report

0.014

0.032

0.022

0.009

0.014

0.026

0.007

0.019

0.021

0.018

0.02

0.021

0.019

Reader Report

0

0

-0.014

-0.021

-0.016

-0.017

-0.011

-0.014

-0.013

-0.009

-0.014

-0.012

-0.017

Re-reader Report

0

-0.013

-0.02

-0.035

-0.027

-0.026

-0.022

-0.018

-0.011

-0.016

-0.009

-0.017

-0.016

Random Read Report

0

-0.023

-0.013

-0.024

-0.029

-0.027

-0.021

-0.019

-0.008

-0.016

-0.007

-0.017

-0.016

Random Write Report

0.059

0.118

0.096

0.055

0.041

0.019

0.017

-0.011

0.015

0.01

0.018

0.025

0.02

Backward Read Report

0

0

-0.02

-0.018

-0.02

-0.021

-0.016

-0.014

-0.015

-0.013

-0.011

-0.018

-0.013

Record Rewrite Report

0.077

0.091

0.096

0.1

0.102

0.098

0.096

0.117

0.081

0.054

0.027

0.031

0.015

Stride Read Report

0

-0.045

-0.019

-0.069

-0.029

-0.026

-0.027

-0.019

-0.008

-0.029

-0.016

-0.016

-0.018

Fwrite Report

0.012

0.015

0.006

0.024

0.019

0.015

0.015

0.018

0.023

0.025

0.035

0.025

0.023

Re-fwrite Report

0.014

0.029

0.012

0.009

-0.001

0.009

0.016

0.012

0.016

0.023

0.011

0.009

0.019

Fread Report

0

0

0

-0.003

-0.007

-0.01

0.022

0.012

-0.025

0.011

0.002

0.009

0.011

Re-fread Report

0

-0.011

0

-0.01

-0.007

-0.012

0.019

0.01

-0.018

0.011

-0.001

0.033

0.013

Default case with DIRECT I/O (command: iozone -a -e -N -p -s32M -I -R)

Test

Record Length (KB)

4

8

16

32

64

128

256

512

1024

2048

4096

8192

16384

Writer Report

0.021

-0.076

0.041

-0.066

-0.13

-0.107

-0.172

-0.177

-0.216

-0.208

-0.201

-0.205

-0.143

Re-writer Report

-0.032

-0.141

0.03

-0.058

-0.12

-0.113

-0.157

-0.171

-0.198

-0.194

-0.195

-0.199

-0.156

Reader Report

-0.005

-0.056

-0.152

-0.117

-0.112

-0.061

-0.059

-0.023

-0.028

-0.023

-0.025

-0.022

-0.02

Re-reader Report

-0.005

-0.058

-0.153

-0.117

-0.112

-0.06

-0.058

-0.022

-0.028

-0.024

-0.025

-0.023

-0.02

Random Read Report

0.004

-0.053

-0.067

-0.012

-0.025

-0.037

-0.033

-0.007

-0.012

-0.018

-0.024

-0.023

-0.021

Random Write Report

-0.001

-0.119

-0.244

-0.262

-0.236

-0.223

-0.231

-0.199

-0.227

-0.242

-0.214

-0.193

-0.172

Backward Read Report

-0.015

-0.062

-0.054

0.018

0.016

0.018

0.019

0.008

0.002

0.004

-0.004

-0.019

-0.025

Record Rewrite Report

-0.038

-0.107

-0.164

-0.213

-0.198

-0.213

-0.208

-0.169

-0.208

-0.194

-0.206

-0.196

-0.171

Stride Read Report

-0.004

-0.058

-0.055

0.019

0.019

0.016

0.011

0.007

-0.007

-0.015

-0.019

-0.013

-0.03

Fwrite Report

0.029

0.024

0.022

0.031

0.022

0.023

0.017

0.022

0.017

-0.06

0.027

0.024

0.022

Re-fwrite Report

0.037

0.02

0.024

0.015

0.022

0.017

0.019

0.01

0.026

0.032

0.018

0.025

0.022

Fread Report

0.021

-0.023

0.006

0

-0.003

0.006

0.012

0.015

-0.008

0.01

0.006

-0.001

0.004

Re-fread Report

0

-0.011

0

-0.007

-0.01

-0.004

0.008

0.008

-0.006

0.012

0.01

0.007

0.02

Default case with mix of mmap() and file I/O (command: iozone -a -e -N -p -s32M -Z -R)

Test

Record Length (KB)

4

8

16

32

64

128

256

512

1024

2048

4096

8192

16384

Writer Report

0.047

0.053

0.056

0.044

0.049

0.049

0.044

0.044

0.052

0.049

0.05

0.032

0.054

Re-writer Report

0.01

0.018

0.021

0.014

0.014

0.012

0.011

0.02

0.016

0.019

0.012

0.015

0.026

Reader Report

0

-0.013

-0.02

-0.028

-0.027

-0.024

-0.022

-0.02

-0.021

-0.012

-0.017

-0.02

-0.022

Re-reader Report

0

-0.025

-0.046

-0.035

-0.032

-0.028

-0.028

-0.023

-0.021

-0.012

-0.018

-0.023

-0.023

Random Read Report

0

-0.034

-0.038

-0.031

-0.029

-0.029

-0.028

-0.026

-0.021

-0.012

-0.021

-0.02

-0.022

Random Write Report

0.078

0.117

0.088

0.058

0.025

0.006

0.021

-0.006

0.017

0.026

0.014

0.026

0.019

Backward Read Report

0

0

-0.02

-0.024

-0.027

-0.026

-0.018

-0.016

-0.036

-0.009

-0.015

-0.021

-0.022

Record Rewrite Report

0.077

0.091

0.107

0.11

0.115

0.11

0.101

0.086

0.053

0.024

0.054

0.027

0.013

Stride Read Report

0

-0.023

-0.032

-0.038

-0.034

-0.03

-0.026

-0.027

-0.022

-0.045

-0.021

-0.024

-0.021

Fwrite Report

0.021

0.013

0.03

0.035

0.002

0.005

0.01

0.007

0.011

0.017

0.022

0.018

0.012

Re-fwrite Report

0.033

0.017

0.002

0.024

0.012

0.025

-0.004

0.013

0.01

0.031

0.014

0.011

0.02

Fread Report

0

-0.023

-0.019

-0.013

-0.003

-0.004

0.012

-0.005

-0.009

0.012

0.006

0.014

0.005

Re-fread Report

0

-0.012

-0.013

-0.016

-0.008

-0.005

0.013

-0.009

-0.01

0.013

0.004

0.021

0.016

Default case with multiple file buffers (command: iozone -a -e -N -p -s32M -m -R)

Test

Record Length (KB)

4

8

16

32

64

128

256

512

1024

2048

4096

8192

16384

Writer Report

-0.034

0.069

0.077

0.066

0.072

0.078

0.084

0.079

0.068

0.067

0.08

0.077

0.09

Re-writer Report

0.024

0.019

0.006

0.019

0.012

0.015

0.025

0.024

0.017

0.022

0.015

0.028

0.013

Reader Report

0

-0.025

-0.014

-0.022

-0.013

-0.014

-0.012

-0.011

-0.011

-0.013

-0.015

-0.007

-0.012

Re-reader Report

0

-0.013

-0.014

-0.015

-0.012

-0.017

-0.014

-0.014

-0.011

-0.01

-0.009

-0.008

-0.018

Random Read Report

0

-0.023

-0.007

-0.014

-0.013

-0.017

-0.016

-0.014

-0.012

-0.01

-0.008

-0.009

-0.017

Random Write Report

0.096

0.119

0.096

0.051

0.054

0.031

0.015

0.013

0.01

0.002

0.019

0.032

0.018

Backward Read Report

0

-0.012

-0.034

-0.011

-0.01

-0.015

-0.014

-0.014

-0.005

-0.003

-0.011

-0.007

-0.014

Record Rewrite Report

0.063

0.071

0.066

0.071

0.079

0.087

0.08

0.08

0.059

0.005

0.051

0.012

0.016

Stride Read Report

0

-0.023

-0.007

-0.014

-0.017

-0.057

-0.016

-0.014

-0.011

-0.012

-0.015

-0.022

-0.019

Fwrite Report

0.03

0.003

0.018

0.008

0.022

-0.006

0.006

0.03

0.024

0.023

0.034

0.021

0.035

Re-fwrite Report

0.026

0.027

0.017

0.022

0.022

0.014

0.026

0.009

0.011

0.018

0.024

0.021

0.011

Fread Report

0.037

0

0.006

0

0.011

0.009

0.005

0.003

0.009

0.011

0.016

0.005

0.013

Re-fread Report

0.037

0

0.006

-0.009

0.013

0.012

0.008

-0.001

0.005

0.008

0.017

0.005

0.028

Multiple simultaneous processes (command: iozone -e -p -s32M -l1 -u4 -i0 -i1 -i2 -i3 -i4 -i5 -i6 -i7 -i8 -i9 -i10 -i11 -i12 -R -b)

Test

Number of Processes

1

2

3

4

Initial Write

0.057

0.169

0.231

0.154

Rewrite

0.033

0.057

0.092

-0.001

Read

0

-0.005

-0.018

-0.059

Re-Read

-0.008

-0.007

-0.016

-0.032

Reverse Read

-0.005

0.001

-0.005

-0.023

Stride Read

-0.022

0.004

0.003

-0.014

Random Read

-0.033

0.008

0.001

-0.042

Mixed Workload

-0.035

0.062

0.038

-0.356

Random Write

0.062

0.236

0.352

0.623

Pwrite

0.018

0.181

0.236

0.12

Pread

0.01

-0.001

-0.009

-0.059

Fwrite

0.034

0.056

0.16

0.04

Fread

0.023

0.024

0.015

0.007

5. I/O Scheduler

The I/O scheduler is responsible for governing when to block I/O operations are submitted to the storage medium. Since the SQLite database lives on the flash storage, it would be interesting to see if any improvements can be had by using different I/O schedulers.

Experiments were carried out on a Nexus 7 (2013) running the same benchmark applications as the F2FS experiment. The Nexus 7 kernel includes three I/O schedulers: CFQ, NOOP, and Deadline. The CFQ (Completely Fair Queuing) scheduler is the default one, but it is written with mechanical hard disks in mind. The NOOP (No-Operation) scheduler basically has no queuing logic and is supposed to have better improvements for flash medium. The DEADLINE scheduler is suppose to be an improvement to CFQ by implementing deadlines for requests.

From the test results (see below), the variance between the times between I/O schedulers is very minimal. However, the DEADLINE scheduler does seem to show a slight improvement over the default CFQ scheduler.

5.1. Test Setup

  • Nexus 7 (2013) 32 GB WiFi (razor/flo)

  • Android: AOSP 4.4.2
  • Flight mode: on
  • Brightness: minimum
  • Screen timeout: 30 min
  • Rotation locked to portrait
  • CPU governor: performance @ 1512000 (via "echo performance > /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor")

  • Disabled CPU offline code (remove mpdecision service from init.flo.rc)

5.2. Test Results

All results are in seconds; the lower the better.

Benchmark Suite

CFQ

NOOP

DEADLINE

RL Benchmark

29.56025

29.617

29.53075

SQLite Benchmark

17.907

17.85525

17.8

AndroBench

27.935

27.8275

27.7625

ACREVE Benchmark

82.2375

84.25775

84.12425

6. GPU Acceleration with !RenderScript

There are papers (link) describing the use of GPU to accelerate certain SQL operations. One of the papers describes using NVIDIA's CUDA API to accelerate 13 SQLite SELECT statements. Tom Gall @ Linaro has performed a similar experiment with OpenCL on an ARM Mali GPU. The details and benchmark results of his experiment can be found on his blog. The results are quite promising.

To use GPU acceleration in Android, the RenderScript framework provides something very similar to OpenCL. Prior to Android KitKat, RenderScript was only available to the Android VM. Since the SQLite shared library lives in Linux user space, it was not possible to use RenderScript. The part that lives in Android VM is the preprocessing that happens before calling the JNI to reach the SQLite shared library. The preprocessing is mostly error checking/handling and string operations, which is not beneficial to be GPU-accelerated. However, with Android KitKat, some C/C++ APIs were being exposed and some examples could be found in AOSP at frameworks/rs/tests. More work in this area is TBD.

7. SQLite Shared Library Profiling

The SQLite shared library (libsqlite.so), built from external/sqlite in AOSP, lives in Linux user space. There is a JNI to allow processes inside the Android VM to use the SQLite shared library for database operations. An exercise was carried out identify bottlenecks, if any, in the SQLite shared library. To do this, the perf tool was used. It is a Linux user space utility to collect performance metrics in user and kernel space. It does not have the ability to peek into the Android VM.

The experiment consists of running Android SQLite benchmark apps and using perf to collect the amount of CPU spent inside the SQLite library. From the results (see below), it is shown that the actual amount of CPU time spent inside the SQLite shared library (libsqlite.so) is quite low. The highest CPU-usage function is /system/lib/libsqlite.so:sqlite3VdbeExec, which is the main Virtual DataBase Engine (VDBE) execution routine.

7.1. Test Results

RL Benchmark

Function

% Time of Benchmark

/system/lib/libsqlite.so:sqlite3VdbeExec

7.05

/system/lib/libsqlite.so:sqlite3Parser

2.12

/system/lib/libsqlite.so:sqlite3BtreeMovetoUnpacked

2.06

/system/lib/libsqlite.so:dropCell

1.65

/system/lib/libsqlite.so:sqlite3VdbeRecordCompare

1.04

/system/lib/libsqlite.so:sqlite3VdbeSerialGet

1.01

/system/lib/libsqlite.so:insertCell

0.99

/system/lib/libsqlite.so:sqlite3BtreeInsert

0.85

/system/lib/libsqlite.so:btreeParseCellPtr

0.78

/system/lib/libsqlite.so:sqlite3MemCompare

0.69

/system/lib/libsqlite.so:balance

0.63

/system/lib/libsqlite.so:sqlite3GetToken

0.55

/system/lib/libsqlite.so:pcache1Fetch

0.54

/system/lib/libsqlite.so:pager_write

0.5

ACREVE Benchmark

Function

% Time of Benchmark

/system/lib/libsqlite.so:sqlite3VdbeExec

1.93

/system/lib/libsqlite.so:sqlite3VdbeRecordCompare

0.63

/system/lib/libsqlite.so:sqlite3BtreeMovetoUnpacked

0.54

/system/lib/libsqlite.so:balance

0.5

/system/lib/libicuuc.so:icu_51::UnicodeString::~UnicodeString()

0.69

/system/lib/libicuuc.so:_ZL16init_resb_resultPK12ResourceDatajPKciP18UResourceDataEntryPK15UResourceBundleiPS6_P10UErrorCode.part.1

0.31

/system/lib/libicuuc.so:icu_51::UnicodeString::doReplace()

0.23

/system/lib/libicui18n.so:icu_51::DecimalFormat::applyPatternWithoutExpandAffix()

0.36

Platform/Android/SQLiteOptimization (last modified 2014-04-17 08:17:10)