/ Check-in [67d6c42d]
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

 ```448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 ... 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 ... 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 ... 568 569 570 571 572 573 574 ``` ``` + ((ind-1)/27) * 27 + lp + ((lp-1) / 3) * 6, 1) ) ) SELECT s FROM x WHERE ind=0; } {534678912672195348198342567859761423426853791713924856961537284287419635345286179} # Test cases to illustrate on the ORDER BY clause on a recursive query can be # used to control depth-first versus breath-first search in a tree. # do_execsql_test 9.1 { CREATE TABLE org( name TEXT PRIMARY KEY, boss TEXT REFERENCES org ) WITHOUT ROWID; INSERT INTO org VALUES('Alice',NULL); INSERT INTO org VALUES('Bob','Alice'); INSERT INTO org VALUES('Cindy','Alice'); ................................................................................ .........Mary .........Noland .........Olivia}} # The previous query used "ORDER BY level" to yield a breath-first search. # Change that to "ORDER BY level DESC" for a depth-first search. # do_execsql_test 9.2 { WITH RECURSIVE under_alice(name,level) AS ( VALUES('Alice','0') UNION ALL SELECT org.name, under_alice.level+1 FROM org, under_alice WHERE org.boss=under_alice.name ................................................................................ ......Gail .........Noland .........Olivia}} # Without an ORDER BY clause, the recursive query should use a FIFO, # resulting in a breath-first search. # do_execsql_test 9.3 { WITH RECURSIVE under_alice(name,level) AS ( VALUES('Alice','0') UNION ALL SELECT org.name, under_alice.level+1 FROM org, under_alice WHERE org.boss=under_alice.name ................................................................................ .........Kate .........Lanny .........Mary .........Noland .........Olivia}} finish_test ``` ``` > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | > ``` ```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 ... 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 ... 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 ... 722 723 724 725 726 727 728 729 ``` ``` + ((ind-1)/27) * 27 + lp + ((lp-1) / 3) * 6, 1) ) ) SELECT s FROM x WHERE ind=0; } {534678912672195348198342567859761423426853791713924856961537284287419635345286179} #-------------------------------------------------------------------------- # Some tests that use LIMIT and OFFSET in the definition of recursive CTEs. # set I [list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] proc limit_test {tn iLimit iOffset} { if {\$iOffset < 0} { set iOffset 0 } if {\$iLimit < 0 } { set result [lrange \$::I \$iOffset end] } else { set result [lrange \$::I \$iOffset [expr \$iLimit+\$iOffset-1]] } uplevel [list do_execsql_test \$tn [subst -nocommands { WITH ii(a) AS ( VALUES(1) UNION ALL SELECT a+1 FROM ii WHERE a<20 LIMIT \$iLimit OFFSET \$iOffset ) SELECT * FROM ii }] \$result] } limit_test 9.1 20 0 limit_test 9.2 0 0 limit_test 9.3 19 1 limit_test 9.4 20 -1 limit_test 9.5 5 5 limit_test 9.6 0 -1 limit_test 9.7 40 -1 limit_test 9.8 -1 -1 limit_test 9.9 -1 -1 #-------------------------------------------------------------------------- # Test the ORDER BY clause on recursive tables. # do_execsql_test 10.1 { DROP TABLE IF EXISTS tree; CREATE TABLE tree(id INTEGER PRIMARY KEY, parentid, payload); } proc insert_into_tree {L} { db eval { DELETE FROM tree } foreach key \$L { unset -nocomplain parentid foreach seg [split \$key /] { if {\$seg==""} continue set id [db one { SELECT id FROM tree WHERE parentid IS \$parentid AND payload=\$seg }] if {\$id==""} { db eval { INSERT INTO tree VALUES(NULL, \$parentid, \$seg) } set parentid [db last_insert_rowid] } else { set parentid \$id } } } } insert_into_tree { /a/a/a /a/b/c /a/b/c/d /a/b/d } do_execsql_test 10.2 { WITH flat(fid, p) AS ( SELECT id, '/' || payload FROM tree WHERE parentid IS NULL UNION ALL SELECT id, p || '/' || payload FROM flat, tree WHERE parentid=fid ) SELECT p FROM flat ORDER BY p; } { /a /a/a /a/a/a /a/b /a/b/c /a/b/c/d /a/b/d } # Scan the tree-structure currently stored in table tree. Return a list # of nodes visited. # proc scan_tree {bDepthFirst bReverse} { set order "ORDER BY " if {\$bDepthFirst==0} { append order "2 ASC," } if {\$bReverse==0} { append order " 3 ASC" } else { append order " 3 DESC" } db eval " WITH flat(fid, depth, p) AS ( SELECT id, 1, '/' || payload FROM tree WHERE parentid IS NULL UNION ALL SELECT id, depth+1, p||'/'||payload FROM flat, tree WHERE parentid=fid \$order ) SELECT p FROM flat; " } insert_into_tree { /a/b /a/b/c /a/d /a/d/e /a/d/f /g/h } # Breadth first, siblings in ascending order. # do_test 10.3 { scan_tree 0 0 } [list {*}{ /a /g /a/b /a/d /g/h /a/b/c /a/d/e /a/d/f }] # Depth first, siblings in ascending order. # do_test 10.4 { scan_tree 1 0 } [list {*}{ /a /a/b /a/b/c /a/d /a/d/e /a/d/f /g /g/h }] # Breadth first, siblings in descending order. # do_test 10.5 { scan_tree 0 1 } [list {*}{ /g /a /g/h /a/d /a/b /a/d/f /a/d/e /a/b/c }] # Depth first, siblings in ascending order. # do_test 10.6 { scan_tree 1 1 } [list {*}{ /g /g/h /a /a/d /a/d/f /a/d/e /a/b /a/b/c }] # Test cases to illustrate on the ORDER BY clause on a recursive query can be # used to control depth-first versus breath-first search in a tree. # do_execsql_test 11.1 { CREATE TABLE org( name TEXT PRIMARY KEY, boss TEXT REFERENCES org ) WITHOUT ROWID; INSERT INTO org VALUES('Alice',NULL); INSERT INTO org VALUES('Bob','Alice'); INSERT INTO org VALUES('Cindy','Alice'); ................................................................................ .........Mary .........Noland .........Olivia}} # The previous query used "ORDER BY level" to yield a breath-first search. # Change that to "ORDER BY level DESC" for a depth-first search. # do_execsql_test 11.2 { WITH RECURSIVE under_alice(name,level) AS ( VALUES('Alice','0') UNION ALL SELECT org.name, under_alice.level+1 FROM org, under_alice WHERE org.boss=under_alice.name ................................................................................ ......Gail .........Noland .........Olivia}} # Without an ORDER BY clause, the recursive query should use a FIFO, # resulting in a breath-first search. # do_execsql_test 11.3 { WITH RECURSIVE under_alice(name,level) AS ( VALUES('Alice','0') UNION ALL SELECT org.name, under_alice.level+1 FROM org, under_alice WHERE org.boss=under_alice.name ................................................................................ .........Kate .........Lanny .........Mary .........Noland .........Olivia}} finish_test ```