This is how I do it - which uses Ivy. I use it in a currently 1.2 MB file containing the names of students and classes (I teach Business English online to Chinese professionals). I looked around for quite a while to find a way to efficiently insert internal links, the link completion didn't seem to work very well. This article contains the code for the technique I use. It does take a few seconds to find it given the size of the file but I can tolerate that.
Edited to add code.
First, you need to install Ivy (I also installed the related tools Counsel and Swiper). I used Elpa to do this.
I also installed worf as this code uses it:
Then based on the linked article, I added the following code to init.el:
(setq ivy-count-format "(%d/%d) ")
(global-set-key (kbd "C-s") 'swiper)
(defun bjm/worf-insert-internal-link ()
"Use ivy to insert a link to a heading in the current `org-mode' document. Code is based on `worf-goto'."
(let ((cands (worf--goto-candidates)))
(ivy-read "Heading: " cands
(defun bjm/worf-insert-internal-link-action (x)
"Insert link for `bjm/worf-insert-internal-link'"
;; go to heading
(goto-char (cdr x))
;; store link
;; return to original point and insert link
;; org-insert-last-stored-link adds a newline so delete this
;; this is the key that I decided to use to call this function
(global-set-key (kbd "C-c v") (quote bjm/worf-insert-internal-link))