Taogen's Blog

This post is talking about automatic and adaptive memory management in the Java runtime. It mainly includes the following content: concepts of memory management, how a garbage collector works, memory management in the JRockit VM.

Concepts of Automatic Memory Management

Automatic memory management is defined as any garbage collection technique that automatically gets rid of stale references, making a free operator unnecessary.

There are many implementation of automatic memory management techniques, such as reference counting, heap management strategies, tracing techniques (traversing live object graphs).

Adaptive memory management

JVM behavior on runtime feedback is a good idea. JRockit was the first JVM to recognize that adaptive optimization based on runtime feedback could be applied to all subsystems in the runtime and not just to code generation. One of these subsystems is memory management.

Adaptive memory management is based heavily on runtime feedback. It is a special case of automatic memory management.

Adaptive memory management must correctly utilize runtime feedback for optimal performance. This means changing GC strategies, automatic heap resizing, getting rid of memory fragmentation at the right intervals, or mainly recognizing when it is most appropriate to “stop the world”. Stopping the world means halting the executing Java program, which is a necessary evil for parts of a garbage collection cycle.

Advantages of automatic memory management

• It contributes to the speed of the software development cycle. Because using automatic memory management, memory allocation bugs can’t occur and buffer overruns can’t occur.
• An adaptive memory manager may pick the appropriate garbage collection strategy for an application based on its current behavior, appropriately changing the number of garbage collecting threads or fine tuning other aspects of garbage collection strategies whenever needed.

Disadvantages of automatic memory management

• It can slow down execution for certain applications to such an extent that it becomes impractical.
• There may still be memory leaks in a garbage collected environment.

Fundamental Heap Management

Before knowing actual algorithms for garbage collection, we need to know the allocation and deallocation of objects. We also need to know which specific objects on the heap to garbage collect, and how they get there and how they are removed.

Allocating and releasing objects

Allocation on a per-object, in the common case, never takes place directly on the heap. Rather, it is performed in the thread local buffers or similar constructs that promoted to the heap from time to time. However, in the end, allocation is still about finding appropriate space on the heap for the newly allocated objects or collections of objects.

In order to put allocated objects on the heap, the memory management system must keep track of which section of the heap are free. Free heap space is usually managed by maintaining a free list – a linked list of the free memory chunks on the heap, prioritized in some order that makes sense.

A best fit or first fit can be performed on the free list in order to find a heap address where enough free space is available for the object. There are many different allocation algorithms for this, with different advantages.

Fragmentation and compaction

It is not enough to just keep track of free space in a useful manner. Fragmentation is also an issue for the memory manager. When dead objects are garbage collected all over the heap, we end up with a lot of holes from where objects have been removed.

Fragmentation is a serious scalability issue for garbage collection, as we can have a very large amount of free space on the heap that, even though it is free, is actually unusable.

If the memory manager can’t find enough contiguous free space for the new object, an OutOfMemoryError will be thrown, even though there are much free space on the heap.

Thus, a memory management system needs some logic for moving objects around on the heap, in order to create larger contiguous free regions. This process is called compaction, and involves a separate GC stage where the heap is defragmented by moving live objects so that they are next to one another on the heap.

Compaction is difficult to do without stopping the world. By looking at the object reference graph and by gambling that objects referencing each other are likely to be accessed in sequence, the compaction algorithm may move these objects so that they are next to one another on the heap. This is beneficial for the cache, the object lifetimes are similar so that larger free heap holes are crated upon reclamation.

Garbage collection algorithms

All techniques for automatic memory management boil down to keeping track of which objects are being used by the running program, in other words, which objects are referenced by other objects that are also in use. Objects that are no longer in use may be garbage collected. Objects in use also means live objects.

There are two category common garbage collection techniques: reference counting and tracing garbage collection.

Reference counting

Reference counting is a garbage collection algorithm where the runtime keeps track of how many live objects point to a particular object at a given time.

When the reference count for an object decreases to zero, the object has no referrers left, the object is available for garbage collection.

Advantages of reference counting algorithm

• It is obvious simplicity, is that any unreferenced object may be reclaimed immediately when its reference count drops to zero.

Disadvantages of reference counting algorithm

• The obvious flaw that cyclic constructs can never be garbage collected. Consequently cause a memory leak.
• Keeping the reference counts up to date can be expensive, especially in a parallel environment where synchronization is required.

There are no commercial Java implementations today where reference counting is a main garbage collection technique in the JVM, but it might well be used by subsystems and for simple protocols in the application layer.

Tracing techniques

A tracing garbage collection start by marking all objects currently seen by the running program as live. The recursively mark all objects reachable from those objects live as well. There are many variations of tracing techniques, for example, “mark and sweep” and “stop and copy”.

There are some basic concepts of tracing techniques, for example, root set that means the initial input set for this kind of search algorithm, that is the set of live objects from which the trace will start. The root set contains all objects that are available without having to trace any references.

Mark and sweep

The mark and sweep algorithm is the basis of all the garbage collectors in all commercial JVMs today. Mark and sweep can be done with or without copying or moving objects. However, the real challenge is turning it into an efficient and highly scalable algorithm for memory management. The following pseudocode describes a naive mark and sweep algorithm:

Mark:
	Add each object in the root set to a queue
		For each object X in the "queue"
			Mark X reachable
			Add all objects referenced from X to the queue
Sweep:
	For each object X on the "heap"
		If the X not marked, garbage collect it

The following figures show the process of mark and sweep:

1. Before mark

2. After mark.

3. After sweep

In naive mark and sweep implementations, a mark bit is typically associated with each reachable object. The mark bit keeps track of if the object has been marked or not.

A variant of mark and sweep that parallelizes better is tri-coloring mark and sweep. Basically, instead of using just one binary mark bit per object, a color, or ternary value is used. There are three color: white, grey, and black.

• White objects are considered dead and should be garbage collected.
• Black objects are guaranteed to have no references to white objects.
• Grey objects are live, but with the status of their children unknown.

Initially, there are no black object – the marking algorithm needs to find them, and the root set is colored grey to make the algorithm explore the entire reachable object graph. All other objects start out as white.

The tri-color algorithm is fairly simple:

Mark:
	All objects are White by default.
	Color all objects in the root set Grey.
	While there exist Grey objects
		For all Grey object, X
			For all white objects (successors) Y, that X references Color Y Grey.
			If all edges from X lead to another Grey object, Color X Black.
Sweep:
	Garbage collect all White objects
	

The main idea here is that as long as the invariant that no block nodes ever point to white nodes is maintained, the garbage collector can continue marking even while changes to the object graph take place.

Stop and Copy

Stop and copy can be seen as a special case of tracing GC, and is intelligent in its way, but is impractical for large heap sizes in real applications.

Stop and copy garbage collection partitioning the heap into two region of equal size. Only one region is in use at a time. Stop and copy garbage collection goes through all live objects in one of the heap regions, starting at the root set, following the root set pointers to other objects and so on. The marked live objects are moved to the other heap region. After garbage collection, the heap regions are switched so that other half of the heap becomes the active region before the next collection cycle.

Advantages of stop and copy algorithm:

• fragmentation can’t become an issue.

Disadvantages of stop and copy algorithm:

• All live objects must be copied each time a garbage collection is performed, introducing a serious overhead in GC time as a function of the amount of live data.
• Only using half of heap at a time is a waste of memory.

The following figure shows the process of stop and copy:

Generational garbage collection

In object-oriented languages, most objects are temporary or short-lived. However, performance improvement for handling short-lived objects on the heap can be had if the heap is split into two or more parts called generations.

In generational garbage collection, new objects are allocated in “young” generations of the heap, that typically are orders of magnitude smaller than the “old” generation, the main part of the heap. Garbage collection is then split into young and old collections, a young collection merely sweeping the young spaces of the heap, removing dead objects and promoting surviving objects by moving them to an older generation.

Collecting a smaller young space is orders of magnitude faster than collecting the larger old space. Even though young collections need to happen far more frequently, this is more efficient because many objects die young and never need to be promoted. ideally, total throughput is increased and some potential fragmentation is removed.

JRockit refer to the young generations as nurseries.

Muti generation nurseries

While generational GCs typically default to using just one nursery, sometimes it can be a good idea to keep several small nursery partitions in the heap and gradually age young objects, moving them from the “younger” nurseries to the “older” ones before finally promoting them to the “old” part of heap. This stands in contrast with the normal case that usually involves just one nursery and one old space.

Multi generation nurseries may be more useful in situations where heavy object allocation takes place.

If young generation objects live just a bit longer, typically if they survive a first nursery collection, the standard behavior of a single generation nursery collector, would cause these objects to be promoted to the old space. There, they will contribute more to fragmentation when they are garbage collected. So it might make sense to have several young generations on the heap, with different age spans for young objects in different nurseries, to try to keep the heap holes away from the old space where they do the most damage.

Of course the benefits of a multi-generational nursery must be balanced against the overhead of copying objects multiple times.

Write barriers

In generational GC, objects may reference other objects located in different generations of the heap. For example, objects in the old space may point to objects in the young spaces and vice versa. If we had to handle updates to all references from the old space to the young space on GC by traversing the entire old space, no performance would be gained from the generational approach. As the whole point of generational garbage collection is only to have to go over a small heap segment, further assistance from the code generator is required.

In generational GC, most JVMs use a mechanism called write barriers to keep track of which parts of the heap need to be traversed. Every time an object A starts to reference another object B, by means of B being placed in one of A’s fields or arrays, write barriers are needed.

The traditional approach to implementing write barriers is to divide the heap into a number of small consecutive sections (typically about 512 bytes each) that are called cards. The address space of the heap is thus mapped to a more coarse grained card table. whenever the Java program writes to a field in an object, the card on the heap where the object resides is “dirtied” by having the write barrier code set a dirty bit.

Using the write barriers, the traversal time problem for references from the old generation to the nursery is shortened. When doing a nursery collection, the GC only has to check the portions of the old space represented by dirty cards.

Throughput versus low latency

Garbage collection requires stopping the world, halting all program execution, at some stage. Performing GC and executing Java code concurrently requires a lot more bookkeeping and thus, the total time spent in GC will be longer. If we only care about throughput, stopping the world isn’t an issue–just halt everything and use all CUPs to garbage collect. However, to most applications, latency is the main problem, and latency is caused by not spending every available cycle executing Java code.

Thus, the tradeoff in memory management is between maximizing throughput and maintaining low latencies. But, we can’t expect to have both.

Garbage collection in JRockit

The backbone of the GC algorithm used in JRockit is based on the tri-coloring mark and sweep algorithm. For nursery collections, heavily modified variants of stop and copy are used.

Garbage collection in JRockit can work with or without generations, depending on what we are optimizing for.

Summary

• First, we need to know what is automatic memory management, its advantages and disadvantages.
• Fundamentals of heap management are: how to allocating and releasing objects on the heap, how to compact fragmentations of heap memory.
• There are two common garbage collection algorithms: reference counting and tracing garbage collection. The reference counting is simple, but have some serious drawbacks. There are many variations of tracing techniques: “mark and sweep” and “stop and copy”. The “stop and copy” technique has some drawbacks, and it only uses in some special scenarios. Therefore, the mark and sweep is the most popular garbage collection algorithm use in JVMs.
• The real-world garbage collector implementation is called generational garbage collection that is based on the “mark and sweep” algorithm.

References

[1] Oracle JRockit: The Definitive Guide by Marcus Hirt, Marcus Lagergren

The Java Virtual Machine defines various run-time data areas that are used during execution of a program. Some of these data areas are created on Java Virtual Machine start-up and are destroyed only when the Java Virtual Machine exits. Other data areas are per thread. Per-thread data areas are created when a thread is created and destroyed when the thread exits. The data areas of JVM are logical memory spaces, and they may be not contiguous physical memory space. The following image shows the JVM run-time data areas:

The pc Register

The Java Virtual Machine can support many threads of execution at once. Each JVM thread has its own pc (program counter) register. At any point, each JVM thread is executing the code of a single method, namely the current method for that thread. If that method is not native, the pc register contains the address of the JVM instruction currently being executed. If the method is native, the value of the pc register is undefined.

Java Virtual Machine Stacks

Each JVM thread has a private JVM stack, created at the same time as the thread. A JVM stack stores frames. The JVM stack holds local variables and partial results, and plays a part in method invocation and return.

Each frame in a stack stores the current method’s local variable array, operand stack, and constant pool reference. A JVM stack may have many frames because until any method of a thread is finished it may call many other methods, and frames of these methods also store in the same JVM stack.

Because the JVM stack is never manipulated directly except to push and pop frames, frames may be heap allocated. The memory for a JVM stack does not need to be contiguous.

Frames

A frame is used to store data and partial results, as well as to perform dynamic link, return values for method, and dispatch exceptions.

A new frame is created each time a method is invoked. A frame is destroyed when its method invocation completes, whether that completion is normal or abrupt. Frames are allocated from the JVM stack of the thread creating the frame. Each frame has its own array of local variables, operand stack, and a reference to the run-time constant pool of the class of the current method.

Only one frame for the executing method, is active at any point in a given thread of control. This frame is referred to as the current frame, and its method is known as the current method. The class in which the current method is defined is the current class. Operations on local variables and the operand stack are typically with reference to the current frame.

A frame ceases to be current if its method invokes another method or if its method completes. When a method is invoked, a new frame is created and becomes current when control transfers to the new method. On method return, the current frame passes back the result of its method invocation, to the previous frame.

A frame created by a thread is local to that thread and connot be referenced by any other thread.

Heap

The JVM has a heap that is shared among all JVM threads. The heap is the run-time data area from which memory for all class instances and arrays is allocated.

The heap is created on virtual machine start-up. Heap storage for objects is reclaimed by an automatic storage management system (known as a garbage collector); objects are never explicitly deallocated. The JVM assumes no particular type of automatic storage management system, and the storage management technique may be chosen according to the implementor’s system requirements. The memory for the heap does not need to be contiguous.

Method Area

The JVM has a method area that is shared among all JVM threads. The method area is analogous to the storage area for compiled code of conventional language or analogous to the “text” segment in an operating system process. It stores per-class structures such as the run-time constant poll, field and method data, and the code for methods and constructors, including the special methods used in class and instance initialization and interface initialization.

The Method area is created on virtual machine start-up. Although the method area is logically part of the heap, simple implementations may choose not to either garbage collect or compact it. The method area may be of a fixed size or may be expanded as required. The memory for the method area does not need to be contiguous.

Run-Time Constant Pool

A run-time constant pool is a per-class or per-interface run-time representation of the constant_pool table in a class file. It contains several kinds of constant, ranging from numeric literals known at compile-time to method and field references that must be resolved at run-time. The run-time constant pool serves a function similar to that of a symbol table for a conventional programming language, although it contains a wider range of data than a typical symbol table.

Each run-time constant pool is allocated from the JVM’s method area. The run-time constant pool for a class or interface is constructed when the class or interface is created by the JVM.

References constant pools

• A symbolic reference to a class or interface is in CONSTANT_Class_info structure.
• A symbolic reference to a field of a class are in CONSTANT_Fieldref_info structure.
• A symbolic reference to a method of a class is derived from a CONSTANT_Methodref_info structure.
• A symbolic reference to a method of an interface is derived from a CONSTANT_InterfaceMethodref_info structure.

Literals constant pools

• A string literal is in CONSTANT_String_info structure
• Constant values are in CONSTANT_Integer_info, CONSTANT_Float_info, CONSTANT_Long_info, or CONSTANT_Double_info structures.

Native Method Stacks

JVM may use native method stacks to support native methods. The native methods are written in a language other than the Java programming language. JVM implementations that cannot load native methods and that do not themselves rely on conventional stacks need not supply native method stack. If supplied, native method stacks are typical allocated per thread when each thread is created.

How does A Program’s Running Represent in JVM Memory Area

• Program start with the main method.
• Before execute the main(). 1) JVM creates a thread and allocates pc register, JVM stack, native method stack run-time memory area for the main thread. 2) JVM loading the class of main() and initializes the class static resources (that stored in constant pool). 3) create a new frame for main() method and construct the frame’s structure. 4) update the pc register to refer to the first line of main().
• JVM executing pc register referred instruction of the main thread.
• When we need to create an instance of a class in the main() method. 1) JVM loads the calling class, and initializes its static resources 2) JVM creates a new object in heap, and initializes its members, and constructs the object.
• When we calling a method of the new created object in the main(). 1) The JVM create a new frame in JVM stack for the calling method of that object, and that frame becomes current frame. 2) update pc register to refer to that method. 3) JVM executing pc register referred instruction.

Conclusion

Per-Thread Data Areas

• The pc Register. It contains the address of the JVM instruction currently being executed.
• Java Virtual Machine Stacks. It holds local variables and partial results.
• Native Method Stacks. To support native methods.

Threads-Shared Data Areas

• Heap. It contains all class instances and arrays.
• Method Area. It’s part of heap. It stores per-class structures such as run-time constant poll, field and method data, and the code for methods and constructors.
• Run-Time Constant Pool. It’s part of method area. It contains several kinds of constant, literals and reference constant.

References

[1] The Java Virtual Machine Specification

[2] JVM Stacks and Stack Frames

我在2019年的7月和8月之间大概花了两个多星期写了一个比较简单的爬虫项目，项目主要的功能是周期性的爬取一些网站的热点信息，然后把数据存在 Redis 缓存中，然后有一个可以切换不同网站和展示信息的页面。

为什么会写这个项目呢？写这个项目的原因是在 V2EX 网站上看到很多人在分享他自己做的热点聚合网站，由于，我当时属于离职状态，好久没写代码了，于是决定也写一个类似的项目练练手。于是就写了 hot-crawler 这个项目，项目的源码放在了 GitHub 上。

写完了之后，就购买了域名和云服务器，然后就部署上去了。但是，我发现网站会偶尔访问不了，无响应。发现是服务器的程序进程挂掉了，于是重新启动项目后，我在服务器的控制面板观察服务器的资源状态，看到系统占用内存会不断的升高，所以，我猜应该是内存不足导致进程挂掉了，可是不知道为什么会导致内存泄漏。由于当时已经在网上推广了自己的网站，事情比较紧急，想着用什么方法来解决呢？于是我先是把应用程序作为 Linux 自启的系统服务，这样程序挂掉之后会自动重新启动，不至于一直访问不了。然后，我又通过加一台服务器使用 Nginx 进行负载均衡。因为程序挂掉是需要经过一段时间的，然后需要十几秒的时间重启，在相同的十几秒时间，两台服务器同时挂掉的机率比较小，通过负载均衡可以错开这十几秒，从而使得网站可以持续访问。

