forked from pingcap/tidb
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bench_test.go
1855 lines (1803 loc) · 62 KB
/
bench_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Copyright 2016 PingCAP, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package session
import (
"context"
"fmt"
"math/rand"
"strconv"
"strings"
"testing"
"time"
"github.com/pingcap/log"
"github.com/pingcap/tidb/config"
"github.com/pingcap/tidb/domain"
"github.com/pingcap/tidb/executor"
"github.com/pingcap/tidb/infoschema"
"github.com/pingcap/tidb/kv"
"github.com/pingcap/tidb/store/mockstore"
"github.com/pingcap/tidb/types"
"github.com/pingcap/tidb/util/benchdaily"
"github.com/pingcap/tidb/util/chunk"
"github.com/pingcap/tidb/util/logutil"
"github.com/pingcap/tidb/util/sqlexec"
"go.uber.org/zap"
"go.uber.org/zap/zapcore"
)
var smallCount = 100
var bigCount = 10000
func prepareBenchSession() (Session, *domain.Domain, kv.Storage) {
config.UpdateGlobal(func(cfg *config.Config) {
cfg.Log.EnableSlowLog.Store(false)
})
store, err := mockstore.NewMockStore()
if err != nil {
logutil.BgLogger().Fatal(err.Error())
}
domain, err := BootstrapSession(store)
if err != nil {
logutil.BgLogger().Fatal(err.Error())
}
log.SetLevel(zapcore.ErrorLevel)
se, err := CreateSession4Test(store)
if err != nil {
logutil.BgLogger().Fatal(err.Error())
}
mustExecute(se, "use test")
return se, domain, store
}
func prepareBenchData(se Session, colType string, valueFormat string, valueCount int) {
mustExecute(se, "drop table if exists t")
mustExecute(se, fmt.Sprintf("create table t (pk int primary key auto_increment, col %s, index idx (col))", colType))
mustExecute(se, "begin")
for i := 0; i < valueCount; i++ {
mustExecute(se, "insert t (col) values ("+fmt.Sprintf(valueFormat, i)+")")
}
mustExecute(se, "commit")
}
func prepareSortBenchData(se Session, colType string, valueFormat string, valueCount int) {
mustExecute(se, "drop table if exists t")
mustExecute(se, fmt.Sprintf("create table t (pk int primary key auto_increment, col %s)", colType))
mustExecute(se, "begin")
r := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < valueCount; i++ {
if i%1000 == 0 {
mustExecute(se, "commit")
mustExecute(se, "begin")
}
mustExecute(se, "insert t (col) values ("+fmt.Sprintf(valueFormat, r.Intn(valueCount))+")")
}
mustExecute(se, "commit")
}
func prepareJoinBenchData(se Session, colType string, valueFormat string, valueCount int) {
mustExecute(se, "drop table if exists t")
mustExecute(se, fmt.Sprintf("create table t (pk int primary key auto_increment, col %s)", colType))
mustExecute(se, "begin")
for i := 0; i < valueCount; i++ {
mustExecute(se, "insert t (col) values ("+fmt.Sprintf(valueFormat, i)+")")
}
mustExecute(se, "commit")
}
func readResult(ctx context.Context, rs sqlexec.RecordSet, count int) {
req := rs.NewChunk(nil)
for count > 0 {
err := rs.Next(ctx, req)
if err != nil {
logutil.Logger(ctx).Fatal("read result failed", zap.Error(err))
}
if req.NumRows() == 0 {
logutil.Logger(ctx).Fatal(strconv.Itoa(count))
}
count -= req.NumRows()
}
rs.Close()
}
func BenchmarkBasic(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select 1")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkTableScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%v", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], smallCount)
}
b.StopTimer()
}
func BenchmarkExplainTableScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%v", 0)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "explain select * from t")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkTableLookup(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%d", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where pk = 64")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkExplainTableLookup(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%d", 0)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "explain select * from t where pk = 64")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkStringIndexScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "varchar(255)", "'hello %d'", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col > 'hello'")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], smallCount)
}
b.StopTimer()
}
func BenchmarkExplainStringIndexScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "varchar(255)", "'hello %d'", 0)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "explain select * from t where col > 'hello'")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkPointGet(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, "create table t (pk int primary key)")
mustExecute(se, "insert t values (61),(62),(63),(64)")
b.ResetTimer()
alloc := chunk.NewAllocator()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where pk = 64")
if err != nil {
b.Fatal(err)
}
_, err = drainRecordSet(ctx, se.(*session), rs[0], alloc)
if err != nil {
b.Fatal(err)
}
alloc.Reset()
}
b.StopTimer()
}
func BenchmarkBatchPointGet(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, "create table t (pk int primary key)")
mustExecute(se, "insert t values (61),(62),(63),(64)")
alloc := chunk.NewAllocator()
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where pk in (61, 64, 67)")
if err != nil {
b.Fatal(err)
}
_, err = drainRecordSet(ctx, se.(*session), rs[0], alloc)
if err != nil {
b.Fatal(err)
}
alloc.Reset()
}
b.StopTimer()
}
func BenchmarkPreparedPointGet(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, "create table t (pk int primary key)")
mustExecute(se, "insert t values (61),(62),(63),(64)")
stmtID, _, _, err := se.PrepareStmt("select * from t where pk = ?")
if err != nil {
b.Fatal(err)
}
alloc := chunk.NewAllocator()
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.ExecutePreparedStmt(ctx, stmtID, []types.Datum{types.NewDatum(64)})
if err != nil {
b.Fatal(err)
}
_, err = drainRecordSet(ctx, se.(*session), rs, alloc)
if err != nil {
b.Fatal(err)
}
alloc.Reset()
}
b.StopTimer()
}
func BenchmarkStringIndexLookup(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "varchar(255)", "'hello %d'", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col = 'hello 64'")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkIntegerIndexScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%v", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col >= 0")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], smallCount)
}
b.StopTimer()
}
func BenchmarkIntegerIndexLookup(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "int", "%v", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col = 64")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkDecimalIndexScan(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "decimal(32,6)", "%v.1234", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col >= 0")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], smallCount)
}
b.StopTimer()
}
func BenchmarkDecimalIndexLookup(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareBenchData(se, "decimal(32,6)", "%v.1234", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t where col = 64.1234")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkInsertWithIndex(b *testing.B) {
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, "drop table if exists t")
mustExecute(se, "create table t (pk int primary key, col int, index idx (col))")
b.ResetTimer()
for i := 0; i < b.N; i++ {
mustExecute(se, fmt.Sprintf("insert t values (%d, %d)", i, i))
}
b.StopTimer()
}
func BenchmarkInsertNoIndex(b *testing.B) {
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, "drop table if exists t")
mustExecute(se, "create table t (pk int primary key, col int)")
b.ResetTimer()
for i := 0; i < b.N; i++ {
mustExecute(se, fmt.Sprintf("insert t values (%d, %d)", i, i))
}
b.StopTimer()
}
func BenchmarkSort(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareSortBenchData(se, "int", "%v", bigCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t order by col limit 50")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 50)
}
b.StopTimer()
}
func BenchmarkJoin(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareJoinBenchData(se, "int", "%v", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t a join t b on a.col = b.col")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], smallCount)
}
b.StopTimer()
}
func BenchmarkJoinLimit(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
prepareJoinBenchData(se, "int", "%v", smallCount)
b.ResetTimer()
for i := 0; i < b.N; i++ {
rs, err := se.Execute(ctx, "select * from t a join t b on a.col = b.col limit 1")
if err != nil {
b.Fatal(err)
}
readResult(ctx, rs[0], 1)
}
b.StopTimer()
}
func BenchmarkPartitionPruning(b *testing.B) {
ctx := context.Background()
se, do, st := prepareBenchSession()
defer func() {
se.Close()
do.Close()
st.Close()
}()
mustExecute(se, `create table t (id int, dt datetime)
partition by range (to_days(dt)) (
partition p0 values less than (737515),
partition p1 values less than (737516),
partition p2 values less than (737517),
partition p3 values less than (737518),
partition p4 values less than (737519),
partition p5 values less than (737520),
partition p6 values less than (737521),
partition p7 values less than (737522),
partition p8 values less than (737523),
partition p9 values less than (737524),
partition p10 values less than (737525),
partition p11 values less than (737526),
partition p12 values less than (737527),
partition p13 values less than (737528),
partition p14 values less than (737529),
partition p15 values less than (737530),
partition p16 values less than (737531),
partition p17 values less than (737532),
partition p18 values less than (737533),
partition p19 values less than (737534),
partition p20 values less than (737535),
partition p21 values less than (737536),
partition p22 values less than (737537),
partition p23 values less than (737538),
partition p24 values less than (737539),
partition p25 values less than (737540),
partition p26 values less than (737541),
partition p27 values less than (737542),
partition p28 values less than (737543),
partition p29 values less than (737544),
partition p30 values less than (737545),
partition p31 values less than (737546),
partition p32 values less than (737547),
partition p33 values less than (737548),
partition p34 values less than (737549),
partition p35 values less than (737550),
partition p36 values less than (737551),
partition p37 values less than (737552),
partition p38 values less than (737553),
partition p39 values less than (737554),
partition p40 values less than (737555),
partition p41 values less than (737556),
partition p42 values less than (737557),
partition p43 values less than (737558),
partition p44 values less than (737559),
partition p45 values less than (737560),
partition p46 values less than (737561),
partition p47 values less than (737562),
partition p48 values less than (737563),
partition p49 values less than (737564),
partition p50 values less than (737565),
partition p51 values less than (737566),
partition p52 values less than (737567),
partition p53 values less than (737568),
partition p54 values less than (737569),
partition p55 values less than (737570),
partition p56 values less than (737571),
partition p57 values less than (737572),
partition p58 values less than (737573),
partition p59 values less than (737574),
partition p60 values less than (737575),
partition p61 values less than (737576),
partition p62 values less than (737577),
partition p63 values less than (737578),
partition p64 values less than (737579),
partition p65 values less than (737580),
partition p66 values less than (737581),
partition p67 values less than (737582),
partition p68 values less than (737583),
partition p69 values less than (737584),
partition p70 values less than (737585),
partition p71 values less than (737586),
partition p72 values less than (737587),
partition p73 values less than (737588),
partition p74 values less than (737589),
partition p75 values less than (737590),
partition p76 values less than (737591),
partition p77 values less than (737592),
partition p78 values less than (737593),
partition p79 values less than (737594),
partition p80 values less than (737595),
partition p81 values less than (737596),
partition p82 values less than (737597),
partition p83 values less than (737598),
partition p84 values less than (737599),
partition p85 values less than (737600),
partition p86 values less than (737601),
partition p87 values less than (737602),
partition p88 values less than (737603),
partition p89 values less than (737604),
partition p90 values less than (737605),
partition p91 values less than (737606),
partition p92 values less than (737607),
partition p93 values less than (737608),
partition p94 values less than (737609),
partition p95 values less than (737610),
partition p96 values less than (737611),
partition p97 values less than (737612),
partition p98 values less than (737613),
partition p99 values less than (737614),
partition p100 values less than (737615),
partition p101 values less than (737616),
partition p102 values less than (737617),
partition p103 values less than (737618),
partition p104 values less than (737619),
partition p105 values less than (737620),
partition p106 values less than (737621),
partition p107 values less than (737622),
partition p108 values less than (737623),
partition p109 values less than (737624),
partition p110 values less than (737625),
partition p111 values less than (737626),
partition p112 values less than (737627),
partition p113 values less than (737628),
partition p114 values less than (737629),
partition p115 values less than (737630),
partition p116 values less than (737631),
partition p117 values less than (737632),
partition p118 values less than (737633),
partition p119 values less than (737634),
partition p120 values less than (737635),
partition p121 values less than (737636),
partition p122 values less than (737637),
partition p123 values less than (737638),
partition p124 values less than (737639),
partition p125 values less than (737640),
partition p126 values less than (737641),
partition p127 values less than (737642),
partition p128 values less than (737643),
partition p129 values less than (737644),
partition p130 values less than (737645),
partition p131 values less than (737646),
partition p132 values less than (737647),
partition p133 values less than (737648),
partition p134 values less than (737649),
partition p135 values less than (737650),
partition p136 values less than (737651),
partition p137 values less than (737652),
partition p138 values less than (737653),
partition p139 values less than (737654),
partition p140 values less than (737655),
partition p141 values less than (737656),
partition p142 values less than (737657),
partition p143 values less than (737658),
partition p144 values less than (737659),
partition p145 values less than (737660),
partition p146 values less than (737661),
partition p147 values less than (737662),
partition p148 values less than (737663),
partition p149 values less than (737664),
partition p150 values less than (737665),
partition p151 values less than (737666),
partition p152 values less than (737667),
partition p153 values less than (737668),
partition p154 values less than (737669),
partition p155 values less than (737670),
partition p156 values less than (737671),
partition p157 values less than (737672),
partition p158 values less than (737673),
partition p159 values less than (737674),
partition p160 values less than (737675),
partition p161 values less than (737676),
partition p162 values less than (737677),
partition p163 values less than (737678),
partition p164 values less than (737679),
partition p165 values less than (737680),
partition p166 values less than (737681),
partition p167 values less than (737682),
partition p168 values less than (737683),
partition p169 values less than (737684),
partition p170 values less than (737685),
partition p171 values less than (737686),
partition p172 values less than (737687),
partition p173 values less than (737688),
partition p174 values less than (737689),
partition p175 values less than (737690),
partition p176 values less than (737691),
partition p177 values less than (737692),
partition p178 values less than (737693),
partition p179 values less than (737694),
partition p180 values less than (737695),
partition p181 values less than (737696),
partition p182 values less than (737697),
partition p183 values less than (737698),
partition p184 values less than (737699),
partition p185 values less than (737700),
partition p186 values less than (737701),
partition p187 values less than (737702),
partition p188 values less than (737703),
partition p189 values less than (737704),
partition p190 values less than (737705),
partition p191 values less than (737706),
partition p192 values less than (737707),
partition p193 values less than (737708),
partition p194 values less than (737709),
partition p195 values less than (737710),
partition p196 values less than (737711),
partition p197 values less than (737712),
partition p198 values less than (737713),
partition p199 values less than (737714),
partition p200 values less than (737715),
partition p201 values less than (737716),
partition p202 values less than (737717),
partition p203 values less than (737718),
partition p204 values less than (737719),
partition p205 values less than (737720),
partition p206 values less than (737721),
partition p207 values less than (737722),
partition p208 values less than (737723),
partition p209 values less than (737724),
partition p210 values less than (737725),
partition p211 values less than (737726),
partition p212 values less than (737727),
partition p213 values less than (737728),
partition p214 values less than (737729),
partition p215 values less than (737730),
partition p216 values less than (737731),
partition p217 values less than (737732),
partition p218 values less than (737733),
partition p219 values less than (737734),
partition p220 values less than (737735),
partition p221 values less than (737736),
partition p222 values less than (737737),
partition p223 values less than (737738),
partition p224 values less than (737739),
partition p225 values less than (737740),
partition p226 values less than (737741),
partition p227 values less than (737742),
partition p228 values less than (737743),
partition p229 values less than (737744),
partition p230 values less than (737745),
partition p231 values less than (737746),
partition p232 values less than (737747),
partition p233 values less than (737748),
partition p234 values less than (737749),
partition p235 values less than (737750),
partition p236 values less than (737751),
partition p237 values less than (737752),
partition p238 values less than (737753),
partition p239 values less than (737754),
partition p240 values less than (737755),
partition p241 values less than (737756),
partition p242 values less than (737757),
partition p243 values less than (737758),
partition p244 values less than (737759),
partition p245 values less than (737760),
partition p246 values less than (737761),
partition p247 values less than (737762),
partition p248 values less than (737763),
partition p249 values less than (737764),
partition p250 values less than (737765),
partition p251 values less than (737766),
partition p252 values less than (737767),
partition p253 values less than (737768),
partition p254 values less than (737769),
partition p255 values less than (737770),
partition p256 values less than (737771),
partition p257 values less than (737772),
partition p258 values less than (737773),
partition p259 values less than (737774),
partition p260 values less than (737775),
partition p261 values less than (737776),
partition p262 values less than (737777),
partition p263 values less than (737778),
partition p264 values less than (737779),
partition p265 values less than (737780),
partition p266 values less than (737781),
partition p267 values less than (737782),
partition p268 values less than (737783),
partition p269 values less than (737784),
partition p270 values less than (737785),
partition p271 values less than (737786),
partition p272 values less than (737787),
partition p273 values less than (737788),
partition p274 values less than (737789),
partition p275 values less than (737790),
partition p276 values less than (737791),
partition p277 values less than (737792),
partition p278 values less than (737793),
partition p279 values less than (737794),
partition p280 values less than (737795),
partition p281 values less than (737796),
partition p282 values less than (737797),
partition p283 values less than (737798),
partition p284 values less than (737799),
partition p285 values less than (737800),
partition p286 values less than (737801),
partition p287 values less than (737802),
partition p288 values less than (737803),
partition p289 values less than (737804),
partition p290 values less than (737805),
partition p291 values less than (737806),
partition p292 values less than (737807),
partition p293 values less than (737808),
partition p294 values less than (737809),
partition p295 values less than (737810),
partition p296 values less than (737811),
partition p297 values less than (737812),
partition p298 values less than (737813),
partition p299 values less than (737814),
partition p300 values less than (737815),
partition p301 values less than (737816),
partition p302 values less than (737817),
partition p303 values less than (737818),
partition p304 values less than (737819),
partition p305 values less than (737820),
partition p306 values less than (737821),
partition p307 values less than (737822),
partition p308 values less than (737823),
partition p309 values less than (737824),
partition p310 values less than (737825),
partition p311 values less than (737826),
partition p312 values less than (737827),
partition p313 values less than (737828),
partition p314 values less than (737829),
partition p315 values less than (737830),
partition p316 values less than (737831),
partition p317 values less than (737832),
partition p318 values less than (737833),
partition p319 values less than (737834),
partition p320 values less than (737835),
partition p321 values less than (737836),
partition p322 values less than (737837),
partition p323 values less than (737838),
partition p324 values less than (737839),
partition p325 values less than (737840),
partition p326 values less than (737841),
partition p327 values less than (737842),
partition p328 values less than (737843),
partition p329 values less than (737844),
partition p330 values less than (737845),
partition p331 values less than (737846),
partition p332 values less than (737847),
partition p333 values less than (737848),
partition p334 values less than (737849),
partition p335 values less than (737850),
partition p336 values less than (737851),
partition p337 values less than (737852),
partition p338 values less than (737853),
partition p339 values less than (737854),
partition p340 values less than (737855),
partition p341 values less than (737856),
partition p342 values less than (737857),
partition p343 values less than (737858),
partition p344 values less than (737859),
partition p345 values less than (737860),
partition p346 values less than (737861),
partition p347 values less than (737862),
partition p348 values less than (737863),
partition p349 values less than (737864),
partition p350 values less than (737865),
partition p351 values less than (737866),
partition p352 values less than (737867),
partition p353 values less than (737868),
partition p354 values less than (737869),
partition p355 values less than (737870),
partition p356 values less than (737871),
partition p357 values less than (737872),
partition p358 values less than (737873),
partition p359 values less than (737874),
partition p360 values less than (737875),
partition p361 values less than (737876),
partition p362 values less than (737877),
partition p363 values less than (737878),
partition p364 values less than (737879),
partition p365 values less than (737880),
partition p366 values less than (737881),
partition p367 values less than (737882),
partition p368 values less than (737883),
partition p369 values less than (737884),
partition p370 values less than (737885),
partition p371 values less than (737886),
partition p372 values less than (737887),
partition p373 values less than (737888),
partition p374 values less than (737889),
partition p375 values less than (737890),
partition p376 values less than (737891),
partition p377 values less than (737892),
partition p378 values less than (737893),
partition p379 values less than (737894),
partition p380 values less than (737895),
partition p381 values less than (737896),
partition p382 values less than (737897),
partition p383 values less than (737898),
partition p384 values less than (737899),
partition p385 values less than (737900),
partition p386 values less than (737901),
partition p387 values less than (737902),
partition p388 values less than (737903),
partition p389 values less than (737904),
partition p390 values less than (737905),
partition p391 values less than (737906),
partition p392 values less than (737907),
partition p393 values less than (737908),
partition p394 values less than (737909),
partition p395 values less than (737910),
partition p396 values less than (737911),
partition p397 values less than (737912),
partition p398 values less than (737913),
partition p399 values less than (737914),
partition p400 values less than (737915),
partition p401 values less than (737916),
partition p402 values less than (737917),
partition p403 values less than (737918),
partition p404 values less than (737919),
partition p405 values less than (737920),
partition p406 values less than (737921),
partition p407 values less than (737922),
partition p408 values less than (737923),
partition p409 values less than (737924),
partition p410 values less than (737925),
partition p411 values less than (737926),
partition p412 values less than (737927),
partition p413 values less than (737928),
partition p414 values less than (737929),
partition p415 values less than (737930),
partition p416 values less than (737931),
partition p417 values less than (737932),
partition p418 values less than (737933),
partition p419 values less than (737934),
partition p420 values less than (737935),
partition p421 values less than (737936),
partition p422 values less than (737937),
partition p423 values less than (737938),
partition p424 values less than (737939),
partition p425 values less than (737940),
partition p426 values less than (737941),
partition p427 values less than (737942),
partition p428 values less than (737943),
partition p429 values less than (737944),
partition p430 values less than (737945),
partition p431 values less than (737946),
partition p432 values less than (737947),
partition p433 values less than (737948),
partition p434 values less than (737949),
partition p435 values less than (737950),
partition p436 values less than (737951),
partition p437 values less than (737952),
partition p438 values less than (737953),
partition p439 values less than (737954),
partition p440 values less than (737955),
partition p441 values less than (737956),
partition p442 values less than (737957),
partition p443 values less than (737958),
partition p444 values less than (737959),
partition p445 values less than (737960),
partition p446 values less than (737961),
partition p447 values less than (737962),
partition p448 values less than (737963),
partition p449 values less than (737964),
partition p450 values less than (737965),
partition p451 values less than (737966),
partition p452 values less than (737967),
partition p453 values less than (737968),
partition p454 values less than (737969),
partition p455 values less than (737970),
partition p456 values less than (737971),