Находит счетчик строк "Первый Pattern ", затем использует head для отображения строк над ним, пропускает через tac и обрабатывает его.
head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2"
Например.
head --lines=+6 file | tac | grep -m1 "Pattern2"
Это более надежно, чем использование -m 1000000 в grep. Поскольку скорость важна для OP, я проверил время выполнения, и он также оказался быстрее, чем все другие текущие ответы (в моей системе)
wc -l file
25910209 file
time awk '/Pattern2/ {line=$0; next}; /First Pattern/ {print line; exit}' file
Pattern2:TheRightBar
real 0m2.881s
user 0m2.844s
sys 0m0.036s
time sed '/Pattern2/h;/First Pattern/!d;x;/Pattern2/!d;q' file
Pattern2:TheRightBar
real 0m5.218s
user 0m5.192s
sys 0m0.024s
time (grep -m1 "First Pattern" file -B 10000000 | tac | grep -m1 "Pattern2")
real 0m0.624s
user 0m0.552s
sys 0m0.124s
time (head --lines=+"$(grep -nm1 "First Pattern" file | cut -d\: -f1)" file | tac | grep -m1 "Pattern2")
Pattern2:TheRightBar
real 0m0.586s
user 0m0.528s
sys 0m0.160s