0

I have MySQL table like this

|-----------------------------|
|IDENTIFIER | POINT1 | POINT2 |
|-----------------------------|
| NAME1     | AA1    | BB1    |
| NAME2     | AA1    | BB2    |
| NAME3     | AA1    | BB3    |
| NAME4     | BB2    | CC1    |
| NAME5     | BB1    | BB2    |
| NAME6     | AA1    | CC1    |
| NAME7     | CC1    | BB1    |
| NAME8     | BB2    | BB3    |
| NAME9     | CC1    | BB3    |
|-----------------------------|

and this procedure to find all possible ways in table

DELIMITER $$

USE `test`$$
DROP PROCEDURE IF EXISTS `FindWays`$$

CREATE DEFINER=`root`@`localhost` PROCEDURE `FindWays`(IN MY_START VARCHAR (20),  IN MY_FINISH VARCHAR (20),  IN WAY TEXT,  IN PROHIBITED_POINTS TEXT,IN CYCLE INTEGER,IN MAXCYCLES INTEGER)
BEGIN
  /* define variables */ 
  DECLARE MYNAME VARCHAR(20); /* IDENTIFIER */
  DECLARE ROW1 VARCHAR(20); /* POINT1 */
  DECLARE ROW2 VARCHAR(20); /* POINT2 */
  DECLARE TMP_PROHIBITED TEXT; 
  DECLARE TMP_WAY TEXT;
  DECLARE FINISHED INTEGER DEFAULT 0;
  DECLARE TMP_CYCLE INTEGER DEFAULT 1;
  /* cursor (select) */
  DECLARE curs CURSOR FOR SELECT IDENTIFIER , POINT1 , POINT2  FROM my_table 
    WHERE (POINT1  = MY_START OR POINT2  = MY_START) AND PROHIBITED_POINTS NOT LIKE CONCAT('%',IDENTIFIER,'%') ORDER BY IDENTIFIER ASC;
  /* handler to controll loop */
  DECLARE CONTINUE HANDLER FOR NOT FOUND SET FINISHED = 1;  
  
    
  OPEN curs;
  SET TMP_CYCLE = TMP_CYCLE + CYCLE;
  TreeLoop: LOOP
    FETCH curs INTO MYNAME,ROW1,ROW2;
    /* finish loop if no rows or MAXCYCLES */
    IF FINISHED = 1 OR CYCLE = MAXCYCLES THEN 
    LEAVE TreeLoop;
    END IF;
    /*IF first loop set without comma*/  
    IF LENGTH(WAY)>0 THEN
      SET TMP_PROHIBITED = CONCAT(PROHIBITED_POINTS,",",MYNAME);
      SET TMP_WAY = CONCAT(WAY,',',MYNAME);
    ELSE
      SET TMP_PROHIBITED = MYNAME;
      SET TMP_WAY = MYNAME;
    END IF;
    /* if first way then do at least one iteration*/   
    IF (ROW1 = MY_FINISH OR ROW2 = MY_FINISH) AND LENGTH(WAY)>0 THEN
      INSERT INTO resulTable VALUES (TMP_WAY);
      SET FINISHED = 1;
    ELSE
      IF ROW1 = MY_START THEN 
        CALL FindWays (ROW2,  MY_FINISH, TMP_WAY ,  TMP_PROHIBITED,TMP_CYCLE,MAXCYCLES);
      ELSE 
        CALL FindWays (ROW1,  MY_FINISH, TMP_WAY ,  TMP_PROHIBITED,TMP_CYCLE,MAXCYCLES);
      END IF;    
    END IF;
  END LOOP TreeLoop;       
  CLOSE curs;
END$$

DELIMITER ;

procedure working as expected just is too slow. Procedure is called like CALL FindWays('AA1','AA1','','',0,5) The result is something like this (Circle ways)

Row1: NAME1,NAME5,NAME2
Row2: NAME1,NAME5,NAME8,NAME3
Row3: NAME1,NAME5,NAME8,NAME9,NAME6

When I have in table around 1000 rows and set MAXCYCLES to 5 it takes around 4 mins, with MAXCYCLES = 10 after half hour i had around 30000 possible ways but it was not finished.

So I think its really slow (+/- 20 ways per second).

Have someone any idea how to optimise it? (MySQL: 10.5.9-MariaDB, source and result tables are MEMORY)

4
  • to find all possibilities takes time, that why railroaids and buses make their new plans once or twice a year even with big computers. but i think you can do mariadb.com/kb/en/with a recursive cte. – nbk Apr 10 at 10:50
  • looks interesting, but with my knowledge its too hard to imagine how to use it for now, can you make example for my case pls? – Andy Apr 10 at 12:10
  • you must first get a clear id what you are making as you noticed with the increasing time spent you have a exponentially function which basically goes to infinity. i think i didn't make that clear i my first comment. you can find many example that help you build such a tree, but you need to have an exeon the depths you want. – nbk Apr 10 at 12:25
  • Look at this fiddle. It performs the task similar to your one. – Akina Apr 10 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.