网站挂掉的问题解决掉了，但不是真正意义上的解决。我也想去分析程序为什么会出现泄漏，但我不知从何开始。也许可能需要学习很多 JVM 相关的知识，由于当时我的学习计划是先学习计算机基础（体系结构、操作系统、算法、网络、数据库系统等），然后在深入学习 Java 和 Java Web。所以我只能先把这个问题放着，继续学习计算机基础。然而这个问题一直在我的心中困扰着我，这也是后来促使我这么强烈地想学习 JVM 的原因。

最近一段时间一直在学习 JVM，先看了 JVM 内部的实现原理，主要是 adaptive code generation, adaptive memory management, 以及 threads and synchronization。然后看了 JVM 优化的方法，主要是如何选择 JIT compiler 和 garbage collector，如何看 GC 日志，如何使用可视化工具分析程序的运行时状态，如何调整 JVM 的参数。

经过一段时间的 JVM 的学习，我准备开始分析我之前写的 hot-crawler 这个项目。下面就是我的分析过程。

1. 我先不设置 JVM 的内存大小，直接打印 GC 日志看有什么问题。下面是对应的 JVM options 和 GC log。

-XX:+PrintGCDetails -Xloggc:hotcrawler_jvm.log

Java HotSpot(TM) 64-Bit Server VM (25.171-b11) for windows-amd64 JRE (1.8.0_171-b11), built on Mar 28 2018 16:06:12 by "java_re" with MS VC++ 10.0 (VS2010)
Memory: 4k page, physical 16655468k(11303820k free), swap 19145836k(12290304k free)
CommandLine flags: -XX:InitialHeapSize=266487488 -XX:MaxHeapSize=4263799808 -XX:+PrintGC -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:-UseLargePagesIndividualAllocation -XX:+UseParallelGC 
0.809: [GC (Allocation Failure) [PSYoungGen: 65536K->10724K(76288K)] 65536K->10905K(251392K), 0.0073689 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
1.603: [GC (Allocation Failure) [PSYoungGen: 76260K->10737K(76288K)] 76441K->12235K(251392K), 0.0107562 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
2.292: [GC (Allocation Failure) [PSYoungGen: 76273K->10728K(76288K)] 77771K->18061K(251392K), 0.0105378 secs] [Times: user=0.03 sys=0.00, real=0.01 secs] 
2.669: [GC (Allocation Failure) [PSYoungGen: 76264K->10728K(141824K)] 83597K->23640K(316928K), 0.0166216 secs] [Times: user=0.13 sys=0.00, real=0.02 secs] 
3.431: [GC (Metadata GC Threshold) [PSYoungGen: 94298K->10728K(141824K)] 107211K->30083K(316928K), 0.0206330 secs] [Times: user=0.13 sys=0.00, real=0.02 secs] 
3.452: [Full GC (Metadata GC Threshold) [PSYoungGen: 10728K->0K(141824K)] [ParOldGen: 19355K->26803K(141312K)] 30083K->26803K(283136K), [Metaspace: 20761K->20761K(1069056K)], 0.1067090 secs] [Times: user=0.53 sys=0.02, real=0.11 secs] 
4.969: [GC (Allocation Failure) [PSYoungGen: 131072K->19710K(199168K)] 157875K->46522K(340480K), 0.0136119 secs] [Times: user=0.13 sys=0.00, real=0.01 secs] 
6.407: [GC (Allocation Failure) [PSYoungGen: 198910K->21995K(265728K)] 225722K->54167K(407040K), 0.0228798 secs] [Times: user=0.16 sys=0.00, real=0.02 secs] 

通过上面的 GC 日志，可以看出 HotSpot VM 把我电脑的所有可用空间（4G 多）作为了最大的堆内存空间，然后进行了若干次的 Minor GC。然后进行了一次 Full GC，增加了 Metadata 即 Permanent generation 区域的内存空间大小。然后又进行了几次 Minor GC。以上是全部的 GC 日志，后面就没有任何日志了。

通过分析直接打印 GC 日志，好像看不出什么，没什么收获。

2. 我决定设置 JVM 各个区域的内存空间大小（heap, young generation, permanent generation） ，然后再观察 GC 日志有什么变化。下面是对应的 JVM options 和 GC log。

-XX:+PrintGCDetails -Xloggc:hotcrawler_jvm.log -Xms188m -Xmx188m -XX:NewSize=70m -XX:MaxNewSize=70m -XX:MetaspaceSize=48m -XX:MaxMetaspaceSize=48m

Java HotSpot(TM) 64-Bit Server VM (25.171-b11) for windows-amd64 JRE (1.8.0_171-b11), built on Mar 28 2018 16:06:12 by "java_re" with MS VC++ 10.0 (VS2010)
Memory: 4k page, physical 16655468k(8988472k free), swap 19145836k(9640588k free)
CommandLine flags: -XX:CompressedClassSpaceSize=41943040 -XX:InitialHeapSize=197132288 -XX:MaxHeapSize=197132288 -XX:MaxMetaspaceSize=50331648 -XX:MaxNewSize=73400320 -XX:MetaspaceSize=50331648 -XX:NewSize=73400320 -XX:+PrintGC -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+UseCompressedClassPointers -XX:+UseCompressedOops -XX:-UseLargePagesIndividualAllocation -XX:+UseParallelGC 
0.662: [GC (Allocation Failure) [PSYoungGen: 54272K->8698K(62976K)] 54272K->8969K(183808K), 0.0063849 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
1.212: [GC (Allocation Failure) [PSYoungGen: 62970K->8693K(62976K)] 63241K->11555K(183808K), 0.0120044 secs] [Times: user=0.08 sys=0.03, real=0.01 secs] 
1.519: [GC (Allocation Failure) [PSYoungGen: 62965K->8680K(62976K)] 65827K->16997K(183808K), 0.0102365 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
1.822: [GC (Allocation Failure) [PSYoungGen: 62952K->8680K(62976K)] 71269K->21376K(183808K), 0.0082618 secs] [Times: user=0.13 sys=0.00, real=0.01 secs] 
2.123: [GC (Allocation Failure) [PSYoungGen: 62952K->8696K(62976K)] 75648K->26253K(183808K), 0.0090796 secs] [Times: user=0.13 sys=0.00, real=0.01 secs] 
2.519: [GC (Allocation Failure) [PSYoungGen: 62968K->8696K(48640K)] 80525K->30111K(169472K), 0.0105225 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
2.890: [GC (Allocation Failure) [PSYoungGen: 48632K->13143K(55808K)] 70047K->37449K(176640K), 0.0127155 secs] [Times: user=0.11 sys=0.02, real=0.01 secs] 
3.187: [GC (Allocation Failure) [PSYoungGen: 53079K->15846K(48640K)] 77385K->45876K(169472K), 0.0092983 secs] [Times: user=0.06 sys=0.00, real=0.01 secs] 
3.740: [GC (Allocation Failure) [PSYoungGen: 48614K->14735K(52224K)] 78644K->47682K(173056K), 0.0079699 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
3.907: [GC (Allocation Failure) [PSYoungGen: 47503K->2562K(50176K)] 80450K->48166K(171008K), 0.0091892 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 
4.044: [GC (Allocation Failure) [PSYoungGen: 33282K->1646K(32768K)] 78886K->49090K(153600K), 0.0036603 secs] [Times: user=0.11 sys=0.00, real=0.00 secs] 
4.195: [GC (Allocation Failure) [PSYoungGen: 32366K->1328K(48128K)] 79810K->50120K(168960K), 0.0050500 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
4.376: [GC (Allocation Failure) [PSYoungGen: 27952K->3178K(49152K)] 76744K->53074K(169984K), 0.0036726 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
4.543: [GC (Allocation Failure) [PSYoungGen: 29802K->2879K(49152K)] 79698K->55308K(169984K), 0.0047447 secs] [Times: user=0.13 sys=0.00, real=0.01 secs] 
4.857: [GC (Allocation Failure) [PSYoungGen: 29503K->4040K(49152K)] 81932K->58848K(169984K), 0.0043435 secs] [Times: user=0.13 sys=0.00, real=0.00 secs] 
5.262: [GC (Allocation Failure) [PSYoungGen: 30664K->1376K(49664K)] 85472K->60099K(170496K), 0.0039789 secs] [Times: user=0.09 sys=0.00, real=0.00 secs] 
5.549: [GC (Allocation Failure) [PSYoungGen: 29024K->2343K(49664K)] 87747K->62299K(170496K), 0.0041532 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
6.053: [GC (Allocation Failure) [PSYoungGen: 29991K->4762K(51200K)] 89947K->66211K(172032K), 0.0036624 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
6.323: [GC (Allocation Failure) [PSYoungGen: 34458K->1177K(50176K)] 95907K->66148K(171008K), 0.0032255 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
6.495: [GC (Allocation Failure) [PSYoungGen: 30873K->2340K(52224K)] 95844K->67544K(173056K), 0.0025049 secs] [Times: user=0.00 sys=0.00, real=0.00 secs] 
6.826: [GC (Allocation Failure) [PSYoungGen: 34596K->5084K(51712K)] 99800K->71949K(172544K), 0.0051142 secs] [Times: user=0.11 sys=0.02, real=0.01 secs] 
7.002: [GC (Allocation Failure) [PSYoungGen: 37340K->2259K(53760K)] 104205K->73418K(174592K), 0.0056459 secs] [Times: user=0.00 sys=0.00, real=0.01 secs] 

通过上面的 GC 日志，可用看出 HotSpot VM 实际分配的各个区域的内存比我们设置的要稍微大一点。然后 JVM 进行了多次的 Minor GC，不断地收集 Young generation 的空间，可能 Young generation 空间设置的小了一点，但也感觉不是小了，因为只有项目刚启动时有 Minor GC，后面一直都没有 Minor GC 了。

然而，重点来了，重点是现在没有了 Full GC，这说明 heap 的 Old generation 和 permanent generation 的内存是够用的。通过 Windows 操作系统的进程管理器会发现程序所占的内存远远超过 JVM 堆的内存，而且程序占用的内存还在不断的上升。通过 GC 日志感觉堆内存没什么问题，那么问题出在哪里呢？

3. 由于 GC 日志找不出问题，于是我决定使用 JConsole 看一下程序的运行时状态。经过一段时间的观察，我似乎找到了问题的根源，那就是 thread 太多了，并且不断的在增加。下图是 thread 的变化曲线。

于是我回想代码中哪里会创建线程或线程池，我想只有一个地方创建了线程池，那就是在爬虫的定时任务中创建线程池进行页面的爬取。这行代码如下所示：

ExecutorService executorService = Executors.newFixedThreadPool(threadPoolNum);

虽然这行创建线程池没什么问题，但是我把创建线程池的代码写在了定时任务执行的方法中，因此，每执行一次任务，就会创建一个线程池和若干的线程。我立刻把线程池定义成了成员变量，然后观察 JVM 的内存和线程，发现一切都稳定、正常了。内存空间和线程数不会一直增加。下图是修复代码后的线程变化图：

通过自己的努力，我终于解决了那个积压已久的问题。在重新部署后的那一刻，我内心是无比的兴奋与激动。

以前自己写代码主要在乎功能的实现，经过这个教训，更让我懂得了软件的性能和稳定性的重要性。

What is Proxy

The Proxy is a design pattern in software design. It provides a surrogate or placeholder for another object to control access to it. It lets you call a method of a proxy object the same as calling a method of a POJO. But the proxy’s methods can do additional things than POJO’s method.

Why Do We Need Proxy

• It lets you control to access an object. For example, to delay an object’s construction and initialization.
• It lets you track the object access. For example, tracking methods access that can analyze user behavior or analyze system performance.

How to Use Proxy in Java

There are commonly three ways to implement the proxy pattern in Java: static proxy, JDK dynamic proxy, and CGLib dynamic proxy.

Static Proxy

The static proxy implemented by reference the common class in proxy class. The following example is a basic static proxy implementation:

public interface Subject{
    void request();
}

public class RealSubject implements Subject{
    public void request(){
        System.out.println("request to RealSubject...");
    }
}

public interface Proxy extends Subject{}

public class ConcreteProxy implements Proxy{
    private RealSubject realSubject = new RealSubject();
    public void request(){
        System.out.println("before...");
        realSubject.request();
        System.out.println("after...");
    }
}

public class Client{
    public static void main(String[] args){
        Subject subject = new ConcreteProxy();
        subject.request();
    }
}

JDK Dynamic Proxy

The JDK dynamic proxy implemented in package java.lang.reflect of Java API. Its underlying implementation is the Java reflection.

The manly class for implemented dynamic proxy are: the interface java.lang.reflect.InvocationHandler, and the class java.lang.reflect.Proxy.

You can call the Proxy‘s a static method Object newProxyInstance(ClassLoader loader, Class<?>[] interfaces, InvocationHandler h) to get a proxy object.

• The ClassLoader instance commonly use ClassLoader.getSystemClassLoader().
• The array of Class Class<?>[] is the interfaces you want to implement.
• The InvocationHandler instance is an invocation handler that handling proxy method calling with the method invoke(Object proxy, Method method, Object[] args). We need to create an invocation handler by implementing the interface InvocationHandler.

The following code example is a basic JDK Dynamic proxy implementation:

public interface Subject{
    void request();
}

public class RealSubject implements Subject{
    public void request(){
        System.out.println("request to RealSubject...");
    }
}

public class MyInvocationHandler implements InvocationHandler {
    private RealSubject realSubject = new RealSubject();

    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("before...");
        Object result = method.invoke(realSubject, args);
        System.out.println("after...");
        return result;
    }
}

public class Client {
    public static void main(String[] args) {
        Subject subject = (Subject) Proxy.newProxyInstance(
                ClassLoader.getSystemClassLoader(),
                new Class[]{Subject.class}, new MyInvocationHandler());
        subject.request();
    }
}

Properties of Proxy Classes

• All proxy classes extend the class java.lang.reflect.Proxy.
• A proxy class has only one instance field–the invocation handler, which is defined in the Proxy superclass.
• Any additional data required to carry out the proxy objects’ tasks must be stored in the invocation handler. The invocation handler wrapped the actual objects.
• The name of proxy classes are not defined. The Proxy class in Java virtual machine generates class names that begin with string $Proxy.
• There is only one proxy class for a particular class loader and ordered set of interfaces. If you call the newProxyInstance method twice with the same class loader and interface array, you get two objects of the same class. You can get class by Proxy.getProxyClass(). You can test whether a particular Class object represents a proxy class by calling the isProxyClass method of the Proxy class.

CGLib Dynamic Proxy

CGLib (Code Generation Library) is an open source library that capable creating and loading class files in memory during Java runtime. To do that it uses Java bytecode generation library ‘asm’, which is a very low-level bytecode creation tool. CGLib can proxy to objects without Interface.

<dependency>
    <groupId>cglib</groupId>
    <artifactId>cglib</artifactId>
    <version>3.3.0</version>
</dependency>

How to Use CGLib

To create a proxy object using CGLib is almost as simple as using the JDK reflection proxy API. The following code example is a basic CGLib Dynamic proxy implementation:

public interface Subject{
    void request();
}

public class RealSubject implements Subject{
    public void request(){
        System.out.println("request to RealSubject...");
    }
}

public class MyMethodInterceptor implements MethodInterceptor {
    private final Subject realSubject;

    public MyMethodInterceptor(Subject subject){
        this.realSubject = subject;
    }

    @Override
    public Object intercept(Object o, Method method, Object[] args, MethodProxy methodProxy) throws Throwable {
        System.out.println("before...");
        Object result = method.invoke(realSubject, args);
        System.out.println("after...");
        return result;
    }
}

public class Client {
    public static void main(String[] args) {
        Subject subject = new RealSubject();
        MethodInterceptor methodInterceptor = new MyMethodInterceptor(subject);
        Subject proxy = (Subject) Enhancer.create(Subject.class, methodInterceptor);
        proxy.request();
    }
}

The difference between JDK dynamic proxy and CGLib is that name of the classes are a bit different and CGLib do not have an interface.

It is also important that the proxy class extends the original class and thus when the proxy object is created it invokes the constructor of the original class.

Conclusion

Differences between JDK proxy and CGLib:

• JDK Dynamic proxy can only proxy by interface (so your target class needs to implement an interface, which is then also implemented by the proxy class). CGLib (and javassist) can create a proxy by subclassing. In this scenario the proxy becomes a subclass of the target class. No need for interfaces.
• JDK Dynamic proxy generates dynamically at runtime using JDK Reflection API. CGLib is built on top of ASM, this is mainly used the generate proxy extending bean and adds bean behavior in the proxy methods.

References

[1] Core Java Volume I Fundamentals by S, Horstmann

[2] Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides

[3] Understanding “proxy” arguments of the invoke method of java.lang.reflect.InvocationHandler - Stack Overflow

[4] cglib - GitHub

[5] Introduction to cglib

[6] Creating a Proxy Object Using cglib

[7] What is the difference between JDK dynamic proxy and CGLib? - Stack Overflow

The EXPLAIN command is the main way to find out how the query optimizer decides to execute queries. This feature has limitations and doesn’t always tell the truth, but its output is the best information available. Interpreting EXPLAIN will also help you learn how MySQL’s optimizer works.

Invoking EXPLAIN

To use EXPLAIN, simply add the word EXPLAIN just before the SELECT keyword in your query. MySQL will set a flag on the query. When it executes the query, the flag cases it to return information about each step in the execution plan, instead of executing it. It returns one or more rows, which show each part of the execution plan and the order of execution. There is a simple example of EXPLAIN query statement:

EXPLAIN SELECT 1;

There is one row in the output per table in the query. If the query joins two tables, there will be two rows of output. The meaning of “table” is fairly broad meaning: it can mean a subquery, a UNION result, and so on.

It’s a common mistake that MySQL doesn’t execute a query when you add EXPLAIN to it. In fact, if the query contains a subquery in the FROM clause, MySQL actually executes the subquery, places its results into a temporary table, and finishes optimizing the outer query. It has to process all such subqueries before it can optimize the outer query fully, which it must do for EXPLAIN. This means EXPLAIN can actually cause a great deal of work for the server if the statement contains expensive subqueries or views that use the TEMPTABLE algorithm.

EXPLAIN is an approximation. Sometimes it’s a good approximation, but at other times, it can be very far from the truth. Here are some of its limitation:

• EXPLAIN doesn’t tell you anything about how triggers, stored functions, or UDFs will affect your query.
• It doesn’t work for stored procedures.
• It doesn’t tell you about optimization MySQL does during query execution.
• Some of the statistics it shows are estimates and can be very inaccurate.
• It doesn’t show you everything there is to know about a query’s execution plan.
• It doesn’t distinguish between some things with the same name. For example, it uses “filesort” for in-memory sorts and for temporary files, and it displays “Using temporary” for temporary tables on disk and in memory.

Rewriting Non-SELECT Queries

MySQL explain only SELECT queries, not stored routine calls or INSERT, UPDATE, DELETE, or any other statements. However, you can rewrite some non-SELECT queries to be EXPLAIN-able. To do this, you just need to convert the statement into an equivalent SELECT that accesses all the same columns. Any columns mentioned must be in a SELECT list, a join clause, or a WHERE clause. Note that since MySQL 5.6, it can explain INSERT, UPDATE, and DELETE statements.

For example:

UPDATE actor 
INNER JOIN film_actor USING(actor_id)
SET actor.last_update=film_actor.last_update;

To

EXPLAIN SELECT actor.last_update, film_actor.last_update 
FROM actor 
INNER JOIN film_actor USING(actor_id)

The Columns in EXPLAIN

EXPLAIN’s output always has the same columns, which adds a filtered column in MySQL 5.1.

Keep in mind that the rows in the output come in the order in which MySQL actually executes the parts of the query, which is not always the same as the order in which they appear in the original SQL. In EXPLAIN of MySQL, there are columns: id, select_type, table, partitions, type, possible_keys, key_len, ref, rows, filtered, Extra.

The id Column

The column always contains a number, which identifies the SELECT to which the row belongs.

MySQL divides SELECT queries into simple and complex types, and the complex types can be grouped into three broad classes: simple subqueries, derived tables (subqueries in the FROM clause), and UNIONs. Here is a simple subquery example:

EXPLAIN SELECT (SELECT 1 FROM sakila.actor LIMIT 1) FROM sakila.film;

+----+-------------+-------+...
| id | select_type | table |...
+----+-------------+-------+...
| 1  | PRIMARY     | film  |...
| 2  | SUBQUERY    | actor |...
+----+-------------+-------+...

Here is a derived tables query example:

EXPLAIN SELECT film_id FROM (SELECT film_id FROM sakila.film) AS der;

+----+-------------+------------+...
| id | select_type | table      |...
+----+-------------+------------+...
| 1  | PRIMARY     | <derived2> |...
| 2  | DERIVED     | film       |...
+----+-------------+------------+...

A UNION query example:

EXPLAIN SELECT 1 UNION ALL SELECT 1;

+------+--------------+------------+...
| id   | select_type  | table      |...
+------+--------------+------------+...
| 1    | PRIMARY      | NULL       |...
| 2    | UNION        | NULL       |...
| NULL | UNION RESULT | <union1,2> |...
+------+--------------+------------+...

UNION results are always placed into an anonymous temporary table, and MySQL then reads the results back out of the temporary table. The temporary table doesn’t appear in the original SQL, so its id columns is NULL.

The select_type Column

This column shows whether the row is a simple or complex SELECT (and if it’s the latter, which of the three complex types it is). The value SIMPLE means the query contains no subqueries or UNIONs. If the query has any such complex subparts, the outermost part is labeled PRIMARY, and other parts are labeled as follows:

• SUBQUERY. A SELECT that is contained in a subquery in the SELECT clause (not in the FROM clause) is labeled SUBQUERY.
• DERIVED. A SELECT that is contained in a subquery in the FROM clause. The server refers to this as a “derived table” internally, because the temporary table is derived from the subquery.
• UNION. The second and subsequent SELECTs in a UNION are labeled as UNION. The first SELECT is labeled PRIMARY as though it is executed as part of the outer query.
• UNION RESULT. The SELECT used to retrieve results from the UNION’s anonymous temporary table is labeled as UNION RESULT.

In addition to these values, a SUBQUERY and a UNION can be labeled as DEPENDENT and UNCACHEABLE. DEPENDENT means the SELECT depends on data that is found in an outer query; UNCACHEABLE means something in the SELECT prevents the result form being cached with an Item_cache (such as the RAND() function).

UNCACHEABLE UNION example:

EXPLAIN select tmp.id 
FROM (SELECT * FROM test t1 WHERE t1.id=RAND() 
     UNION ALL 
	SELECT * FROM test t2 WHERE t2.id=RAND()) AS tmp;

+----+-------------------+------------+...
| id | select_type       | table      |...
+----+-------------------+------------+...
| 1  | PRIMARY           | <derived2> |...
| 2  | DERIVED           | t1         |...
| 3  | UNCACHEABLE UNION | t2         |...
+----+-------------------+------------+...

The table Column

This column shows which table the row is accessing. It’s the table, or its alias. The number of the rows in EXPLAIN equals the sum of number of SELECT, JOIN and UNION.

MySQL’s query execution plans are always left-deep trees. The leaf nodes in order correspond directly to the rows in EXPLAIN. For example:

EXPLAIN SELECT film.film_id
FROM sakila.film
	INNER JOIN sakila.film_actor USING(film_id)
	INNER JOIN sakila.actor USING(actor_id);

+----+-------------+------------+...
| id | select_type | table      |...
+----+-------------+------------+...
| 1  | SIMPLE      | actor      |...
| 1  | SIMPLE      | film_actor |...
| 1  | SIMPLE      | film       |...
+----+-------------+------------+...

Derived tables and unions

The table column becomes much more complicated when there is a subquery in the FROM clause or a UNION. In these cases, there really isn’t a “table” to refer to, because the anonymous temporary table MySQL creates exists only while the query is executing.

When there’s a subquery in the FROM clause, the table column is of the form <derivedN>, where N is the subquery’s id. This always a “forward reference”. In other words, N refers to a later row in the EXPLAIN output.

When there’s a UNON, the UNION RESULT table column contains a list of ids that participate in the UNION. This is always a “backward reference”, because the UNION RESULT comes after all of the rows that participate in the UNION.

Example of a complex SELECT types:

1 EXPLAIN
2 SELECT actor_id,
3 	(SELECT 1 FROM sakila.film_actor WHERE film_actor.actor_id =
4 		der_1.actor_id LIMIT 1)
5 FROM (
6 	SELECT actor_id
7 	FROM sakila.actor LIMIT 5
8 ) AS der_1
9 UNION ALL
10 SELECT film_id,
11 	 (SELECT @var1 FROM sakila.rental LIMIT 1)
12 FROM (
13 	 SELECT film_id,
14 		(SELECT 1 FROM sakila.store LIMIT 1)
15 	 FROM sakila.film LIMIT 5
16 ) AS der_2;

+------+----------------------+------------+...
| id   | select_type          | table      |...
+------+----------------------+------------+...
| 1    | PRIMARY              | <derived3> |...
| 3    | DERIVED              | actor      |...
| 2    | DEPENDENT SUBQUERY   | film_actor |...
| 4    | UNION                | <derived6> |...
| 6    | DERIVED              | film       |...
| 7    | SUBQUERY             | store      |...
| 5    | UNCACHEABLE SUBQUERY | rental     |...
| NULL | UNION RESULT         | <union1,4> |...
+------+----------------------+------------+...

Reading EXPLAIN’s output often requires you to jump forward and backward in the list.

The type Column

The MySQL manual says this column shows the “join type”, but it’s more accurate to say the access type. In other words, how MySQL has decided to find rows in the table. Here are the most important access methods, from worst to best:

• ALL. This means a table scan. MySQL must scan through the table from beginning to end to find the row. (There are exceptions, such as queries with LIMIT or queries that display “Using distinct/not exist” in the Extra column.)
• index. This means an index scan. The main advantage is that this avoids sorting. The biggest disadvantage is the cost of reading an entire table in index order. This usually means accessing the rows in random order, which is very expensive. If you also see “Using index” in the Extra column, it means MySQL is using a covering index. This is much less expensive than scanning the table in index order.
• range. A range scan is a limited index scan. It begins at some point in the index and returns rows that match a range of values. This is better than a full index scan because it doesn’t go through the entire index. Obvious range scans are queries with a BETWEEN or > in the WHERE clause.
• ref. This is an index access (or index lookup) that returns rows that match a single value. The ref_or_null access type is a variation on ref. It means MySQL must do a second lookup to find NULL entries after doing the initial lookup.
• eq_ref. This is an index lookup that MySQL knows will return at most a single value. You will see this access method when MySQL decides to use a primary key or unique index to satisfy the query by comparing it to some reference value.
• const, system. MySQL uses these access types when it can optimize away some part of the query and turn it into a constant. The table has at most one matching row, which is read at the start of the query. For example, if you select a row’s primary key by placing it primary key into then where clause. e.g SELECT * FROM <table_name> WHERE <primary_key_column>=1;
• NULL. This access method means MySQL can resolve the query during the optimization phase and will not even access the table or index during the execution stage. For example, selecting the minimum value from an indexed column can be done by looking at the index alone and requires no table access during execution.

Other types

• fulltext. The join is performed using a FULLTEXT index.
• index_merge. This join type indicates that the Index Merge optimization is used. In this case, the key column in the output row contains a list of indexes used. Indicates a query to make limited use of multiple indexes from a single table. For example, the film_actor table has an index on film_id and an index on actor_id, the query is SELECT film_id, actor_id FROM sakila.film_actor WHERE actor_id = 1 OR film_id = 1
• unique_subquery. This type replaces eq_ref for some IN subqueries of the following form. value IN (SELECT primary_key FROM single_table WHERE some_expr)
• index_subquery. This join type is similar to unique_subquery. It replaces IN subqueries, but it works for nonunique indexes in subqueries. value IN (SELECT key_column FROM single_table WHERE some_expr)

The possible_keys Column

This column shows which indexes could be used for the query, based on the columns the query accesses and the comparison operators used. This list is created early in the optimization phase, so some of the indexes listed might be useless for the query after subsequent optimization phases.

The key Column

This column shows which index MySQL decided to use to optimize the access to the table. If the index doesn’t appear in possible_keys, MySQL chose it for another reason–for example, it might choose a covering index even when there is no WHERE clause.

In other words, possible_keys reveals which indexes can help make row lookups efficient, but key shows which index the optimizer decided to use to minimize query cost.

Here’s an example:

EXPLAIN SELECT actor_id, film_id FROM sakila.film_actor;

*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: film_actor
type: index
possible_keys: NULL
key: idx_fk_film_id
key_len: 2
ref: NULL
rows: 5143
Extra: Using index

The key_len Column

This column shows the number of bytes MySQL will use in the index. If MySQL is using only some of the index’s columns, you can use this value to calculate which columns it uses. Remember that MySQL 5.5 and older versions can use only the left most prefix of the index. For example, file_actor’s primary key covers two SMALLINT columns, and a SMALLINT is two bytes, so each tuple in the index is four bytes. Here’s a query example:

EXPLAIN SELECT actor_id, film_id FROM sakila.film_actor WHERE actor_id=4;

...+------+---------------+---------+---------+...
...| type | possible_keys | key    | key_len  |...
...+------+---------------+---------+---------+...
...| ref  | PRIMARY       | PRIMARY | 2       |...
...+------+---------------+---------+---------+...

You can use EXPLAIN to get how many bytes in one row of the index, then to calculate the query uses how much rows index by the key_len of the EXPLAIN.

MySQL doesn’t always show you how much of an index is really being used. For example, if you perform a LIKE query with a prefix pattern match, it will show that the full width of the column is being used.

The key_len column shows the maximum possible length of the indexed fields, not the actual number of bytes the data in the table used.

The ref Column

This column shows which columns or constant from preceding tables are being used to look up values in the index named in the key column.

The rows Column

This column shows the number of rows MySQL estimates it will need to read to find the desired rows.

Remember, this is the number of rows MySQL thinks it will examine, not the number of rows in the result set. Also realize that there are many optimizations, such as join buffers and caches, that aren’t factored into the number of rows shown.

The filtered Column

This column shows a pessimistic estimate of the percentage of rows that will satisfy some condition on the table, such as a WHERE clause or a join condition. If you multiply the rows column by this percentage, you will see the number of rows MySQL estimates it will join with the previous tables in the query plan.

The Extra Colum

This column contains extra information that doesn’t fit into other columns. The most important values you might frequently are as follows:

• Using index. This indicates that MySQL will use a covering index to avoid accessing the table.
• Using where. This means the MySQL server will post-filter rows after the storage engine retrieves them.
• Using temporary. This means MySQL will use a temporary table while sorting the query’s result.
• Using filesort. This means MySQL will use an external sort to order the results, instead of reading the rows from the table in index order. MySQL has two filesort algorithms. Either type can be done in memory or on disk. EXPLAIN doesn’t tell you which type of filesort MySQL will use, and it doesn’t tell you whether the sort will be done in memory or on disk.
• Range checked for each record (index map:N). This value means there’s no good index, and the indexes will be reevaluated for each row in a join. N is a bitmap of the indexes shown in possible_keys and is redundant.
• Using index condition: Tables are read by accessing index tuples and testing them first to determine whether to read full table rows.

Improvements in MySQL 5.6

Some EXPLAIN improvements in MySQL 5.6

• To explain queries such as UPDATE, INSERT, and so on.
• A variety of improvements to the query optimizer and execution engine that allow anonymous temporary tables to be materialized as late as possible, rather than always creating and filling them before optimizing and executing the portions of the query that refer to them. This will allow MySQL to explain queries with subqueries instantly, without having to actually execute the subqueries first.

Conclusion

The most important columns of EXPLAIN are type and Extra. They determine does the query uses an index or covering index.

the most important access methods (the type column of EXPLAIN), from worst to best:

• ALL
• index
• range
• ref
• eq_ref
• const, system
• NULL

References

[1] High Performance MySQL by Baron Schwartz, Vadim Tkachenko, Peter Zaitsev, Derek J. Balling

[2] EXPLAIN Output Format - MySQL 8.0 Documentation

Principles of MySQL Optimization

Using general principles and best practices to create your table schema.

Understanding the structure and properties of different kinds of indexes, and to choose a proper kind of index.

According to query statements in your application to create indexes, creates as few indexes as possible. And makes your indexes covering as more frequently selected columns as possible.

Using EXPLAIN to check how a query execution.

Using query profiling to determine which strategy is optimal, or which query is faster.

Common Strategies for MySQL Optimization

• Schema
  • Choosing optimal data types.
  • Denormalization.
  • Cache and Summary Tables.
• Index
  • Common indexes such as B-Tree, Hash, and Bitmap.
  • Multi-column indexes and covering indexes, prefix indexes and compressed indexes.
  • Avoid to add redundant and duplicate indexes, and remove unused indexes.
• Query
  • Queries tricks. For example, chopping up a query (or finding difference set).
  • Join decomposition. Converting join to single-table queries.
  • Using query optimizer hints.
  • Optimizing specific types of queries.
  • Do complex operations in application programs instead of in database systems. Complex operations: join, nested subqueries, group by, order by.

This post is talking about MySQL query optimization, if you are familiar with this topic, you can go to the conclusion part that’s a good summary of the query optimization in MySQL that may give you some enlightenment.

Schema optimization and indexing, which are necessary for high performance. But they are not enough, you also need to design your queries well. If your queries are bad, even the best-designed schema and indexes will not perform well.

We need to understand deeply how MySQL really executes queries, so you can reason about what is efficient or inefficient, exploit MySQL’s strengths, and avoid its weakness.

Why Are Queries Slow

Before trying to write fast queries, you need to know the good or bad queries are determined by response time. Queries are tasks, but they are composed of subtasks, and those subtasks consume time. To optimize a query, you must optimize its subtasks by eliminating them, make them happen fewer times, or making them happen more quickly.

You can use profiling a query to find out what subtasks performs to execute a query, and which ones are slow. In general, you can think of a query’s lifetime by following the query through its sequence from the client to the server, where it is parsed, planned, and executed, and then back again to the client. Execution is one of the most important stages in a query’s lifetime. It involves lots of calls to the storage engine to retrieve rows, as well as post-retrieval operations such as grouping and sorting.

While accomplishing all these tasks, the query spends time on the network, in the CPU, in operations (such as statistics and planning, locking, and call the storage engine to retrieve rows).

In every case, excessive time may be consumed because the operations are performed needless, performed too many times, or are too slow. The goal of optimization is to avoid that, by eliminating or reducing operations, or making them faster. For do this optimization, we need to understanding a query’s lifecycle and thinking in terms of where the time is consumed.

Slow Query Basic: Optimize Data Access

The most basic reason a query doesn’t perform well is because it’s working with too much data. We can use the following methods to find out whether your query is access to more data than it needs.

• Find out whether your application is retrieving more data than you need. That means it’s accessing too many rows, or accessing too many columns.
• Find out whether the MySQL server is analyzing more rows than it needs.

Are You Asking the Database for Data You Don’t Need

Some query ask for more data than they need and then throw some of it away. This demands extra work of the MySQL server, adds network overhead, and consumes memory and CPU resources on the application server.

The common mistakes of fetching more data

• Fetching more rows than needed.
• Fetching all columns from a multi-table join.
• Fetching all columns.
• Fetching the same data repeatedly. You don’t need to fetch multiple times for the same data. You could cache it the first time you fetch it, and reuse it thereafter.

Is MySQL Examining Too Much Data

Once you are sure your queries retrieve only the data you need, you can look for queries that examine too much data while generating results. In MySQL, the simplest query cost metrics are:

• Response time.
• Number of rows examined
• Number of rows returned

None of these metrics is a perfect way to measure query cost, but they reflect roughly how much data access to execute a query and translate approximately into how fast the query runs. All three metrics are logged in the query log, so looking at the query log is one of the best ways to find queries that examine too much data.

Response time

Response time is the sum of two things: service time and queue time. Service time is how long it takes the server to actually process the query. Queue time is the portion of response time during which the server isn’t really executing the query–it’s waiting for something, such as I/O, row lock and so forth. As a result, response time is not consistent under varying load conditions. When you look at a query’s response time, you should ask yourself whether the response time is reasonable for the query.

Rows examined and rows return

It’s useful to think about the number of rows examined when analyzing queries, because you can see how efficiently the queries are finding data you need.

However, not all row accesses are equal. Shorter rows are faster to access, and fetching rows form memory is much faster than reading them from disk.

Ideally, the number of rows examined would be the same as the number returned, but in practice this rarely possible. For example, when constructing rows with joins.

Rows examined and access types

MySQL can use several access methods to find and return a row. Some require examining many rows, but others might be without examining any.

The access methods appear in the type column in EXPLAIN’s output. The access types range from a full table scan to index scans, range scans, unique index lookups, and constants. Each of these is faster than the one before it, because it requires reading less data.

If you aren’t getting a good access type, the best way to solve the problem is usually by adding an appropriate index.

In general, MySQL can apply a WHERE clause in three ways, from best to worst:

• Apply the conditions to the index lookup operation to eliminate nonmatching rows. This happen at the storage engine layer.
• Use a covering index (“Using index” in the Extra column of EXPLAIN) to avoid row accesses and filter out nonmatching rows after retrieving each result from the index.
• Retrieve rows from the table, then filter nonmatching rows (“Using where” in the Extra column of EXPLAIN). This happens at the server layer.

Good indexes help your queries get a good access type and examine only the rows they need. However, adding an index doesn’t always mean that MySQL will access fewer rows, or access and return the same number of rows. For example, a query that uses the COUNT() aggregate function.

If you find that a huge number of rows were examined to produce relatively few rows in the result, you can try some more sophisticated fixes:

• Use covering indexes.
• Change the schema.
• Rewrite a complicated query.

Ways to Restructure Queries

As you optimize problematic queries, your goal should be to find alternative ways to get the result you want. You can sometimes transform queries into equivalent forms that return the same results, and get better performance.

Complex Queries Versus Many Queries

It’s a good idea to use as few queries as possible, but sometimes you can make a query more efficient by decomposing it and executing a few simple queries instead of one complex one.

Chopping Up a Query

Another way to slice up a query is to divide and conquer, keeping it essentially the same but running it in smaller “chunks” that affect fewer rows each time.

Purging old data is a great example. For example:

DELETE FROM messages WHERE created < DATE_SUB(NOW(), INTERVAL 3 MONTH);

It might also be a good idea to add some sleep time between the DELETE statements to spread the load over time and reduce the amount of time locks are held.

Join Decomposition

Many high-performance applications use join decomposition. You can decompose a join by running multiple single-table queries instead of a multitable join. For example:

SELECT * FROM tag
    JOIN tag_post ON tag_post.tag_id=tag.id
    JOIN post ON tag_post.post_d=post.id
WHERE tag.tag='mysql';

replace to

SELECT * FROM tag WHERE tag='mysql';
SELECT * FROM tag_post WHERE tag_id=1234;
SELECT * FROM post WHERE post.id in (123,456,567,8876);

Advantages of multiple single-table queries

• Caching can be more efficient.
• Executing the queries individually can sometimes reduce lock contention.
• The queries themselves can be more efficient.
• You can reduce redundant row accesses.

Query Execution Basics

If you need to get high performance from your MySQL server, one of the best ways to learning how MySQL optimizes and executes queries.

The process MySQL to execute queries:

1. The client sends the SQL statement to the server.
2. The server checks the query cache. If there’s a hit, it returns the stored result from the cache, otherwise to next step.
3. The server parses, preprocesses, and optimizes the SQL into a query execution plan.
4. The query execution engine executes the plan by making calls to the storage engine API.
5. The server sends the result to the client.

The MySQL Client/Server Protocol

The protocol is half-duplex, which means that at any given time the MySQL server can be either sending or receiving messages, but not both. This protocol makes MySQL communication simple and fast, but it have some limitation. For example, once one side sends a message, the other side must fetch the entire message before responding.

The client sends a query to the server as a single packet of data. So max_allowed_packet configuration variable is important if you have large queries.

In contrast, the response from the server usually consist of many packets of data. When the server responds, the client has to receive the entire result set. Most libraries that connect to MySQL let you either fetch the whole result and buffer it in memory, or fetch each row as you need it.

Query States

Each MySQL connection, or thread, has a state that shows what it is doing at any given time. There are several ways to view these states, but the easiest is to use the SHOW FULL PROCESSLIST command. The basic states in MySQL:

• Sleep
• Query
• Locked
• Analyzing and statistics
• Copying to tmp table [on disk]
• Sorting result
• Sending data

The Query Cache

Before parsing a query, MySQL checks for it in the query cache, if the cache is enabled. This operation is a case-sensitive hash lookup. If the query differs from a similar query in the cache by even a single byte, it won’t match.

If MySQL does find a match in the query cache, it must check privileges before returning the cache query. If the privileges are OK, MySQL retrieves the stored result from the query cache and sends it to the client. The query is never parsed, optimized, or executed.

The Query Optimization Process

After doesn’t find a match in the query cache, the next step in the query lifecycle turns a SQL query into an execution plan for the query execute engine. It has several substeps: parsing, preprocessing, and optimization. Errors (like syntax errors) can be raised at any point in the process.

The parser and the preprocessor

• query parsing: MySQL’s parser breaks the query into tokens and builds a parse tree from them. The parser uses MySQL’s SQL grammar to interpret and validate the query.
• query preprocessing: the preprocessor checks the resulting parse tree for additional semantics. For example, it checks that tables and columns exist, and it resolves names and aliases to ensure that column references aren’t ambiguous. Next, the preprocessor checks privileges.

The query optimizer

After preprocessing the parse tree is now valid and ready for the optimizer to turn it into a query execution plan. A query can often be executed many different ways and produce the same result. The optimizer’s job is to find the best option.

MySQL uses a cost-based optimizer, which means it tries to predict the cost of various execution plans and choose the least expensive. The unit of cost way originally a single random 4KB data page read, but also includes factors such as the estimated cost of executing a WHERE clause comparison. You can see how expensive the optimizer estimated a query to be by running the query, then inspecting the Last_query_cost session variable:

SELECT SQL_NO_CACHE COUNT(*) FROM your_table;
SHOW STATUS LIKE 'Last_query_cost';

Result of SHOW STATUS LIKE 'Last_query_cost' means that the optimizer estimated it would need to do about how much random data page reads to execute the query.

The optimizer might not always choose the best plan, for many reasons:

• The statistics could be wrong.
• The cost metric is not exactly equivalent to the true cost of running the query.
• MySQL’s idea of optimal might not match yours. MySQL doesn’t really try to make queries fast; it tries to minimize their.
• MySQL doesn’t consider other queries that are running concurrently.
• MySQL doesn’t always do cost-based optimization.
• The optimizer doesn’t take into account the cost of operations not under its control, such as executing stored functions.

MySQL’s join execution strategy

MySQL consider every query a join–not just every query that matches rows from two tables, but every query. It’s very important to understand how MySQL executes joins.

MySQL’s join execution strategy is simple: it treats every join as a nested-loop join. This means MySQL runs a loop to find a row from a table, then run a nested loop to find a matching row in the next table. It continues until it has found a matching row in each table in the join. For example:

SELECT tab1.col1, tab2.col2 
FROM tab1 INNER JOIN tab2 USING(col3)
WHERE tab1.col1 in (5, 6);

following pseudocode shows how MySQL might execute the query:

outer_iter = iterator over tbl1 where col1 IN(5,6)
outer_row = outer_iter.next
while outer_row
	inner_iter = iterator over tbl2 where col3 = outer_row.col3
	inner_row = inner_iter.next
	while inner_row
		output [ outer_row.col1, inner_row.col2 ]
		inner_row = inner_iter.next
	end
	outer_row = outer_iter.next
end

First Finding table iterator that fulfills the WHERE condition, then finding equal values on join columns.

The execution plan

MySQL doesn’t generate byte-code to execute a query, instead, the query execution plan is actually a tree of instructions that the query execution engine follows to produce the query results.

Any multitable query can conceptually be represent as a tree. MySQL always begins with one table and finds matching rows in the next table. Thus, MySQL’s query execution plans always take the form of left-deep tree. As shown in the figure below.

The join optimizer

The most important part of the MySQL query optimizer is the join optimizer, which decides the best order of execution for multitable queries.

MySQL’s join optimizer can reorder queries to make them less expensive to execute. You can use STRAIGHT_JOIN and write queries in the order you think is best, but such times are rare. In most cases, the join optimizer will outperform a human.

Sort optimizations

Sorting results can be a costly operation, so you can often improve performance by avoiding sorts or by performing them on fewer rows.

When MySQL can’t use an index to produce a sorted result, it must sort the rows itself. It can do this in memory or on disk, but it always calls this process a filesort, even if it doesn’t actually use a file.

If the values to be sorted will fit into the sort buffer, MySQL can perform the sort entirely in memory with a quiksort. If MySQL can’t do the sort in memory, it performs it on disk by sorting the values in chunks with quicksort, and then merges the sorted chunks into results.

When sorting a join, if the ORDER BY clause refers only to columns from the first table in the join order, MySQL can filesort this table and then proceed with the join. This case will show “Using filesort” in the Extra column of EXPLAIN. If ORDER BY clause contains columns from more than one table, MySQL must store the query’s results into a temporary table and then filesort then temporary table after the join finishes. This case will show “Using temporary; Using filesort” in the Extra column of EXPLAIN.

The Query Execution Engine

The parsing and optimizing stage outputs a query execution plan, which MySQL’s query execution engine uses to process the query. The plan is a data structure; it is not executable byte-code, which is how many other database execute queries.

In contrast to the optimization stage, the execution stage is usually not all that complex: MySQL simply follows the instructions given in the query execution plan. Many of the operations in the plan invoke methods implemented by the storage engine interface, also known as the handler API.

To execute the query, the server just repeats the instructions until there are no more rows to examine.

Returning Results to the Client

The final step in executing a query is to reply to the client. Even queries that don’t return a result set still reply to the client connection with information about the query, such as how many rows it affected.

The server generates and sends results incrementally. As soon as MySQL processes the last table and generates one row successfully, it can and should send that row to the client. This has two benefits: it lets the server avoid holding the row in memory, and it means the client starts getting the results as soon as possible. Each row in the result set is sent in a separate packet in the MySQL client/server protocol, although protocol packets can be buffered and sent together at the TCP protocol layer.

Limitations of the MySQL Query Optimizer

Correlated Subqueries

MySQL sometimes optimizes subqueries very badly. The worst offenders are IN() subqueries in the WHERE clause.

The standard advice for this query is to write it as a LEFT OUTER JOIN instead of using a subquery.

UNION Limitations

You should put condition clauses inside each part of the UNION.

For example, if you UNION together two tables and LIMIT the result to the first 20 rows:

Query 1:

This query will store all rows of tables into a temporary table then fetch first 20 rows form that temporary table.

(SELECT first_name, last_name
FROM sakila.actor
ORDER BY last_name)
UNION ALL
(SELECT first_name, last_name
FROM sakila.customer
ORDER BY last_name)
LIMIT 20;

Query 2:

This query will store first 20 rows each table into a temporary table and then fetch first 20 rows from that temporary table.

(SELECT first_name, last_name
FROM sakila.actor
ORDER BY last_name
LIMIT 20)
UNION ALL
(SELECT first_name, last_name
FROM sakila.customer
ORDER BY last_name
LIMIT 20)
LIMIT 20;

You should use query 2 (contains inside LIMIT) instead of query 1 (only outer LIMIT).

SELECT and UPDATE on the Same Table

MySQL doesn’t let you SELECT from a table while simultaneously running an UPDATE on it. To work around this limitation, you can use a derived table, because MySQL materializes it as a temporary table.

UPDATE tb1 AS outer_tb1
SET cnt = (
	SELECT count(*) tb1 AS inner_tb1
    WHERE inner_tb1.type = outer_tb1.type
);

To

UPDATE tb1 
    INNER JOIN(
        SELECT type, count(*) as cnt
        FROM tb1
        GOURP BY type
    ) AS der USING(type)
SET tb1.cnt = der.cnt;

Query Optimizer Hints

MySQL has a few optimizer hints you can use to control the query plan if you are not content with the one MySQL’s optimizer chooses. You place the appropriate hint in the query whose plan you want to modify, and it is effective for only that query. Some of them are version-dependent. You can check the MySQL manual for the exact syntax of each hint.

STRAIGHT_JOIN. Putting this hint in after the SELECT keyword that forces all tables in the query to be joined in the order in which they are listed in the statement. Putting in between two joined tables that force a join order on the two tables between which the hint appears. It is useful when MySQL doesn’t choose a good join order, or when the optimizer takes a long time to decide on a join order.

select a.id, c.id
from a
straight_join b on b.a_id = a.id
join c on c.id = b.c_id

or

select straight_join a.id, c.id
from a
b on b.a_id = a.id
join c on c.id = b.c_id

USE INDEX, IGNORE INDEX, and FORCE INDEX. These hints tell the optimizer which indexes to use or ignore for finding rows in a table.

Optimizing Specific Types of Queries

There are some advice on how to optimize certain kinds of queries. Most of the advice is version-dependent, and it might not hold for future versions of MySQL.

Optimizing COUNT() Queries

Before optimization, it’s important that you understand what COUNT() really does.

The COUNT() counts how many times that expression has a value. When you want to know the number of rows in the result, you should always use COUNT(*).

Simple Optimizations

Example 1:

SELECT COUNT(*) FROM world.City WHERE ID > 5;

replace to

SELECT (SELECT COUNT(*) FROM world.City) - COUNT(*) 
FROM world.City WHERE ID <= 5;

Example 2:

SELECT SUM(IF(color = 'blue', 1, 0)) AS blue,SUM(IF(color = 'red', 1, 0)) AS red FROM items;

replace to

SELECT COUNT(color = 'blue' OR NULL) AS blue, COUNT(color = 'red' OR NULL) AS red FROM items;

Using an approximation

Sometimes you don’t need an accurate count, so you can just use an approximation. The optimizer’s estimated rows in EXPLAIN often serves well for this. Just execute an EXPLAIN query instead of the real query.

EXPLAIN select COUNT(*) from your_table;

Fast, accurate, and simple: pick any two.

Optimizing JOIN Queries

There are some principles for optimizing JOIN queries:

• Make sure there are indexes on the columns in the ON or USING clauses. Consider the join order when adding indexes. In general, you need to add indexes only on the second table in the join order (for example, table A join B, you need add index on B rather than A), unless they’re needed for some other reason.
• Try to ensure that any GROUP BY or ORDER BY expression refers only to columns from a single table, so MySQL can try to use an index for that operation.
• Be careful when upgrading MySQL, because the join syntax, operator precedence, and other behaviors have changed at various time.

Optimizing Subqueries

The core of the post is focused on MySQL 5.1 and MySQL 5.5. In these versions of MySQL, and in most situations, you should usually prefer a join where possible, rather than subqueries. However, prefer a join is not future-proof advice, so you need be cautious with it.

Optimizing GROUP BY and DISTINCT

MySQL optimizing these two kinds of queries similarly in many cases, and in fact converts between them as needed internally during then optimization process.

MySQL has two kinds of GROUP BY strategies when it can’t use an index: it can use a temporary table or file sort to perform the grouping. Either one can be more efficient for any given query. You can force the optimizer to choose one method or the other with the SQL_BIG_RESULT and SQL_SMALL_RESULT optimizer hints.

If you need to group a join by a value that comes from a lookup table, it is usually more efficient to group by the lookup table’s identifier than by value.

SELECT actor.first_name, actor.last_name, COUNT(*)
FROM sakila.film_actor
INNER JOIN sakila.actor USING(actor_id)
GROUP BY actor.first_name, actor.last_name;

Replace to

SELECT actor.first_name, actor.last_name, COUNT(*)
FROM sakila.film_actor
INNER JOIN sakila.actor USING(actor_id)
GROUP BY film_actor.actor_id;

It’s generally a bad idea to select nongrouped columns in a grouped query, because the results will be nondeterministic and could easily change if you change an index or the optimizer decides to use a different strategy. It’s better to be explicit. We suggest you set the server’s SQL_MODE configuration variable to include ONLY_FULL_GROUP_BY so it produces an error instead of letting you write a bad query. Query select values only are grouped columns or aggregate function on grouped columns. For example:

SELECT name, COUNT(*) FROM your_table GROUP BY name;

MySQL automatically orders grouped queries by the columns in the GROUP BY clause, unless you specify an ORDER BY clause explicitly. If you don’t care about the order and you see this causing a filesort, you can use ORDER BY NULL to skip the automatic sort.

Optimizing GROUP BY WITH ROLLUP

A variation on grouped queries is to ask MySQL to do superaggregation within the results. You can do this with a WITH ROLLUP clause, but it might not be as well optimized as you need. Check the execution method with EXPLAIN , paying attention to whether the grouping is done via filesort or temporary table; try removing the WITH ROLLUP and seeing if you get the same group method.

Sometimes it’s more efficient to do superaggregation in your application, even if it means fetching many more rows from the server.

Optimizing LIMIT and OFFSET

Queries with LIMITs and OFFSETs are common in systems that do pagination, nearly always in conjunction with an ORDER BY clause. It’s helpful to have an index that supports the ordering; otherwise, the server has to do a lot of filesorts.

A frequent problem is having high value for offset. For example, if you query looks like LIMIT 10000, 20, it is generating 10020 rows and throwing away the first 10000 of them, which is very expensive. To optimize them, you can either limit how many pages are permitted in a pagination view, or try to make the high offsets more efficient.

The key of optimizing do pagination is using an index to sort rather than using a filesort. You can use join or using some methods to replace the OFFSET.

• using index for sort
  • Using join. SELECT * FROM ... JOIN (SELECT id ... ORDER BY .. LIMIT off, count)
  • Remove offset. SELECT * ... ORDER BY ... LIMIT count
  • Remove offset and limit. SELECT * ... WHERE <column> BETWEEN <start> AND <end> ORDER BY ...
• Using filesort
  • SELECT * ... ORDER BY ... LIMIT offset, row_count

1. Optimizing sort by using joins

One ways to optimizing the high value offset is offset on a covering index, rather than the full rows. You can then join the result to the full row and retrieve the additional columns you need. For example:

SELECT film_id, description FROM sakila.film ORDER BY title LIMIT 50, 5;

replace to

SELECT film.film_id, film.description
FROM sakila.film
INNER JOIN (
    SELECT film_id FROM sakila.film
    ORDER BY title LIMIT 50, 5
) AS lim USING(film_id);

SELECT id FROM your_table ORDER BT title can use the covering index(title, id). However, SELECT * ... ORDER BY title have no index to use because in general there is no covering all column index in a table, and it has to using filesort.

2. Optimizing offset by using positional range queries

Limit to a positional query, which the server can executes as an index range scan. For example:

SELECT film_id, description FROM sakila.film
WHERE position BETWEEN 50 AND 54 ORDER BY position;

3. Using a start position instead of an OFFSET

If you use a sort of bookmark to remember the position of the last row you fetch, you can generate the next set of rows by starting from that position instead of using an OFFSET.

first page query

SELECT * FROM sakila.rental
ORDER BY rental_id ASC LIMIT 20;

next page query

SELECT * FROM sakila.rental
WHERE rental_id > 20
ORDER BY rental_id ASC LIMIT 20;

Optimizing UNION

MySQL always executes UNION queries by creating a temporary table and filling it with the UNION results. MySQL can’t apply as many optimizations to UNION queries as you might be used to. You might have to help the optimizer by manually pushing down WHERE, LIMIT, ORDER BY, and other conditions because you can’t use index in temporary tables. For example, copying them, as appropriate, from the outer query into each SELECT in the UNION.

It’s important to always use UNION ALL, unless you need the server to eliminate duplicate rows. If you omit the ALL keyword, MySQL adds the distinct option to the temporary table, which uses the full row to determine uniqueness. This is quite expensive.

Static Query Analysis

Percona Toolkit contains pt-query-advisor, a tool that parses a log of queries, analyzes the query patterns, and gives annoyingly detailed advice about potentially bad practices in them. It will catch many common problems such as those we’ve mentioned in the previous sections of this post.

Conclusion

For query optimization, we should understanding query execution basic such as what is a general query execution process in MySQL.

Before we to optimize a query, we must find the reason of slow to a query. We can use EXPLAIN to see how the query to execute. However a slow query may cause by many reasons which are schema of table, indexes of table, and the query statement. We need to combine these aspects to optimize.

We know query optimization that is part of optimization. In theory, MySQL will execute some queries almost identically. In reality, measuring is the only way to tell which approach is really faster. For query optimization, There are some advice on how to optimize certain kinds of queries. Most of the advice is version-dependent, and it might not hold for future versions of MySQL.

Appendixes

Common Types of Query

• Single Table Query
• JOIN
• UNION, UNION ALL
• Subquery

Efficiency of Queries

Efficiency of kinds of single table query from high to low:

• Extra: Using index. Using covering index. (lookup in an index, fetch data from an index file).
• Extra: (isn’t Using index). That means don’t fetch data from index file.
  • type: ref (or type: range, Extra: Using index condition). Using index to find all columns of rows (lookup in an index, fetch data from a table file).
  • type: index_merge. Using multiple index to find all columns of rows (lookup in multiple indexes, fetch data from a table file). For example, select * from <table_name> where <column in index1> = <value1> or <column in index2> = <value2>.
  • type: index. To scan an index (Scan an index, fetch data from a table file).
  • type: range, Extra: Using where. Using index find all columns of rows, and the MySQL server is applying a WHERE filter after the storage engine returns the rows. (lookup in an index, fetch data from a table file, and filter data by MySQL server). For example, SELECT * FROM <table> WHERE id > 5 AND id <> 1.
  • type: ALL. To scan an table file.
    • type: ALL, Extra: Using where. To scan an table. For example, SELECT * FROM <table> WHERE <column not in index> > "".
    • type: ALL, Extra: Using where, Using filesort. To scan an table, and do a filesort. For example, SELECT * FROM <table> WHERE <column not in index> > "" order by <column not in index>.

Internal Temporary Table

In some cases, the server creates internal temporary tables while processing statement. To determine whether a statement requires a temporary table, use EXPLAIN and check the Extra column to see whether it says Using temporary

• Evaluation of UNION statements, when UNION DISTINCT, or have a global ORDER BY clause.
• Evaluation of derived tables.
• Evaluation of common table expressions (WITH)
• Evaluation of statements that contain an ORDER BY clause and a different GROUP BY clause, or for which the ORDER BY or GROUP BY contains columns from tables other than the first table in the join queue.
• Evaluation of subquery has no indexes.
• Evaluation of DISTINCT combined with ORDER BY may require a temporary table.
• For queries that use the SQL_SMALL_RESULT modifier, MySQL uses an in-memory temporary table, unless the query also contains elements that require on-disk storage.
• To evaluate INSERT … SELECT statements that select from and insert into the same table.
• Evaluation of multiple-table UPDATE statements.
• Evaluation of window functions uses temporary tables as necessary.

Some query conditions prevent the use of an in-memory temporary table, in which case the server uses an on-disk table instead:

• Presence of a BLOB or TEXT column in the table.
• Presence of any string column with a maximum length larger than 512 bytes or characters in SELECT.
• The SHOW COLUMNS and DESCRIBE statements use BLOB as the type for some columns.

Format of SELECT Statement

SELECT
    [ALL | DISTINCT | DISTINCTROW ]
    [HIGH_PRIORITY]
    [STRAIGHT_JOIN]
    [SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT]
    [SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS]
    select_expr [, select_expr] ...
    [into_option]
    [FROM table_references
      [PARTITION partition_list]]
    [WHERE where_condition]
    [GROUP BY {col_name | expr | position}, ... [WITH ROLLUP]]
    [HAVING where_condition]
    [WINDOW window_name AS (window_spec)
        [, window_name AS (window_spec)] ...]
    [ORDER BY {col_name | expr | position}
      [ASC | DESC], ... [WITH ROLLUP]]
    [LIMIT {[offset,] row_count | row_count OFFSET offset}]
    [into_option]
    [FOR {UPDATE | SHARE}
        [OF tbl_name [, tbl_name] ...]
        [NOWAIT | SKIP LOCKED] 
      | LOCK IN SHARE MODE]
    [into_option]

into_option: {
    INTO OUTFILE 'file_name'
        [CHARACTER SET charset_name]
        export_options
  | INTO DUMPFILE 'file_name'
  | INTO var_name [, var_name] ...
}

References

[1] High Performance MySQL by Baron Schwartz, Vadim Tkachenko, Peter Zaitsev, Derek J. Balling

[2] MySQL 8.0 Reference Manual

This post is talking about MySQL index, if you are familiar with this topic, you can go to the conclusion part that’s a good summary of the indexing in MySQL that may give you some enlightenment.

Indexes (also called keys in MySQL) are data structures that storage engines use to find rows quickly.

Indexes are critical for good performance, and become more important as your data grows larger. Small, lightly loaded databases often perform well even without proper indexes, but as the dataset grows, performance can drop very quickly.

Index optimization is perhaps the most powerful way to improve query performance. Indexes can improve performance by many orders of magnitude, and optimal indexes can sometimes boost performance about two orders of magnitude more than indexes that merely good. Creating truly optimal indexes will often require you to rewrite queries.

Indexing Basics

An index contains values from one or more columns in a table. If you index more than one column, the column order is very important, because MySQL can only search efficiently on a leftmost prefix of the index. Creating an index on two columns is not the same as creating two separate single-column indexes.

Types of Indexes

There are many types of indexes, each designed to perform well for different purposes. Indexes are implemented in the storage engine layer, not the server layer. Thus, they are not standardized: indexing works slightly differently in each engine, and not all engines support all types of indexes.

B-Tree Indexes

When people talk about an index without mentioning a type, they are probably referring to a B-Tree index, which uses a B-Tree data structure to store its data. Most of MySQL’s storage engines support this index type.

Storage engines use B-Tree indexes in various ways, which can affect performance. For example, MyISAM uses a prefix compression technique that makes indexes smaller, but InnoDB leaves values uncompressed in its indexes. Also, MyISAM indexes refer to the indexed rows by their physical storage locations, but InnoDB refers to them by their primary key values. Each variation has benefits and drawbacks.

A B-Tree index speeds up data access because the storage engine doesn’t have to scan the whole table to find the desired data. And you can find a specific row using O(log n) time cost from an index file.

Limitations of B-Tree indexes:

• They are not useful if the lookup does not start from the leftmost side of the indexed columns.
• You can’t skip columns in the index. For example, an index of your table is key(last_name, first_name, birth_date), if you skip first_name, MySQL can use only the first column of the index, whether the birth_date appears in the where clause.
• The storage engine can’t optimize accesses with any columns to the right of the first range condition. For example, your index is key(last_name, first_name, birth_date), and your query is WHERE last_name="xx" AND first_name LIKE "xx%" AND birth_date="xxx", the index access will use only the first two columns in the index, because the LIKE is a range condition.

Column order in index is very important, because limitations of B-Tree indexes are all related to column ordering. Some of these limitations are not inherent to B-Tree indexes, but are a result of how the MySQL query optimizer and storage engines use indexes. Some of these limitations might be removed in the future.

Hash Indexes

A hash index is built on a hash table and is useful only for exact lookups that use every column in the index. For each row, the storage engine computes a hash code of the indexed columns, which is a small value that will probably differ from the hash codes computed for other rows with different key values. It stores the hash codes in the index and stores a pointer to each row in a hash table.

Because the indexes themselves store only short hash values, hash indexes are very compact. As a result, lookups are usually lightning fast. However, hash indexes have some limitations:

• Because the index contains only hash codes and row pointer rather than the values themselves, MySQL can’t use the values in the index to avoid reading the rows. Fortunately, accessing the in-memory rows is very fast.
• MySQL can’t use hash indexes for sorting because they don’t store rows in sorted order.
• Hash indexes don’t support partial key matching, because they compute the hash from the entire indexed value. That is, if you have an index on (A, B) and your query’s WHERE clause refers only to A, the index won’t help.
• Hash indexes support only equality comparisons that use the =, in(), and <=> operators (note that <> and <=> are not the same operator). They can’t speed up range queries.
• Accessing data in hash index is very quick, unless there are many collisions (multiple values with the same hash). When there are collisions, the storage engine must follow each row pointer in the linked list to sequence lookup the right rows.
• Some index maintenance operations (delete or add a row to table) can be slow if there are many hash collisions.

These limitations make hash indexes useful only in special cases. However, when they match the application’s needs, they can improve performance dramatically.

If your storage engine doesn’t support hash indexes, you can emulate them yourself in a manner similar to that InnoDB uses.

Full-text Indexes

FULLTEXT is a special type of index that finds keywords in the text instead of comparing values directly to the values in the index. Full-text searching is completely different from other types of matching. It has many subtleties, such as stopwords, stemming and plurals, and Boolean searching. It is much more analogous to what a search engine does than to simple WHERE parameter matching.

Having a full-text index on a column does not eliminate the value of a B-Tree index on the same column. Full-text indexes are for MATCH AGAINST operations, not ordinary WHERE clause operations.

In standard MySQL, only part of storage engines supports full-text indexing, and there are third-party storage engines for full-text search, such as Sphinx, Lucene, Solr, Groonga, and so on.

Benefits of Indexes

• Indexes reduce the amount of data the server has to examine.
• Indexes help the server avoid sorting and temporary tables.
• Indexes turn random I/O into sequential I/O.

Index Strategies

Creating the correct indexes and using them properly is essential to good query performance. There are many ways to choose and use indexes effectively, because there are many special-case optimizations and specialized behaviors. We need to understand how to use indexes effectively.

Isolating the column

There are queries that defeat indexes or prevent MySQL from using the available indexes. MySQL generally can’t use indexes on columns unless the columns are isolated in the query. Isolating the column means it should not be part of an expression or be inside a function in the query. Some examples of don’t isolating the column queries.

'bad query exapmles'
mysql> SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;
mysql> SELECT ... WHERE TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) <= 10;

Prefix Indexes and Index Selectivity

Sometimes you need to index very long character columns, which makes you indexes large and slow. One strategy is to simulate a hash index.

Another way is prefix indexes. You can often save space and get good performance by indexing the first few characters instead of the whole value. This makes your indexes use less space, but it also makes them less selective. Index selectivity is the ratio of the number of distinct indexed values to the total number of rows in the table, and range from 1/rows to 1. A highly selective index is good because it lets MySQL filter out more rows when it looks for matches.

A prefix of the column is often selective enough to give good performance. If you are indexing BLOB or TEXT columns, or very long VARCHAR columns, you must define prefix indexes, because MySQL disallows indexing their full length. To create a prefix index:

CREATE INDEX index_name
ON table_name(column_name(length));

Ways to calculate a good prefix length

• Find the most frequent values and compare that list to a list of the most frequent prefixes.

• Computing the full column’s selectivity and trying to make the prefix’s selectivity close to that value.

  'full column selectivity' mysql> SELECT COUNT(DISTINCT city)/COUNT(*) FROM sakila.city_demo; '' mysql> SELECT COUNT(DISTINCT LEFT(city, 3))/COUNT(*) AS sel3, -> COUNT(DISTINCT LEFT(city, 4))/COUNT(*) AS sel4, -> COUNT(DISTINCT LEFT(city, 5))/COUNT(*) AS sel5, -> COUNT(DISTINCT LEFT(city, 6))/COUNT(*) AS sel6 -> FROM sakila.city_demo;

Prefix indexes can be a great way to make indexes smaller and faster, but they have downsides too: MySQL cannot use prefix indexes for ORDER BY or GROUP BY queries, nor can it use them as covering indexes.

A common case found to benefit from prefix indexes is when long hexadecimal identifiers are used. Adding an index on the first eight characters or so often boosts performance significantly, in a way that’s completely transparent to the application.

Multicolumn Indexes

Multicolumn indexes are often very poorly understood. Common mistakes are to index many or all of the columns separately, or to index columns in the wrong order.

Individual indexes on lots of columns won’t help MySQL improve performance for most queries. Earlier versions of MySQL could only a single index, so when no single index was good enough to help, MySQL often chose a table scan. MySQL 5.0 and newer can cope a little with such poorly indexed tables by using a strategy as index merge, which permits a query to make limited use of multiple indexes from a single table to locate desired rows.

For example, the film_actor table has an index on film_id and an index on actor_id, but neither is a good choice for both WHERE conditions in this query:

mysql> SELECT film_id, actor_id FROM sakila.film_actor
-> WHERE actor_id = 1 OR film_id = 1;

In older MySQL versions, that query would produce a table scan unless you wrote it as UNION of two queries:

mysql> SELECT film_id, actor_id FROM sakila.film_actor WHERE actor_id = 1
-> UNION ALL
-> SELECT film_id, actor_id FROM sakila.film_actor WHERE film_id = 1
-> AND actor_id <> 1;

In MySQL 5.0 and newer, the query can use both indexes, scanning them simultaneously and merging the result.

The index merge strategy sometimes works very well, but it’s more common for it to actually be an indication of a poorly indexed table.

When you see an index merge in EXPLAIN, you should examine the query and table structure to see if this is really the best you can get.

Choosing a Good Column Order

The correct order depends on the queries that will use the index, and you must think about how to choose the index order such that rows are sorted and grouped in a way that will benefit the query.

The order of columns in a multicolumn B-Tree index means that the index is sorted first by the leftmost column, the by the next column, and so on. Therefore, the index can be scanned in either forward or reverse order, to satisfy queries with ORDER BY, GOURP BY, and DISTINCT clauses that match the column order exactly.

There is a rule of thumb for choosing column order: place the most selective columns first in the index. It can be helpful in some cases, but it’s usually much less important than avoiding random I/O and sorting, all things considered. Specific cases vary, so there’s no one-size-fits-all rule. This rule of thumb is probably less important than you think.

Placing the most selective columns first can be a good idea when there is no sorting or grouping to consider, and thus the purpose of the index is only to optimize WHERE lookups. For example:

SELECT * FROM payment WHERE staff_id = 2 AND customer_id = 584;

Should you create an index on (staff_id, customer_id), or should you reverse the column order? We can run some quick queries to help examine the distribution of values in the table and determine which column has higher selectivity.

SELECT SUM(staff_id = 2), SUM(customer_id = 584) FROM payment

The Result:
SUM(staff_id = 2): 7992
SUM(customer_id = 584): 30

According to the rule of thumb, we should place customer_id first in the index, because the predicate matches fewer rows in the table (it has high selectivity).

If you don’t have specific samples to run, it might be better to use the rule of thumb, which is to look at the cardinality across the board, not just for one query:

SELECT COUNT(DISTINCT staff_id)/COUNT(*) AS staff_id_selectivity,
COUNT(DISTINCT customer_id)/COUNT(*) AS customer_id_selectivity,
COUNT(*) 
FROM payment

THe Result:
staff_id_selectivity: 0.0001
customer_id_selectivity: 0.0373
COUNT(*): 16049

customer_id has higher selectivity, so again the answer is to put that column first in the index.

You have to be careful not to assume that average-case performance is representative of special-case performance. Special cases can wreck performance for the whole application.

Although the rule of thumb about selectivity and cardinality is important, other factors–such as sorting, grouping, and the presence of range conditions the query’s WHERE clause–can make a much bigger difference to query performance.

Clustered Indexes

Clustered indexes aren’t separate type of index, but make adjacent key values together. The exact detail vary between implementations, but InnoDB’s clustered indexes actually store a B-Tree index. The term “clustered” refers to the fact that rows with adjacent key values are stored close to each other.

You can have only one clustered index per table, because you can’t store the rows in two places at once. Storage engines are responsible for implementing indexes, but not all storage engines support clustered indexes.

InnoDB clusters the data by the primary key. If you don’t define a primary key, InnoDB will try to use a unique nonnullable index instead. If there is no such index, InnoDB will define a hidden primary key for you and then cluster on that. InnoDB clusters records together only within a page.

A clustering primary key can help performance, but it can also cause serious performance problems. Thus, you should think carefully about clustering, especially when you change a table’s storage engine from InnoDB to something else.

Advantages of clustering indexes

• It keeps related data close together.
• Data access is fast.

Disadvantages of clustered indexes

• Insert speeds depend heavily on insertion order. Inserting rows in primary key order is the fastest way.
• Updating the clustered index columns is expensive, because it forces InnoDB to move each updated row to a new location.
• Secondary (nonclustered) indexes access require two index lookups instead of one. Because it stores the row’s primary key values rather than stores the pointer to the row’s physical location.

Covering Indexes

An index that contains (or covers) all the data needed to satisfy a query is called a covering index. In other words, a covering index is a multi-columns index that indexes on all columns needed for your queries. In MySQL, secondary indexes in your table default contain the primary key column values.

Benefits of covering indexes

• Index entries are usually much smaller than the full row size, so MySQL can access significantly less data if it reads only the index.
• Indexes are sorted by their index values, so I/O-bound range accesses will need to do less I/O compared to fetching each row from a random disk location.

A covering index can’t be any kind of index. The index must store the values from the columns it contains. Hash, spatial, and full-text indexes don’t store these values, so MySQL can use only B-Tree indexes to cover queries.

When you issue a query that is covered by an index, you will see “Using index” in the Extra column in EXPLAIN. For example, the inventory table has a multicolumn index on (store_id, film_id)

EXPLAIN SELECT store_iid, file_id FROM inventory;

Result:
...
Extra: Using index

Using Index Scans for Sorts

MySQL has two ways to produce ordered result: using a sort operation, or scanning an index in order. You can tell when MySQL plans to scan an index by looking for “index” in the type column in EXPLAIN.

Scanning the ordered index itself is fast, because it simply requires moving from one index entry to the next. However, if MySQL isn’t using the index to scanning, it will have to look up each row it finds in the index. Reading data in index order is usually much slower than a sequential table scan, especially for I/O-bound workloads.

MySQL can use the same index for both sorting and finding rows. It’s a good idea to design your indexes so that they’re useful for both tasks at once.

Ordering the result by the index works:

• only when the index’s order is exactly the same as the ORDER BY clause and all columns are sorted in the same direction (ascending or descending).
• If the query joins multiple tables, it works only when all columns in the ORDER BY clause refer to the first table.
• The ORDER BY clause also needs to from a leftmost prefix of the index.
• One case where the ORDER BY clause doesn’t have to specify a leftmost prefix of the index is if there are constants for the leading columns. If the WHERE clause or a JOIN clause specifies constants for these columns, they can “fill the gaps” in the index.

Packed (Prefix-Compressed) Indexes

Prefix compression reduce index size, allowing more of the index to fit in memory and dramatically improving performance in some cases.

Compressed blocks use less space, but they make some operations slower. For example, binary searches, ORDER BY.

The trade-off is one of CUP and memory resources versus disk resources. Packed indexes can be about one-tenth the size on disk, and if you have an I/O-bound workload they can more than offset the cost for some queries.

You can control how a table’s indexes are packed with the PACK_KEYS option to CREATE TABLE or ALTER TABLE. For example,

CREATE  TABLE `test_database`.`new_table` (
  `id` INT NOT NULL ,
  `address` VARCHAR(45) NULL ,
  PRIMARY KEY (`id`) ,
  INDEX `address` (`address` ASC) )
  PACK_KEYS = 1;

This option PACK_KEYS can have following three values: 1, 0, DEFAULT. Set this option to 1 to pack indexes of all kind of columns. Set it to 0 will disable all kind of indexes compression. Set it to DEFAULT will pack only CHAR, VARCHAR, BINARY, or VARBINARY type columns.

Conclusion of using packed indexes

• Packed indexes may give great space savings.
• PACK_KEYS applies to MyISAM tables only.
• Packed indexes can slow down your integer joins a lot.
• Packed indexes will make you read faster and updates will become slower.

Redundant and Duplicate Indexes

MySQL allows you to create multiple indexes on the same column; it does not notice and protect you from your mistake. MySQL has to maintain each duplicate index separately, and the query optimizer will consider each of them when it optimizes queries.

Duplicate indexes are indexes of the same type, created on the same set of columns in the same order. You should try to avoid creating them, and you should remove them if you find them.

Sometimes you can create duplicate indexes without knowing it. For example:

CREATE TABLE table_name(
    ID INT NOT NULL PRIMARY KEY,
    ...
    UINQUE(ID),
    INDEX(ID)
)

MySQL implements UNIQUE constraints and PRIMARY KEY constraints with indexes, so this example actually creates three indexes on the same column.

Redundant indexes are a bit different from duplicate indexes. If there is an index on (A, B), another index on (A) would be redundant because it is a prefix of the first index. The index on (A, B) can also be used as an index on (A) when they are B-Tree indexes.

Redundant indexes usually appear when people add indexes to a table. In most cases you don’t want redundant indexes, and to avoid them you should extend existing indexes rather than add new ones. Still, there are times when you will need redundant indexes for performance reasons. Extending an existing index might make it much larger and reduce performance for some queries.

The drawback of having two indexes is the maintenance cost. Inserting new rows into the table with more indexes is slower. Adding new indexes might have a performance impact for INSERT, UPDATE, DELETE operations, especially if a new index causes you to hit memory limits.

The solution for redundant and duplicate indexes is simply to drop them, but first you need to identify them. You can write various complicated queries against the INFORMATION_SCHEMA tables. You can also use tools to analyze them, such as common_schema, and pt-duplicate-keychecker tool.

Be careful when determining which indexes are candidates for dropping or extending. It’s good to validate your planned changes carefully with a tool such as pt-upgrade from Percona Toolkit.

Unused Indexes

In addition to duplicate and redundant indexes, you might have some indexes that the server simply doesn’t use. You should consider dropping them. There are two tools that can help you identify unused indexes. The easiest and most accurate is the INFORMATION_SCHEMA.INDEX_STATISTICS table in Percona Server and MariaDB. Alternatively, you can use the pt-index-usage tool included in Percona Toolkit.

Indexes and Locking

Indexes permit queries to lock fewer rows. If you queries never touch rows they don’t need, they’ll lock fewer rows, and that’s better for performance.

InnoDB locks rows only when it accesses them, and an index can reduce the number of rows InnoDB accesses and therefore locks. However, this works only if InnoDB can filter out the undesired rows at the storage engine level. For example,

SET AUTOCOMMIT=0;
BEGIN;
SELECT actor_id FROM actor WHERE actor_id < 5 
    AND actor_id <> 1 FOR UPDATE;

Result:
+----------+
| actor_id |
+----------+
|        2 |
|        3 |
|        4 |
+----------+

This query returns only rows 2 through 4, but it actually gets exclusive locks on rows 1 through 4. InnoDB locked row 1 because the plan MySQL chose for this query was an index range access:

EXPLAIN SELECT actor_id FROM actor WHERE actor_id < 5 
    AND actor_id <> 1 FOR UPDATE;

Result:
+----+-------------+-------+-------+---------+--------------------------+
| id | select_type | table | type  | key     | Extra                    |
+----+-------------+-------+-------+---------+--------------------------+
| 1  | SIMPLE      | actor | range | PRIMARY | Using where; Using index |
+----+-------------+-------+-------+---------+--------------------------+

In other words, the low-level storage engine operation was “begin at the start of the index and fetch all rows until actor_id < 5 is false”. The server didn’t tell InnoDB about the WHERE condition that eliminated row 1. Note the presence of “Using where” in the Extra column in EXPLAIN. This indicates that MySQL server is applying a WHERE filter after the storage engine returns the rows.

Index and Table Maintenance

Once you have created tables with proper data types and added indexes, you work isn’t over: you still need to maintain your tables and indexes to make sure they perform well. The three main goals of table maintenance are: finding and fixing corruption, maintaining accurate index statistics, and reducing fragmentation.

Finding and Repairing Table Corruption

The worst thing is table corruption. This often happens due to crashes. However, all storage engines can experience index corruption due to hardware problems or internal bugs in MySQL or the operating system.

Corrupted indexes can cause queries to return incorrect results, raise duplicate-key errors when there is no duplicate value, or even cause lockups and crashes. If you experience odd behavior you can run CHECK TABLE to see if the table is corrupt. CHECK TABLE usually catches most table and index errors. (Note that some storage engines don’t support this command.)

You can fix corrupt tables with the REPAIR TABLE command, but not all storage engines support this.

Alternatively, you can either use an offline engine-specific repair utility, such as myisamchk, or dump the data and reload it.

If you experience data corruption, the most important thing to do is try to determine why it’s occurring; don’t simply repair the data, or the corruption could return.

Updating Index Statistics

The MySQL query optimizer uses two API calls to ask the storage engines how index values are distributed when deciding how to use indexes. The first is the records_in_range() call, which accepts range end points and returns the number of records in that range.

The second API call is info(), which can return various types of data, including index cardinality (approximately how many records there are for each key value).

If the statistics were never generated, or if they are out of date, the optimizer can make bad decisions. The solution is to run ANALYZE TABLE, which regenerates the statistics.

Each storage engine implements index statistics differently, so the frequency with which you’ll need to run ANALYZE TABLE differs, as does the cost of running the statement:

• The memory storage engine does not store index statistics at all.
• MyISAM stores statistics on disk, and ANALYZE TABLE performs a full index scan to compute cardinality. The entire table is locked during this process.
• InnoDB does not store statistics on disk as of MySQL 5.5, but rather estimates them with random index dives and stores them in memory.

You can examine the cardinality of your indexes with the SHOW INDEX FROM command.

InnoDB calculates statistics for indexes when tables are first opened, when you run ANALYZE TABLE, and when the table’s size changes significantly.

For even more query plan stability, and for faster system warmups, you can use a system table to store index statistics so they are stable across server restarts and don’t need to be recomputed when InnoDB opens the table for the first time after booting up. Index statistics persistence in MySQL 5.6 controlled by the innodb_analyze_is_persistent option.

If you configure your server not to update index statistics automatically, you need to do it manually with periodic ANALYZE TABLE commands, unless you know that the statistics won’t change in ways.

Reducing Index and Data Fragmentation

B-Tree indexes can become fragmented, which might reduce performance. Fragmented indexes can be poorly filled and non-sequential on disk.

The table’s data storage can also become fragmented. However, data storage fragmentation is more complex than index fragmentation. There are three types of data fragmentation:

• Row fragmentation
• Intra-row fragmentation
• Free space fragmentation

MyISAM tables might suffer from all types of fragmentation, but InnoDB never fragments short rows; it moves them and rewrites them in a single piece.

To defragment data, you can either run OPTIMIZE TABLE or dump and reload data. These approaches work for most storage engines. For storage engines that don’t support OPTIMIZE TABLE, you can rebuild the table with a no-op ALTER TABLE. Just alter the table to have the same engine it currently uses:

ALTER TABLE <table> ENGINE=<engine>;

Don’t assume that you need to defragment your index and tables–measure them first to find out. Percona XtraBackup has a –stats option that can help for to measure fragmentation .

Conclusion

Indexing is a very complex topic. There are no fixed rules to guide how to indexing. It depends on many factors, such as what are your data structures, how did you use the data in your application, what results are you want, how did storage engines implement the index, properties of each type of index.

If you want to improve a slow query, you can profiling the query that lets you see which subtask costs the most time, or using the EXPLAIN command. Whatever you use what ways to analyze, but you always need to find the reasons for the cause slow to query. There are some methods that may be helpful to improve a query, such as update the table’s schema, add or extend indexes, and rewrite the query statement. Remember that indexing is part of improving a query. Note that Indexes are good for queries, but too many indexes may slow to write operations.

There are some basic principles to choose indexes:

• General using of index is the B-Tree index, and the other types of indexes are rather more suitable for special purposes.
• Reads data from index files are faster than reads from physical data files.
• Single-row access is slow. You better to read in a block that contains lots of rows you need.
• Accessing ranges of rows in order is fast. First, sequential I/O doesn’t require disk seek, so it is faster than random I/O. Secondly, it doesn’t need to perform any follow-up work to sort it.
• Index-only access is fast. If an index contains all the columns that the query needs, the storage engine don’t need to find the other columns by looking up rows in the table. This avoids lots of single-row access.

General process for choosing indexes:

1. Choosing a type of index
2. Determining what properties of the index to use.
   • prefix indexes and compressed indexes
   • multicolumn indexes (like B-Tree index, hash index) and covering indexes (like B-Tree index), also consider indexes columns order)
3. Avoid to add redundant and duplicate indexes, and remove unused indexes.

It’s very important to be able to reason through how indexes work, and to choose them based on that understanding, not on rules of thumb or heuristics such as “place the most selective columns first in multicolumn indexes” or “you should index all of the columns that appear in the WHERE clause”.

If you find a query that doesn’t benefit from all of these possible advantages of indexes, see if a better index can be created to improve performance. If not, perhaps a rewrite can transform the query so that it can use an index.

Appendixes

I. Indexes contrast Table

References

[1] High Performance MySQL by Baron Schwartz, Vadim Tkachenko, Peter Zaitsev, Derek J. Balling

[2] Speed up your queries using the covering index in MySQL

This post is talking about MySQL schema optimization, if you are familiar with this topic, you can go to the conclusion part that’s a good summary of the schema optimization of MySQL that may give you some enlightenment.

Good logical and physical design is the cornerstone of high performance, and you must design your schema for the specific queries you will run. This often involves trade-offs. For example, a denormalized schema can speed up some types of queries but slow down others. Adding counter and summary tables is a great way to optimize queries, but they can be expensive to maintain.

Choosing Optimal Data Types

General principles for choosing better data types

• Smaller is usually better. Try to use the smallest data type that can correctly store and represent your data. Smaller data types are usually faster, because they use less space on disk, in memory, and in the CPU cache. They also generally require fewer CPU cycles to process.
• Simple is good. Fewer CPU cycles are typically required to process operations on simpler data types. For example, integers are cheaper to compare than characters. because character sets and collations (sorting rules) make character comparisons complicated.
• Avoid NULL if possible. It’s usually best to specify columns as NOT NULL unless you intend to store NULL in them. It’s harder for MySQL to optimize queries that refer to nullable columns, because they make indexes, index statistics, and value comparisons more complicated.

Steps to choosing better data types

1. Determining what general class of types is appropriate: numeric, string, temporal, and so on.
2. Choosing the specific type. Many of MySQL’s data types can store the same kind of data but vary in the range of values they can store, the precision they permit, or the physical space (on disk and in memory) they require. Some data types also have special behaviors or properties. For example, DATETIME and TIMESTAMP can store the same kind of data: date and time, to a precision of one second. However, TIMESTAMP use only half as much storage space, and have time zone autoupdating capabilities.

MySQL supports many aliases for compatibility, such as INTEGER, BOOL, and NUMERIC. These are only aliases, don’t affect performance. You can use SHOW CREATE TABLE to see base types rather than aliases you used.

Numbers

There are two kinds of numbers: whole numbers and real numbers (numbers with a fractional part).

Whole Numbers

Integer types: TINYINT, SMALLINT, MEDIUMINT, INT, and BIGINT. These require 8, 16, 24, 32 and 64 bits of storage space, respectively. They can store values from -2^(N-1) to 2^(n-1)-1, where N is the number of bits of storage space they use.

Integer types can optionally have the UNSIGNED attribute, which disallows negative values and approximately doubles the upper limit of positive values. For example, a TINYINT UNSIGNED can store values ranging from 0 to 255 instead of from -128 to 127.

Your choice determines how MySQL stores the data, in memory and on disk. However, integer computations generally use 64-bit BIGINT integers, even on 32-bit architectures. (The exceptions are some aggregate functions, which use DECIMAL or DOUBLE to perform computations.)

MySQL lets you specify a width for integer types, such as INT(11). This meaningless for most applications: it does not restrict the legal range of values, but simply specifies the number of characters MySQL’s interactive tools (such as the command-line client).

Real Numbers

Real numbers are numbers that have a fractional part. However, they aren’t just for fractional numbers. You can also use DECIMAL to store integers that are so large they don’t fit in BIGINT.

The FLOAT and DOUBLE types support approximate calculations with standard floating point math. The DECIMAL type is for storing exact fractional numbers. it supports exact math.

Floating-point math is significantly faster than decimal math, because the CPU performs the computations natively.

Both floating-point and DECIMAL types let you specify a precision. For a DECIMAL column, you can specify the maximum allowed digits and the decimal point. For example, DECIMAL(5, 2) be able to store any value with five digits and two decimals, so it can store values from -999.99 to 999.99.

MySQL use DOUBLE for its internal calculations on floating-point types.

Note: Because of the additional space requirements and computational cost, you should use DECIMAL only when you need exact results for fractional numbers, for example, when storing financial data. You can also use BIGINT to store financial data, avoiding both the imprecision of floating-point storage and the cost of the precise DECIMAL math.

String Types

VARCHAR and CHAR types

The two major string types are VARCHAR and CHAR, which store character values.

VARCHAR stores variable-length character strings and is the most common string data type. It can require less storage space than fixed-length types, because it uses only as much space as it needs.

CHAR is fixed-length. Values are padded with spaces as needed for comparisons. CHAR is useful if you want to store very short string, or if all the values are nearly the same length. For example, CHAR is a good choice for MD5 values for user passwords. CHAR is also better than VARCHAR for data that’s changed frequently, because a fixed-length row is not prone to fragmentation. For very short columns, CHAR is also more efficient than VARCHAR, because VARCHAR needs an extra length byte.

BLOB and TEXT types

BLOB and TEXT are string data types designed to store large amounts of data as either binary or character strings, respectively.

Unlike with all other data types, MySQL handles each BLOB and TEXT value as an object with its own identity. Storage engines often store them specially. InnoDB may use a separate external storage area for them when they’re large.

The only difference between the BLOB and TEXT families is that BLOB types store binary data with no collation or character set, but TEXT types store string data and that have a character set and collation (for sort).

MySQL sorts BLOB and TEXT columns differently from other types: it sorts only the first max_sort_length bytes of such columns. if you need to sort by only the first few characters, you can either decrease the max_sort_length or use ORDER BY SUBSTRING(column, length).

MySQL can’t index the full length of these data types and can’t use the indexes for sorting.

Using ENUM instead of a string type

Sometimes you can use an ENUM column instead of conventional string types. An ENUM column can store a predefined set of distinct string values. MySQL stores them very compactly. It stores each value internally as an integer representing its position in the field definition list.

ENUM values sort by the internal integer values, not by the strings themselves. You can also use FIELD() to specify a sort order explicitly in your queries, but this prevents MySQL from using the index for sorting.

The biggest disadvantage of ENUM is that the list of strings is fixed, and adding or removing strings requires the use of ALTER TABLE. It might not be a good idea to use ENUM as a string data type when the list of allowed string values is likely to change arbitrarily in the future, unless it’s acceptable to add them at the end of the list, which can be done without a full rebuild of the table.

Another disadvantage of ENUM values as integers and have to do a lookup to convert it to its string representation, that have some overhead. In particular, it can be slower to join a CHAR or VARCHAR column to an ENUM column than to another CHAR or VARCHAR column.

Date and Time Types

MySQL has many types for various kinds of date and time values, such as YEAR and DATE. The finest granularity of time MySQL can store is one second. However, it can do temporal computations with microsecond granularity.

Most of date and time types have no alternatives, so there is no question of which one is the best choice. The only question is what to do when you need to store both date and time. MySQL offers two very similar data types for this purpose: DATETIME and TIMESTAMP. For many applications, either will work, but in some cases, one works better than the other.

DATETIME

DATETIME can stores values from the year 1001 to the year 9999, with a precision of one second. It stores the date and time packed into an integer in YYYYMMDDHHMMSS format, independent of time zone. This uses eight bytes of storage space.

It is not recommended to use a numeric column type (INT) to store datetime information. MySQL (and other systems too) provides many functions to handle datetime information. These functions are faster and more optimized than custom functions or calculations

TIMESTAMP

TIMESTAMP can stores the number of seconds elapsed since midnight, January 1, 1970, Greenwich Mean Time (GMT)–the same as a Unix timestamp. TIMESTAMP uses only four bytes of storage, so it has a much smaller range than DATETIME: from the year 1970 to the year 2038. MySQL provides the FROM_UNIXTIME() and UNIX_TIMESTAMP() functions to convert a Unix timestamp to a date, and vice versa.

The value a TIMESTAMP displays also depends on the time zone. The MySQL server, operating system, and client connections all have time zone settings.

TIMESTAMP also has special properties that DATETIME doesn’t have. TIMESTAMP columns are NOT NULL by default, which is difference from every other data type.

In general you should use TIMESTAMP to store date and time, because it is more space-efficient than DATETIME.

Subsecond

If you need to store a date and time value with subsecond. MySQL concurrently does not have an appropriate data type for this, but you can use your own storage format: you can use BIGINT data type and store the value as a timestamp in microseconds, or you can use a DOUBLE and store the fractional part of the second after the decimal point. Or you can use MariaDB instead of MySQL.

Bit-Packed Data Types

MySQL has a few data types that use individual bits within a value to store data compactly.

BIT

You can use a BIT column to store one or many true/false values in single column. BIT(1) defines a defines a field that contains a single bit, BIT(2) store 2 bits, and so on. The maximum length of a BIT column is 64 bits. For example, BIT(2) can store integer value 0~3, that represent two bits binary value 00, 01, 10, 11, respectively.

MySQL treats BIT as a string type, not a numeric type. When you retrieve a BIT(1) value, the result is a string but the contents are the binary value 0 or 1, not the ASCII value “0” or “1”.

This data type very confused, so you should use BIT with caution. For most applications, it is a better idea to avoid this type. If you want to store a true/false value in a single bit of storage space, another option is to create a nullable CHAR(0) column. This column is capable of storing either the absence of a value (NULL) or a zero-length value (the empty string).

Data Types Choice for Specific Usage

Choosing Identifiers

Choosing a good data type for an identifier column is very important. You are more likely to compare these columns to other values (for example, in joins) and to use them for lookups than other columns.

When choosing a type for an identifier column, you need to consider not only the storage type, but also how MySQL performs computations and comparisons on that type. For example, MySQL stores ENUM and SET types internally as integers but converts them to strings when doing comparisons in a string context.

You should use the same data types for identifier column in related tables. The types should match exactly, including properties such as UNSIGNED.

Choose the smallest size that can hold your required range of values.

Integer types are usually the best choice for identifiers, because they are fast and they work with AUTO_INCREMENT.

ENUM and SET types are generally a poor choice for identifiers.

String types. Avoid string types for identifiers if possible, because they take up a lot of space and are generally slower than integer types.

You should also be very careful with completely random strings, such as those produced by MD5(), SHA1(), or UUID(). Each new value you generate with them will be distributed in arbitrary ways over a large space, which can slow INSERT because of random location in indexes and some types of SELET queries because of logically adjacent rows will be widely dispersed on disk and in memory.

If you do store UUID values, you should remove the dashes or, even better, convert the UUID values to 16-byte numbers with UNHEX() and store them in a binary(16) column. You can retrieve the values in hexadecimal format with the HEX() function. Values generated by UUID() have different characteristics from those generated by a cryptographic hash function such as SHA1() : the UUID values are unevenly distributed and are somewhat sequential. They’re still not as good as a monotonically increasing integer.

Insertion operations

• Autoincrement integer: O(1)
• UUID: O(log n)

Query n rows by insertion order

• Autoincrement integer: O(1 * log n)
• UUID: O(n * log n)

Example of UUID store to and query by binary(16):

insert into sometable (your_id) values (UNHEX(REPLACE("3f06af63-a93c-11e4-9797-00505690773f", "-", "")))

select * from sometable where your_id = UNHEX("3f06af63a93c11e4979700505690773f");

IPv4 Address

You should use INT UNSIGNED data type ((unsigned 32-bit integers) ) to store IP address. MySQL provides the INET_ATON() and INET_NTOA() functions to convert between the two representations.

INSERT INTO yourtable (ip_addr) values (INET_ATON('94.120.175.182'));

SELECT INET_NTOA(ip_addr) from yourtable;

Schema Design Pitfalls in MySQL

There are also issues that arise from how MySQL is implemented, and that means you can make MySQL-specific mistakes, too. We need to avoid those mistakes and choose alternatives that work better with MySQL’s specific implementation.

Too many columns

MySQL’s storage engine API works by copying rows between the server and the storage engine in a row buffer format. The server then decodes the buffer into columns. But it can be costly to turn the row buffer into the row data structure with the decoded columns. If you are planning for hundreds of columns, be aware that the server’s performance characteristics will be a bit different.

Too many joins

Too many joins will be problematic in MySQL, because the cost of planning and optimizing the query is very expensive. MySQL has a limitation of 61 tables per join, and entity-attribute-value database require many self-joins. As a rough rule of thumb, it’s better to have a dozen or fewer tables per query if you need queries to execute very fast with high concurrency.

The all-powerful ENUM

Beware of overusing ENUM. For example,

CREATE TABLE ... (
	country enum('', '1', '2',..., '31')

This would be a questionable design decision in any database with an enumerated value type, because it really should be an integer that is foreign-keyed to a “dictionary” or “lookup” table anyway. Before MySQL 5.1 you can’t add a new country to the list without an ALTER TABLE, which is a blocking operation, and even in 5.1 and newer if you add the value anywhere but at the end of the list.

The ENUM in disguise

An ENUM permits the column to hold one value from a set of defined values. A SET permits the column to hold one or more values from a set of defined values. Sometimes these can be easy to confuse. For example,

CREATE TABLE ...(
	is_default set('Y', 'N') NOT NULL default 'N'

That almost surely ought to be an ENUM instead of a SET, assuming that it can’t be both true and false at the same time.

NULL not invented here

There are some benefit of avoiding NULL, and indeed you can consider alternatives when possible. Even when you do need to store a “no value” fact in a table, you might not need to use NULL. Perhaps you can use zero, a special value, or an empty string instead.

To store a not null value is better performance, but sometimes it will confuse its meaning, complicate your code, and introduce bugs. Therefore you can take this to extremes. Don’t be too afraid of using NULL when you need to represent an unknown value. In some cases, it’s better to use NULL than a magical constant. Handling NULL isn’t always easy, but it’s often better than alternative, for example

CREATE TABLE ...(
	dt DATETIME NOT NULL DEFAULT '0000-00-00 00:00:00'

That bogus all-zeros value can cause lots of problems.

Normalization and Denormalization

There are usually many ways to represent any given data, ranging from fully normalized to fully denormalized and anything in between. In a normalized database, each fact is represented once and only once. Conversely, in a denormalized database, information is duplicated, or stored in multiple places.

Storing duplicate data may cause inconsistency of data and need more storage space. Normalization is a way to avoid this problems.

Pros and Cons of a Normalized Schema

Advantages

• Normalized updates are usually faster than denormalized updates.
• Normalization makes your tables have little or no duplicated data, so there’s less data to change.
• Normalized tables are usually smaller, so they fit better in memory and perform better.
• The lack of redundant data means there’s less need for DISTINCT or GROUP BY queries when retrieving lists of values.

Disadvantages

• Any nontrivial query on a well-normalized schema will probably require at least one join, and perhaps several. This is not only expensive, but it can make some indexing strategies impossible.

Pros and Cons of a Denormalized Schema

A denormalized schema works well because everything is in the same table, which avoids joins.

Advantages

• Avoids joins. If you don’t need to join tables, the worst case for most queries, even the ones that don’t use indexes is a full table scan. This can be much faster than a join when the data doesn’t fit in memory, because it avoids random I/O.
• A single table can also allow more efficient indexing strategies.

A Mixture of Normalized and Denormalized

The truth is fully normalized and fully denormalized schemas are not fit the real world, you often need to mix the approaches, possibly using a partially normalized schema, cache tables, and other techniques.

Denomalization is more expensive to updates, because you have to change it in all tables. You must consider how frequently you’ll have to make such changes and how long they will take, compared to how often you’ll run the SELECT query.

Cache and Summary Tables

Sometimes the best way to improve performance is to keep redundant data in the same table as the data from which it was derived. However, sometimes you’ll need to build completely separate summary or cache tables, specially tuned for your retrieval needs. This approach works best if you can tolerate slightly stale data, but sometimes you really don’t have a choice. For instance, when you need to avoid complex and expensive real-time updates.

Cache tables mean tables that contain data that can be easily retrieved from the schema. Some column data of tables are logically redundant. Cache tables are useful for optimizing search and retrieval queries. For example, you might need many different index combinations to speed up various types of queries. These conflicting requirements sometimes demand that you create a cache table that contains only some of the columns from the main table.

Summary tables mean tables that hold aggregated data from GOURP BY queries. The data that is not logically redundant. They also use the term “roll-up table”. For example, it would be impossible to maintain an accurate real-time counter on a busy site. Instead, you could generate a summary table every hour. You can often do this with a single query, and it’s more efficient than maintaining counters in real time. The drawback is that the counts are not 100% accurate.

When using cache and summary tables, you have to decide whether to maintain their data in real time or with periodic rebuilds. Which is better will depend on your application, but a periodic rebuild not only can save resource but also can result in a more efficient table that’s not fragmented and has fully sorted indexes.

When you rebuild summary and cache tables, you’ll often need their data to remain available during the operation. You can achieve this by using a “shadow table”, which is a table you build behind the real table. When you’re done building it, you can swap the tables with an atomic rename. For example

DROP TABLE IF EXISTS my_summary_new, my_summary_old;
CREATE TABLE my_summary_new LIKE my_summary;
RENAME TABLE my_summary TO my_summary_old, my_summary_new TO my_summary;

Materialized Views

View are a logical virtual table created by “select query” but the result is not stored anywhere in the disk and every time we need to fire the query when we need data, so always we get updated or latest data from original tables.

Materialized views are also the logical view of our data-driven by the select query but the result of the query will get stored in the table or disk, also the definition of the query will also store in the database.

MySQL doesn’t support this natively. However, you can implement materialized view yourself, using Justin Swanhart’s open source Flexviews tools.

Counter Tables

An application that keeps counts in a table can run into concurrency problems when updating the counters. Such tables are very common in web applications. You can use them to cache the number friends a user has, the number of downloads of a file, and so on. It’s often a good idea to build a separate table for the counters, to keep it small and fast.

CREATE TABLE hit_counter (
	cnt int unsigned not null
) ENGINE=InnoDB;
UPDATE hit_counter SET cnt = cnt + 1;

CREATE TABLE hit_counter (
	slot tinyint unsigned not null primary key,
    cnt int unsigned not null
) ENGINE=InnoDB;
UPDATE hit_counter SET cnt = cnt + 1 WHERE slot = RAND() * 100;
SELECT SUM(cnt) FROM hit_counter;

Speeding Up Alter Table

MySQL’s ALTER TABLE performance can become a problem with very large tables. MySQL performs most alterations by making an empty table with the desired new structure, inserting all the data from the old table into the new one, and deleting the old table. This can take a very long time, especially if you’re short on memory and the table is large and has lots of indexes.

In general, most ALTER TABLE operations will cause interruption of service in MySQL. For the general case, you need to use either operational tricks such as swapping servers around and performing the ALTER on servers that are not in production service, or a shadow copy approach. Tools can help with to build a new table for a shadow copy. For example, the “online schema change” tools from Facebook’s database operations team, Shlomi Noach’s openark toolkit, and Percona Toolkit.

Not all ALTER TABLE operations cause table rebuilds. For example, change or drop a column’s default value in two ways (one fast, and one slow).

ALTER TABLE your_table
MODIFY COLUMN your_column TINYINT(3) NOT NULL DEFAULT 5;

The following code is a fast way to modify column’s default value. The default value for the column is actually stored in the table’s .frm file, so you should be able to change it without touching the table itself. Any MODIFY COLUMN will cause a table rebuild, but you can use ALTER COLUMN to change column’s default value.

ALTER TABLE your_table
ALTER COLUMN your_column SET DEFAULT 5;

Conclusion

The general principles for choosing a data type are introduced earlier in this article. They are “smaller is usually better”, “simple is good”, and “avoid NULL if possible”.

• Sometimes, the data type of a column doesn’t limit one kind of data type, so we can use the principle “simple is good” to determine what kind of data type we use.
• When we determine what kind of data type for the column, we can follow the principle of “smaller is usually better” to choose a specific data type. Then, we also can follow the principle “avoid NULL if possible” to determine does the column allows NULL.

The kinds of data types are whole numbers, real numbers, strings (text), binary, temporal (time), and others. For choosing a specific data type from a kind of data type, you can use the following methods.

• For choosing a data type of whole numbers. 1. First, you should choose the less length of integer type if possible. 2. If you don’t there are no negative numbers, you should set it to be unsigned (that makes values range larger). 3. For storing bool data, the better choice is BOOL(TINYINT) data type, others choices are BIT(1), CHAR(0). 4. There are many common usage scenarios of whole numbers. For example, table’s identifiers, counter numbers. For identifiers of tables, integers are the best choice for identifiers, and all tables’ identifiers should be the same integer type.
• For choosing a data type of real numbers. 1. If you need exact calculations you should choose the DECIMAL type. 2. If you can accept approximate calculations you can choose the FLOAT and DOUBLE data type by different precisions. 3. Note that you should use DECIMAL only when you need exact results for fractional numbers because it needs more cost than floating numbers. 4. There are many common usage scenarios of real numbers, for example, financial data. For financial data, the DECIMAL type is a better choice for representing financial data, but if the financial data have small limit precision you can convert all data to integer values and use BIGINTEGER to store them.
• For choosing a data type of temporal types. 1. Sometimes you can use integers to replace temporal types because integer types are simpler and faster than temporal types, but you will lose lots of very convenient built-in functions with temporal types, such as WEEK(), ADDDATE(). 2. In the choice of temporal types, the most common question is how to choose a data type that contains both date and time types from DATETIME and TIMESTAMP. The main differences between DATETIME and TIMESTAMP are representing range, space cost, and affect by time zone.
• For choosing a specific string type. 1. The most choice are VARCHAR and CHAR. When your column values limit by small length, you can use CHAR to store it, otherwise use VARCHAR. 2. When you need to store large amounts of characters, you can choose a text type from text family types according to your range of characters of text. 3. For binary data, the basic choices are BINARY and VARBINARY that same with CHAR and VARCHAR, but store binary. 4. When you want to store large amounts of binary, you can choose a binary type from blob family types. 5. There are some special data types in string types, such as ENUM, SET, and JSON. 6. There are many common usage scenarios of string types, for example, ID card No., account number, name, URI, and so on. 7. Note that sometimes you can use integers to replace strings it has much performance improvement, such as IPv4 address can use BIGINTEGER to represent.

Comparison and Sorting

• Same data types comparison is faster than different data types.
• Numeric data types comparison is faster than character data types.

Beware of Autogenerated Schemas

Autogenerate schemas can cause severe performance problems. Some programs use large VARCHAR fields for everything, or use difference data types for columns that will be compared in joins. Be sure to double-check a schema if it was created for you automatically.

Appendix

I. Basic Information of Data Types

Fractional Seconds Precision Storage (Since MySQL 5.6.4)

References

[1] High Performance MySQL by Baron Schwartz, Vadim Tkachenko, Peter Zaitsev, Derek J. Balling

[2] MySQL 5.7 Reference Manual

Introduction

Computer users want to do more than one thing at a time. A single application does more than one things at a time called concurrent software.

The Java platform is designed to support concurrent programming. Since Java SE 5, the Java platform has also included high-level concurrency APIs.

Processes and Threads

In concurrent programming, there are two basic units of execution: process and threads. In the Java programming language, concurrent programming is mostly concerned with threads.

A computer system has many active processes and threads. If in computer systems that only have a single execution core, there is one thread actually executing at any given moment. Processing time for a single core is shared among processes and threads through an OS feature called time slicing.

It’s becoming more and more common for computer systems to have multiple processors or processors with multiple execution cores.

Processes

A process has a self-contained execution environment. A process generally has a complete, private set of basic run-time resources, for example, memory space.

Processes are often seen as synonymous with programs or applications. Most implementations of Java Virtual machines run as a single process. A Java application can create additional processes using ProcessBuilder object.

Threads

Threads are sometimes called lightweight processes. Both processes and threads provide an execution environment, but creating a new thread requires fewer resources than creating a new process.

Threads exist within a process, and every process has at least one thread. Threads share the process’s resources, including memory and open files. This makes for efficient, but potentially problematic, communication.

Difference between processes and threads

Threads exist within a process, and every process has at least one thread. Both processes and threads are units of execution, and they have an execution environment.

A process is a minimal resource assignment unit, but a thread is a minimal execution unit.

A process has a self-contained execution environment. No resources are shared between processes. But threads have a private resource from a process, and multiple threads in the same process also can share the resource of their process.

The Advantages and Disadvantages of Threads

Advantages

• Improve the performance of applications.
• Asynchronous workflows.
• Exploiting multiple processors.
• More responsive user interfaces.

Disadvantages

• Safety.
• Liveness.
• Performance. Thread introduces additional performance costs, for example, context switches, and synchronization costs.

Properly using multi-thread is more beneficial than disadvantages.

Thread Objects

Each thread is associated with an instance of the class Thread. There are two basic strategies for using Thread objects to create a concurrent application.

• To directly control thread creation and management, simply instantiate Thread each time.
• To abstract thread management from the rest of your application, pass the application’s task to an executor.

Creating an instance of Thread must provide the code that will run in that thread. There are two ways to create a Thread instance:

• Provide a runnable object.
• Subclass Thread.

Using a class of implemented Runnable interface to create an instance of Thread is more general because of the Runnable object can subclass a class other than Thread.

Methods of Thread class:

• Constructors
  • Thread(), Thread(String name)
  • Thread(Runnable target), Thread(Runnable target, String name)
  • Thread(ThreadGroup group, Runnable target, String name), Thread(ThreadGroup group, Runnable target, String name, long stackSize)
  • Thread(ThreadGroup group, String name)
• Static Methods
  • static in activeCount()
  • static Thread currentThread()
  • static void dumpStack(), static Map<Thread, StackTraceElement[]> getAllStackTraces()
  • static int enumerate(Thread[] tarray)
  • static Thread.UncaughtExceptionHandler getDefaultUncaughtExceptionHandler()
  • static boolean holdsLock(Object obj)
  • static boolean interrupted()
  • static void yield()
• Get Thread Information
  • long getId()
  • String getName()
  • int getPriority()
  • ClassLoader getConctextClassLoader()
  • StackTraceElement[] getStackTrace()
  • Thread.State getState()
  • ThreadGroup getThreadGroup()
  • Thread.UncaughtExceptionHandler getUncaughtExceptionHandler()
• Check
  • void checkAccess()
  • boolean isAlive()
  • boolean isDaemon()
  • boolean isInterrupted()
• Operating thread
  • void interrupt()
  • void join(), void join(long millis), join(long millis, int nanos)
  • void run()
  • void setName(String name), void setPriority(int newPriority), void setContextClassLoader(ClassLoader c), void setDaemon(boolean on)
  • void sleep(long millis), sleep(long millis, int nanos)
  • void start()

Why are Thread.stop, Thread.suspend and Thread.resume Deprecated?

Interrupts

An interrupt is an indication to a thread that it should stop what it is doing and do something else. Thread.interrupt() sets the interrupted status/flag of the target thread. The code running in that target thread MAY poll the interrupted status and handle it appropriately. Some methods that block such as Object.wait() may consume the interrupted status immediately and throw an appropriate exception (usually InterruptedException). Thread interruption is a gentle way to stop a thread. It is used to give threads a chance to exit cleanly, as opposed by deprecated Thread.stop() that force to stop the thread.

Interruption in Java is not preemptive. Threads have to cooperate in order to process the interrupt properly. If the target thread does not poll the interrupted status the interrupt is effectively ignored. Polling occurs via the Thread.interrupted() method which returns the current thread’s interrupted status and clears that interrupt flag. Usually, the thread might then do something such as throw InterruptedException. If a thread goes a long time without invoking a method that throws InterruptedException Then it must periodically invoke Thread.interrupted(), which returns if an interrupt has been received. For example:

while (...){
    doSometing();
    if (Thread.interrupted()){
        // We've been interrupted
        System.out.println("Thread interrupted!");
        return; // or break loop
    }
}

if (Thread.interrupted()){
    throw new InterrupteException();
}

Some API methods have built-in interrupt handling

• Object.wait()
• Thread.sleep(), Thread.join()
• Most java.util.concurrent structures.
• Java NIO (it does not use InterruptedException, instead using ClosedByInterruptException).

Joins

The join method allows one thread to wait for the completion of another. Example of current thread wait for thread t to be complete:

t.join()

join is similar to sleep doesn’t release the locks it holds, it just suspends the current thread.

Difference Between Wait and Sleep

• wait is for concurrent programming but sleep not. Sleeping does not release the locks it holds while wait releases the lock on wait() is called.
• sleep just suspends a thread execution for a fixed time, but wait suspends a thread execution until notify is called.
• wait must happen in a block synchronized on the monitor object (otherwise occurs IllegalMonitorStateException ) whereas sleep does not.

Object lock = ...;
synchronized (lock) {
    lock.wait();
} 

• You can wait on object itself whereas you call sleep on Thread.

Synchronization

Threads communicate primarily by sharing access to fields and the objects reference fields refer to. This form of communication is extremely efficient, but makes two kinds of errors possible: thread interference and memory consistency errors. The tool needed to prevent these errors is synchronization.

However, synchronization can introduce threads deadlock and thread contention (starvation and livelock).

• Thread Interference: Errors are introduced when multiple threads access shared data.
• Memory Consistency Errors: Errors that result form inconsistent views of shared memory.
• Synchronized Methods: It can effectively prevent thread interference and memory consistency errors.
• Implicit Locks: synchronization is based on implicit locks.
• Atomic Access: operations that can’t be interfered with by other threads.

Thread Interference

class Counter {
    private int c = 0;
    public void increment(){
        c++;
    }
    public void decrement(){
        c--;
    }
    public int value(){
        return c;
    }
}

The increment() and decrement() are not atomic operations. Each method has three steps operations: retrieve variable, update value, store result in variable. When multiple threads invoke these methods, they interfere with each other, because the three steps of each thread are interleaving executed. So the result of each thread is unpredictable.

Memory Consistency Errors

Memory consistency errors occur when different threads have inconsistent views of what should be the same data. When other thread update value of a variable, your current thread still read old value of the variable.

The key to avoiding memory consistency errors is understanding the happens-before relationship. This relationship is simply a guarantee that memory writes by one specific statement is visible to another specific statement.

There are several actions that create happens-before relationships:

• Single thread rule: Each action in a single thread happens-before every action in that thread that comes later in the program order.
• Monitor lock rule (synchronization): An unlock on a monitor lock (exiting synchronized method/block) happens-before every subsequent acquiring on the same monitor lock.
• Volatile variable rule: A write to a volatile field happens-before every subsequent read of that same field.
• Thread start rule: A call to Thread.start() on a thread happens-before every action in the started thread.
• Thread join rule: All actions in a thread happen-before any other thread successfully returns from a join on that thread.
• Transitivity: If A happens-before B, and B happens-before C, then A happens-before C.

Synchronized Methods

The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements. synchronized make non-atomic operations become atomic operations and establish happens-before relationships between threads that access the same variables.

class SynchronizedCounter {
    private int c = 0;
    public synchronized void increment(){
        c++;
    }
    public synchronized void decrement(){
        c--;
    }
    public synchronized int value(){
        return c;
    }
}

Synchronized methods enable a simple strategy for preventing thread interference and memory errors. First, it is not possible for two invocations of synchronized methods on the same object to interleave. Second, when a synchronized method exists, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object.

Intrinsic Locks and Synchronization

Synchronization is built around an internal entity known as the intrinsic lock or monitor lock. (The API specification often refers to this entity simply as a “monitor.”) Intrinsic locks play a role in both aspects of synchronization: enforcing exclusive access to an object’s state and establishing happens-before relationships.

Every object has an intrinsic lock associated with it.

Locks in Synchronized Methods

When a thread invokes a synchronized method, it automatically acquires the intrinsic lock for that method’s object and release it when the method returns. The lock release occurs even if the return was caused by an uncaught exception.

A static synchronized method is associated with a class. A thread acquires the intrinsic lock for the Class object associated with the class.

Synchronized Statements

public void add(String name){
    synchronized(this){
        lastName = name;
        nameCount++;
    }
    nameList.add(name);
}

Invoking other objects’ methods from synchronized code can create liveness problems.

Synchronized statements are also useful for improving concurrency with fine-grained synchronization.

Reentrant Synchronization

Allowing a thread to acquire the same lock more than once enable reentrant synchronization.

Atomic Access

Common Atomic Actions

• Reads and writes are atomic for reference variables and for most of primitive variables (except long and double).
• Reads and writes are atomic for all variable declared volatile (including long and double variables)

Atomic actions cannot be interleaved, so they can be used without fear of thread interference. However, this does not eliminate all need to synchronize atomic actions, because memory consistency errors are still possible. Using volatile variables reduce the risk of memory consistency errors, because any write to a volatile variable establishes a happens-before relationship with subsequent reads of the same variable.

Using simple atomic variable access is more efficient than accessing these variables through synchronized code, but requires more care by the programmer to avoid memory consistency errors. Some of the classes in the java.util.concurrent package provide atomic methods that do not rely on synchronization.

Liveness

The most common kind of liveness problem is the deadlock, others are starvation and livelock.

Deadlock

Deadlock describes a situation where two or more threads are blocked forever, waiting for each other.

public class DeadlockExample{
    private static Object lock1 = new Object();
    private static Object lock2 = new Object();

    public static void main(String[] args) {
        new Thread(()->{
            synchronized (lock1){
                try {
                    // ensure both two threads acquired their first lock, 
                    // and waiting for acquired the second lock.
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (lock2){}
            }
        }).start();
        new Thread(()->{
            synchronized (lock2){
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (lock1){}
            }
        }).start();
    }
}

Starvation and Livelock

Starvation and livelock are much less common a problem than deadlock, but are still problems that every designer of concurrent software is likely to encounter.

Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress.

Livelock is a situation threads simply too busy responding to each other and unable to make further progress.

Guarded Blocks

Threads often have to coordinate their actions. The most common coordination idiom is the guarded block. Such a block begins by polling a condition that must be true before the block can proceed.

Guard by simply loop

public void guardedJoy(){
	while(!joy) {}
	System.out.println("Joy has been achived!");
}

Guard by invokes Object.wait. A more efficient guard.

public synchronized void guardedJoy(){
    while(!joy){
        try{
            wait();
        } catch (InterruptedException e){}
    }
    System.out.println("Joy efficiently has been achived!");
}

public synchronized notifyJoy() {
    joy = true;
    notifyAll();
}

Using guarded blocks can create a Producer-Consumer application.

Immutable Objects

An object is considered immutable if its state connot change after it is constructed.

Immutable objects are particularly useful in concurrent applications. Since they cannot change state, they cannot be corrupted by thread interference or observed in an inconsistent state.

Immutable objects using strategies

• Don’t provide “setter” methods. Methods that modify fields or objects referred to by fields.
• Make all fields final and private.
• Don’t allow subclass to override methods. The simplest way to do this is to declare the class as final. A more sophisticated approach is to make the constructor private and construct instances in factory methods in this class.
• If the instance fields include references to mutable objects, don’t allow those objects to be change. Don’t provide methods that modify the mutable objects. Don’t share references to the mutable objects.

High Level Concurrency Objects

These low-level APIs are adequate for very basic tasks, but higher-level building blocks are needed for more advanced tasks. This is especially useful for massively concurrent applications in multiprocessor and multi-core systems.

High Level Concurrency Features:

• Lock object support locking idioms that simplify many concurrent applications.
• Executors define a high-level API for launching and managing threads. Executor implementations provided by java.util.concurrent provide thread pool management suitable for large-scale applications.
• Concurrent collections make it easier to manage large collections of data, and can greatly reduce the need for synchronization.
• Atomic variables have features that minimize synchronization and help avoid memory consistency errors.
• ThreadLocalRandom provides efficient generation of pseudorandom numbers from multiple threads.

Lock Objects

Synchronized code relies on a simple kind of reentrant lock. This kind of lock is easy to use, but many limitations. More sophisticated locking idioms are supported by the java.util.concurrent.locks package.

Lock objects work very much like the implicit locks used by synchronized code. The biggest advantage of Lock objects over implicit locks is their ability to back out of an attempt to acquire a lock. The tryLock method backs out if the lock is not available immediately or before a timeout expires.

We can use Lock objects to solve the deadlock problem. First we use Lock.tryLock() method to acquire all locks we needed, if fail to acquire, then unlock all acquired locks, else we can acquire all locks and without deadlock problem.

Executors

In large-scale applications, it makes sense to separate thread management and creation from the rest of the application. Objects that encapsulate these functions are known as executors.

• Executor Interfaces: defines the three executor object types.
• Thread Pools: are the most common kind of executor implementation.
• Fork/Join: is a framework for taking advantage of multiple processors.
• Executors: is a utility class that has factory and utility methods for Executor, ExecutorService, ScheduledExecutorService, ThreadFactory, and Callable classes.

Hierarchy of Executor

(I)Executor
|----(I)ExecutorService
|--------(I)ScheduledExecutorService
|--------(A)AbstractExecutorService
|------------ForkJoinPool
|------------ThreadPoolExecutor
|----------------ScheduledThreadPoolExecutor
Executors

Executor Interfaces

The java.util.concurrent package defines three executor interfaces: Executor, ExecutorService, ScheduledExecutorService. Typically, variables that refer to executor objects are declared as one of these three interface types, not with an executor class type.

The Executor interface provides a single method execute() designed to be a replacement for a common thread-creation idiom.

new Thread(r).start();

executor.execute(r);

The ExecutorService interface provides methods execute and submit. Like execute, the submit method accepts Runnable objects, but also accepts Callable object, which allow the task to return a value. The submit method returns a Future object.

The ScheduledExecutorService interface supplements the methods of its parent ExecutorService with schedule, which executes a Runnable or Callable task after a specified delay. In addition, the interface defines scheduleAtFixedRate and scheduleWithFixedDelay, which executes specified tasks repeatedly, at defined intervals.

Thread Pools

Most of executor implementations use thread pools. One common type of thread pool is the fixed thread pool.

One common type of thread pool is the fixed thread pool. A simple way to create an executor that uses a fixed thread pool is to invoke the newFixedThreadPool factory method of java.util.concurrent.Executors. This class also provides the following factory methods:

• newCachedThreadPool
• new SingleThreadExecutor
• several factory methods returns ScheduledExecuteorService executors.

If none of the executors provided by the factory methods of Executors meet your needs, constructing instance of ThreadPoolExecutor or ScheduledThreadPoolExecutor will give you additional options.

To construct a ThreadPoolExecutor object, you least specify five arguments:

• ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit, BlockingQueue<Runnable> workQueue)

Fork/Join

The fork/join framework is an implementation of ExecutorService interface that helps you take advantage of multiple processors. It is designed for work that can be broken into smaller pieces recursively.

The fork/join framework is distinct because it uses a work-stealing algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy.

The center of the fork/join framework is the ForkJoinPool class, an extension of the AbstractExecutorService class. ForkJoinPool implements the core work-stealing algorithm and can execute ForkJoinTask processes.

You submit tasks to a ForkJoinPool similarly to how you submit tasks to an ExecutorService. You can submit two types of tasks. One is RecursiveAction that does not return any result. Another is RecursiveTask can return a result. They are a subclass of ForkJoinTask, and all of the tasks classes are abstract.

There are some generally useful features in JavaSE which are already implemented using the fork/join framework.

• Arrays class methods: parallelSort()
• java.util.stream package

fork/join framework pseudocode:

if (my portion of the work is small enough)
	do the work directly
else
	split my work into two pieces

Example of ForkJoinPool

public class Main {
    public static void main(String[] args) {
        ForkJoinPool forkJoinPool = new ForkJoinPool(5);
        forkJoinPool.invoke(new MyRecursiveAction(100));
    }
}

public class MyRecursiveAction extends RecursiveAction {
    private long workload = 0;
    private static final long THRESHOLD = 16;
    
    public MyRecursiveAction(long workload) {
        this.workload = workload;
    }

    @Override
    protected void compute() {
        if (this.workload <= THRESHOLD) {
            System.out.println("Doing workload myself : " + this.workload);
        } else {
            System.out.println("Splitting workload : " + this.workload);
            List<MyRecursiveAction> subtasks = new ArrayList<>();
            subtasks.addAll(createSubtasks());
            for (RecursiveAction subtask : subtasks) {
                subtask.fork();
            }
        }
    }

    private List<MyRecursiveAction> createSubtasks() {
        List<MyRecursiveAction> subtasks = new ArrayList<>();
        MyRecursiveAction subtask1 = new MyRecursiveAction(this.workload / 2);
        MyRecursiveAction subtask2 = new MyRecursiveAction(this.workload / 2);
        subtasks.add(subtask1);
        subtasks.add(subtask2);
        return subtasks;
    }
}

Concurrent Collections

Concurrent collections are high concurrency and thread-safe collection implementation. For example, CopyOnWriteArrayList, ConcurrentHashMap.

Atomic Variables

The java.util.concurrent.atomic package defines classes that support atomic operations on single variable. All classes have get and set methods that work like reads and writes on volatile variables. A set has a happens-before relationship with any subsequent get on the same variable. The atomic compareAndSet method also has these memory consistency feature, as do the simple atomic arithmetic methods that apply to integer atomic variables.

Example of Basic Usage of AtomicInteger

AtomicInteger atomicInteger = new AtomicInteger(0);
atomicInteger.accumulateAndGet(10, (x, y)->{return x + y;});
System.out.println(atomicInteger.get());

Example of Using Atomic Variable instead of Synchronized Methods

public class AtomicCounter {
    private AtomicInteger c = new AtomicInteger(0);

    public void increment() {
        c.incrementAndGet();
    }

    public void decrement() {
        c.decrementAndGet();
    }

    public int value() {
        return c.get();
    }
}

Concurrent Random Numbers

The package java.util.concurrent includes a convenience class, ThreadLocalRandom, for applications that expect to use random numbers from multiple threads or ForkJoinTasks.

For concurrent access, using ThreadLocalRandom instead of Math.random() results in less contention and better performance.

Example of ThreadLocalRandom

int r = ThreadLocalRandom.current().nextInt(1, 10);

Conclusion

In multi-threads programming, allows multiple threads simultaneously access shared resources that may cause unpredicted results or corrupted values. For thread-safe, we need to consider two factors: thread interference and memory consistency errors.

Thread interference can be solved by atomic access (common using exclusive locks). Memory consistency errors can be solved by establishing a happens-before relationship (that between reads and writes the same variable).

We can simply use synchronized to solve the two thread-safe problems. But for high concurrency and thread-safe, we should use as few locks as possible, even have no locks. So we consider using a combination of explicit locks (reentrant locks), immutable objects, volatile variables, and atomic variables to solve the two thread-safe problems.

Locks may cause liveness problems: deadlock, starvation, and livelock. we can follow some coding principles to avoid these problems happens.

Guarded blocks common use for in threads cooperation. The most common example is the Producer-Consumer application.

Executors are for efficient thread creation and management.

Concurrent collections are high concurrency and thread-safe collection implementation.

References

[1] The Java Tutorial: A Short Course on the Basics

[2] Difference between wait() and sleep()

[3] What does java.lang.Thread.interrupt() do?

[4] Java - Understanding Happens-before relationship

[5] Memory Consistency - happens-before relationship in Java