I could resolve the issue following an advice from Ciencia Al Poder.
I contribute the answer here for those who may face the same issue.
Background of the issue: I imported categories from another wiki using Special:Export/Special:Import.
Each category had several subcategories. I hoped that importing category from another wiki would preserve category's hierarchy. But that didn't work. The "categorylinks" table (Manual:categorylinks table) keeps category->subcategory relationships and hierarchy. But that table was not populated properly during the import.
How the issue is resolved: Since I imported lots of templates and categories using Special:Import, the job table (Manual:job table) was populated with 20,000 records. Since one job is normally executed on each page load, regular site visits were not able to run that number of jobs in a short period of time. So I run php maintenance/runJobs.php script (Manual:RunJobs.php) manually two times to be able to execute all jobs in the queue. After that, I got all categories linked to each other in a hierarchy.