From: Claudio Nanni Date: May 9 2012 3:34pm Subject: =?GB2312?Q?Re=3A_=BB=D8=B8=B4=A3=BA_Why_is_creating_indexes_faster_after_i?= =?GB2312?Q?nserting_massive_data_rows=3F?= List-Archive: http://lists.mysql.com/mysql/227374 Message-Id: MIME-Version: 1.0 Content-Type: multipart/alternative; boundary=f46d0408d3bf2c9fb704bf9c3d61 --f46d0408d3bf2c9fb704bf9c3d61 Content-Type: text/plain; charset=GB2312 Content-Transfer-Encoding: quoted-printable This thread is going on and on and on and on, does anyone have time to actually measure I/O? Let's make numbers talk. Claudio 2012/5/9 Rick James > A BTree that is small enough to be cached in RAM can be quickly > maintained. Even the =A1=B0block splits=A1=B1 are not too costly without= the I/O. > > A big file that needs sorting =A8C bigger than can be cached in RAM =A8C = is more > efficiently done with a dedicated =A1=B0sort merge=A1=B1 program. A =A1= =B0big=A1=B1 INDEX on a > table may be big enough to fall into this category. > > I/O is the most costly part of any of these operations. My rule of thumb > for MySQL SQL statements is: If everything is cached, the query will run > ten times as fast as it would if things have to be fetched from disk. > > Sortmerge works this way: > > 1. Sort as much of the file as you can in RAM. Write that sorted > piece to disk. > > 2. Repeat for the next chunk of the file. Repeat until the input > file is broken into sorted chunks. > > 3. Now, =A1=B0merge=A1=B1 those chunks together =A8C take the first= row from > each, decide which is the =A1=B0smallest=A1=B1, send it to the output > > 4. Repeat until finished with all the pieces. > For a really big task, there may have to be more than on =A1=B0merge=A1= =B1 pass. > Note how sort merge reads the input sequentially once, writes the output > sequentially once, and has sequential I/O for each merge chunk. > =A1=B0Sequential=A1=B1 I/O is faster than =A1=B0random=A1=B1 I/O =A8C no = arm motion on > traditional disks. (SSDs are a different matter; I won=A1=AFt go into th= at.) > > The =A1=B0output=A1=B1 from the sortmerge is fed into code that builds th= e BTree for > the table. This building of the BTree is sequential =A8C fill the first > block, move on to the next block, and never have to go back. > > BTrees (when built randomly), if they need to spill to disk, will involve > random I/O. (And we are talking about an INDEX that is so big that it > needs to spill to disk.) > > When a block =A1=B0splits=A1=B1, one full block becomes two half-full blo= cks. > Randomly filling a BTree leads to, on average, the index being 69% full. > This is not a big factor in the overall issue, but perhaps worth noting. > > How bad can it get? Here=A1=AFs an example. > > =A1=A4 You have an INDEX on some random value, such as a GUID or = MD5. > > =A1=A4 The INDEX will be 5 times as big as you can fit in RAM. > > =A1=A4 MySQL is adding to the BTree one row at a time (the > non-sortmerge way) > When it is nearly finished, only 1 of 5 updates to the BTree can be done > immediately in RAM; 4 out of 5 updates to the BTree will have to hit disk= . > If you are using normal disks, that is on the order of 125 rows per seco= nd > that you can insert =A8C Terrible! Sortmerge is likely to average over 1= 0,000. > > > > From: Zhangzhigang [mailto:zzgang_2008@stripped] > Sent: Tuesday, May 08, 2012 9:13 PM > To: Rick James > Cc: mysql@stripped > Subject: =BB=D8=B8=B4=A3=BA Why is creating indexes faster after insertin= g massive data > rows? > > James... > >* By doing all the indexes after building the table (or at least all the > non-UNIQUE indexes), "sort merge" can be used. This technique had been > highly optimized over the past half-century, and is more efficient. > > I have a question about "sort merge": > > Why does it do the all "sort merge"? > > In my opinion, it just maintains the B tree and inserts one key into a B > tree node which has fewer sorted keys, so it is good performance. > > If it only does the "sort merge", the B tree data structure have to been > created separately. it wastes some performance. > > Does it? > > > ________________________________ > =B7=A2=BC=FE=C8=CB=A3=BA Rick James > > =CA=D5=BC=FE=C8=CB=A3=BA Johan De Meersman >; > Zhangzhigang > > =B3=AD=CB=CD=A3=BA "mysql@stripped" = < > mysql@stripped> > =B7=A2=CB=CD=C8=D5=C6=DA=A3=BA 2012=C4=EA5=D4=C28=C8=D5, =D0=C7=C6=DA=B6= =FE, =C9=CF=CE=E7 12:35 > =D6=F7=CC=E2: RE: Why is creating indexes faster after inserting massive = data rows? > > * Batch INSERTs run faster than one-row-at-a-time, but this is unrelated > to INDEX updating speed. > * The cache size is quite important to dealing with indexing during > INSERT; see http://mysql.rjweb.org/doc.php/memory < > http://mysql.rjweb.org/doc.php/memory%0A> > * Note that mysqldump sets up for an efficient creation of indexes after > loading the data. This is not practical (or necessarily efficient) when > incremental INSERTing into a table. > > As for the original question... > * Updating the index(es) for one row often involves random BTree > traversals. When the index(es) are too big to be cached, this can involv= e > disk hit(s) for each row inserted. > * By doing all the indexes after building the table (or at least all the > non-UNIQUE indexes), "sort merge" can be used. This technique had been > highly optimized over the past half-century, and is more efficient. > > > > -----Original Message----- > > From: Johan De Meersman [mailto:vegivamp@stripped vegivamp@stripped>] > > Sent: Monday, May 07, 2012 1:29 AM > > To: Zhangzhigang > > Cc: mysql@stripped > > Subject: Re: Why is creating indexes faster after inserting massive > > data rows? > > > > ----- Original Message ----- > > > From: "Zhangzhigang" zzgang_2008@stripped>> > > > > > > Creating indexes after inserting massive data rows is faster than > > > before inserting data rows. > > > Please tell me why. > > > > Plain and simple: the indices get updated after every insert statement, > > whereas if you only create the index *after* the inserts, the index > > gets created in a single operation, which is a lot more efficient. > > > > I seem to recall that inside of a transaction (thus, InnoDB or so) the > > difference is markedly less; I might be wrong, though. > > > > > > -- > > Bier met grenadyn > > Is als mosterd by den wyn > > Sy die't drinkt, is eene kwezel > > Hy die't drinkt, is ras een ezel > > > > -- > > MySQL General Mailing List > > For list archives: http://lists.mysql.com/mysql < > http://lists.mysql.com/mysql%0A> > > To unsubscribe: http://lists.mysql.com/mysql < > http://lists.mysql.com/mysql%0A> > > > --=20 Claudio --f46d0408d3bf2c9fb704bf9c3d61--